操作系統(tǒng)驅動調度

1、實驗三 驅動調度一、實驗內容模擬電梯調度算法，實現對磁盤的驅動調度。二、實驗目的 磁盤是一種高速、大容量、旋轉型、可直接存取的存儲設備。它作為計算機系統(tǒng)的輔助存儲器，擔負著繁重的輸入輸出任務、在多道程序設計系統(tǒng)中，往往同時會有若干個要求訪問磁盤的輸入輸出請求等待處理。系統(tǒng)可采用一種策略，盡可能按最佳次序執(zhí)行要求訪問磁盤的諸輸入輸出請求。這就叫驅動調度，使用的算法稱為驅動調度算法。驅動調度能降低為若干個輸入輸出請求服務所需的總時間，從而提高系統(tǒng)效率。本實驗要求學生模擬設計一個驅動調度程序，觀察驅動調度程序的動態(tài)運行過程。通過實驗使學生理解和掌握驅動調度的職能。三、數據結構#define M 20

2、 typedef struct PCB char procM;/進程名 int cylinder_num;/柱面號 int track_num;/磁道號 int phy_num;/物理記錄號 struct PCB *next; PCB; 四、實驗題目模擬電梯調度算法，對磁盤進行移臂和旋轉調度。（1）磁盤是可供多個進程共享的存儲設備，但一個磁盤每時刻只能為一個進程服務。當有進程在訪問某個磁盤時，其他想訪問該磁盤的進程必須等待，直到磁盤一次工作結束。當有多個進程提出輸入輸出要求而處于等待狀態(tài)時，可用電梯調度算法從若干個等待訪問者中選擇一個進程，讓它訪問磁盤。選擇訪問者的工作由“驅動調度”進程來完成

3、。 由于磁盤與處理器是可以并行工作的、所以當磁盤在作為一個進程服務時，占有處理器的另一進程可以提出使用磁盤的要求，也就是說，系統(tǒng)能動態(tài)地接收新的輸入輸出請求。為了模擬這種情況，在本實驗中設置了一個“接收請求”進程?！膀寗诱{度”進程和“接收請求”進程能否占有處理器運行，取決于磁盤的結束中斷信號和處理器調度策略。在實驗中可用隨機數來模擬確定這兩個進程的運行順序，以代替中斷處理和處理器調度選擇的過程。因而，程序的結構可參考圖31（2） “接收請求”進程建立一張“請求I/O”表，指出訪問磁盤的進程要求訪問的物理地址，表的格式為：進程名柱面號磁道號物理記錄號初始化輸入在0，1區(qū)間內的一個隨機數隨機數&g

4、t;1/2開始驅動調度接受請求繼續(xù)？結束是是否否 圖31 程序結構假定某個磁盤組共有200個柱面，由外向里順序編號（0199），每個柱面上有20個磁道，編號為019，每個磁道分成8個物理記錄，編號07。進程訪問磁盤的物理地址可以用鍵盤輸入的方法模擬得到。圖32是“接收請求”進程的模擬算法。在實際的系統(tǒng)中必須把等待訪問磁盤的進程排入等待列隊，由于本實驗模擬驅動調度，為簡單起見，在實驗中可免去隊列管理部分，故設計程序時可不考慮“進程排入等待隊列”的工作。（3）“驅動調度”進程的功能是查“請求I/O”表，當有等待訪問磁盤的進程時，按電梯調度算法從中選擇一個等待訪問者，按該進程指定的磁盤物理地址啟動磁

5、盤為其服務。對移動臂磁盤來說，驅動調度分移臂調度和旋轉調度。電梯調度算法的調度策略是與移動臂的移動方向和移動臂的當前位子有關的，所以每次啟動磁盤時都應登記移動臂方向和當前位子。電梯調度算法是一種簡單而實用的驅動調度方法，這種調度策略總是優(yōu)先選擇與當前柱面號相同的訪問請求，從這些請求中再選擇一個能使旋轉距離最短的等待訪問者。如果沒有與當前柱面號相同的訪問請求，則根據移臂方向來選擇，每次總是沿臂移動方向選擇一個與當前柱面號最近的訪問請求，若沿這個方向沒有訪問請求時，就改變臂的移動方向。這種調度策略能使移動臂的移動頻率極小，從而提高系統(tǒng)效率。用電梯調度算法實現驅動調度的模擬算法如圖33。 開始有請求

6、？輸入：進程名物理地址進程排入等待隊列登記“請求I/O表返回是否 圖 32 “接收請求”模擬算法（4）圖31中的初始化工作包括，初始化“請求I/O”表，置當前移臂方向為里移；置當前位置為0號柱面，0號物理記錄。程序運行前可假定“請求I/O”表中已經有如干個進程等待訪問磁盤。在模擬實驗中，當選中一個進程可以訪問磁盤時，并不實際地啟動磁盤，而用顯示：“請求I/O”表；當前移臂方向；當前柱面號，物理記錄號來代替圖33中的“啟動磁盤”這項工作開始查”請求I/O表”否是有等待訪問者?有與當前柱面號相同的訪問者?否是返回選擇能使旋轉距離最短的訪問者當前移臂方向是向里移?否是有比當前柱面號大的訪問請求?有比

7、當前柱面號小的訪問請求?否是是置當前移臂方向為向里移置當前移臂方向為向外移從大于當前柱面號的訪問請求中選擇一個最小者從大于當前柱面號的訪問請求中選擇一個最小者添加當前位置：柱面號；物理記錄號啟動磁盤，被選中者退出“請求I/O表”圖3-3 電梯調度模擬算法返回五、源程序#include"stdio.h" #include"stdlib.h" #include"conio.h" #include"string.h" #define M 20 typedef struct PCB char procM;/進程名 int

8、cylinder_num;/柱面號 int track_num;/磁道號 int phy_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-

9、>phy_num= 0; /模擬記錄當前運行進程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; /插入函數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() /輸出進程的信息 printf("n"); printf(" 進程名 柱面號 磁道號 物理記錄號 方向 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("進程名柱面

11、號 磁道號 物理記錄號n"); if(p=NULL) printf("-*進程表為空,接收請求或按'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請求表void create_PCB() PCB *p,*q; q=head; int i,n; printf("n"); printf

12、("請輸入I/O進程表中進程等待的個數：n"); printf("n"); scanf("%d",&n); printf("請依次輸入進程的相關信息: （用空格分隔）n"); printf("n"); printf("進程名，柱面號，磁道號，物理記錄號n"); for(i=1;i<=n;) i+; /printf("請輸入第%d個進程的信息: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"); /接受請求模塊void Receive_requests() PCB *p; int i,n,m; printf("請輸入一個值: n"); printf(&quo

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

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

16、,&p->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("沒有接受進程，繼續(xù)往下運行程序n"); /電梯調度算法v

17、oid lift() int min,cha,max; PCB *p,*q,*B;/p為指要刪除的節(jié)點，q為查找的節(jié)點，B指向要刪除節(jié)點的前一個節(jié)點 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->cyl

18、inder_num) 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指向最大的節(jié)點 q=q->next; else/有大于當前柱面號的等待進程 min=q->cylinder_num; p=q; q=q-&

19、gt;next; while(q!=NULL)/大于當前柱面號并且小于指定最小的節(jié)點時 if(h->cylinder_num<q->cylinder_num)&&(q->cylinder_num<p->cylinder_num) min=q->cylinder_num; p=q;/p指向最小的節(jié)點 q=q->next; else/當前移臂方向向外 while(q!=NULL)&&(q->cylinder_num >h->cylinder_num) q=q->next; if(q=NULL)/

20、沒有比當前柱面號小的請求 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指向最小的節(jié)點 q=q->next; else/有比當前柱面號小的請求進程 max=q->cylinder_num; p=q; q=q->next; while(q!=NULL)/從小當前柱面號訪問進程中選擇一個最大的，用p指向

21、if(p->cylinder_num<q->cylinder_num&&q->cylinder_num<h->cylinder_num) max=q->cylinder_num; p=q;/p指向最大的節(jié)點 q=q->next; /else/有比當前柱面號小的請求進程 /else/當前移臂方向向外 /if(q=NULL)/沒有柱面號相同 else/有柱面號相同的等待進程 min=q->phy_num-h->phy_num;/第一個相同柱面號設為最小值 p=q;/指向最小的節(jié)點，旋轉距離最短的訪問者 if(min<

22、0) min=-min; q=q->next; while(q!=NULL) if(q->cylinder_num=h->cylinder_num)/有柱面號相同 cha=q->phy_num-h->phy_num; if(cha<0) cha=-cha; if(min>cha)/有更小的節(jié)點，旋轉距離最短的訪問者 min=cha; p=q;/指向最小的節(jié)點 q=q->next; /while查找 /else current_process(p);/保留選中的進程 if(direction=1) /啟動磁盤 printf("被選中的等待

23、進程為：n"); printf("n"); out_info(); printf(" 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)/找到要刪

24、除進程的前一個節(jié)點 B=B->next; B->next=p->next;/被選中者退出I/O請求表 /if(q!=NULL)結束 else printf("請求進程表為空,接收請求或退出n"); /電梯調度算法結束void main()/主函數 system("cls"); char go='y' float number; init(); printf(" -*執(zhí)行驅動調度*-n"); printf(" -*當前運行進程為*-n"); out_info(); printf(" upn"); printf(" -*創(chuàng)建I/O請求進程等待表*-n"); create_PCB(); /創(chuàng)建進程鏈表 printf("n"); printf("I/O請求進程等待表為：n"); printf("n"); output(); while(go='y'|go!='n') printf("n&qu