實驗三___驅(qū)動調(diào)度

1、實驗三 驅(qū)動調(diào)度一、實驗內(nèi)容模擬電梯調(diào)度算法，實現(xiàn)對磁盤的驅(qū)動調(diào)度。二、實驗?zāi)康?磁盤是一種高速、大容量、旋轉(zhuǎn)型、可直接存取的存儲設(shè)備。它作為計算機系統(tǒng)的輔助存儲器，擔負著繁重的輸入輸出任務(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)運行過程。通過實驗使學(xué)生理解和掌握驅(qū)動調(diào)度的職能。三、實驗題目模擬電梯調(diào)度算法，對磁盤

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

3、取決于磁盤的結(jié)束中斷信號和處理器調(diào)度策略。在實驗中可用隨機數(shù)來模擬確定這兩個進程的運行順序，以代替中斷處理和處理器調(diào)度選擇的過程。因而，程序的結(jié)構(gòu)可參考圖31初始化輸入在0，1區(qū)間內(nèi)的一個隨機數(shù)隨機數(shù)>1/2開始驅(qū)動調(diào)度接受請求繼續(xù)？結(jié)束是是否否圖31 程序結(jié)構(gòu)（2）“接收請求”進程建立一張“請求I/O”表，指出訪問磁盤的進程要求訪問的物理地址，表的格式為：進程名柱面號磁道號物理記錄號 假定某個磁盤組共有200個柱面，由外向里順序編號（0199），每個柱面上有20個磁道，編號為019，每個磁道分成8個物理記錄，編號07。進程訪問磁盤的物理地址可以用鍵盤輸入的方法模擬得到。圖32是“接收請

4、求”進程的模擬算法。 開始有請求？輸入：進程名物理地址進程排入等待隊列登記“請求I/O表返回是否 圖 32 “接收請求”模擬算法在實際的系統(tǒng)中必須把等待訪問磁盤的進程排入等待列隊，由于本實驗?zāi)M驅(qū)動調(diào)度，為簡單起見，在實驗中可免去隊列管理部分，故設(shè)計程序時可不考慮“進程排入等待隊列”的工作。（3）“驅(qū)動調(diào)度”進程的功能是查“請求I/O”表，當有等待訪問磁盤的進程時，按電梯調(diào)度算法從中選擇一個等待訪問者，按該進程指定的磁盤物理地址啟動磁盤為其服務(wù)。對移動臂磁盤來說，驅(qū)動調(diào)度分移臂調(diào)度和旋轉(zhuǎn)調(diào)度。電梯調(diào)度算法的調(diào)度策略是與移動臂的移動方向和移動臂的當前位子有關(guān)的，所以每次啟動磁盤時都應(yīng)登記移動臂方

5、向和當前位子。電梯調(diào)度算法是一種簡單而實用的驅(qū)動調(diào)度方法，這種調(diào)度策略總是優(yōu)先選擇與當前柱面號相同的訪問請求，從這些請求中再選擇一個能使旋轉(zhuǎn)距離最短的等待訪問者。如果沒有與當前柱面號相同的訪問請求，則根據(jù)移臂方向來選擇，每次總是沿臂移動方向選擇一個與當前柱面號最近的訪問請求，若沿這個方向沒有訪問請求時，就改變臂的移動方向。這種調(diào)度策略能使移動臂的移動頻率極小，從而提高系統(tǒng)效率。用電梯調(diào)度算法實現(xiàn)驅(qū)動調(diào)度的模擬算法如圖33。（4）圖31中的初始化工作包括，初始化“請求I/O”表，置當前移臂方向為里移；置當前位置為0號柱面，0號物理記錄。程序運行前可假定“請求I/O”表中已經(jīng)有如干個進程等待訪問磁

6、盤。在模擬實驗中，當選中一個進程可以訪問磁盤時，并不實際地啟動磁盤，而用顯示：“請求I/O”表；當前移臂方向；當前柱面號，物理記錄號來代替圖33中的“啟動磁盤”這項工作。置當前移臂方向為向外移置當前移臂方向為向外移從大于當前柱面號的訪問請求中選擇一個最小者從小于當前柱面號的訪問請求中選擇一個最大者登記當前位置；柱面號；物理記錄號；啟動磁盤被選者退出“請求I/O”表返回開 始否否查“請求I/O表”有等待訪問者？返回有與當前柱面號相同的訪問者？是否否否是是是是選擇能使旋轉(zhuǎn)距離最短的訪問者當前移臂方向是向里？有比當前柱面號大的訪問請求？有比當前柱面號小的訪問請求？圖33 電梯調(diào)度模擬算法四、實驗報告

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

8、問磁盤的若干個進程struct Requie_I_O Cur_Location;/當前位置int last;/最后一個等待訪問磁盤的進程的下標六、源代碼#include<iostream>#include<string>#include<ctime>using namespace std;/請求I/O表struct Requie_I_Ostring Pro_Name;/進程名int Cy_Num;/柱面號int Track_Num;/磁道號int Phy_Re_Num;/物理記錄號char *Direction;/方向I_O100, a100;/定義兩個變量

9、數(shù)組，代表等待訪問磁盤的若干個進程struct Requie_I_O Cur_Location;/當前位置int last;/最后一個等待訪問磁盤的進程的下標/初始化請求I/O表void Init_I_O()Cur_Location.Cy_Num = 0;/當前柱面號Cur_Location.Phy_Re_Num = 0;/當前物理記錄號Cur_Location.Direction = "up"/當前方向/已有的若干個（5個）等待訪問磁盤的進程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;/接收請求void Accept_Request()char ans;cout << "請問是否有請求？(Y/N)n"cin >> ans;if (ans = 'Y')la

12、st+;cout << "請輸入進程名物理地址:進程名、柱面號（0-199）、磁道號（0-99）、物理記錄號（0-7）n"cin >> I_Olast.Pro_Name >> I_Olast.Cy_Num >> I_Olast.Track_Num >> I_Olast.Phy_Re_Num;/有請求所以登記請求I/O表/驅(qū)動調(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 << "無等待訪問磁盤的進程！" << endl;/無等待訪問所以返回else int count0 = 0;/與當前柱面號相同的訪問進程數(shù)for (int i = 0; i < last + 1; i+)if (I_Oi.Cy_Num = Cur_Location.Cy_Num)/判斷是否有與當前柱面號相同的訪問者acount0 = I_Oi; count0+;if (-count0 > 0)/有與當前柱面號相同的訪問者0 = 0;/未完成/當前移

14、臂方向為向里else if (string(Cur_Location.Direction) = string("up")int flag=0,m,n=0,temp;/flag=1的時候判斷是否滿足條件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;/將第一個滿足條件的值保存在tempif (flag = 1)/有比當前柱面號大的訪問者if (last = 0) m = n; /當只有一個

15、元素時，該元素就是我么要找尋的else/在大于當前柱面號的訪問者中選擇一個最小者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; /登記當前位置，柱面號、物理記錄號Cur_Location.Cy_Num = I_Om.Cy_Num; Cur_Location.Phy_Re_Num = I_Om.Phy_Re_Num;/啟動磁盤cout << "請求I/O表n&qu

16、ot;cout << "當前移臂方向為：" << Cur_Location.Direction << endl;cout << "當前柱面號為：" << Cur_Location.Cy_Num << endl;cout << "當前物理記錄號為：" << Cur_Location.Phy_Re_Num << endl;for (int i = m; i < last + 1; i+)I_Oi = I_Oi + 1;/被選者

17、退出last-;/數(shù)組元素減一else/沒有比當前柱面號大的訪問請求Cur_Location.Direction = "down"int temp = I_O0.Cy_Num, p = 0;for (int j = 1; j < last + 1; j+)/從小于當前柱面號的訪問請求中選擇一個最大者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、< "請求I/O表n"cout << "當前移臂方向為：" << Cur_Location.Direction << endl;cout << "當前柱面號為：" << Cur_Location.Cy_Num << endl;cout << "當前物理記錄號為：" << Cur_Location.Phy_Re_Num << endl;for (int i = p; i < last + 1; i+

19、)I_Oi = I_Oi + 1;last-;else/當前移臂方向為向外int 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)/有比當前柱面號小的訪問請求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 << "請求I/O表n"cout << "當前移臂方向為：" << Cur_Location.Direction << endl;cout << "當前柱面號為：" << Cur_Location.Cy_Num << endl

21、;cout << "當前物理記錄號為：" << Cur_Location.Phy_Re_Num << endl;for (int i = m; i < last + 1; i+)I_Oi = I_Oi + 1;last-;else/沒有比當前柱面號小的訪問請求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 << "請求I/O表n"cout << "當前移臂方向為：" << Cur_Location.Direction << endl;cout << "當前柱面號為：" << Cur_Location.Cy_Num << endl;cout << "當前物理記錄號為：" << 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類型的隨機數(shù)char ans;cout << "-START-n"Init_I_O();/