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

..>操作系統(tǒng)實(shí)驗(yàn)〔第三次〕一、實(shí)驗(yàn)內(nèi)容模擬電梯調(diào)度算法，實(shí)現(xiàn)對磁盤的驅(qū)動調(diào)度。二、實(shí)驗(yàn)?zāi)康拇疟P是一種高速、大容量、旋轉(zhuǎn)型、可直接存取的存儲設(shè)備。它作為計(jì)算機(jī)系統(tǒng)的輔助存儲器，擔(dān)負(fù)著繁重的輸入輸出任務(wù)、在多道程序設(shè)計(jì)系統(tǒng)中，往往同時會有假設(shè)干個要求訪問磁盤的輸入輸出請求等待處理。系統(tǒng)可采用一種策略，盡可能按最正確次序執(zhí)行要求訪問磁盤的諸輸入輸出請求。這就叫驅(qū)動調(diào)度，使用的算法稱為驅(qū)動調(diào)度算法。驅(qū)動調(diào)度能降低為假設(shè)干個輸入輸出請求效勞所需的總時間，從而提高系統(tǒng)效率。本實(shí)驗(yàn)要求學(xué)生模擬設(shè)計(jì)一個驅(qū)動調(diào)度程序，觀察驅(qū)動調(diào)度程序的動態(tài)運(yùn)行過程。通過實(shí)驗(yàn)使學(xué)生理解和掌握驅(qū)動調(diào)度的職能。實(shí)驗(yàn)題目模擬電梯調(diào)度算法，對磁盤進(jìn)展移臂和旋轉(zhuǎn)調(diào)度。[提示]：〔1〕磁盤是可供多個進(jìn)程共享的存儲設(shè)備，但一個磁盤每時刻只能為一個進(jìn)程效勞。當(dāng)有進(jìn)程在訪問*個磁盤時，其他想訪問該磁盤的進(jìn)程必須等待，直到磁盤一次工作完畢。當(dāng)有多個進(jìn)程提出輸入輸出要求而處于等待狀態(tài)時，可用電梯調(diào)度算法從假設(shè)干個等待訪問者中選擇一個進(jìn)程，讓它訪問磁盤。選擇訪問者的工作由"驅(qū)動調(diào)度〞進(jìn)程來完成。由于磁盤與處理器是可以并行工作的、所以當(dāng)磁盤在作為一個進(jìn)程效勞時，占有處理器的另一進(jìn)程可以提出使用磁盤的要求，也就是說，系統(tǒng)能動態(tài)地接收新的輸入輸出請求。為了模擬這種情況，在本實(shí)驗(yàn)中設(shè)置了一個"接收請求〞進(jìn)程。"驅(qū)動調(diào)度〞進(jìn)程和"接收請求〞進(jìn)程能否占有處理器運(yùn)行，取決于磁盤的完畢中斷信號和處理器調(diào)度策略。在實(shí)驗(yàn)中可用隨機(jī)數(shù)來模擬確定這兩個進(jìn)程的運(yùn)行順序，以代替中斷處理和處理器調(diào)度選擇的過程。因而，程序的構(gòu)造可參考圖3—1〔2〕"接收請求〞進(jìn)程建立一張"請求I/O〞表，指出訪問磁盤的進(jìn)程要求訪問的物理地址，表的格式為：假定*個磁盤組共有200個柱面，由外向里順序〔0—199〕，每個柱面上有20個磁道，為0—19，每個磁道分成8個物理記錄，0—7。進(jìn)程訪問磁盤的物理地址可以用鍵盤輸入的方法模擬得到。圖3—2是"接收請求〞進(jìn)程的模擬算法。在實(shí)際的系統(tǒng)中必須把等待訪問磁盤的進(jìn)程排入等待列隊(duì)，由于本實(shí)驗(yàn)?zāi)M驅(qū)動調(diào)度，為簡單起見，在實(shí)驗(yàn)中可免去隊(duì)列管理局部，故設(shè)計(jì)程序時可不考慮"進(jìn)程排入等待隊(duì)列〞的工作。〔3〕"驅(qū)動調(diào)度〞進(jìn)程的功能是查"請求I/O〞表，當(dāng)有等待訪問磁盤的進(jìn)程時，按電梯調(diào)度算法從中選擇一個等待訪問者，按該進(jìn)程指定的磁盤物理地址啟動磁盤為其效勞。對移動臂磁盤來說，驅(qū)動調(diào)度分移臂調(diào)度和旋轉(zhuǎn)調(diào)度。電梯調(diào)度算法的調(diào)度策略是與移動臂的移動方向和移動臂的當(dāng)前位子有關(guān)的，所以每次啟動磁盤時都應(yīng)登記移動臂方向和當(dāng)前位子。電梯調(diào)度算法是一種簡單而實(shí)用的驅(qū)動調(diào)度方法，這種調(diào)度策略總是優(yōu)先選擇與當(dāng)前柱面號一樣的訪問請求，從這些請求中再選擇一個能使旋轉(zhuǎn)距離最短的等待訪問者。如果沒有與當(dāng)前柱面號一樣的訪問請求，則根據(jù)移臂方向來選擇，每次總是沿臂移動方向選擇一個與當(dāng)前柱面號最近的訪問請求，假設(shè)沿這個方向沒有訪問請求時，就改變臂的移動方向。這種調(diào)度策略能使移動臂的移動頻率極小，從而提高系統(tǒng)效率。用電梯調(diào)度算法實(shí)現(xiàn)驅(qū)動調(diào)度的模擬算法如圖3－3?！?〕圖3－1中的初始化工作包括，初始化"請求I/O〞表，置當(dāng)前移臂方向?yàn)槔镆?；置?dāng)前位置為0號柱面，0號物理記錄。程序運(yùn)行前可假定"請求I/O〞表中已經(jīng)有如干個進(jìn)程等待訪問磁盤。在模擬實(shí)驗(yàn)中，中選中一個進(jìn)程可以訪問磁盤時，并不實(shí)際地啟動磁盤，而用顯示："請求I/O〞表；當(dāng)前移臂方向；當(dāng)前柱面號，物理記錄號來代替圖3－3中的"啟動磁盤〞這項(xiàng)工作。程序中使用的數(shù)據(jù)構(gòu)造及其說明。constintPCB=100;//定義100個進(jìn)程intpcbs_num=0;//記錄當(dāng)前io表的進(jìn)程個數(shù)typedefstructprocess//請求io表{charpname[10];//進(jìn)程名intCylinder;//柱面號intTrack;//磁道號intRecord;//物理記錄號intWay;}PROCESS;PROCESSpcbs[PCB];PROCESSa;//記錄當(dāng)前位置〔柱面號、物理記錄號〕采用帶頭節(jié)點(diǎn)的循環(huán)鏈表存打印一份源程序并附上注釋。#include<iostream>#include<iomanip>#include<stdio.h>#include<cstdlib>#include<fstream>usingnamespacestd;constintPCB=100;//定義100個進(jìn)程intpcbs_num=0;//記錄當(dāng)前io表的進(jìn)程個數(shù)typedefstructprocess//請求io表{charpname[10];//進(jìn)程名intCylinder;//柱面號intTrack;//磁道號intRecord;//物理記錄號intWay;}PROCESS;PROCESSpcbs[PCB];PROCESSa;voidinit_a()//設(shè)置當(dāng)前位置{a.Cylinder=4;a.Track=0;a.Record=0;}intcount_PN()//記錄進(jìn)程總數(shù){inti;for(i=0;pcbs[i].Cylinder!=NULL;i++) { }cout<<i<<endl;returni;}voidaccept()//承受請求模擬算法{cout<<"輸入進(jìn)程名和物理地址〔柱面號，磁道號，物理記錄號〕"<<endl;cin>>pcbs[pcbs_num].pname>>pcbs[pcbs_num].Cylinder>>pcbs[pcbs_num].Track>>pcbs[pcbs_num].Record;pcbs_num++;}intCylinder_e()//判斷柱面號相等{for(inti=0;i<pcbs_num;i++) {if(pcbs[i].Cylinder==a.Cylinder)returni; }return0;}intCylinder_near(intcylinder,intrecord)////選擇當(dāng)前柱面號的訪問者中物理塊號最近的{intt=8,a,k;for(inti=0;i<pcbs_num;i++) {if(pcbs[i].Cylinder==cylinder) {a=pcbs[i].Record-record;if(a<0){a=a+8;}if(a<t) {t=a;k=i; } } }returnk;}intCylinder_ma*(intcylinder)//選擇比當(dāng)前柱面號大的請求中柱面號最小的{intnum,t=199,i,a=0,b=0;for(i=0;i<pcbs_num;i++) {if((abs(pcbs[i].Cylinder-cylinder))<t&&pcbs[i].Cylinder>cylinder) {t=abs(pcbs[i].Cylinder-cylinder); } }num=cylinder+t;//選擇的柱面號t=8;//物理塊號最大相差7for(i=0;i<pcbs_num;i++) {if(pcbs[i].Cylinder==num&&pcbs[i].Record<t) {t=pcbs[i].Record;a=i; } }returna;}intCylinder_ma*1(intcylinder){intt=199,i,b=0,c=0;for(i=0;i<pcbs_num;i++) {if((abs(pcbs[i].Cylinder-cylinder))>b&&pcbs[i].Cylinder>cylinder) {b=abs(pcbs[i].Cylinder-cylinder); } }returnb;}intCylinder_min(intcylinder)//選擇比當(dāng)前柱面號小的請求中柱面號最大的{intnum,t=199,i,a=0;for(i=0;i<pcbs_num;i++) {if((abs(pcbs[i].Cylinder-cylinder))<t&&pcbs[i].Cylinder<cylinder) {t=abs(pcbs[i].Cylinder-cylinder); } }num=cylinder-t;t=8;//物理塊號相差最大為7for(i=0;i<pcbs_num;i++) {if(pcbs[i].Cylinder==num&&pcbs[i].Record<t) {t=pcbs[i].Record;a=i; } }returna;//返回柱面號小的請求中柱面號最大的下標(biāo)}voiddelete_scan(int*){for(inti=*;i<pcbs_num;i++)pcbs[i]=pcbs[i+1];pcbs_num--;}voidprint_io()//打印請求io表{cout<<"輸出請求i/o表："<<endl;cout<<"進(jìn)程名"<<"柱面號"<<"磁道號"<<"物理記錄號"<<endl;for(inti=0;i<pcbs_num;i++) {cout<<setfill('')<<setw(6)<<pcbs[i].pname<<setfill('')<<setw(8)<<pcbs[i].Cylinder<<setfill('')<<setw(8)<<pcbs[i].Track<<setfill('')<<setw(10)<<pcbs[i].Record<<endl; }}voidprint_scan(bool*){cout<<"選中的："<<endl;cout<<"進(jìn)程名"<<"柱面號"<<"磁道號"<<"物理記錄號"<<"方向"<<endl;cout<<setfill('')<<setw(6)<<a.pname<<setfill('')<<setw(8)<<a.Cylinder<<setfill('')<<setw(10)<<a.Track<<setfill('')<<setw(10)<<a.Record<<setfill('')<<setw(6)<<*<<endl;}intSCAN()//驅(qū)動調(diào)度電梯調(diào)度模擬算法{print_io();//打印io表intscan;intscan1;//scan為選擇的進(jìn)程的boolway=1;//方向0=out1=inif(a.Cylinder==NULL) {init_a(); }if(pcbs_num==0) {cout<<"無等待訪問者"<<endl;return0; }else {if(pcbs[Cylinder_e()].Cylinder==a.Cylinder)//選擇能使旋轉(zhuǎn)距離最短的訪問者 {scan=Cylinder_near(a.Cylinder,a.Record);//選擇當(dāng)前柱面號的訪問者中最近的if(pcbs[scan].Cylinder<a.Cylinder) {way=0; }elseway=1; }else {if(way==1) {scan=Cylinder_ma*(a.Cylinder);//選擇比當(dāng)前柱面號大的請求中物理塊號最小的scan1=Cylinder_ma*1(a.Cylinder);if(scan==scan1) {scan=Cylinder_min(a.Cylinder);//選擇比當(dāng)前柱面號小的請求中物理塊號最大的way=0; } }else {scan=Cylinder_min(a.Cylinder);if(scan==0) {scan=Cylinder_ma*(a.Cylinder);way=1; } } }a=pcbs[scan];delete_scan(scan);//刪除pcbs[scan]print_scan(way);//打印return1; }}voidwork()//初始化{floatn;