操作系统设计报告

课程设计 报告

课程名：操作系统

专业 计算机科学与技术

学生姓名 施利华 班学

级 号

M计算机101 1051401103 李先锋 2013年1月8日

指导教师 完成日期

博雅学院

“操作系统”课程设计报告

——页面置换算法的模拟实现

1. 课程设计的目的

(1)熟悉FIFO和LRU算法 (2)比较两种算法的性能优劣

(3) 编写页面置换算法，实现计算机中页面置换的模拟

(4) 通过算法模拟的实现，理解几种常用的页面置换算法的执行过程

2．设计内容

2.1 概述

在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页 为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。

常用的算法有先进先出置换算法（FIFO）, 最近最久未使用置换算法（LRU）。该设计是在VC++6.0环境下分别用LRU和FIFO来实现页面置换算法的模拟程序，并测试。

2.2 设计原理

FIFO基本思想：

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

LRU基本思想：

是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。 2.3 详细设计及编码 2.3.1 FIFO（先进先出）

- 1 -

设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当 前的页面。

开始

Y 当前Y p[]中第i个元i++ 素是否已在内存

N

Page[]是否有空

Y N 把p[i]的内容直接把page[]中最先装入的页 装入最上面一个面置换出去.i++ 空内存块，i++

输出当前内存块状态

结束

图2-3-1 FIFO算法流程图

页面走向存入数组p[]中，内存块用page[]表示初始化为0 2.3.2 LRU（最近最久未使用）

设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。

算法流程图：

- 2 -

开始 页面走向存入数组p[]中，内 存块用page[]表示初始化为0 Y 当前p[]中第i个元i++ 素是否已在内存 N Page[]是否有空 Y N 把page[]中最近最久未使把p[i]的内容直接 用的页面置换出去.i++ 装入最上面一个 空内存块，i++ 输出当前内存块状态 结束 图2-3-2 LRU算法流程图

2.4代码源程序： 源程序清单 #include #include #include /*全局变量*/

- 3 -

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 print(unsigned int t); void designBy(); void download();

void mDelay(unsigned int Delay); /*主函数*/ void main() {

int i,k,code;

system(\"color 0A\"); designBy();

printf(\"┃请按任意键进行初始化操作... ┃\\n\"); printf(\"┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\\n\"); printf(\" >>>\"); getch();

system(\"cls\");

system(\"color 0B\");

printf(\"请输入物理块的个数(M<=10)：\"); scanf(\"%d\

printf(\"请输入页面号引用串的个数(P<=100)：\"); scanf(\"%d\

puts(\"请依次输入页面号引用串(连续输入，无需隔开)：\"); for(i=0;iscanf(\"%1d\ download(); system(\"cls\");

system(\"color 0E\"); do{

puts(\"输入的页面号引用串为：\"); for(k=0;k<=(pSIZE-1)/20;k++) {

for(i=20*k;(i- 4 -

if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(\"%d\\n\ else

printf(\"%d \ } }

printf(\"* * * * * * * * * * * * * * * * * * * * * * *\\n\"); printf(\"* 请选择页面置换算法：\\\ *\\n\");

printf(\"* ----------------------------------------- *\\n\"); printf(\"* 1.先进先出(FIFO) 2.最近最久未使用(LRU) *\\n\"); printf(\"* 3.退出 * * * * * * * * *\\n\"); printf(\"* * * * * * * * * * * * * * * * * * * * * * *\\n\"); printf(\"请选择操作：[ ]\\b\\b\"); scanf(\"%d\ switch(code) {

case 1:

FIFO(); break; case 2: LRU(); break; case 3:

system(\"cls\");

system(\"color 0A\");

designBy(); /*显示设计者信息后退出*/

printf(\"┃谢谢使用页面置换算法演示器! ┃\\n\");

printf(\"┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\\n\");

exit(0); default:

printf(\"输入错误，请重新输入：\"); }

printf(\"按任意键重新选择置换算法：>>>>>\"); getch();

system(\"cls\"); }while (code!=4); getch(); }

/*载入数据*/

- 5 -

void download() {

int i;

system(\"color 0D\");

printf(\"╔════════════╗\\n\"); printf(\"║正在载入数据，请稍候 !!!║\\n\"); printf(\"╚════════════╝\\n\"); printf(\"Loading...\\n\");

printf(\" O\"); for(i=0;i<51;i++) printf(\"\\b\"); for(i=0;i<50;i++) {

mDelay((pSIZE+mSIZE)/2); printf(\">\"); }

printf(\"\\nFinish.\\n载入成功，按任意键进入置换算法选择界面：>>>\"); getch(); }

/*设置延迟*/

void mDelay(unsigned int Delay) {

unsigned int i;

for(;Delay>0;Delay--) {

for(i=0;i<124;i++) {

printf(\" \\b\"); } } }

/*显示设计者信息*/ void designBy() {

printf(\"┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\"); printf(\"┃ 实验四：页面置换算法 ┃\\n\"); printf(\"┃ M计算机101 ┃\\n\");

printf(\"┃ 姓名：施利华 ┃\\n\"); printf(\"┣━━━━━━━━━━━━━━━━━━━━━━━━━┫\\n\"); }

- 6 -

void print(unsigned int t) {

int i,j,k,l; int flag;

for(k=0;k<=(pSIZE-1)/20;k++) {

for(i=20*k;(iif(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(\"%d\\n\ else

printf(\"%d \ }

for(j=0;jfor(i=20*k;(iif(i>=j)

printf(\" |%d|\ else

printf(\" | |\"); }

for(i=mSIZE+20*k;(ifor(flag=0,l=0;lif(temp[i][l]==temp[i-1][l]) flag++;

if(flag==mSIZE)/*页面在物理块中*/ printf(\" \"); else

printf(\" |%d|\ }

/*每行显示20个*/ if(i%20==0) continue; printf(\"\\n\"); } }

printf(\"----------------------------------------\\n\"); printf(\"缺页次数：%d\\\

printf(\"缺页率：%d/%d\\n\

- 7 -

printf(\"置换次数：%d\\\

printf(\"访问命中率：%d%%\\n\ printf(\"----------------------------------------\\n\"); }

/*计算过程延迟*/ void compute() {

int i;

printf(\"正在进行相关计算，请稍候\"); for(i=1;i<20;i++) {

mDelay(15); if(i%4==0)

printf(\"\\b\\b\\b\\b\\b\\b \\b\\b\\b\\b\\b\\b\"); else

printf(\"Θ\"); }

for(i=0;i++<30;printf(\"\\b\")); for(i=0;i++<30;printf(\" \")); for(i=0;i++<30;printf(\"\\b\")); }

/*先进先出页面置换算法*/ void FIFO() {

int memery[10]={0};

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

int max=0; /*记录换出页*/

int count=0; /*记录置换次数*/ /*前mSIZE个数直接放入*/ for(i=0;imemery[i]=page[i]; time[i]=i;

for(j=0;jfor(i=mSIZE;i/*判断新页面号是否在物理块中*/ for(j=0,k=0;j- 8 -

{

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

if(k==mSIZE) /*如果不在物理块中*/ {

count++;

/*计算换出页*/

max=time[0]if(time[m]memery[max]=page[i];

time[max]=i; /*记录该页进入物理块的时间*/ for(j=0;jfor(j=0;jcompute(); print(count); }

/*最近最久未使用置换算法*/ void LRU() {

int memery[10]={0};

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

int max=0; /*记录换出页*/

int count=0; /*记录置换次数*/ /*前mSIZE个数直接放入*/ for(i=0;imemery[i]=page[i]; flag[i]=i;

for(j=0;j- 9 -

}

for(i=mSIZE;i/*判断新页面号是否在物理块中*/ for(j=0,k=0;jif(memery[j]!=page[i]) k++; else

flag[j]=i; /*刷新该页的访问时间*/ }

if(k==mSIZE) /*如果不在物理块中*/ {

count++;

/*计算换出页*/

max=flag[0]if(flag[m]memery[max]=page[i];

flag[max]=i; /*记录该页的访问时间*/ for(j=0;jfor(j=0;j}

compute(); print(count); }

- 10 -

3、 结果及分析

图3-1编者信息显示界面

图3-2 输入物理块个数

- 11 -

3-3输入页面号引用串个数

3-4输入页面号引用串

- 12 -

3-5 进入置换算法载入界面

3-6 进入选择算法界面

- 13 -

3-7 FIFO算法运行结果

3-8 LRU算法运行结果

- 14 -

3-9运行结束界面

4、 设计小结

通过这次的程序设计，让我对C语言有了更深一步的了解和认识，编程能力也有了提高，我认到学好计算机要重视实践操作，只有真正动手了才知道自己还有那些不足之处。通过这次实验我对先进先出FIFO，最近最久未使用LRU页面置换算法的实现方法。有了更多的了解。在编程过程中我也通过查阅书籍和复习以前的课本，对C++编程语言进行了复习。 通过这个实验我也体会到思路的重要性，一个程序如果一开始计划的好，结构设计完善，才可能顺利进行。这次实验模拟出了优先权调度算法，使我更加了解这一算法的调度过程。以前仅限于知道这一知识点，现在居然能用程序来实现这个过程。我相信这将是一个很好的学习方法。

5、参考文献

1. 严蔚敏, 吴伟民. 数据结构. 清华大学出版社, 2005.11 2. 谭浩强. C语言程序设计. 清华大学出版社, 2005.11

- 15 -