实验三___驱动调度

实验三驱动调度一、实验内容模拟电梯调度算法，实现对磁盘的驱动调度。二、实验目的磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。三、实验题目模拟电梯调度算法，对磁盘进行移臂和旋转调度。[提示]：（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代表外移。打印格式为：五、数据结构//请求I/O表structRequie_I_O{stringPro_Name;//进程名intCy_Num;//柱面号intTrack_Num;//磁道号intPhy_Re_Num;//物理记录号char*Direction;//方向}I_O[100],a[100];//定义两个变量数组，代表等待访问磁盘的若干个进程structRequie_I_OCur_Location;//当前位置intlast;//最后一个等待访问磁盘的进程的下标六、源代码#includeiostream#includestring#includectimeusingnamespacestd;//请求I/O表structRequie_I_O“请求I/O”表进程名柱面号物理记录号方向{stringPro_Name;//进程名intCy_Num;//柱面号intTrack_Num;//磁道号intPhy_Re_Num;//物理记录号char*Direction;//方向}I_O[100],a[100];//定义两个变量数组，代表等待访问磁盘的若干个进程structRequie_I_OCur_Location;//当前位置intlast;//最后一个等待访问磁盘的进程的下标//初始化请求I/O表voidInit_I_O(){Cur_Location.Cy_Num=0;//当前柱面号Cur_Location.Phy_Re_Num=0;//当前物理记录号Cur_Location.Direction=up;//当前方向//已有的若干个（5个）等待访问磁盘的进程I_O[0].Pro_Name=P0;I_O[0].Cy_Num=145;I_O[0].Track_Num=36;I_O[0].Phy_Re_Num=6;I_O[1].Pro_Name=P1;I_O[1].Cy_Num=126;I_O[1].Track_Num=97;I_O[1].Phy_Re_Num=1;I_O[2].Pro_Name=P2;I_O[2].Cy_Num=67;I_O[2].Track_Num=23;I_O[2].Phy_Re_Num=5;I_O[3].Pro_Name=P3;I_O[3].Cy_Num=99;I_O[3].Track_Num=0;I_O[3].Phy_Re_Num=4;I_O[4].Pro_Name=P4;I_O[4].Cy_Num=3;I_O[4].Track_Num=63;I_O[4].Phy_Re_Num=7;I_O[5].Pro_Name=P5;I_O[5].Cy_Num=100;I_O[5].Track_Num=19;I_O[5].Phy_Re_Num=2;last=5;}//接收请求voidAccept_Request(){charans;cout请问是否有请求？(Y/N)\n;cinans;if(ans=='Y'){last++;cout请输入进程名物理地址:进程名、柱面号（0-199）、磁道号（0-99）、物理记录号（0-7）\n;cinI_O[last].Pro_NameI_O[last].Cy_NumI_O[last].Track_NumI_O[last].Phy_Re_Num;}//有请求所以登记请求I/O表}//驱动调度voidDriven_Scheduling(){Cur_Location.Cy_Num=160;Cur_Location.Phy_Re_Num=13;Cur_Location.Direction=up;if(last0)cout无等待访问磁盘的进程！endl;//无等待访问所以返回else{intcount0=0;//与当前柱面号相同的访问进程数for(inti=0;ilast+1;i++)if(I_O[i].Cy_Num==Cur_Location.Cy_Num)//判断是否有与当前柱面号相同的访问者{a[count0]=I_O[i];count0++;}if(--count00)//有与当前柱面号相同的访问者{0==0;//未完成}//当前移臂方向为向里elseif(string(Cur_Location.Direction)==string(up)){intflag=0,m,n=0,temp;//flag=1的时候判断是否满足条件for(inti=0;ilast+1;i++){if(I_O[i].Cy_NumCur_Location.Cy_Num){flag=1;n=i;break;}temp=I_O[n].Cy_Num;//将第一个满足条件的值保存在temp}if(flag==1)//有比当前柱面号大的访问者{if(last==0){m=n;}//当只有一个元素时，该元素就是我么要找寻的else{//在大于当前柱面号的访问者中选择一个最小者for(inti=n;ilast+1;i++){if(I_O[i].Cy_NumCur_Location.Cy_Num)if(tempI_O[i].Cy_Num){temp=I_O[i].Cy_Num;m=i;}}}//登记当前位置，柱面号、物理记录号Cur_Location.Cy_Num=I_O[m].Cy_Num;Cur_Location.Phy_Re_Num=I_O[m].Phy_Re_Num;//启动磁盘cout请求I/O表\n;cout当前移臂方向为：Cur_Location.Directionendl;cout当前柱面号为：Cur_Location.Cy_Numendl;cout当前物理记录号为：Cur_Location.Phy_Re_Numendl;for(inti=m;ilast+1;i++)I_O[i]=I_O[i+1];//被选者退出last--;//数组元素减一}else//没有比当前柱面号大的访问请求{Cur_Location.Direction=down;inttemp=I_O[0].Cy_Num,p=0;for(intj=1;jlast+1;j++){//从小于当前柱面号的访问请求中选择一个最大者if(tempI_O[j].Cy_Num){temp=I_O[j].Cy_Num;p=j;}}Cur_Location.Cy_Num=I_O[p].Cy_Num;Cur_Location.Phy_Re_Num=I_O[p].Phy_Re_Num;cout请求I/O表\n;cout当前移臂方向为：Cur_Location.Directionendl;cout当前柱面号为：Cur_Location.Cy_Numendl;cout当前物理记录号为：Cur_Location.Phy_Re_Numendl;for(inti=p;ilast+1;i++)I_O[i]=I_O[i+1];last--;}}else//当前移臂方向为向外{intflag=0,m,n;for(inti=0;ilast+1;i++){if(I_O[i].Cy_NumCur_Location.Cy_Num){flag=1;n=i;break;}}if(flag==1)//有比当前柱面号小的访问请求{inttemp=I_O[n].Cy_Num;f