操作系统实验六-虚拟存储器实验报告

admin管理员组

文章数量:1530518

2024年1月17日发(作者：)

word格式-可编辑-感谢下载支持

实验六 虚拟存储器

一、实验内容

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

二、实验目的

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

三、实验题目

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

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

[提示]

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

页号

标志

主存块号

在磁盘上的位置

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

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

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

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

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

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

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

word格式-可编辑-感谢下载支持

查页表

取指令中访问的页号

取一条指令

开始

word格式-可编辑-感谢下载支持

是

该页标志=1？

形成绝对地址

否

输出“*”页号表

示发生缺页中断

输出绝对地址

有后继指令？

取下一条指令

结束

图6-1 地址转换模拟算法

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

0

1

2

3

4

5

6

1

1

1

1

0

0

0

5

8

9

1

011

012

013

021

022

023

121

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

操作

+

+

×

存

取

－

页号

0

1

2

3

0

6

单元号

70

50

15

21

56

40

操作

移位

+

存

取

+

存

页号

4

5

1

2

4

6

单元号

053

023

037

078

001

084

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

第二题：用先进先出（FIFO）页面调度算法处理缺页中断。

[提示]：

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

（2） FIFO页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。假定作业被选中时，把开始的m个页面装入主存，则数组的元素可定为m

word格式-可编辑-感谢下载支持

个。例如：

P[0]，P[1]，….，P[m-1]

其中每一个P[i]（i=0，1，….，m-1）表示一个在主存中的页面号。它们的初值为：

P[0]:=0，P[1]:=1，….，P[m-1]:=m-1

用一指针k指示当要装入新页时，应淘汰的页在数组中的位置，k的初值为“0”。

当产生缺页中断后，操作系统选择P[k]所指出的页面调出，然后执行：

P[k]:=要装入页的页号

k:=(k+1) mod m

再由装入程序把要访问的一页信息装入到主存中。重新启动刚才那条指令执行。

（3） 编制一个FIFO页面调度程序，为了提高系统效率，如果应淘汰的页在执行中没有修改过，则可不必把该页调出（因在磁盘上已有副本）而直接装入一个新页将其覆盖。因此在页表中增加是否修改过的标志，为“1”表示修改过，为“0”表示未修改过，格式为：

页号 标志 主存块号 修改标志 在磁盘上的位置

由于是模拟调度算法，所以，不实际启动输出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替一次调出和装入的过程。

把第一题中程序稍作修改，与本题结合起来，FIFO页面调度模拟算法如图6-2。

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

页号 标志 主存块号 修改标志 在磁盘上的位置

0

1

2

3

4

5

6

1

1

1

1

0

0

0

5 0

8 0

9 0

1 0

0

0

0

011

012

013

021

022

023

121

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

word格式-可编辑-感谢下载支持

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

开始

取一条指令

取指令中访问的页号→L

查页表

是

该页标志=1？

形成绝对地址

是

是存指令？

否（产生缺页中断）

word格式-可编辑-感谢下载支持

置L页修改标志为“1” 否

输出绝对地址

否

有后继指令？

是

取下一条指令

结束

输出“out j”

j页修改标志为

1

模拟硬件

地址转换

模拟FIFO

j:=P[k] 页面调度

(接下页)

(接上页)

输出“in L”

P[k]:=L, k:=(k+1) mod m

修改页表

图6-2 FIFO页面调度模拟算法

第三题：用最近最少用（LRU）页面调度算法处理缺页中断。

[提示]

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

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

3

2

1

0

0

3

2

1

6

0

3

2

4

6

0

3

5

4

6

0

1

5

4

6

2

1

5

4

4

3

1

5

6

4

2

1

(3) 编制一个LRU页面调度程序，为了提高系统效率，如果应淘汰的页在执行中没有修改过，则可不必

word格式-可编辑-感谢下载支持

把该页调出。参看第二题中提示（3）。模拟调度算法不实际启动输出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替。把第一题中的程序稍作

改动，与本题集合起来，LRU页面调度模拟算法如图6-3。

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

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

开始

取一条指令

取指令中访问的页号→L

查页表

是

该页标志=1？

形成绝对地址

是

是存指令？

置L页修改标志为“1” 否

输出绝对地址

否

有后继指令？

是

结束

取下一条指令

否（产生缺页中断）

模拟硬件

地址转换

模拟LRU

j:=被淘汰的页号 页面调度

(接下页)

(接上页)

word格式-可编辑-感谢下载支持

输出“out j”

j页修改标志为1

输出“in L”

调整数组，j退出数组，L→数组第一个元素中

修改页表

图6-3 LRU页面调度算法

四、实验报告

（1） （第一题必做，第二题和第三题任选其一）。

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

（3） 打印初始页表，每次调出（要调出一页时）和装入的页号，执行最后一条指令后在主存中的页面号（即数组的值）。

思考题

如果你有兴趣的话，可把两种页面调度算法都做一下，比较两种调度算法的效率（哪种调度算法产生缺页中断的次数少）；分析在什麽情况下采用哪种调度算法更有利？

五、实验答案

一、实验目的

在计算机系统中，为了提高主存利用率，往往把辅助存储器（如

磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间

总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为

虚拟存储器。通过本实验帮助同学理解在分页式存储管理中怎样实现

虚拟存储器。

二、实验要求及实验环境

第一题：模拟分页式存储管理中硬件的地址转换和产生缺页中

断。分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业

被选中时，可把作业的开始几页先装入主存且启动执行。为此，在为

作业建立页表时，应说明哪些页已在主存，哪些页尚未装入主存。

作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页

word格式-可编辑-感谢下载支持

号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为

“1”，则表示该页已在主存，这时根据关系式“绝对地址=块号×块

长+单元号”计算出欲访问的主存单元地址。如果块长为2 的幂次，

则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而

成绝对地址。若访问的页对应标志为“0”，则表示该页不在主存，这

时硬件发“缺页中断”信号，有操作系统按该页在磁盘上的位置，把

该页信息从磁盘读出装入主存后再重新执行这条指令。设计一个“地

址转换”程序来模拟硬件的地址转换工作。当访问的页在主存时，则

形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代

替一条指令的执行。当访问的页不在主存时，则输出“* 该页页号”，

表示产生了一次缺页中断。

第二题：用先进先出（FIFO）页面调度算法处理缺页中断。

在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操

作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用

FIFO 页面调度算法把该作业中最先进入主存的一页调出，存放到磁

盘上，然后再把当前要访问的页装入该块。调出和装入后都要修改页

表页表中对应页的标志。

FIFO 页面调度算法总是淘汰该作业中最先进入主存的那一页，

因此可以用一个数组来表示该作业已在主存的页面。假定作业被选中

时，把开始的m 个页面装入主存，则数组的元素可定为m 个。

编制一个FIFO 页面调度程序，为了提高系统效率，如果应淘汰

的页在执行中没有修改过，则可不必把该页调出（因在磁盘上已有副

本）而直接装入一个新页将其覆盖。由于是模拟调度算法，所以，不

实际启动输出一页和装入一页的程序，而用输出调出的页号和装入的

页号来代替一次调出和装入的过程。

三、设计思想（本程序中的用到的所有数据类型的定义，主

程序的流程图及各程序模块之间的调用关系）

1．程序流程图

word格式-可编辑-感谢下载支持

以下为FIFO 算法流程：

word格式-可编辑-感谢下载支持

2 ．逻辑设计

使用线性表保存页表。每个节点信息包括调入主存的标志，主

存块号，在磁盘上的位置，修改标志等。使用线性表保存FIFO 算法

使用的对应关系数组P，用数组模拟实现调度的队列。该队列需支持

查找，插入和删除操作（即替换操作）。

3、物理设计

全局定义如下：

struct info//页表

{

bool flag; //标志

long block;//块号

long disk;//在磁盘上的位置

bool dirty;//修改标志

}pagelist[SizeOfPage];

long po;//队列标记

long P[M];

使用函数init()进行初始化，使用循环结构读入各条指令。

四、测试结果

word格式-可编辑-感谢下载支持

实际运行的结果如下：

请选择题号(1/2):1

请输入指令的页号和单元号：

0 70

绝对地址=710

请输入指令的页号和单元号：

4 053

* 4

请输入指令的页号和单元号：

1 50

绝对地址=1074

请输入指令的页号和单元号：

5 023

* 5

请输入指令的页号和单元号：

2 15

绝对地址=1167

请输入指令的页号和单元号：

1 037

绝对地址=1061

请输入指令的页号和单元号：

exit

请选择题号(1/2):2

请输入指令的页号、单元号，以及是否为存指令：

0 70 N

绝对地址=710

请输入指令的页号、单元号，以及是否为存指令：

4 053 N

out 0

in 4

请输入指令的页号、单元号，以及是否为存指令：

1 50 N

绝对地址=1074

请输入指令的页号、单元号，以及是否为存指令：

5 023 N

out 1

in 5

请输入指令的页号、单元号，以及是否为存指令：

word格式-可编辑-感谢下载支持

2 15 N

绝对地址=1167

请输入指令的页号、单元号，以及是否为存指令：

1 037 y

out 2

in 1

请输入指令的页号、单元号，以及是否为存指令：

3 21 Y

绝对地址=149

请输入指令的页号、单元号，以及是否为存指令：

2 078 N

out 3

in 2

请输入指令的页号、单元号，以及是否为存指令：

0 56 N

out 4

in 0

请输入指令的页号、单元号，以及是否为存指令：

4 001 N

out 5

in 4

请输入指令的页号、单元号，以及是否为存指令：

6 40 N

out 1

in 6

请输入指令的页号、单元号，以及是否为存指令：

6 084 Y

绝对地址=1236

请输入指令的页号、单元号，以及是否为存指令：

exit

数组P 的值为：

P[0]=0

P[1]=4

P[2]=6

P[3]=2

五、系统不足与经验体会

系统的不足包括健壮性尚不够好，界面比较简单，对页表的

初始化需要修改程序。

word格式-可编辑-感谢下载支持

经验体会：注意体会算法的精神，程序前后逻辑要一致。注

意测试时数据的全面性。

六、附录：源代码（带注释）

#include

#include

#define SizeOfPage 100

#define SizeOfBlock 128

#define M 4

struct info//页表

{

bool flag; //标志

long block;//块号

long disk;//在磁盘上的位置

bool dirty;//修改标志

}pagelist[SizeOfPage];

long po;//队列标记

long P[M];

void init_ex1()

{

memset(pagelist,0,sizeof(pagelist));

pagelist[0].flag=1;

pagelist[0].block=5;

pagelist[0].disk=011;

pagelist[1].flag=1;

pagelist[1].block=8;

pagelist[1].disk=012;

pagelist[2].flag=1;

pagelist[2].block=9;

pagelist[2].disk=013;

pagelist[3].flag=1;

pagelist[3].block=1;

pagelist[3].disk=021;

}

void work_ex1()

{

bool stop=0;

long p,q;

char s[128];

word格式-可编辑-感谢下载支持

do

{

printf("请输入指令的页号和单元号：n");

if (scanf("%ld%ld",&p,&q)!=2)

{

scanf("%s",s);

if (strcmp(s,"exit")==0)

{

stop=1;

}

}

else

{

if (pagelist[p].flag)

{

printf("绝对地址=%ldn",pagelist[p].block*SizeOfBlock+q);

}

else

{

printf("* %ldn",p);

}

}

}while (!stop);

}

void init_ex2()

{

po=0;

P[0]=0;P[1]=1;P[2]=2;P[3]=3;

memset(pagelist,0,sizeof(pagelist));

pagelist[0].flag=1;

pagelist[0].block=5;

pagelist[0].disk=011;

pagelist[1].flag=1;

pagelist[1].block=8;

pagelist[1].disk=012;

pagelist[2].flag=1;

pagelist[2].block=9;

pagelist[2].disk=013;

pagelist[3].flag=1;

word格式-可编辑-感谢下载支持

pagelist[3].block=1;

pagelist[3].disk=021;

}

void work_ex2()

{

long p,q,i;

char s[100];

bool stop=0;

do

{

printf("请输入指令的页号、单元号，以及是否为存指令：n");

if (scanf("%ld%ld",&p,&q)!=2)

{

scanf("%s",s);

if (strcmp(s,"exit")==0)

{

stop=1;

}

}

else

{

scanf("%s",s);

if (pagelist[p].flag)

{

printf("绝对地址=%ldn",pagelist[p].block*SizeOfBlock+q);

if (s[0]=='Y' || s[0]=='y')

{

pagelist[p].dirty=1;

}

}

else

{

if (pagelist[P[po]].dirty)

{

//将更新后的内容写回外存

pagelist[P[po]].dirty=0;

}

pagelist[P[po]].flag=0;

printf("out %ldn",P[po]);

word格式-可编辑-感谢下载支持

printf("in %ldn",p);

pagelist[p].block=pagelist[P[po]].block;

pagelist[p].flag=1;

P[po]=p;

po=(po+1)%M;

}

}

}while (!stop);

printf("数组P 的值为：n");

for (i=0;i

{

printf("P[%ld]=%ldn",i,P[i]);

}

}

void select()

{

long se;

char s[128];

do

{

printf("请选择题号(1/2):");

if (scanf("%ld",&se)!=1)

{

scanf("%s",s);

if (strcmp(s,"exit")==0)

{

return;

}

}

else

{

if (se==1)

{

init_ex1();

work_ex1();

}

if (se==2)

{

init_ex2();

word格式-可编辑-感谢下载支持

work_ex2();

}

}

}while (1);

}

int main()

{

select();

return 0;

}

本文标签： 主存地址指令装入页面