实验三 驱动调度

实验三驱动调度一、实验内容模拟电梯调度算法，实现对磁盘的驱动调度。二、实验目的磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。三、实验题目模拟电梯调度算法，对磁盘进行移臂和旋转调度。[提示]：（1）磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时，占有处理器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的输入输出请求。为了模拟这种情况，在本实验中设置了一个“接收请求”进程。“驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断处理和处理器调度选择的过程。因而，程序的结构可参考图3—1图3—1程序结构（2）“接收请求”进程建立一张“请求I/O”表，指出访问磁盘的进程要求访问的物理地址，表的格式为：进程名柱面号磁道号物理记录号假定某个磁盘组共有200个柱面，由外向里顺序编号（0—199），每个柱面上有20个磁道，编号为0—19，每个磁道分成8个物理记录，编号0—7。进程访问磁盘的物理地址可以用键盘输入的方法模拟得到。图3—2是“接收请求”进程的模拟算法。初始化输入在[0，1]区间内的一个随机数随机数1/2开始驱动调度接受请求继续？结束是是否否图3—2“接收请求”模拟算法在实际的系统中必须把等待访问磁盘的进程排入等待列队，由于本实验模拟驱动调度，为简单起见，在实验中可免去队列管理部分，故设计程序时可不考虑“进程排入等待队列”的工作。（3）“驱动调度”进程的功能是查“请求I/O”表，当有等待访问磁盘的进程时，按电梯调度算法从中选择一个等待访问者，按该进程指定的磁盘物理地址启动磁盘为其服务。对移动臂磁盘来说，驱动调度分移臂调度和旋转调度。电梯调度算法的调度策略是与移动臂的移动方向和移动臂的当前位子有关的，所以每次启动磁盘时都应登记移动臂方向和当前位子。电梯调度算法是一种简单而实用的驱动调度方法，这种调度策略总是优先选择与当前柱面号相同的访问请求，从这些请求中再选择一个能使旋转距离最短的等待访问者。如果没有与当前柱面号相同的访问请求，则根据移臂方向来选择，每次总是沿臂移动方向选择一个与当前柱面号最近的访问请求，若沿这个方向没有访问请求时，就改变臂的移动方向。这种调度策略能使移动臂的移动频率极小，从而提高系统效率。用电梯调度算法实现驱动调度的模拟算法如图3－3。（4）图3－1中的初始化工作包括，初始化“请求I/O”表，置当前移臂方向为里移；置当前位置为0号柱面，0号物理记录。程序运行前可假定“请求I/O”表中已经有如干个进程等待访问磁盘。在模拟实验中，当选中一个进程可以访问磁盘时，并不实际地启动磁盘，而用显示：“请求I/O”表；当前移臂方向；当前柱面号，物理记录号来代替图3－3中的“启动磁盘”这项工作。开始有请求？输入：进程名物理地址进程排入等待队列登记“请求I/O表返回是否图3－3电梯调度模拟算法置当前移臂方向为向外移置当前移臂方向为向外移从大于当前柱面号的访问请求中选择一个最小者从小于当前柱面号的访问请求中选择一个最大者登记当前位置；柱面号；物理记录号；启动磁盘被选者退出“请求I/O”表返回开始否否否否查“请求I/O表”有等待访问者？返回有与当前柱面号相同的访问者？是否否否否否否是是是是选择能使旋转距离最短的访问者当前移臂方向是向里？有比当前柱面号大的访问请求？有比当前柱面号小的访问请求？四、实验报告（1）实验题目。（2）程序中使用的数据结构及其说明。（3）打印一份源程序并附上注释。（4）打印驱动调度进程每次选择访问请求前的“请求I/O”表以及每次选中的进程名、访问的柱面号、物理记录号和当前移臂方向（用up代表里移，down代表外移。打印格式为：五、数据结构classI_O_Table//请求I/O表{public:stringName;//进程名intCylinder_Num;//柱面号intTrack_Num;//磁道号intPhysic_Rec;//物理记录号intsign;//标志位，是否被选中I_O_Table();//I/O请求表初始化voidInsert(stringNa,intC,intT,intP);//I/O表登记函数voidclear();//清除选中进程voiddisplay();};六、源代码#includeiostream#includestringusingnamespacestd;#defineN10“请求I/O”表进程名柱面号物理记录号方向classI_O_Table//请求I/O表{public:stringName;//进程名intCylinder_Num;//柱面号intTrack_Num;//磁道号intPhysic_Rec;//物理记录号intsign;//标志位，是否被选中I_O_Table(){//I/O请求表初始化Name='';Cylinder_Num=-1;Track_Num=-1;Physic_Rec=-1;}voidInsert(stringNa,intC,intT,intP)//I/O表登记函数{Name=Na;Cylinder_Num=C;Track_Num=T;Physic_Rec=P;sign=0;}voidclear(){Name=NULL;Cylinder_Num=-1;Track_Num=-1;Physic_Rec=-1;sign=0;}voiddisplay(){coutName\t\tCylinder_Num\t\tTrack_Num\t\tPhysic_Rec\t\tsignendl;}};voidRequired(I_O_Table*list){stringNa;intC,T,P;cout请输入进程名：;cinNa;cout请输入柱面号(0-199)：;cinC;cout请输入磁道号(0-19)：;cinT;cout请输入物理记录号(0-7)：;cinP;for(inti=0;iN;i++)if(list[i].Cylinder_Num==-1){list[i].Insert(Na,C,T,P);break;}}voidControl(I_O_Table*list,string&dir,inttemp){//intsame=-2;inti=0,j=0;intm=temp;//for(;iN;i++)if(list[i].Cylinder_Num!=-1)break;if(i==N)cout当前不存在等待进程!endl;else{/*for(;jN;j++)if(list[j].sign==1)same=list[j].Cylinder_Num;for(intk=0;kN;k++)if(list[k].Cylinder_Num==same&&k!=j)return;//旋转臂*/if(dir==up)//往里移{for(;m200;m++)for(i=0;iN;i++)if(list[i].Cylinder_Num==m){list[i].sign=1;return;}if(m==200)dir=down;}if(dir==down){for(;m-1;m--)for(i=0;iN;i++)if(list[i].Cylinder_Num==m){list[i].sign=1;return;}if(m==-1)dir=up;}}}voidmain(){I_O_Tablept[N];stringdir=up;//设定方向向里floatn;inttemp=0;charchoice;pt[0].Insert(P0,0,0,0);//初始化当前进程pt[1].Insert(P1,100,1,1);pt[2].Insert(P2,20,2,2);do{cout输入在[0,1]区间的一个随机数:endl;cinn;if(0=n&&n=0.5)Required(pt);//接受请求elseif(0.5n&&n=1)Control(pt,dir,temp);//驱动调度elsecout输入错误！endl;for(inti=0;iN;i++)if(pt[i].sign==1){cout选中的进程：endl;cout进程名\t\t柱面号\t\t物理记录号\t方向endl;temp=pt[i].Cylinder_Num;coutpt[i].Name\t\tpt[i].Cylinder_Num\t\tpt[i].Physic_Rec\t\tdirendl;pt[i].clear();}cout请求I/O表：endl;cout进程名\t\t柱面号\t\t磁道号\t\t物理记录号endl;for(inti=0;iN;i++)if(pt[i].Cylinder_Num!=-1&&pt[i].sign!=1)pt[i].display();cout是否继续?(Y/N)endl;getchar();cinchoice;}while(choice=='Y'||choice=='y');system(pause);}七、实验结果原等待队列有三个进程，先执行一次驱动调度请求一个新进程P3再次执行驱动调度，按电梯算法，P3优先执行请求一个新进程P4执行驱动调度的结果：执行顺序为P2-P1-P4,\驱动调度执行成功！八、实验小结通过这次实验，我更加深刻的理解了电梯调度算法以及驱动调度的相关概念。进一步的提高了自己对C++的认知能力、编程技巧，加强了自己的动手能力，更加深入的理解和认识了操作系统这门课程，更加深入的理解计算机的实际工作原理，为以后学习操作系统课程打下一定的基础。