计算机操作系统课程设计

1、计算机操作系统课程设计报告题目:模拟设计页面调度编程专业：计算机科学与技术班级：12级计算机二班姓名:朱绍锋学 号：12838076赵飞12838064王伟12838039王焱焱12838045刘继运12838061谭兵12838053指导老师：郭伟光二O五年六月安徽农业大学经济技术学院计算机操作系统目录一、 实验目的1二、基本知识介绍12.1、 分页12.2、页面调入策略12.3、从何调入页面22.4、页面调入过程22.5、页面置换算法 3三、页面置换算法框架及 LRU算法实现 7四、 实验结果11I安徽农业大学经济技术学院计算机操作系统、实验目的1）了解内存分页管理策略；2）掌握调页策略；

2、3）掌握一般常用的页面置换算法；4）选取页面置换算法中的典型算法，模拟实现。二、基本知识介绍2.1、分页分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页 面或页。2.2、页面调入策略1）、何时调入页面如果进程的许多页是存放在外存的一个连续 区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更 高效一些。但如果调入的一批页面中的大多数都未被访问，则又是 低效的。可采用一种以预测为基础的预调页策略，将那些预计在不 久之后便会被访问的页面，预先调入内存。如果预测较准确，那么， 这种策略显然是很有吸引力的。 但目前预调页的成功率仅为50%且 这种策略主要用于进程的首次调入时，由程

3、序员指出应该先调入哪 些页。2）、请求调页策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问 的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中， 大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系 统开销，增加了磁盘I/O的启用频率。2.3、从何处调入页面在请求分页系统中的外存分为两部分：用于存放文件的文件区和 用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式， 而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统

4、应从何处将缺页调入内存，可 分成如下三种情况：1）、系统拥有足够的对换区空间，这时可以全部从对换区调入 所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程 有关的文件，从文件区拷贝到对换区。2）、系统缺少足够的对换区空间，这时凡是不会被修改的文件， 都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不 必再将它们换出时，以后需要时，再从对换区调入。3）、UNIX方式。由于与进程有关的文件都放在文件区，故凡是 未运行过的页面，都从文件区调入。而对于曾经运行过但又被换出的 页面，由于被放在对换区，因此在下次时，应从对换区调入。由于 UNIX系统允许页面共享，因此，某进程所请求的页

5、面有可能已被其它进程调入内存，此时也就无须再从对换区调入。2.4、页面调入过程每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页 中断处理程序。该程序通过查找页表，得到该页在外在原物理 块后, 如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存， 然后修改页表。如果内存已满，则须先按照某种置换算法从内存中 选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘； 但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调 入内存，并修改页表中的相应表项，置其存在位“ 1”，并将此页表 项写入快表中。在缺页调入内存后，

6、利用修改后的页表，去形成所 要访问数据的物理地址，再去访问内存数据。整个页面的调入过程 对用户是透明的。2.5、页面置换算法在进程运行过程中，若其所要访问的页面不在内存而需把它们调 入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统 必须从内存中调出一页程序或数据， 送磁盘的对换区中。但应将哪个 页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法 称为页面置换算法(Page_Replacement Algorithms)。一个好的页面 置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后 不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调 出。常见置换算法

7、有：1)、最佳置换算法(Optimal)它是由Belady于1966年提出的一种理论上的算法。其所选择的 被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被 访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但 由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以 利用此算法来评价其它算法。页面装入物理块中选择物理块中距离该页表之后最远的或不在出现的页表与之置换完成2)、先进先出(FIFO)页面置换算法这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法

8、实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并3）、LRU置换算法FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情 况。最近最久未使用（LRU置换算法，是根据页面调入内存后的使 用情况进行决策的。由于无法预测各页面将来的使用情况， 只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。 该算法赋予每个页面一个访问 字段，用来记录一个页面自上次被访问以来所经历的时间t,当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用 的页面予以淘汰。LRU置

9、换算法虽然是一种比较好的算法，但要求系统有较多的支 持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进 程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有寄存器或者堆栈的支持。下一页面是否在物理快中物理快是否装 满开始页面装入物理块中N三、页面置换算法框架及 LRU算法实现#i nclude <stdafx.h> #in clude<stdio.h>#in clude<c oni o.h> #defi ne M 3#defi ne N 20#define Mypri ntf-+-+-+-+-|n") /*显示格式 */typed

10、ef struct pageint num; /*记录页面号*/int time; /*记录调入内存时间*/Page; /*页面逻辑结构，结构为方便算法实现设计*/Page bM; /*内存单元数*/in t cMN; /*暂保存内存当前的状态：缓冲区*/int queue100; /* 记录调入队列*/int K; /*调入队列计数变量*/*初始化内存单元、缓冲区*/void In it(Page *b,i nt cMN)int i,j;for(i=0;i<N;i+)bi. num=-1;bi.time=N-i-1;for(i=0;i<M;i+)for(j=0;j<N;j+

11、)cij=-1;/*取得在内存中停留最久的页面，默认状态下为最早调入的页面*/int GetMax(Page *b)int i;int max=-1;int tag=0;for(i=0;i<M;i+)if(bi.time>max)max=bi.time;tag=i;return tag;/*判断页面是否已在内存中*/int Equati on (i nt fold,Page *b)int i;for(i=0;i<M;i+)if (fold=bi. num)return i;return -1;/*LRU核心部分*/void Lru(i nt fold,Page *b)int

12、i;int val;val=Equatio n( fold,b);if (val>=0)bval.time=0; for(i=0;i<M;i+)if (i!=val)bi.time+;elsequeue+K=fold;/* 记录调入页面 */ val=GetMax(b);bval. num=fold; bval.time=0;for(i=0;i<M;i+)if (i!=val)bi.time+;/*主程序*/int mai n()int aN=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1; int i,j;doK=-1;In it(b, c)

13、;for(i=0;i<N;i+)Lru(ai,b);cOi=ai;/*记录当前的内存单元中的页面*/for(j=0;j<M;j+)cji=bj. num;/*结果输出*/prin tf(" 内存状态为：n");Mypri ntf;for(j=0;j<N;j+)prin tf("|%2d ",aj);prin tf("|n");Mypri ntf;for(i=0;i<M;i+)for(j=0;j<N;j+)if(cij=-1)prin tf("|%2c ",32);elseprin tf("|%2d ",cij);prin tf("|n");Mypri ntf;printf("n调入队列为:");for(i=0;i<K+1;i+)prin tf("%3d",queuei);prin tf("n缺页次数为：%6dn缺页率：%16.6f",K+1,(float)(K+1)/N);prin tf("nAre you continuin g!t ?"); while(getchar()='y');-13 -四