實(shí)驗(yàn)三___驅(qū)動(dòng)調(diào)度

1、實(shí)驗(yàn)三 驅(qū)動(dòng)調(diào)度一、實(shí)驗(yàn)內(nèi)容模擬電梯調(diào)度算法，實(shí)現(xiàn)對(duì)磁盤(pán)的驅(qū)動(dòng)調(diào)度。二、實(shí)驗(yàn)?zāi)康?磁盤(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)度程序，觀察驅(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)度算法，對(duì)磁盤(pán)

2、進(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)程能否占有處理器運(yùn)行，

3、取決于磁盤(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初始化輸入在0，1區(qū)間內(nèi)的一個(gè)隨機(jī)數(shù)隨機(jī)數(shù)>1/2開(kāi)始驅(qū)動(dòng)調(diào)度接受請(qǐng)求繼續(xù)？結(jié)束是是否否圖31 程序結(jié)構(gòu)（2）“接收請(qǐng)求”進(jìn)程建立一張“請(qǐng)求I/O”表，指出訪(fǎng)問(wèn)磁盤(pán)的進(jìn)程要求訪(fǎng)問(wèn)的物理地址，表的格式為：進(jìn)程名柱面號(hào)磁道號(hào)物理記錄號(hào) 假定某個(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)

4、求”進(jìn)程的模擬算法。 開(kāi)始有請(qǐng)求？輸入：進(jìn)程名物理地址進(jìn)程排入等待隊(duì)列登記“請(qǐng)求I/O表返回是否 圖 32 “接收請(qǐng)求”模擬算法在實(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)中可免去隊(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)臂方

5、向和當(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ù)移臂方向來(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)磁

6、盤(pán)。在模擬實(shí)驗(yàn)中，當(dāng)選中一個(gè)進(jìn)程可以訪(fǎng)問(wèn)磁盤(pán)時(shí)，并不實(shí)際地啟動(dòng)磁盤(pán)，而用顯示：“請(qǐng)求I/O”表；當(dāng)前移臂方向；當(dāng)前柱面號(hào)，物理記錄號(hào)來(lái)代替圖33中的“啟動(dòng)磁盤(pán)”這項(xiàng)工作。置當(dāng)前移臂方向?yàn)橄蛲庖浦卯?dāng)前移臂方向?yàn)橄蛲庖茝拇笥诋?dāng)前柱面號(hào)的訪(fǎng)問(wèn)請(qǐng)求中選擇一個(gè)最小者從小于當(dāng)前柱面號(hào)的訪(fǎng)問(wèn)請(qǐng)求中選擇一個(gè)最大者登記當(dāng)前位置；柱面號(hào)；物理記錄號(hào)；啟動(dòng)磁盤(pán)被選者退出“請(qǐng)求I/O”表返回開(kāi) 始否否查“請(qǐng)求I/O表”有等待訪(fǎng)問(wèn)者？返回有與當(dāng)前柱面號(hào)相同的訪(fǎng)問(wèn)者？是否否否是是是是選擇能使旋轉(zhuǎn)距離最短的訪(fǎng)問(wèn)者當(dāng)前移臂方向是向里？有比當(dāng)前柱面號(hào)大的訪(fǎng)問(wèn)請(qǐng)求？有比當(dāng)前柱面號(hào)小的訪(fǎng)問(wèn)請(qǐng)求？圖33 電梯調(diào)度模擬算法四、實(shí)驗(yàn)報(bào)告

7、（1）實(shí)驗(yàn)題目。（2）程序中使用的數(shù)據(jù)結(jié)構(gòu)及其說(shuō)明。（3）打印一份源程序并附上注釋。（4）打印驅(qū)動(dòng)調(diào)度進(jìn)程每次選擇訪(fǎng)問(wèn)請(qǐng)求前的“請(qǐng)求I/O”表以及每次選中的進(jìn)程名、訪(fǎng)問(wèn)的柱面號(hào)、物理記錄號(hào)和當(dāng)前移臂方向（用up代表里移，down代表外移。打印格式為：“請(qǐng)求I/O”表進(jìn)程名 柱面號(hào) 物理記錄號(hào) 方向五、數(shù)據(jù)結(jié)構(gòu)/請(qǐng)求I/O表struct Requie_I_Ostring Pro_Name;/進(jìn)程名int Cy_Num;/柱面號(hào)int Track_Num;/磁道號(hào)int Phy_Re_Num;/物理記錄號(hào)char *Direction;/方向I_O100, a100;/定義兩個(gè)變量數(shù)組，代表等待訪(fǎng)

8、問(wèn)磁盤(pán)的若干個(gè)進(jìn)程struct Requie_I_O Cur_Location;/當(dāng)前位置int last;/最后一個(gè)等待訪(fǎng)問(wèn)磁盤(pán)的進(jìn)程的下標(biāo)六、源代碼#include<iostream>#include<string>#include<ctime>using namespace std;/請(qǐng)求I/O表struct Requie_I_Ostring Pro_Name;/進(jìn)程名int Cy_Num;/柱面號(hào)int Track_Num;/磁道號(hào)int Phy_Re_Num;/物理記錄號(hào)char *Direction;/方向I_O100, a100;/定義兩個(gè)變量

9、數(shù)組，代表等待訪(fǎng)問(wèn)磁盤(pán)的若干個(gè)進(jìn)程struct Requie_I_O Cur_Location;/當(dāng)前位置int last;/最后一個(gè)等待訪(fǎng)問(wèn)磁盤(pán)的進(jìn)程的下標(biāo)/初始化請(qǐng)求I/O表void Init_I_O()Cur_Location.Cy_Num = 0;/當(dāng)前柱面號(hào)Cur_Location.Phy_Re_Num = 0;/當(dāng)前物理記錄號(hào)Cur_Location.Direction = "up"/當(dāng)前方向/已有的若干個(gè)（5個(gè)）等待訪(fǎng)問(wèn)磁盤(pán)的進(jìn)程I_O0.Pro_Name = "P0" I_O0.Cy_Num = 145; I_O0.Track_Num =

10、 36; I_O0.Phy_Re_Num = 6;I_O1.Pro_Name = "P1" I_O1.Cy_Num = 126; I_O1.Track_Num = 97; I_O1.Phy_Re_Num = 1;I_O2.Pro_Name = "P2" I_O2.Cy_Num = 67; I_O2.Track_Num = 23; I_O2.Phy_Re_Num = 5;I_O3.Pro_Name = "P3" I_O3.Cy_Num = 99; I_O3.Track_Num = 0; I_O3.Phy_Re_Num = 4;I_O4.

11、Pro_Name = "P4" I_O4.Cy_Num = 3; I_O4.Track_Num = 63; I_O4.Phy_Re_Num = 7;I_O5.Pro_Name = "P5" I_O5.Cy_Num = 100; I_O5.Track_Num = 19; I_O5.Phy_Re_Num = 2;last = 5;/接收請(qǐng)求void Accept_Request()char ans;cout << "請(qǐng)問(wèn)是否有請(qǐng)求？(Y/N)n"cin >> ans;if (ans = 'Y')la

12、st+;cout << "請(qǐng)輸入進(jìn)程名物理地址:進(jìn)程名、柱面號(hào)（0-199）、磁道號(hào)（0-99）、物理記錄號(hào)（0-7）n"cin >> I_Olast.Pro_Name >> I_Olast.Cy_Num >> I_Olast.Track_Num >> I_Olast.Phy_Re_Num;/有請(qǐng)求所以登記請(qǐng)求I/O表/驅(qū)動(dòng)調(diào)度void Driven_Scheduling()Cur_Location.Cy_Num = 160;Cur_Location.Phy_Re_Num = 13;Cur_Location.Dir

13、ection = "up"if (last < 0) cout << "無(wú)等待訪(fǎng)問(wèn)磁盤(pán)的進(jìn)程！" << endl;/無(wú)等待訪(fǎng)問(wèn)所以返回else int count0 = 0;/與當(dāng)前柱面號(hào)相同的訪(fǎng)問(wèn)進(jìn)程數(shù)for (int i = 0; i < last + 1; i+)if (I_Oi.Cy_Num = Cur_Location.Cy_Num)/判斷是否有與當(dāng)前柱面號(hào)相同的訪(fǎng)問(wèn)者acount0 = I_Oi; count0+;if (-count0 > 0)/有與當(dāng)前柱面號(hào)相同的訪(fǎng)問(wèn)者0 = 0;/未完成/當(dāng)前移

14、臂方向?yàn)橄蚶飁lse if (string(Cur_Location.Direction) = string("up")int flag=0,m,n=0,temp;/flag=1的時(shí)候判斷是否滿(mǎn)足條件for (int i = 0; i < last + 1; i+)if (I_Oi.Cy_Num > Cur_Location.Cy_Num)flag = 1; n = i; break;temp = I_On.Cy_Num;/將第一個(gè)滿(mǎn)足條件的值保存在tempif (flag = 1)/有比當(dāng)前柱面號(hào)大的訪(fǎng)問(wèn)者if (last = 0) m = n; /當(dāng)只有一個(gè)

15、元素時(shí)，該元素就是我么要找尋的else/在大于當(dāng)前柱面號(hào)的訪(fǎng)問(wèn)者中選擇一個(gè)最小者for (int i = n; i < last + 1; i+)if (I_Oi.Cy_Num > Cur_Location.Cy_Num)if (temp > I_Oi.Cy_Num) temp = I_Oi.Cy_Num; m = i; /登記當(dāng)前位置，柱面號(hào)、物理記錄號(hào)Cur_Location.Cy_Num = I_Om.Cy_Num; Cur_Location.Phy_Re_Num = I_Om.Phy_Re_Num;/啟動(dòng)磁盤(pán)cout << "請(qǐng)求I/O表n&qu

16、ot;cout << "當(dāng)前移臂方向?yàn)椋?quot; << Cur_Location.Direction << endl;cout << "當(dāng)前柱面號(hào)為：" << Cur_Location.Cy_Num << endl;cout << "當(dāng)前物理記錄號(hào)為：" << Cur_Location.Phy_Re_Num << endl;for (int i = m; i < last + 1; i+)I_Oi = I_Oi + 1;/被選者

17、退出last-;/數(shù)組元素減一else/沒(méi)有比當(dāng)前柱面號(hào)大的訪(fǎng)問(wèn)請(qǐng)求Cur_Location.Direction = "down"int temp = I_O0.Cy_Num, p = 0;for (int j = 1; j < last + 1; j+)/從小于當(dāng)前柱面號(hào)的訪(fǎng)問(wèn)請(qǐng)求中選擇一個(gè)最大者if (temp < I_Oj.Cy_Num)temp = I_Oj.Cy_Num;p = j;Cur_Location.Cy_Num = I_Op.Cy_Num; Cur_Location.Phy_Re_Num = I_Op.Phy_Re_Num;cout <

18、< "請(qǐng)求I/O表n"cout << "當(dāng)前移臂方向?yàn)椋?quot; << Cur_Location.Direction << endl;cout << "當(dāng)前柱面號(hào)為：" << Cur_Location.Cy_Num << endl;cout << "當(dāng)前物理記錄號(hào)為：" << Cur_Location.Phy_Re_Num << endl;for (int i = p; i < last + 1; i+

19、)I_Oi = I_Oi + 1;last-;else/當(dāng)前移臂方向?yàn)橄蛲鈏nt flag=0, m, n;for (int i = 0; i < last + 1; i+)if (I_Oi.Cy_Num < Cur_Location.Cy_Num)flag = 1; n = i;break;if (flag=1)/有比當(dāng)前柱面號(hào)小的訪(fǎng)問(wèn)請(qǐng)求int temp = I_On.Cy_Num;for (int i = n ; i < last + 1;i+)if (I_Oi.Cy_Num < Cur_Location.Cy_Num)if (temp <= I_Oi.Cy

20、_Num) temp = I_Oi.Cy_Num; m = i; Cur_Location.Cy_Num = I_Om.Cy_Num; Cur_Location.Phy_Re_Num = I_Om.Phy_Re_Num;cout << "請(qǐng)求I/O表n"cout << "當(dāng)前移臂方向?yàn)椋?quot; << Cur_Location.Direction << endl;cout << "當(dāng)前柱面號(hào)為：" << Cur_Location.Cy_Num << endl

21、;cout << "當(dāng)前物理記錄號(hào)為：" << Cur_Location.Phy_Re_Num << endl;for (int i = m; i < last + 1; i+)I_Oi = I_Oi + 1;last-;else/沒(méi)有比當(dāng)前柱面號(hào)小的訪(fǎng)問(wèn)請(qǐng)求Cur_Location.Direction = "up"int temp = I_O0.Cy_Num, p;if (last = 0) p = last; elsefor (int i = 1; i < last + 1; i+)if (temp &

22、gt; I_Oi.Cy_Num) temp = I_Oi.Cy_Num; p = i; Cur_Location.Cy_Num = I_Op.Cy_Num; Cur_Location.Phy_Re_Num = I_Op.Phy_Re_Num;cout << "請(qǐng)求I/O表n"cout << "當(dāng)前移臂方向?yàn)椋?quot; << Cur_Location.Direction << endl;cout << "當(dāng)前柱面號(hào)為：" << Cur_Location.Cy_Num << endl;cout << "當(dāng)前物理記錄號(hào)為：" << Cur_Location.Phy_Re_Num << endl;for (int i = p; i < last + 1; i+)I_Oi = I_Oi + 1;last-;void main()double number;/double類(lèi)型的隨機(jī)數(shù)char ans;cout << "-START-n"Init_I_O();/