模拟电梯调度算法实现对磁盘的驱动调度.docx
《模拟电梯调度算法实现对磁盘的驱动调度.docx》由会员分享，可在线阅读，更多相关《模拟电梯调度算法实现对磁盘的驱动调度.docx（17页珍藏版）》请在冰点文库上搜索。
模拟电梯调度算法实现对磁盘的驱动调度
模拟电梯调度算法-实现对磁盘的驱动调度。
————————————————————————————————作者：
————————————————————————————————日期：
操作系统实验
（第三次）
一、实验内容
模拟电梯调度算法，实现对磁盘的驱动调度。
二、实验目的
磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。
它作为计算机系统的辅
助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求
访问磁盘的输入输出请求等待处理。
系统可采用一种策略，尽可能按最佳次序执行要求访问
磁盘的诸输入输出请求。
这就叫驱动调度，使用的算法称为驱动调度算法。
驱动调度能降低
为若干个输入输出请求服务所需的总时间，从而提高系统效率。
本实验要求学生模拟设计一
个驱动调度程序，观察驱动调度程序的动态运行过程。
通过实验使学生理解和掌握驱动调度
的职能。
3、实验题目
模拟电梯调度算法，对磁盘进行移臂和旋转调度。
[提示]：
（1）磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。
当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。
当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访问者
中选择一个进程，让它访问磁盘。
选择访问者的工作由“驱动调度”进程来完成。
由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时，占有处理
器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的输入输出请求。
为了模拟这种情况，在本实验中设置了一个“接收请求”进程。
“驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信
号和处理器调度策略。
在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断
4、处理和处理器调度选择的过程。
因而，程序的结构可参考图3—1
（2）“接收请求”进程建立一张“请求I/O”表，指出访问磁盘的进程要求访问的物理
地址，表的格式为：
假定某个磁盘组共有200个柱面，由外向里顺序编号（0—199），每个柱面上有20个
磁道，编号为0—19，每个磁道分成8个物理记录，编号0—7。
进程访问磁盘的物理地址
可以用键盘输入的方法模拟得到。
图3—2是“接收请求”进程的模拟算法。
在实际的系统中必须把等待访问磁盘的进程排入等待列队，由于本实验模拟驱动调
度，为简单起见，在实验中可免去队列管理部分，故设计程序时可不考虑“进程排入等待队
列”的工作。
（3）“驱动调度”进程的功能是查“请求I/O”表，当有等待访问磁盘的进程时，按
电梯调度算法从中选择一个等待访问者，按该进程指定的磁盘物理地址启动磁盘为其服务。
对移动臂磁盘来说，驱动调度分移臂调度和旋转调度。
电梯调度算法的调度策略是与
移动臂的移动方向和移动臂的当前位子有关的，所以每次启动磁盘时都应登记移动臂方向和
当前位子。
电梯调度算法是一种简单而实用的驱动调度方法，这种调度策略总是优先选择与
当前柱面号相同的访问请求，从这些请求中再选择一个能使旋转距离最短的等待访问者。
如
果没有与当前柱面号相同的访问请求，则根据移臂方向来选择，每次总是沿臂移动方向选择
一个与当前柱面号最近的访问请求，若沿这个方向没有访问请求时，就改变臂的移动方向。
这种调度策略能使移动臂的移动频率极小，从而提高系统效率。
用电梯调度算法实现驱动调
度的模拟算法如图3－3。
（4）图3－1中的初始化工作包括，初始化“请求I/O”表，置当前移臂方向为里移；
置当前位置为0号柱面，0号物理记录。
程序运行前可假定“请求I/O”表中已经有如干个
进程等待访问磁盘。
在模拟实验中，当选中一个进程可以访问磁盘时，并不实际地启动磁盘，而用显示：
“请
求I/O”表；当前移臂方向；当前柱面号，物理记录号来代替图3－3中的“启动磁盘”这
项工作。
（1）程序中使用的数据结构及其说明。
constintPCB=100;//定义100个进程
intpcbs_num=0;//记录当前io表的进程个数
typedefstructprocess//请求io表
{
charpname[10];//进程名
intCylinder;//柱面号
intTrack;//磁道号
intRecord;//物理记录号
intWay;
}PROCESS;
PROCESSpcbs[PCB];
PROCESSa;//记录当前位置（柱面号、物理记录号）采用带头节点的循环链表存
（2）打印一份源程序并附上注释。
（3）#include
（4）#include
（5）#include
（6）#include
（7）#include
（8）usingnamespacestd;
（9）constintPCB=100;//定义100个进程
（10）intpcbs_num=0;//记录当前io表的进程个数
（11）typedefstructprocess//请求io表
（12）{
（13）charpname[10];//进程名
（14）intCylinder;//柱面号
（15）intTrack;//磁道号
（16）intRecord;//物理记录号
（17）intWay;
（18）}PROCESS;
（19）PROCESSpcbs[PCB];
（20）PROCESSa;
（21）voidinit_a（）//设置当前位置
（22）{
（23）a.Cylinder=4;
（24）a.Track=0;
（25）a.Record=0;
（26）}
（27）intcount_PN（）//记录进程总数
（28）{
（29）inti;
（30）for（i=0;pcbs[i].Cylinder!
=NULL;i++）
（31）{
（32）}
（33）cout<（34）returni;
（35）}
（36）voidaccept（）//接受请求模拟算法
（37）{
（38）cout<<"输入进程名和物理地址（柱面号，磁道号，物理记录号）"<（39）cin>>pcbs[pcbs_num].pname>>pcbs[pcbs_num].Cylinder>>pcbs[pcbs_num].Track>>pcbs[pcbs_num].Record;
（40）pcbs_num++;
（41）}
（42）intCylinder_e（）//判断柱面号相等
（43）{
（44）for（inti=0;i（45）{
（46）if（pcbs[i].Cylinder==a.Cylinder）
（47）returni;
（48）}
（49）return0;
（50）}
（51）intCylinder_near（intcylinder,intrecord）////选择当前柱面号的访问者中物理块号最近的
（52）{
（53）intt=8,a,k;
（54）for（inti=0;i（55）{
（56）if（pcbs[i].Cylinder==cylinder）
（57）{
（58）a=pcbs[i].Record-record;
（59）if（a<0）{a=a+8;}
（60）if（a（61）{
（62）t=a;k=i;
（63）}
（64）}
（65）}
（66）returnk;
（67）}
（68）intCylinder_max（intcylinder）//选择比当前柱面号大的请求中柱面号最小的
（69）{
（70）intnum,t=199,i,a=0,b=0;
（71）for（i=0;i（72）{
（73）if（（abs（pcbs[i].Cylinder-cylinder））cylinder）
（74）{
（75）t=abs（pcbs[i].Cylinder-cylinder）;
（76）}
（77）}num=cylinder+t;//选择的柱面号
（78）t=8;//物理块号最大相差7
（79）for（i=0;i（80）{
（81）if（pcbs[i].Cylinder==num&&pcbs[i].Record（82）{
（83）t=pcbs[i].Record;a=i;
（84）}
（85）}
（86）returna;
（87）}
（88）intCylinder_max1（intcylinder）
（89）{
（90）intt=199,i,b=0,c=0;
（91）for（i=0;i（92）{
（93）if（（abs（pcbs[i].Cylinder-cylinder））>b&&pcbs[i].Cylinder>cylinder）
（94）{
（95）b=abs（pcbs[i].Cylinder-cylinder）;
（96）}
（97）}
（98）returnb;
（99）}
（100）intCylinder_min（intcylinder）//选择比当前柱面号小的请求中柱面号最大的
（101）{
（102）intnum,t=199,i,a=0;for（i=0;i（103）{
（104）if（（abs（pcbs[i].Cylinder-cylinder））（105）{
（106）t=abs（pcbs[i].Cylinder-cylinder）;
（107）}
（108）}
（109）num=cylinder-t;t=8;//物理块号相差最大为7
（110）for（i=0;i（111）{
（112）if（pcbs[i].Cylinder==num&&pcbs[i].Record（113）{
（114）t=pcbs[i].Record;a=i;
（115）}
（116）}
（117）returna;//返回柱面号小的请求中柱面号最大的下标
（118）}
（119）voiddelete_scan（intx）
（120）{
（121）for（inti=x;i（122）pcbs[i]=pcbs[i+1];pcbs_num--;
（123）}
（124）voidprint_io（）//打印请求io表
（125）{
（126）cout<<"输出请求i/o表：
"<（127）cout<<"进程名"<<"柱面号"<<"磁道号"<<"物理记录号"<（128）for（inti=0;i（129）{
（130）cout<（131）}
（132）}
（133）voidprint_scan（boolx）
（134）{
（135）cout<<"选中的：
"<（136）}
（137）intSCAN（）//驱动调度电梯调度模拟算法
（138）{
（139）print_io（）;//打印io表
（140）intscan;
（141）intscan1;//scan为选择的进程的编号
（142）boolway=1;//方向0=out1=in
（143）if（a.Cylinder==NULL）
（144）{
（145）init_a（）;
（146）}
（147）if（pcbs_num==0）
（148）{
（149）cout<<"无等待访问者"<（150）}
（151）else
（152）{
（153）if（pcbs[Cylinder_e（）].Cylinder==a.Cylinder）//选择能使旋转距离最短的访问者
（154）{
（155）scan=Cylinder_near（a.Cylinder,a.Record）;//选择当前柱面号的访问者中最近的
（156）if（pcbs[scan].Cylinder（157）{
（158）way=0;
（159）}
（160）elseway=1;
（161）}
（162）else
（163）{
（164）if（way==1）
（165）{
（166）scan=Cylinder_max（a.Cylinder）;//选择比当前柱面号大的请求中物理块号最小的
（167）scan1=Cylinder_max1（a.Cylinder）;
（168）if（scan==scan1）
（169）{
（170）scan=Cylinder_min（a.Cylinder）;//选择比当前柱面号小的请求中物理块号最大的
（171）way=0;
（172）}
（173）}
（174）else
（175）{
（176）scan=Cylinder_min（a.Cylinder）;
（177）if（scan==0）
（178）{
（179）scan=Cylinder_max（a.Cylinder）;
（180）way=1;
（181）}
（182）}
（183）}a=pcbs[scan];
（184）delete_scan（scan）;//删除pcbs[scan]
（185）print_scan（way）;//打印
（186）return1;
（187）}
（188）}
（189）voidwork（）//初始化
（190）{
（191）floatn;chary='y';while（y=='y'||y=='Y'）
（192）{
（193）cout<<"输入在[0，1]区间内的一个随机数"<（194）cin>>n;
（195）if（n>0.5）
（196）{
（197）SCAN（）;//驱动调度
（198）}
（199）else
（200）{
（201）accept（）;//接受请求
（202）}
（203）cout<<"继续？
（y/n）"<（204）cin>>y;
（205）}
（206）}
（207）voidmain（）
（208）{
（209）work（）;
（210）}
（4）打印驱动调度进程每次选择访问请求前的“请求I/O”表以及每次选中的进程名、
访问的柱面号、物理记录号和当前移臂方向（用up代表里移，down代表外移
升级会员 