操作系統(tǒng)驅(qū)動調(diào)度數(shù)據(jù)參考

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

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

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

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

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

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

7、號小的訪問請求?否是是置當(dāng)前移臂方向為向里移置當(dāng)前移臂方向為向外移從大于當(dāng)前柱面號的訪問請求中選擇一個最小者從大于當(dāng)前柱面號的訪問請求中選擇一個最小者添加當(dāng)前位置：柱面號；物理記錄號啟動磁盤，被選中者退出“請求i/o表”圖3-3 電梯調(diào)度模擬算法返回五、源程序#includestdio.h #includestdlib.h #includeconio.h #includestring.h #define m 20 typedef struct pcb char procm;/進(jìn)程名 int cylinder_num;/柱面號 int track_num;/磁道號 int phy_num;/物理

8、記錄號 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-phy_num= 0; /模擬記錄當(dāng)前運(yùn)行進(jìn)程void current_process(pcb *q) strcpy(h-proc,q-proc); h

9、-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); p-next=q-next; q-next=p; void out_info() /輸出進(jìn)程的信息 printf(n); printf( 進(jìn)程名 柱面號 磁道號 物理記錄號 方向 n); printf( n); printf( %s t%

10、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)程名柱面號 磁道號 物理記錄號n); if(p=null) printf(-*進(jìn)程表為空,接收請求或按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;

11、int i,n; printf(n); printf(請輸入i/o進(jìn)程表中進(jìn)程等待的個數(shù)：n); printf(n); scanf(%d,&n); printf(請依次輸入進(jìn)程的相關(guān)信息: （用空格分隔）n); printf(n); printf(進(jìn)程名，柱面號，磁道號，物理記錄號n); for(i=1;iproc); 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()

12、pcb *p; int i,n,m; printf(請輸入一個值: n); printf(1. n); printf(0. n); scanf(%d,&i); if(i=1) printf(正在運(yùn)行的進(jìn)程為：n); printf(n); /*if(direction=1) /啟動磁盤 out_info(); printf( upn); printf(n); if(direction=-1) out_info(); printf( downn); printf(n); */ printf(n); printf(接受請求前的等待進(jìn)程表為n); output(); printf(請輸入接受等待進(jìn)程數(shù)

13、量n); scanf(%d,&n); printf(請依次輸入進(jìn)程的信息n); printf(進(jìn)程名，柱面號，磁道號，物理記錄號n); for(m=1;mproc); scanf(%d,&p-cylinder_num); scanf(%d,&p-track_num); scanf(%d,&p-phy_num); p-next=null; insert(p); 網(wǎng)絡(luò)軟硬件printf(接受請求后的等待進(jìn)程表為：n); printf(n); output(); else printf(沒有接受進(jìn)程，繼續(xù)往下運(yùn)行程序n); /電梯調(diào)度算法void lift() int min,cha,max; pc

14、b *p,*q,*b;/p為指要刪除的節(jié)點(diǎn)，q為查找的節(jié)點(diǎn)，b指向要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn) q=head; if(q!=null) while(q!=null)&(q-cylinder_num!=h-cylinder_num)/找到第一個相同的柱面號 q=q-next; if(q=null)/沒有柱面號相同的等待進(jìn)程 q=head; if(direction=1)/當(dāng)前移臂方向up while(q!=null)&(q-cylinder_num cylinder_num) q=q-next; if(q=null)/沒有比當(dāng)前柱面號大的等待進(jìn)程 direction=-1;/置當(dāng)前移臂方向為外移 q=

15、head;/從小于當(dāng)前柱面號的訪問中選擇一個最大的,p指向p=q; max=q-cylinder_num; q=q-next; while(q!=null) if(maxcylinder_num) max=q-cylinder_num; p=q;/p指向最大的節(jié)點(diǎn) q=q-next; else/有大于當(dāng)前柱面號的等待進(jìn)程 min=q-cylinder_num; p=q; q=q-next; while(q!=null)/大于當(dāng)前柱面號并且小于指定最小的節(jié)點(diǎn)時 if(h-cylinder_numcylinder_num)&(q-cylinder_numcylinder_num) min=q-cy

16、linder_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)/沒有比當(dāng)前柱面號小的請求 direction=1; q=head;/從大于當(dāng)前柱面號的訪問中選擇一個最小的,p指向 p=q; min=q-cylinder_num; q=q-next; while(q!=null) if(minq-cylinder_num) min=q-cylinder_num; p=q;/p指向最小的節(jié)點(diǎn) q=q-next; else/有比當(dāng)

17、前柱面號小的請求進(jìn)程 max=q-cylinder_num; p=q; q=q-next; while(q!=null)/從小當(dāng)前柱面號訪問進(jìn)程中選擇一個最大的，用p指向 if(p-cylinder_numcylinder_num&q-cylinder_numcylinder_num) max=q-cylinder_num; p=q;/p指向最大的節(jié)點(diǎn) q=q-next; /else/有比當(dāng)前柱面號小的請求進(jìn)程 /else/當(dāng)前移臂方向向外 /if(q=null)/沒有柱面號相同 else/有柱面號相同的等待進(jìn)程 min=q-phy_num-h-phy_num;/第一個相同柱面號設(shè)為最小值 p

18、=q;/指向最小的節(jié)點(diǎn)，旋轉(zhuǎn)距離最短的訪問者 if(minnext; while(q!=null) if(q-cylinder_num=h-cylinder_num)/有柱面號相同 cha=q-phy_num-h-phy_num; if(chacha)/有更小的節(jié)點(diǎn)，旋轉(zhuǎn)距離最短的訪問者 min=cha; p=q;/指向最小的節(jié)點(diǎn) q=q-next; /while查找 /else current_process(p);/保留選中的進(jìn)程 if(direction=1) /啟動磁盤 printf(被選中的等待進(jìn)程為：n); printf(n); out_info(); printf( upn);

19、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)/找到要刪除進(jìn)程的前一個節(jié)點(diǎn) b=b-next; b-next=p-next;/被選中者退出i/o請求表 /if(q!=null)結(jié)束 else printf(請求進(jìn)程表為空,接收請求或退出n); /電梯調(diào)度算法結(jié)束void main()/主函數(shù) system(cls); char go=y; float number; init(); printf( -*執(zhí)行驅(qū)動調(diào)度*-n); printf( -*當(dāng)前運(yùn)行進(jìn)程為*-n); out_info(); printf( upn); printf( -*創(chuàng)建i/o請求進(jìn)程等待表*-n); create_pcb(); /創(chuàng)建進(jìn)程鏈表 printf(n); printf(i/o請求進(jìn)程等待表為：n); printf(n); output(); while(