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

1、操作系統(tǒng)實(shí)驗(yàn)（第三次） 一、實(shí)驗(yàn)內(nèi)容模擬電梯調(diào)度算法，實(shí)現(xiàn)對磁盤的驅(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è)要求訪問磁盤的輸入輸出請求等待處理。系統(tǒng)可采用一種策略，盡可能按最佳次序執(zhí)行要求訪問磁盤的諸輸入輸出請求。這就叫驅(qū)動(dòng)調(diào)度，使用的算法稱為驅(qū)動(dòng)調(diào)度算法。驅(qū)動(dòng)調(diào)度能降低為若干個(gè)輸入輸出請求服務(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)度的職能。3、 實(shí)驗(yàn)題目模擬電梯調(diào)度算法

2、，對磁盤進(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)程來完成。由于磁盤與處理器是可以并行工作的、所以當(dāng)磁盤在作為一個(gè)進(jìn)程服務(wù)時(shí)，占有處理器的另一進(jìn)程可以提出使用磁盤的要求，也就是說，系統(tǒng)能動(dòng)態(tài)地接收新的輸入輸出請求。為了模擬這種情況，在本實(shí)驗(yàn)中設(shè)置了一個(gè)“接收請求”進(jìn)程?！膀?qū)動(dòng)調(diào)度”進(jìn)程和“接收請求”進(jìn)程能否占有處理器

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

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

5、是沿臂移動(dòng)方向選擇一個(gè)與當(dāng)前柱面號最近的訪問請求，若沿這個(gè)方向沒有訪問請求時(shí)，就改變臂的移動(dòng)方向。這種調(diào)度策略能使移動(dòng)臂的移動(dòng)頻率極小，從而提高系統(tǒng)效率。用電梯調(diào)度算法實(shí)現(xiàn)驅(qū)動(dòng)調(diào)度的模擬算法如圖33。（4）圖31 中的初始化工作包括，初始化“請求I/O”表，置當(dāng)前移臂方向?yàn)槔镆?；置?dāng)前位置為0 號柱面，0 號物理記錄。程序運(yùn)行前可假定“請求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)前柱面號，物理記錄號來代替圖33 中的“啟動(dòng)磁盤”這項(xiàng)工作。（1） 程序中使用的數(shù)據(jù)結(jié)構(gòu)及其說明。const

6、 int PCB=100; /定義100個(gè)進(jìn)程 int pcbs_num=0; /記錄當(dāng)前io表的進(jìn)程個(gè)數(shù) typedef struct process /請求io表 char pname10; /進(jìn)程名 int Cylinder; /柱面號 int Track; /磁道號 int Record; /物理記錄號 int Way; PROCESS; PROCESS pcbsPCB; PROCESS a; /記錄當(dāng)前位置（柱面號、物理記錄號）采用帶頭節(jié)點(diǎn)的循環(huán)鏈表存（2） 打印一份源程序并附上注釋。（3） #include <iostream> （4） #include <iom

7、anip> （5） #include <stdio.h> （6） #include <cstdlib> （7） #include <fstream> （8） using namespace std;（9） const int PCB = 100; /定義100個(gè)進(jìn)程 （10） int pcbs_num = 0; /記錄當(dāng)前io表的進(jìn)程個(gè)數(shù) （11） typedef struct process /請求io表（12） （13） char pname10; /進(jìn)程名 （14） int Cylinder; /柱面號 （15） int Track; /磁道號

8、（16） int Record; /物理記錄號 （17） int Way;（18） PROCESS;（19） PROCESS pcbsPCB;（20） PROCESS a;（21） void init_a() /設(shè)置當(dāng)前位置 （22） （23） a.Cylinder = 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 <

9、;< endl;（34） return i;（35） （36） void accept() /接受請求模擬算法 （37） （38） cout << "輸入進(jìn)程名和物理地址（柱面號，磁道號，物理記錄號）" << endl;（39） cin >> pcbspcbs_num.pname >> pcbspcbs_num.Cylinder >> pcbspcbs_num.Track >> pcbspcbs_num.Record;（40） pcbs_num+;（41） （42） int Cylinder_e(

10、) /判斷柱面號相等 （43） （44） for (int i = 0; i<pcbs_num; i+)（45） （46） if (pcbsi.Cylinder = a.Cylinder)（47） return i;（48） （49） return 0;（50） （51） int Cylinder_near(int cylinder, int record) /選擇當(dāng)前柱面號的訪問者中物理塊號最近的 （52） （53） int t = 8, a, k;（54） for (int i = 0; i<pcbs_num; i+)（55） （56） if (pcbsi.Cylinder =

11、 cylinder)（57） （58） a = pcbsi.Record - record;（59） if (a<0) a = a + 8; （60） if (a<t)（61） （62） t = a; k = i;（63） （64） （65） （66） return k;（67） （68） int Cylinder_max(int cylinder) /選擇比當(dāng)前柱面號大的請求中柱面號最小的 （69） （70） int num, t = 199, i, a = 0, b = 0;（71） for (i = 0; i < pcbs_num; i+)（72） （73） if (a

12、bs(pcbsi.Cylinder - cylinder)<t && pcbsi.Cylinder > cylinder)（74） （75） t = abs(pcbsi.Cylinder - cylinder);（76） （77） num = cylinder + t; /選擇的柱面號 （78） t = 8; /物理塊號最大相差7 （79） for (i = 0; i<pcbs_num; i+)（80） （81） if (pcbsi.Cylinder = num &&pcbsi.Record < t)（82） （83） t = pcbsi

13、.Record; a = i;（84） （85） （86） return a;（87） （88） int Cylinder_max1(int cylinder)（89） （90） int t = 199, i, b = 0, c = 0;（91） for (i = 0; i<pcbs_num; i+)（92） （93） if (abs(pcbsi.Cylinder - cylinder)>b && pcbsi.Cylinder > cylinder)（94） （95） b = abs(pcbsi.Cylinder - cylinder);（96） （97） （

14、98） return b;（99） （100） int Cylinder_min(int cylinder) /選擇比當(dāng)前柱面號小的請求中柱面號最大的 （101） （102） int num, t = 199, i, a = 0; for (i = 0; i < pcbs_num; i+)（103） （104） if (abs(pcbsi.Cylinder - cylinder)<t && pcbsi.Cylinder < cylinder)（105） （106） t = abs(pcbsi.Cylinder - cylinder);（107） （108） （

15、109） num = cylinder - t; t = 8; /物理塊號相差最大為7 （110） for (i = 0; i < pcbs_num; i+)（111） （112） if (pcbsi.Cylinder = num && pcbsi.Record <t)（113） （114） t = pcbsi.Record; a = i;（115） （116） （117） return a; /返回柱面號小的請求中柱面號最大的下標(biāo)（118） （119） void delete_scan(int x)（120） （121） for (int i = x; i<

16、pcbs_num; i+)（122） pcbsi = pcbsi + 1; pcbs_num-;（123） （124） void print_io() /打印請求io表 （125） （126） cout << "輸出 請求i/o表：" << endl;（127） cout << "進(jìn)程名" << " 柱面號" << " 磁道號" << " 物理記錄號" << endl;（128） for (int i = 0;

17、i<pcbs_num; i+)（129） （130） cout << setfill(' ') << setw(6) << pcbsi.pname << setfill(' ') << setw(8) << pcbsi.Cylinder << setfill(' ') << setw(8) << pcbsi.Track << setfill(' ') << setw(10) << p

18、cbsi.Record << endl;（131） （132） （133） void print_scan(bool x)（134） （135） cout << "選中的：" << endl; cout << "進(jìn)程名" << " 柱面號" << " 磁道號" << " 物理記錄號" << " 方向" << endl; cout << setfill(

19、9; ') << setw(6) << a.pname << setfill(' ') << setw(8) << a.Cylinder << setfill(' ') << setw(10) << a.Track << setfill(' ') << setw(10) << a.Record << setfill(' ') << setw(6) << x

20、<< endl;（136） （137） int SCAN() /驅(qū)動(dòng)調(diào)度 電梯調(diào)度模擬算法 （138） （139） print_io(); /打印io表 （140） int scan;（141） int scan1;/scan為選擇的進(jìn)程的編號 （142） bool way = 1; /方向 0=out 1=in （143） if (a.Cylinder = NULL)（144） （145） init_a();（146） （147） if (pcbs_num = 0)（148） （149） cout << "無等待訪問者" << endl

21、; return 0;（150） （151） else（152） （153） if (pcbsCylinder_e().Cylinder = a.Cylinder) /選擇能使旋轉(zhuǎn)距離最短的訪問者 （154） （155） scan = Cylinder_near(a.Cylinder, a.Record);/選擇當(dāng)前柱面號的訪問者中最近的 （156） if (pcbsscan.Cylinder<a.Cylinder)（157） （158） way = 0;（159） （160） else way = 1;（161） （162） else（163） （164） if (way = 1)（165） （166） scan = Cylinder_max(a.Cylinder); /選擇比當(dāng)前柱面號大的請求中物理塊號最小的 （167） scan1 = Cylinder_max1(a.Cylinder);（168） if (scan = scan1)（169） （170） scan = Cylinder_min(a.Cylinder); /選擇比當(dāng)前柱面號小的請求中物理塊號最大的 （171） way = 0;（172） （173） （174） else（175） （176） s