使用优先数法和简单轮转法实现进程调度课程设计报告

操作系统原理课程设计报告姓名： 班级： 学号： 指导老师:二O三年十二月二十日目录一、操作系统原理课程设计的目的与要求11.目的12要求1二、简述课程设计内容、主要功能和实现环境11课程设计内容12主要功能23.实现环境2三、任务的分析、设计、实现和讨论21 任务的分析22任务的设计与实现33操作过程和结果分析44思考题的解答和讨论8四、操作系统课程设计小结14五、参考文献15六、附录15一、操作系统原理课程设计的目的与要求1 目的进程是操作系统最重要的概念之一，进程调度又是操作系统核心的主要内容。 本实习要求学生独立地用高级语言编写和调试一个简单的进程调度程序。调度算 法可任意选择或自行设计，采用优先数法等。本课题可以加深对进程调度和各种 调度算法的理解。2 要求(1) 设计一个有n个进程并发的进程调度程序。每个进程由一个进程控 制块(PCB )表示。进程控制块一般应该包含下述信息：进程名、进程 优先数、进程需要运行的时间、占用CPU的时间以及进程的状态等，且 可按调度算法的不同而增删。(2) 调度程序采用优先数法，并且调度程序应该具备用户设计优先级的 功能。(3) 算法应能显示或打印各个进程的PID、状态(运行状态R、等待状态 W等)和参数(已运行时间等)的变化情况，便于观察诸进程的调度过 程进程是操作系统最重要的概念之一，进程调度又是操作系统核心的主要内容。 本实习要求学生独立地用高级语言编写和调试一个简单的进程调度程序。调度算 法自行设计，主要采用优先数法，本课题可以加深对进程调度和各种调度算法的 理解。二、简述课程设计内容、主要功能和实现环境1 课程设计内容进程调度是处理机管理的核心内容。本实验要求用C语言编写和调试一个 简单的进程调度程序。选用优先数法五个进程进行调度。每个进程处于运行R(run)、就绪W(wait)和完成F(finish)三种状态之一，并假设起始状态都是就绪状 态W。为了便于处理，程序进程的运行时间以时间片为单位计算。各进程的优 先数以及进程需要运行的时间片数，在创建进程时均有、由用户自定义，在进程 执行中则由机器进行减运算。通过本实验可以加深理解有关进程控制块、进程队 列的概念，并体会和了解优先数调度算法的具体实施办法。2 主要功能本程序可选用优先数法对N个进程进行调度。每个进程处于运行R(run)、 就绪W(wait)和完成F(finish)三种状态之一，并假设起始状态都是就绪状态W。 为了便于处理，程序进程的运行时间以时间片为单位计算，根据优先级来调度进 程成，用cpu在每个时间片内完成每个进程。3 实现环境本次课程设计结合算法的特点，采用Windows操作系统平台。开发工具为Microsoft Visual C+6.0。三、任务的分析、设计、实现和讨论1 任务的分析本程序可选用优先数法对N个进程进行调度。每个进程处于运行R(run)、 就绪W(wait)和完成F(finish)三种状态之一，并假设起始状态都是就绪状态W。 为了便于处理，程序进程的运行时间以时间片为单位计算。各进程的优先数以及 进程需要运行的时间片数，在创建进程时均有、由用户自定义，在进程执行中则 由机器进行减运算。下面介绍优先数调度算法：优先数法:进程就绪链按优先数大小从高到低排列，链首进程首先投入运行。 每过一个时间片，运行进程所需运行的时间片数减1,说明它已运行了一个时间 片，优先数也减3,理由是该进程如果在一个时间片中完成不了，优先级应该降 低一级，占用cpu的时间加1,接着比较现行进程和就绪链链首进程的优先数, 如果仍是现行进程高或者相同，就让现行进程继续进行，否则，调度就绪链链首 进程投入运行。原运行进程再按其优先数大小插入就绪链，且改变它们对应的进 程状态，直至所有进程都运行完各自的时间片数。简单轮转法：进程就绪链按各进程进入的先后次序排列，进程每次占用处理 机的轮转时间按其重要程度登入进程控制块中的轮转时间片数记录项（相当于优 先数法的优先数记录项位置）。每过一个时间片，运行进程占用处理机的时间片 数加1,然后比较占用处理机的时间片数是否与该进程的轮转时间片数相等，若 相等说明已到达轮转时间，应将现运行进程排到就绪链末尾，调度链首进程占用 处理机，且改变它们的进程状态，直至所有进程完成各自的时间片。进程控制块 PCB结构如下：进程ID石指针优先数/轮转时间片数占用CPU时间片数进程所需时间片数呢程状态表3-1进程控制块结构PCB进程控制块链结构如下：RUNHEAD,TAIL1352RWWW表3-2进程控制块链结构 其中：RUN当前运行进程指针；HEAD进程就绪链链首指针； TAID进程就绪链链尾指针。2 任务的设计与实现算法流程图：图3-1优先数法和简单轮转法进程调度框图3 操作过程和结果分析优先数调度算法测试数据：数据用可以使用rand ()函数随机产生也可以手动输入产生:IDneedtimepriority12282525313246135439表3-3优先数调度算法测试数据简单轮转法调度算法测试数据：数据用可以使用rand ()函数随机产生也可以手动输入产生:IDneedtimeRound122222352表3-4简单轮转法调度算法测试数据本组程序主要用了 10 个函数：firstin() ， void prtl(char a) ， voidprt2(char a,PCB *q) ， void prt(char algo) ， insert1 (PCB *q), insert2(PCB *p2), void createl(char alg), void create2(char alg), priority (charalg), roundrun(char alg)。算法主要是比较优先数算法和简单轮转法算法。我们的程序是既可以手动输入的，也可以不需要手动输入，里面的优先数和 进程需要时间片是既可以随机产生也可以手动输入输入产生，然后有firstin(), void createl(char alg)或者有 firstin()，void create2(char alg)函数来利 用指针数据结构的特点，对优先数进行比较，然后选出优先数最大的进程，状态 为R，剩下的进程继续比较调用void insertl(PCB *q)或者void insert2(PCB *p2) 函数，同时产生等待队列。然后priority(char alg)或者roundrun(char alg) 函数在循环中调用指针数据结构进行模拟进程运行。优先数进程调度算法：运行 一次需要时间片减1, cpu使用时间片加1,优先数减3,判断需要的时间片是否 为0为0,进程状态变成F，否则与等待队列的进程比较优先数，再次调用void insertl(PCB *q)，生成新的等待队列。直至等待队列为0，循环结束。简单转 轮算法进程调度算法：运行一次需要时间片减1, cpu使用处理机时间片加一， 计数器加一，再次调用void insert2(PCB *p2)函数，生成新的等待队列。然后 比较占用处理机的时间片数是否与该进程的轮转时间片数相等，若相等说明已到 达轮转时间，应将现运行进程排到就绪链末尾，调度链首进程占用处理机，且改 变它们的进程状态，直至所有进程完成各自的时间片。都会在屏幕上输出。如下 图所示。本次程序在编写的过程中没遇到什么较大的困难，在同学的互相帮助下，还 是挺圆满的完成了本次课设。优先数调度算法程序运行结果截图：实验每一步的优先数的减少都会生成一组。：课程设讯De bu g调考题程事E KTsy. exeoutput of priority：4 IDAllTine412cput ineQneedtime1A UTine412needtlme412priority3932282513priority3632282513stateustateRw4H.几XX 其只 貝其 J:MXXJC貝几XX 其只 貝其 J:MXXJCM：標程设计bu g思考题程序名KTsy. * -回4IDAlli imecput linenecdtInepriority5 tdte463310Bn256017FLI123025F313029F546033FIDfill!imecpu t讪日needtineDpioritystate46607F2EG019F123025F313029F546033F简单轮转法调度算法程序运行结果截图: 实验每一步的优先数的减少都会生成一组。：頒程设计氐bu g偲考题程懿KTsy. exe -1=1= |.joutput ofpoundIDfaKcput imeneedt imeLcountroundstate=_J103Q2w203&2w3B62wIDcput imeneedt imecountroundstate20302R30602w113012F川误程设计氐bu gl思考题程序5 KTsy. exe -B 1旦L空J一 4IDcput imeneedt imecountroundst ateLI30602R23012Fi3012FIDcput imeneedt imecountroundst ate33312B23012F13012Fr4 思考题的解答和讨论4.1.示例中的程序，没有使用指针型(pointer)数据结构，如何用 指针型结构改写本实例，使更能体现C语言的特性(1) 指针型数据结构，变量与主程序typedef struct nodechar ID10; /*进程标识符*/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) /*当运行队列不空时，有进程正在运行*/run-cputime=run-cputime+l; run-needtime=run-needtime-l;run-prio=run-prio-3; /*每运行一次优先数降低3个单位*/ if(run-needtime=O) /*如所需时间为0将其插入完成队列*/ run-next=finish;finish=run;run-state=F; /*置状态为完成态*/ run=NULL; /*运行队列头指针为空*/ if(ready!=NULL) /*如就绪队列不空*/firstin(); /*将就绪对列的第一个进程投入运行*/else if(ready!=NULL)&(run-priovready-prio) /* 没有运行完同时 优先数不是最大，则将其变为就绪态插入到就绪队列*/run-state=W;insert1(run);firstin(); /*将就绪队列的第一个进程投入运行*/ prt(alg); /*输出进程PCB信息*/2)轮转法进程调度程序roundrun(char alg)while(run!=NULL)run-cputime=run-cputime+1; run-needtime=run-needtime-1;run-count=run-count+l;if(run-needtime=O)/*运行完将其变为完成态，插入完成队列*/run-next=finish;finish=run;run-state=F;run=NULL;if(ready!=NULL)firstin(); /*就绪对列不空，将第一个进程投入运行*/elseif(run-count=run-round) /* 如果时间片到 */run-count=0; /* 计数器置 0*/if(ready!=NULL) /*如就绪队列不空*/run-state=W; /*将进程插入到就绪队列中等待轮转*/ insert2(run);firstin(); /*将就绪对列的第一个进程投入运行*/prt(alg); /*输出进程信息*/4.2如何在程序中真实地模拟进程运行的时间片在程序中设置时间片大小，模拟进程运行的时间片，设置cputieme模拟cpu 的运行，当进程从就绪队列通过指针调进运行队列，使运行指针处于运行状态， 每次在时间片时间范围内运行，运行结束 cputime自动加上一个时间片， need time （完成整个进程所需要的时间）减去一个时间片，从而模拟了进程运行 的时间片。4.3如果增加进程的“等待”状态，即进程因请求输入输出等问题而 挂起的状态，如何在程序中实现如果增加进程的等待状态，进程在输入输出等时处于阻塞状态，利用java 高级语言，在菜单栏上增加阻塞按钮，菜单栏上设置开始，添加，阻塞进程的按 钮，点击添加进程则创建一个进程，在界面的左侧显示进程的号，进程完成所需 要的时间和进程到达时间，点击开始菜单则会显示进程所需要时间和进程运行时 间，当点击阻塞，进程将被阻塞，等待结束，进程将调进就绪队列再从就绪队列 调进运行队列完成进程。public class RR ext ends JFrame implementsActionListener,RunnableThread myThread;JPanelp1=newJPanel();/*就绪*/JPanel/*控制台*/p2二newJPanel();JPanel/*完成*/p3=newJPanel();JPanel/*左边*/p4二newJPanel();JButtonb二newJBu tto n10; /* 就绪队列*/JButtond二newJBu tto n10; /* 完成队列*/JButtonjbBegin,jbAdd,jbSuspend;public int pcb二new int 105; /*最多10个进程。存放进 程信息：第一列表示所需时间片，第 二列表示已执行与否，第三列表示剩 下的时间片，第四列表示到达时间， 第五列进程ID*/public final static int pT=20;/*单位时间片长度Piece of Time*/public int curTime=0;/*作为程序运行时的时间*/public intpcbCount=0;/*进程数量，最多10个进程*/booleanContinue二false;/*开始执行标志*/booleanSusp=false;/*增加进程标志*/public RR()/*线程*/ myThread二newThread(this); myThread.s tart(); /*程序窗口初始化*/JFrame f=new JFrame();f.se tTit le(“时间片轮转 调度算法(RR) )；f.se tSize(650,450);f.setDefaultCloseOperation(JF rame.EXIT_ON_CLOSE);f.se tV isible( true);f.se tLayo ut( newGridLayo ut( 1,2);/*进程信息初始化*/for(i nt i=0;i10;i+) pcbil=0;/*无进程，不显示*/bi=newJBu tt on();pl.se tV isible( true); pl.se tLayo ut( new GridLayo ut(10,1);for(int i=0;i10;i+) p1.add(bi);/*初始化“添加进程”和 “开始”按钮*/jbBegin二new JButton(“ 开始)；jbAdd二newJButton(添加进程)；jbSuspend二newJBu tt on(阻塞)；p2.se tV isible( true); p2.se tLayo ut( new GridLayo ut( 3,1);p2.add(jbBegin); p2.add(jbAdd); p2.add(jbSuspend); f.add(pl);f.add(p2); /*添加事件监听*/jbBegin.addActionListener(thi s);jbAdd.addAc tio nLis tener( this)7jbSuspend.addActionListener(t his);publicvoidactionPerformed(ActionEvent e) if (e.ge tSource() = jbBegin)if(Continue二二false)Continue二true;if(e.ge tSource() =jbAdd)if(pcbCoun t10)inttNeed=(in t)(Ma th.random ()* 100); pcbpcbCou nt0=tN eed; pcbpcbCou nt1 = 1; pcbpcbCount2二tNeed; pcbpcbCount3=curTime; pcbpcbCount4=pcbCount+1; bpcbCount.setText( 进 程+(pcbCoun t+1)+ 到 达 时 间 +curTime+ 需要时间 +tNeed+ )；pcbCount+;curTime+;if(e.ge tSource() =jbSuspend)Susp二true;public void run()while( true)if(Co ntin ue二二t rue)int select=0;/选出最先到达的进程，冒泡排序for(i nti=0;ipcbCount;i+)for(i ntj=0;jpcbj+l3) int t emp=pcbj;pcbj二pcbj+l;pcbj+l二t emp;/重新显示就绪 队列for(i nt j=0;j10;j+)if(pcbj1=1)bj.se tTex t(“进 程+(pcbj4)+ 到 达 时 间 +pcbj3+需要时 间+pcbjO+ 剩 余时间+pcbj2);if(pcbj1=2)bj.se tTex t(进 程+(pcbj4)+ 执行完毕)；/*已执行的进程 不能再执行，置select为T作为标 志*/if(pcb0l=2)selec t=T; /被选中而开始 执行的进程，则不再在队列中显示， 把显示标记置1elsepcb01=1;/放到开始按钮(CPU)上显示j=1;j=0)jbBegin.se tTex t( 进 程 +(pcb04)+ 需要时 间 +pcbOO+ 正在执行： +pcb02);elsebreak;tryThread.sleep(100);catch(InterruptedException e);pcb03=curTime;/*如果已经执行if(selec t!二 T)完*/if(pcb020)pcb0l=2; pcb03=1000000;public static void main(S tring args)new RR();四、操作系统课程设计小结这次课程设计，我们小组抽中了第二组，使用优先数法实现操作系统的进程 调度，经过小组的讨论，组长将思考题交给了我和施彬彬，随后我和施彬彬浏览 了操作系统课程设计指导书new和操作系统课程设计-格式模板，对这次实 验内容有了详细地了解，弄清楚这次课程设计是关于处理机调度的问题，明确了 方向，我们开始复习课件第二章处理机管理。通过复习课件我知道了常用的调度 放算法：先进先出法，短进程优先法，时间片轮转法，优先级调度法，短作业优 先调度算法，最高相应比优先调度。在多任务系统中，进程调度是CPU管理的一 项核心工作。根据调度模式的不同，多任务系统有两种类型，即非抢占式和抢占 式。其中，优先数法是非抢占式调度策略，进程调度算法是系统效率的关键，它 确定了系统对资源，特别是对CPU资源的分配策略，因而直接决定着系统最本质 的性能指标，如相应速度和吞吐量等。然后，我和施彬彬再分工，我负责编写程序，施彬彬负责写报告和画流程图， 经过我在网上大量搜索，找到了一些源程序，但是这些源程序有的使用了 VC+ 里没有的函数，要么就是手动输入不符合这次课程设计的要求，要么就是随进函 数rand()的随机数太大，对此，我不断缩小随机数的大小，通过修改代码实现 进程完成时间和进程优先数自动产生，不需要手动产生，实现了既可以手动输入 数据也可以自动产生数据，使搜索的程序经过编译测试符合本次的实验要求，还 将使用简单轮转法实现操作系统的进程调度和使用优先数法实现操作系统的进 程调度用一个程序实现。这次课程设计不仅考察了我c语言的编程编译测试能力，也考察了我的操作系统原理的知识，非常有意义和实用价值。五、参考文献1 苏庆刚，操作系统原理与应用教程上海：上海交通大学出版社2 胡志刚，谭长庚等.计算机操作系统中南大学出版社.20053 谭浩强，C程序设计（第四版）北京：清华大学出版社4 王旭阳，李睿操作系统原理北京：机械工业出版社，20095 汤子瀛等计算机操作系统西安电子科技大学出版社六、附录源代码程序：#include st dio.h#include stdlib.h#include string.h #include typedef struct nodechar ID10;/* 进程标识符*/int prio;/*进程优先数*/int round; /*进程时间轮 转时间片*/int cputime; /*进程占用 CPU时间*/int need time; /* 进程到完 成还要的时间*/int AllTime;int cou nt; /* 计数器*/ char state; /*进程的状态 */st ruc t node * nex t; /*链扌旨 针*/PCB;PCB*finish,*ready,*tail,*run; /* 队 列指针*/int N; /*进程数*/firs tin()run二ready;/*就绪队列头指针赋值给运行头指针*/run-state=R;/* 进程状态变为运行态*/ready二ready-next; /* 就 绪对列头指针后移到下一进程*/void prt1 (char a)if(toupper(a)二二P) /*优 先数法*/printf(“IDAllTime cputimeneedtimepriority staten);else if(to upper(a)二二R) printf(“ ID cputime needtimecountroundstaten);elseprintf(“notexist!n);void prt 2(char a,PCB *q)if(to upper(a)二二P)/*优先数法的输出*/printf(-10s%-9d%-8d%-lld%-l0d%-3cn,q-ID,q-AllTime,qcp uti me,qneed ti me,qprio, q-state);elseif(t oupper(a)二二R)/* 轮转法的输出*/printf(%8s%9d%9d%9d%9d%-3cn,q-ID,qcp uti me,qneed ti me,qcou nt ,q-round,q-s tat e);elseprintf(notexist!n)；void prt(char algo)PCB *p;prt l(algo); /* 输出标题*/if(run!二NULL) /* 如果运行 指针不空*/prt2(algo,run); /*输出当前正在运行的PCB*/p二ready; /*输出就绪队列PCB */while(p!=NULL)prt 2(algo,p);p=pnext;p二finish; /*输出完成队 列的PCB*/while(p!=NULL)prt 2(algo,p);p=pnext;get char(); /*按任意键继 续*/insertl(PCB *q)PCB *p1, *s,*r;int b;s=q; /*待插入的PCB指针 */pl二ready; /*就绪队列头指 针*/r=p1; /*r做pl的前驱指针 */b=1;while(p1!=NULL)&b)/*根据优先数确定插入位置*/ if(p1prio=sprio) r=p1;p1=p1next;elseb=0;if(r!=p1)/*如果条件成立说明插入在r与pl之间*/rnext二s; snext二pl;elsesnex t二pl; /* 否则插 入在就绪队列的头*/ready=s;insert2(PCB *p2)t ailnex t二p2;/* 将新的PCB插入在当前就绪队列的尾*/tail=p2;p2next二NULL;void createl(char alg)PCB *p;int i;char na10;ready二NULL; /*就绪队列头 指针*/finish二NULL; /* 完成队列 头指针*/run二NULL; /*运行队列指针 */printf(Enter ID(数字或 字符串)t ime(整数)and priority (整数)of processn); /* 输入进程标识和所需时间创建PCB*/printf(Enter ID(进程号用 数字或字符串表示)n)；for(i=1;iID,na); p-cputime=0; /p-needtime二time;p-need ti me=(rand()+l)%37-3; if(p-needtime=10)p-needtime=p-needtime%10;p-AllTime=p-needtime;/p-needtime二time; p-s tat e=w;/*p-prio=50-time; / p-prio二priority;p-prio=(rand()+ll)%41; if(ready!=NULL) /*就绪 队列不空调用插入函数插入*/insertl (p); else p-nex t二 ready; /* 创建就 绪队列的第一个PCB*/ready=p;sys tem(cls)；printf(outputof priority:n)； printf(* *n);prt (alg); /* 输出进程 PCB 信息*/run=ready; /*将就绪队列的 第一个进程投入运行*/ready二ready-next;run-s tat e=R;void create2(char alg)PCB *p;int i;char na10;ready二NULL;finish二NULL;run二NULL;/printf(Enter ID(数字或 字符串)and t ime(整数)of round processn);printf(Enter ID(进程号用 数字或字符串表示)n)；for(i=1;iID,na); p-cputime=0;p-need time=(rand()+1)%37-2;if(p-needtime=10)p-needtime=p-needtime%10;elseif(p-needtimeneedtime=p-needtime+3;/p-needtime二time; p-count=0; /*计数器*/ p-s tat e=w;p-round=2; /* 时间片 */if(ready!二NULL)inser t2(p);elsepnext二ready;ready二p;tail=p;sys tem(cls);printf(“output of roundn);printf(* *n) prt(alg);/*输出进程PCB信息*/run二ready; /*将就绪队列 的第一个进程投入运行*/ready=readynext; runs tat e=R;priority (char alg, int H)while(run!=NULL) /* 当运 行队列不空时，有进程正在运行*/runneedtime=runneedtimeH;if(runneedtimeneedtime=0;runprio=runprio3;/*每运行一次优先数降低3个单位*/ if(runneedtime=0) /*如所需时间为0将其插入完成队列 */runnext二finish;finish二run;runstate=F;/* 置状态为完成态*/run二NULL; /*运行队列头 指针为空*/if(ready!=NULL) /*如就绪 队列不空*/firstin(); /*将就绪对 列的第一个进程投入运行*/elseif(ready!=NULL)&(runprioprio) /*没有运行完同时优先 数不是最大，则将其变为就绪态插入 到就绪队列*/runs tat e=W;insertl(run);firstin(); /*将就绪队 列的第一个进程投入运行*/prt(alg); /*输出进程PCB信息*/ roundrun(char alg,i nt H) while(run!二NULL)runcputime=runcputime+Hrunneedtime=runneedtimeH;runcputime=runcputime+H;if(run-needtimeneedtime=O;runcount二runcount+1;if(runneedtime=O)/* 运行完将 其变为完成态，插入完成队列*/runnext二finish; finish二run;runs tat e=F; run二NULL;if(ready!二NULL) firstin(); /*就绪对列 不空，将第一个进程投入运行*/elseif(runcount二二run-round)/*如果时间片到*/runcount=O;/* 计数器置0*/if(ready!=NULL) /*如 就绪队列不空*/runstate=W; /* 将进程插入到就绪队列中等待轮转 */inser t2(run);firs tin(); /* 将就 绪对列的第一个进程投入运行*/ prt(alg); /*输出进程信 息*/ main() 一char algo; /* 算法标记*/ int比sys tem(cls);doprintf(typethealgorithm:P/R(priority/roundrob in)n);scanf(%c, &algo); /*输入 字符确定算法*/prin tf(请输入时间片大小： n);scanf(%d, &H);printf(Enterprocessnumber:(输入int型正整数)n);scanf(%d, &N); /* 输入进 程数*/if(algo二二,P，|algo二二,p，)crea tel(algo); /* 优先 数法*/prior ity (algo,H);else if(algo=，R，|algo=，r，)crea te2(algo); /* 轮转法 */roundrun(algo,H);elseprin tf(没有相应的匹 配算法，无法进行进程调度！ n)； prin tf(请按任意键继续： n)；while(ge tch();