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

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中的“启动磁盘”这项工作。(

6、1)程序中使用的数据结构及其说明。(2)con st int PCB=100;ylin der != NULL i+)“请(3)(4)(5)cout i pcbspcbs_num.Cylinder pcbspcbs_num.Track pcbspcbs_ num.Record;(9)pcbs_ num+;(10) (11) int Cylinder_e() ylinder =(12)return i;(13)(14)return 0;(15)(16)int Cylinder_near( intcylinder , int record ) ylinder =cylinder )(17)(18)

7、a = pcbsi.Record -record ;(19)if (a0) a = a + 8; (20)if (at)(21)(45)(22)t = a; k = i;(23)(24)(25)(26)return k;(27) (28) int Cylinder_max( int cylinder ) ylinder -cylinder )cylinder )(29)(30)t = abs(pcbsi.Cylinder -cylinder );(31)(32) num =cyli nder + t;yli nder = num &pcbsi.Record t)|(33)(34)t =

8、 pcbsi.Record; a = i;(35)(36)(37)return a;(38) (39) int Cylinder_max1( int cylinder )(40) (41)int t = 199, i, b = 0, c = 0;(42)for (i = 0; ib & pcbsi.Cylinder cylinder )(47)(48)(49)return b;(50)(51)int Cylinder_min( int cylinder ) ylinder -cylinder )t & pcbsi.Cylinder cylinder )(52)(53)t = a

9、bs(pcbsi.Cylinder -cylinder );(54)(55)(56)num = cyli nder - t; t = 8; yli nder = num & pcbsi.Record t)(57)(58)t = pcbsi.Record; a = i;(59)(60)(61)return a; name setfill( ) setw(8) pcbsi.Cylinder setfill( ) setw(8) pcbsi.Track setfill( ) setw(10) pcbsi.Record en dl;(62)(63)(64)void print_scan(boo

10、l x)(65)(66)cout 选中的： endl; cout 进程名 “ 柱面号 “ 磁道号 物理记录号 方向 endl; cout setfill( ) setw(6) setfill() setw(8) setfill( ) setw(10) setfill( ) setw(10) setfill( ) setw(6) x endl;(46)b = abs(pcbsi.Cyli nder -cylinder );(67)(68) intSCAN() ylinder = yli nderv(69)(70)way = 0;(71)(72)else way = 1;(73)(74)else(

11、75)(76)if (way = 1)(77)(78)scan = Cylinder_max;/选择比当前柱面号大的请求中物理块号最小的(79)sca n1 = Cyli nder_max1;(80)if (scan = scan1)(81) (82)scan = Cylinder_min;/选择比当前柱面号小的请求中物理块号最大的way = 0;(84)(85)(86)else(87)(88)sca n = Cyli nder_min;(89)if (scan = 0)(83)(90)sea n = Cyli nder_max;(92)way = 1;(93)(94)(95) a = pcbssca n;(96)delete_scan(scan);/ 删除 pcbsscan(97)print_scan(way);/ 打印(98)return 1;(99)(100) (101) void work() / 初始化(102) (103)float n; char y =y ;while (y =y| y =Y)(104)(105)cout 输入在0 , 1区间内的一个随机数 n;(107)if (n(108)(109)SCAN(); /驱动调度(110)(111)el