操作系统原理 第2版实验与思考第8章处理器管理.docx

【实验与思考】进程调度算法模拟实现1 .背景知识（1） FCFS：先来先服务，按照进程就绪的先后顺序来调度进程，到达的越早，其优先级 越高。获得处理机的进程，在未遇到其他情况时一直运行下去，直到结束或进行I/O。（2） RR：简单轮转法，系统把所有就绪进程按先后次序排队，处理机总是优先分配给就 绪队列中的第一个就绪进程，并分配它一个固定的时间片（如50毫秒）。当该运行进程用完规 定的时间片时，被迫释放处理机给下一个处于就绪队列中的第一个进程，自己回到就绪队列的尾 部，并等待下次调度。当某个正在运行的进程的时间片尚未用完，但进程需要I/O时，该进程 被送到相应阻塞队列，等I/O完成重新返回到就绪队列尾部，等待调度。（3） SPN:最短进程优先，选择当前就绪队列中所需处理时间最短的进程。获得处理机的 进程，在未遇到其他情况时一直运行下去，直到结束。短进程将会越过长进程，得到优先运行, 但长进程可能会被“饿死”。（4） SRT：最短剩余时间优先，对SPN增加剥夺机制。当一个时钟中断周期到后，调度程 序总是选择预期剩余时间最短的进程。当一个新进程加入就绪队列时，它可能比当前运行的进 程具有更短的剩余时间，因此，调度程序将剥夺当前程序，将处理器分配给新进程。（5） HRRN：最高响应比优先，最高响应比也是对最短进程法的一种改进，当前进程完成 或被阻塞时，选择响应比最大的进程先执行，获得处理机的进程，在未遇到其他情况时一直运 行下去，直到结束。响应比的计算公式如下：响应比R 二（等待时间W+预计执行时间S） /预计执行时间S（6） PRIORITY：优先级调度算法，选择当前就绪队列中优先级最高的进程到处理机上运 行。分为非抢占优先级调度和可抢占优先级调度。非抢占的优先级调度法：一旦一个高优先级的进程占有了处理器，就一直运行下去，直到 因等待某事被阻塞或执行结束，才选择就绪队列中优先级最高的进程来执行。可抢占的优先级调度法：任何时刻都按照高优先级进程在处理器上运行的原则进行进程调 度。当一高优先级进程运行时，若有一更高优先级进程到达就绪队列，则当前运行进程立刻将 处理器让给更高优先级的进程（即使未处理完，也无遇到阻塞情况）（7） FB：反馈法。将划分多个就绪队列，优先级逐步降低。新建进程进入优先级最高的队 列中，每当进程规定的时间片用完，被剥夺时，就送往低一级的就绪队列。进程调度时总是先 执行高优先级队列中的进程。高优先级队列为空后，才转去处理低一级优先级队列中的进程。 同一优先级队列（除最低）的进程，按FIFO机制调度。最低优先级队列，按时间片轮转调度算 法执行。不同优先级队列可以拥有相同的时间片，也可以不同。通常考虑到低优先级进程的特 性，优先级低的就绪队列会给予较长一些的时间片。2 .工具/准备工作步骤2：编译源程序并运行。如有问题请分析解决，并进行必要的情况说明。步骤3：完善程序，请给出最短剩余时间优先，可抢占优先级和简单轮转法（时间片为4） 的实现方法。代码请附纸。步骤4：运行程序，给出各个调度算法的运行结果。4 .实验总结5 .教师实验评价（1）在开始本实验之前，请回顾教科书的相关内容。（2）需要准备一台运行Windows操作系统的计算机，且该计算机中需安装Visual C+6.0。3.实验内容与步骤编写程序，模拟实现各进程调度算法。从测试文件读入进程相关信息，然后给出不同进程 调度算法下，进程的运行次序情况。测试数据文件格式测试数据文件包括n行测试数据，分别描述n个进程的相关信息。每行测试数据包括四个 字段，各个字段间用空格分隔： 第一字段为字符串，表示进程名； 第二字段是整数，表示进程到达时间； 第三字段为整数，表示进程预期的执行时间； 第四字段为整数，表示进程的优先级（注：数值越大，优先级越高）。下面是一个测试数据文件（data.txt）的例子：A033B262C441D654E823步骤1:程序清单8-1给出了一部分进程调度算法的代码实现。请参考程序清单8-1的代码, 完成进程调度算法的模拟实现。清单87进程调度算法。# include# include# include# include# include# include<conio . h><stdlib . h><fstream><io . h><stdio . h><iostream>#include <string>struct Processinfo(string pname;int arrivetime;int bursttime;int priority;/进程信息节点的定义/进程名称/到达时间/运行所需时间/优先级，数值越大优先级越高int needtime;/剩余运行时间double hrrn;/实时响应比，每个时刻需要重新计算响应比Processinfo *next;/链表指针）；Processinfo *basehead=newProcessinfo;/进程基础信息链表首指针/复制链表Processinfo *copyProcessQueue(Processinfo *head)Processinfo *t, *newhead=new Processinfo;Processinfo *temp=head->next;newhead->next=NULL;t=newhead;while (temp!=NULL)Processinfo *p=new Processinfo;p->pname=temp->pname;p->arrivetime=temp->arrivetime;p->bursttime=temp->bursttime; p->priority=temp->priority;p->next=NULL;t->next=p;t=t->next;temp=temp->next;) return newhead;/某时刻就绪队列的维护void do_currread(int time,Processinfo *ready,Processinfo *rrhead) /将就绪队列指针移动到队尾 Processinfo *temp=ready;while(temp->next!=NULL)temp=temp->next;/将某时刻前已经到达的进程，按时间顺序加入就绪队列while(rrhead->next!=NULL&&rrhead->next->arrivetime<=time)temp->next=rrhead->next;rrhead->next=rrhead->next->next;temp->next->needtime=temp->next->bursttime;temp=temp->next;)temp->next=NULL;)/cpu空转输出void do_free(int currtime,int firstArrivetime) int interval=firstArrivetime-currtime;while(interval>0)coutcc“空”; interval-;)/先来先服务算法void FCFS( Processinfo *basehead)if (basehead->next=NULL) coutX”没有进程信息” << ndl; return;)Processinfo *run;int time=basehead->next->ar rive time; /用于存放当前时亥 U run=basehead->next;while (run!=NULL) do_free(timef run->arrivetime);for (int j =0; j< rtin->bursttime; j+) cout<<run->pname; t ime=t ime+r tin->bur sttime;run=run->next;)/最短进程优先void SPN(Processinfo *basehead) if (basehead->next=NULL) <”没有进程信息 ”<<endl; return;Processinfo *tempf *spnhead;/ 复制J basehead中的进程信息到spnhead中spnhead=copyProcessQueue(basehead);int time=spnhead->next->ar rive time; /将最先到达的进程作为开始运行的起始时间。 while(spnhead->next!=NULL)/空转处理，即此刻没有就绪进程到达就绪队列 do_free(time,spnhead->next->arrivetime);/用search-next指向当前时刻运行时间最短的进程Processinfo *search=spnhead;temp=spnhead->next;/在已经到达的进程中寻找运行时间最短的进程while(temp->next!=NULL& &temp->next->arrivetime<=time) if(temp->next->bursttime<search->next->bursttime) search=temp;temp=temp->next;)/执行search->next指向的进程 Processinfo *run=search->next;time=time+run->bursttime;for (int j=0;j< run->bursttime;j+ + )cout<<run->pname; search->next=search->next->next;free (run);/简单轮转法，时间片为1void RR(ProcessInfo *basehead)if(basehead->next=NULL) cout<<”没有进程信息” <<endl; return;Processinfo *temp, *rrhead;/ 复制basehead中的进程信息到rrhead中rrhead=copyProcessQueue(bashad);int tim-rrhead->nxt->arrivtim；/将最先到达的进程作为开始运行的起始时间。 Processinfo *ready=new Processinfo;ready->next=NULL; /初始化就绪链表为空while (rrhead->next!=NULL| |ready->next!=NULL) if (ready->next=NULL) do_f ree (time, rrhead->next->ar rive time) ; /处理空转/将rrhead中的第一个进程移动到ready链表，并设置time为该进程的到达时间time=rrhead->next->arrivetime;ready->next=rrhead->next;rrhead->next=rrhead->next->next;ready->next->next=NULL;ready->next->needtime=ready->next->bursttime;/执行就绪队列第一个进程Processinfo *run=ready->next; ready->next=ready->next->next; run->next=NULL;cout<<run->pname; run->needtime-;time+；/重新维护新时刻的就绪队列/如果还有进程要达到，则处理是否有新进程到达就绪队列if(rrhead->next!=NULL)do_currread(time,ready,rrhead);if (run->needtime>0) /如果进程没有运行完，则排到就绪队列尾部 /将就绪队列指针移动到队尾Processinfo *temp=ready;while(temp->next!=NULL)temp=temp->next;temp->next=run;)else free (run);/最高响应比优先void HRRN(Processinfo *basehead)if (basehead->next=NULL) Processinfo *tmp, *hrrnhead;/ 复制basehead中的进程信息至U hrrnhead中 hrrnhead=copyProcessQueue(basehead);int time=hrrnhead->next->ar rive time; /将最先到达的进程作为开始运行的起始时间。while (hrrnhead->next!=NULL) /空转处理，即此刻没有就绪进程到达就绪队列do_free(time,hrrnhead->next->arrivetime);Processinfo *search=hrrnhead; /ffl search>next 指向当前时亥U响应比最高进程 search->next->hrrn=l+(time-search->next->arrivetime)/search->next-> bursttime;temp=hrrnhead->next;/在已经到达的进程中寻找响应比最高的进程while(temp->next!=NULL&&temp->next->arrivetime<=time) temp->next->hrrn=l+(time-temp->next->arrivetime)/ temp->next->bursttime;if(temp->next->hrrn>search->next->hrrn) search=temp; temp=temp->next;/执行search->next指向的进程Processinfo * run=search->next;time=time+run->bursttime;for (int j=0;j< run->bursttime;j +)cout<<run->pname;search->next=search->next->next;free (run);/非抢占优先级void PRIORITY(Processinfo *basehead) if (basehead->next=NULL) 003七”没有进程信息、"911d1; return;Processinfo *tempz *priorityhead;/ 复制basehead中的进程信息至U priorityhead中 priorityhead=copyProcessQueue(basehead);/将最先到达的进程作为开始运行的起始时间。int time=priorityhead->next->arrivetime;while(priorityhead->next!=NULL)/空转处理，即此刻没有就绪进程到达就绪队列do_free(time,priorityhead->next->arrivetime);/用search->next指向当前时刻优先级最高的进程Processinfo *search=priorityhead;temp=priorityhead->next;/在已经到达的进程中寻找优先级最高的进程while(temp->next!=NULL&&temp->next->arrivetime<=time) if(temp->next->priority>search->next->priority) search=temp;temp=temp->next;/执行search->next指向的进程Processinfo *run=search->next;time=time+run->bursttime;for (int j =0;j< run->bursttime;j+)cout<<run->pname;search->next=search->next->next;free (run);int main() (ifstream infile;infile . open (ne : Wdata . txtn) ; /打开文件(请用实际的文件路径) Processinfo *t;printf (“初始进程相关数据：n”)； basehead->next=NULL;while (infil)/从文件读取数据Processinfo *p=new Processinfo;infile>>p->pname;infile>>p->arrivetime;infile>>p->bursttime;infile>>p->priority;/从文件读入进程信息时按照到达时间插入进程链表basehead t=basehead;while ( (t->next!=NULL)&&(p->arrivetime>=t->next->arrivetime) t=t->next;p->next=t->next;t->next=p;infile.get ();进程名：n<<p->pname<<n至 U 达时间：n<<p->ar rive time<<n运彳亍时间：n<<p->bursttime<<n优先级:n<<p->priority<<endl;infile.close ();/选择算法int i=0;while (i!=6) printf (“nn请选择算法：nl-先来先服务；2最短进程优先；3简单轮转法(时间片为1 )； 4最高响应比优先；5非抢占优先级；6退出；n”)；cin>>i;switch (i) case 1 先来先服务的进程运行顺序如下：”<ndl;FCFS( basehead);break;case 2 :最短进程优先的进程运行顺序如下：<ndl;SPN(basehead);break;case 3 轮转法(时间片为1)的进程运行顺序如下：”<一nWL;RR(basehead);break;case 4 : cout<<”最高响应比优先的进程运行顺序如下："<<end1;HRRN(basehead);break;case 5 : coutxc”非抢占优先级的进程运行顺序如下："<<endl;PRIORITY(basehead);break;)