模擬電梯調度算法實現對磁盤的驅動調度

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

2、，對磁盤進行移臂和旋轉調度。提示：（1）磁盤是可供多個進程共享的存儲設備，但一個磁盤每時刻只能為一個進程服務。當有進程在訪問某個磁盤時，其他想訪問該磁盤的進程必須等待，直到磁盤一次工作結束。 當有多個進程提出輸入輸出要求而處于等待狀態(tài)時，可用電梯調度算法從若干個等待訪問者 中選擇一個進程，讓它訪問磁盤。選擇訪問者的工作由“驅動調度”進程來完成。由于磁盤與處理器是可以并行工作的、所以當磁盤在作為一個進程服務時，占有處理 器的另一進程可以提出使用磁盤的要求，也就是說，系統(tǒng)能動態(tài)地接收新的輸入輸出請求。為了模擬這種情況，在本實驗中設置了一個“接收請求”進程。驅動調度”進程和“接收請求”進程能否占有處

3、理器運行，取決于磁盤的結束中斷信 號和處理器調度策略。在實驗中可用隨機數來模擬確定這兩個進程的運行順序，以代替中斷四、處理和處理器調度選擇的過程。因而，程序的結構可參考圖31（2）“接收請求”進程建立一張“請求I/O”表，指出訪問磁盤的進程要求訪問的物理地址，表的格式為：假定某個磁盤組共有200個柱面，由外向里順序編號（0199），每個柱面上有20個 磁道，編號為019，每個磁道分成8個物理記錄，編號07。進程訪問磁盤的物理地址 可以用鍵盤輸入的方法模擬得到。圖32是“接收請求”進程的模擬算法。 在實際的系統(tǒng)中必須把等待訪問磁盤的進程排入等待列隊，由于本實驗模擬驅動調 度，為簡單起見，在實驗中

4、可免去隊列管理部分，故設計程序時可不考慮“進程排入等待隊 列”的工作。（3）“驅動調度”進程的功能是查“請求I/O”表，當有等待訪問磁盤的進程時，按電梯調度算法從中選擇一個等待訪問者，按該進程指定的磁盤物理地址啟動磁盤為其服務。 對移動臂磁盤來說，驅動調度分移臂調度和旋轉調度。電梯調度算法的調度策略是與 移動臂的移動方向和移動臂的當前位子有關的，所以每次啟動磁盤時都應登記移動臂方向和 當前位子。電梯調度算法是一種簡單而實用的驅動調度方法，這種調度策略總是優(yōu)先選擇與 當前柱面號相同的訪問請求，從這些請求中再選擇一個能使旋轉距離最短的等待訪問者。如 果沒有與當前柱面號相同的訪問請求，則根據移臂方向

5、來選擇，每次總是沿臂移動方向選擇 一個與當前柱面號最近的訪問請求，若沿這個方向沒有訪問請求時，就改變臂的移動方向。 這種調度策略能使移動臂的移動頻率極小，從而提高系統(tǒng)效率。用電梯調度算法實現驅動調 度的模擬算法如圖33。（4）圖31中的初始化工作包括，初始化“請求I/O”表，置當前移臂方向為里移； 置當前位置為0號柱面，0號物理記錄。程序運行前可假定“請求I/O”表中已經有如干個 進程等待訪問磁盤。在模擬實驗中，當選中一個進程可以訪問磁盤時，并不實際地啟動磁盤，而用顯示:求I/O”表；當前移臂方向；當前柱面號，物理記錄號來代替圖3-3中的“啟動磁盤”這項工作。(1)程序中使用的數據結構及其說明

6、。con st int PCB=100; /定義100個進程int pcbs_num=0; /記錄當前io表的進程個數typedef struct process /請求io表“請char pn ame10; /進程名int Cyli nder; /柱面號int Track; /磁道號int Record; /物理記錄號int Way;PROCESS;PROCESS pcbsPCB;PROCESS a; /記錄當前位置(柱面號、物理記錄號)采用帶頭節(jié)點的循環(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 個進程(10)int pcbs_num = 0;/記錄當前 io 表的進程個數(35) (11)typedef struct process / 請求 io 表（(13)char pname10;/ 進程名(14)int Cylinder; / 柱面號(15)int Track;/ 磁道號（int Record; /物理記錄號(17)int Way;(18) PROCESS(19) PROCESpbbsPCB;(20) PROCESS(21) void in it a()/

8、設置當前位置(22) (23)a.Cyli nder = 4;(24)a.Track = 0;(25)a.Record = 0;(26) (27) int count_PN()/記錄進程總數(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 接受請求模擬算法(37) (38)cout 輸入進程名和物理地址(柱面號，磁道號， 物理記錄號)“ pcbspcbs_ num.p name pcbspcbs_ num.Cyli

9、nder pcbspcbs_ num.Track pcbspcbs_ num.Record;(40)pcbs_ num+;(41) (42) intCylinder_e()/判斷柱面號相等(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 ) /選擇當前柱面號的訪問者中物理塊號最近的(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 )/選擇比當前柱面號大的請求中柱面號最小的(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;/選擇的柱面號(78)t = 8;/物理塊號最大相差 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 )/選擇比當前柱面號小的請求中柱面號最大的(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;/返回柱面號小的請求中柱面號最大的下標(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()/ 打印請求 io 表(125) (126)cout 輸岀 請求 i/o 表： endl;(127)cout 進程名“ “ 柱面號 “ 磁道號 物理記錄號 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)/物理塊號相差最大為 7(132) (133)void print_scan( bool x)(134) (135)cout 選中的：“ endl; cout 進程名“ 柱面號“ “ 磁道號 物理記錄號 方向 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()/驅動調度電梯調度模擬算法(138) (139)prin t_io();/打印 io 表(140)int scan;(141)int scan1; /scan 為選擇的進程的編號 |(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 無等待訪問者 endl;return 0(150)(151)else(152)(154)(153)if (pcbsCylinder_e().Cylinder = a.Cylinder)/選擇能使旋轉距離最短的訪問者(155)scan = Cylinder_near(a.Cylinder,a.Record); /選擇當前柱面號的訪冋者中最近的(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);/選擇比當前柱面號大的請求中物理塊號最小的(167)sca n1 = Cyli nder_max1(a.Cyli nder);(168)if (scan = scan1)(169)(170)sca n = Cyli nder_ min( a.Cylinder);/選擇比當前柱面號小的請求中物理塊號最大的(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