BX110937李建辉使用优先数法和轮转法实现操作系统的进程调度

1、BX110937李建辉使用优先数法和简单轮转法实现进程调度课程设计操作系统原理课程设计报告姓 名： 李建辉 班 级： BX1109 学 号： 37 指导老师： 苏庆刚 二一三年 十二 月二十日目 录一、操作系统原理课程设计的目的与要求11目的12要求1二、简述课程设计内容、主要功能和实现环境11课程设计内容12主要功能23实现环境2三、任务的分析、设计、实现和讨论21任务的分析22任务的设计与实现33操作过程和结果分析44思考题的解答和讨论8四、操作系统课程设计小结14五、参考文献15六、附录15BX110937李建辉使用优先数法和简单轮转法实现进程调度课程设计一、操作系统原理课程设计的目的与

2、要求1目的进程是操作系统最重要的概念之一，进程调度又是操作系统核心的主要内容。本实习要求学生独立地用高级语言编写和调试一个简单的进程调度程序。调度算法可任意选择或自行设计，采用优先数法等。本课题可以加深对进程调度和各种调度算法的理解。2要求（1） 设计一个有n个进程并发的进程调度程序。每个进程由一个进程控制块（PCB）表示。进程控制块一般应该包含下述信息：进程名、进程优先数、进程需要运行的时间、占用CPU的时间以及进程的状态等，且可按调度算法的不同而增删。（2） 调度程序采用优先数法，并且调度程序应该具备用户设计优先级的功能。 （3） 算法应能显示或打印各个进程的PID、状态（运行状态R、等待

3、状态W等）和参数（已运行时间等）的变化情况，便于观察诸进程的调度过程进程是操作系统最重要的概念之一，进程调度又是操作系统核心的主要内容。本实习要求学生独立地用高级语言编写和调试一个简单的进程调度程序。调度算法自行设计，主要采用优先数法，本课题可以加深对进程调度和各种调度算法的理解。二、简述课程设计内容、主要功能和实现环境1课程设计内容 进程调度是处理机管理的核心内容。本实验要求用C语言编写和调试一个简单的进程调度程序。选用优先数法五个进程进行调度。每个进程处于运行R(run)、就绪W(wait)和完成F(finish)三种状态之一，并假设起始状态都是就绪状态W。为了便于处理，程序进程的运行时间

4、以时间片为单位计算。各进程的优先数以及进程需要运行的时间片数，在创建进程时均有、由用户自定义，在进程执行中则由机器进行减运算。通过本实验可以加深理解有关进程控制块、进程队列的概念，并体会和了解优先数调度算法的具体实施办法。2主要功能本程序可选用优先数法对N个进程进行调度。每个进程处于运行R(run)、就绪W(wait)和完成F(finish)三种状态之一，并假设起始状态都是就绪状态W。为了便于处理，程序进程的运行时间以时间片为单位计算，根据优先级来调度进程成，用cpu在每个时间片内完成每个进程。3实现环境本次课程设计结合算法的特点，采用Windows操作系统平台。开发工具为Microsoft

5、Visual C+6.0。三、任务的分析、设计、实现和讨论1任务的分析本程序可选用优先数法对N个进程进行调度。每个进程处于运行R(run)、就绪W(wait)和完成F(finish)三种状态之一，并假设起始状态都是就绪状态W。为了便于处理，程序进程的运行时间以时间片为单位计算。各进程的优先数以及进程需要运行的时间片数，在创建进程时均有、由用户自定义，在进程执行中则由机器进行减运算。下面介绍优先数调度算法：优先数法：进程就绪链按优先数大小从高到低排列，链首进程首先投入运行。每过一个时间片，运行进程所需运行的时间片数减1，说明它已运行了一个时间片，优先数也减3，理由是该进程如果在一个时间片中完成不

6、了，优先级应该降低一级，占用cpu的时间加1，接着比较现行进程和就绪链链首进程的优先数，如果仍是现行进程高或者相同，就让现行进程继续进行，否则，调度就绪链链首进程投入运行。原运行进程再按其优先数大小插入就绪链，且改变它们对应的进程状态，直至所有进程都运行完各自的时间片数。简单轮转法：进程就绪链按各进程进入的先后次序排列，进程每次占用处理机的轮转时间按其重要程度登入进程控制块中的轮转时间片数记录项（相当于优先数法的优先数记录项位置）。每过一个时间片，运行进程占用处理机的时间片数加1，然后比较占用处理机的时间片数是否与该进程的轮转时间片数相等，若相等说明已到达轮转时间，应将现运行进程排到就绪链末尾

7、，调度链首进程占用处理机，且改变它们的进程状态，直至所有进程完成各自的时间片。进程控制块PCB结构如下：进程ID链指针优先数/轮转时间片数占用CPU时间片数进程所需时间片数进程状态表3-1进程控制块结构PCB进程控制块链结构如下：TAILRUN1RHEAD3W5W2W表3-2进程控制块链结构其中：RUN当前运行进程指针；HEAD进程就绪链链首指针；TAID进程就绪链链尾指针。2任务的设计与实现算法流程图： 图3-1 优先数法和简单轮转法进程调度框图3操作过程和结果分析优先数调度算法测试数据：数据用可以使用rand（）函数随机产生也可以手动输入产生：IDneedtimepriority12282

8、525313246135439表3-3优先数调度算法测试数据简单轮转法调度算法测试数据：数据用可以使用rand（）函数随机产生也可以手动输入产生：IDneedtimeRound122222352表3-4简单轮转法调度算法测试数据本组程序主要用了10个函数：firstin() ，void prt1(char a) ，void prt2(char a,PCB *q) ，void prt(char algo) ，insert1(PCB *q)，insert2(PCB *p2)，void create1(char alg)，void create2(char alg), priority(char a

9、lg), roundrun(char alg)。算法主要是比较优先数算法和简单轮转法算法。我们的程序是既可以手动输入的，也可以不需要手动输入，里面的优先数和进程需要时间片是既可以随机产生也可以手动输入输入产生，然后有firstin()，void create1(char alg)或者有firstin()，void create2(char alg)函数来利用指针数据结构的特点，对优先数进行比较，然后选出优先数最大的进程，状态为R，剩下的进程继续比较调用void insert1(PCB *q)或者void insert2(PCB *p2)函数，同时产生等待队列。然后priority(char a

10、lg)或者roundrun(char alg)函数在循环中调用指针数据结构进行模拟进程运行。优先数进程调度算法：运行一次需要时间片减1，cpu使用时间片加1，优先数减3，判断需要的时间片是否为0，为0，进程状态变成F，否则与等待队列的进程比较优先数，再次调用void insert1(PCB *q)，生成新的等待队列。直至等待队列为0，循环结束。简单转轮算法进程调度算法：运行一次需要时间片减1，cpu使用处理机时间片加一，计数器加一，再次调用void insert2(PCB *p2)函数，生成新的等待队列。然后比较占用处理机的时间片数是否与该进程的轮转时间片数相等，若相等说明已到达轮转时间，应将

11、现运行进程排到就绪链末尾，调度链首进程占用处理机，且改变它们的进程状态，直至所有进程完成各自的时间片。都会在屏幕上输出。如下图所示。本次程序在编写的过程中没遇到什么较大的困难，在同学的互相帮助下，还是挺圆满的完成了本次课设。优先数调度算法程序运行结果截图：实验每一步的优先数的减少都会生成一组。简单轮转法调度算法程序运行结果截图：实验每一步的优先数的减少都会生成一组。4思考题的解答和讨论4.1. 示例中的程序，没有使用指针型（pointer）数据结构，如何用指针型结构改写本实例，使更能体现C语言的特性（1） 指针型数据结构，变量与主程序 typedef struct node char ID10

12、; /*进程标识符*/ int prio; /*进程优先数*/ int round; /*进程时间轮转时间片*/ int cputime; /*进程占用CPU时间*/ int needtime; /*进程到完成还要的时间*/ int count; /*计数器*/ char state; /*进程的状态*/ struct node *next; /*链指针*/PCB;PCB *finish,*ready,*tail,*run; /*队列指针*/（2） 进程调度程序1) 优先数法进程调度程序priority(char alg) while(run!=NULL) /*当运行队列不空时，有进程正在运行

13、*/ run->cputime=run->cputime+1; run->needtime=run->needtime-1; run->prio=run->prio-3; /*每运行一次优先数降低3个单位*/ if(run->needtime=0) /*如所需时间为0将其插入完成队列*/ run->next=finish; finish=run; run->state='F' /*置状态为完成态*/ run=NULL; /*运行队列头指针为空*/ if(ready!=NULL) /*如就绪队列不空*/ firstin();

14、/*将就绪对列的第一个进程投入运行*/ else if(ready!=NULL)&&(run->prio<ready->prio) /*没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列*/ run->state='W' insert1(run); firstin(); /*将就绪队列的第一个进程投入运行*/ prt(alg); /*输出进程PCB信息*/ 2) 轮转法进程调度程序roundrun(char alg) while(run!=NULL) run->cputime=run->cputime+1; run-

15、>needtime=run->needtime-1; run->count=run->count+1; if(run->needtime=0)/*运行完将其变为完成态，插入完成队列*/ run->next=finish; finish=run; run->state='F' run=NULL; if(ready!=NULL) firstin(); /*就绪对列不空，将第一个进程投入运行*/ else if(run->count=run->round) /*如果时间片到*/ run->count=0; /*计数器置0*/

16、 if(ready!=NULL) /*如就绪队列不空*/ run->state='W' /*将进程插入到就绪队列中等待轮转*/ insert2(run); firstin(); /*将就绪对列的第一个进程投入运行*/ prt(alg); /*输出进程信息*/ 4.2.如何在程序中真实地模拟进程运行的时间片在程序中设置时间片大小，模拟进程运行的时间片，设置cputieme模拟cpu的运行，当进程从就绪队列通过指针调进运行队列，使运行指针处于运行状态，每次在时间片时间范围内运行，运行结束cputime自动加上一个时间片，needtime（完成整个进程所需要的时间）减去一个时间

17、片，从而模拟了进程运行的时间片。4.3.如果增加进程的“等待”状态，即进程因请求输入输出等问题而挂起的状态，如何在程序中实现如果增加进程的等待状态，进程在输入输出等时处于阻塞状态，利用java高级语言，在菜单栏上增加阻塞按钮，菜单栏上设置开始，添加，阻塞进程的按钮，点击添加进程则创建一个进程，在界面的左侧显示进程的号，进程完成所需要的时间和进程到达时间，点击开始菜单则会显示进程所需要时间和进程运行时间，当点击阻塞，进程将被阻塞，等待结束，进程将调进就绪队列再从就绪队列调进运行队列完成进程。11public class RR extends JFrame implements ActionLis

18、tener,RunnableThread myThread;JPanel p1=new JPanel(); /*就绪*/JPanel p2=new JPanel(); /*控制台*/JPanel p3=new JPanel(); /*完成*/JPanel p4=new JPanel(); /*左边*/JButton b=new JButton10; /*就绪队列*/JButton d=new JButton10; /*完成队列*/JButton jbBegin,jbAdd,jbSuspend;public int pcb=new int 105; /*最多10个进程。存放进程信息：第一列表示所

19、需时间片，第二列表示已执行与否，第三列表示剩下的时间片，第四列表示到达时间，第五列进程ID*/public final static int pT=20;/*单位时间片长度 Piece of Time*/public int curTime=0; /*作为程序运行时的时间*/public int pcbCount=0; /*进程数量，最多10个进程*/boolean Continue=false; /*开始执行标志*/boolean Susp=false; /*增加进程标志*/public RR()/*线程*/myThread=new Thread(this);myThread.start()

20、;/*程序窗口初始化*/JFrame f=new JFrame();f.setTitle("时间片轮转调度算法（RR）");f.setSize(650,450);f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);f.setVisible(true);f.setLayout(new GridLayout(1,2);/*进程信息初始化*/for(int i=0;i<10;i+)pcbi1=0; /*无进程，不显示*/bi=new JButton();p1.setVisible(true);p1.setLayout(new G

21、ridLayout(10,1);for(int i=0;i<10;i+)p1.add(bi);/*初始化“添加进程”和“开始”按钮*/jbBegin=new JButton(" 开始 ");jbAdd=new JButton(" 添加进程 ");jbSuspend=new JButton(" 阻塞 ");p2.setVisible(true);p2.setLayout(new GridLayout(3,1);p2.add(jbBegin);p2.add(jbAdd);p2.add(jbSuspend);f.add(p1);f.a

22、dd(p2);/*添加事件监听*/jbBegin.addActionListener(this);jbAdd.addActionListener(this);jbSuspend.addActionListener(this);public void actionPerformed(ActionEvent e)if (e.getSource() = jbBegin)if(Continue=false)Continue=true;if (e.getSource() = jbAdd)if(pcbCount<10)int tNeed=(int)(Math.random()*100);pcbpcb

23、Count0=tNeed;pcbpcbCount1=1;pcbpcbCount2=tNeed;pcbpcbCount3=curTime;pcbpcbCount4=pcbCount+1;bpcbCount.setText(" 进程"+(pcbCount+1)+" 到达时间"+curTime+" 需要时间"+tNeed+" ");pcbCount+;curTime+;if (e.getSource() = jbSuspend)Susp=true;public void run()while(true)if(Contin

24、ue=true)int select=0;/选出最先到达的进程，冒泡排序for(int i=0;i<pcbCount;i+)for(int j=0;j<pcbCount-i-1;j+)if(pcbj3>pcbj+13)int temp=pcbj;pcbj=pcbj+1;pcbj+1=temp;/重新显示就绪队列for(int j=0;j<10;j+)if(pcbj1=1)bj.setText(" 进程"+(pcbj4)+" 到达时间"+pcbj3+" 需要时间"+pcbj0+" "+&quo

25、t; 剩余时间"+pcbj2);if(pcbj1=2)bj.setText(" 进程"+(pcbj4)+" 执行完毕");/*已执行的进程不能再执行，置select 为-1作为标志*/if(pcb01=2)select=-1;/被选中而开始执行的进程，则不再在队列中显示，把显示标记置1elsepcb01=1;/放到开始按钮（CPU）上显示if(select!=-1)for(int j=1;j<=pT;j+)if(Susp=true)jbBegin.setText("处理I/O请求，"+"进程"+(p

26、cb04)+" 阻塞");tryThread.sleep(8888);catch(InterruptedException e);Susp=false;break;elsecurTime+;if(pcb02>=0)jbBegin.setText("进程"+(pcb04)+" 需要时间"+pcb00+" 正在执行: "+pcb02-);elsebreak;tryThread.sleep(100);catch(InterruptedException e);pcb03=curTime;/*如果已经执行完*/if(

27、pcb02<0)pcb01=2;pcb03=1000000;public static void main(String args)new RR();19四、操作系统课程设计小结这次课程设计，我们小组抽中了第二组，使用优先数法实现操作系统的进程调度，经过小组的讨论，组长将思考题交给了我和施彬彬，随后我和施彬彬浏览了操作系统课程设计指导书new和操作系统课程设计-格式模板，对这次实验内容有了详细地了解，弄清楚这次课程设计是关于处理机调度的问题，明确了方向，我们开始复习课件第二章处理机管理。通过复习课件我知道了常用的调度放算法：先进先出法，短进程优先法，时间片轮转法，优先级调度法，短作业优先

28、调度算法，最高相应比优先调度。在多任务系统中，进程调度是CPU管理的一项核心工作。根据调度模式的不同，多任务系统有两种类型，即非抢占式和抢占式。其中，优先数法是非抢占式调度策略，进程调度算法是系统效率的关键，它确定了系统对资源，特别是对CPU资源的分配策略，因而直接决定着系统最本质的性能指标，如相应速度和吞吐量等。然后，我和施彬彬再分工，我负责编写程序，施彬彬负责写报告和画流程图，经过我在网上大量搜索，找到了一些源程序，但是这些源程序有的使用了VC+里没有的函数，要么就是手动输入不符合这次课程设计的要求，要么就是随进函数rand()的随机数太大，对此，我不断缩小随机数的大小，通过修改代码实现进

29、程完成时间和进程优先数自动产生，不需要手动产生，实现了既可以手动输入数据也可以自动产生数据，使搜索的程序经过编译测试符合本次的实验要求，还将使用简单轮转法实现操作系统的进程调度和使用优先数法实现操作系统的进程调度用一个程序实现。这次课程设计不仅考察了我c语言的编程编译测试能力，也考察了我的操作系统原理的知识，非常有意义和实用价值。五、参考文献1 苏庆刚，操作系统原理与应用教程 上海：上海交通大学出版社2012.01.012 胡志刚，谭长庚等. 计算机操作系统.中南大学出版社. 20053 谭浩强，C程序设计（第四版）.北京：清华大学出版社.2010.06.04 4 王旭阳，李睿 操作系统原理北

30、京：机械工业出版社，20095 汤子瀛等 计算机操作系统 西安电子科技大学出版社六、附录源代码程序:#include "stdio.h"#include "stdlib.h"#include "string.h"#include<math.h>typedef struct node char ID10; /*进程标识符*/ int prio; /*进程优先数*/ int round; /*进程时间轮转时间片*/ int cputime; /*进程占用CPU时间*/ int needtime; /*进程到完成还要的时间*/

31、int AllTime; int count; /*计数器*/ char state; /*进程的状态*/ struct node *next; /*链指针*/PCB;PCB *finish,*ready,*tail,*run; /*队列指针*/int N; /*进程数*/firstin() run=ready; /*就绪队列头指针赋值给运行头指针*/ run->state='R' /*进程状态变为运行态*/ ready=ready->next; /*就绪对列头指针后移到下一进程*/void prt1(char a) if(toupper(a)='P'

32、;) /*优先数法*/ printf(" ID AllTime cputime needtime priority staten"); else if(toupper(a)='R') printf(" ID cputime needtime count round staten"); else printf(" not exist!n");void prt2(char a,PCB *q) if(toupper(a)='P') /*优先数法的输出*/ printf(" %-10s%-9d%-8d

33、%-11d%-10d%-3cn",q->ID,q->AllTime, q->cputime,q->needtime,q->prio,q->state); else if (toupper(a)='R')/*轮转法的输出*/ printf(" %-8s%-9d%-9d%-9d%-9d%-3cn",q->ID, q->cputime,q->needtime,q->count,q->round,q->state); else printf(" not exist!n&quo

34、t;); void prt(char algo) PCB *p; prt1(algo); /*输出标题*/ if(run!=NULL) /*如果运行指针不空*/ prt2(algo,run); /*输出当前正在运行的PCB*/ p=ready; /*输出就绪队列PCB*/ while(p!=NULL) prt2(algo,p); p=p->next; p=finish; /*输出完成队列的PCB*/ while(p!=NULL) prt2(algo,p); p=p->next; getchar(); /*按任意键继续*/insert1(PCB *q) PCB *p1,*s,*r;

35、int b; s=q; /*待插入的PCB指针*/ p1=ready; /*就绪队列头指针*/ r=p1; /*r做p1的前驱指针*/ b=1; while(p1!=NULL)&&b) /*根据优先数确定插入位置*/ if(p1->prio>=s->prio) r=p1; p1=p1->next; else b=0; if(r!=p1) /*如果条件成立说明插入在r与p1之间*/ r->next=s; s->next=p1; else s->next=p1; /*否则插入在就绪队列的头*/ ready=s; insert2(PCB *p

36、2) tail->next=p2; /*将新的PCB插入在当前就绪队列的尾*/ tail=p2; p2->next=NULL;void create1(char alg) PCB *p; int i; char na10; ready=NULL; /*就绪队列头指针*/ finish=NULL; /*完成队列头指针*/ run=NULL; /*运行队列指针*/ /printf("Enter ID(数字或字符串）time(整数) and priority(整数) of processn"); /*输入进程标识和所需时间创建PCB*/ printf("En

37、ter ID(进程号用数字或字符串表示)n"); for(i=1;i<=N;i+) p=malloc(sizeof(PCB); scanf("%s",na); /scanf("%d",&time); /scanf("%d",&priority); strcpy(p->ID,na); p->cputime=0; /p->needtime=time; p->needtime=(rand()+1)%37-3; if(p->needtime>=10) p->needti

38、me=p->needtime%10; p->AllTime=p->needtime; /p->needtime=time; p->state='w' /*p->prio=50-time; / p->prio=priority; p->prio=(rand()+11)%41; if(ready!=NULL) /*就绪队列不空调用插入函数插入*/ insert1(p); else p->next=ready; /*创建就绪队列的第一个PCB*/ ready=p; system("cls"); printf(&

39、quot; output of priority:n"); printf("*n"); prt(alg); /*输出进程PCB信息*/ run=ready; /*将就绪队列的第一个进程投入运行*/ ready=ready->next; run->state='R'void create2(char alg) PCB *p; int i; char na10; ready=NULL; finish=NULL; run=NULL; /printf("Enter ID(数字或字符串) and time(整数) of round pr

40、ocessn"); printf("Enter ID(进程号用数字或字符串表示)n"); for(i=1;i<=N;i+) p=malloc(sizeof(PCB); scanf("%s",na); /scanf("%d",&time); strcpy(p->ID,na); p->cputime=0; p->needtime=(rand()+1)%37-2; if(p->needtime>=10) p->needtime=p->needtime%10; else if(

41、p->needtime<=0) p->needtime=p->needtime+3; /p->needtime=time; p->count=0; /*计数器*/ p->state='w' p->round=2; /*时间片*/ if(ready!=NULL) insert2(p); else p->next=ready; ready=p; tail=p; system("cls"); printf(" output of roundn"); printf("*n"

42、); prt(alg); /*输出进程PCB信息*/ run=ready; /*将就绪队列的第一个进程投入运行*/ ready=ready->next; run->state='R'priority(char alg, int H) while(run!=NULL) /*当运行队列不空时，有进程正在运行*/ run->cputime=run->cputime+H ; run->needtime=run->needtime-H; if(run->needtime<0) run->needtime=0; run->prio=run->prio-3; /*每运行一次优先数降低3个单位*/ if(run->needtime=0) /*如所需时间为0将其插入完成队列*/ run->next=finish; finish=run; run->state='F' /*置状态为完成态*/ run=NULL; /*运行队列