操作系统实验(2-5)

1、实验二 单处理器系统的进程调度1实验目的加深对进程概念的理解，明确进程和程序的区别；深入了解系统如何组织进程、创建进程；进一步认识如何实现处理器调度。2实验预备知识进程的概念；进程的组织方式；进程的创建；进程的调度。3实验内容编写程序完成单处理机系统中的进程调度，要求采用时间片轮转调度算法。实验具体包括：首先确定进程控制块的内容，进程控制块的组成方式；然后完成进程创建原语和进程调度原语；最后编写主函数对所作工作进程测试。4提示与讲解这个实验主要要考虑三个问题：如何组织进程、如何创建进程和如何实现处理器调度。考虑如何组织进程，首先就要设定进程控制块的内容。进程控制块PCB记录各个进程执行时的情况

2、。不同的操作系统，进程控制块记录的信息内容不一样。操作系统功能越强，软件也越庞大，进程控制块记录的内容也就越多。这里的实验只使用了必不可少的信息。一般操作系统中，无论进程控制块中信息量多少，信息都可以大致分为以下四类： 标识信息每个进程都要有一个惟一的标识符，用来标识进程的存在和区别于其他进程。这个标识符是必不可少的，可以用符号或编号实现，它必须是操作系统分配的。在后面给出的参考程序中，采用编号方式，也就是为每个进程依次分配一个不相同的正整数。 说明信息用于记录进程的基本情况，例如进程的状态、等待原因、进程程序存放位置、进程数据存放位置等等。实验中，因为进程没有数据和程序，仅使用进程控制块模拟

3、进程，所以这部分内容仅包括进程状态。 现场信息现场信息记录各个寄存器的内容。当进程由于某种原因让出处理器时，需要将现场信息记录在进程控制块中，当进行进程调度时，从选中进程的进程控制块中读取现场信息进行现场恢复。现场信息就是处理器的相关寄存器内容，包括通用寄存器、程序计数器和程序状态字寄存器等。在实验中，可选取几个寄存器作为代表。用大写的全局变量AX、BX、CX、DX模拟通用寄存器、大写的全局变量PC模拟程序计数器、大写的全局变量PSW模拟程序状态字寄存器。 管理信息管理信息记录进程管理和调度的信息。例如进程优先数、进程队列指针等。实验中，仅包括队列指针。因此可将进程控制块结构定义如下：stru

4、ct pcbint name; /进程标识符 int status; /进程状态 int ax, bx, cx,dx; /进程现场信息，通用寄存器内容 int pc; /进程现场信息，程序计数器内容 int psw; /进程现场信息，程序状态字寄存器内容 int next; /下一个进程控制块的位置确定进程控制块内容后，要考虑的就是如何将进程控制块组织在一起。多道程序设计系统中，往往同时创建多个进程。在单处理器的情况下，每次只能有一个进程处于运行态，其他的进程处于就绪状态或等待状态。为了便于管理，通常把处于相同状态的进程的进程控制块链接在一起。单处理器系统中，正在运行的进程只有一个。因此，单处

5、理器系统中进程控制块分成一个正在运行进程的进程控制块、就绪进程的进程控制块组织成的就绪队列和等待进程的进程控制块组成的等待队列。由于实验模拟的是进程调度，没有对等待队列的操作，所以实验中只有一个指向正在运行进程的进程控制块指针和一个就绪进程的进程控制块队列指针。操作系统的实现中，系统往往在主存中划分出一个连续的专门区域存放系统的进程控制块，实验中应该用数组模拟这个专门的进程控制块区域，定义如下：#define n 10 /假定系统允许进程个数为10struct pcb pcbarean; /模拟进程控制块区域的数组 这样，进程控制块的链表实际上是数据结构中使用的静态链表。进程控制块的链接方式可

6、以采用单向和双向链表，实验中，进程控制块队列采用单向不循环静态链表。为了管理空闲进程控制块，还应该将空闲控制块链接成一个队列。实验中采用时间片轮转调度算法，这种算法是将进程控制块按照进入就绪队列的先后次序排成队列。关于就绪队列的操作就是从队头摘下一个进程控制块和从队尾挂入一个进程控制块。因此为就绪队列定义两个指针，一个头指针，指向就绪队列的第一个进程控制块；一个尾指针，指向就绪队列的最后一个进程控制块。实验中指向运行进程的进程控制块指针、就绪队列指针和空闲进程控制块队列指针定义如下：int run; /定义指向正在运行进程的进程控制块的指针structint head; int tail;re

7、ady; /定义指向就绪队列的头指针head和尾指针tailint pfree; /定义指向空闲进程控制块队列的指针以上是如何组织进程，下面考虑如何创建进程。进程创建是一个原语，因此在实验中应该用一个函数实现，进程创建的过程应该包括：申请进程控制块：进程控制块的数量是有限的，如果没有空闲进程控制块，则进程不能创建，如果申请成功才可以执行第步；申请资源：除了进程控制块外，还需要有必要的资源才能创建进程，如果申请资源不成功，则不能创建进程，并且归还已申请的进程控制块；如果申请成功，则执行第三步，实验无法申请资源，所以模拟程序忽略了申请资源这一步；填写进程控制块：将该进程信息写入进程控制块内，实验中

8、只有进程标识符、进程状态可以填写，每个进程现场信息中的寄存器内容由于没有具体数据而使用进程（模拟进程创建时，需输入进程标识符字，进程标识符本应系统建立，并且是惟一的，输入时注意不要冲突），刚刚创建的进程应该为就绪态，然后转去执行第四步；挂入就绪队列：如果原来就绪队列不为空，则将该进程控制块挂入就绪队列尾部，并修改就绪队列尾部指针；如果原来就绪队列为空，则将就绪队列的头指针、尾指针均指向该进程控制块，进程创建完成。进程创建流程图如图2.2所示。多道程序设计的系统中，处于就绪态的进程往往是多个，它们都要求占用处理器，可是单处理器系统的处理器只有一个，进程调度就是解决这个处理器竞争问题的。进程调度的

9、任务就是按照某种算法从就绪进程队列中选择一个进程，让它占有处理器。因此进程调度程序就应该包括两部分，一部分是在进程就绪队列中选择一个进程，并将其进程控制块从进程就绪队列中摘下来，另一部分工作就是分配处理器给选中的进程，也就是将指向正在运行进程的进程控制块指针指向该进程的进程控制块，并将该进程的进程控制块信息写入处理器的各个寄存器中。图2.2 进程创建流程图实验中采用时间片轮转调度算法。时间片轮转调度算法让就绪进程按就绪的先后次序排成队列，每次总是选择就绪队列中的第一个进程占有处理器，但是规定只能使用一个“时间片”。时间片就是规定进程一次使用处理器的最长时间。实验中采用每个进程都使用相同的不变的

10、时间片。采用时间片轮转调度算法的进程调度流程图如图2.3所示。完成上述功能后，编写主函数进行测试：首先建立一个就绪队列，手工输入信息建立几个进程；然后进行进程调度；最后将指向正在运行进程的指针指向的进程控制块的内容输出，察看结果。5课外题编程实现采用优先数调度算法的进程调度。6参考程序图2.3 进程调度流程图#include stdio.h#define running 1/用running表示进程处于运行态#define aready 2/用aready表示进程处于就绪态#define blocking 3/用blocking表示进程处于等待态#define sometime 5/用some

11、time表示时间片大小#define n 10/假定系统允许进程个数为nstructint name;/进程标识符int status;/进程状态int ax,bx,cx,dx;/进程现场信息，通用寄存器内容int pc;/进程现场信息，程序状态寄存器内容int psw;/下一个进程控制块的位置int next;/模拟进程控制块的数组pcbarean;/模拟进程控制块区域的数组int PSW,AX,BX,CX,DX,PC,TIME;/模拟寄存器int run;/定义指向正在运行进程的进程控制块的指针struct int head;int tail;ready;/定于就绪队列的头指针head和尾

12、指针tailint pfree;/定义指向空闲进程控制块队列的指针sheduling()/进程调度函数int i;if(ready.head=-1)printf(无就绪进程n);return;i=ready.head;/就绪队列头指针赋给iready.head=pcbareaready.head.next;/就绪队列头指针后移if(ready.head=-1)ready.tail=-1;/就绪队列为空，修正尾指针ready.tailpcbareai.status=running;/修改进程控制块状态TIME=sometime;/设置相对时钟寄存器/恢复该进程现场信息：AX=pcbarearun

13、.ax;BX=pcbarearun.bx;CX=pcbarearun.cx;DX=pcbarearun.dx;PC=pcbarearun.pc;PSW=pcbarearun.psw;run=i;/修改指向运行进程的指针/进程调度函数结束create(int x)/创建进程int i;if(pfree=-1)/空闲进程控制块队列为空printf(无空闲进程控制块，进程创建失败n);return;i=pfree;/取空闲进程控制块队列的第一个pfree=pcbareapfree.next;/pfree后移/填写该进程控制块内容：=x;pcbareai.status=are

14、ady;pcbareai.ax=x;pcbareai.bx=x;pcbareai.cx=x;pcbareai.dx=x;pcbareai.pc=x;pcbareai.psw=x;if(ready.head!=-1)/就绪队列不空时，挂入就绪队列方式pcbareaready.tail.next=i;ready.tail=i;pcbareaready.tail.next=-1;else /就绪队列空时,挂入就绪队列方式ready.head=i;ready.tail=i;pcbareaready.tail.next=-1;/进程创建函数结束main()/系统初始化int num,i,j,block;

15、run=ready.head=ready.tail=block=-1;pfree=0;for(j=0;j=0)create(num);scanf(%d,&num);sheduling();/进程调度if(run!=-1)printf(进程标识符 进程状态 寄存器内容:ax bx cx dx pc psw:n);printf(%8d%10d%3d%3d%3d%3d%3d%3dn,,pcbarearun.status,pcbarearun.ax,pcbarearun.bx,pcbarearun.cx,pcbarearun.dx,pcbarearun.pc,pcbare

16、arun.psw);/main()结束实验三 动态分区存储管理方式的主存分配回收1实验目的深入了解动态分区存储管理方式的主存分配回收的实现。2实验预备知识存储管理中动态分区的管理方式。3实验内容编写程序完成动态分区存储管理方式的主存分配回收的实现。实验具体包括：首先确定主存空间分配表；然后采用最优适应算法完成主存空间的分配，完成主存空间的回收；最后编写主函数对所作工作进程测试。4提示与讲解动态分区管理方式预先不将主存划分成几个区域，而把主存除操作系统占用区域外的空间看作一个大的空闲区。当作业要求装入主存时，根据作业需要的主存空间的大小查询主存内各个空闲区，当从主存空间中找到一个大于或等于该作业

17、大小的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。作业执行完后，它所占的主存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。实现动态分区的分配和回收，主要考虑的问题有三个：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。首先，考虑第一个问题：设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域。由于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收变动。

18、总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收主存分区时，可能会合并空闲分区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，主存的分配和回收主要是对空闲区的操作。这样为了便于对主存空间的分配和回收，就建立两张分区表记录主存使用情，一张表格记录作业占用分区的“已

19、分配区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种，一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分配区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因而在多数情况下，无论是“已分配区表”还是“空闲区表”都有空闲栏目。已分配区表中除了分区起始地址、长度外，也至少还要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；空闲区表中除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，内容为“空”，

20、如果为某个空闲区的登记项，内容为“未分配”（。在实际系统中，这两表格的内容可能还要多，实验中仅仅使用上述必须的数据。为此,“已分配区表”和“空闲区表”在实验中有如下的结构定义。已分配区表的定义：#define n 10 /假定系统允许的最大作业数量为nstructfloat address; /已分分区起始地址 float length; /已分分区长度，单位为字节 int flag; /已分配区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名used_tablen; /已分配区表空闲区表的定义：#define m 10 /假定系统允许的空闲区表最大为mstructfloat ad

21、dress; /空闲区起始地址 float length; /空闲区长度，单位为字节 int flag; /空闲区表登记栏标志，用“0”表示空栏目，用“1”表示未分配free_tablem; /空闲区表其中分区起始地址和长度数值太大，超出了整型表达范围，所以采用了float类型。然后，就要考虑如何在设计的数据表格上进行主存的分配。当要装入一个作业时，从空闲区表中查找标志为“未分配”的空闲区，从中找出一个能容纳该作业的空闲区。如果找到的空闲区正好等于该作业的长度，则把该分区全部分配给作业。这时应该把该空闲区登记栏中的标志改为“空”，同时在已分配区表中找到一个标志为“空”的栏目登记新装入作业所占用

22、分区的起始地址、长度和作业名。如果找到的空闲区大于作业长度，则把空闲区分成两部分，一部分用来装入作业，另外一部分仍为空闲区。这时只要修改原空闲区的长度，且把新装入的作业登记到已分配区表中。实验中主存分配算法采用“最优适应”算法。最优适应算法是按作业要求挑选一个能满足作业要求的最小空闲区，这样保证可以不去分割一个大的区域，使装入大作业时比较容易得到满足。但是最优适应算法容易出现找到的一个分区可能只比作业所要求的长度略大一点的情况，这时，空闲区分割后剩下的空闲区就很小，这种很小的空闲区往往无法使用，却影响了主存的使用。为了一定程度上解决这个问题，如果空闲区的大小比作业要求的长度略大一点，不再将空闲

23、区分成已分分区和空闲区两部分，而是将整个空闲区分配给作业。在实现最优适应算法时，可把空闲区按长度以递增方式登记在空闲区表中。分配时顺序查找空闲表，查找到的第一个空闲区就是满足作业要求的最小分区。这样查找速度快，但是为使空闲区按长度以递增顺序登记在空闲表中，就必须在分配回收时进行空闲区表的调整。空闲区表调整时移动表目的代价要高于查询整张表的代价，所以实验中不采用空闲区有序登记在空闲表中的方法。动态分区方式的主存分配流程图如图2.4所示。最后是动态分区方式下的主存回收问题。动态分区方式下回收主存空间时，应该检查是否有与归还区相邻的空闲区。若有，则应该合并成一个空闲区。一个归还区可能有上邻空闲区，也

24、可能有下邻空闲区，或者既有上邻空闲区又有下邻空闲区，或者既无上邻空闲区也无下邻空闲区。在实现回收时，首先将作业归还的区域在已分配表中找到，将该栏目的状态变为“空”，然后检查空闲区表中标志为“未分配”的栏目，查找是否有相邻空闲区；最后，合并空闲区，修改空闲区表。假定作业归还的分区起始地址为S，长度为L，则： 归还区有下邻空闲区如果S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，则表明归还区有一个下邻空闲区。这时只要修改第j栏登记项的内容：起始地址=S；第j栏长度=第j栏长度+L；则第j栏指示的空闲区是归还区和下邻空闲区合并后的大空闲区； 归还区有上邻空闲区如果空闲区表中某个登记栏

25、目（假定为第k栏）的“起始地址+长度”正好等于S，则表明归还区有一个上邻空闲区。这时要修改第k栏登记项的内容（起始地址不变）：第k栏长度=第k栏长度+L；于是第k栏指示的空闲区是归还区和上邻空闲区合并后的大空闲区； 归还区既有上邻空闲区又有下邻空闲区如果S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，同时还有某个登记栏目（假定为第k栏）的“起始地址+长度”正好等于S，这表明归还区既有一个上邻空闲区又有一个下邻空闲区。此时对空闲区表的修改如下：第k栏长度=第k栏长度+第j栏长度+L；（第k栏起始地址不变）第j栏状态=“空”；（将第j栏登记项删除）这样，第k栏指示的空闲区是归还区和

26、上、下邻空闲区合并后的大空闲区；原来的下邻空闲区登记项（第j栏）被删除，置为“空”。 2.4 动态分区最优分配算法流程图图2.5 动态分区回收流程图 归还区既无上邻空闲区又无下邻空闲区如果在检查空闲区表时，无上述三种情况出现，则表明归还区既无上邻空闲区又无下邻空闲区。这时，应该在空闲区表中查找一个状态为“空”的栏目（假定查到的是第t栏），则第t栏的内容修改如下：第t栏起始地址=S；第t栏长度=L；第t栏状态=“未分配”这样，第t栏指示的空闲区是归还区。按上述方法归还主存区域的流程图如图2.5所示。由于是实验，没有真正的主存要分配，所以在实验中，首先应建立一张空闲区表，初始状态只有一个空闲登记项

27、（假定的主存空闲区）和一张所有状态都为“空”的已分配区表，假定主存空间110KB，操作系统占用10KB,其余为空闲区；然后，可以选择进行主存分配或主存回收，如果是分配，要求输入作业名和所需主存空间大小，如果是回收，输入回收作业的作业名，循环进行主存分配和回收后，如果需要，则显示两张表的内容，以检查主存的分配和回收是否正确。5.课外题编程实现页式存储管理的主存分配和回收。用链表方式表示主存空间分配情况，完成动态分区管理方式下的主存空间的分配和回收。#define n 10 /假定系统允许的最大作业数量为n#define m 10 /假定系统允许的空闲区表最大为m#define minisize

28、100struct float address; /已分分区起始地址 float length; /已分分区长度，单位为字节 int flag; /已分配区表登记栏标志，用0表示空栏目，实验中只支持一个字符的作业名used_tablen; /已分配区表structfloat address; /空闲区起始地址 float length; /空闲区长度，单位为字节 int flag; /空闲区表登记栏标志，用0表示空栏目，用1表示未分配free_tablem; /空闲区表 allocate(J,xk) /采用最优分配算法分配xk大小的空间 char J; float xk;int i,k; fl

29、oat ad; k=-1; for(i=0;i=xk&free_tablei.flag=1) if(k=-1|free_tablei.lengthfree_tablek.length) k=i; if(k=-1) /未找到可用空闲区，返回 printf(无可用空闲区n); return; /找到可用空闲区，开始分配：若空闲区大小与要求分配的空间差小于minisize大小，则空闲区全部分配；若空闲区大小与要求分配的空间差大于minisize大小，则从空闲区划出一部分分配 if(free_tablek.length-xk=minisize) free_tablek.flag=0; ad=free_

30、tablek.address; xk=free_tablek.length; else free_tablek.length=free_tablek.length-xk; ad=free_tablek.address+free_tablek.length; /修改已分配区表 i=0; while(used_tablei.flag!=0&i=n) /无表目填写已分分区 printf(无表目填写已分分区，错误n); /修正空闲区表 if(free_tablek.flag=0) /前面找到的是整个空闲区 free_tablek.flag=1; else /前面找到的是某个空闲区的一部分 free_t

31、ablek.length=free_tablek.length+xk; return; else /修改已分配区表 used_tablei.address=ad; used_tablei.length=xk; used_tablei.flag=J; return; /主存分配函数结束 reclaim(J)/回收作业名为J的作业所占主存空间 char J; int i,k,j,s,t; float S,L; /寻找已分配区表中对应登记项 s=0; while(used_tables.flag!=J|used_tables.flag=0)&s=n) /在已分配区表中找不到名字为J的作业 print

32、f(找不到该作业n); return; /修改已分配区表 used_tables.flag=0; /取得归还分区的起始地址S和长度L S=used_tables.address; L=used_tables.length; j=-1;k=-1;i=0; /寻找回收分区的上下邻空闲区，上邻表目k，下邻表目j while(im&(j=-1|k=-1) if(free_tablei.flag=0) if(free_tablei.address+free_tablei.length=S)k=i; /找到上邻 if(free_tablei.address=S+L)j=i; /找到下邻 i+; if(k!

33、=-1) if(j!=-1) / 上邻空闲区，下邻空闲区，三项合并 free_tablek.length=free_tablej.length+free_tablek.length+L; free_tablej.flag=0; else / 上邻空闲区，下邻非空闲区，与上邻合并 free_tablek.length=free_tablek.length+L; else if(j!=-1) /上邻非空闲区，下邻为空闲区，与下邻合并 free_tablej.address=S; free_tablej.length=free_tablej.length+L; else /上下邻均为非空闲区，回收区

34、域直接填入 /在空闲区表中寻找空栏目 t=0; while(free_tablet.flag=1&t=m) /空闲区表满,回收空间失败,将已分配区表复原 printf(主存空闲表没有空间,回收空间失败n); used_tables.flag=J; return; free_tablet.address=S; free_tablet.length=L; free_tablet.flag=1; return(t); /主存归还函数结束 main( ) int i,a; float xk; char J; /空闲区表初始化 free_table0.address=10240; free_table0

35、.length=; free_table0.flag=1; for(i=1;im;i+) free_tablei.flag=0; /已分配区表初始化 for(i=0;in;i+) used_tablei.flag=0; while(1) printf(选择功能项（0-退出,1-分配主存,2-回收主存,3-显示主存）n); printf(选择功项(03) :); scanf(%d,&a); switch(a) case 0: exit(0); /a=0程序结束 case 1: /a=1分配主存空间 printf(输入作业名J和作业所需长度xk: ); scanf(%*c%c%f,&J,&xk);

36、 allocate(J,xk);/分配主存空间 break; case 2: /a=2回收主存空间 printf(输入要回收分区的作业名); scanf(%*c%c,&J); reclaim(J);/回收主存空间 break; case 3: /a=3显示主存情况，输出空闲区表和已分配区表 printf(输出空闲区表：n起始地址 分区长度 标志n); for(i=0;im;i+) printf(%5.0f%10.0f%6dn,free_tablei.address,free_tablei.length, free_tablei.flag); printf( 按任意键,输出已分配区表n); ge

37、tch(); printf( 输出已分配区表：n起始地址 分区长度 标志n); for(i=0;in;i+) if(used_tablei.flag!=0) printf(%6.0f%9.0f%6cn,used_tablei.address,used_tablei.length, used_tablei.flag); else printf(%6.0f%9.0f%6dn,used_tablei.address,used_tablei.length, used_tablei.flag); break; default:printf(没有该选项n); /case /while /main( )结束

38、实验四 页式虚拟存储管理中地址转换和缺页中断1实验目的深入了解页式存储管理如何实现地址转换；进一步认识页式虚拟存储管理中如何处理缺页中断。2实验预备知识页式存储管理中的地址转换的方法；页式虚拟存储的缺页中断处理方法。3实验内容编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。实验具体包括：首先对给定的地址进行地址转换工作，若发生缺页则先进行缺页中断处理，然后再进行地址转换；最后编写主函数对所作工作进程测试。假定主存64KB，每个主存块1024字节，作业最大支持到64KB，系统中每个作业分得主存块4块。4提示与讲解页式存储管理中地址转换过程很简单，假定主存块的大小为2n字节，主存大

39、小为2m字节和逻辑地址m位，则进行地址转换时，首先从逻辑地址中的高m-n位中取得页号，然后根据页号查页表，得到块号，并将块号放入物理地址的高m-n位，最后从逻辑地址中取得低n位放入物理地址的低n位就得到了物理地址，过程如图2.61所示。页 号 页内地址块 号 块内地址页号 块号物理地址逻辑地址m n n-1 0m n n-1 0图2.6 页式存储管理系统地址转换示意图地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程，模拟地址转换的流程图如图2.7所示（实验中假定主存64KB，每个主存块1024字节，即n=10,m=16，物理地址中块号6位、块内地址10位；作业最大64KB，即m=16

40、，逻辑地址中页号6位、页内地址10位）。在页式虚拟存储管理方式中，作业信息作为副本放在磁盘上，作业执行时仅把作业信息的部分页面装入主存储器，作业执行时若访问的页面在主存中，则按上述方式进行地址转换，若访问的页面不在主存中，则产生一个“缺页中断”，由操作系统把当前所需的页面装入主存储器后，再次执行时才可以按上述方法进行地址转换。页式虚拟存储管理方式中页表除页号和该页对应的主存块号外，至少还要包括存在标志（该页是否在主存），磁盘位置（该页的副本在磁盘上的位置）和修改标志（该页是否修改过）。这样，在实验中页表格式如图2.7所示。页表用数组模拟，在实验中页表数据结构定义为：define n 32 /实

41、验中假定的页表长度，页表的长度实际上是由系统按照作业长度决定的structint lnumber; /页号 int flag; /表示该页是否在主存，“1”表示在主存，“0”表示不在主存 int pnumber; /该页所在主存块的块号 int write; /该页是否被修改过，“1”表示修改过，“0”表示没有修改过 int dnumber; /该页存放在磁盘上的位置，即磁盘块号pagen; /页表定义图2.7 模拟地址转换的流程图缺页处理过程简单阐述如下： 根据当前执行指令中逻辑地址中的页号查页表，判断该页是否在主存储器中，若该页标志为“0”，形成缺页中断。中断装置通过交换PSW让操作系统的

42、中断处理程序占用处理器； 操作系统处理缺页中断的方法就是查主存分配表，找一个空闲主存块；若无空闲块，查页表，选择一个已在主存的页面，把它暂时调出主存。若在执行过程中该页被修改过，则需将该页信息写回磁盘，否则不必写回； 找出该页的磁盘位置，启动磁盘读出该页信息，把磁盘上读出的信息装入第2步找到的主存块，修改页表中该页的标志为“1”； 由于产生缺页中断的那条指令没有执行完，所以页面装入后应重新执行被中断的指令。当重新执行该指令时，由于要访问的页面已在主存中，所以可正常执行。关于第步的查找装入新页面的主存块的处理方式，不同系统采用的策略可能有所不同，这里采用局部置换算法，就是每个作业分得一定的主存块

43、，只能在分得的主存块内查找空闲块，若无空闲主存块，则从该作业中选择一个页面淘汰出主存。实验中使用局部置换算法。使用局部置换算法时，存在这样一个问题：就是在分配给作业主存空间时，装入哪些页？有的系统采取不装入任何一页，当执行过程中需要时才将其调入。有的系统采用页面预置的方法，就是估计可能某些页面会先用到，在分配主存块后将这些页面装入。实验中，采用第二种方法，分配主存空间时将前几页调入主存，假定系统中每个作业分得主存块m（m=4）块，则将第0m-1页装入主存。因为是模拟硬件工作，所以实验中如果访问的页不在主存时，则输出该页页号，表示硬件产生缺页中断，然后直接转去缺页中断处理；由于采用页面预置方法，

44、在给定的主存块中一定无空闲块，只能淘汰已在主存的一页；没有启动磁盘的工作，淘汰的页需要写回磁盘时，用输出页号表示，调入新的一页时，将该页在页表中的存在标志置为“1”，输出页号表示将该页调入主存。图2.8 采用先进先出页面置换算法的缺页中断流程图主存中无空闲块时，为装入一个页面，必须按某种算法从已在主存的页中选择一页，将它暂时调出主存，让出主存空间，用来存放需装入的页面，这个工作称为“页面调度”。如何选择调出的页是很重要的，常用的页面调度算法有先进先出算法、最近最少用算法和最近最不常用算法。实验中使用先进先出调度算法。先进先出调度算法总是选择驻留在主存时间最长的一页调出。先进先出算法简单，易实现

45、。可以把在主存储器的页的页号按进入主存的先后次序排成队列，每次总是调出队首的页，当装入一个新页后，把新页的页号排入队尾。实验中，用一个数组存放页号的队列。假定分配给作业的主存块数为m，数组可由m个元素组成，p0，p1pm-1；队首指针head；采用页面预置的方法，页号队列的长度总是m，tail等于(head+1)%m。因此可以使用一个指针，只用head即可。在装入一个新的页时，装入页和淘汰页同时执行，当装入一个新的页时，将其页号存入数组：淘汰页的页号=phead;phead=新装入页的页号；head=(head+1)%m;实验中，采用先进先出页面置换算法的缺页中断流程图如图2.8所示。图2.9 一条指令执行的模拟流程图实验执行一条指令时，不模拟指令的执行，只是考虑指令执行是否修改页面，若修改页面，则将该页的页表中修改标志为置“1”，然后输出转换后的物理地址，并输出物理地址来表示一条指令执行完成；如果访问的页不在主存时，则产生缺页中断，然后直接转去缺页中断处理，最后模拟中断返回，就是返回重新进行地址转换。一条指令执行的模拟流程图如图2.9所示。因为没有实际主存，所以在模拟程序中首先手工输入页表信息，创建该作业的页表；然后循环执行假定的指令，观察地址转换情况。5课外题采用LRU页面调度算法编程实现上述虚拟页式存储管理的地址转换。#incl