北邮操作系统第二次实验_北邮操作系统实验
北邮操作系统第二次实验由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“北邮操作系统实验”。
北京邮电大学操作系统实验实验报告
班号：2011211314姓名：oneseven学号：
实验日期： 2013.12.16 实验名称： 操作系统实验
一、实验目的通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
二、实验内容
1.实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。
实验准备
用随机函数仿真进程进行内存申请，并且以较为随机的次序进行释放。对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。
2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。
1)最佳置换算法（Optimal）
2)先进先出法（Fisrt In First Out）
3)最近最久未使用（Least Recently Used）4)最不经常使用法（Least Frequently Used）
其中，命中率＝１－页面失效次数／页地址流长度。试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比较。
实验准备
本实验中主要的流程：首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。
实验可先从一个具体的例子出发。
(1)通过随机数产生一个指令序列，共2048条指令。指令的地址按下述原则生成： A：50%的指令是顺序执行的B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是：
A：在[0，1023]的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令
C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’ D：顺序执行一条指令，其地址为m’+1 E：在后地址[m’+2，2047]中随机选取一条指令并执行 F：重复步骤A-E，直到2048次指令(2)将指令序列变换为页地址流 设：页面大小为4K；
用户内存容量4页到32页； 用户虚存容量为32K。
在用户虚存中，按每K存放64条指令排列虚存地址，即2048条指令在虚存中的存放方式为：
第 0 条-第 63 条指令为第0页（对应虚存地址为[0，63]）第64条-第127条指令为第1页（对应虚存地址为[64，127]）
………………………………
－1－ 第1984条-第2047条指令为第31页（对应虚存地址为[1984，2047]）按以上方式，用户指令可组成32页。
以此为基础，给出较为一般的情形：仿真内存容量和虚存容量参数变化时的情形。
3.实现内存的slab分配器：
其基本思想是：一次向内核获取整数页，slab根据数据结构的大小进行划分为一个个小的数据结构，当需要时直接从该链表上摘取一个返回应用程序，当应用程序释放时，而非真正释放，只需要该空间放回到链表中，当分散的一页多块又聚集一页时，又会拼成一页，同时判断slab空闲的页数，如果空闲页超过一定的页数，就会向系统释放一定的页数。一个slab分配器只能管理一个指定大小的数据结构分配。
三、项目要求及分析
3.1实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。假设系统的可利用内存空间容量为2m个字(地址从0到2m-1)，则在开始运行时，整个内存区是一个大小为2m的空闲块，在运行了一段时间之后，被分隔成若干占用块和空闲块。为了在分配时查找方便起见，我们将所有大小相同的空闲块建于一张子表中。每个子表是一个双重链表，这样的链表可能有m+1个，将这m+1个表头指针用向量结构组织成一个表，这就是伙伴系统中的可利用空间表，如图所示：
分配算法：
当用户提出大小为n的内存请求时，首先在可利用表上寻找结点大小与n相匹配的子表，若此子表非空，则将子表中任意一个结点分配之即可；若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块，则将其中一部分分配给用户，而将剩余部分插入相应的子表中。
若2k-1
2、…、2k-i的子表中。回收算法：
在用户释放不再使用的占用块时，系统需将这新的空闲块插入到可利用空间表中去。这里，同样有一个地址相邻的空闲块归并成大块的问题。但是在伙伴系统中仅考虑互为“伙伴”的两个空闲块的归并。
何谓“伙伴”?如前所述，在分配时经常需要将一个大的空闲块分裂成两个大小相等的存
－2－ 储区，这两个由同一大块分裂出来的小块就称之“互为伙伴”。例如：假设p为大小为pow(2,k)的空闲块的初始地址，且p MOD pow(2,k+1)=0，则初始地址为p和p+pow(2,k)的两个空闲块互为伙伴。在伙伴系统中回收空闲块时，只当其伙伴为空闲块时才归并成大块。也就是说，若有两个空闲块，即使大小相同且地址相邻，但不是由同一大块分裂出来的，也不归并在一起。
由此，在回收空闲块时，应首先判别其伙伴是否为空闲块，若否，则只要将释放的空闲块简单插入在相应子表中即可；若是，则需在相应子表中找到其伙伴并删除之，然后再判别合并后的空闲块的伙伴是否是空闲块。依此重复，直到归并所得空闲块的伙伴不是空闲块时，再插入到相应的子表中去。
3.2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。
页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。页面替换算法主要用于如下几个地方：
(1)虚拟存储器中，主存页面（或程序段）的替换。
(2)Cache中的块替换。
(3)虚拟存储器的快慢表中，快表的替换。
(4)虚拟存储器中，用户基地址寄存器的替换。
在虚拟存储器中常用的页面替换算法有如下几种：
(1)最优替换算法，即OPT算法（OPTimal replacement algorithm）。上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然，这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换算法的命中率一定是最高的，它就是最优替换算法。
要实现OPT算法，唯一的办法是让程序先执行一遍，记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然，这样做是不现实的。因此，OPT算法只是一种理想化的算法，然而，它也是一种很有用的算法。实际上，经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的情况下，哪一种页面替换算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。(2)先进先出算法，即FIFO算法（First-In First-Out algorithm）。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，没有反映程序的局部性。因为最先调入主存的页面，很可能也是经常要使用的页面。
(3)最久没有使用算法，即LRU算法（Least Recently Used algorithm）。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的“多”与“少”简化成判断“有”与“无”，因此，实现起来比较容易。
(4)近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。这种算法选择近期最少访问的页面作为被替换的页面。显然，这是一种非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性。但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时，要从所有计数器中找出一个计数值最大的计数器。因此，通常采用如下一种相 －3－ 对比较简单的方法。
3.3实现内存的slab分配器
slab描述符和空闲对象管理部分成为 slab的管理部分，也可以称为slab头
slab的头可以放在slab自身，也可以放在 slab 之外。如果slab头放在了slab 之外，那么用户申请obj时，需要首先访问 slab头，slab头提供未使用free obj的指针
然后再访问这个free obj的地址。完成这项工作需要访问2个页块。会带来效率上的损失。slab头始终位于slab 也存在问题，比如一个页面只有4K，objsize = 2K，那么slab 头在slab 上，就意味着，这个4K的页面只能够分配一个obj。造成了内存的浪费。
如果 页数太少，存放的 obj个数少，那么 增加管理开销，同时 内存使用率低，如果页数太多对伙伴内存系统不好，所以需要一定的策略妥协。
这个妥协过程是有calculate_slab_order 这个函数来实现的。从 0阶（即一页）到kmalloc的最高阶 KMALLOC_MAX_ORDER，挨个尝试，由cache_estimate这个函数计算 如果选用order 阶，那么能分配 多少个 obj（num），剩余空间是多少（remainder）。所谓剩余空间，就是除去slab头（如果有的话），除去 obj*num，剩下的边角料空间是多少。需要分成两种情况去计算，分成两种情况的原因，很快就能看到 A)slab头不在slab上，即 flag & CFLGS_OFF_SLAB == 1的时候 这种情况比较简单，由于管理数据完全不在slab 上，size_tslab_size = PAGE_SIZE
换句话，slab头的大小取决于obj的个数，obj的个数取决于 slab头的大小，四、具体实现
4.1实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。
程序：
#include #include #include
#define MIN_MOMORY_SIZE 536870912
//随机产生的最小内存空间 #define WORKTIME 1500
//系统工作时间
#define MAX_REQ_SIZE 268435456
//申请空闲内存分配的最大容量：256M #define MIN_DUE 30
//使用内存块的最短时间 #define MAX_DUE 90
//使用内存块的最长时间 #define OCCUPY_INTERVAL 60
//每次分配的最大间隔 #define USED 1
//内存块被使用 #define UNUSED 0
//内存块未被使用
//内存块链表结点结构 typedefstructbuddy_node { int flag;
//标记空间是否被使用
－4－ int base;
//本块儿内存的基地址
int occupy;
//实际使用空间大小
int fragment;
//碎片大小
intduetime;
//使用时间
structbuddy_node *nextPtr;
//指向下一个结点 } Buddy, *BuddyPtr;
IndexTable table[INDEX_SIZE];//使用哈希表管理伙伴系统 int ready = 0;
//需要分配内存的时刻 intavailSpace;
//可分配空间大小 inttotalFragment = 0;
//总碎片大小
//函数：添加结点（形参为内存块结点的信息）
void insert_node(inti, intinbase, int f, intocc, int frag, int d){ BuddyPtrnewnodePtr = NULL, prePtr = NULL, curPtr = NULL;
newnodePtr =(BuddyPtr)malloc(sizeof(Buddy));//分配结点 newnodePtr->base = inbase;newnodePtr->flag = f;newnodePtr->occupy = occ;newnodePtr->fragment = frag;newnodePtr->duetime = d;newnodePtr->nextPtr = NULL;
if(table[i].headPtr == NULL)
table[i].headPtr = newnodePtr;
else { curPtr = table[i].headPtr;prePtr = NULL;
//按地址顺序插入内存块
while(curPtr&&curPtr->base nextPtr;
}
if(prePtr == NULL){
//插在最前 newnodePtr->nextPtr = curPtr;
table[i].headPtr = newnodePtr;
}
else if(curPtr == NULL){
//插在最后 prePtr->nextPtr = newnodePtr;
}
else {
//插在中间 prePtr->nextPtr = newnodePtr;newnodePtr->nextPtr = curPtr;
－5－
}
} }
//函数：删除结点
intdelete_node(inti, BuddyPtrdelPtr){ BuddyPtrprePtr = NULL, curPtr = NULL;intbasehold = delPtr->base;
curPtr = table[i].headPtr;
while(curPtr!= delPtr){ //寻找要删除的结点的位置 prePtr = curPtr;curPtr = curPtr->nextPtr;
}
if(prePtr == NULL)
//要删除的结点在最前
table[i].headPtr = curPtr->nextPtr;
else
//要删除的结点不在链表的最前 prePtr->nextPtr = curPtr->nextPtr;
free(curPtr);
//释放结点
return basehold;
//返回删除的内存块结点的基地址 }
//函数：伙伴系统的分配算法 void buddy_allocate(inttime_slice){ inti, j, size, due;int state = 0;
//分配状态：0为未分配，1为已分配 intinbase, basehold;BuddyPtrcurPtr = NULL;
if(ready == time_slice){ //到达分配内存的时刻 printf(“Time %d:”, time_slice);
size = 1 + rand()% MAX_REQ_SIZE;
//申请使用内存的大小
due = MIN_DUE + rand()%(MAX_DUEsize;curPtr->duetime = due + ready;
//修改可系统分配空间和碎片大小 availSpace-= table[i].nodesize;totalFragment += curPtr->fragment;
state = 1;//标记已分配
break;
}
//空闲块的大小刚大于申请大小的2倍
else { basehold = delete_node(i, curPtr);//删除较大的空闲块并保留其基地址 inbase = basehold + table[i].nodesize;
j = i;
//分割空闲块
do {
j--;inbase-= table[j].nodesize;
//设置要添加内存块结点的基地址 insert_node(j, inbase, UNUSED, 0, 0, 0);//添加较小的空闲块 printf(“A block cut takes placen”);
} while(table[j].nodesize / size > 1);
//分配
insert_node(j, basehold, USED, size, table[j].nodesizesize;
state = 1;//标记已分配
}
}
//块被占用，查看下一结点
else curPtr = curPtr->nextPtr;
}
}
} printf(“Allocated %d,Fragment %d,Due %dn”, size, totalFragment, ready+due);
－7－
}
else if((availSpace= size))printf(“Allocation failed because of fragment!n”);
else printf(“Allocation failed because of no enough unused space!n”);
ready +=(1 + rand()% OCCUPY_INTERVAL);//下次需要分配内存的时刻
} }
//函数：伙伴系统的回收算法 void buddy_retrieve(inttime_slice){ inti, basehold, dif;int f = 0;intModnext=0;BuddyPtrcurPtr = NULL, todelPtr = NULL;
//依次查找，并回收需要回收的块
for(i = 0;i
if(table[i].headPtr){ curPtr = table[i].headPtr;
while(curPtr){
if((curPtr->flag == USED)&&(curPtr->duetime == time_slice)){//需要回收
//修改可系统分配空间和碎片大小 availSpace += table[i].nodesize;totalFragment-= curPtr->fragment;
//回收为空闲块 curPtr->flag = UNUSED;curPtr->occupy = 0;curPtr->fragment = 0;curPtr->duetime = 0;printf(“Time %d:Retrieve %d,Fragment %dn”, time_slice, table[i].nodesize, totalFragment);
} curPtr = curPtr->nextPtr;
}
}
}
//合并空闲块
for(i = 0;i
if(table[i].headPtr){
－8－ curPtr = table[i].headPtr;
while(curPtr&&curPtr->nextPtr){
//将地址连续且都为空闲的块合并后加入下一级的链表中
if(curPtr->flag == UNUSED &&(curPtr->nextPtr)->flag == UNUSED){ dif =(curPtr->nextPtr)->base-curPtr->base;
Modnext =((int)(curPtr->nextPtr->base))%(2*table[i].nodesize);
if((dif == table[i].nodesize)&&(Modnext==0)){
//删除两个结点 todelPtr = curPtr;curPtr = curPtr->nextPtr;basehold = delete_node(i, todelPtr);todelPtr = curPtr;curPtr = curPtr->nextPtr;delete_node(i, todelPtr);insert_node(i+1, basehold, UNUSED, 0, 0, 0);//添加合并后的结点 printf(“Two blocks mergen”);
}
else curPtr = curPtr->nextPtr;
}
else curPtr = curPtr->nextPtr;
}
}
} }
//函数：伙伴系统的处理过程 void buddy_system(void){ inttime_slice = 0;
//在每个时间片内使用分配算法和回收算法
for(;time_slice
//分配算法 buddy_retrieve(time_slice);
//回收算法
} }
int main(intargc, char *argv[]){ intmemory_size;
－9－ ini_index();
//初始化哈希索引表 srand(time(NULL));
//设置随机数种子
//随机产生需要管理的内存大小：512M ~ 1G
memory_size = MIN_MOMORY_SIZE + rand()% MIN_MOMORY_SIZE;printf(“The size of memory is:%dn”, memory_size);
int_system(memory_size);
//初始化伙伴系统
buddy_system();
//伙伴系统的处理过程
printf(“Time %d:System execution stops and the spaces are all freed.n”, WORKTIME);
free_system();
//释放所有结点
system(“pause”);
return 0;}
4．2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。程序：
#include #include #include #define TRUE 1 #define FALSE 0 #define INVALID-1 #define NUL 0 #define total_instruction 320 //指令流长 #define total_vp 32
//虚页长 #define clear_period 50
//清零周期
typedefstruct {
intpn;
//页号 intpfn;
// 面号
int counter;
// 一个周期内访问该页面的次数 int time;
// time为访问时间 }pl_type;pl_typepl[total_vp];//页面结构数组
structpfc_struct{
//页面控制结构 intpn,pfn;structpfc_struct *next;};typedefstructpfc_structpfc_type;
－10－
pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;intdiseffect,a[total_instruction];int page[total_instruction], offset[total_instruction];/*
Name: void Lprintf(void)
Achieve: 格式控制 */ void Lprintf(void){ inti,j;printf(“|”);
for(i = 1;i
{
for(j = 1;j
if(i!=6)printf(“+”);
} printf(“|n”);
} /*
Name: void initialize(inttotal_pf)
Achieve:初始化相关数据结构 */ void initialize(inttotal_pf){ inti;diseffect=0;
for(i=0;i
{ pl[i].pn=i;pl[i].pfn=INVALID;
//置页面控制结构中的页号，页面为空
pl[i].counter=0;pl[i].time=-1;//页面控制结构中的访问次数为0，时间为-1
}
for(i=1;i
{ pfc[i-1 ].next=&pfc[i];pfc[i-1].pfn=i-1;//建立pfc[i-1]和pfc[i]之间的连接
}
pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0];
//页面队列的头指针为pfc[0] } /*
－11－ Name:void FIFO(inttotal_pf)
Achieve:先进先出法（Fisrt In First Out）*/
void FIFO(inttotal_pf){ inti,j;pfc_type *p;//中间变量
initialize(total_pf);//初始化相关页面控制用数据结构
busypf_head=busypf_tail=NULL;//忙页面队列头，队列尾链接
for(i=0;i
if(pl[page[i]].pfn==INVALID)
//页面失效
{
diseffect+=1;//失效次数
if(freepf_head==NULL)//无空闲页面
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID;
freepf_head=busypf_head;//释放忙页面队列的第一个页面
freepf_head->next=NULL;//表明还是缺页*/
busypf_head=p;
}
p=freepf_head->next;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
freepf_head->next=NULL;//使busy的尾为null
if(busypf_tail==NULL)
{
busypf_tail=busypf_head=freepf_head;
}
else
{
busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;
} } printf(“%6.3f”,1-(float)diseffect/320);} /*
Name: void LRU(inttotal_pf)
Achieve: 最近最久未使用（Least Recently Used）*/
－12－ void LRU(inttotal_pf){ intmin,minj,i,j,present_time;//minj为最小值下标
initialize(total_pf);present_time=0;for(i=0;i
if(pl[page[i]].pfn==INVALID)//页面失效
{
diseffect++;
if(freepf_head==NULL)//无空闲页面
{
min=32767;//设置最大值
for(j=0;j
{
if(min>pl[j].time&&pl[j].pfn!=INVALID)
{
min=pl[j].time;
minj=j;
}
}
freepf_head=&pfc[pl[minj].pfn];
//空出一个单元
pl[minj].pfn=INVALID;
pl[minj].time=0;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效
pl[page[i]].time=present_time;
freepf_head=freepf_head->next;//减少一个free 页面
}
else
{
pl[page[i]].time=present_time;//命中则增加该单元的访问次数
present_time++;
} } printf(“%6.3f”,1-(float)diseffect/320);} /* Name:void OPT(inttotal_pf)
Achieve:最佳置换算法（Optimal）*/ void OPT(inttotal_pf){
－13－ inti,j, max,maxpage,d,dist[total_vp];pfc_type *t;initialize(total_pf);for(i=0;i
if(pl[page[i]].pfn==INVALID)
/*页面失效*/
{
diseffect++;
if(freepf_head==NULL)
/*无空闲页面*/
{
for(j=0;j
{
if(pl[j].pfn!=INVALID)
dist[j]=32767;
else
dist[j]=0;
}
for(j=0;j
{
if((pl[j].pfn!=INVALID)&&(dist[j]==32767))
{
dist[j]=j;
}
}
max=0;
for(j=0;j
if(max
{
max=dist[j];
maxpage=j;
}
freepf_head=&pfc[pl[maxpage].pfn];
freepf_head->next=NULL;
pl[maxpage].pfn=INVALID;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
} } printf(“%6.3f”,1-(float)diseffect/320);} /*
Name: vodi LFU(inttotal_pf)
Achieve:最不经常使用法（Least Frequently Used）
－14－ */ void LFU(inttotal_pf)
{ inti,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;i
if(pl[page[i]].pfn==INVALID)//页面失效
{
diseffect++;
if(freepf_head==NULL)//无空闲页面
{
min=32767;
//获取counter的使用用频率最小的内存
for(j=0;j
{
if(min>pl[j].counter&&pl[j].pfn!=INVALID)
{
min=pl[j].counter;
minpage=j;
}
}
freepf_head=&pfc[pl[minpage].pfn];
pl[minpage].pfn=INVALID;
pl[minpage].counter=0;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效
pl[page[i]].counter++;
freepf_head=freepf_head->next;//减少一个free 页面
}
else
{
pl[page[i]].counter;
pl[page[i]].counter=pl[page[i]].counter+1;
} } printf(“%6.3f”,1-(float)diseffect/320);}
int main(int){
intS,i;
－15－ srand((int)getpid());
for(i=0;i
{
S=(int)rand()%320;
a[i]=S;
//任选一指令访问点
a[i+1]=a[i]+1;//顺序执行一条指令
a[i+2]=(int)rand()%a[i+1];//执行前地址指令m'
a[i+3]=a[i+2]+1;//顺序执行一条指令
a[i+4]=(int)rand()%(319-a[i+2]-1)+a[i+2]+2;//执行后地址指令
} for(i=0;i
{
page[i]=a[i]/10;
offset[i]=a[i]%10;}
printf(“FrametOPTtFIFOtLRUtLFU n”);for(i=4;i
{
printf(“%dt”,i);OPT(i);printf(“t”);
FIFO(i);printf(“t”);
LRU(i);
printf(“t”);
LFU(i);
printf(“n”);} system(“pause”);return 0;} 4.3 实现内存的slab分配器 程序: #include #include #include using namespace std;－16－
－17－
}
五、调试运行结果
－18－ 5.1 实现一个内存管理的伙伴算法
5.2设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。
－19－
5.3 实现内存的slab分配器
六、所遇问题及解决方法
1.在写第一个程序的时候，对树的合并在之前的学习中，有比较多的学习，数据结构中此程序有详细的介绍，因此在编写这个程序的时候，比较顺利的完成了要求。但要求中需要产生一些随机的数据，重新对随机仿真函数进行回顾，最后较为顺利的完成了程序。2.第二个程序，要求随机产生一些数据，对srand()和rand()函数定义和产生指令序列，在进一步的学习中，完成了这些函数，仿真内存容量和虚存容量参数变化时的情形，对此不太熟悉，四个算法对要求较高，在完成算法的学习后，完成了程序。
3.第三个程序因不太理解其要求，上网搜寻了一些代码，但对其最后的结果依然没有得出，为此询问了同学，但不知是否正确。
－20－
