操作系統(tǒng)驅(qū)動(dòng)調(diào)度

1、.實(shí)驗(yàn)三驅(qū)動(dòng)調(diào)度一、實(shí)驗(yàn)內(nèi)容模擬電梯調(diào)度算法 ，實(shí)現(xiàn)對(duì)磁盤的驅(qū)動(dòng)調(diào)度 。二、實(shí)驗(yàn)?zāi)康拇疟P是一種高速 、大容量 、旋轉(zhuǎn)型、可直接存取的存儲(chǔ)設(shè)備。它作為計(jì)算機(jī)系統(tǒng)的輔助存儲(chǔ)器 ，擔(dān)負(fù)著繁重的輸入輸出任務(wù)、在多道程序設(shè)計(jì)系統(tǒng)中，往往同時(shí)會(huì)有若干個(gè)要求訪問(wèn)磁盤的輸入輸出請(qǐng)求等待處理。系統(tǒng)可采用一種策略 ，盡可能按最佳次序執(zhí)行要求訪問(wèn)磁盤的諸輸入輸出請(qǐng)求。這就叫驅(qū)動(dòng)調(diào)度 ，使用的算法稱為驅(qū)動(dòng)調(diào)度算法 。 驅(qū)動(dòng)調(diào)度能降低為若干個(gè)輸入輸出請(qǐng)求服務(wù)所需的總時(shí)間，從而提高系統(tǒng)效率 。本實(shí)驗(yàn)要求學(xué)生模擬設(shè)計(jì)一個(gè)驅(qū)動(dòng)調(diào)度程序，觀察驅(qū)動(dòng)調(diào)度程序的動(dòng)態(tài)運(yùn)行過(guò)程 。通過(guò)實(shí)驗(yàn)使學(xué)生理解和掌握驅(qū)動(dòng)調(diào)度的職能。三、數(shù)據(jù)結(jié)構(gòu)#d

2、efine M 20typedef struct PCBchar procM;/進(jìn)程名int cylinder_num;/柱面號(hào)int track_num;/磁道號(hào).專業(yè) .專注.int phy_num;/物理記錄號(hào)struct PCB *next;PCB;四、實(shí)驗(yàn)題目模擬電梯調(diào)度算法 ，對(duì)磁盤進(jìn)行移臂和旋轉(zhuǎn)調(diào)度。（1）磁盤是可供多個(gè)進(jìn)程共享的存儲(chǔ)設(shè)備，但一個(gè)磁盤每時(shí)刻只能為一個(gè)進(jìn)程服務(wù)。當(dāng)有進(jìn)程在訪問(wèn)某個(gè)磁盤時(shí)，其他想訪問(wèn)該磁盤的進(jìn)程必須等待，直到磁盤一次工作結(jié)束 。 當(dāng)有多個(gè)進(jìn)程提出輸入輸出要求而處于等待狀態(tài)時(shí)，可用電梯調(diào)度算法從若干個(gè)等待訪問(wèn)者中選擇一個(gè)進(jìn)程，讓它訪問(wèn)磁盤 。 選擇訪問(wèn)者

3、的工作由“驅(qū)動(dòng)調(diào)度 ”進(jìn)程來(lái)完成 。由于磁盤與處理器是可以并行工作的、所以當(dāng)磁盤在作為一個(gè)進(jìn)程服務(wù)時(shí)，占有處理器的另一進(jìn)程可以提出使用磁盤的要求，也就是說(shuō) ，系統(tǒng)能動(dòng)態(tài)地接收新的輸入輸出請(qǐng)求 。 為了模擬這種情況 ，在本實(shí)驗(yàn)中設(shè)置了一個(gè)“接收請(qǐng)求 ”進(jìn)程?！膀?qū)動(dòng)調(diào)度 ”進(jìn)程和 “接收請(qǐng)求 ”進(jìn)程能否占有處理器運(yùn)行，取決于磁盤的結(jié)束中斷信號(hào)和處理器調(diào)度策略。在實(shí)驗(yàn)中可用隨機(jī)數(shù)來(lái)模擬確定這兩個(gè)進(jìn)程的運(yùn)行順序，以代替中斷處理和處理器調(diào)度選擇的過(guò)程。因而，程序的結(jié)構(gòu)可參考圖3 1（2）“接收請(qǐng)求 ”進(jìn)程建立一張 “請(qǐng)求 I/O ”表 ，指出訪問(wèn)磁盤的進(jìn)程要求訪問(wèn)的物理地址 ，表的格式為 ：進(jìn)程名柱面號(hào)

4、磁道號(hào)物理記錄號(hào).專業(yè) .專注.開始初始化輸入在 0，1區(qū)間內(nèi)的一個(gè)隨機(jī)數(shù)是否隨機(jī)數(shù) >1/2驅(qū)動(dòng)調(diào)度接受請(qǐng)求是否繼續(xù)？結(jié)束.專業(yè) .專注.圖 31程序結(jié)構(gòu)假定某個(gè)磁盤組共有200 個(gè)柱面，由外向里順序編號(hào) （0 199 ），每個(gè)柱面上有 20 個(gè)磁道，編號(hào)為 0 19，每個(gè)磁道分成8 個(gè)物理記錄 ，編號(hào) 0 7。進(jìn)程訪問(wèn)磁盤的物理地址可以用鍵盤輸入的方法模擬得到。圖 32 是“接收請(qǐng)求 ”進(jìn)程的模擬算法 。在實(shí)際的系統(tǒng)中必須把等待訪問(wèn)磁盤的進(jìn)程排入等待列隊(duì)，由于本實(shí)驗(yàn)?zāi)M驅(qū)動(dòng)調(diào)度 ，為簡(jiǎn)單起見 ，在實(shí)驗(yàn)中可免去隊(duì)列管理部分，故設(shè)計(jì)程序時(shí)可不考慮“進(jìn)程排入等待隊(duì)列 ”的工作。（3）“驅(qū)動(dòng)

5、調(diào)度 ”進(jìn)程的功能是查 “請(qǐng)求 I/O ”表，當(dāng)有等待訪問(wèn)磁盤的進(jìn)程時(shí)，.專業(yè) .專注.按電梯調(diào)度算法從中選擇一個(gè)等待訪問(wèn)者，按該進(jìn)程指定的磁盤物理地址啟動(dòng)磁盤為其服務(wù) 。對(duì)移動(dòng)臂磁盤來(lái)說(shuō)，驅(qū)動(dòng)調(diào)度分移臂調(diào)度和旋轉(zhuǎn)調(diào)度。電梯調(diào)度算法的調(diào)度策略是與移動(dòng)臂的移動(dòng)方向和移動(dòng)臂的當(dāng)前位子有關(guān)的，所以每次啟動(dòng)磁盤時(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)求，

6、若沿這個(gè)方向沒(méi)有訪問(wèn)請(qǐng)求時(shí)，就改變臂的移動(dòng)方向 。 這種調(diào)度策略能使移動(dòng)臂的移動(dòng)頻率極小 ，從而提高系統(tǒng)效率 。用電梯調(diào)度算法實(shí)現(xiàn)驅(qū)動(dòng)調(diào)度的模擬算法如圖33。開始否有請(qǐng)求？是輸入：進(jìn)程返回名物理地址進(jìn)程排入等待隊(duì)列登記“請(qǐng)求I/O 表.專業(yè) .專注.圖 3 2“接收請(qǐng)求 ”模擬算法（4）圖 31 中的初始化工作包括 ，初始化 “請(qǐng)求 I/O ”表 ，置當(dāng)前移臂方向?yàn)槔镆?；置?dāng)前位置為 0 號(hào)柱面，0 號(hào)物理記錄 。程序運(yùn)行前可假定 “請(qǐng)求 I/O ”表中已經(jīng)有如干個(gè)進(jìn)程等待訪問(wèn)磁盤。在模擬實(shí)驗(yàn)中 ，當(dāng)選中一個(gè)進(jìn)程可以訪問(wèn)磁盤時(shí)，并不實(shí)際地啟動(dòng)磁盤 ，而用顯示：“請(qǐng)求 I/O ”表； 當(dāng)前移臂方

7、向 ；當(dāng)前柱面號(hào) ，物理記錄號(hào)來(lái)代替圖3 3 中的“啟動(dòng)磁盤 ”這項(xiàng)工作開始.專業(yè) .專注.查”請(qǐng)求 I/O 表 ”否是有等待訪問(wèn)者 ?有與當(dāng)前柱面號(hào)相返回否是同的訪問(wèn)者 ?選擇能使旋轉(zhuǎn)距當(dāng)前移臂方向離最短的訪問(wèn)者是否是向里移 ?有比當(dāng)前柱面號(hào)有比當(dāng)前柱面號(hào)大的訪問(wèn)請(qǐng)求 ?小的訪問(wèn)請(qǐng)求 ?否是是置當(dāng)前移臂方置當(dāng)前移臂方向?yàn)橄蛲庖葡驗(yàn)橄蚶镆?專業(yè) .專注.從大于當(dāng)前柱面號(hào)的訪問(wèn)從大于當(dāng)前柱面號(hào)的訪問(wèn)請(qǐng)求中選擇一個(gè)最小者請(qǐng)求中選擇一個(gè)最小者添加當(dāng)前位置：柱面號(hào)；物理記錄號(hào)啟動(dòng)磁盤，被選中者退出“請(qǐng)求I/O 表”返回圖 3-3 電梯調(diào)度模擬算法五、源程序#include"stdio.h&q

8、uot;#include"stdlib.h"#include"conio.h"#include"string.h"#define M 20typedef struct PCB.專業(yè) .專注.char procM;/進(jìn)程名int cylinder_num;/柱面號(hào)int track_num;/磁道號(hào)int phy_num;/物理記錄號(hào)struct PCB *next;PCB;PCB *head=NULL;int direction ;/定義方向 ， 1為 up ， -1 為downPCB *h=NULL; / 存放當(dāng)前運(yùn)行中的進(jìn)程的信息

9、.專業(yè) .專注.void init () /初始化當(dāng)前進(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;/ 模擬記錄當(dāng)前運(yùn)行進(jìn)程void current_process(PCB *Q)strcpy(h->proc,Q->proc);h->cylinder_num = Q->cylinder_num;h->track_num=Q->track_n

10、um;h->phy_num=Q->phy_num;/ 插入函數(shù)void insert(PCB *p)PCB *q;q=head;.專業(yè) .專注.if(head=NULL)head=p;elsefor(q=head;q->next!=NULL;q=q->next);p->next=q->next;q->next=p;void out_info()/ 輸出進(jìn)程的信息printf(" n");printf(" 進(jìn)程名 柱面號(hào) 磁道號(hào) 物理記錄號(hào) 方向 n");printf(" n");printf(

11、"%st%dt%dt%d",h->proc,h->cylinder_num,h->track_num,h->phy_num);.專業(yè) .專注.void output()PCB *p;p=head;printf(" 進(jìn)程名柱面號(hào)磁道號(hào) 物理記錄號(hào) n");if(p=NULL)printf("-*進(jìn)程表為空 ,接收請(qǐng)求或按 'n' 退出 *-n");elsewhile(p!=NULL)printf("%st%dt%dt%dn",p->proc,p->cylinder_

12、num,p->track_num,p->phy_num);p=p->next;/ 初始化 I/O 請(qǐng)求表void create_PCB().專業(yè) .專注.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",&n);printf(" 請(qǐng)依次輸入進(jìn)程的相關(guān)信息: （用空格分隔 ）n");printf(" n");prin

13、tf(" 進(jìn)程名，柱面號(hào)，磁道號(hào)，物理記錄號(hào) n");for(i=1;i<=n;)i+;/printf(" 請(qǐng)輸入第 %d個(gè)進(jìn)程的信息 :n",i);p=(PCB *)malloc(sizeof(PCB);scanf("%s",&p->proc);scanf("%d",&p->cylinder_num);scanf("%d",&p->track_num);scanf("%d",&p->phy_num);p->

14、next=NULL;insert(p); printf(" n");.專業(yè) .專注./ 接受請(qǐng)求模塊void Receive_requests()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)行的進(jìn)程為 ：n");printf("n")

15、;/*if(direction=1)/ 啟動(dòng)磁盤out_info();printf(" upn");printf("n");if(direction=-1).專業(yè) .專注.out_info();printf(" downn");printf("n");*/printf("n");printf(" 接受請(qǐng)求前的等待進(jìn)程表為n");output();printf(" 請(qǐng)輸入接受等待進(jìn)程數(shù)量n");scanf("%d",&n);pri

16、ntf(" 請(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->proc);.專業(yè) .專注.scanf("%d",&p->cylinder_num);scanf("%d",&p->track_num);scanf("%d",&p->phy_num);p->

17、;next=NULL;insert(p);printf(" 接受請(qǐng)求后的等待進(jìn)程表為：n");printf("n");output();elseprintf(" 沒(méi)有接受進(jìn)程 ，繼續(xù)往下運(yùn)行程序n");/ 電梯調(diào)度算法void lift()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).專業(yè) .專注. .while(q!=NULL)&&(q->cylinder_num!=h->cyli

18、nder_num)/找到第一個(gè)相同的柱面號(hào)q=q->next;if(q=NULL)/沒(méi)有柱面號(hào)相同的等待進(jìn)程q=head;if(direction=1)/當(dāng)前移臂方向 upwhile(q!=NULL)&&(q->cylinder_num <h->cylinder_num)q=q->next;if(q=NULL)/沒(méi)有比當(dāng)前柱面號(hào)大的等待進(jìn)程direction=-1;/置當(dāng)前移臂方向?yàn)橥庖苢=head;/ 從小于當(dāng)前柱面號(hào)的訪問(wèn)中選擇一個(gè)最大的,p指向.專業(yè) .專注. .p=q;max=q->cylinder_num;q=q->next;

19、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;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).專業(yè) .專注. .min=q-&g

20、t;cylinder_num;p=q;/p 指向最小的節(jié)點(diǎn)q=q->next;else/ 當(dāng)前移臂方向向外while(q!=NULL)&&(q->cylinder_num >h->cylinder_num)q=q->next;if(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;.專業(yè) .專注. .while(q!=NULL)if(min>q->cylinder_num)min=

21、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è)最大的，用p 指向if(p->cylinder_num<q->cylinder_num&&q->cylinder_num<h->cylinder_num)max=q->cylinder_num;.專業(yè) .專注. .p=q;/p 指向最大的節(jié)點(diǎn)q=q->next;/

22、else/ 有比當(dāng)前柱面號(hào)小的請(qǐng)求進(jìn)程/else/ 當(dāng)前移臂方向向外/if(q=NULL)/沒(méi)有柱面號(hào)相同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->cylinder_num=h->cylinder_num)/有柱面號(hào)相同cha=q->phy_num-h->phy_num;if(cha<0).專業(yè) .專注. .cha=-cha;

23、if(min>cha)/有更小的節(jié)點(diǎn) ，旋轉(zhuǎn)距離最短的訪問(wèn)者min=cha;p=q;/ 指向最小的節(jié)點(diǎn)q=q->next;/while 查找/elsecurrent_process(p);/ 保留選中的進(jìn)程if(direction=1)/ 啟動(dòng)磁盤printf(" 被選中的等待進(jìn)程為 ：n");printf("n");out_info();printf(" upn");printf("n");if(direction=-1)printf(" 被選中的等待進(jìn)程為 ：n");.專業(yè) .專

24、注. .printf("n");out_info();printf(" downn");printf("n");if(p=head)head=p->next;elseB=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)求表/if(q!=NULL) 結(jié)束elseprintf(" 請(qǐng)求進(jìn)程表為空 ,接收請(qǐng)求或退出 n");.專業(yè) .專注. ./ 電梯調(diào)度算法結(jié)束void main()/主函

25、數(shù)system("cls");char go='y'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");printf("I/O 請(qǐng)求進(jìn)程等待表為 ：n");printf("n");output();while(go='y'|go!='n') printf("n");printf(" 輸入 01 之間的數(shù)