一、实验内容
模拟电梯调度算法，实现对磁盘的驱动调度。
二、实验目的
磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出任务。在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。
三、实验题目
模拟电梯调度算法，对磁盘进行移臂和旋转调度。
(1)磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访向者中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度"进程来完成。
由于磁盘与处理器是可以并行工作的，所以当磁盘在作为一个进程服务时，占有处理器的另一进程可以提出使用磁盘的要求。也就是说，系统能动态地接收新的输入输出请求。为了模拟这种情况，在本实验中设置了一个“接收请求”进程。
“驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断处理和处理器调度选择的过程。因而，程序的结构可参考图。
| 进程名 | 柱面号 | 磁道号 | 物理记录号 |
假定某个磁盘组共有200个柱面，由外向里顺序编号(0-199),每个柱面上有20个磁道，编号为0-19，每个磁道分成8个物理记录，编号0-7。进程访问磁盘的物理地址可以用键盘输入的方法模拟得到。图2是“接收请求”进程的模拟算法。
在实际的系统中必须把等待访问磁盘的进程排入等待队列，由于本实验模拟驱动调度，为简单起见，在实验中可免去队列管理部分，故设计程序时可不考虑“进程排入等待队列”的工作。
(3)“驱动调度”进程的功能是查“请求I/O”表，当有等待访问磁盘的进程时，按电梯调度算法从中选择一个等待访问者，按该进程指定的磁盘物理地址启动磁盘为其服务。
对移动臂磁盘来说，驱动调度分移臂调度和旋转调度。电梯调度算法的调度策略是与移动臂的移动方向和移动臂的当前位置有关的，所以每次启动磁盘时都应登记移动臂方向和当前位置。电梯调度算法是一种简单而实用的驱动调度方法，这种调度策略总是优先选择与当前柱面号相同的访问请求，从这些请求中再选择一个能使旋转距离最短的等待访问者。如果没有与当前柱面号相同的访问请求，则根据移臂方向来选择，每次总是沿臂移动方向选择一个与当前柱面号最近的访问请求，若沿这个方向没有访问请求时，就改变臂的移动方向。这种调度策略能使移动臂的移动频率极小，从而提高系统效率。用电梯调度算法实现驱动调度的模拟算法如图。(实验指导书上的流程图有误！！！)
(4)图1中的初始化工作包括：初始化“请求1/O”表、置当前移臂方向为向里移，置当前位置为0号柱面、0号物理记录。程序运行前可假定“请求I/O"表中已经有若干个进程等待访问磁盘。
在模拟实验中，当选中一个进程可以访问磁盘时，并不实际地启动磁盘，而用显示：“请求I/0”表、当前移臂方向、当前柱面号、物理记录号来代替图3
中的“启动磁盘”这项工作。
四、实验报告
（1）实验题目
见上文
（2）程序中使用的数据结构及其说明
数据结构：
请求I/O表：需要说明的是，请求I/O表的数据项与实验指导书略有不同（实验指导书可能有误！！！），每个数据项的四个属性分别为进程id、柱面号、盘面号、扇区号。
struct process { int id; int cylinder; int track; int sector; };
请求I/O表用到的物理结构不是数组，而是采取了可变长数组vector。因为要频繁地查表并得知请求I/O表的进程数量，所以利用vector的size()属性可以方便地得知当前进程数量而无需我们手动维护。
vector<process> iorequests;
因为是模拟程序，所以我们可以直接将当前移臂方向、当前柱面号、当前扇区号都直接设置为全局变量。
bool direction;//0 up,1down int curCylinder; int curSector;
在模拟调度中，需要记录是否有与当前柱面号相同的访问者。同样的，这些访问者也可以用一个vector暂存。
vector<int> sameCylinderpos;//当前柱面号相同访问者
（3）打印一份源程序并附上注释
1.程序说明
main函数执行两个函数，分别为初始化与模拟cpu运行。
int main() { init(); cpuwork(); }
初始化时，将当前移臂方向为向里移，当前柱面号为0号柱面，当前扇区号为0号扇区。
void init() { direction = 0; curCylinder = 0; curSector = 0; direction = 0; }
处理机工作，与图1是一致的。生成随机数，并根据随机数决定当前在驱动调度或接受请求。
void cpuwork() { srand(time(NULL)); while (1) { cout << "1. Drive scheduling 2.Accept Requests"; double opnum= rand() / double(RAND_MAX); if (opnum > 0.5) driveScheduling(); else acceptRequest(); cout << "Continue?Y/N"; char op; cin >> op; if (op == 'Y'); else break; } }
在接受请求时，简化了进程进入等待队列。但是仍然会输入与登记I/O请求表。
void acceptRequest() { cout << "\nAccepting requests!"; cout << "\ninput request num:"; int n; cin >> n; if (n == 0) {//不发送请求 cout << "No requests!"; return; } else while(n--) { cout << "input process id,cylinder,track,sector"; int id, cylinder, track, sector; cin >> id >> cylinder >> track >> sector; process newp(id, cylinder, track, sector); iorequests.push_back(newp); } }
在电梯模拟调度算法中，为了减少对I/O请求表的遍历次数，本程序采用的流程与流程图略有区别。先遍历数组，利用vector sameCylinderpos记录与当前柱面号相同的访问者。若这个可变长数组长度大于0，则说明有与当前柱面号相同的访问者。在遍历数组过程中，同时利用标记与位置值判断有无并找到大于当前柱面号的请求中的最小者和小于当前柱面号请求的最大者。
需要着重说明的是流程图中有一个步骤是“选择能使旋转距离最短的访问者”。由于磁盘只能一个方向旋转，所以在这一步骤中需要进行一定的数学处理。记请求的扇区号为y，磁盘当前扇区号为x。磁盘的某一个柱面的一个盘面上8个扇区。可以利用简单的数学知识，统一地用一个式子对磁盘旋转记录进行表示：(x+8-y)%8。例如，磁盘当前在4号扇区，有一个请求在7号扇区，则(7+8-4)%8=3，磁盘要转动3个单位。还有个请求在1号扇区，则(1+8-4)%8=5，磁盘要转动五个单位。
若没有与当前柱面号相同的访问者，则剩余过程与实验指导书类似，但是对请求的判断与选择如上文所述，都是在第一次对数组的遍历时处理好。
void driveScheduling() {//驱动调度 if (iorequests.empty()) //当前有无等待访问者 return; else { bool sameCylinder = 0;//有无与当前柱面号相同访问者 bool greaterCylinder = 0;//有无大于当前柱面号访问者 bool lesserCylinder = 0;//有无小于当前柱面号访问者 sameCylinderpos.clear(); int mingtCylinderpos=-1;//大于当前柱面号的最小者 int maxltCylinderpos=-1;//小于当前柱面号的最大者 int iorequestPos=0;//位置 for (int i = 0; i < iorequests.size(); i++) {//判断有无与当前柱面号相同访问者，比当前大的请求、比当前小的请求 if (iorequests[i].cylinder == curCylinder) { sameCylinder = 1; sameCylinderpos.push_back(i);//与当前柱面号相同的访问者，放入可变长数组中暂存 } if (iorequests[i].cylinder > curCylinder) {//从大于当前柱面号请求中选一个最小者 greaterCylinder = 1; if (mingtCylinderpos == -1) mingtCylinderpos = i; if (iorequests[i].cylinder < iorequests[mingtCylinderpos].cylinder) mingtCylinderpos = i; } if (iorequests[i].cylinder < curCylinder) {//从小于当前柱面号请求中选一个最大者 lesserCylinder = 1; if (maxltCylinderpos == -1) maxltCylinderpos = i; if (iorequests[i].cylinder > iorequests[maxltCylinderpos].cylinder) maxltCylinderpos = i; } } if (sameCylinder == 1) {//选使得旋转距离最短的访问者 int rotateDist = 20; iorequestPos = sameCylinderpos[0]; for (int i=0;i<sameCylinderpos.size();i++) { int pos = sameCylinderpos[i]; int& x = iorequests[pos].sector; int& y = curSector; int dist = ((x+8-y)%8); if (dist < rotateDist) {//选择能使旋转距离最短的访问者 rotateDist = dist; iorequestPos = pos; } } } else { if (direction == 0) { if (greaterCylinder) iorequestPos = mingtCylinderpos; else { direction = 1;//置移臂方向 iorequestPos = maxltCylinderpos; } } else { if (lesserCylinder) iorequestPos = maxltCylinderpos; else { direction = 0;//置移臂方向为往里 iorequestPos = mingtCylinderpos; } } } curCylinder = iorequests[iorequestPos].cylinder; curSector = iorequests[iorequestPos].sector; iorequests.erase(iorequests.begin() + iorequestPos); } }
