模拟电梯调度算法，实现对磁盘的驱动调度。
二、实验目的
磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。
三、数据结构
#define M 20
typedef struct PCB {
char proc[M];//进程名 int cylinder_num;//柱面号 int track_num;//磁道号 int phy_num;//物理记录号 struct PCB *next; }PCB;
四、实验题目
模拟电梯调度算法，对磁盘进行移臂和旋转调度。
（1）磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。
由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时，占有处理器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的
输入输出请求。为了模拟这种情况，在本实验中设置了一个“接收请求”进程。
“驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断处理和处理器调度选择的过程。因而，程序的结构可参考图3—1
（2）“接收请求”进程建立一张“请求I/O”表，指出访问磁盘的进程要求访问的物理地址，表的格式为：
进程名 柱面号 磁道号 物理记录号
开始
初始化 输入在[0，1]区间 内的一个随机数
是 否
随机数>1/2
驱动调度 接受请求 是 否 继续？ 结束
图3—1 程序结构
假定某个磁盘组共有200个柱面，由外向里顺序编号（0—199），每个柱面上有20个磁道，编号为0—19，每个磁道分成8个物理记录，编号0—7。进程访问磁盘的物理地址可以用键盘输入的方法模拟得到。图3—2是“接收请求”进程的模拟算法。
在实际的系统中必须把等待访问磁盘的进程排入等待列队，由于本实验模拟驱动调度，为简单起见，在实验中可免去队列管理部分，故设计程序时可不考虑“进程排入等待队列”的工作。
（3）“驱动调度”进程的功能是查“请求I/O”表，当有等待访问磁盘的进程时，按电梯调度算法从中选择一个等待访问者，按该进程指定的磁盘物理地址启动磁盘为其服务。
对移动臂磁盘来说，驱动调度分移臂调度和旋转调度。电梯调度算法的调度策略是与移动臂的移动方向和移动臂的当前位子有关的，所以每次启动磁盘时都应登记移动臂方向和当前位子。电梯调度算法是一种简单而实用的驱动调度方法，这种调度策略总是优先选择与当前柱面号相同的访问请求，从这些请求中再选择一个能使旋转距离最短的等待访问者。如果没有与当前柱面号相同的访问请求，则根据移臂方向来选择，每次总是沿臂移动方向选择一个与当前柱面号最近的访问请求，若沿这个方向没有访问请求时，就改变臂的移动方向。这种调度策略能使移动臂的移动频率极小，从而提高系统效率。用电梯调度算法实现驱动调度的模拟算法如图3－3。 开始 否 有请求？
是 输入：进程 返回 名物理地址
进程排入等待队列 登记“请求I/O表
图 3—2 “接收请求”模拟算法
（4）图3－1中的初始化工作包括，初始化“请求I/O”表，置当前移臂方向为里移；置当前位置为0号柱面，0号物理记录。程序运行前可假定“请求I/O”表中已经有如干个进程等待访问磁盘。
在模拟实验中，当选中一个进程可以访问磁盘时，并不实际地启动磁盘，而用
显示：“请求I/O”表；当前移臂方向；当前柱面号，物理记录号来代替图3－3中的“启动磁盘”这项工作
开始 查”请求I/O表” 否 是 有等待访问者? 返回 否 是 有与当前柱面号相 同的访问者? 选择能使旋转距 是 否 当前移臂方向离最短的访问者 是向里移? 有比当前柱面号有比当前柱面号 大的访问请求? 小的访问请求? 否 是 是 置当前移臂方置当前移臂方 向为向外移 向为向里移 从大于当前柱面号的访问从大于当前柱面号的访问 请求中选择一个最小者 请求中选择一个最小者 添加当前位置：柱面号；物理记录号 启动磁盘，被选中者退出“请求I/O表” 返回 图3-3 电梯调度模拟算法
五、源程序
#include\"stdio.h\" #include\"stdlib.h\" #include\"conio.h\" #include\"string.h\" #define M 20
typedef struct PCB {
char proc[M];//进程名 int cylinder_num;//柱面号 int track_num;//磁道号 int phy_num;//物理记录号 struct PCB *next; }PCB;
PCB *head=NULL;
int direction ;//定义方向，1为up，-1为down PCB *h=NULL; //存放当前运行中的进程的信息
void init () //初始化当前进程 {
h=(PCB *)malloc(sizeof(PCB)); direction=1;
strcpy(h->proc,\"p\"); h->cylinder_num = 0; h->track_num= 0; h->phy_num= 0; }
//模拟记录当前运行进程 void current_process(PCB *Q) {
strcpy(h->proc,Q->proc);
h->cylinder_num = Q->cylinder_num; h->track_num=Q->track_num; h->phy_num=Q->phy_num; }
//插入函数
void insert(PCB *p) {
PCB *q; q=head;
if(head==NULL) head=p; else {
for(q=head;q->next!=NULL;q=q->next); p->next=q->next; q->next=p; } }
void out_info()
{//输出进程的信息
printf(\"┌────┬─────┬───────┬────────┬────┐\\n\");
printf(\"│ 进程名│ 柱面号│ 磁道号 │ 物理记录号 │ 方向 │ \\n\");
printf(\"└────┴─────┴───────┴────────┴────┘ \\n\");
printf(\" %s \%d \%d \%d\ }
void output() {
PCB *p; p=head;
printf(\"进程名柱面号 磁道号 物理记录号\\n\"); if(p==NULL) {
printf(\"---*进程表为空,接收请求或按'n'退出*----\\n\"); } else {
while(p!=NULL) {
printf(\"%s \%d \%d \%d\\n\ p=p->next; } } }
//初始化I/O请求表 void create_PCB() {
PCB *p,*q; q=head; int i,n;
printf(\"\\n\");
printf(\"请输入I/O进程表中进程等待的个数：\\n\"); printf(\"\\n\"); scanf(\"%d\
printf(\"请依次输入进程的相关信息: （用空格分隔）\\n\"); printf(\"━━━━━━━━━━━━━━━\\n\"); printf(\"进程名，柱面号，磁道号，物理记录号\\n\"); for(i=1;i<=n;) { i++;
//printf(\"请输入第%d个进程的信息:\\n\ p=(PCB *)malloc(sizeof(PCB)); scanf(\"%s\
scanf(\"%d\ scanf(\"%d\ scanf(\"%d\ p->next=NULL; insert(p);
} printf(\"━━━━━━━━━━━━━━━\\n\");
}
//接受请求模块
void Receive_requests() {
PCB *p; int i,n,m;
printf(\"请输入一个值: \\n\"); printf(\"1.<接收请求> \\n\"); printf(\"0.<继续执行> \\n\"); scanf(\"%d\ if(i==1) {
printf(\"正在运行的进程为：\\n\"); printf(\"\\n\");
/*if(direction==1) {//启动磁盘 out_info(); printf(\" up\\n\"); printf(\"\\n\"); }
if(direction==-1) {
out_info();
printf(\" down\\n\"); printf(\"\\n\"); }*/
printf(\"\\n\");
printf(\"接受请求前的等待进程表为\\n\"); output();
printf(\"请输入接受等待进程数量\\n\"); scanf(\"%d\
printf(\"请依次输入进程的信息\\n\");
printf(\"进程名，柱面号，磁道号，物理记录号\\n\"); for(m=1;m<=n;m++) {
p=(PCB *)malloc(sizeof(PCB)); scanf(\"%s\
scanf(\"%d\ scanf(\"%d\ scanf(\"%d\ p->next=NULL; insert(p); }
printf(\"接受请求后的等待进程表为：\\n\"); } printf(\"\\n\"); output(); } else
printf(\"没有接受进程，继续往下运行程序\\n\");
//电梯调度算法 void lift() {
int min,cha,max;
PCB *p,*q,*B;//p为指要删除的节点，q为查找的节点，B指向要删除节点的前一个节点 q=head;
if(q!=NULL) {
while((q!=NULL)&&(q->cylinder_num!=h->cylinder_num))//找到第一个相同的柱面号 {
q=q->next; }
if(q==NULL)//没有柱面号相同的等待进程 {
q=head;
if(direction==1)//当前移臂方向up {
while((q!=NULL)&&(q->cylinder_num q=q->next; } if(q==NULL)//没有比当前柱面号大的等待进程 { direction=-1;//置当前移臂方向为外移 q=head;//从小于当前柱面号的访问中选择一个最大的,p指向 p=q; max=q->cylinder_num; q=q->next; while(q!=NULL) { if(max max=q->cylinder_num; p=q;//p指向最大的节点 } q=q->next; } } else//有大于当前柱面号的等待进程 { min=q->cylinder_num; p=q; q=q->next; while(q!=NULL)//大于当前柱面号并且小于指定最小的节点时 { if((h->cylinder_num min=q->cylinder_num; p=q;//p指向最小的节点 } q=q->next; } } } else//当前移臂方向向外 { while((q!=NULL)&&(q->cylinder_num >h->cylinder_num)) { q=q->next; } if(q==NULL)//没有比当前柱面号小的请求 { direction=1; q=head;//从大于当前柱面号的访问中选择一个最小的,p指向 p=q; min=q->cylinder_num; q=q->next; while(q!=NULL) { if(min>q->cylinder_num) { min=q->cylinder_num; p=q;//p指向最小的节点 } q=q->next; } } else//有比当前柱面号小的请求进程 { max=q->cylinder_num; p=q; q=q->next; while(q!=NULL)//从小当前柱面号访问进程中选择一个最大的，用p指向 { if(p->cylinder_num max=q->cylinder_num; p=q;//p指向最大的节点 } q=q->next; } }//else//有比当前柱面号小的请求进程 }//else//当前移臂方向向外 }//if(q==NULL)//没有柱面号相同 else//有柱面号相同的等待进程 { min=q->phy_num-h->phy_num;//第一个相同柱面号设为最小值 p=q;//指向最小的节点，旋转距离最短的访问者 if(min<0) min=-min; q=q->next; while(q!=NULL) { if(q->cylinder_num==h->cylinder_num)//有柱面号相同 { cha=q->phy_num-h->phy_num; if(cha<0) cha=-cha; if(min>cha)//有更小的节点，旋转距离最短的访问者 { min=cha; p=q;//指向最小的节点 } } q=q->next; }//while查找 }//else current_process(p);//保留选中的进程 if(direction==1) {//启动磁盘 printf(\"被选中的等待进程为：\\n\"); printf(\"\\n\"); out_info(); printf(\" up\\n\"); printf(\"\\n\"); } if(direction==-1) { printf(\"被选中的等待进程为：\\n\"); printf(\"\\n\"); out_info(); printf(\" down\\n\"); printf(\"\\n\"); } if(p==head) { head=p->next; } else { B=head; while(B->next!=p)//找到要删除进程的前一个节点 B=B->next; B->next=p->next;//被选中者退出I/O请求表 } }//if(q!=NULL)结束 else { printf(\"请求进程表为空,接收请求或退出\\n\"); } }//电梯调度算法结束 void main()//主函数 { system(\"cls\"); char go='y'; float number; init(); printf(\" -------*执行驱动调度*-------\\n\"); printf(\" ------*当前运行进程为*------\\n\"); out_info(); printf(\" up\\n\"); printf(\" ---*创建I/O请求进程等待表*---\\n\"); create_PCB(); //创建进程链表 printf(\"\\n\"); printf(\"I/O请求进程等待表为：\\n\"); printf(\"\\n\"); output(); while(go=='y'||go!='n') { printf(\"\\n\"); printf(\"输入0~1之间的数：\\n\"); printf(\"大于0.5 <电梯调度> \\n\"); printf(\"小于0.5 <接受请求> \\n\"); scanf(\"%f\ while(number>0.5) { lift(); printf(\"调用电梯驱动调度算法后的I/O请求表为：\\n\"); printf(\"\\n\"); output(); break; } if(number<=0.5) Receive_requests();//调用接受请求模块 {printf(\"是否继续？\\n\"); printf(\" } 七、心得体会 模拟电梯调度算法，实现对磁盘的驱动调度 磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使我理解并且掌握了驱动调度的职能。学到了书上学不到的东西，丰富了知识面收益匪浅，感谢老师的指导 操作系统 实 验 报 告 学 号： 0913063021 姓 名： 张广辉 班 级： 软件工程091 指导老师： 丁 红 南通大学杏林学院 2011年12月 因篇幅问题不能全部显示，请点此查看更多更全内容