模拟电梯调度算法-实现对磁盘的驱动调度

操作系统实验〔第三次〕一、实验内容模拟电梯调度算法，实现对磁盘的驱动调度。二、实验目的磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有假设干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最正确次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低为假设干个输入输出请求效劳所需的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。实验题目模拟电梯调度算法，对磁盘进行移臂和旋转调度。[提示]：〔1〕磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程效劳。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从假设干个等待访问者中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程效劳时，占有处理器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的输入输出请求。为了模拟这种情况，在本实验中设置了一个“接收请求”进程。“驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断处理和处理器调度选择的过程。因而，程序的结构可参考图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中的“启动磁盘”这项工作。程序中使用的数据结构及其说明。constintPCB=100;//定义100个进程intpcbs_num=0;//记录当前io表的进程个数typedefstructprocess//请求io表{charpname[10];//进程名intCylinder;//柱面号intTrack;//磁道号intRecord;//物理记录号intWay;}PROCESS;PROCESSpcbs[PCB];PROCESSa;//记录当前位置〔柱面号、物理记录号〕采用带头节点的循环链表存打印一份源程序并附上注释。#include<iostream>#include<iomanip>#include<stdio.h>#include<cstdlib>#include<fstream>usingnamespacestd;constintPCB=100;//定义100个进程intpcbs_num=0;//记录当前io表的进程个数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()//记录进程总数{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