硬件上除了支持请求分页词组管理的内存和外存外，还要有相应的页表和地址转换机制，以及出现缺页时的中断处理机制。
 页表
 基本页式存储管理系统，中业边儿是包含页号和物理块两项。请求分页存储管理中经常只有一部分页面在内存中，因此业表不但需要记录哪些页面在内容那些页面再外存，而且要记录页面的外存位置，以便当某个需要的页面不存在内存时，系统能立即找到它并把它装入内存。因此请求分页存储管理方式需要对页表进行扩充。增加状态为外孙地址访问类和修改为的信息。

请求分页中的硬件支持
 1.页表机制
 ●基本作用:地址转换
 ●增加页表字段，供程序在换入换出时参考
 
 状态位P:用于指示该页是否已调入内存
 访问字段A:记录本页在一段时间内被访问的次数
 修改位M:该页在调入内存后是否被修改过
 外存地址：指示该页在外存上的地址（物理块号）
 2.缺页中断机构:
 ●缺页中断与其他中断的不同:
 (1)在指令执行期间产生和处理中断信号
 (2)一条指令在执行期间可能产生多次缺页中断
 
 3.地址变换机构
 
 内存分配策略和分配算法
 1.最小物理块数的确定:
 ●保证进程正常运行所需的最小物理块数;
 ●与硬件结构有关，取决于指令的格式、功能和寻址方式。
 2.物理块的分配策略:
 ●两种内存分配策略:
 ■固定分配:为进程分配的物理块数固定不变。
 ■可变分配:先为每个进程分配一定 数目的物理块，若发生缺页中断，再增加物理块数。
 ●两种置换策略:
 ■局部置换:只能将自己的某个内存页换出。
 ■全局置换：可将系统中任一进程的内存页换出。
 ●组合出以下三种适用策略:
 ■(1) 固定分配局部置换
 ■(2) 可变分配全局置换
 ■(3)可变分配局部置换
 3.物理块分配算法:
 ●(1)平均分配算法
 ●(2)按比例分配算法:根据进程大小按比例分
 配（Si/s）*m (m:物理块总数，S:各进程页面总数)
 ●(3)考虑优先权的分配算法:一-部分按比例分配;另一部分为优先权高的进程增加分配份额
 调页策略
 1.调入页面的时机:
 ●预调页策略:进程首次调入内存时，由程序员指出应该先调入哪些页。
 ●请求调页策略:进程运行中发生缺页时，提出请求，由OS将其所需页面调入内存。
 2.确定从何处调入页面:
 请求分页系统将外存分为两部分:
 文件区(离散分配)、 对换区(连续分配)
 ●发生缺页请求时，有以下三种情况:
 系统拥有足够的对换区空间
 系统缺少足够的对换区空间
 UNIX方式
 3.页面调入过程:
 ①若发生缺页，便向CPU发出缺页中断
 ②中断处理程序保存CPU环境，转中断处理程序
 ③该程序查找页表，得到该页在外存中的块号
 ④若内存未满，启动磁盘I/O调入页面;若内存已满，先置换再调入
 ⑤修改页表项内容，并写入快表。

 
 
 
一、实验目的与要求
 
掌握分页存储管理的基本原理及分页存储管理中的地址变换过程，编制一个模拟地址变换过程的程序并能采用先进先出页面置换算法实现页面置换。
 
 
二、实验内容
 
１、复习分页存储管理的基本概念、基本原理、及地址变换过程。
 ２、编制一个模拟地址变换过程并能进行缺页中断处理和页面置换的程序。
 
 
三、实验原理
 
在页式内存管理中，将程序空间分成大小相同的页，物理内存空间也分成大小相同的块，页的大小和块的大小一致。当程序装入内存准备运行时，逻辑上连续的页可以装入不连续的物理块中（当然也可以是连续的物理块）。
 
程序执行时，为了正确地访问内存物理地址，需要使用页表，该表在创建进程由操作系统在内存特定区域创建，并根据当时的内存分配情况，动态地将程序中的各页装入内存的空闲块中，并填上页表。
 
在支持页式管理的系统中，为了加快地址映射速度，通常都把页表的全部或一部分放在快表中，由硬件自动完成地址映射过程。程序的逻辑地址可表示为：P W
 
其中P为页号，W为页内位移。假设块或页的大小为2nB（n为整数），则W的取值范围为0-2n-1。 给定一个逻辑地址LA，可以用两种方法得到P和W。
 （1）P=LA>>n，W=LA&(2n-1)
 （2）P=INT(LA/2n) ，W=LA % 2n
 
当取得页号P 后查页表，能得到这一页装在内存中的块号B，可采用两种方法计算物理地址PA。
 （1）PA=(B<<n)|W
 （2）PA=B×2n+W 由于在CPU执行逻辑指令的速度远高于执行算术指令的，故采用方法一进行地址映射。
 
在进程执行的过程中，如果访问的页暂时不在内存，便产生缺页中断，由操作系统负责把所缺的页从外存调入内存，然后再重复执行产生缺页中断的指令，从而实现请求页式管理。
 
在调页的过程中，如果内存还有空闲的物理块时，当然可以给该进程追加内存分配；如果当内存中没有空闲的物理块时就需要淘汰一个当前在内存的“老页”，这个“老页”可以属于该进程本身，也可能属于别的进程。为了降低置换算法的复杂性而又不对其它进程产生影响，本实验采用前者，即局部置换方法。这样便可以在一个比较小的内存空间里运行一个较大的进程，从而实现虚拟存储器。
 
 
四、程序代码
 
#include <bits/stdc++.h>
using namespace std;
#define m 3				//实际为该作业分配的主存块块数
#define page_length 5	//页表实际长度
struct  //页表
{
	int lnumber;	//页号
	int pnumber;	//该页所在主存块的块号
	int flag;		//状态位,"1"表示该页在主存,"0"表示该页不在主存
	int write;		//修改位,"1"表示该页内容被修改过,"0"表示该页内容末修改过
	int dnumber;	//该页存在外存位置,即磁盘块号
}page[page_length];
int p[m];			//存放在主存中页的页号
int head;			//主存中页号队列p首指针

void page_interrupt(int lnumber) /*缺页中断处理函数，采用FIFO页面置换算法*/
{
  int j;
  printf("发生缺页中断* %d\n",lnumber);
  /*淘汰页*/
  j=p[head];
  p[head]=lnumber;/* 装入替换后的新页号*/
  head=(head+1)%m;
  if (page[j].write==1)
  printf("将页 %d写回磁盘第%d块\n",j,page[j].dnumber);
  /*修改页表*/
  page[j].flag=0;/* 第j页被换出，第j页存在标志改为"0"*/
  page[lnumber].pnumber=page[j].pnumber;/* 第lnumber页装入原来第j页所在的物理块*/
  page[lnumber].flag=1;/* 第lnumber页存在标志改为"1"*/
  page[lnumber].write=0;/* 第lunmber页修改标志改为"0"*/
  printf("淘汰主存块%2d中的页%2d，从磁盘第%d块中调入页%2d\n", page[j].pnumber,j,page[lnumber].dnumber,lnumber);
}/*缺页中断处理函数结束*/

void command(unsigned laddress,int write) /*命令处理函数*/
{
  unsigned paddress,ad,pnumber;//分别存放物理地址、页内地址和外存地址（盘块号）；
  int lnumber;//存放页号；
  lnumber=laddress>>10;//页号=逻辑地址/2^10                 /*先计算出页号（高6位）和页内地址（低10位）；*/
  ad=laddress%0x3ff;//页内地址利用位运算来取出后10位           
kk:
  if(lnumber>=page_length)    /*判断页号是否越界，若越界，显示越界不再进行地址变换；*/
    {
        printf("超出页长，不存在该页\n");
        return;
    }
    if(page[lnumber].flag==1)   /*若访问的页在内存，查找对应的物理块，计算物理地址；若不在内存，先调用page_interrupt(int lnumber)进行页面置换，再进行地址变换。*/
 
    {
        pnumber=page[lnumber].pnumber;
        paddress=pnumber<<10|ad;
        printf("逻辑地址是:%d,对应物理地址是:%d\n",laddress,paddress);
        if(write==1)
            page[lnumber].write=1;
    }
    else
    {
        page_interrupt(lnumber);
        goto kk;
    }
}

int main()  //主函数
{
	int write;
	unsigned laddress;
	//初始化页表，分配3个物理块。数据可改
	page[0].lnumber=0;page[0].pnumber=4;page[0].flag=1;page[0].write=0;page[0].dnumber=4;
	page[1].lnumber=1;page[1].pnumber=3;page[1].flag=1;page[1].write=0;page[1].dnumber=20;
	page[2].lnumber=2;page[2].pnumber=7;page[2].flag=1;page[2].write=0;page[2].dnumber=18;
	page[3].lnumber=3;page[3].pnumber=0;page[3].flag=0;page[3].write=0;page[3].dnumber=6;
	page[4].lnumber=4;page[4].pnumber=0;page[4].flag=0;page[4].write=0;page[4].dnumber=9;
	head=0;			//开始指向p[0]
	p[0]=0;p[1]=1;p[2]=2;  //3个物理块中所放的页为0页、1页、2页
	cout<<"**********************************"<<endl;
	cout<<"**************23夏旭**************"<<endl;  
	cout<<"**********************************"<<endl; 
	while(1)
	{
		cout<<"输入指令性质(1-写指令,0-读指令,其他--结束程序运行)和逻辑地址:";
		cin>>write;
		cin>>laddress;
		if(write==0||write==1)	command(laddress,write);
		else  break;
	}
}
 
 
五、结果分析
 
 
1、输入 1 500：
 首先取出逻辑地址500的页号（高六位）和页内地址，页号只需移位操作即可得到，页内地址通过逻辑地址与2n-1进行按位与操作即可得到，500移位后的页号为0没有越界，块号为4，块号左移10位后再与页内地址进行按位与操作，就可以得到物理地址：4*1024+500=4596。
 
2、输入 1 3500：
 页号为3，没有越界，但是page[3]对应的flag=0，缺页中断，调用缺页中断处理函数，将原来的p[ ]数组里的首元素淘汰，用一个变量j记录其值，然后将这个位置改为缺页页号，将该缺页页号的flag改为1，表示该页存在主存，将write改为0，表示该页未修改，接着输出被淘汰的页号及其主存块值，新的页号及其主存块值，这样缺页中断函数结束，通过goto kk回到取逻辑地址的页号和页内地址的地方，过程同上，得出页号为3，此时他的快号为4，接着将逻辑地址和2n-1按位与得出页内地址，将快号左移十位在与页内地址按位与得到物理地址：4524
 
3、输入 1 4500：
 页号为4，没有越界，但是page[4]对应的flag为0，即该页不在主存，缺页中断，调用缺页中断处理函数，将原来的p[ ]数组里的首元素淘汰，用一个变量j记录其值，然后将这个位置改为缺页页号，将该缺页页号的flag改为1，表示该页存在主存，将write改为0，表示该页未修改，接着输出被淘汰的页号及其主存块值，新的页号及其主存块值，这样缺页中断函数结束，通过goto kk回到取逻辑地址的页号和页内地址的地方，过程同上，得出页号为4，此时他的快号为3，接着将逻辑地址和2n-1按位与得出页内地址，将快号左移十位在与页内地址按位与得到物理地址： 3476
 
4、输入 1 6000：
 页号为5，越界，结果输出 “超出页长，不存在该页”。
 
 
六、实验小结
 
通过此次实验，我能够编制一个模拟地址变换过程并能进行缺页中断处理和页面置换的程序，更加熟悉分页存储管理的基本原理及分页存储管理中的地址变换过程。了解如何根据当时的内存分配情况，动态地将程序中的各页装入内存的空闲块中，并填上页表等重要的知识。
 

1、离散分配方式
 
----连续分配方式（分区存储管理）要求把作业放在一个连续的存储区中，因而会形成许多“碎片”，固定分区会产生内部碎片，动态分区会产生外部碎片。虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间，但需为之付出很大开销。如果允许将一个进程直接分散的装入到许多不相邻接的分区中，则无需再进行“紧凑”。基于这一思想而产生了离散分配方式。
 
如果离散分配的基本单位是页，则称为分页存储管理方式；
 
如果离散分配的基本单位是段，则称为分段存储管理方式。
 
---- 在分页存储管理方式中，如果不具备页面置换功能，则称为基本的分页存储管理方式，或称为纯分页存储管理方式。它不具有支持实现虚拟存储器的功能，它要求把每个作业全部装入内存后方能运行。
 
也就是说，不具备页面置换功能的基本分页存储管理方式要求把每个作业全部装入内存之后方能运行。
 
2、页面与页表
 
----页面和物理块
 
分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框（frame）,也加以编号，如0#块，1#块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。
 
由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。
 
----页面大小
 
问：页面大小该如何设置？（内存碎片、置换的效率问题、页表长度、内存利用率）
 
在分页系统中的页面大小应适中。
 
页面若太小，粒度比较小一方面虽然可使内存碎片减小，有利于提高内存利用率。但是另一方面页表会比较大，也会使每个进程占用较多的页面，从而导致进程的页表过长（页号->块号），占用大量内存，还会降低页面换进换出的效率。
 
若页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，却又会使页内碎片增大。因此，页面的大小选择应适中，且页面大小应是2的幂，通常为512B~8KB。
 
----地址结构
 
分页地址中的地址结构有两部分：前一部分是页号P，后一部分为页内位移量W（或称为页内地址）。如下图所示：如果逻辑地址空间是2的m次方，页面大小是2的n次方（字节），那么逻辑地址的高m-n位是页号，低n位是页内偏移量。
 

 上述地址结构中，两部分的地址长度为32位，其中0～11位（计12位）为页内偏移量，即每页大小=2^12=4KB;12~31位（计20位）为页号，即（页表项的个数）最多的页数=2^20=1MB。页内偏移量也称为页内位移、页偏移或页内地址等。对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址W可按下式求得： P=INT(A/L)        W=(A)MOD(L)    其中，INT是整除函数，MOD是取余函数。
 
例如，系统的页面大小是1KB（1024B），设A=2170B，则得出P=2，W=2170-2048=122.
 
----页表
 
在分页系统中，允许将进程的各个页离散地存储在内存不同的物理块中，但系统应能保证进程的正确运行，即能在内存中找到每个页面所对应的物理块，为此，系统又为每个进程建立了一张页面映像表，简称页表。
 
在进程地址空间内的所有页（0~n），依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。在配置了页表后，进程执行时，通过查找该页表，即可找到每页在内存中的块号（页框号），页表的作用是实现从页号到物理块号的地址映射。即使在简单的分页系统中，也常在页表的表项中设置一存取控制字段，用于对该存储块中的内容加以保护。
 
-- 当存取控制字段仅有一位时，可用来规定该存储块中的内容是允许读/写，还是只读。
 
-- 当存取控制字段为二位，则可规定为读/写、只读和只执行等存取方式。
 
如果有一进程试图去写一个只允许读的存储块时，将引起操作系统的一次中断。如果要利用分页系统去实现虚拟存储器，还需在页表中增设状态位/修改位等数据项来供页面换进换出参考，具体可看请求分页存储管理方式。http://blog.csdn.net/dongyanxia1000/article/details/51727339 
 
为了实现上面的方便，系统中设置了一个页表寄存器（PTR，Page Table Register），其中存放页表在内存的起始地址F和页表的长度M。进程未执行时，页表的起始地址和长度存放在进程控制块（PCB）中。当进程执行时，才将页表起始地址和长度存入页表寄存器中。
 
假设页面大小为L，页表长度（页表项的个数）为M，逻辑地址A通过地址变换得到物理地址E的过程如下：
 
--1）计算页号P=(int)(A/L)；页内偏移量W=A%L。
 
--2）比较页号P(理论值0~M-1)和页表长度M，若P>= M，则产生越界中断，否则转到下一步执行。(判断是否越界)
 
--3）页表中页号P对应的页表项的地址=页表起始地址F + 页号P x 页表项大小，取出该页表项中的物理块号b的内容。
 
--4）计算E=bxL+W   （页面的大小就是物理块的大小，页内地址就是物理块内的地址）
 
--5）用得到的物理地址E去访问内存。（放到总线，访问内存）
 
以上整个地址变换过程都是由硬件自动完成的。地址变换过程如下图所示：
 
 

 请求分页存储管理方式
 
----- 请求分页系统是建立在基本分页的基础上的，为了能支持虚拟存储器功能而增加了请求调页功能和页面置换功能。
 
相应地，每次调入和换出的基本单位都是长度固定的页面，这使得请求分页系统在实现上要比请求分段系统简单。
 
请求分段系统在换进和换出时是可变长度的段，因此，请求分页便成为目前最常用的一种实现虚拟存储器的方式。
 
请求分页中的硬件支持 
 
-- 为了实现请求分页，系统必须提供一定的硬件支持。除了需要一台具有一定容量的内存及外存的计算机系统外，还需要有页表机制、缺页中断机构以及地址变换机构。
 
1）页表机制
 
在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将用户空间中的逻辑地址变换为内存空间中的物理地址。
 
由于只将应用程序的一部分调入内存，还有一部分仍在盘上，故需在页表中再增加若干项，供程序（数据）在换进、换出时参考。
 
在请求分页系统中的每个页表项如下所示：
 
 
各字段的说明如下：
 
---- 状态位P：用于指示该页是否已调入内存，供程序访问时参考。（“在/不在”位）
 
---- 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。
 
---- 修改位M：表示该页在调入内存后是否被修改过。供置换页面时参考。
 
由于内存中的每一页都在外存上有一份副本，因此，若未被修改，在置换该页时就不需要将该页写回到外存上，直接丢弃，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。
 
---- 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。（页框号）
 
 
 
有的操作系统实现还添加了  
 
 
保护位：指出一个页允许什么类型的访问。读写？读？写？
 
 
TLB禁止位：当前页表项是否禁止TLB？
 
 
2）缺页中断机构
 
-- 在请求分页系统中，每当所要访问的页面不在内存中时，便产生一次缺页中断，请求OS将所缺之页调入内存。
 
-- 缺页中断作为中断，同样需要经历诸如保护CPU现场、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU现场等几个步骤。
 
-- 但缺页中断又是一种特殊的中断，它与一般的中断相比，有着明显的区别，主要表现在下面两个方面：
 
---- 在指令执行期间产生和处理中断信号。通常，CPU都是在一条指令执行完成后，才检查是否有中断请求到达。若有，便去响应，否则，继续执行下一条指令。然而，缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时所产生和处理的。
 
---- 一条指令在执行期间，可能产生多次缺页中断。所以，系统中的硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处继续执行。
 
3）地址变换机构
 
-- 请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，为实现虚拟存储器而增加了某些功能而形成的，
 
如产生和处理缺页中断，以及从内存中换出一页的功能等等。
 
---- 在进行地址变换时，首先去检索快表，试图从中找出所要访问的页。若找到，便修改页表项中的访问位。对于写指令，还需将修改位置成“1”。然后利用页表项中给出的物理块号和页内地址形成物理地址。地址变换过程到此结束。
 
---- 如果在快表中未找到该页的页表项时，应到内存中去查找页表，再根据找到的页表项中的状态位P，了解该页是否已调入内存。
 
---- 若该页已调入内存，这时应将此页的页表项写入快表，当快表已满时，应先调出按某种算法所确定的页的页表项；然后再写入该页的页表项。
 
---- 若该页尚未调入内存，这时应产生缺页中断，请求OS从外存把该页调入内存。
 
 
 

补充：硬失效和软失效
 
软失效：TLB没有、内存有，加载到TLB，利用页表项中给出的物理块号和页内地址形成物理地址。地址变换过程到此结束。
 
硬失效：TLB没有、内存没有，缺页中断，调入缺少的页