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

《操作系统原理 第2版实验与思考第8章处理器管理.docx》由会员分享，可在线阅读，更多相关《操作系统原理 第2版实验与思考第8章处理器管理.docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【实验与思考】进程调度算法模拟实现1 .背景知识（1） FCFS：先来先服务，按照进程就绪的先后顺序来调度进程，到达的越早，其优先级 越高。获得处理机的进程，在未遇到其他情况时一直运行下去，直到结束或进行I/O。（2） RR：简单轮转法，系统把所有就绪进程按先后次序排队，处理机总是优先分配给就 绪队列中的第一个就绪进程，并分配它一个固定的时间片（如50毫秒）。当该运行进程用完规 定的时间片时，被迫释放处理机给下一个处于就绪队列中的第一个进程，自己回到就绪队列的尾 部，并等待下次调度。当某个正在运行的进程的时间片尚未用完，但进程需要I/O时，该进程 被送到相应阻塞队列，等I/O完成重新返回到就绪

2、队列尾部，等待调度。（3） SPN:最短进程优先，选择当前就绪队列中所需处理时间最短的进程。获得处理机的 进程，在未遇到其他情况时一直运行下去，直到结束。短进程将会越过长进程，得到优先运行, 但长进程可能会被“饿死”。（4） SRT：最短剩余时间优先，对SPN增加剥夺机制。当一个时钟中断周期到后，调度程 序总是选择预期剩余时间最短的进程。当一个新进程加入就绪队列时，它可能比当前运行的进 程具有更短的剩余时间，因此，调度程序将剥夺当前程序，将处理器分配给新进程。（5） HRRN：最高响应比优先，最高响应比也是对最短进程法的一种改进，当前进程完成 或被阻塞时，选择响应比最大的进程先执行，获得处理机

3、的进程，在未遇到其他情况时一直运 行下去，直到结束。响应比的计算公式如下：响应比R 二（等待时间W+预计执行时间S） /预计执行时间S（6） PRIORITY：优先级调度算法，选择当前就绪队列中优先级最高的进程到处理机上运 行。分为非抢占优先级调度和可抢占优先级调度。非抢占的优先级调度法：一旦一个高优先级的进程占有了处理器，就一直运行下去，直到 因等待某事被阻塞或执行结束，才选择就绪队列中优先级最高的进程来执行。可抢占的优先级调度法：任何时刻都按照高优先级进程在处理器上运行的原则进行进程调 度。当一高优先级进程运行时，若有一更高优先级进程到达就绪队列，则当前运行进程立刻将 处理器让给更高优先级

4、的进程（即使未处理完，也无遇到阻塞情况）（7） FB：反馈法。将划分多个就绪队列，优先级逐步降低。新建进程进入优先级最高的队 列中，每当进程规定的时间片用完，被剥夺时，就送往低一级的就绪队列。进程调度时总是先 执行高优先级队列中的进程。高优先级队列为空后，才转去处理低一级优先级队列中的进程。 同一优先级队列（除最低）的进程，按FIFO机制调度。最低优先级队列，按时间片轮转调度算 法执行。不同优先级队列可以拥有相同的时间片，也可以不同。通常考虑到低优先级进程的特 性，优先级低的就绪队列会给予较长一些的时间片。2 .工具/准备工作步骤2：编译源程序并运行。如有问题请分析解决，并进行必要的情况说明。

5、步骤3：完善程序，请给出最短剩余时间优先，可抢占优先级和简单轮转法（时间片为4） 的实现方法。代码请附纸。步骤4：运行程序，给出各个调度算法的运行结果。4 .实验总结5 .教师实验评价（1）在开始本实验之前，请回顾教科书的相关内容。（2）需要准备一台运行Windows操作系统的计算机，且该计算机中需安装Visual C+6.0。3.实验内容与步骤编写程序，模拟实现各进程调度算法。从测试文件读入进程相关信息，然后给出不同进程 调度算法下，进程的运行次序情况。测试数据文件格式测试数据文件包括n行测试数据，分别描述n个进程的相关信息。每行测试数据包括四个 字段，各个字段间用空格分隔： 第一字段为字符

6、串，表示进程名； 第二字段是整数，表示进程到达时间； 第三字段为整数，表示进程预期的执行时间； 第四字段为整数，表示进程的优先级（注：数值越大，优先级越高）。下面是一个测试数据文件（data.txt）的例子：A033B262C441D654E823步骤1:程序清单8-1给出了一部分进程调度算法的代码实现。请参考程序清单8-1的代码, 完成进程调度算法的模拟实现。清单87进程调度算法。# include# include# include# include# include# include#include struct Processinfo(string pname;int arriveti

7、me;int bursttime;int priority;/进程信息节点的定义/进程名称/到达时间/运行所需时间/优先级，数值越大优先级越高int needtime;/剩余运行时间double hrrn;/实时响应比，每个时刻需要重新计算响应比Processinfo *next;/链表指针）；Processinfo *basehead=newProcessinfo;/进程基础信息链表首指针/复制链表Processinfo *copyProcessQueue(Processinfo *head)Processinfo *t, *newhead=new Processinfo;Processin

8、fo *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,Proc

9、essinfo *ready,Processinfo *rrhead) /将就绪队列指针移动到队尾 Processinfo *temp=ready;while(temp-next!=NULL)temp=temp-next;/将某时刻前已经到达的进程，按时间顺序加入就绪队列while(rrhead-next!=NULL&rrhead-next-arrivetimenext=rrhead-next;rrhead-next=rrhead-next-next;temp-next-needtime=temp-next-bursttime;temp=temp-next;)temp-next=NULL;)/

10、cpu空转输出void do_free(int currtime,int firstArrivetime) int interval=firstArrivetime-currtime;while(interval0)coutcc“空”; interval-;)/先来先服务算法void FCFS( Processinfo *basehead)if (basehead-next=NULL) coutX”没有进程信息” next-ar rive time; /用于存放当前时亥 U run=basehead-next;while (run!=NULL) do_free(timef run-arrive

11、time);for (int j =0; jbursttime; j+) coutpname; t ime=t ime+r tin-bur sttime;run=run-next;)/最短进程优先void SPN(Processinfo *basehead) if (basehead-next=NULL) ”没有进程信息 ”next-ar rive time; /将最先到达的进程作为开始运行的起始时间。 while(spnhead-next!=NULL)/空转处理，即此刻没有就绪进程到达就绪队列 do_free(time,spnhead-next-arrivetime);/用search-ne

12、xt指向当前时刻运行时间最短的进程Processinfo *search=spnhead;temp=spnhead-next;/在已经到达的进程中寻找运行时间最短的进程while(temp-next!=NULL& &temp-next-arrivetimenext-bursttimenext-bursttime) search=temp;temp=temp-next;)/执行search-next指向的进程 Processinfo *run=search-next;time=time+run-bursttime;for (int j=0;jbursttime;j+ + )coutpname;

13、search-next=search-next-next;free (run);/简单轮转法，时间片为1void RR(ProcessInfo *basehead)if(basehead-next=NULL) cout”没有进程信息” nxt-arrivtim；/将最先到达的进程作为开始运行的起始时间。 Processinfo *ready=new Processinfo;ready-next=NULL; /初始化就绪链表为空while (rrhead-next!=NULL| |ready-next!=NULL) if (ready-next=NULL) do_f ree (time, rrh

14、ead-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;cou

15、tpname; run-needtime-;time+；/重新维护新时刻的就绪队列/如果还有进程要达到，则处理是否有新进程到达就绪队列if(rrhead-next!=NULL)do_currread(time,ready,rrhead);if (run-needtime0) /如果进程没有运行完，则排到就绪队列尾部 /将就绪队列指针移动到队尾Processinfo *temp=ready;while(temp-next!=NULL)temp=temp-next;temp-next=run;)else free (run);/最高响应比优先void HRRN(Processinfo *baseh

16、ead)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; /

17、ffl searchnext 指向当前时亥U响应比最高进程 search-next-hrrn=l+(time-search-next-arrivetime)/search-next- bursttime;temp=hrrnhead-next;/在已经到达的进程中寻找响应比最高的进程while(temp-next!=NULL&temp-next-arrivetimenext-hrrn=l+(time-temp-next-arrivetime)/ temp-next-bursttime;if(temp-next-hrrnsearch-next-hrrn) search=temp; temp=tem

18、p-next;/执行search-next指向的进程Processinfo * run=search-next;time=time+run-bursttime;for (int j=0;jbursttime;j +)coutpname;search-next=search-next-next;free (run);/非抢占优先级void PRIORITY(Processinfo *basehead) if (basehead-next=NULL) 003七”没有进程信息、911d1; return;Processinfo *tempz *priorityhead;/ 复制basehead中的进

19、程信息至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;/在已经

20、到达的进程中寻找优先级最高的进程while(temp-next!=NULL&temp-next-arrivetimenext-prioritysearch-next-priority) search=temp;temp=temp-next;/执行search-next指向的进程Processinfo *run=search-next;time=time+run-bursttime;for (int j =0;jbursttime;j+)coutpname;search-next=search-next-next;free (run);int main() (ifstream infile;in

21、file . open (ne : Wdata . txtn) ; /打开文件(请用实际的文件路径) Processinfo *t;printf (“初始进程相关数据：n”)； basehead-next=NULL;while (infil)/从文件读取数据Processinfo *p=new Processinfo;infilep-pname;infilep-arrivetime;infilep-bursttime;infilep-priority;/从文件读入进程信息时按照到达时间插入进程链表basehead t=basehead;while ( (t-next!=NULL)&(p-arr

22、ivetime=t-next-arrivetime) t=t-next;p-next=t-next;t-next=p;infile.get ();进程名：npnamen至 U 达时间：nar rive timen运彳亍时间：nbursttimen优先级:npriorityi;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;)