操作系统课程设计报告页面置换算法模拟程序设计

1、 操作系统课程设计报告题 目：页面置换算法模拟程序设计 专 业：软件工程 院 系：信息管理学院 年 级：大三软件Q1141 学 号： 姓 名：李艳平 指导教师：李红艳 职 称：副教授 湖北经济学院教务处 制目录第一部分 概述第二部分 设计的基本概念和原理第三部分 总体设计3.1算法流程图3.2算法的简要实现方法3.2.1 OPT页面置换算法3.2.2 FIFO页面置换算法3.2.3 LRU页面置换算法3.2.4 LFU页面置换算法第四部分 详细设计4.1 main函数4.2 OPT函数4.2 FIFO函数4.3 LRU函数4.5 LFU函数4.6辅助函数4.6.1 Designer函数4.6.

2、2 mDelay函数4.6.3 Download函数4.6.4 Compute函数4.6.5 showTable函数第五部分 实现源代码第六部分 简要的使用说明及主要运行界面第七部分 总结第八部分 参考文献第一部分 概述设计任务：页面置换算法是虚拟存储管理实现的关键，通过本次课程设计理解内存页面调度的机制，在模拟实现OPT、FIFO、LRU和LFU几种经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。第二部分 设计的基本概念和原理(1)页面淘汰机制页面淘汰又称为页面置换。若请求调页程序要调进一个页面，而此时该作业所分得的主存块已全部用完，则必须淘汰该作业已在

3、主存中的一个页。这时，就产生了在诸页面中淘汰哪个页面的问题，这就是淘汰算法（或称为置换算法）。置换算法可描述为，当要索取一个页面并送入主存时，必须将该作业已在主存中的某一页面淘汰掉，用来选择淘汰哪一页的规则就叫做置换算法。(2)各种页面置换算法的实现思想OPT算法是当要调入一新页而必须先淘汰一旧业时，所淘汰的那一页应是以后不要再用的或是以后很长时间才会用到的页。FIFO算法的实质是，总是选择在主存中居留时间最长（即最老）的一页淘汰。其理由是最先调入主存的页面，其不再被使用的可能性比最近调入主存的页的可能性大。LRU算法的实质是，当需要置换一页时，选择最长时间未被使用的那一页淘汰。如果某一页被访

4、问了，它很可能马上还要被访问；相反，如果它很长时间未曾用过，看起来在最近的未来是不大需要的。LFU即最不经常使用页置换算法，要求在页置换时置换在一定时期内引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。本次设计取整个页面访问时期为计算周期，实际问题中应根据页面数量多少来确定周期。第三部分 总体设计3.1算法流程图输入页面访问序列取访问的页号查页表是否缺页否是置缺页标志flag为*按算法不同淘汰一页面调入所访问的页面3.2算法的简要实现方法选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：最佳置换算法（OPT）：是用一维数组pagePSIZE存储页面号序列，memery

5、MSIZE是存储装入物理块中的页面，用pflagPSIZE数组标记缺页中断处。数组nextMSIZE记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面，然后初始化nextMSIZE，便于下次使用。【特别声明】若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。先进先出置换算法（FIFO）：是用一维数组pagePSIZE存储页面号序列，memeryMSIZE是存储装入物理块中的页面，用pflagPSIZE数组标记缺页中断处。采用队列的思想，总是把最先进入物理块中的页面放在第一个位置，当发生缺页时，就从队头删除一页，而

6、从队尾加入缺页。最久未使用置换算法（LRU）：是用一维数组pagePSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页面，用pflagPSIZE数组标记缺页中断处。总是把最长时间内未被使用的页放在最后一块，当发生缺页时，就删掉最后一页，将当前所缺页面放入第一块。最不经常使用淘汰算法（LFU）：是用一维数组pagePSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页面，用pflagPSIZE数组标记缺页中断处。用useMSIZE数组记录当前各页已使用次数，其中use0中存放使用次数最少的页的次数，当发生缺页时，就在已放入物理块的页中查找当前使用次数最少的页，将

7、之删掉，并引入当前缺页页面。第四部分 详细设计main函数：void main()int i, k, code;int mSize, pSize, pagePSIZE;system(color 0A);Designer();printf(请按任意键继续. n);printf(n);printf( );getchar();system(cls); /DOS命令，清除屏幕上的所有文字system(color 0B); /改变控制台的前景和背景色printf(请输入物理块的个数mSize = 10：);scanf(%d, &mSize);printf(请输入页面数pSize = 50：);scanf

8、(%d, &pSize);printf(请输入页面序列110之间：n);for (i = 0; i pSize; i +)scanf(%d, &pagei);Download(pSize, mSize);system(cls);system(color 0E);doprintf(即将进入物理块的页面序列为:n);for (i = 0; i );getchar();system(pause); /冻结屏幕system(cls); while (code != 5);getchar ();OPT函数：void OPT(int page, int pSize, int mSize)int i, j,

9、 k;int count = 0; /计数器int memeryMSIZE = 0; /存储装入物理块中的页面int nextMSIZE = 0; /记录物理块中对应页面的最后访问时间sum = 0;for (i = 0; i pSize; i +)j = 0;while (j mSize) & (pagei != memeryj) /查页表，看是否缺页j +;if (j = mSize) flag = *; /缺页，则置标志flag为*sum += 1; /记录缺页次数if (sum = mSize) /如果物理块中有空余，则将当前页面直接放入for (j = 0; j mSize; j +

10、)if (memeryj = 0)memeryj = pagei;break;else /物理块已满的情况下for (j = i + 1; j pSize; j +) /查找以后不再使用或在最长时间以后才会用到的页for (k = 0; k mSize; k +)if (pagej = memeryk)nextk += 1; /记录将被使用的次数，可以不用累加count +; /记录物理块中以后将即被使用的页面个数break;if (count = mSize - 1) break; /如果已有mSize-1个页面即将被使用，则剩下最后一个页面一定是最长时间后才会用到的页if (count =

11、 0)memery0 = pagei;elsecount = 0;for (k = 0; k mSize; k +)if (nextk = 0) /总是置换出第一个可以换出的页memeryk = pagei;nextk = 0; /初始化next数组else flag = ;pflagi = flag; /记录当前页的缺页情况for (k = 0; k mSize; k +) /记录每一次的置换情况tableki = memeryk;Compute();showTable(page, pSize, mSize);FIFO函数：void FIFO(int page, int pSize, int

12、 mSize)int i, j;int memeryMSIZE = 0; /存储装入物理块中的页面sum = 0;for(i = 0; i pSize; i+) /查页表，看是否缺页 j = 0;while (j 0; j -) /淘汰最先调入的页面，并调入当前页面memeryj = memeryj-1;memery0 = pagei;else flag = ;pflagi = flag;for (j = 0; j mSize; j+) tableji = memeryj;Compute();showTable(page, pSize, mSize);LRU函数：void LRU(int pa

13、ge, int pSize, int mSize)int i, j, k;int memeryMSIZE = 0; /存储装入物理块中的页面sum = 0;for (i = 0; i pSize; i +)j = 0;while (j 0) /总是把最长时间内未被使用的页放在最后一页memeryk = memeryk-1;k -;memery0 = pagei; /调入当前页面for (k = 0; k mSize; k +) /记录每一次的置换情况tableki = memeryk;Compute();showTable(page, pSize, mSize);LFU函数：void LFU(

14、int page, int pSize, int mSize)int i, j, replace; /replace标记使用次数最少的页int useMSIZE = 0; /记录当前各页已使用次数, 其中use0中存放使用次数最少的页的次数int memeryMSIZE = 0; /存储装入物理块中的页面sum = 0;for (i = 0; i pSize; i +)usepagei += 1; /下标即为页号j = 0;while (j mSize) & (pagei != memeryj) /查页表，看是否缺页j +;if (j = mSize) flag = *; /缺页，则置标志fl

15、ag为*sum += 1; if (sum = mSize) /如果物理块中有空余，则将当前页面直接放入for (j = 0; j mSize; j +)if (memeryj = 0)memeryj = pagei;break;else /物理块已满的情况下use0 = 100;for (j = 0; j mSize; j +) /在已放入物理块的页中查找当前使用次数最少的页if (usememeryj use0)use0 = usememeryj;replace = j; /标记页号memeryreplace = pagei;else flag = ;pflagi = flag; /记录当

16、前页的缺页情况for (j = 0; j mSize; j +) /记录每一次的置换情况tableji = memeryj;Compute();showTable(page, pSize, mSize);辅助函数Designer函数：void Designer() printf(n);printf( 课题：页面置换算法 n);printf( 学号：11150038 n);printf( 姓名：李艳平 n);printf( n);printf(n);mDelay函数：void mDelay(unsigned int Delay) unsigned int i;while (Delay 0)for

17、 (i = 0; i 125; i+)printf( b);Delay-;Download函数：void Download(int pSize, int mSize)int i;system(color 0D);printf(n);printf(正在载入数据，请稍后. n);printf(n);printf(Loading.n);printf( 0n); for (i = 0; i 51; i+)printf(b);for (i = 0; i );printf(nFinish.n载入成功，按任意键进入置换算法选择界面：);getchar();Compute函数：void Compute()in

18、t i;printf(正在进行相关计算，请稍候.n);for(i=1;i);for(i=0;i+30;printf(b);for(i=0;i+30;printf( );for(i=0;i+30;printf(b);showTable函数：void showTable(int page, int pSize, int mSize) int i, j;/*printf(即将进入物理块的页面序列为:n);for (i = 0; i pSize; i +)printf(%3d, pagei);printf(n输出置换过程，“*”标记缺页中断处n);*/for (i = 0; i mSize; i +)

19、for (j = 0; j pSize; j +)printf(%3d, tableij);printf(n);for (i = 0; i pSize; i +)printf(%3c, pflagi); printf(nn);printf(总的缺页次数为：%dn, sum);printf(缺页中断率为：%.2lf%n, 100.0 * sum / pSize);printf( n);第五部分 实现源代码#include #include /*宏定义*/#define MSIZE 10 /最大物理块数#define PSIZE 50 /最大页面数/*全局变量*/char flag, pflagP

20、SIZE; /缺页标志 int tableMSIZEPSIZE; /存放置换记录int sum = 0; /记录每个算法的缺页次数/*置换算法函数*/void OPT(int page, int pSize, int mSize); /最佳置换算法void FIFO(int page, int pSize, int mSize); /先进先出置换算法void LRU(int page, int pSize, int mSize); /最久未使用置换算法void LFU(int page, int pSize, int mSize); /最不经常使用淘汰算法(当前使用次数最少)/*辅助函数*/void Designer(); /显示设计者信息void m