操作系统驱动调度

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

2、 typedef struct PCB char procM;/进程名 int cylinder_num;/柱面号 int track_num;/磁道号 int phy_num;/物理记录号 struct PCB *next; PCB; 四、实验题目模拟电梯调度算法，对磁盘进行移臂和旋转调度。（1）磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成

3、。 由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时，占有处理器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的输入输出请求。为了模拟这种情况，在本实验中设置了一个“接收请求”进程。“驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断处理和处理器调度选择的过程。因而，程序的结构可参考图31（2） “接收请求”进程建立一张“请求I/O”表，指出访问磁盘的进程要求访问的物理地址，表的格式为：进程名柱面号磁道号物理记录号初始化输入在0，1区间内的一个随机数随机数&g

4、t;1/2开始驱动调度接受请求继续？结束是是否否 图31 程序结构假定某个磁盘组共有200个柱面，由外向里顺序编号（0199），每个柱面上有20个磁道，编号为019，每个磁道分成8个物理记录，编号07。进程访问磁盘的物理地址可以用键盘输入的方法模拟得到。图32是“接收请求”进程的模拟算法。在实际的系统中必须把等待访问磁盘的进程排入等待列队，由于本实验模拟驱动调度，为简单起见，在实验中可免去队列管理部分，故设计程序时可不考虑“进程排入等待队列”的工作。（3）“驱动调度”进程的功能是查“请求I/O”表，当有等待访问磁盘的进程时，按电梯调度算法从中选择一个等待访问者，按该进程指定的磁盘物理地址启动磁

5、盘为其服务。对移动臂磁盘来说，驱动调度分移臂调度和旋转调度。电梯调度算法的调度策略是与移动臂的移动方向和移动臂的当前位子有关的，所以每次启动磁盘时都应登记移动臂方向和当前位子。电梯调度算法是一种简单而实用的驱动调度方法，这种调度策略总是优先选择与当前柱面号相同的访问请求，从这些请求中再选择一个能使旋转距离最短的等待访问者。如果没有与当前柱面号相同的访问请求，则根据移臂方向来选择，每次总是沿臂移动方向选择一个与当前柱面号最近的访问请求，若沿这个方向没有访问请求时，就改变臂的移动方向。这种调度策略能使移动臂的移动频率极小，从而提高系统效率。用电梯调度算法实现驱动调度的模拟算法如图33。 开始有请求

6、？输入：进程名物理地址进程排入等待队列登记“请求I/O表返回是否 图 32 “接收请求”模拟算法（4）图31中的初始化工作包括，初始化“请求I/O”表，置当前移臂方向为里移；置当前位置为0号柱面，0号物理记录。程序运行前可假定“请求I/O”表中已经有如干个进程等待访问磁盘。在模拟实验中，当选中一个进程可以访问磁盘时，并不实际地启动磁盘，而用显示：“请求I/O”表；当前移臂方向；当前柱面号，物理记录号来代替图33中的“启动磁盘”这项工作开始查”请求I/O表”否是有等待访问者?有与当前柱面号相同的访问者?否是返回选择能使旋转距离最短的访问者当前移臂方向是向里移?否是有比当前柱面号大的访问请求?有比

7、当前柱面号小的访问请求?否是是置当前移臂方向为向里移置当前移臂方向为向外移从大于当前柱面号的访问请求中选择一个最小者从大于当前柱面号的访问请求中选择一个最小者添加当前位置：柱面号；物理记录号启动磁盘，被选中者退出“请求I/O表”图3-3 电梯调度模拟算法返回五、源程序#include"stdio.h" #include"stdlib.h" #include"conio.h" #include"string.h" #define M 20 typedef struct PCB char procM;/进程名 int

8、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-

9、>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);

10、 p->next=q->next; q->next=p; void out_info() /输出进程的信息 printf("n"); printf(" 进程名 柱面号 磁道号 物理记录号 方向 n"); printf(" n"); printf(" %s t%d t%d t%d",h->proc,h->cylinder_num,h->track_num,h->phy_num); void output() PCB *p; p=head; printf("进程名柱面

11、号 磁道号 物理记录号n"); if(p=NULL) printf("-*进程表为空,接收请求或按'n'退出*-n"); else while(p!=NULL) printf("%s t%d t%d t%dn",p->proc,p->cylinder_num,p->track_num,p->phy_num); p=p->next; /初始化I/O请求表void create_PCB() PCB *p,*q; q=head; int i,n; printf("n"); printf

12、("请输入I/O进程表中进程等待的个数：n"); printf("n"); scanf("%d",&n); printf("请依次输入进程的相关信息: （用空格分隔）n"); printf("n"); printf("进程名，柱面号，磁道号，物理记录号n"); for(i=1;i<=n;) i+; /printf("请输入第%d个进程的信息:n",i); p=(PCB *)malloc(sizeof(PCB); scanf("%s&

13、quot;,&p->proc); scanf("%d",&p->cylinder_num); scanf("%d",&p->track_num); scanf("%d",&p->phy_num); p->next=NULL; insert(p); printf("n"); /接受请求模块void Receive_requests() PCB *p; int i,n,m; printf("请输入一个值: n"); printf(&quo

14、t;1.<接收请求> n"); printf("0.<继续执行> n"); scanf("%d",&i); if(i=1) printf("正在运行的进程为：n"); printf("n"); /*if(direction=1) /启动磁盘 out_info(); printf(" upn"); printf("n"); if(direction=-1) out_info(); printf(" downn");

15、printf("n"); */ printf("n"); printf("接受请求前的等待进程表为n"); output(); printf("请输入接受等待进程数量n"); scanf("%d",&n); printf("请依次输入进程的信息n"); printf("进程名，柱面号，磁道号，物理记录号n"); for(m=1;m<=n;m+) p=(PCB *)malloc(sizeof(PCB); scanf("%s"

16、,&p->proc); scanf("%d",&p->cylinder_num); scanf("%d",&p->track_num); scanf("%d",&p->phy_num); p->next=NULL; insert(p); printf("接受请求后的等待进程表为：n"); printf("n"); output(); else printf("没有接受进程，继续往下运行程序n"); /电梯调度算法v

17、oid 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 <h->cyl

18、inder_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<q->cylinder_num) max=q->cylinder_num; p=q;/p指向最大的节点 q=q->next; else/有大于当前柱面号的等待进程 min=q->cylinder_num; p=q; q=q-&

19、gt;next; while(q!=NULL)/大于当前柱面号并且小于指定最小的节点时 if(h->cylinder_num<q->cylinder_num)&&(q->cylinder_num<p->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)/

20、没有比当前柱面号小的请求 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指向

21、if(p->cylinder_num<q->cylinder_num&&q->cylinder_num<h->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<

22、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("被选中的等待

23、进程为：n"); printf("n"); out_info(); printf(" upn"); printf("n"); if(direction=-1) printf("被选中的等待进程为：n"); printf("n"); out_info(); printf(" downn"); printf("n"); if(p=head) head=p->next; else B=head; while(B->next!=p)/找到要删

24、除进程的前一个节点 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(" upn"); printf(" -*创建I/O请求进程等待表*-n"); create_PCB(); /创建进程链表 printf("n"); printf("I/O请求进程等待表为：n"); printf("n"); output(); while(go='y'|go!='n') printf("n&qu