操作系統(tǒng)電梯調(diào)度LRU頁(yè)面反饋

1、操作系統(tǒng)原理課程設(shè)計(jì)報(bào)告姓 名： 付豪 班 級(jí)： 網(wǎng)絡(luò)1311 學(xué) 號(hào)： 131003600139 指導(dǎo)老師： 寧建紅 2016 年 1月目 錄1 背景知識(shí)11.1電梯調(diào)度算法11.2頁(yè)故障率反饋模型12 設(shè)計(jì)內(nèi)容22.1電梯調(diào)度算法22.1.1基本原理分析22.1.2數(shù)據(jù)結(jié)構(gòu)22.1.3程序流程圖32.1.4函數(shù)介紹42.1.5源代碼42.1.6結(jié)果122.2頁(yè)故障率反饋模型142.2.1基本原理分析142.2.2程序流程圖152.2.3函數(shù)介紹162.2.4源代碼162.2.5結(jié)果183 結(jié)論20參考文獻(xiàn)211 背景知識(shí)1.1電梯調(diào)度算法磁盤(pán)調(diào)度在多道程序設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)中，各個(gè)進(jìn)程可能會(huì)

2、不斷提出不同的對(duì)磁盤(pán)進(jìn)行讀/寫(xiě)操作的請(qǐng)求。由于有時(shí)候這些進(jìn)程的發(fā)送請(qǐng)求的速度比磁盤(pán)響應(yīng)的還要快，因此我們有必要為每個(gè)磁盤(pán)設(shè)備建立一個(gè)等待隊(duì)列，常用的磁盤(pán)調(diào)度算法有以下四種：先來(lái)先服務(wù)算法（FCFS），最短尋道時(shí)間優(yōu)先算法（SSTF），電梯調(diào)度算法（SCAN），循環(huán)掃描算法（CSCAN） SCAN算法在磁頭當(dāng)前移動(dòng)方向上選擇與當(dāng)前磁頭所在磁道距離最近的請(qǐng)求作為下一次服務(wù)的對(duì)象。由于磁頭移動(dòng)規(guī)律與電梯運(yùn)行相似，故又稱(chēng)為電梯調(diào)度算法。SCAN算法對(duì)最近掃描過(guò)的區(qū)域不公平，因此，它在訪問(wèn)局部性方面不如FCFS算法和SSTF算法好。 算法思想：當(dāng)設(shè)備無(wú)訪問(wèn)請(qǐng)求時(shí)，磁頭不動(dòng)；當(dāng)有訪問(wèn)請(qǐng)求時(shí)，磁頭按一個(gè)方向

3、移動(dòng)，在移動(dòng)過(guò)程中對(duì)遇到的訪問(wèn)請(qǐng)求進(jìn)行服務(wù)，然后判斷該方向上是否還有訪問(wèn)請(qǐng)求，如果有則繼續(xù)掃描；否則改變移動(dòng)方向，并為經(jīng)過(guò)的訪問(wèn)請(qǐng)求服務(wù)，如此反復(fù)。1.2頁(yè)故障率反饋模型在虛擬頁(yè)式存儲(chǔ)管理系統(tǒng)中，進(jìn)程運(yùn)行之前會(huì)把一部分頁(yè)面裝入內(nèi)存，而另一部分頁(yè)面裝入外存中。在進(jìn)程運(yùn)行過(guò)程中，如果所訪問(wèn)的頁(yè)面在內(nèi)存，則與無(wú)虛擬頁(yè)存儲(chǔ)時(shí)的情形相同；所訪問(wèn)的頁(yè)面不在內(nèi)存，則發(fā)生缺頁(yè)故障。建立工作集頁(yè)面模型，利用隨機(jī)函數(shù)動(dòng)態(tài)生成進(jìn)程訪問(wèn)頁(yè)面的序列號(hào)，實(shí)現(xiàn)頁(yè)面淘汰算法，實(shí)現(xiàn)頁(yè)故障率反饋模型。在虛擬頁(yè)式存儲(chǔ)管理系統(tǒng)中，進(jìn)程運(yùn)行之前會(huì)把一部分頁(yè)面裝入內(nèi)存，而另一部分頁(yè)面裝入外存。在進(jìn)程運(yùn)行過(guò)程中，如果所訪問(wèn)的頁(yè)面在內(nèi)存，則

4、與無(wú)虛擬頁(yè)式存儲(chǔ)時(shí)的情形相同；如果所訪問(wèn)的頁(yè)面不在內(nèi)存，則發(fā)生缺頁(yè)故障，進(jìn)入操作系統(tǒng)，有操作系統(tǒng)進(jìn)行頁(yè)面的動(dòng)態(tài)調(diào)度，進(jìn)行頁(yè)面的置換。2 設(shè)計(jì)內(nèi)容2.1電梯調(diào)度算法2.1.1基本原理分析電梯調(diào)度算法的調(diào)度策略是與移動(dòng)臂的移動(dòng)方向和移動(dòng)臂的當(dāng)前位子有關(guān)的，所以每次啟動(dòng)磁盤(pán)時(shí)都應(yīng)登記移動(dòng)臂方向和當(dāng)前位子。電梯調(diào)度算法是一種簡(jiǎn)單而實(shí)用的驅(qū)動(dòng)調(diào)度方法，這種調(diào)度策略總是優(yōu)先選擇與當(dāng)前柱面號(hào)相同的訪問(wèn)請(qǐng)求，從這些請(qǐng)求中再選擇一個(gè)能使旋轉(zhuǎn)距離最短的等待訪問(wèn)者。如果沒(méi)有與當(dāng)前柱面號(hào)相同的訪問(wèn)請(qǐng)求，則根據(jù)移臂方向來(lái)選擇，每次總是沿臂移動(dòng)方向選擇一個(gè)與當(dāng)前柱面號(hào)最近的訪問(wèn)請(qǐng)求，若沿這個(gè)方向沒(méi)有訪問(wèn)請(qǐng)求時(shí)，就改變臂的

5、移動(dòng)方向。這種調(diào)度策略能使移動(dòng)臂的移動(dòng)頻率極小，從而提高系統(tǒng)效率。用電梯調(diào)度算法實(shí)現(xiàn)驅(qū)動(dòng). 模擬電梯調(diào)度算法，對(duì)磁盤(pán)進(jìn)行移臂和旋轉(zhuǎn)調(diào)度。磁盤(pán)是可供多個(gè)進(jìn)程共享的存儲(chǔ)設(shè)備，但一個(gè)磁盤(pán)每時(shí)刻只能為一個(gè)進(jìn)程服務(wù)。當(dāng)有進(jìn)程在訪問(wèn)某個(gè)磁盤(pán)時(shí)，其他想訪問(wèn)該磁盤(pán)的進(jìn)程必須等待，直到磁盤(pán)一次工作結(jié)束。當(dāng)有多個(gè)進(jìn)程提出輸入輸出要求而處于等待狀態(tài)時(shí)，可用電梯調(diào)度算法從若干個(gè)等待訪問(wèn)者中選擇一個(gè)進(jìn)程，讓它訪問(wèn)磁盤(pán)。選擇訪問(wèn)者的工作由“驅(qū)動(dòng)調(diào)度”進(jìn)程來(lái)完成。 由于磁盤(pán)與處理器是可以并行工作的、所以當(dāng)磁盤(pán)在作為一個(gè)進(jìn)程服務(wù)時(shí)，占有處理器的另一進(jìn)程可以提出使用磁盤(pán)的要求，也就是說(shuō)，系統(tǒng)能動(dòng)態(tài)地接收新的輸入輸出請(qǐng)求。為了模

6、擬這種情況，在本實(shí)驗(yàn)中設(shè)置了一個(gè)“接收請(qǐng)求”進(jìn)程?！膀?qū)動(dòng)調(diào)度”進(jìn)程和“接收請(qǐng)求”進(jìn)程能否占有處理器運(yùn)行，取決于磁盤(pán)的結(jié)束中斷信號(hào)和處理器調(diào)度策略。在實(shí)驗(yàn)中可用隨機(jī)數(shù)來(lái)模擬確定這兩個(gè)進(jìn)程的運(yùn)行順序，以代替中斷處理和處理器調(diào)度選擇的過(guò)程。2.1.2數(shù)據(jù)結(jié)構(gòu)typedef struct PCB char procM;/進(jìn)程名 int cylinder_num;/柱面號(hào) int track_num;/磁道號(hào) int phy_num;/物理記錄號(hào) struct PCB *next;/ 進(jìn)程指向下一節(jié)點(diǎn)PCB; 2.1.3程序流程圖開(kāi)始查”請(qǐng)求I/O表”否是有等待訪問(wèn)者?有與當(dāng)前柱面號(hào)相同的訪問(wèn)者?否是返

7、回選擇能使旋轉(zhuǎn)距離最短的訪問(wèn)者當(dāng)前移臂方向是向里移?否是有比當(dāng)前柱面號(hào)大的訪問(wèn)請(qǐng)求?有比當(dāng)前柱面號(hào)小的訪問(wèn)請(qǐng)求?否是是置當(dāng)前移臂方向?yàn)橄蚶镆浦卯?dāng)前移臂方向?yàn)橄蛲庖茝男∮诋?dāng)前柱面號(hào)的訪問(wèn)請(qǐng)求中選擇一個(gè)最大者從大于當(dāng)前柱面號(hào)的訪問(wèn)請(qǐng)求中選擇一個(gè)最小者添加當(dāng)前位置：柱面號(hào)；物理記錄號(hào)啟動(dòng)磁盤(pán)，被選中者退出“請(qǐng)求I/O表”圖2.1.3-1 電梯調(diào)度模擬算法框圖返回2.1.4函數(shù)介紹 void init () /初始化進(jìn)程并分配空間 void current_process(PCB *Q) /模擬進(jìn)程記錄void insert(PCB *p) /插入函數(shù)void out_info() /輸出進(jìn)程的信息v

8、oid output()/顯示當(dāng)前I/O表void create_PCB()/初始化I/O請(qǐng)求表void Receive_requests()/接受請(qǐng)求模塊void lift()/電梯調(diào)度算法void main()/主函數(shù)2.1.5源代碼#include"stdio.h" #include"stdlib.h" #include"string.h" #define M 20 typedef struct PCB char procM;/進(jìn)程名 int cylinder_num;/柱面號(hào) int track_num;/磁道號(hào) int ph

9、y_num;/物理記錄號(hào) struct PCB *next; PCB; PCB *head=NULL; int direction ;/定義方向，1為up，-1為down PCB *h=NULL; /存放當(dāng)前運(yùn)行中的進(jìn)程的信息void init ()/初始化進(jìn)程并分配空間 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) /模擬進(jìn)程記錄 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) /插入函數(shù) 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() /輸出進(jìn)程的信息 printf(" 進(jìn)程名 柱面號(hào) 磁道號(hào) 物理記錄號(hào) 方向n"); printf(" %s t%d t%d t%d ",h->proc,h->cylinder_num,h->track_num,h->phy_num); void output() /顯示當(dāng)前I/O表 PCB *p; p=head; printf("進(jìn)程名 柱面號(hào) 磁道號(hào) 物理記錄號(hào)n"); if(p=NULL) printf("-進(jìn)程表為空,接收請(qǐng)求或按'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請(qǐng)求表void create_PCB() PCB *p,*q; q=head; int i,n; printf("n"); printf("請(qǐng)輸入I/O進(jìn)程表中進(jìn)程等待的個(gè)數(shù)：n"); printf("n"); scanf("%d",&a

13、mp;n); printf("請(qǐng)依次輸入進(jìn)程的相關(guān)信息: （用空格分隔）n"); printf("-n"); printf("進(jìn)程名，柱面號(hào)，磁道號(hào)，物理記錄號(hào)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() /接受請(qǐng)求模塊 PCB *p; int i,n,m; printf("請(qǐng)輸入一個(gè)值: n"); printf("1.<接收請(qǐng)求> n"); printf("0.<繼續(xù)執(zhí)行> n"); scanf("%d",&i); if(i=1) printf("正在運(yùn)

15、行的進(jìn)程為：n"); printf("n"); printf("接受請(qǐng)求前的等待進(jìn)程表為n"); output(); printf("請(qǐng)輸入接受等待進(jìn)程數(shù)量n"); scanf("%d",&n); printf("請(qǐng)依次輸入進(jìn)程的信息n"); printf("進(jìn)程名，柱面號(hào)，磁道號(hào)，物理記錄號(hào)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("接受請(qǐng)求后的等待進(jìn)程表為：n"); printf("n"); output(); else printf("沒(méi)有接受進(jìn)程，繼續(xù)往下運(yùn)行程序n"); void lift() /電梯調(diào)度算

17、法 int min,cha,max; PCB *p,*q,*B;/p為指要?jiǎng)h除的節(jié)點(diǎn)，q為查找的節(jié)點(diǎn)，B指向要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) q=head; if(q!=NULL) while(q!=NULL)&&(q->cylinder_num!=h->cylinder_num)/找到第一個(gè)相同的柱面號(hào) q=q->next; if(q=NULL)/沒(méi)有柱面號(hào)相同的等待進(jìn)程 q=head; if(direction=1)/當(dāng)前移臂方向up while(q!=NULL)&&(q->cylinder_num <h->cylinder_num

18、)/找到比當(dāng)前柱面號(hào)大的等待進(jìn)程 q=q->next; if(q=NULL)/沒(méi)有比當(dāng)前柱面號(hào)大的等待進(jìn)程 direction=-1;/置當(dāng)前移臂方向?yàn)橥庖?q=head;/從小于當(dāng)前柱面號(hào)的訪問(wèn)中選擇一個(gè)最大的,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指向最大的節(jié)點(diǎn) q=q->next; else/有大于當(dāng)前柱面號(hào)的等待進(jìn)程 min=q->cylinder_num; p=q

19、; q=q->next; while(q!=NULL)/大于當(dāng)前柱面號(hào)并且小于指定最小的節(jié)點(diǎn)時(shí) if(h->cylinder_num<q->cylinder_num)&&(q->cylinder_num<p->cylinder_num) min=q->cylinder_num; p=q;/p指向最小的節(jié)點(diǎn) q=q->next; else/當(dāng)前移臂方向?yàn)槔镆?while(q!=NULL)&&(q->cylinder_num >h->cylinder_num) q=q->next; if(

20、q=NULL)/沒(méi)有比當(dāng)前柱面號(hào)小的請(qǐng)求 direction=1; q=head;/從大于當(dāng)前柱面號(hào)的訪問(wèn)中選擇一個(gè)最小的,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指向最小的節(jié)點(diǎn) q=q->next; else/有比當(dāng)前柱面號(hào)小的請(qǐng)求進(jìn)程 max=q->cylinder_num; p=q; q=q->next; while(q!=NULL)/從小于當(dāng)前柱面號(hào)訪問(wèn)進(jìn)程中選擇一個(gè)

21、最大的，用p指向 if(p->cylinder_num<q->cylinder_num&&q->cylinder_num<h->cylinder_num) max=q->cylinder_num; p=q;/p指向最大的節(jié)點(diǎn) q=q->next; else/有柱面號(hào)相同的等待進(jìn)程 min=q->phy_num-h->phy_num;/第一個(gè)相同柱面號(hào)設(shè)為最小值 p=q;/指向最小的節(jié)點(diǎn)，旋轉(zhuǎn)距離最短的訪問(wèn)者 if(min<0) min=-min; q=q->next; while(q!=NULL) if(q

22、->cylinder_num=h->cylinder_num)/有柱面號(hào)相同 cha=q->phy_num-h->phy_num; if(cha<0) cha=-cha; if(min>cha)/有更小的節(jié)點(diǎn)，旋轉(zhuǎn)距離最短的訪問(wèn)者 min=cha; p=q;/指向最小的節(jié)點(diǎn) q=q->next; current_process(p);/保留選中的進(jìn)程 if(direction=1) /啟動(dòng)磁盤(pán) printf("被選中的等待進(jìn)程為：n"); printf("n"); out_info(); printf("

23、; upn"); printf("n"); if(direction=-1) printf("被選中的等待進(jìn)程為：n"); printf("n"); out_info(); printf(" downn"); printf("n"); if(p=head) head=p->next; else B=head; while(B->next!=p)/找到要?jiǎng)h除進(jìn)程的前一個(gè)節(jié)點(diǎn) B=B->next; B->next=p->next;/被選中者退出I/O請(qǐng)求表 e

24、lse printf("請(qǐng)求進(jìn)程表為空,接收請(qǐng)求或退出n"); /電梯調(diào)度算法結(jié)束void main()/主函數(shù) char go='y' /默認(rèn)值 float number; init(); printf(" -執(zhí)行驅(qū)動(dòng)調(diào)度-n"); printf(" -當(dāng)前運(yùn)行進(jìn)程為-n"); out_info(); printf(" upn"); printf(" -*創(chuàng)建I/O請(qǐng)求進(jìn)程等待表*-n"); create_PCB(); /創(chuàng)建進(jìn)程鏈表 printf("n")

25、; printf("I/O請(qǐng)求進(jìn)程等待表為：n"); printf("n"); output(); while(go='y'|go!='n') printf("n"); /number=rand()/(RAND_MAX+1.0); printf("輸入01之間的數(shù)：n"); printf(">0.5 -<電梯調(diào)度> n"); printf("<=0.5 -<接受請(qǐng)求> n"); scanf("%f&

26、quot;,&number); while(number>0.5) lift(); printf("調(diào)用電梯驅(qū)動(dòng)調(diào)度算法后的I/O請(qǐng)求表為：n"); printf("n"); output(); break; if(number<=0.5) Receive_requests();/調(diào)用接受請(qǐng)求模塊 printf("是否繼續(xù)？n"); printf("<y:繼續(xù)>n"); printf("<n:退出>n"); scanf("%s",&

27、amp;go); 2.1.6結(jié)果 圖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頁(yè)故障率反饋模型2.2.1基本原理分析頁(yè)故障率反饋模型工作集模型的精確度與窗口尺寸密切相關(guān)。如過(guò)小，程序的活動(dòng)頁(yè)面不能全部裝入內(nèi)存，缺頁(yè)率就高；如過(guò)大，允許同時(shí)并發(fā)執(zhí)行進(jìn)程的個(gè)數(shù)就會(huì)降低。采用工作集模型，操作系統(tǒng)動(dòng)態(tài)紀(jì)錄各個(gè)進(jìn)程的工作集，并動(dòng)態(tài)地調(diào)整分配給各個(gè)進(jìn)程的頁(yè)架數(shù)。在虛擬頁(yè)式存儲(chǔ)管理中，頁(yè)故障率反饋模型試圖將各個(gè)進(jìn)程的缺頁(yè)率控制在一個(gè)合適的范圍內(nèi)。當(dāng)一個(gè)進(jìn)程缺頁(yè)率大于指定的故障率上限，而且內(nèi)存有空閑的頁(yè)架，就給該進(jìn)程增加分配的頁(yè)架數(shù)；當(dāng)一個(gè)進(jìn)

28、程缺頁(yè)率小于指定的故障率下限，就從該進(jìn)程所分配的頁(yè)架中收回一些頁(yè)架；當(dāng)頁(yè)故障率在指定的范圍之內(nèi)，則保持該進(jìn)程所擁有的頁(yè)架。最近最少使用頁(yè)面替換算法LRU最近最少使用頁(yè)面替換算法淘汰的頁(yè)面是在最近一段時(shí)間內(nèi)最近未被訪問(wèn)的那一頁(yè)，它是基于程序局部性原理來(lái)考慮的，認(rèn)為那些剛被使用過(guò)的頁(yè)面可能還要立即被使用，而那些在較長(zhǎng)時(shí)間內(nèi)未被使用的頁(yè)面可能不會(huì)立即使用。為了能準(zhǔn)確地淘汰最近最少使用的頁(yè)面，必須維護(hù)一個(gè)特殊隊(duì)列頁(yè)面淘汰隊(duì)列，此隊(duì)列存放當(dāng)前在內(nèi)存中的所有頁(yè)號(hào)，每訪問(wèn)一頁(yè)時(shí)就調(diào)整一次，使隊(duì)列尾總是指向最近訪問(wèn)的頁(yè)，隊(duì)列頭就是最近最少使用的頁(yè)，顯然，發(fā)生缺頁(yè)異常時(shí)總是淘汰隊(duì)列頭所指頁(yè)面；而執(zhí)行頁(yè)面訪問(wèn)后，

29、需要從隊(duì)列中把此頁(yè)調(diào)整到隊(duì)列尾。2.2.2程序流程圖開(kāi)始初始化工作集模型調(diào)用隨機(jī)產(chǎn)生的序列NY頁(yè)面在工作集？查找最先進(jìn)入頁(yè)面繼續(xù)調(diào)用下一頁(yè)面換頁(yè)NY序列完成修改工作集時(shí)間故障反饋，修改工作集大小NY結(jié)束輸入為q? 圖2.2.3-1 頁(yè)故障率反饋模型框圖2.2.3函數(shù)介紹void changeArray()/生成初始序列void LRU()/電梯調(diào)度，缺頁(yè)反饋int main()/主函數(shù)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("進(jìn)程調(diào)用頁(yè)面序列：");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