一、实验内容

 模拟分页式存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。

二、实验目的

 在计算机系统中，为了提高主存利用率，往往把辅助存储器(如磁盘)作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实验帮助同学理解在分页式存储管理中怎样实现虚拟存储器。

三、实验题目

 本实验有三道题目，其中第一题必做，第二、三题中可任选一个。

第一题：

 模拟分页式存储管理中硬件的地址转换和产生缺页中断。

 （1）分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。为此，在为作业建立页表时，应说明哪些页已在主存，哪些页尚未装入主存，页表的格式为：

 其中，标志——用来表示对应页是否已经装入主存。标志位=1,则表示该页已经在主存；标志位=0，则表示该页尚未装入主存。

主存块号——用来表示已经装入主存的页所占的块号。

在磁盘上的位置----用来指出作业副本的每一页被存放在磁盘上的位置。

 （2）作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页号和单元号，硬件的地址转换机构按页号查页表。若该页对应标志为“1”，则表示该页已在主存，这时根据关系式：

绝对地址=块号*块长+单元号

 计算出欲访问的主存单元地址。如果块长为2的幂次，则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而成绝对地址。若访问的页对应标志为“0”，则表示该页不在主存，这时硬件发“缺页中断”信号，有操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。

  （3）设计一个“地址转换”程序来模拟硬件的地址转换工作。当访问的页在主存时，则形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时，则输出“该页页号”，表示产生了一次缺页中断。该模拟程序的算法如图1。

  （4）假定主存的每块长度为128个字节。现有一个共七页的作业，其中第0页至第3页已经装入主存，其余三页尚未装入主存。该作业的页表为:

  如果作业依次执行的指令序列为：

  （5）运行设计的地址转换程序，显示或打印运行结果。因仅模拟地址转换，并不模拟指令的执行，故可不考虑上述指令序列中的操作。

第二题

  由于是模拟调度算法，所以，不实际启动输出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替一次调出和装入的过程。把第一题中程序稍作修改，与本题结合起来，FIFO页面调度模拟算法如图2.

  （4）磁盘上，在磁盘上存放地址以及已装入主存的页和作业依次执行的指令序列都同第一题中（4）所示。于是增加了“修改标志”后的初始页表为：

  依次执行指令序列，运行你所设计的程序，显示或打印每次调出和装入的页号，以及执行了最后一条指令后数组P的值。

  （5）为了检查程序的正确性，可再任意确定一组指令序列，运行设计的程序，核对执行的结果。

第三题

 用最近最少用(LRU)页面调度算法处理缺页中断。

 （1）在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用LRU页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上，然后再把当前要访问的页装入该块。调出和装入后都要修改页表页表中对应页的标志。

 （2）LRU页面调度算法总是淘汰该作业中距现在最久没有访问过的那一页，因此可以用一个数组来表示该作业已在主存的页面。数组中的第一个元素总是指出当前刚访问的页号，因此最久没被访问的页总是由最后一个元素指出。如果主存中只有四块空闲块且执行第一题提示(4)假设的指令序列，采用LRU页面调度算法，那么在主存中的页面变化情况如下:

 （3）编制一个LRU页面调度程序，为了提高系统效率，如果应淘汰的页在执行中没有修改过，则可不必把该页调出。参看第二题中提示(3)。模拟调度算法不实际启动输出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替。把第一题中的程序稍作改动，与本题集合起来，LRU页面调度模拟算法如图3。

 （4）按第一题中提示(4)的要求，建立一张初始页表，表中为每一页增加“修改标志”位(参考第二题中提示(4))。然后按依次执行的指令序列，运行你所设计的程序，显示或打印每次调出和装入的页号，以及执行了最后一条指令后的数组中的值。

 （5）为了检查程序的正确性，可再任意确定一组指令序列，运行设计的程序，核对执行的结果。

（实验指导书上的流程图有误！！！仔细比对！！！）

四、实验报告

（1）实验题目

见前文

（2）程序中使用的数据结构及符号说明

数据结构：

 主存中的页面的逻辑结构：顺序表。物理结构：数组。因为是模拟运行，为了节省内存空间，主存中只存了页号，用int类型存储，而不是存为PAGE存了每个页面的完整信息。主存中的页面数M为4。

符号说明：

 结构体PAGE表示页表中的一项：有4个属性：flag标志位，blockNum主存块号，diskPos在磁盘上位置，editFlag修改标志。

const int M = 4;//主存页面数
int P[M];//主存
struct PAGE {
  int flag;//标志
  int blockNum;//主存块号
  int diskPos;//在磁盘上位置
  int editFlag;//修改标志
  PAGE() {
    flag = blockNum = diskPos = editFlag = 0;
  }
};

 页表的物理结构：数组。页表类的定义及符号说明见上文。

PAGE page[105];

 指令序列的物理结构：数组。

 符号说明：主存中的页面数M为4；FIFO算法中，指针为k；结构体instruct表示操作，有3个属性：op操作，pageNum页号，unitNum单元号。

struct instruct {
  string op;//操作
  int pageNum;//页号
  int unitNum;//单元号
};
instruct inst[105];

 在FIFO算法中，初始指向主存第0项页面。

int k = 0;//FIFO的指针

（3）打印一份源程序并附上注释

1.程序说明

 程序说明：FIFO.cpp完成的是第二题，LRU.cpp完成的是第三题。

 两个程序大部分内容相似。首先，在main函数中根据提示让用户选择输入方式，用户可以手动输入页表、指令，也可以直接自动装载实验指导书中的页表与指令集合。在初始化完成后，模拟的执行调度算法。

int main() {
  int choose;
  cout << "Choose input:1. auto 2.by hand";
  cin >> choose;
  if (choose == 1)
    init();
  else
    input();
  cpuwork();
}

 执行cpuwork()。在cpuwork()函数中，根据流程图先取指令、访问页号，查页表，判断该页标志是否为1.若该页标志位1，则形成绝对地址，并根据其是否为存指令决定是否置当前页的修改标志为“1”。再判断是否后继指令，直到所有指令运行完成。在运行调度算法时，FIFO算法与LRU算法的流程区别不仅仅在于对中断的处理，而且LRU算法每次运行时都需要对主存中的页表进行修改。

void cpuwork() {
  for (int i = 0; i < n; i++) {
    int L = inst[i].pageNum;//取指令中访问的页号
    inst[i].print();
    if (page[L].flag == 1) {//查页表
      int addr = page[L].blockNum * blocklen + inst[i].unitNum;//输出绝对地址
      if (inst[i].op == "save")//是否为存指令
        page[L].editFlag = 1;
      cout << "absolute address:" << addr << endl;
    }
    else {
      cout << "******interrupt!*****\n";
      interrupt(L);
      i--;//重新查页表
    }
  }
}

 LRU.cpp中，缺页中断服务模拟的是LRU的页面调度。将数组底部的页面调出，将新来的页面装入数组顶部。同样的，也要根据修改标志判断是否输出当前页。LRU.cpp中，cpuwork()也略有区别。每访问一次主存，就要修改主存中的页面情况。

 此为LRU算法中的模拟CPU流程，每执行一次指令就要调整一次主存页面。

void cpuwork() {
  for (int i = 0; i < n; i++) {
    int L = inst[i].pageNum;//取指令访问的页号
    inst[i].print();
    if (page[L].flag == 1) {
      int addr = page[L].blockNum * blocklen + inst[i].unitNum;//形成绝对地址
      if (inst[i].op == "save")
        page[L].editFlag = 1;
      cout << "absolute address:" << addr << endl;
      int pos = 0;//调整主存中的页面
      for (int i = 1; i <m; i++) {
        if (P[i] == L) {
          pos = i;
          break;
        }
      }
      if(pos!=0)
        for (int i = pos; i >= 1; i--)
          P[i] = P[i - 1];
      P[0] = L;
    }
    else {
      cout << "******interrupt!*****\n";
      interrupt(L);
      i--;
    }
  }
}

 FIFO.cpp中，缺页中断服务模拟的是FIFO的页面调度，用指针k指示要装入的页。在调出页面时根据修改标志判断是否要输出当前页，再将新页调入。

void interrupt(int L) {//中断处理
  int j = P[k];//要调出的页面
  if (page[j].editFlag == 1)
    cout << "out J!" << j << endl;//调出当前页
  page[j].flag = 0;
  cout << "in L" << L << endl;//调入页面
  P[k] = L;
  k = (k + 1) % m;
  page[L].flag = 1;//将页装入主存
}

 LRU的中断处理如下

void interrupt(int L) {//中断服务
  int j = P[m - 1];//栈底页面调出
  if (page[j].editFlag == 1)
    cout << "out J!" << j << endl;//调出该页面
  page[j].flag = 0;
  cout << "in L" << L << endl;
  P[3] = P[2];
  P[2] = P[1];
  P[1] = P[0];
  P[0] = L;//调整主存中的页面
  page[L].flag = 1;
}