南京信息工程大学实验（实习）报告
实验（实习）名称存储管理实验（实习）日期 20131130 得分指导教师
系计算机系专业计科年级 2011 班次 1 姓名汤建洋学号 20112308018
1. 实验目的
本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的
特点，掌握请求页式存储管理的页面置换算法，此外通过实验了解HASH表数据结构的使用。
2. 实验准备
⑴数据结构HASH表查找方式。
⑵操作系统相关内存交换知识。
⑶阅读Linux系统的msg.c、sem.c和shm.c等源码文件，掌握几个LINUX函数getpid ( )、srand (int a)和int rand ( )的使用方法。
3. 实验内容
设计一个虚拟存储区和内存工作区，并分别编程实现使用先进先出置换算法（FIFO）
和最近最少使用页面置换算法（LRU）计算访问命中率。
4. 实验指导
拥有页面交换机制的操作系统总是把当前进程中急需处理的部分页面换入到内存当中，而把更多暂时不需处理的页面放置在外存当中，由于进程需要处理页面的顺序不同，而需要
在内存与外存之间进行页面交换，交换算法也就应运而生。
本实验并没有进入系统空间对实际进程页面进行控制，而是在用户空间用线性表的连续
存储方式对进程页面交换进行的模拟。
⑴ FIFO算法实现
<原理描述>
在分配内存页面数（AP）小于进程页面数（PP）时，当然是最先的AP个页面放入
内存；
这时有需要处理新的页面，则将原理在内存中的AP个页面中最先进入的调出，然
后放入新页面；
以后如果有新页面需要调入，按（2）之规则进行。
算法特点：所使用的内存页面构成一个队列。
<算法实现提示>
要得到“命中率”，必然应该有一个常量total_instruction记录页面总共使用次数；此外需
要一个变量记录总共换入页面的次数（需要换出页面，总是因为没有命中而产生的）diseffect。
利用公式(1-diseffect/total_instructiong)×100%可以得到命中率。
[步骤1] 初始化。
设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分
配的页面数，并产生一个的随机数序列main[total_instruction]（当然这个序列由page[]的下标
随机构成），表示待处理的进程页面顺序，diseffect置零。
[步骤2] 看main[]中是否有下一个元素，有就由main[]中获取该页面下标，并转到⑶；
没有，就转到⑺。
[步骤3] 如果该page业已在内存中，就转到⑵；否则就到⑷，同时未命中的diseffect加1。
[步骤4] 观察pagecontrol是否占满，如果占满需将使用队列（⑹中建立的）中最先进入的（就是队列第一个单元）pagecontrol单元“清干净”，同时将对应的page[]单元置为“不在内存中”。
[步骤5] 将该page[]与pagecontrol[]建立关系（可以改变pagecontrol[]的标示位，也可以采用指针连接，总之至少要使对应的pagecontrol单元包含两个信息：一是它被使用了，另外是哪个page[]单元使用的；page[]单元包含两个信息：对应的pagecontrol单元号、本page[]单元已在内存中）
[步骤6] 将用到的pagecontrol置入使用队列（这里的队列当然是一种先进先出的数据结构了，而不是泛指），返回⑵；
[步骤7] 显示(1-diseffect/total_instructiong)×100%，完成。
<程序设计>
为了便于操作和观察结果，用一个程序作为“引子”，先后fork ( )两个子进程SERVER和CLIENT进行通信，
SERVER端建立一个KEY为75的消息队列，等待其他进程发来的消息。
当遇到类型为1的消息时，则作为结束信号，取消该队列并退出SERVER。
SERVER每接收到一个消息后显示一句“( server) received”。
CLIENT端使用KEY为75的消息队列，先后发送类型从10到1的消息后退出。
最后的一个消息即是SERVER端需要的结束信号。
CLIENT每发送一条消息后显示一句“（client）sent”。
父进程在SERVER和CLIENT均退出后结束。
<程序代码>
# include <stdio.h>
# include <sys/types.h>
# include <sys/msg.h>
# include <sys/ipc.h>
# define MSGKEY 75 /* 定义关键词*/
struct msgform /* 定义消息结构*/
{
long mtype;
char mtrex [1030]; /*文本长度*/
}msg;
int msgqid, i;
viod CLIENT ( )
{ int i;
msgqid=msgget ( MSGKEY, 0777);
for (i=10, i>=1, i--)
{ msg, mtype=i;
printf (“(client) sent \n”)
msgsnd ( msgqid, &msg, 1024,0); /*发送消息msg入msgqid消息队列*/ }
exit ( );
}
Void SERVER ( )
{
msgqid=msgget ( MSGKEY, 0777| IPC_CREAT); /* 由关键字获得消息队列*/
do
{ msgrcv ( msgqid, &msg, 1030,0,0); /* 从msgqid队列接收消息msg */ printf (“(server) received \n”);
} while ( msg.type ! =1); /* 消息类型为1时，释放队列*/ magctl ( msgqid, IPC_RMID, 0);
exit (0);
}
void main ( )
{
while ((i= fork ( )) = = -1 );
if ( ! i) SERVER ( );
while ((i= fork ( )) = = -1 );
if ( ! i) CLIENT ( );
wait (0);
wait (0);
}
<运行结果>
从理想的结果来说，应当是每当CLIENT发送一个消息后，SERVER接收该消息，CLIENT再发送下一条。
也就是说“( client ) sent ”和“( server ) receive ”的字样应该在屏幕上交替出现。
实际的结果大多是，先由CLIENT发送了两条消息，然后SERVER接收一条消息。
此后CLIENT_SERVER交替发送和接收消息。
最后SERVER一次接收两条消息。
CLIENT和SERVER分别发送和接收了10条消息，与预期设想一致。
<分析>
message的传送和控制并不保证完全同步，当一个程序不在激活状态的时候，它完全可能继续睡眠，造成了上面的现象，在多次send message后才received message。
这一点有助于理解消息传送的实现原理。