模擬電梯調度算法-實現(xiàn)對磁盤的驅動調度

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