操作系统电梯调度LRU页面反馈

1、操作系统原理课程设计报告姓 名： 付豪 班 级： 网络1311 学 号： 131003600139 指导老师： 宁建红 2016 年 1月目 录1 背景知识11.1电梯调度算法11.2页故障率反馈模型12 设计内容22.1电梯调度算法22.1.1基本原理分析22.1.2数据结构22.1.3程序流程图32.1.4函数介绍42.1.5源代码42.1.6结果122.2页故障率反馈模型142.2.1基本原理分析142.2.2程序流程图152.2.3函数介绍162.2.4源代码162.2.5结果183 结论20参考文献211 背景知识1.1电梯调度算法磁盘调度在多道程序设计的计算机系统中，各个进程可能会

2、不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有以下四种：先来先服务算法（FCFS），最短寻道时间优先算法（SSTF），电梯调度算法（SCAN），循环扫描算法（CSCAN） SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。由于磁头移动规律与电梯运行相似，故又称为电梯调度算法。SCAN算法对最近扫描过的区域不公平，因此，它在访问局部性方面不如FCFS算法和SSTF算法好。 算法思想：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向

3、移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。1.2页故障率反馈模型在虚拟页式存储管理系统中，进程运行之前会把一部分页面装入内存，而另一部分页面装入外存中。在进程运行过程中，如果所访问的页面在内存，则与无虚拟页存储时的情形相同；所访问的页面不在内存，则发生缺页故障。建立工作集页面模型，利用随机函数动态生成进程访问页面的序列号，实现页面淘汰算法，实现页故障率反馈模型。在虚拟页式存储管理系统中，进程运行之前会把一部分页面装入内存，而另一部分页面装入外存。在进程运行过程中，如果所访问的页面在内存，则

4、与无虚拟页式存储时的情形相同；如果所访问的页面不在内存，则发生缺页故障，进入操作系统，有操作系统进行页面的动态调度，进行页面的置换。2 设计内容2.1电梯调度算法2.1.1基本原理分析电梯调度算法的调度策略是与移动臂的移动方向和移动臂的当前位子有关的，所以每次启动磁盘时都应登记移动臂方向和当前位子。电梯调度算法是一种简单而实用的驱动调度方法，这种调度策略总是优先选择与当前柱面号相同的访问请求，从这些请求中再选择一个能使旋转距离最短的等待访问者。如果没有与当前柱面号相同的访问请求，则根据移臂方向来选择，每次总是沿臂移动方向选择一个与当前柱面号最近的访问请求，若沿这个方向没有访问请求时，就改变臂的

5、移动方向。这种调度策略能使移动臂的移动频率极小，从而提高系统效率。用电梯调度算法实现驱动. 模拟电梯调度算法，对磁盘进行移臂和旋转调度。磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。 由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时，占有处理器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的输入输出请求。为了模

6、拟这种情况，在本实验中设置了一个“接收请求”进程。“驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断处理和处理器调度选择的过程。2.1.2数据结构typedef struct PCB char procM;/进程名 int cylinder_num;/柱面号 int track_num;/磁道号 int phy_num;/物理记录号 struct PCB *next;/ 进程指向下一节点PCB; 2.1.3程序流程图开始查”请求I/O表”否是有等待访问者?有与当前柱面号相同的访问者?否是返

7、回选择能使旋转距离最短的访问者当前移臂方向是向里移?否是有比当前柱面号大的访问请求?有比当前柱面号小的访问请求?否是是置当前移臂方向为向里移置当前移臂方向为向外移从小于当前柱面号的访问请求中选择一个最大者从大于当前柱面号的访问请求中选择一个最小者添加当前位置：柱面号；物理记录号启动磁盘，被选中者退出“请求I/O表”图2.1.3-1 电梯调度模拟算法框图返回2.1.4函数介绍 void init () /初始化进程并分配空间 void current_process(PCB *Q) /模拟进程记录void insert(PCB *p) /插入函数void out_info() /输出进程的信息v

8、oid output()/显示当前I/O表void create_PCB()/初始化I/O请求表void Receive_requests()/接受请求模块void lift()/电梯调度算法void main()/主函数2.1.5源代码#include"stdio.h" #include"stdlib.h" #include"string.h" #define M 20 typedef struct PCB char procM;/进程名 int cylinder_num;/柱面号 int track_num;/磁道号 int ph

9、y_num;/物理记录号 struct PCB *next; PCB; PCB *head=NULL; int direction ;/定义方向，1为up，-1为down PCB *h=NULL; /存放当前运行中的进程的信息void init ()/初始化进程并分配空间 h=(PCB *)malloc(sizeof(PCB); direction=1; strcpy(h->proc,"p"); h->cylinder_num = 0; h->track_num= 0; h->phy_num= 0; void current_process(PCB

10、*Q) /模拟进程记录 strcpy(h->proc,Q->proc); h->cylinder_num = Q->cylinder_num; h->track_num=Q->track_num; h->phy_num=Q->phy_num; void insert(PCB *p) /插入函数 PCB *q; q=head; if(head=NULL) head=p; else for(q=head;q->next!=NULL;q=q->next); p->next=q->next; q->next=p; void

11、out_info() /输出进程的信息 printf(" 进程名 柱面号 磁道号 物理记录号 方向n"); printf(" %s t%d t%d t%d ",h->proc,h->cylinder_num,h->track_num,h->phy_num); void output() /显示当前I/O表 PCB *p; p=head; printf("进程名 柱面号 磁道号 物理记录号n"); if(p=NULL) printf("-进程表为空,接收请求或按'n'退出-n"

12、); else while(p!=NULL) printf("%s t%d t%d t%dn",p->proc,p->cylinder_num,p->track_num,p->phy_num); p=p->next; /初始化I/O请求表void create_PCB() PCB *p,*q; q=head; int i,n; printf("n"); printf("请输入I/O进程表中进程等待的个数：n"); printf("n"); scanf("%d",&a

13、mp;n); printf("请依次输入进程的相关信息: （用空格分隔）n"); printf("-n"); printf("进程名，柱面号，磁道号，物理记录号n"); for(i=1;i<=n;i+) p=(PCB *)malloc(sizeof(PCB); scanf("%s",&p->proc); scanf("%d",&p->cylinder_num); scanf("%d",&p->track_num); scanf(

14、"%d",&p->phy_num); p->next=NULL; insert(p); printf("-n"); void Receive_requests() /接受请求模块 PCB *p; int i,n,m; printf("请输入一个值: n"); printf("1.<接收请求> n"); printf("0.<继续执行> n"); scanf("%d",&i); if(i=1) printf("正在运

15、行的进程为：n"); printf("n"); printf("接受请求前的等待进程表为n"); output(); printf("请输入接受等待进程数量n"); scanf("%d",&n); printf("请依次输入进程的信息n"); printf("进程名，柱面号，磁道号，物理记录号n"); for(m=1;m<=n;m+) p=(PCB *)malloc(sizeof(PCB); scanf("%s",&p-&g

16、t;proc); scanf("%d",&p->cylinder_num); scanf("%d",&p->track_num); scanf("%d",&p->phy_num); p->next=NULL; insert(p); printf("接受请求后的等待进程表为：n"); printf("n"); output(); else printf("没有接受进程，继续往下运行程序n"); void lift() /电梯调度算

17、法 int min,cha,max; PCB *p,*q,*B;/p为指要删除的节点，q为查找的节点，B指向要删除节点的前一个节点 q=head; if(q!=NULL) while(q!=NULL)&&(q->cylinder_num!=h->cylinder_num)/找到第一个相同的柱面号 q=q->next; if(q=NULL)/没有柱面号相同的等待进程 q=head; if(direction=1)/当前移臂方向up while(q!=NULL)&&(q->cylinder_num <h->cylinder_num

18、)/找到比当前柱面号大的等待进程 q=q->next; if(q=NULL)/没有比当前柱面号大的等待进程 direction=-1;/置当前移臂方向为外移 q=head;/从小于当前柱面号的访问中选择一个最大的,p指向 p=q; max=q->cylinder_num; q=q->next; while(q!=NULL) if(max<q->cylinder_num) max=q->cylinder_num; p=q;/p指向最大的节点 q=q->next; else/有大于当前柱面号的等待进程 min=q->cylinder_num; p=q

19、; q=q->next; while(q!=NULL)/大于当前柱面号并且小于指定最小的节点时 if(h->cylinder_num<q->cylinder_num)&&(q->cylinder_num<p->cylinder_num) min=q->cylinder_num; p=q;/p指向最小的节点 q=q->next; else/当前移臂方向为里移 while(q!=NULL)&&(q->cylinder_num >h->cylinder_num) q=q->next; if(

20、q=NULL)/没有比当前柱面号小的请求 direction=1; q=head;/从大于当前柱面号的访问中选择一个最小的,p指向 p=q; min=q->cylinder_num; q=q->next; while(q!=NULL) if(min>q->cylinder_num) min=q->cylinder_num; p=q;/p指向最小的节点 q=q->next; else/有比当前柱面号小的请求进程 max=q->cylinder_num; p=q; q=q->next; while(q!=NULL)/从小于当前柱面号访问进程中选择一个

21、最大的，用p指向 if(p->cylinder_num<q->cylinder_num&&q->cylinder_num<h->cylinder_num) max=q->cylinder_num; p=q;/p指向最大的节点 q=q->next; else/有柱面号相同的等待进程 min=q->phy_num-h->phy_num;/第一个相同柱面号设为最小值 p=q;/指向最小的节点，旋转距离最短的访问者 if(min<0) min=-min; q=q->next; while(q!=NULL) if(q

22、->cylinder_num=h->cylinder_num)/有柱面号相同 cha=q->phy_num-h->phy_num; if(cha<0) cha=-cha; if(min>cha)/有更小的节点，旋转距离最短的访问者 min=cha; p=q;/指向最小的节点 q=q->next; current_process(p);/保留选中的进程 if(direction=1) /启动磁盘 printf("被选中的等待进程为：n"); printf("n"); out_info(); printf("

23、; upn"); printf("n"); if(direction=-1) printf("被选中的等待进程为：n"); printf("n"); out_info(); printf(" downn"); printf("n"); if(p=head) head=p->next; else B=head; while(B->next!=p)/找到要删除进程的前一个节点 B=B->next; B->next=p->next;/被选中者退出I/O请求表 e

24、lse printf("请求进程表为空,接收请求或退出n"); /电梯调度算法结束void main()/主函数 char go='y' /默认值 float number; init(); printf(" -执行驱动调度-n"); printf(" -当前运行进程为-n"); out_info(); printf(" upn"); printf(" -*创建I/O请求进程等待表*-n"); create_PCB(); /创建进程链表 printf("n")

25、; printf("I/O请求进程等待表为：n"); printf("n"); output(); while(go='y'|go!='n') printf("n"); /number=rand()/(RAND_MAX+1.0); printf("输入01之间的数：n"); printf(">0.5 -<电梯调度> n"); printf("<=0.5 -<接受请求> n"); scanf("%f&

26、quot;,&number); while(number>0.5) lift(); printf("调用电梯驱动调度算法后的I/O请求表为：n"); printf("n"); output(); break; if(number<=0.5) Receive_requests();/调用接受请求模块 printf("是否继续？n"); printf("<y:继续>n"); printf("<n:退出>n"); scanf("%s",&

27、amp;go); 2.1.6结果 图2.1.61 图2.1.6-2 图2.1.6-3 图2.1.6-4 图2.1.6-5 图2.1.6-6 2.2页故障率反馈模型2.2.1基本原理分析页故障率反馈模型工作集模型的精确度与窗口尺寸密切相关。如过小，程序的活动页面不能全部装入内存，缺页率就高；如过大，允许同时并发执行进程的个数就会降低。采用工作集模型，操作系统动态纪录各个进程的工作集，并动态地调整分配给各个进程的页架数。在虚拟页式存储管理中，页故障率反馈模型试图将各个进程的缺页率控制在一个合适的范围内。当一个进程缺页率大于指定的故障率上限，而且内存有空闲的页架，就给该进程增加分配的页架数；当一个进

28、程缺页率小于指定的故障率下限，就从该进程所分配的页架中收回一些页架；当页故障率在指定的范围之内，则保持该进程所拥有的页架。最近最少使用页面替换算法LRU最近最少使用页面替换算法淘汰的页面是在最近一段时间内最近未被访问的那一页，它是基于程序局部性原理来考虑的，认为那些刚被使用过的页面可能还要立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。为了能准确地淘汰最近最少使用的页面，必须维护一个特殊队列页面淘汰队列，此队列存放当前在内存中的所有页号，每访问一页时就调整一次，使队列尾总是指向最近访问的页，队列头就是最近最少使用的页，显然，发生缺页异常时总是淘汰队列头所指页面；而执行页面访问后，

29、需要从队列中把此页调整到队列尾。2.2.2程序流程图开始初始化工作集模型调用随机产生的序列NY页面在工作集？查找最先进入页面继续调用下一页面换页NY序列完成修改工作集时间故障反馈，修改工作集大小NY结束输入为q? 图2.2.3-1 页故障率反馈模型框图2.2.3函数介绍void changeArray()/生成初始序列void LRU()/电梯调度，缺页反馈int main()/主函数2.2.4源代码#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define n 20int ymn;int mem

30、page=10;double maxRate=0.8,minRate=0.2;double curRate;int m=3;void changeArray()int i;for(i=0;i<n;i+)ymi=rand()%mempage;printf("进程调用页面序列：");for(i=0;i<n;i+)printf("%d|",ymi);printf("n");void LRU() int conflictCount=0;int i,j,q,memm,tablemn;changeArray();for(i=0;i<n;i+) q=0; while(ymi!=memq)&&(q!=m) q+; if(q=m) conflictCount+; for(j=q;j>0;j-) memj=me