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

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

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

3、“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信号和处理器调度策略。 在实验中可用随机数来模拟确定这两个进程的运行顺序， 以代替中断四、 处理和处理器调度选择的过程。因而，程序的结构可参考图31开始随机数1/2二进程名柱面号磁道号物理记录号假定某个磁盘组共有200个柱面，由外向里顺序编号(0199),每个柱面上有20个I/O”表，指出访问磁盘的进程要求访问的物理(2) “接收请求”进程建立一张“请求 地址，表的格式为：图3-1 程序结构结束愉人在0,1区间 内的个随机数初始化驱动调度樱受请求磁道，编号为019,每个磁道分成 8个物理记录，编号 07。进程访问磁盘的物理地址可以用键盘输

4、入的方法模拟得到。图32是“接收请求”进程的模拟算法。图3-2 “接收请求”模拟算法在实际的系统中必须把等待访问磁盘的进程排入等待列队，由于本实验模拟驱动调度，为简单起见，在实验中可免去队列管理部分，故设计程序时可不考虑“进程排入等待队列”的工作。(3) “驱动调度”进程的功能是查“请求 I/O”表，当有等待访问磁盘的进程时，按 电梯调度算法从中选择一个等待访问者，按该进程指定的磁盘物理地址启动磁盘为其服务。 对移动臂磁盘来说，驱动调度分移臂调度和旋转调度。电梯调度算法的调度策略是与 移动臂的移动方向和移动臂的当前位子有关的，所以每次启动磁盘时都应登记移动臂方向和当前位子。电梯调度算法是一种简

5、单而实用的驱动调度方法，这种调度策略总是优先选择与当前柱面号相同的访问请求，从这些请求中再选择一个能使旋转距离最短的等待访问者。如果没有与当前柱面号相同的访问请求，则根据移臂方向来选择，每次总是沿臂移动方向选择一个与当前柱面号最近的访问请求，若沿这个方向没有访问请求时，就改变臂的移动方向。这种调度策略能使移动臂的移动频率极小，从而提高系统效率。用电梯调度算法实现驱动调度的模拟算法如图 3 3。(4)图3- 1中的初始化工作包括，初始化“请求 I/O ”表，置当前移臂方向为里移；置当前位置为0号柱面，0号物理记录。程序运行前可假定“请求I/O”表中已经有如干个进程等待访问磁盘。在模拟实验中，当选

6、中一个进程可以访问磁盘时，并不实际地启动磁盘，而用显示：“请求I/O ”表；当前移臂方向；当前柱面号，物理记录号来代替图3-3中的“启动磁盘”这项工作。(1)程序中使用的数据结构及其说明const int PCB=100; 定义 100 个进程int pcbs_num=0; /记录当前io表的进程个数typedef struct process / 请求 io 表char pname10; / 进程名int Cylinder; / 柱面号int Track; / 磁道号int Record; / 物理记录号int Way;PROCESS;PROCESS pcbsPCB;PROCESS a; /

7、记录当前位置(柱面号、物理记录号)采用带头节点的循环链表存 (2)打印一份源程序并附上注释。(3) #include (4) #include (5) #include (6) #include #include (8) using namespacestd;(9) const int PCB = 100; / 定义 100 个进程(10) int pcbs_num = 0;记录当前io表的进程个数(11) typedef struct process / 请求 io 表(12) (13) char pname10; / 进程名(14) intCylinder;/ 柱面号(15) intTra

8、ck;/磁道号(16) intRecord;/ 物理记录号(17) intWay;(18) PROCESS(19) PROCESpcbsPCB;(20) PROCESS(21) void init_a()/设置当前位置(22) (23) a.Cylinder = 4;(24) a.Track = 0;(25) a.Record = 0;(26) (27) int count_PN() / 记录进程总数(28) (29) inti;(30) for(i = 0; pcbsi.Cylinder !=NULLi+)(31) (32) (33) cout i endl;(34) return i;(3

9、5) (36) void accept() /接受请求模拟算法(37) (38) cout 输入进程名和物理地址(柱面号，磁道号，物理记录号) pcbspcbs_num.pname pcbspcbs_num.Cylinder pcbspcbs_num.Track pcbspcbs_num.Record;(40) pcbs_num+;(41) (42) int Cylinder_e()/判断柱面号相等(43) (44) for (int i = 0; ipcbs_num; i+)(45) (46) if (pcbsi.Cylinder = a.Cylinder)(47) return i;(48

10、) (49) return 0;(50) (51) int Cylinder_near( int cylinder , int record ) / 选择当前柱面号的访问者中物理块号最近的(52) (53) int t = 8, a, 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)

11、 (65) (66) return k;(67) (68) int Cylinder_max( int cylinder )/选择比当前柱面号大的请求中柱面号最小的(69) (70) int num, t = 199, i, a = 0, b = 0;(71) for (i = 0; i pcbs_num; i+)(72) (73) if (abs(pcbsi.Cylinder - cylinder ) cylinder )(75) t = abs(pcbsi.Cylinder - cylinder );(76) (77) num = cylinder + t;/ 选择的柱面号(78) t =

12、 8;/物理块号最大相差7(79) for (i = 0; ipcbs_num; i+)(80) (81) if(pcbsi.Cylinder = num &pcbsi.Record t)(82) (83) t = pcbsi.Record; a = i;(84) (85) (86) return a;(87) (88) int Cylinder_max1( int cylinder )(89) (90) int t = 199, i, b = 0, c = 0;(91) for (i = 0; ib & pcbsi.Cylinder cylinder )(94) (95) b = abs(p

13、cbsi.Cylinder - cylinder );(96) (97) (98) return b;(99) (100) int Cylinder_min( int cylinder )/选择比当前柱面号小的请求中柱面号最大的(101) (102) int num, t = 199, i, a = 0;for (i = 0; i pcbs_num; i+)(103) (104) if (abs(pcbsi.Cylinder - cylinder )t & pcbsi.Cylinder cylinder )(105) (106) t = abs(pcbsi.Cylinder - cylinde

14、r );(107) (108) (109) num = cylinder - t; t = 8;/物理块号相差最大为 7(110) for (i = 0; i pcbs_num; i+)(111) (112) if(pcbsi.Cylinder = num & pcbsi.Record t)(113) (114) t = pcbsi.Record; a = i;(115) (116) (117) return a;/返回柱面号小的请求中柱面号最大的下标(118) (119) void delete_scan( int x)(120) (121) for ( int i = x; ipcbs_n

15、um; 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; ipcbs_num; i+)(129) (130) cout setfill( ) setw(6) pcbsi.pname setfill( ) setw(8) pcbsi.Cylinder setfill( ) setw(8) pcbsi.Track se

16、tfill( ) setw(10) pcbsi.Record endl;(131) (132) (133) void print_scan( bool x)(134) (135) 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 setll( ) setw(6) x endl;(136) (137) int SCA

17、N() /驱动调度 电梯调度模拟算法(138) (139) print_io();/ 打印 io 表(140) int scan;(141) int scan1; /scan为选择的进程的编号(142) bool way = 1;/ 方向 0=out 1=in(143) if (a.Cylinder =NULL(144) (145) init_a();(146) (147) if (pcbs_num = 0)(148) (149) cout 无等待访问者 endl; return 0;(150) (151) else(152) (153) if (pcbsCylinder_e().Cylind

18、er = a.Cylinder)/ 选择能使旋转距离最短的访问者(154) (155) scan = Cylinder_near(a.Cylinder, a.Record); / 选择当前柱面号的访问者中最近的(156)if (pcbsscan.Cylindera.Cylinder)(157)(158)way = 0;(159)(160)else way = 1;(161)(162)else(163)(164)if (way = 1)(165)(166)scan = Cylinder_max(a.Cylinder);/选择比当前柱面号大的请求中物理块号最小的(167)scan1 = Cylin

19、der_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 = pcbsscan;(184)delete_scan(scan);/ 删除 pcbsscan(185)print_scan(way);/ 打印(186)return 1;(187)(188) (189) void work() / 初始化(190) (191)floatn; char y