处理器调度算法

1、调度算法，实现处理器调度。一、实验目的在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪状态进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下处理器调度，帮助自己加深了解处理器调度的工作。二、实验题目选择一个调度算法，实现处理器调度。三、背景材料（一）设计一个按优先数调度算法实现处理器调度的程序提示：1、假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：进程名指针要求运行时间优先数状态进程名作为进程的标识，假设五个进程的进程名分别为Pl,P2,P3,P4,P5。指针按优先数的大小把五个进程连成队列，

2、用指针指出下一个进程的进程控制块的首地址,最后一个进程中的指针为“0”。要求运行时间假设进程需要运行的单位时间数。优先数赋予进程的优先数,调度时总是选取优先数大的进程先执行。状态可假设有两种状态,“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”,用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。2、在每次运行你所设计的处理器调度程序之前,为每个进程任意确定它的“优先数”和“要求运行时间”。本实验由于为了检查的方便，优先数和运行时间采用下表中的数值。3、为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。例如：队首

3、标志K2K1P1K2P2K3P3K4P4K5P50K4K5K3K12312415342RRRRRPCB1PCB2PCB3PCB4PCB54、处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：优先数-1要求运行时间-1来模拟进程的一次运行。提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。5、进程运行一次后，若要求运行时间10,则再将它加入队列(按优先数大小插入，且置队首标志)；若要求运行

4、时间=0,贝I把它的状态修改成“结束”(E),且退出队列。6、若“就绪”状态的进程队列不为空，则重复上面(4)和(5)的步骤，直到所有进程都成为“结束”状态。7、在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。可以为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。#include#includeusingnamespacestd;/struct_proccharname32;struct_proc*next;intrun_time;intpriorit

5、y;intstate;/就绪为;_proc*root;/向就绪队列中插入进程,按照降序voidInsert(_proc*pr)_proc*q=root;方便插入,记录插入位置的前面的进程_proc*p=root-next;if(root-state!=0)while(p!=NULL)找插入位置if(p-prioritypr-priority)优先级小于时，继续遍历q=p;p=p-next;else/找到插入break;pr-next=p;插入q-next=pr;+root-state;进程个数加一/创建进程_procCreat(charname,intpriority,intrun_time)

6、_procpr;strcpy(,name);pr.priority=priority;pr.run_time=run_time;pr.state=0;pr.next=NULL;returnpr;/删除就绪队列中对首进程_proc*Delete()_proc*pr=root-next;root-next=root-next-next;-root-state;returnpr;/对就绪队列排序,按照降序voidSort()if(root-next-run_time=0)要执行时间为时，从就绪队列中删除该进程Delete();root-next-state=1;else/不为时，先删除

7、，再根据变化后的优先级，插入到相应位置_proc*pr=Delete();Insert(pr);/输出执行进程号voidOutPut()coutvvroot-next-namevvendl;输出，模拟进程执行-root-next-priority;修改进程的优先级和运行时间，状态-root-next-run_time;voidSolve()/根结点root=new_proc;root-state=0;/state记录就绪队列中的进程个数root-next=NULL;指向第一个进程/创建几个进程，并插入就绪队列_procpr1=Creat(p1，2，1);Insert(&pr1);_procpr

8、2=Creat(p2，3，5);Insert(&pr2);_procpr3=Creat(p3，1，3);Insert(&pr3);_procpr4=Creat(p4，2，4);Insert(&pr4);_procpr5=Creat(p5，4，2);Insert(&pr5);coutvv调度序列：vvendl;while(root-state!=0)OutPut();Sort();intmain()Solve();getchar();getchar();return0;（二）设计一个按时间片轮转法实现处理器调度的程序。1、假定系统有五个进程，每一个进程用一个进程控制块PCB来代表。进程控制块的格

9、式为：进程名指针要求运行时间已运行时间状态进程名作为进程的标识，假设五个进程的进程名分别为QI,Q2,Q3,Q4,Q5。指针进程按顺序排成循环队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。要求运行时间假设进程需要运行的单位时间数。已运行时间假设进程已经运行的单位时间数,初始值为“0”。状态有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。当一个进程运行结束后，它的状态为“结束”，用“E”表示。2、每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。3、把五个进程按顺序排成循环队列，用指针指出队列连接情

10、况。另用一标志单元记录轮到运行的进程。例如，当前轮到P2执行，则有：标志单元K2K1Q1K2Q2K3Q3K4Q4K5Q5K2K3K4K5K12312410000RRRRRPCB1PCB2PCB3PCB4PCB54、处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。请同学注意：在实际的系统中，当一个进程被选中运行时，必须置上该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片。在这时省去了这些工作，仅用“

11、已运行时间+1”来表示进程已经运行满一个时间片。5、进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间1已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（E）且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。6、若“就绪”状态的进程队列不为空，则重复上面的4和5的步骤，直到所有的进程都成为“结束”状态。7、在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的

12、进程名以及运行一次后进程队列的变化。可以为五个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。#include#includeusingnamespacestd;/struct_proccharname32;struct_proc*next;intrun_time;intalloc_time;intstate;/就绪为;_proc*root;/向就绪队列中插入进程,按照降序voidInsert(_proc*pr)if(root-next=NULL)root=pr;pr-next=pr;return;pr-next=root

13、-next;插入root-next=pr;root=pr;/创建进程_procCreat(charname,intrun_time,intalloc_time)_procpr;strcpy(,name);pr.run_time=run_time;pr.alloc_time=alloc_time;pr.state=0;pr.next=NULL;returnpr;/删除就绪队列中对首进程voidDelete()if(root-next=root)root=NULL;return;root-next=root-next-next;/输出进程号,模拟进程执行voidOutPut()cou

14、tvvroot-next-namevvendl;输出，模拟进程执行+root-next-alloc_time;修改进程voidSolve()/根结点root=new_proc;root-state=0;/state记录就绪队列中的进程个数root-next=NULL;空循环链表，指向自身/创建几个进程,并插入就绪队列_procpr1=Creat(Q1,2,1);Insert(&pr1);_procpr2=Creat(Q2,3,0);Insert(&pr2);_procpr3=Creat(Q3,1,0);Insert(&pr3);_procpr4=Creat(Q4,2,0);Insert(&pr

15、4);_procpr5=Creat(Q5,4,0);Insert(&pr5);coutvv调度序列：vvendl;while(root!=NULL)一直循环遍历OutPut();执行root指向的进程执行完毕即：run_time=alloc_time，从队列中删除该进程if(root-next-alloc_time=root-next-run_time)执行完毕Delete();从就绪队列中，删除该进程continue;root=root-next;/root指针后移，执行下一个进程做准备intmain()Solve();getchar();getchar();return0;四、实验内容1、

16、设计一个按背景材料中指定优先数的优先数调度算法实现处理器调度的程序2、设计一个按时间片轮转法实现处理器调度的程序。#includestdio.h#include#include#definegetpch(type)(type*)malloc(sizeof(type)#defineNULL0structpcb/*定义进程控制块PCB*/charname10;charstate;intsuper;intntime;intrtime;structpcb*link;*ready=NULL,*p;typedefstructpcbPCB;sort()/*建立对进程进行优先级排列函数*/PCB*first,

17、*second;intinsert=0;if(ready=NULL)p-link=ready;ready=p;else/*进程比较优先级,插入适当的位置中*/first=ready;second=first-link;while(second!=NULL)first=first-link;second=second-link;/*插尾*/if(insert=0)first-link=p;input()/*建立进程控制块函数*/inti,num;system(cls);/*清屏*/printf(n请输入进程号?);scanf(%d,&num);for(i=0;iname);printf(n输入进

18、程运行时间:);scanf(%d,&p-ntime);printf(n);p-rtime=0;p-state=w;p-link=NULL;sort();/*调用sort函数*/intspace()intl=0;PCB*pr=ready;while(pr!=NULL)l+;pr=pr-link;return(l);disp(PCB*pr)/*建立进程显示函数,用于显示当前进程*/printf(nqnametstatetsupertndtimetruntimen);printf(|%st,pr-name);printf(|%ct,pr-state);printf(|%dt,pr-super);printf(|%dt,pr-ntime);printf(|%dt,pr-rtime)