操作系统驱动调度

实验三驱动调度一、实验内容模拟电梯调度算法，实现对磁盘的驱动调度。二、实验目的磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。三、数据结构#defineM20typedefstructPCB{charproc[M];//进程名intcylinder_num;//柱面号inttrack_num;//磁道号intphy_num;//物理记录号structPCB*next;}PCB;四、实验题目模拟电梯调度算法，对磁盘进行移臂和旋转调度。（1）磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时，占有处理器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的输入输出请求。为了模拟这种情况，在本实验中设置了一个“接收请求”进程。“驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断处理和处理器调度选择的过程。因而，程序的结构可参考图3—1（2）“接收请求”进程建立一张“请求I/O”表，指出访问磁盘的进程要求访问的物理地址，表的格式为：进程名柱面号磁道号物理记录号图3—1程序结构初始化输入在[0，1]区间内的一个随机数随机数1/2开始驱动调度接受请求继续？结束是是否否假定某个磁盘组共有200个柱面，由外向里顺序编号（0—199），每个柱面上有20个磁道，编号为0—19，每个磁道分成8个物理记录，编号0—7。进程访问磁盘的物理地址可以用键盘输入的方法模拟得到。图3—2是“接收请求”进程的模拟算法。在实际的系统中必须把等待访问磁盘的进程排入等待列队，由于本实验模拟驱动调度，为简单起见，在实验中可免去队列管理部分，故设计程序时可不考虑“进程排入等待队列”的工作。（3）“驱动调度”进程的功能是查“请求I/O”表，当有等待访问磁盘的进程时，按电梯调度算法从中选择一个等待访问者，按该进程指定的磁盘物理地址启动磁盘为其服务。对移动臂磁盘来说，驱动调度分移臂调度和旋转调度。电梯调度算法的调度策略是与移动臂的移动方向和移动臂的当前位子有关的，所以每次启动磁盘时都应登记移动臂方向和当前位子。电梯调度算法是一种简单而实用的驱动调度方法，这种调度策略总是优先选择与当前柱面号相同的访问请求，从这些请求中再选择一个能使旋转距离最短的等待访问者。如果没有与当前柱面号相同的访问请求，则根据移臂方向来选择，每次总是沿臂移动方向选择一个与当前柱面号最近的访问请求，若沿这个方向没有访问请求时，就改变臂的移动方向。这种调度策略能使移动臂的移动频率极小，从而提高系统效率。用电梯调度算法实现驱动调度的模拟算法如图3－3。图3—2“接收请求”模拟算法（4）图3－1中的初始化工作包括，初始化“请求I/O”表，置当前移臂方向为里移；置当前位置为0号柱面，0号物理记录。程序运行前可假定“请求I/O”表中已经有如干个进程等待访问磁盘。在模拟实验中，当选中一个进程可以访问磁盘时，并不实际地启动磁盘，而用开始有请求？输入：进程名物理地址进程排入等待队列登记“请求I/O表返回是否是是是是是否否否否显示：“请求I/O”表；当前移臂方向；当前柱面号，物理记录号来代替图3－3中的“启动磁盘”这项工作开始查”请求I/O表”有等待访问者?有与当前柱面号相同的访问者?当前移臂方向是向里移?有比当前柱面号小的访问请求?有比当前柱面号大的访问请求?置当前移臂方向为向外移置当前移臂方向为向里移从大于当前柱面号的访问请求中选择一个最小者从大于当前柱面号的访问请求中选择一个最小者选择能使旋转距离最短的访问者添加当前位置：柱面号；物理记录号启动磁盘，被选中者退出“请求I/O表”返回返回图3-3电梯调度模拟算法五、源程序#includestdio.h#includestdlib.h#includeconio.h#includestring.h#defineM20typedefstructPCB{charproc[M];//进程名intcylinder_num;//柱面号inttrack_num;//磁道号intphy_num;//物理记录号structPCB*next;}PCB;PCB*head=NULL;intdirection;//定义方向，1为up，-1为downPCB*h=NULL;//存放当前运行中的进程的信息voidinit()//初始化当前进程{h=(PCB*)malloc(sizeof(PCB));direction=1;strcpy(h-proc,p);h-cylinder_num=0;h-track_num=0;h-phy_num=0;}//模拟记录当前运行进程voidcurrent_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;}//插入函数voidinsert(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;}}voidout_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);}voidoutput(){PCB*p;p=head;printf(进程名柱面号磁道号物理记录号\n);if(p==NULL){printf(---*进程表为空,接收请求或按'n'退出*----\n);}else{while(p!=NULL){printf(%s\t%d\t%d\t%d\n,p-proc,p-cylinder_num,p-track_num,p-phy_num);p=p-next;}}}//初始化I/O请求表voidcreate_PCB(){PCB*p,*q;q=head;inti,n;printf(\n);printf(请输入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,&p-proc);scanf(%d,&p-cylinder_num);scanf(%d,&p-track_num);scanf(%d,&p-phy_num);p-next=NULL;insert(p);}printf(━━━━━━━━━━━━━━━\n);}//接受请求模块voidReceive_requests(){PCB*p;inti,n,m;printf(请输入一个值:\n);printf(1.接收请求\n);printf(0.继续执行\n);scanf(%d,&i);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,&n);printf(请依次输入进程的信息\n);printf(进程名，柱面号，磁道号，物理记录号\n);for(m=1;m=n;m++){p=(PCB*)malloc(sizeof(PCB));scanf(%s,&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();}elseprintf(没有接受进程，继续往下运行程序\n);}//电梯调度算法voidlift(){intmin,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_numh-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(maxq-cylinder_num){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_numq-cylinder_num)&&(q-cylinder_nump-cylinder_num)){min=q-cylinder_num;p=q;//p指向最小的节点}q=q-next;}}}else//当前移臂方向向外{while((q!=NULL)&&(q-cylinder_numh-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(minq-cylinder_num){min=q-c