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

1、系统（第三次）一、实验内容模拟电梯调度算法，实现对磁盘的驱动调度。二、实验目的磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅 助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求 访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问 磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低 为若干个输入输出请求服务所需的总时间，从而提高系统效率。本实验要求学生模拟设计一 个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度 的职能。三、实验题目模拟电梯调度算法

2、，对磁盘进行移臂和旋转调度。提示：（1）磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。 当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访问者 中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时，占有处理 器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的输入输出请求。为了模拟这种情况，在本实验中设置了一个“接收请求”进程。驱动调度”进程和“接收请求”进程能否占有处

3、理器运行，取决于磁盘的结束中断信 号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断四、处理和处理器调度选择的过程。因而，程序的结构可参考图31（2）“接收请求”进程建立一张“请求I/O”表，指出访问磁盘的进程要求访问的物理地址，表的格式为：假定某个磁盘组共有200个柱面，由外向里顺序编号（0199），每个柱面上有20个 磁道，编号为019，每个磁道分成8个物理记录，编号07。进程访问磁盘的物理地址 可以用键盘输入的方法模拟得到。图32是“接收请求”进程的模拟算法。 在实际的系统中必须把等待访问磁盘的进程排入等待列队，由于本实验模拟驱动调 度，为简单起见，在实验中

4、可免去队列管理部分，故设计程序时可不考虑“进程排入等待队 列”的工作。（3）“驱动调度”进程的功能是查“请求I/O”表，当有等待访问磁盘的进程时，按电梯调度算法从中选择一个等待访问者，按该进程指定的磁盘物理地址启动磁盘为其服务。 对移动臂磁盘来说，驱动调度分移臂调度和旋转调度。电梯调度算法的调度策略是与 移动臂的移动方向和移动臂的当前位子有关的，所以每次启动磁盘时都应登记移动臂方向和 当前位子。电梯调度算法是一种简单而实用的驱动调度方法，这种调度策略总是优先选择与 当前柱面号相同的访问请求，从这些请求中再选择一个能使旋转距离最短的等待访问者。如 果没有与当前柱面号相同的访问请求，则根据移臂方向

5、来选择，每次总是沿臂移动方向选择 一个与当前柱面号最近的访问请求，若沿这个方向没有访问请求时，就改变臂的移动方向。 这种调度策略能使移动臂的移动频率极小，从而提高系统效率。用电梯调度算法实现驱动调 度的模拟算法如图33。（4）图31中的初始化工作包括，初始化“请求I/O”表，置当前移臂方向为里移； 置当前位置为0号柱面，0号物理记录。程序运行前可假定“请求I/O”表中已经有如干个 进程等待访问磁盘。在模拟实验中，当选中一个进程可以访问磁盘时，并不实际地启动磁盘，而用显示:求I/O”表；当前移臂方向；当前柱面号，物理记录号来代替图3-3中的“启动磁盘”这项工作。(1)程序中使用的数据结构及其说明

6、。con st int PCB=100; /定义100个进程int pcbs_num=0; /记录当前io表的进程个数typedef struct process /请求io表“请char pn ame10; /进程名int Cyli nder; /柱面号int Track; /磁道号int Record; /物理记录号int Way;PROCESS;PROCESS pcbsPCB;PROCESS a; /记录当前位置(柱面号、物理记录号)采用带头节点的循环链表存(2)打印一份源程序并附上注释。(3) #i nclude(4) #i nclude(5) #i nclude#i nclude#i

7、n clude(8)using namespacestd;(9)const int PCB = 100;/ 定义 100 个进程(10)int pcbs_num = 0;/记录当前 io 表的进程个数(35) (11)typedef struct process / 请求 io 表（(13)char pname10;/ 进程名(14)int Cylinder; / 柱面号(15)int Track;/ 磁道号（int Record; /物理记录号(17)int Way;(18) PROCESS(19) PROCESpbbsPCB;(20) PROCESS(21) void in it a()/

8、设置当前位置(22) (23)a.Cyli nder = 4;(24)a.Track = 0;(25)a.Record = 0;(26) (27) int count_PN()/记录进程总数(28) (29)int i;(30)for (i = 0; pcbsi.Cylinder !=NULL i+)(31)(32)(33)cout i en dl;(34)return i;(36) void accept。 II 接受请求模拟算法(37) (38)cout 输入进程名和物理地址(柱面号，磁道号， 物理记录号)“ pcbspcbs_ num.p name pcbspcbs_ num.Cyli

9、nder pcbspcbs_ num.Track pcbspcbs_ num.Record;(40)pcbs_ num+;(41) (42) intCylinder_e()/判断柱面号相等(43) (44)for (int i = 0; ipcbs_num; i+)(45)(46)if (pcbsi.Cylinder = a.Cylinder)(47)return i;(48)(49)return 0;(50) (51) intCylinder_near(int cylinder , int record ) /选择当前柱面号的访问者中物理块号最近的(52) (53)int t = 8, a,

10、 k;(54)for (int i = 0; ipcbs_num; i+)(55)(56)if (pcbsi.Cylinder =cylinder )(57)(58)a = pcbsi.Record -record ;(59)if (a0) a = a + 8; (60)if (at)(61)(62)t = a; k = i;(63)(64)(65)(66)return k;(67) (68) intCylinder_max( int cylinder )/选择比当前柱面号大的请求中柱面号最小的(69) (70)int num, t = 199, i, a = 0, b = 0;|(71)fo

11、r (i = 0; i pcbs_ num; i+)(72)(73)if (abs(pcbsi.Cylinder -cylinder )cylinder )(74)(75)t = abs(pcbsi.Cylinder -cylinder );(76)(77) num =cylinder + t;/选择的柱面号(78)t = 8;/物理块号最大相差 7(79)for (i = 0; ipcbs_ num; i+)(80)(81)if (pcbsi.Cylinder = num &pcbsi.Record t)(82)t = pcbsi.Record; a = i;(83)(84)(85)(86)

12、return a;(87) (88) intCylinder_max1( int cylinder )(89) (90)int t = 199, i, b = 0, c = 0;(91)for (i = 0; ib & pcbsi.Cylinder cyli nder(94)(95)b = abs(pcbsi.Cyli nder -cylinder );(96)(97)(98)return b;(99) (100) int Cylinder_min( int cylinder )/选择比当前柱面号小的请求中柱面号最大的(101) (102)int num, t = 199, i, a = 0;

13、for (i = 0; i pcbs_num; i+)(103)(104)if (abs(pcbsi.Cylinder -cylinder )t & pcbsi.Cylinder cylinder )(105)(106)t = abs(pcbsi.Cyli nder -cylinder );(107)(84)(108)(154)(109)num = cyli nder - t; t = 8;(110)for (i = 0; i pcbs_num; i+)(111)(112)if(pcbsi.Cylinder = num & pcbsi.Record t)(113)(114)t = pcbsi.

14、Record; a = i;(115)(116)(117)return a;/返回柱面号小的请求中柱面号最大的下标(118) (119) void delete_scan( int x)(120) (121)for (int i = x; ipcbs_num; i+)(122)pcbsi = pcbsi + 1; pcbs_ num-;(123) (124)void print_io()/ 打印请求 io 表(125) (126)cout 输岀 请求 i/o 表： endl;(127)cout 进程名“ “ 柱面号 “ 磁道号 物理记录号 endl;(128)for (int i = 0; i

15、pcbs_num; i+)(129)(130)cout setfill( ) setw(6) pcbsi.pname setfill( ) setw(8) pcbsi.Cylinder setfill( ) setw(8) pcbsi.Track setfill( ) setw(10) pcbsi.Record en dl;(131)/物理块号相差最大为 7(132) (133)void print_scan( bool x)(134) (135)cout 选中的：“ endl; cout 进程名“ 柱面号“ “ 磁道号 物理记录号 方向 endl; cout setfill( ) setw(

16、6) a.pname setfill( ) setw(8) a.Cylinder setfill() setw(10) a.Track setfill() setw(10) a.Record setfill() setw(6) x en dl;(136) (137) int SCAN()/驱动调度电梯调度模拟算法(138) (139)prin t_io();/打印 io 表(140)int scan;(141)int scan1; /scan 为选择的进程的编号 |(142)bool way = 1;/ 方向 O=out 1=in |(143)if (a.Cylinder =：=NULL(14

17、4)(145)ini t_a();(146)(147)if (pcbs_num = =0)(148)(149)cout 无等待访问者 endl;return 0(150)(151)else(152)(154)(153)if (pcbsCylinder_e().Cylinder = a.Cylinder)/选择能使旋转距离最短的访问者(155)scan = Cylinder_near(a.Cylinder,a.Record); /选择当前柱面号的访冋者中最近的(156)if (pcbsscan.Cylinderva.Cylinder)(157)(158)way = 0;(159)(160)els

18、e way = 1;(161)(162)else(163)(164)if (way = 1)(165)(166)sca n = Cyli nder_max(a.Cyli nder);/选择比当前柱面号大的请求中物理块号最小的(167)sca n1 = Cyli nder_max1(a.Cyli nder);(168)if (scan = scan1)(169)(170)sca n = Cyli nder_ min( a.Cylinder);/选择比当前柱面号小的请求中物理块号最大的(171)way = 0;(172)(173)(174)else(175)(176)sca n = Cyli nder_ min( a.Cyli nder);(177)if (scan = 0)(178)(179)(180)sea n = Cyli nder_max(a.Cyli nder);way = 1;(181)(182)(183) a = pcbssca n;(184)delete_sca n( sea n);/ 删除 pcbsscan(185)prin t_sca n( way);/打印(186)return 1;(187)(188) (189) void work() /初始化(190) (191)float n; c