一． 实验目的和要求
- 目的
- 存储管理的主要功能之一是合理地分配主存空间。请求页式管理是一种常用的虚拟存储管理技术。
- 本实验的目的是通过请求页式存储管理中页面置换算法的模拟设计来了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
- 要求
- 模拟页式虚拟存储管理中硬件的地址转换和缺页中断的处理过程，并用先进先出调度算法（FIFO）处理缺页中断。
二．实验内容
-
为了装入一个页面而必须调出一页时，如果被选中调出的页在执行中没有修改过，则不必把该页重新写到磁盘上（因磁盘上已有副本）。
因此，在页表中可以增加是否修改过的标志，当执行“存”指令、“写”指令时把对应页的修改标志置成“1”，表示该页修改过，否则为“0”，表示该页未修改过。页表格式如表3-1所示。
| 页号 | 标志 | 主存块号 | 修改标志 | 磁盘上的位置 |
|---|---|---|---|---|
-
设计一个地址转换程序来模拟硬件的地址转换和软件的缺页中断处理过程。
当访问的页在主存时则形成绝对地址，但不去模拟指令的执行，可用输出转换后的绝对地址来表示一条指令已完成。当访问的页不在主存时则输出“*该页页号”来表示硬件产生了一次缺页中断。模拟地址转换的程序流程如图3-1所示。 -
编制一个FIFO页面调度程序。
FIFO页面调度算法总是先调出作业中最先进入主存的那一页，因此，可以用一个数组来构成页号队列。
数组中每个元素是该作业已在主存的页面号，假定分配给作业的主存块数为m，且该作业开始的m页已装入主存，则数组可由m个元素组成：P[0]，P[1]，…，P[m-1]
它们的初值为： P[0]∶=0，P[1]∶=1，…，P[m-1]∶= m-1用一指针k指示当要装入新页时应调出的页在数组的位置，k的初值为“0”。
图3-1 地址转换和FIFO页面调度流程当产生缺页中断后，操作系统总是选择P[k]所指出的页面调出，然后执行
P[k]∶=要装入的新页页号 k∶=（k+1）mod m在实验中不必实际地启动磁盘执行调出一页和装入一页的工作，而用输出“OUT调出的页号”和“IN要装入的新页页号”来模拟一次调出和装入的过程。模拟程序的流程见图3-1所示。
-
假定主存的每块长度为1024个字节，现有一个共7页的作业，其副本已在磁盘上。系统为该作业分配了4块主存块，且该作业的第0页至第3页已经装入主存，其余3页尚未装入主存，该作业的页表如表3-2所示。假定该作业依次执行的指令序列如表3-3所示。
依次执行指令序列来调试你所设计的程序（仅模拟指令的执行，不必考虑指令序列中具体操作的执行）
| 页号 | 标志 | 主存块号 | 修改标志 | 在磁盘上的位置 |
|---|---|---|---|---|
| 0 | 1 | 5 | 0 | 011 |
| 1 | 1 | 8 | 0 | 012 |
| 2 | 1 | 9 | 0 | 013 |
| 3 | 1 | 1 | 0 | 021 |
| 4 | 0 | 0 | 022 | |
| 5 | 0 | 0 | 023 | |
| 6 | 0 | 0 | 121 |
| 序号 | 操作 | 页号 | 页内地址 | 序号 | 操作 | 页号 | 页内地址 |
|---|---|---|---|---|---|---|---|
| 1 | 存 | 0 | 070 | 7 | 移位 | 4 | 053 |
| 2 | + | 1 | 050 | 8 | + | 5 | 023 |
| 3 | × | 2 | 015 | 9 | 存 | 1 | 037 |
| 4 | 存 | 3 | 021 | 10 | 取 | 2 | 078 |
| 5 | 取 | 0 | 056 | 11 | + | 4 | 001 |
| 6 | - | 6 | 040 | 12 | 存 | 6 | 084 |
- 为了检查程序的正确性，可自行确定若干组指令序列，运行设计的程序，核对执行结果。
三．实验程序清单
#include "stdio.h"
#include <string.h>
#define size 1024 // 每个页框的大小（假定为 1024 字节）
// 定义 页表 结构
struct plist
{
int number; // 页号
int flag; // 标志 是否在内存，1 表示在内存，0 表示不在内存
int block; // 主存块号/页框号/页架号，-1 表示不在内存
int modify; // 修改标志，1 表示修改过，0 表示未修改
int location; // 磁盘上的位置
};
// 给定的作业页表，模拟页面的初始状态
struct plist page_table[7] = {
{0,1,5,0,011}, // 页号0，已在内存，页框号为5
{1,1,8,0,012},
{2,1,9,0,013},
{3,1,1,0,021},
{4,0,-1,0,022}, // 页号4，不在内存
{5,0,-1,0,023},
{6,0,-1,0,121}
};
// 定义 输入指令 结构
struct ilist
{
char operation[6]; // 指令名称
int pagenumber; // 指令操作页号
int address; // 指令目标地址
};
//当执行“存”指令、“写”指令时把对应页的修改标志置成“1”，表示该页修改过，否则为“0”，表示该页未修改过
struct ilist instructions[12] = {
{"存",0,70}, // 页号0，执行"存"操作，操作地址为70
{"+",1,50},
{"*",2,15},
{"存",3,21},
{"取",0,56},
{"-",6,40},
{"移位",4,53},
{"+",5,23},
{"存",1,37},
{"取",2,78},
{"+",4,1},
{"存",6,84}
};
int main()
{
int logical_page_number, // 逻辑页号
page_in_memory_flag, // 指示逻辑页面是否已加载到内存
replaced_page_number, // 被替换下的逻辑页号
replaced_page_modified_flag =0; //被替换页面的修改状态标志
char* isOUT = " ";
int m = 4; // (主存)页框数量
int p[4] = { 0, 1, 2, 3 }; // 初始(主存)页框中存放的页面，FIFO 队列
int k = 0; // FIFO 队列指针，用于指示要被替换的页框
long memaddress; // 物理地址
printf("\n指令序号 操作\t 页号 \t页内地址 标志 缺页指示 修改页号 主存块号 绝对地址\n");
int instruction_index; // 指令序列的当前索引
for (instruction_index = 0; instruction_index < 12; instruction_index++) //取一条指令
{
logical_page_number = instructions[instruction_index].pagenumber; // 当前指令操作的页号
page_in_memory_flag = page_table[logical_page_number].flag; // 查页表，检查该页是否在内存（标志位)
if (page_in_memory_flag == 0) // 不在内存，发生缺页中断，缺页中断处理 需要输出*页号
{
replaced_page_number = p[k]; // 获取当前需要 FIFO 替换的页号
replaced_page_modified_flag = page_table[replaced_page_number].modify; // 被替换页号是否修改过
p[k] = logical_page_number; // 替换为当前指令需要的页号
k = (k + 1) % m; // 更新 FIFO 指针到下一位
page_table[logical_page_number].flag = 1; // 更新标志位，表示新页已调入内存
/*此处作用：将标志位改为a1*/
page_table[logical_page_number].block = page_table[replaced_page_number].block; // 分配被替换页的页框
/*
修改被置换页状态
*/
page_table[replaced_page_number].block = -1; // 被替换页不再有主存页框
page_table[replaced_page_number].flag = 0; // 被替换页标记为不在内存
page_table[replaced_page_number].modify = 0; // 重置修改标志
}
// 地址转换：页框号 * 每页大小 + 页内地址
memaddress = page_table[logical_page_number].block * size + instructions[instruction_index].address;
// 如果操作是存储，标记该页已被修改
if (strcmp(instructions[instruction_index].operation, "存") ==0)
page_table[logical_page_number].modify = 1;
// printf("指令：%s modified:%d\n ", instructions[instruction_index].operation, page_table[logical_page_number].modify);
if (replaced_page_modified_flag)
isOUT = "OUT";
else {
isOUT = " ";
}
printf(" %d\t", instruction_index+1); // 指令序号
printf(" %s\t", instructions[instruction_index].operation); // 操作类型
printf(" %d\t", instructions[instruction_index].pagenumber); // 页号
printf(" %d\t", instructions[instruction_index].address); // 页内地址
printf(" %d\t", page_in_memory_flag); // 标志位（是否在内存）
// 输出指示缺页
if (page_in_memory_flag == 1) // 页在内存，输出绝对地址
printf(" \t");
else // 缺页，标记为 *
printf(" *%d\t", instructions[instruction_index].pagenumber);
// 输出替换信息
if (page_in_memory_flag == 1) // 页在内存，无替换
printf(" \t");
else // 缺页替换
printf(" %s %d->IN %d\t", isOUT,replaced_page_number, instructions[instruction_index].pagenumber);
printf(" %d\t", page_table[logical_page_number].block);
printf(" %d\t", memaddress);
printf("\n");
replaced_page_modified_flag = 0; //重置为0;
}
}
四．实验结果
指令序号 操作 页号 页内地址 标志 缺页指示 修改页号 主存块号 绝对地址
1 存 0 70 1 5 5190
2 + 1 50 1 8 8242
3 * 2 15 1 9 9231
4 存 3 21 1 1 1045
5 取 0 56 1 5 5176
6 - 6 40 0 *6 OUT 0->IN 6 5 5160
7 移位 4 53 0 *4 1->IN 4 8 8245
8 + 5 23 0 *5 2->IN 5 9 9239
9 存 1 37 0 *1 OUT 3->IN 1 1 1061
10 取 2 78 0 *2 6->IN 2 5 5198
11 + 4 1 1 8 8193
12 存 6 84 0 *6 4->IN 6 8 8276