操作系统课程设计 LRU算法的实现.doc

《操作系统原理》
课程设计报告

姓 名： 黄崧岳
班 级： BX1010
学 号： 5
指导老师： 苏庆刚

二〇一二年 十二 月十四日
目 录
一、《操作系统原理》课程设计的目的与要求 1
1目的 1
2要求 1
二、简述课程设计内容、主要功能和实现环境 1
1课程设计内容 1
2主要功能 1
3实现环境 2
三、任务的分析、设计、实现和讨论 2
1任务的分析 2
2任务的设计与实现 3
4思考题的解答和讨论 10
四、 《操作系统》课程设计小结 14
五、参考文献 14
附录 14

一、《操作系统原理》课程设计的目的与要求
1目的
近年来，由于大规模集成电路（LSI）和超大规模集成电路（VLSI）技术的发展，使存储器的容量不断扩大，价格大幅度下降。但从使用角度看，存储器的容量和成本总受到一定的限制。所以，提高存储器的效率始终是操作系统研究的重要课题之一。虚拟存储技术是用来扩大内存容量的一种重要方法。学生应独立地用高级语言编写几个常用的存储分配算法，并设计一个存储管理的模拟程序，对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。
2要求
任务四采用最近最少使用页淘汰算法(LRU)实现。为了比较真实地模拟存储管理，可预先生成一个大致符合实际情况的指令地址流。然后模拟这样一种指令序列的执行来计算和分析各种算法的访问命中率。

二、简述课程设计内容、主要功能和实现环境
1课程设计内容
最近最少使用页淘汰算法(LRU)，这是一种经常使用的方法。有各种不同的实施方案，这里采用的是不断调整页表链的方法，即总是淘汰页表链链首的页，而把新访问的页插入链尾。如果当前调用页已在页表内，则把它再次调整到链尾。这样就能保证最近使用的页，总是处于靠近链尾部分，而不常使用的页就移到链首，逐个被淘汰，在页表较大时，调整页表链的代价也是不小的。
2主要功能
（1） 菜单函数int menu_select()：用于显示主菜单，可在其中选择1.自定义进程数和块数；2.显示显示用户自定义的进程数和块数；3.进行LRU算法4.退出程序。
（2） 最近最久未使用算法函数void LRU()：此函数是将随机产生的页面进行最近未使用便置换的函数，也是本程序的主要部分。
（3） 自定义进程数和块数函数void Zidingyi()：此函数是主菜单中的第一个选项，即用户可以自定义所需的进程数和块数。
（4） 显示用户自定义的进程数和块数函数void ShowCustomer()：此函数是用于显示用户自定义的进程数和块数的情况。
（5） 修改块数函数void Xiugaikuaishu()：此函数是在进行LRU算法后，可以在原来的进程数的基础上，修改块数并重新生成一组LRU算法的过程。
（6） 显示每次换页后的结果函数void ShowResult()：此函数是显示在LRU算法的执行过程中每次换页的情况。
（7） 显示一定不用换页的函数void ShowNot()：此函数是显示最近使用过的页面，即不用换页的结果。
3实现环境
本次课程设计结合算法的特点，采用Windows操作系统平台。开发工具为Microsoft Visual C++6.0。
三、任务的分析、设计、实现和讨论
1任务的分析
本示例是采用页式分配存储管理方案，并通过分析计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣。另外也考虑到改变页面大小和实际存储器容量对计算结果的影响，从而可为算则好的算法、合适的页面尺寸和实存容量提供依据。
本程序是按下述原则生成指令序列的：
（1） 50%的指令是顺序执行的。
（2） 25%的指令均匀散布在前地址部分。
（3） 25%的指令均匀散布在后地址部分。
示例中选用最佳淘汰算法（OPT）和最近最少使用页面淘汰算法（LRU）计算页面命中率。公式为

假定虚存容量为32K，页面尺寸从1K至8K，实存容量从4页至32页。
2任务的设计与实现
2.1 main( )函数流程图：
开始
进入主菜单
是否输入为“1”
是否输入为“2”
是否输入为“3”
是否输入为“4”
显示进程数和块数
自定义进程数和块数
进入LRU算法
退出程序
N
N
N
N
Y
Y
Y
Y
结束

2.2 主菜单流程图：

2.3 LRU函数流程图：

2.4 Zidingyi( )函数流程图：

2.5 ShowCustomer( )函数流程图：

2.6 ShowNot( )函数流程图：

2.7 ShowResult( )函数流程图：

3操作过程和结果分析
按1进入自定义进程数和块数

按2显示进程数，块数和随机分配页号

按3实现LRU算法，输出命中率

按1修改物理块数，重新实现LRU算法并输出命中率

按4退出程序

FIFO算法
该算法总是淘汰最先进入内存的页面，既选择内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需要把一个进程已调入内存的页面，按照先后测序链接成一个队列，并设置一个指针，使他总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。 这里，我们用下面的例子，采用FIFO算法进行页面置换。当进程第一次访问页面2时，将把第七页换出，因为它是最先被调入内存的；在第一次范文页面3时，又将把第零页换出，因为他在现有的2，0，1三个页面中是最老的页。由下图可以看出，利用FIFO算法时进行了十二次页面置换，比最佳置换算法正好多一倍。

结果分析——两种算法的比较：
先进先出(FIFO)算法较易实现，比较适用于具有线性顺序特性的程序，而对其他特性的程序则效率不高。缺页中断率为最佳算法的2~3倍；增加可用主存块的数量会导致更多的缺页，此算法还可能出现抖动现象异常。
最近最久未被使用(LRU)算法的实现需要硬件支持，基于程序的局部性原理，所以适用用大多数程序，此算实现必须维护一个特殊的队列——页面淘汰队列。关键是确定页面最后访问以来所经历的时间。

4思考题的解答和讨论
（1）设计一个界地址存储管理的模拟系统，模拟界地址方式下存储区的分配和回收过程。
提示：必须设置一个内存分配表，按照分配表中有关信息实施存储区的分配，并不断根据存储区的分配和回收修改该表。算法有首次匹配法，循环首次匹配法和最佳匹配法等。可用各种方法的比较来充实实习内容。可使用碎片收集和复盖等技术。
答：
开始
选择菜单
0
退出程序
1
2
3
分配主存

回收主存
显示主存
N
Y
N
N
N
Y
Y
Y

（1）数据结构及说明
本程序为可变分区管理方式主存分配回收模拟程序，采用首次适应策略。
主要数据结构：
空闲区链表FBC，分配区链表ABC：
表中记录块的起始地址和大小，块按照始地址大小从小到大排列。
（2）功能实现
①分配时，根据用户提供的作业大小，从第一个空闲块开始查找，将找到的第一个足够大的空闲块块分配给该作业，返回给用户该块始地址。如果该块剩余部分小于特定阈值（本程序为2k),将该块整体分配给此作业，将该块直接加入分配区链表，若剩余块大于或等于阈值，将分配块加入分配区链表，剩余部分作为新的空闲块.另：程序开始时已将0到20k分配给操作系统。
②回收时，根据用户提供的作业的始地址，在分配区表查找，若找到该块，将其加入空闲区链表，提示用户释放成功。若新形成的空闲块与其前后的空闲块相连，合并空闲块形成更大的空闲块。
③显示，用户可随时选择查看内存分配状态图以及空闲区表与分配区表，在分配或回收成功时，程序自动显示内存分配状态图、空闲区表与分配区表。

（2）自行设计或选用一种较为完善的内存管理方法，并加以实现。
提示：设计一个段页式管理的模拟程序或通过一个实际系统的消化和分析，编制一个程序来模拟该系统。
答:

分配总空间大小为128，若输入的进程大于该数，则显示“占用空间过大，分配失败”

若分配的进程大小为0，则显示“进程空间大小错误”

选择1分配内存，输入内存名和占用空间大小即可分配内存，显示的项目有进程名、起始地址和长度，已分配的内存分配情况会显示出来，如上图。空间分配满则显示“无空闲区”

选择2回收内存，输入已分配的内存名称即可回收该内存，并显示剩余的已分配内存

四、 《操作系统》课程设计小结
页面置换算法理解比较容易，这次根据学号要求实现的是LRU算法的实现。
分配到我的是两道思考题，其实这两道思考题的算法是差不多的，所以第一题我没有去编写只是写出了大概的思路和算法框图。其实这两种算法的程序编写比较容易，虽然不全是自己编写的，一部分是参考的网上的例题，但是通过对每一语句的理解，自己弄懂了整个程序的执行原理。但是，在编写过程中自己还是遇到了一些问题。
最大的一个问题就是两个算法的正确实现，在程序的编写时，两个程序是分开进行编写的，分别执行起来没有什么问题，但是把两个程序融合在一起后，却出现了问题，即在执行完成一个算法后再执行另外一个算法时，开始的数据是紧接着上次算法结果的数据进行实验的。这个问题困扰了我好长时间，直到现在还没有很好的解决掉，程序只能分别执行一次，如果再进行执行的话，就会出现问题。
自己的编程技术不好，程序编的也很繁琐，但是基本的要求已经实现了，希望这次的实验是自己动手的一个开始，自己应该更加努力，再接再厉。

五、参考文献
【1】 《计算机操作系统》 孙雅如 等 编著 西安电子科技大学 2003
【2】 《计算机操作系统》（第2版）吴企渊 等 编著 清华大学出版社 2003
【3】 《操作系统教程》 徐甲同 编著 西安电子科技大学出版社.2001

附录
LRU算法实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define Maxsize 300
void Xiugaikuaishu();
void Inition();
void Zidingyi();
void ShowCustomer();
void ShowResult();
void ShowNot();
void LRU();
int menu_select();
int pageNum = 0; //页面数
int pages[Maxsize];//存储页号
int Fuzhu[Maxsize];//辅助数组
int Time[Maxsize];//记录页在内存中的时间
int block;//记录物理块数
int Fz;//辅助变量

int main()
{
for(;;) /*循环无限次*/
{
switch(menu_select())
{
case 1: Zidingyi();
break;
case 2: ShowCustomer();
break;
case 3: LRU();
break;
case 4:
{
printf("谢谢使用LRU算法!\n");
printf(" Bye Bye^-^\n");
exit(0);
}/*如菜单返回值为13则程序结束*/
}
}

return 0;
}

int menu_select()
{
int n;
printf(" ┏━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
printf(" ┃ 请求页式存储管理中LRU算法的实现 ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ 1. 自定义进程数和块数 ┃\n");
printf(" ┃ 2. 显示用户自定义 ┃\n");
printf(" ┃ 3. LRU算法 ┃\n");
printf(" ┃ 4. EXIT ┃\n");
printf(" ┃ ┃\n");
printf(" ┃ ┃\n");
printf(" ┣━━━━━━━━━━━━━━━━━━━━━━━━┫\n");
do
{
printf("\n\t\t\t输入你的选择(1~4):");
scanf("%d",&n);
}while(n<1||n>4); /*如果选择项不在1~3之间则重输*/ //||如果一个以上为真，则结果为真，二者都为假时，结果为假
return(n); /*返回选择项，主函数根据该数调用相应的函数*/
}

void Zidingyi() //自定义进程数和块数
{
int i;
system("cls");
printf("*******************************************************\n");
printf(" 页式储存管理—LRU算法 \n");
printf("*******************************************************\n");
printf("-------------------自定义进程数和块数------------------\n");
printf("\n");
printf("请输入进程数：");
scanf("%d",&pageNum);
for(i = 0 ; i < pageNum ; i++)
{
pages[i] = rand()%100; //初始化页号，初始值在0-100之内
}
getchar();
printf("请输入块数：");
scanf("%d",&block );
getchar();
}

void LRU()//最近最久未使用算法
{
int i,j;
int WithOutPages = 0;//记录缺页数
printf("*******************************************************\n");
printf("------------------LRU算法结果显示:---------------------\n");
printf("\n");
ShowNot();
for(i = Fz ; i < pageNum; i++)
{
int key = 0;
for(j = 0 ; j < block ; j++)//判断该页是否在物理块中
{
if(Fuzhu[j] == pages[i])
{
key = 1;
Time[j] = i;//更新时间
break;
}
}

if(key == 0)//若该页不在内存中
{
WithOutPages++;
int min = Time[0];
int flag = 0;
for(j = 1 ; j < block ; j++)
{
if(min > Time[j])
{
min = Time[j];//找到最久的页面
flag = j;
}
}

Time[flag] = i;//记录时间
Fuzhu[flag] = pages[i];
ShowResult();
}
}
printf("置换次数为： %d \n",WithOutPages);
printf("页面总数为： %d \n",pageNum);
double re = ((double)WithOutPages)/((double)pageNum);
printf("置换率为： %.2lf\n",re);
printf("命中率为： %.2lf\n",1-re);
printf("缺页次数为： %d \n",WithOutPages+block);
printf("页面总数为： %d \n",pageNum);
re = ((double)(WithOutPages+block))/((double)pageNum);
printf("缺页率为： %.2lf\n",re);
printf("*******************************************************\n");
printf("--------------按1修改块数，按2返回主菜单---------------\n");
printf("\n");
printf(" Yes--1，No--2 \n");
int la;
scanf("%d",&la);
if(la==1)
{
Xiugaikuaishu();
}
else
{
printf("*******************************************************\n");
printf("-------------------------------------------------------\n");
system("cls");
}
}
void ShowResult()//显示每次换页后的结果
{
int i;
for(i = 0 ; i < block ; i++)
{
printf(" %d",Fuzhu[i]);
}
printf("\n");
}
void Xiugaikuaishu()
{
system("cls");
printf("*******************************************************\n");
printf("----------------请输入需要修改块的数目:----------------\n");
printf("");
{
int a;
scanf("%d",&a);
block = a;
}
ShowCustomer();//显示自定义页面信息
LRU();
}
void ShowCustomer()//显示用户自定义的进程数和块数
{ system("cls");
int i;
printf("*******************************************************\n");
printf("-------------------------显示:-------------------------\n");
printf("进程数为: %d\n",pageNum);
printf("页号分别为: ");
for(i = 0 ; i < pageNum ; i++)
{
printf("%d ",pages[i]);
}
printf("\n");
printf("可用物理块数为: %d\n",block);
printf("*******************************************************\n");
printf("-----------------按任意键可返回主菜单------------------\n");
getchar();
}
void ShowNot()//显示一定不用换页的部分
{
Fz = block;
int i,j,k=0,key = 0;
for(i = 0 ; i < Fz ; i++)
{
int flag = 0;
for(j = 0 ; j <= i-1 ; j++)
{
if(Fuzhu[j] == pages[i])
{
Time[j] = i;
flag = 1;
Fz = Fz+1;
key++;
}
}

if(flag == 0)
{
Time[k] = i;
Fuzhu[k] = pages[i];
k++;
for(j = 0 ; j <= i-key ; j++)
{
printf(" %d",Fuzhu[j]);
}
printf("\n");
}
}
}

思考题2：内存管理小程序
#include <iostream.h>
#include <stdio.h>
#include <string.h>

struct program
{
char name[30];
long start;
long length;
struct program *next;
};

struct space
{
long start;
long length;
struct space *next;
};

void creat();
void allot();
void back();
void callback(program *r);
void sort(space *L);
void sort(program *S);
void display(space *L);
void display(program *S);

space *L;
program *S;

void creat()
{
L=new space;
space *p=new space;
p->start=0;
p->length=128;
p->next=NULL;
L->next=p;
S=new program;
S->next=NULL;
}
void allot()
{
program *q;
q=new program;
cout<<"请输入进程名和占用空间大小:"<<endl;
cin>>q->name>>q->length;
if(q->length<=0)
{
cout<<"进程空间大小错误."<<endl;
delete q;
return;
}
space *p,*r;
p=L;
r=p;
while(p->next!=NULL&&p->next->length<q->length)
{
r=p;
p=p->next;
}
if(p->next==NULL)
{
cout<<"占用空间过大，分配失败"<<endl;
delete q;
return;
}
else
{
q->start=p->next->start;
q->next=S->next;
S->next=q;

p->next->length-=q->length;
if(p->next->length!=0)
p->next->start+=q->length;
else
{
if(p->next->next!=NULL)
p->next=p->next->next;
else
{
r->next=NULL;
delete p->next;
}
}
}
display(L);
display(S);
}
void back()
{
char name[30];
cout<<"输入要回收的进程名：";
cin>>name;
program *p;
p=S;
while(p->next!=NULL)
{
if(strcmp(p->next->name, name)==0)
{
callback(p);
return;
}
p=p->next;
}
if(p->next==NULL)
cout<<"此进程不存在,内存回收失败"<<endl;

}
void callback(program *t)
{
program *r;
r=t->next;
space *p,*q;
long n;
n=r->length;
if(L->next==NULL)
{
space *w=new space;
w->start=0;
w->length=n;
w->next=NULL;
L->next=w;
t->next=r->next;
delete r;
cout<<"此进程内存回收完毕."<<endl;
display(L);
display(S);
return;
}
p=L->next;
while(p!=NULL&&p->start<r->start)
{
q=p;
p=p->next;
}
if((q->start+q->length==r->start)&&(r->start+n==p->start)) //上下均空
{
q->next=p->next;
q->length=q->length+p->length+n;
t->next=r->next;
delete r;
}
else if(r->start+n==p->start) //下邻空
{
p->start-=n;
p->length+=n;
t->next=r->next;
delete r;
}
else if(q->start+q->length==r->start)
{
q->length+=n;
t->next=r->next;
delete r;
}
else
{
space *sp=new space;
sp->start=r->start;
sp->length=n;
sp->next=L->next;
L->next=sp;
t->next=r->next;
delete r;
}
cout<<"此进程内存回收完毕."<<endl;
display(L);
display(S);
}
void display(space *L)
{
sort(L);
space *p=L->next;
cout<<endl<<"空闲区情况："<<endl;
if(p==NULL)
{ cout<<"无空闲区了."<<endl; return;}
while(p!=NULL)
{
cout<<"起始地址:"<<p->start<<" 长度:"<<p->length<<endl;
p=p->next;
}
}
void display(program *S)
{
sort(S);
program *p=S->next;
cout<<endl<<"进程内存分配情况："<<endl;
if(p==NULL)
{ cout<<"内存中无进程."<<endl; return;}
while(p!=NULL)
{
cout<<"进程名:"<<p->name<<" 起始地址:"<<p->start<<" 长度:"<<p->length<<endl;
p=p->next;
}
cout<<endl;
}
void sort(space *L) //链表排序
{
space *p=L->next, *q, *r;
if(p!=NULL)
{
r=p->next;
p->next=NULL;
p=r;
while(p!=NULL)
{
r=p->next;
q=L;
while(q->next!=NULL&&q->next->start<p->start)
q=q->next;
p->next=q->next;
q->next=p;
p=r;
}
}
}
void sort(program *S) //链表排序
{
program *p=S->next, *q, *r;
if(p!=NULL)
{
r=p->next;
p->next=NULL;
p=r;
while(p!=NULL)
{
r=p->next;
q=S;
while(q->next!=NULL&&q->next->start<p->start)
q=q->next;
p->next=q->next;
q->next=p;
p=r;
}
}
}

void main()
{
creat();
int a;
cout<<" 内存分配与回收模拟"<<endl;
cout<<"1:分配内存"<<endl;
cout<<"2:回收内存"<<endl;
cout<<"0:退出"<<endl;
while(1)
{
cout<<endl<<"请按键选择：";
cin>>a;
if(a>2||a<0)
{
cout<<endl<<"输入错误，请重新输入：";
continue;
}
switch(a)
{
case 1: allot(); break;
case 2: back(); break;
case 0: goto end;
}
}
end:
getchar();
}

26