进程调度算法仿真实现

1、计算机操作系统原理课外上机实验报告题目：实验名称：进程调度算法的仿真实现 组长主要任务:1.总体数据结构设计；2.进程调度算法过程构架分析；3.优先级算法静态优先级抢占算法；4.动态优先级算法编写；5.算法测试分析；6.使用手册撰写。组员主要任务:1.总体数据结构设计；2.进程调度算法过程构架分析；3.进程创建算法编写；4.时间片轮转法算法编写5.用户界面编写；6.实验报告撰写。一、实验目的1.仿真进程并发的调度环境，设计和实现PCB控制块、进程创建、进程切换、进程并发、进程阻塞和进程调度的算法2.掌握进程调度的优先权法、时间片轮转法和多级反馈队列算法的实现3.强化算法设计和数据结构。二、核心

2、设计思路及实现内容1.利用随机数产生进程，创建PCB类的数组对象；2.建立等待序列将创建好的PCB数组放入等待序列；3.当进程的进入时间小于等于模拟的系统时间时，将该进程从等待序列进入就绪队列，并将就绪队列内的进程按随机生成的优先级进行排序；4.静态优先级算法：优先级高的进程优先的进入；5.动态优先级算法：与静态优先级算法相类似，增加一个优先级减少的算法，优先级高的进程优先的进入；6.时间片算法：根据随机的优先级，确定时间片执行进程，就绪队列队头进入到运行态，在时间片内不能完成的进入就绪队列，时间片未完成的插入到就绪队列队尾，时间片完成的从运行队列中删除。三、数据结构及操作函数设计1.总体数据

3、结构：class PCB( ) public PCB() /构造函数 public PCB(ID) /重载构造函数public PCB(ID，Priority，in，Alltime，State) /重载构造函数public partial class 进程调度 /队列初始化public 进程调度仿真() ; /用户界面private void button_Click(); /按钮动作函数private void AddListViewItem(); /输出显示窗口 private void staticPriority(); /静态优先级函数 private void ActivePrior

4、ity(); /动态优先级函数private void TimePiece(); /时间片轮转调度算法函数初始化进程控制模块PCB的对象，数组形式，最多可初始化的数目取决于数组大小PCB pcb=new PCBWaitlist= pcbIn=systemtimeReadylist=pcbstaticPriority()ActivePriority()TimePiece()Runninglist=pcb将产生的数组对象放入构建好的等待队列中等待当进入时间等于系统时间时就将进程放入到就绪队列中，并且对就绪队列进行优先级排序选择不同的算法优先级算法：优先级高的优先进入运行队列时间片算法：检索就绪队列

5、队头进入运行队列优先级算法：优先级高的优先抢占时间片算法：未完成的优先级减一且插入到就绪队列队尾，完成的从运行队列中删除。2.模块PCB类：进程控制模块的类，类中包含进程名（ID），优先级（priority），进入时间（In），总时间（Alltime），状态（State），剩余时间（Lefttime）六个属性。类中同时包含构造函数用来进行进程控制模块PCB的初始化class PCB( ) public PCB() /构造函数 public PCB(ID) /重载构造函数public PCB(ID，Priority，in，Alltime，State) /重载构造函数队列对象创建：以链表为主要数据

6、结构创建等待队列（WaitList），就绪队列（ReadyList），运行队列（RunList），处于运行态的队列（RunningList）ArrayList WaitList = new ArrayList();ArrayList ReadyList = new ArrayList();ArrayList RunList = new ArrayList();PCB RunningList = new PCB();界面设置：对显示窗口（LIstView），操作按钮（Button）进行初始化设置、操作动作函数设置public 进程调度仿真() ; /用户界面private void button

7、_Click(); /按钮动作函数private void AddListViewItem(); /输出显示窗口进程初始化：通过规定随机数范围随机产生进程，同时初始化进程名、优先级等六个属性，并将进程保存到进程数组private void initialize();核心函数：进程调度的三种方法所写的函数，静态优先级立即抢占算法（staticPriority()），动态优先级算法（ActivePriority()），时间片轮转调度算法（TimePiece()）private void staticPriority(); /静态优先级函数private void ActivePriority();

8、 /动态优先级函数private void TimePiece(); /时间片轮转调度算法函数主控函数：用来启动界面显示以及整个程序static void Main() Application.Run(new 进程调度仿真(); 3.核心函数静态优先级立即抢占算法设计思想：静态优先级算法,优先级高的进程优先的进入程序流程：清空等待、就绪、运行队列ListClear()随机进程进入等待队列列系统时间SysTime+(PCB)WaistListi.state=0&(PCB)WaistListi.In1根据优先级排序SetOrder()完成抢占ReadyList无PCBRunList有PCBRead

9、yList有PCBRunList有PCBReadyList有PCBRunList无PCBCPU空闲运行时间是否结束伪码：private void StaticPriority() ListClear(); /清空队列Waitlist.add(pcbn); /将pcb放入等待队列if(state=0&waitlist.in1) 由高到低进行排序； /当就绪队列中的进程数大于一个时对这些进程进行冒泡法/排序if(Runninglist=0&Readylist=0) print(“CPU空闲”);/当就绪队列中没有PCB，CPU中也没有正在运行的PCB时，判断CPU空闲if(Runninglist=

10、0&Readylist!=0) RunningList = (PCB)ReadyList0; /将就绪队列中的0号PCB移入运行ReadyList.RemoveAt(0); /将就绪队列中的0号元素删除/当就绪队列中有PCB，CPU中没有正在运行的PCB时，将PCB放入就绪队列if (RunningList!= 0 & ReadyList = 0) if (Passtime = (ReadyList.Priority) Passtime =Passtime + 1; /当cpu中的进程已经运行完毕 if (Passtime = Alltime) SetRunningList(); /清空运行队

11、列 else print( 未完成); RunningList = ReadyList0; Passtime = Passtime + 1; if (Passtime = Alltime) /当cpu中的进程已经运行完毕 RunningList = ReadyList0; ReadyList.RemoveAt(0); 文字描述：1.进程从进程数组到等待队列;2.启动系统时间，并与随机进程的进入时间比较，进入时间小于等于系统时间就进入就绪队列，最终使符合要求的所有进程进入就绪队列，并在就绪队列中按优先级排序;3.当等待和就绪队列都空时，CPU出于空闲状态；当就绪队列中有PCB，CPU中无进程时，

12、将就绪队列中的队头元素移入运行队列；当就绪队列中无PCB，CPU中有进程运行时，判断总时间和运行时间的关系；当就绪队列中有PCB，CPU中正在运行进程时，判断运行队列与就绪队列中进程优先级的关系，运行队列中进程优先级大时，判断运行队列中进程总时间和运行时间的关系，否则就绪队列中的进程完成抢占。动态优先级算法设计思想：动态优先级算法：与静态优先级算法相类似，增加一个优先级减少的算法，优先级高的进程优先的进入程序流程：YY清空等待、就绪、运行队列ListClear()随机进程进入等待队列列系统时间SysTime+进程进入就绪队列(PCB)WaistListi.state=0&(PCB)WaistL

13、isti.In运行队列ReadyList.Count1根据优先级排序SetOrder()完成抢占进程进入就绪队列ReadyList无PCBRunList有PCBReadyList有PCBRunList有PCBReadyList有PCBRunList无PCBCPU空闲运行时间是否结束优先级减1，进程从运行队列-就绪队列RunList.PriorityReadyList.PriorityNY伪码：private void StaticPriority() ListClear(); /清空队列Waitlist.add(pcbn); /将pcb放入等待队列if(state=0&waitlist.in1

14、) 由高到低进行排序； /当就绪队列中的进程数大于一个时对这些进程进行冒泡法/排序if(Runninglist=0&Readylist=0) print(“CPU空闲”);/当就绪队列中没有PCB，CPU中也没有正在运行的PCB时，判断CPU空闲if(Runninglist=0&Readylist!=0) RunningList = (PCB)ReadyList0; /将就绪队列中的0号PCB移入运行ReadyList.RemoveAt(0); /将就绪队列中的0号元素删除/当就绪队列中有PCB，CPU中没有正在运行的PCB时，将PCB放入就绪队列if (RunningList!= 0 & R

15、eadyList = 0) if (Passtime = (ReadyList.Priority) Passtime =Passtime + 1; /当cpu中的进程已经运行完毕 if (Passtime = Alltime) SetRunningList(); /清空运行队列 else print( 未完成);Priority= Priority - 1; /动态优先级算法优先级减1表示动态 /当优先级小于0时，将优先级重置成0 RunningList = ReadyList0; Passtime = Passtime + 1; if (Passtime = Alltime) /当cpu中的

16、进程已经运行完毕 RunningList = ReadyList0; ReadyList.RemoveAt(0); /将就绪队列中的0号元素删除 文字描述：1.进程从进程数组到等待队列;文字描述：2.启动系统时间，并与随机进程的进入时间比较，进入时间小于等于系统时间就进入就绪队列，最终使符合要求的所有进程进入就绪队列，并在就绪队列中按优先级排序;文字描述：3.当等待和就绪队列都空时，CPU出于空闲状态；当就绪队列中有PCB，CPU中无进程时，将就绪队列中的队头元素移入运行队列；当就绪队列中无PCB，CPU中有进程运行时，判断总时间和运行时间的关系；当就绪队列中有PCB，CPU中正在运行进程时，

17、判断运行队列与就绪队列中进程优先级的关系，运行队列中进程优先级大时，判断运行队列中进程总时间和运行时间的关系，否则进程从运行队列中移除，并使进程优先级减1，使就绪队列中的进程完成抢占。时间片轮转调度算法设计思想：根据随机产生的优先级，确定时间片执行进程，就绪队列队头进入到运行态，在时间片内不能完成的进入就绪队列，时间片完成从运行队列中删除。程序流程：YCPU空闲Lefttime=0PcbnWaitlistn=pcbnWaitlistn.in=systemtimeReadylistn=pcbnCPU空闲就绪队列队头进入运行队列Runninglist.ID!=0NYReadylist.count!

18、=0YNRounftime=systimeLefttime=0进程调度完成进程未完成，优先级减1进入就绪队列队尾YNYN伪码：private void Timepiece(pcb) List.clear(); /清空所有的队列 Waitlist.add(pcbn); /将pcb放入等待队列 if(state=0&waitlist.in1) 由高到低进行排序； /当就绪队列中的进程数大于一个时对这些进程进行冒泡法/排序if(Runninglist=0&Readylist=0) print(“CPU空闲”);/当就绪队列中没有PCB，CPU中也没有正在运行的PCB时，判断CPU空闲if(Runni

19、nglist=0&Readylist!=0) Runninglistn = Readylistn;/当就绪队列中有PCB，CPU中没有正在运行的PCB时，将PCB放入就绪队列if(Runninglist!=0) / CPU中有正在运行的PCB时Roundtime=In+priority*10; /时间片等于随机产生优先级的10倍Lefttime=Alltime+In-systime; /剩余时间if(Roundtime systime) /时间片大于系统时间时进行剩余时间判断 if(lefttime0) /剩余时间大于0，则未完成，优先级减1，重返就绪队列 print(“未完成”); prio

20、rity= priority-1; Readylist= newpcb;else /剩余时间小于等于0，完成print(“完成”);else/时间片小于等于系统时间时进行剩余时间判断 if(lefttime0) /剩余时间大于0，则未完成，优先级减1，重返就绪队列 print(“未完成”); priority= priority-1;Readylist= newpcb;else /剩余时间小于等于0，CPU空闲print(“CPU空闲”);文字描述：1.利用随机数初始化进程对象数组，将其加入等待队列；2.当等待队列中的进程的进入时间等于系统时间时代表进程进入也就是将进程加入就绪队列；3.这时候

21、进行判断，分四种情况讨论：第一种：当CPU中没有进程运行时也就是运行队列中没有进程，同时就绪队列里没有进程也就是就绪队列为空时判定CPU为空闲状态；第二种：当CPU中没有进程运行时也就是运行队列中没有进程，同时就绪队列里有进程也就是就绪队列不为空时判定CPU不处于空闲状态，这时将就绪队列队头，即首个元素（进程）进入运行队列，即运行此进程；第三种：当CPU中有进程运行时也就是运行队列中有进程，同时判断时间片是否完成即时间片减去系统时间是否小于0，小于等于0即完成否则为完成。若时间片未完成则进行剩余时间的判断，若剩余时间小于等于0则进程完成，若剩余时间大于0则将进程的优先级减一重新放回到就绪队列队

22、尾，同时将运行队列进行初始化以便接下来的进程继续运行；第四种：当CPU中有进程运行时也就是运行队列中有进程，同时判断时间片是否完成即时间片减去系统时间是否小于0，小于等于0即完成否则为完成。若时间片完成则进行剩余时间的判断，若剩余时间小于等于0则CPU处于空闲状态没有进程在运行；若剩余时间大于0则将进程的优先级减一重新放回到就绪队列队尾，同时将运行队列进行初始化以便接下来的进程继续运行。四、测试运行及结果分析1.随机产生进程模块：初始化随机生成10个进程进程名、优先级、进入时间、总时间等属性在Listview中显示并将随机产生的进程装入等待队列2.静态优先级立即抢占算法：随机产生了3个进程，进

23、程3最先进入，优先执行；在系统时间为4的时候进程1进入，进程1的优先级要高于进程3所以发生立即抢占，这是中断进程3，进程3进入就绪队列将优先级设置为最低，将进程1加入运行队列，开始执行;这时3个进程已经全部进入等待队列，没有优先级高于进程1的进程，所以一直执行进程1直至结束，计算周转时间;因为优先级不会改变就按照就绪队列中目前的优先级排序依次执行各个进程，直至运行队列以及就绪队列均为空，计算CPU利用率为95%，结束。3.动态优先级算法：随机生成7个进程，进程7优先进入，进入时间为7，进程7需要运行的时间为42;进程6进入时间为8，优先级为4高于进程7，所以这时候进程7中断开始执行进程6，进程7被放回就绪队列尾，状态标记为未完成;在系统时间为12,15时，进程3,4,5相继进入但是由于优先级均小于进程6所以不予于执行;进程6运行10以后，进程2进入，进程2优先级要高于进程6，故进程6中断开始执行进程2，进程6被放回就绪队列尾，状态标记为未完成;此时所有进程都已经进入等待队列完毕，但是没有进程优先级高于进程2，故一直执行进程2直至结束，进程2标志为结束，计算进程2的周转时间为54;运行队列此时没有进程运行所以看就绪队列，其中在进行优先级减1过后进程6优先级为最高，故将进程6加入运行队列执行，标记状态未完成，计算周转时间;其余在就绪队列里的进程重复以上操