操作系統(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)康?磁盤是一種高速、大容量、旋轉(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)#define M 20

2、 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; 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)者的工作由“驅(qū)動(dòng)調(diào)度”進(jìn)程來(lái)完成

3、。 由于磁盤與處理器是可以并行工作的、所以當(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)可參考圖31（2） “接收請(qǐng)求”進(jìn)程建立一張“請(qǐng)求I/O”表，指出訪問(wèn)磁盤的進(jìn)程要求訪問(wèn)的物理地址，表的格式為：進(jìn)程名柱面號(hào)磁道號(hào)物理記錄號(hào)初始化輸入在0，1區(qū)間內(nèi)的一個(gè)隨機(jī)數(shù)隨機(jī)數(shù)&g

4、t;1/2開(kāi)始驅(qū)動(dòng)調(diào)度接受請(qǐng)求繼續(xù)？結(jié)束是是否否 圖31 程序結(jié)構(gòu)假定某個(gè)磁盤組共有200個(gè)柱面，由外向里順序編號(hào)（0199），每個(gè)柱面上有20個(gè)磁道，編號(hào)為019，每個(gè)磁道分成8個(gè)物理記錄，編號(hào)07。進(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)單起見(jiàn)，在實(shí)驗(yàn)中可免去隊(duì)列管理部分，故設(shè)計(jì)程序時(shí)可不考慮“進(jìn)程排入等待隊(duì)列”的工作。（3）“驅(qū)動(dòng)調(diào)度”進(jìn)程的功能是查“請(qǐng)求I/O”表，當(dāng)有等待訪問(wèn)磁盤的進(jìn)程時(shí)，按電梯調(diào)度算法從中選擇一個(gè)等待訪問(wèn)者，按該進(jìn)程指定的磁盤物理地址啟動(dòng)磁

5、盤為其服務(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)求，若沿這個(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。 開(kāi)始有請(qǐng)求

6、？輸入：進(jìn)程名物理地址進(jìn)程排入等待隊(duì)列登記“請(qǐng)求I/O表返回是否 圖 32 “接收請(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)前移臂方向；當(dāng)前柱面號(hào)，物理記錄號(hào)來(lái)代替圖33中的“啟動(dòng)磁盤”這項(xiàng)工作開(kāi)始查”請(qǐng)求I/O表”否是有等待訪問(wèn)者?有與當(dāng)前柱面號(hào)相同的訪問(wèn)者?否是返回選擇能使旋轉(zhuǎn)距離最短的訪問(wèn)者當(dāng)前移臂方向是向里移?否是有比當(dāng)前柱面號(hào)大的訪問(wèn)請(qǐng)求?有比

7、當(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)磁盤，被選中者退出“請(qǐng)求I/O表”圖3-3 電梯調(diào)度模擬算法返回五、源程序#include"stdio.h" #include"stdlib.h" #include"conio.h" #include"string.h" #define M 20 typedef struct PCB char procM;/進(jìn)程名 int

8、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為down PCB *h=NULL; /存放當(dāng)前運(yùn)行中的進(jìn)程的信息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-

9、>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_num; h->phy_num=Q->phy_num; /插入函數(shù)void insert(PCB *p) PCB *q; q=head; if(head=NULL) head=p; else for(q=head;q->next!=NULL;q=q->next);

10、 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(" %s t%d t%d t%d",h->proc,h->cylinder_num,h->track_num,h->phy_num); void output() PCB *p; p=head; printf("進(jìn)程名柱面

11、號(hào) 磁道號(hào) 物理記錄號(hào)n"); if(p=NULL) printf("-*進(jìn)程表為空,接收請(qǐng)求或按'n'退出*-n"); 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

12、("請(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"); printf("進(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&

13、quot;,&p->proc); scanf("%d",&p->cylinder_num); scanf("%d",&p->track_num); scanf("%d",&p->phy_num); p->next=NULL; insert(p); printf("n"); /接受請(qǐng)求模塊void Receive_requests() PCB *p; int i,n,m; printf("請(qǐng)輸入一個(gè)值: n"); printf(&quo

14、t;1.<接收請(qǐng)求> n"); printf("0.<繼續(xù)執(zhí)行> n"); scanf("%d",&i); if(i=1) printf("正在運(yùn)行的進(jìn)程為：n"); printf("n"); /*if(direction=1) /啟動(dòng)磁盤 out_info(); printf(" upn"); printf("n"); if(direction=-1) out_info(); printf(" downn");

15、printf("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"

16、,&p->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"); /電梯調(diào)度算法v

17、oid 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) 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->cyl

18、inder_num) 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; q=q-&

19、gt;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)前移臂方向向外 while(q!=NULL)&&(q->cylinder_num >h->cylinder_num) q=q->next; if(q=NULL)/

20、沒(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è)最大的，用p指向

21、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/有比當(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<

22、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) cha=-cha; if(min>cha)/有更小的節(jié)點(diǎn)，旋轉(zhuǎn)距離最短的訪問(wèn)者 min=cha; p=q;/指向最小的節(jié)點(diǎn) q=q->next; /while查找 /else current_process(p);/保留選中的進(jìn)程 if(direction=1) /啟動(dòng)磁盤 printf("被選中的等待

23、進(jìn)程為：n"); printf("n"); out_info(); printf(" 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

24、除進(jìn)程的前一個(gè)節(jié)點(diǎn) B=B->next; B->next=p->next;/被選中者退出I/O請(qǐng)求表 /if(q!=NULL)結(jié)束 else printf("請(qǐng)求進(jìn)程表為空,接收請(qǐng)求或退出n"); /電梯調(diào)度算法結(jié)束void main()/主函數(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&qu