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

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

2、實(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)程在訪問某個(gè)磁盤時(shí)，其他想訪問該磁盤的進(jìn)程必須等待，直到磁盤一次工作結(jié)束。當(dāng)有多個(gè)進(jìn)程提出輸入輸出要求而處于等待狀態(tài)時(shí)，可用電梯調(diào)度算法從若干個(gè)等待訪問者 中選擇一個(gè)進(jìn)程，讓它訪問磁盤。選擇訪問者的工作由“驅(qū)動(dòng)調(diào)度”進(jìn)程來(lái)完成。由于磁盤與處理器是可以并行工作的、所以當(dāng)磁盤在作為一個(gè)進(jìn)程服務(wù)時(shí)，占有處理 器的另一進(jìn)程可以提出使用磁盤的要求，也就是說，系統(tǒng)能動(dòng)態(tài)地接收新的輸入輸出請(qǐng)求。為了模擬這種情況，在本實(shí)驗(yàn)中設(shè)置了一個(gè)“接收請(qǐng)求”進(jìn)程。“驅(qū)動(dòng)調(diào)度”進(jìn)程和

3、“接收請(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)度選擇的過程。因而，程序的結(jié)構(gòu)可參考圖31（2）“接收請(qǐng)求”進(jìn)程建立一張“請(qǐng)求I/O”表，指出訪問磁盤的進(jìn)程要求訪問的物理地址，表的格式為：假定某個(gè)磁盤組共有200個(gè)柱面，由外向里順序編號(hào)（0199），每個(gè)柱面上有20個(gè) 磁道，編號(hào)為019，每個(gè)磁道分成8個(gè)物理記錄，編號(hào)07。進(jìn)程訪問磁盤的物理地址 可以用鍵盤輸入的方法模擬得到。圖32是“接收請(qǐng)求”進(jìn)程的模擬算法。在實(shí)際的系統(tǒng)中必須把等待訪問磁盤的進(jìn)程排入等待列隊(duì)，由于本實(shí)驗(yàn)?zāi)M驅(qū)動(dòng)調(diào)

4、 度，為簡(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)有等待訪問磁盤的進(jìn)程時(shí)，按電梯調(diào)度算法從中選擇一個(gè)等待訪問者， 按該進(jìn)程指定的磁盤物理地址啟動(dòng)磁盤為其服務(wù)。對(duì)移動(dòng)臂磁盤來(lái)說，驅(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)相同的訪問請(qǐng)求， 從這些請(qǐng)求中再選擇一個(gè)能使旋轉(zhuǎn)距離最短的等待訪問者。如 果沒有與當(dāng)前柱面號(hào)

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

6、1)程序中使用的數(shù)據(jù)結(jié)構(gòu)及其說明。(2)con st int PCB=100;ylin der != NULL i+)“請(qǐng)(3)(4)(5)cout i pcbspcbs_num.Cylinder pcbspcbs_num.Track pcbspcbs_ num.Record;(9)pcbs_ num+;(10) (11) int Cylinder_e() ylinder =(12)return i;(13)(14)return 0;(15)(16)int Cylinder_near( intcylinder , int record ) ylinder =cylinder )(17)(18)

7、a = pcbsi.Record -record ;(19)if (a0) a = a + 8; (20)if (at)(21)(45)(22)t = a; k = i;(23)(24)(25)(26)return k;(27) (28) int Cylinder_max( int cylinder ) ylinder -cylinder )cylinder )(29)(30)t = abs(pcbsi.Cylinder -cylinder );(31)(32) num =cyli nder + t;yli nder = num &pcbsi.Record t)|(33)(34)t =

8、 pcbsi.Record; a = i;(35)(36)(37)return a;(38) (39) int Cylinder_max1( int cylinder )(40) (41)int t = 199, i, b = 0, c = 0;(42)for (i = 0; ib & pcbsi.Cylinder cylinder )(47)(48)(49)return b;(50)(51)int Cylinder_min( int cylinder ) ylinder -cylinder )t & pcbsi.Cylinder cylinder )(52)(53)t = a

9、bs(pcbsi.Cylinder -cylinder );(54)(55)(56)num = cyli nder - t; t = 8; yli nder = num & pcbsi.Record t)(57)(58)t = pcbsi.Record; a = i;(59)(60)(61)return a; name setfill( ) setw(8) pcbsi.Cylinder setfill( ) setw(8) pcbsi.Track setfill( ) setw(10) pcbsi.Record en dl;(62)(63)(64)void print_scan(boo

10、l x)(65)(66)cout 選中的： endl; cout 進(jìn)程名 “ 柱面號(hào) “ 磁道號(hào) 物理記錄號(hào) 方向 endl; cout setfill( ) setw(6) setfill() setw(8) setfill( ) setw(10) setfill( ) setw(10) setfill( ) setw(6) x endl;(46)b = abs(pcbsi.Cyli nder -cylinder );(67)(68) intSCAN() ylinder = yli nderv(69)(70)way = 0;(71)(72)else way = 1;(73)(74)else(

11、75)(76)if (way = 1)(77)(78)scan = Cylinder_max;/選擇比當(dāng)前柱面號(hào)大的請(qǐng)求中物理塊號(hào)最小的(79)sca n1 = Cyli nder_max1;(80)if (scan = scan1)(81) (82)scan = Cylinder_min;/選擇比當(dāng)前柱面號(hào)小的請(qǐng)求中物理塊號(hào)最大的way = 0;(84)(85)(86)else(87)(88)sca n = Cyli nder_min;(89)if (scan = 0)(83)(90)sea n = Cyli nder_max;(92)way = 1;(93)(94)(95) a = pcbssca n;(96)delete_scan(scan);/ 刪除 pcbsscan(97)print_scan(way);/ 打印(98)return 1;(99)(100) (101) void work() / 初始化(102) (103)float n; char y =y ;while (y =y| y =Y)(104)(105)cout 輸入在0 , 1區(qū)間內(nèi)的一個(gè)隨機(jī)數(shù) n;(107)if (n(108)(109)SCAN(); /驅(qū)動(dòng)調(diào)度(110)(111)el