操作系统课程设计报告

一、课程设计任务划分

二、基本原理

（一）页面置换算法定义

在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内 存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

（二）所使用的算法

1) 最佳置换算法(opt)：将以后永不使用的或许是在最

长(未来)时间内 不再被访问的页面换出。

2) 先进先出算法(fifo)：淘汰最先进入内存的页面，即 选择在内存中驻留时间最久的页面予以淘汰。

3) 最近最久未使用算法(lru)：淘汰最近最久未被使用 的页面。

（三）设计思想

选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：

opt基本思想：

是用一维数组page[psize]存储页面号序列，memery[msize]是存储装入物理块中的页面。数组ne_t[msize]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。 fifo基本思想：

是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[msize]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。 lru基本思想：

是用一维数组page[psize]存储页面号序列，memery[msize]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。

三、基本思路

实验环境：vc ，编程语言：c语言 #include #include /_全局变量_/

int msize; /_物理块数_/

int psize; /_页面号引用串个数_/

static int memery[10]={0}; /_物理块中的页号_/ static int page[100]={0}; /_页面号引用串_/ static int temp[100][10]={0}; /_辅助数组_/ /_置换算法函数_/ void fifo; void lru; void opt; /_辅助函数_/

void print(unsigned int t); void designby; void download;

void mdelay(unsigned int delay); /_主函数_/ void main {

int i，k，code; system(color 0a); designby; printf(┃请按任意键进行初始化操作... ┃ ); printf(┗━━━━━━━━━━━━━━━━━━━━━┛ ); printf( >;;;>;;;>;;;); getch; system(cls); system(color 0b); printf(请输入物理块的`个数(m<=10)：); scanf(%d，msize); printf(请输入页面号引用串的个数(p<=100)：); scanf(%d，psize); puts(请依次输入页面号引用串(连续输入，无需隔开)：); for(i=0;i< p=>;;;

scanf(，page[i]); download; system(cls); system(color 0e); do{ puts(输入的页面号引用串为：); for(k=0;k<=(psize-1)/20;k )

{ for(i=20_k;(i<20_(k 1));i ) 20==0)||(((i 1));

(i==psize-1))) printf(%d ，page[i]); else printf(%d ，page[i]); } } printf(_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ); printf(_ 请选择页面置换算法： _ ); printf(_ ----------------------------------------- _ );

printf(_ 1.先进先出(fifo) 2.最近最久未使用(lru) _ ); printf(_ 3.最佳(opt) 4.退出 _ ); printf(_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ); printf(请选择操作：[ ]); scanf(%d，code); switch(code) {

case 1:

fifo; break; case 2:

lru; break; case 3:

opt; break; case 4: system(cls); system(color 0a); designby; /_显示设计者信息后退出_/ printf(┃谢谢使用页面置换算法演示器！

┃ ); printf(┗━━━━━━━━━━━━━━━━━━┛ ); e_it(0); default: printf(输入错误，请重新输入：); } printf(按任意键重新选择置换算法：>;;;>;;;>;;;); getch;

system(cls); }while (code！=4); getch; }

/_载入数据_/ void download { int i; system(color 0d); printf(╔════════════╗ ); printf(║正在载入数据，请稍候 ！║ ); printf(╚════════════╝ ); printf(loading... ); printf( for(i=0;i<51;i ) printf(); for(i=0;i<50;i ) { mdelay((psize msize)/2); printf(>;;;); } printf( finish. 载入成功，按任意键进入置换算法选择界面：

>;;;>;;;>;;;); getch; }

/_设置延迟_/

void mdelay(unsigned int delay) {

unsigned int i;

for(;delay>;;;0;delay--) { for(i=0;i<124;i ) { printf( ); } } }

/_显示设计者信息_/ void designby { printf(┏━━━━━━━━━━━━━━━━━━━━┓ ); printf(┃ 页面置换算法 ┃ ); printf(┃ 12级1班 ┃ );

o);

printf(┃ 姓名：张海洋，李奔 ┃ ); printf(┣━━━━━━━━━━━━━━━━━━━━┫ ); }

void print(unsigned int t) { int i，j，k，l; int flag; for(k=0;k<=(psize-1)/20;k ) { for(i=20_k;(i<20_(k 1));i ) 20==0)||(((i 1))(i==psize-1))) else= d= j=;j;=j) printf( |%d|，temp[i][j]); else printf( | |); } for(i=msize 20_k;(i<20_(k 1));i ) {= for(flag=，l=0;l<= p=>;;;

printf(置换次数：%d ，t); printf(访问命中率：%d%% ，(psize-(t msize))_100/psize); printf(---------------------------------------- ); }

/_计算过程延迟_/ void compute { int i; printf(正在进行相关计算，请稍候); for(i=1;i<20;i ) { mdelay(15); if(i%4==0) printf( ); else printf(θ); } for(i=0;i <30;printf()); for(i=0;i <30;printf( )); for(i=0;i <30;printf()); }

/_先进先出页面置换算法_/ void fifo {

int memery[10]={0};

int time[10]={0}; /_记录进入物理块的时间_/ int i，j，k，m;

int ma_=0; /_记录换出页_/ int count=0; /_记录置换次数_/ /_前msize个数直接放入_/ for(i=0;i<= p=>;;;

memery[i]=page[i]; time[i]=i;

for(j=0;j<= p=>;;;

for(i=msize;i<= p=>;;;

if(memery[j]！=page[i]) k ;

}

if(k==msize) /_如果不在物理块中_/ {

count ; /_计算换出页_/

ma_=time[0]

time[ma_]=i; /_记录该页进入物理块的时间_/ for(j=0;j<= p=>;;;

/_最近最久未使用置换算法_/ void lru {

int flag[10]={0}; /_记录页面的访问时间_/ int i，j，k，m;

memery[i]=page[i]; flag[i]=i;

if(memery[j]！=page[i]) k ; else flag[j]=i; /_刷新该页的访问时间_/ }

ma_=flag[0]

flag[ma_]=i; /_记录该页的访问时间_/ for(j=0;j<= p=>;;;

/_最佳置换算法_/ void opt {

int ne_t[10]={0}; /_记录下一次访问时间_/ int i，j，k，l，m;

int ma_; /_记录换出页_/

int count=0; /_记录置换次数_/ /_前msize个数直接放入_/ for(i=0;i<= p=>;;;

memery[i]=page[i]; for(j=0;j<= p=>;;;

/_判断新页面号是否在物理块中_/ for(j=0，k=0;j<= p=>;;;

if(memery[j]！=page[i]) k ; }

if(k==msize) /_如果不在物理块中_/ { count ; /_得到物理快中各页下一次访问时间_/ for(m=0;m=ne_t？0:1; for(m=2;mne_t[ma_]) ma_=m; /_下一次访问时间都为psize，则置换物理块中第一个 _/ memery[ma_]=page[i]; for(j=0;j<= p=>;;;

四、调试及实验结果

第一组数据：

1.运行结果

2. 按任意键进行初始化：

3. 载入数据：

4. 进入置换算法选择界面：

5.运算中延迟操作：

6.三种算法演示结果

7.退出算法

第二组数据：

2．按任意键进行初始化：

3.载入数据：

4.进入置换算法选择界面：

6. 三种算法演示结果

五、个人体会

由于时间有限，本次设计完成的并不是很完美，下面从以下几点来说明本次课程设计的个人体会：

1.本次课程设计中做的比较好的地方：

做的好的地方就是在于对题目意思的正确理解，以及在此基础上的模型设计。最开始一看题目的时候感觉很迷茫，有点不知道如何着手，等静下心来仔细分析了程序，明确了目标，明确了思路，才对程序有了一个较为完整的实现。

2.做得不太好的地方，以及以后如何改正：

做得不太好的地方就是不能把自己所学的c知识和本次课程设计的相关知识很好的结合起来，以至于没有很好的表达出本次课程设计的细节。在以后的过程中，我会运用本次课程设计中所学的知识，以及思考问题的方式和方法，争取能够发扬优点，尽量克服不细心，不严谨等缺点。

3.从本次设计中得到的收获：

通过本次课程设计，我学会了综合运用所学相关知识的能力，动手能力以及独立思考问题的能力。下面具体的收一个边学程序是遇到的困难，首先就是如何把想法变为做法的问题，最开始一拿到题目，我就觉得无从下手，因为我的阅历，不知道如何把这样一个问题变成程序，变成能够让人一目了然的东西，于是，我就先写下了p，v操作的实现过程，因为这个对我来说简单一些，然后，在此基础之上，就好办了，结果最后用了2个函数就解决问题了，所以，我觉得有时候思考问题不要太死脑筋，换一个角度的话，也许会更好，说不定就能达到事半功倍的效果。