模擬電梯調(diào)度算法實(shí)現(xiàn)對(duì)磁盤(pán)的驅(qū)動(dòng)調(diào)度

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

2、，對(duì)磁盤(pán)進(jìn)行移臂和旋轉(zhuǎn)調(diào)度。提示：（1）磁盤(pán)是可供多個(gè)進(jìn)程共享的存儲(chǔ)設(shè)備，但一個(gè)磁盤(pán)每時(shí)刻只能為一個(gè)進(jìn)程服務(wù)。當(dāng)有進(jìn)程在訪(fǎng)問(wèn)某個(gè)磁盤(pán)時(shí)，其他想訪(fǎng)問(wèn)該磁盤(pán)的進(jìn)程必須等待，直到磁盤(pán)一次工作結(jié)束。 當(dāng)有多個(gè)進(jìn)程提出輸入輸出要求而處于等待狀態(tài)時(shí)，可用電梯調(diào)度算法從若干個(gè)等待訪(fǎng)問(wèn)者 中選擇一個(gè)進(jìn)程，讓它訪(fǎng)問(wèn)磁盤(pán)。選擇訪(fǎng)問(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)求。為了模擬這種情況，在本實(shí)驗(yàn)中設(shè)置了一個(gè)“接收請(qǐng)求”進(jìn)程。驅(qū)動(dòng)調(diào)度”進(jìn)程和“接收請(qǐng)求”進(jìn)程能否占有處

3、理器運(yùn)行，取決于磁盤(pá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”表，指出訪(fǎng)問(wèn)磁盤(pán)的進(jìn)程要求訪(fǎng)問(wèn)的物理地址，表的格式為：假定某個(gè)磁盤(pán)組共有200個(gè)柱面，由外向里順序編號(hào)（0199），每個(gè)柱面上有20個(gè) 磁道，編號(hào)為019，每個(gè)磁道分成8個(gè)物理記錄，編號(hào)07。進(jìn)程訪(fǎng)問(wèn)磁盤(pán)的物理地址 可以用鍵盤(pán)輸入的方法模擬得到。圖32是“接收請(qǐng)求”進(jìn)程的模擬算法。 在實(shí)際的系統(tǒng)中必須把等待訪(fǎng)問(wèn)磁盤(pán)的進(jìn)程排入等待列隊(duì)，由于本實(shí)驗(yàn)?zāi)M驅(qū)動(dòng)調(diào) 度，為簡(jiǎn)單起見(jiàn)，在實(shí)驗(yàn)中

4、可免去隊(duì)列管理部分，故設(shè)計(jì)程序時(shí)可不考慮“進(jìn)程排入等待隊(duì) 列”的工作。（3）“驅(qū)動(dòng)調(diào)度”進(jìn)程的功能是查“請(qǐng)求I/O”表，當(dāng)有等待訪(fǎng)問(wèn)磁盤(pán)的進(jìn)程時(shí)，按電梯調(diào)度算法從中選擇一個(gè)等待訪(fǎng)問(wèn)者，按該進(jìn)程指定的磁盤(pán)物理地址啟動(dòng)磁盤(pán)為其服務(wù)。 對(duì)移動(dòng)臂磁盤(pán)來(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)磁盤(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)相同的訪(fǎng)問(wèn)請(qǐng)求，從這些請(qǐng)求中再選擇一個(gè)能使旋轉(zhuǎn)距離最短的等待訪(fǎng)問(wèn)者。如 果沒(méi)有與當(dāng)前柱面號(hào)相同的訪(fǎng)問(wèn)請(qǐng)求，則根據(jù)移臂方向

5、來(lái)選擇，每次總是沿臂移動(dòng)方向選擇 一個(gè)與當(dāng)前柱面號(hào)最近的訪(fǎng)問(wèn)請(qǐng)求，若沿這個(gè)方向沒(méi)有訪(fǎng)問(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。（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)程等待訪(fǎng)問(wèn)磁盤(pán)。在模擬實(shí)驗(yàn)中，當(dāng)選中一個(gè)進(jìn)程可以訪(fǎng)問(wèn)磁盤(pán)時(shí)，并不實(shí)際地啟動(dòng)磁盤(pán)，而用顯示:求I/O”表；當(dāng)前移臂方向；當(dāng)前柱面號(hào)，物理記錄號(hào)來(lái)代替圖3-3中的“啟動(dòng)磁盤(pán)”這項(xiàng)工作。(1)程序中使用的數(shù)據(jù)結(jié)構(gòu)及其說(shuō)明

6、。con st int PCB=100; /定義100個(gè)進(jìn)程int pcbs_num=0; /記錄當(dāng)前io表的進(jìn)程個(gè)數(shù)typedef struct process /請(qǐng)求io表“請(qǐng)char pn ame10; /進(jìn)程名int Cyli nder; /柱面號(hào)int Track; /磁道號(hào)int Record; /物理記錄號(hào)int Way;PROCESS;PROCESS pcbsPCB;PROCESS a; /記錄當(dāng)前位置(柱面號(hào)、物理記錄號(hào))采用帶頭節(jié)點(diǎn)的循環(huán)鏈表存(2)打印一份源程序并附上注釋。(3) #i nclude(4) #i nclude(5) #i nclude#i nclude#i

7、n clude(8)using namespacestd;(9)const int PCB = 100;/ 定義 100 個(gè)進(jìn)程(10)int pcbs_num = 0;/記錄當(dāng)前 io 表的進(jìn)程個(gè)數(shù)(35) (11)typedef struct process / 請(qǐng)求 io 表（(13)char pname10;/ 進(jìn)程名(14)int Cylinder; / 柱面號(hào)(15)int Track;/ 磁道號(hào)（int Record; /物理記錄號(hào)(17)int Way;(18) PROCESS(19) PROCESpbbsPCB;(20) PROCESS(21) void in it a()/

8、設(shè)置當(dāng)前位置(22) (23)a.Cyli nder = 4;(24)a.Track = 0;(25)a.Record = 0;(26) (27) int count_PN()/記錄進(jìn)程總數(shù)(28) (29)int i;(30)for (i = 0; pcbsi.Cylinder !=NULL i+)(31)(32)(33)cout i en dl;(34)return i;(36) void accept。 II 接受請(qǐng)求模擬算法(37) (38)cout 輸入進(jìn)程名和物理地址(柱面號(hào)，磁道號(hào)， 物理記錄號(hào))“ pcbspcbs_ num.p name pcbspcbs_ num.Cyli

9、nder pcbspcbs_ num.Track pcbspcbs_ num.Record;(40)pcbs_ num+;(41) (42) intCylinder_e()/判斷柱面號(hào)相等(43) (44)for (int i = 0; ipcbs_num; i+)(45)(46)if (pcbsi.Cylinder = a.Cylinder)(47)return i;(48)(49)return 0;(50) (51) intCylinder_near(int cylinder , int record ) /選擇當(dāng)前柱面號(hào)的訪(fǎng)問(wèn)者中物理塊號(hào)最近的(52) (53)int t = 8, a,

10、 k;(54)for (int i = 0; ipcbs_num; i+)(55)(56)if (pcbsi.Cylinder =cylinder )(57)(58)a = pcbsi.Record -record ;(59)if (a0) a = a + 8; (60)if (at)(61)(62)t = a; k = i;(63)(64)(65)(66)return k;(67) (68) intCylinder_max( int cylinder )/選擇比當(dāng)前柱面號(hào)大的請(qǐng)求中柱面號(hào)最小的(69) (70)int num, t = 199, i, a = 0, b = 0;|(71)fo

11、r (i = 0; i pcbs_ num; i+)(72)(73)if (abs(pcbsi.Cylinder -cylinder )cylinder )(74)(75)t = abs(pcbsi.Cylinder -cylinder );(76)(77) num =cylinder + t;/選擇的柱面號(hào)(78)t = 8;/物理塊號(hào)最大相差 7(79)for (i = 0; ipcbs_ num; i+)(80)(81)if (pcbsi.Cylinder = num &pcbsi.Record t)(82)t = pcbsi.Record; a = i;(83)(84)(85)(86)

12、return a;(87) (88) intCylinder_max1( int cylinder )(89) (90)int t = 199, i, b = 0, c = 0;(91)for (i = 0; ib & pcbsi.Cylinder cyli nder(94)(95)b = abs(pcbsi.Cyli nder -cylinder );(96)(97)(98)return b;(99) (100) int Cylinder_min( int cylinder )/選擇比當(dāng)前柱面號(hào)小的請(qǐng)求中柱面號(hào)最大的(101) (102)int num, t = 199, i, a = 0;

13、for (i = 0; i pcbs_num; i+)(103)(104)if (abs(pcbsi.Cylinder -cylinder )t & pcbsi.Cylinder cylinder )(105)(106)t = abs(pcbsi.Cyli nder -cylinder );(107)(84)(108)(154)(109)num = cyli nder - t; t = 8;(110)for (i = 0; i pcbs_num; i+)(111)(112)if(pcbsi.Cylinder = num & pcbsi.Record t)(113)(114)t = pcbsi.

14、Record; a = i;(115)(116)(117)return a;/返回柱面號(hào)小的請(qǐng)求中柱面號(hào)最大的下標(biāo)(118) (119) void delete_scan( int x)(120) (121)for (int i = x; ipcbs_num; i+)(122)pcbsi = pcbsi + 1; pcbs_ num-;(123) (124)void print_io()/ 打印請(qǐng)求 io 表(125) (126)cout 輸岀 請(qǐng)求 i/o 表： endl;(127)cout 進(jìn)程名“ “ 柱面號(hào) “ 磁道號(hào) 物理記錄號(hào) endl;(128)for (int i = 0; i

15、pcbs_num; i+)(129)(130)cout setfill( ) setw(6) pcbsi.pname setfill( ) setw(8) pcbsi.Cylinder setfill( ) setw(8) pcbsi.Track setfill( ) setw(10) pcbsi.Record en dl;(131)/物理塊號(hào)相差最大為 7(132) (133)void print_scan( bool x)(134) (135)cout 選中的：“ endl; cout 進(jìn)程名“ 柱面號(hào)“ “ 磁道號(hào) 物理記錄號(hào) 方向 endl; cout setfill( ) setw(

16、6) a.pname setfill( ) setw(8) a.Cylinder setfill() setw(10) a.Track setfill() setw(10) a.Record setfill() setw(6) x en dl;(136) (137) int SCAN()/驅(qū)動(dòng)調(diào)度電梯調(diào)度模擬算法(138) (139)prin t_io();/打印 io 表(140)int scan;(141)int scan1; /scan 為選擇的進(jìn)程的編號(hào) |(142)bool way = 1;/ 方向 O=out 1=in |(143)if (a.Cylinder =：=NULL(14

17、4)(145)ini t_a();(146)(147)if (pcbs_num = =0)(148)(149)cout 無(wú)等待訪(fǎng)問(wèn)者 endl;return 0(150)(151)else(152)(154)(153)if (pcbsCylinder_e().Cylinder = a.Cylinder)/選擇能使旋轉(zhuǎn)距離最短的訪(fǎng)問(wèn)者(155)scan = Cylinder_near(a.Cylinder,a.Record); /選擇當(dāng)前柱面號(hào)的訪(fǎng)冋者中最近的(156)if (pcbsscan.Cylinderva.Cylinder)(157)(158)way = 0;(159)(160)els

18、e way = 1;(161)(162)else(163)(164)if (way = 1)(165)(166)sca n = Cyli nder_max(a.Cyli nder);/選擇比當(dāng)前柱面號(hào)大的請(qǐng)求中物理塊號(hào)最小的(167)sca n1 = Cyli nder_max1(a.Cyli nder);(168)if (scan = scan1)(169)(170)sca n = Cyli nder_ min( a.Cylinder);/選擇比當(dāng)前柱面號(hào)小的請(qǐng)求中物理塊號(hào)最大的(171)way = 0;(172)(173)(174)else(175)(176)sca n = Cyli nder_ min( a.Cyli nder);(177)if (scan = 0)(178)(179)(180)sea n = Cyli nder_max(a.Cyli nder);way = 1;(181)(182)(183) a = pcbssca n;(184)delete_sca n( sea n);/ 刪除 pcbsscan(185)prin t_sca n( way);/打印(186)return 1;(187)(188) (189) void work() /初始化(190) (191)float n; c