多进程调度课程设计

《多进程调度课程设计》由会员分享，可在线阅读，更多相关《多进程调度课程设计（30页珍藏版）》请在装配图网上搜索。

1、综合设计报告设计名称： 操作系统综合设计 设计题目： 模拟进程调度功能的设计与实现 学生学号： 专业班级： 学生姓名： 学生成绩： 指导教师（职称）： 课题工作时间： 2011年6月6日 至 2011年6月29日四、综合设计（课程设计）摘要（中文）：进程调度方式分为非剥夺方式和剥夺方式，调度算法又有先进先出、短时间调度、优先级调度、高响应比调度、时间片调度、多级反馈调度。进程调度模块通过PCB变化来掌握系统中存在的所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系

2、统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。每个进程三种状态：运行态，等待态，就绪态。通过对进程的合理调度，使得系统能够安全有序的良好运转。关键字： 进程调度；处理机；PCB；进程状态五、综合设计（课程设计）Abstract（英文）：AbstractDivided into the process scheduling way and deprivation, deprived scheduling algorithm and a fifo, short time scheduling, priority sched

3、uling, high response than scheduling, time piece of scheduling, multilevel feedback scheduling. Process scheduling module through the PCB change to master the existing in the system of the implementation of all process and characteristic, and the state at the right time ready queue from a selection

4、of a process occupy processor.Whether in batch system or a time-sharing system, user process several generally more than processor number, this will lead to them for each other processor. In addition, the system process using the processor is also required. This requires process scheduler according

5、to certain strategy, dynamically assigned to the processor in ready queue in a process to execution. Each process three states: operation state, waiting for the state, the state is ready. Through the process of the reasonable dispatch, the system can be safely and orderly good operation. Key words:

6、process scheduling ; processor ; PCB ; process state目录摘 要IIABSTRACTII第一章 课题背景11.1 设计背景11.2设计任务11.3设计目的11.4设计要求1第二章 设计简介及设计方案论述22.1设计理论依据2第三章 详细设计63.1数据结构63.2程序功能划分63.3主要介绍63.3.1程序主框架63.3.2程序结点数据结构73.3.3主要程序框图7第四章 设计结果及分析84.1设计结果显示84.1.1进程的创建84.1.2进程正在执行84.1.3执行时间完，调度另一进程94.1.4撤销进程94.1.5进程阻塞104.1.6.唤

7、醒进程104.2程序结果分析11总结12致谢13参考文献14附录重要代码.15摘 要无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。每个进程三种状态：运行态，等待态，就绪态。通过对进程的合理调度，使得系统能够安全有序的良好运转。进程调度方式分为非剥夺方式和剥夺方式，调度算法又有先进先出、短时间调度、优先级调度、高响应比调度、时间片调度、多级反馈调度。进程调度模块通过PCB变化来掌握系统中存在的所有进程的执行情况和状态特征，

8、并在适当的时机从就绪队列中选择出一个进程占据处理机。关键字： 进程调度；处理机；PCB；进程状态AbstractWhether in batch system or a time-sharing system, user process several generally more than processor number, this will lead to them for each other processor. In addition, the system process using the processor is also required. This requires pr

9、ocess scheduler according to certain strategy, dynamically assigned to the processor in ready queue in a process to execution. Each process three states: operation state, waiting for the state, the state is ready. Through the process of the reasonable dispatch, the system can be safely and orderly g

10、ood operation. Divided into the process scheduling way and deprivation, deprived scheduling algorithm and a fifo, short time scheduling, priority scheduling, high response than scheduling, time piece of scheduling, multilevel feedback scheduling. Process scheduling module through the PCB change to m

11、aster the existing in the system of the implementation of all process and characteristic, and the state at the right time ready queue from a selection of a process occupy processor.Key words: process scheduling ; processor ; PCB ; process state- 25 -第一章 课题背景1.1 设计背景21世纪是高科技和高效率的时代，经济的飞速发展也展示了飞速增长的压力

12、，也对工作效率提出了进一步的要求，而计算机高效率的自动化能力在这一方面展示了巨大的前景。所以，利用计算机编程技术安排合适而正确的工作流程来实现事物处理的自动化，成为本报告解释和描述所编辑工程的重点，利用此次的模拟来提高对流程的控制能力。1.2设计任务 确定开发的项目名称，并熟悉相关知识，确定开发工具并实现开发环境的安装配置 实现用户界面的开发 实现进程调度子系统如下功能模块：1.3设计目的在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个，也就是说能运行的进程大于处理机的个数。为了使系统中的进程能有条不紊的工作，必须选用某种调度策略，选择一进城占用处理剂。要求学生设计一个模拟处

13、理剂调度算法，以巩固和加深处理机调度的概念。1.4设计要求 进程调度算法包括：时间片轮换算法，动态优先级算法，短作业算法等。 可选择进程的数量。 本程序包括一种算法，即进程的多级反馈队列调度算法。 实验每人一组，每人交一份设计报告。第二章 设计简介及设计方案论述2.1设计理论依据1.进程控制块的内容如右图所示： 图21 其中进程优先数是赋给进城的优先级，都是总是选取优先级高的进程优先运行。2每个进程的优先数，运行时间由程序任意给定。3为了调度方便，把进程按给定优先级从小到大排成一个队列，按给定的运行时间从小到大排成一个队里啊用一个指针变量作为首指针，指向队列的第一个进程。4.处理机调度总是选队

14、首进程运行，由于本实验是模拟调度，所以选中的进程并不是启动运行，而是执行。5.进程概念：进程是被独立分配资源的最小单位。进程是动态概念，必须程序运行才有进程的产生。6. 进程的状态模型： 运行：进程已获得处理机，当前处于运行状态。 就绪：进程已经准备好，一旦有处理器就可运行。7.处理机调度：在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。8.进程调度算法的功能 记录系统中所有进程的执行情况 选择占有处理机的进程 进行进程的上下文切换9.进程调度的算法：（1）先来先服

15、务算法如图22图22 先来先服务算法流程图（2）优先数算法：即进程的执行顺序由高优先级到低优先级。系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。该算法核心是确定进程的优先级。（3）时间片轮转算法：固定时间片，每个进程在执行一个时间片后，轮到下一进程执行，知道所有的进程执行完毕。处理器同一个时间只能处理一个任务。处理器在处理多任务的时候，就要看请求的时间顺序，如果时间一致，就要进行预测。挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参与，有些不需要（如磁盘控制器的存储过程）。不需要处理器处理的时候，这部分时间就要分配给其他的进程。原来的进程就要处于等待

16、的时间段上。经过周密分配时间，宏观上就象是多个任务一起运行一样，但微观上是有先后的，就是时间片轮换。其算法流程如图23： 图23 时间片轮换算法流程图 (4)多级反馈轮转法 允许进程在队列之间移动。在系统中设置多个就绪队列，每个队列对应一个优先级，第一个队列的优先级最高，第二队列次之。以下各队列的优先级逐步低。 各就绪队列中的进程的运行时间片不同，高优先级队列的时间片小，低优先级队列的时间片大。进程并非总是固定在某一队列中，新进程进入系统后，被存放在第一个队列的末尾。如果某个进程在规定的时间片内没有完成工作，则把它转入到下一个队列的末尾，直至进入最后一个队列。 系统先运行第一个队列中的进程。当

17、第一队列为空时，才运行第二个队列中的进程。依此类推，仅当前面所有的队列都为空时，才运行最后一个队列中的进程。当处理器正在第i个队列中为某个进程服务时，又有新进程进入优先级最高的队列（第1（i-1）中的任何一个对列），则此新进程要抢占正在运行进程的处理器，即由调度程序把正在运行的进程放回第i队列的末尾，把处理器分配给新到的高优先级进程。除最低优先权队列外的所有其他队列，均采用相同的进程调度算法，即按时间片轮转的FIFO（先进先出）算法。 最后一个队列中的进程按按时间片轮转或FCFS策略进行调度。它是综合了FIFO、RR和剥夺式HPF的一种进程调度算法。主要设计流程如下：图24 图24 多级反馈轮

18、转算法的流程图第三章 详细设计3.1数据结构进程控制块PCB：名称字段为char型的数组，所需时间为整型，优先级为整型，并且值小的优先级高；设置一个整型变量表示CPU的时间片。3.2程序功能划分 创建进程：根据编辑框中的信息创建新进程，并将其插入就绪队列；若当前无 进程运行或新进程的优先级高于正在运行的进程，则重新调度，完成后显示更新； 撤消进程：撤消正在运行的进程，重新调度，完成后显示更新； 阻塞进程：将正在运行的进程控制块PCB插入阻塞队列，重新调度，完成后显示更新； 唤醒进程：唤醒阻塞队列队首的进程，将其插入到与其优先级相对应的就绪队列，重新调度，完成后显示更新； 执行进程：将正在运行进

19、程的所剩时间减1，同时将CPU时间片减1。判断执行结果，若时间片未用完，进程也未结束，更新显示正在运行的进程；若时间片未用完，进程结束，则重新调度，并显示更新；若时间片用完，进程结束，则重新调度，并显示更新；若时间片用完，进程未结束，则将进程插入到下一级就绪队列，重新调度，并显示更新。 进程调度：判断当前是否有进程在运行，若有则将正在运行的进程插入到相应的就绪队列，然后由优先级高到低的顺依次探寻各就绪队列，给第一个不为空的就绪队列队首进程分配处理机，再根据队列的优先级为之分配时间片； 先来先服务是根据进程到达的先后次序来决定的，而短作业优先则是根据作业运行所需要的cpu时间的长短来确定的3.3

20、主要介绍3.3.1程序主框架进入主程序唤醒进程阻塞进程撤销进程创建进程 3.3.2程序结点数据结构图313.3.3主要程序框图图32第四章 设计结果及分析4.1设计结果显示4.1.1.进程的创建图41 进程创建4.1.2.进程正在执行图42 进程执行4.1.3.执行时间完，调度另一进程图43进程调度4.1.4撤销进程图44 进程撤销4.1.5进程阻塞图45进程阻塞4.1.6.唤醒进程图46进程唤醒4.1.7短作业优先图47短作业优先4.2程序结果分析： 创建完进程之后，各个进程进入到就绪队列中按enter健执行进程调度，每按 一次，时间计数器的值加1，直到进程被阻塞或者是所分配的时间片用完，开

21、始调度下一个进程。 撤销进程之后，正在运行的进程停止执行，继续执行就绪队列中下一个进程。 对于就绪队列中排在队首的进程优先执行。 进程阻塞之后，该进程排到优先级更低的就绪队列的末尾，然后开始调度下一个进程，时间片也翻了倍。 然后唤醒该进程，把进程调到就绪队列中准备执行。 多级反馈队列调度算法是综合了先来先服务算法，时间片轮换算法的一种调度 算法，有更好的实时性 整个程序包含三种算法，先来先服务算法，短作业优先算法，还有就是多级反馈队列调度算法，可以根据所给的菜单来选择不同的进程调度算法，先来先服务算法是根据进程被创建的时间来决定进程调度顺序的；短作业算法是根据所给的作业运行时间来确定调度顺序的

22、；多级调度算法是这几种算法的综合。总结通过为期两个星期的操作系统课程设计，我对课程设计有了更深的了解，没做课程设计以前，一直对课程设计的概念很模糊，就以为课程设计只是单纯的对本学期所学知识的一个总结，后来上了课程设计才知道，课程设计并不只是简单的总结，更多的是对书本知识一个更深层次的理解。回忆此次课程设计，至今仍然感慨很多。刚开始接到通知说要做课程设计的时候，因为我们的专业课考试很多，加上自己所学的编程语言知识很有限，所以很担心自己不能如期的做好设计。后来，觉得这种担心是多余的，与其担心，不如好好的做，多学点知识。整个过程，从理论到实践，整整两个星期的日子里面，可以说是苦多于甜，有的时候做出个

23、函数会遇到很多错误，到后来都没信心了，但在老师和同学的帮助下，也一直坚持不懈的做下来了，学到了很多东西，不仅仅是专业知识，所以说这一切都是值得的，除了书本上面的知识得到了巩固，我还了解了更多的关于计算机方面的知识，不仅仅限于操作系统，比如说MFC、Java等，这些编程语言以及它的使用以前从来都没有尝试过，但在课程设计课堂上面，刘老师带着我们一起认识了一下Java，让我们这些从没有接触过Java的同学也开始了解到Java是什么，虽然说知道的很少，但这至少是一个开始，希望自己以后能利用空余时间学好Java。这次课程设计原来打算用MFC写出来的，但在编写过程中遇到了很多困难，最后在同学的帮助下，用M

24、FC写出来了一个很小的程序，自己在课下也试图想完全靠自己做出一个完整的界面，但最后都因为自己所积累的知识有限，没有做成功。这次课程设计使用C+写的，也花了一定时间，做出来的程序是参考老师所给的例子一点一点看懂了，然后在自己慢点摸索的，同时也上网搜集了很多资料，关于MFC以及Java，虽然题目不难，但通过这次课程设计，我对面向对象的编程语言有了一个更深的了解。在设计过程中也遇到了不少的问题：1. 调度时机决策；2. 多级反馈队列兼容；3. 设备的分配和释放；4. 进程的抢占 对应的解决办法是：1. 设置进程的相应状态；2. 采用单一就绪队列，各进程转入就绪队列进行插入到相应的位置3. 每执行一次

25、，判断就绪队列首端元素是否有更高的优先级通过这次课程设计，我深刻的认识到理论联系实际的重要性，只有在把书本知识学得扎实的基础上，课后要勤动手，才能算是收获。无论是哪门课程，特别是计算机相关课程，动手能力是很重要的，所以课后一定要多加练习，学会多用所学的知识。课后要做的更多的是多看一些课外书籍，学一些语言，不能仅仅靠课堂上面讲的内容。所以以后一定会多加动手练习，紧紧的结合所学知识，争取把各方面都发展平衡。致谢 在短短两个星期的时间里，完成了课程设计的任务，除了自身的努力之外，更离不开老师和同学们的帮助，老师们细心的指导，在我有困难时同学们不厌其烦的解答，我的课程设计完成的才会顺利。由此，衷心的感

26、谢大家！参考文献1 梁小丹，梁红兵，哲风屏，汤子瀛.计算机操作系统第三版.西安电子科技大学出版社.2007年2 张尧学计算机操作系统教程第2版 习题与实验指导.2000年3 侯俊杰深入浅出MFC第二版M华中科技大学出版社2001年 4 李晓玲，张俊，姬涛等，程序设计基础M.中国铁道出版社，2008，371页5 张俊，张彦铎，C+面向对象程序设计M,中国铁道出版社，2008，379页6 周爱武，汪海威，李知兵等，计算机操作系统教程M, 清华大学出版社，2011，280页7 张尧学，史美玲，张高等，计算机操作系统教程M, 清华大学出版社，2006,302页8 张尧学，计算机操作系统教程第2版M，清

27、华大学出版社，习题与实验指导.2000年，129页附录重要代码#include#include#include#include#include /#include #define MAX 10 using namespace std;#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /class Process/public: / 进程名字 /int Time; / 进程需要时间 /int leval; / 进程优先级 /; typedef

28、struct nodechar name5;/进程名字 char ProcessName5;/int prio;/进程优先级int timeType;/分配的时间片int time;/cpu执行时间/int need;/进程执行所需要的时间/char state;/进程的状态struct node *next;/链表指针 int LeftTime;/ 进程运行一段时间后还需要的时间*PCB;int count=0;/时间计数变量 typedef struct Queue/PCB *Rlink;/就绪队列中的进程对劣指针/int prio;/本就绪队列中的优先级/int time;/本就绪队列中

29、分配的时间片PCB front;/队头指针PCB rear;/队尾指针LinkQueue;LinkQueue qRun,qWait,qReady1,qReady2,qReady3,qReady4; /对各函数的声明 int InitQueue(LinkQueue &Q); int creatPro(LinkQueue &quePro); void dealTime(); void runPro(void);void ShortTime(); void run(); void wait(); void wake(); void endPro();int InitQueue(LinkQueue &

30、Q) /构造一个空队列 if(!(Q.front=Q.rear=(PCB)malloc(sizeof(node) exit(OVERFLOW); /存储分配失败 Q.front-next=NULL; return OK; int EnQueue(LinkQueue &Q,char e5,int proTime,int tType) / 插入元素e为Q的新的队尾元素 PCB p; if(!(p=(PCB)malloc(sizeof(PCB) / 存储分配失败 exit(OVERFLOW); strcpy(p-name,e); p-time=proTime; p-timeType=tType; p

31、-next=NULL; Q.rear-next=p; Q.rear=p; return OK; int DeQueue(LinkQueue &Q,char e5) / 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR PCB p; if(Q.front=Q.rear) return ERROR; p=Q.front-next; strcpy(e,p-name); Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK; int QueueTraverse(LinkQueue &Q,int

32、 x,int y) PCB p; p=Q.front-next; while(p) printf(%st,p-name); printf(%d,p-time); coutnext; printf(n); return OK; void print() if(qRun.front!=qRun.rear) QueueTraverse(qRun,17,5); if(qWait.front!=qWait.rear) QueueTraverse(qWait,17,8); if(qReady1.front!=qReady1.rear) QueueTraverse(qReady1,17,11); if(qR

33、eady2.front!=qReady2.rear) QueueTraverse(qReady2,17,14); if(qReady3.front!=qReady3.rear) QueueTraverse(qReady3,17,17); if(qReady4.front!=qReady4.rear) QueueTraverse(qReady4,17,20); int creatPro(LinkQueue &quePro) char proName5; int proTime; PCB p; cout进程名: proName; cout所需时间: proTime; if(proTime=0) c

34、outname,proName); p-time=proTime; p-timeType=10; /进入时间片为10的就绪队列,即优先级最高的就绪队列 p-next=NULL; quePro.rear-next=p; quePro.rear=p; return OK; void dealTime() char e5; int tType=qRun.front-next-timeType; +count; qRun.front-next-time-; if(qRun.front-next-time=0) DeQueue(qRun,e); runPro(); count=0; else if(qR

35、un.front-next-timeType=count) if(qRun.front-next-timeType=10) EnQueue(qReady2,qRun.front-next-name,qRun.front-next-time,tType+10); if(qRun.front-next-timeType=20) EnQueue(qReady3,qRun.front-next-name,qRun.front-next-time,tType+20); if(qRun.front-next-timeType=40) EnQueue(qReady4,qRun.front-next-name

36、,qRun.front-next-time,80); if(qRun.front-next-timeType=80) EnQueue(qReady4,qRun.front-next-name,qRun.front-next-time,80); DeQueue(qRun,e); runPro(); count=0; void runPro(void) char e5; int pTime,f1=0,f2=0,f3=0,f4=0; if(qReady1.front!=qReady1.rear) pTime=qReady1.front-next-time; EnQueue(qRun,qReady1.

37、front-next-name,pTime,qReady1.front-next-timeType); DeQueue(qReady1,e); f1=1; else if(qReady2.front!=qReady2.rear) pTime=qReady2.front-next-time; EnQueue(qRun,qReady2.front-next-name,pTime,qReady2.front-next-timeType); DeQueue(qReady2,e); f2=1; else if(qReady3.front!=qReady3.rear) pTime=qReady3.fron

38、t-next-time; EnQueue(qRun,qReady3.front-next-name,pTime,qReady3.front-next-timeType); DeQueue(qReady3,e); f3=1; else if(qReady4.front!=qReady4.rear) pTime=qReady4.front-next-time; EnQueue(qRun,qReady4.front-next-name,pTime,qReady4.front-next-timeType); DeQueue(qReady4,e); f4=1; if(f1=0 & f2=0 & f3=0

39、 & f4=0) cout信息提示:无就绪进程,请输入其他功能选项!endl; void run() if(qRun.front=qRun.rear) runPro(); else dealTime(); void endPro() char e5; if(qRun.front=qRun.rear) cout信息提示:无运行进程,请按Enter键运行进程!endl; else DeQueue(qRun,e); cout信息提示:选择菜单功能或按Enter键执行进程!next-name,qRun.front-next-time,qRun.front-next-timeType); DeQueue

40、(qRun,e); print(); cout信息提示: 选择菜单功能或按Enter键执行进程!endl; else cout信息提示:无运行进程,请输入其他功能选项!next-name,qWait.front-next-time,qWait.front-next-timeType); DeQueue(qWait,e); print(); cout信息提示: 选择菜单功能或按Enter键执行进程!endl; else cout信息提示:无等待进程,请输入其他功能选项!next-time; EnQueue(qRun,qReady1.front-next-name,pTime,qReady1.fr

41、ont-next-timeType); DeQueue(qReady1,e); void dealTime2() char e5; qRun.front-next-time-; if(qRun.front-next-time=0) DeQueue(qRun,e); void dealTime3() char e5; int tType=qRun.front-next-timeType; +count; qRun.front-next-time-; if(qRun.front-next-time=0) DeQueue(qRun,e); runPro(); count=0; else if(qRu

42、n.front-next-timeType=count) EnQueue(qReady1,qRun.front-next-name,qRun.front-next-time,tType); DeQueue(qRun,e); runPro(); count=0; char processMAX=; /进程标识 int arrivetimeMAX;/达到时间 int servicetimeMAX;/服务时间 int finishtimeMAX; /完成时间 int init(); void FCFS(); int init() cout 输入进程队列标识(用单个字母表示一个进程,字母间用tab间隔

43、) endl; int i=0; while(iMAX) cin.get(processi); if(processi= | processi=t) continue; if(processi=q | processi=n) processi=0; break; i+; int len=strlen(process); cout 依次输入进程到达时间(时间之间用tab间隔) endl; for(int ix=0; ix arrivetimeix; cout 依次输入服务时间(时间之间用tab间隔) endl; for(ix=0; ix servicetimeix; return len; vo

44、id FCFS(int len) /完成时间的计算 for(int ix=0; ixlen; ix+) finishtimeix=accumulate(servicetime,servicetime+ix+1,0); len=strlen(process); /显示进程序列 for( ix=0; ixlen; ix+) cout processix t; cout endl; /显示到达时间序列 int* arr; for( ix=0; ixlen; ix+) cout arrix t; cout endl; void ShortTime()if(qRun.front=qRun.rear) r

45、unPro2(); else dealTime3();void main() char a=NULL; int len = init(); system(color 0B); InitQueue(qRun); InitQueue(qWait); InitQueue(qReady1); InitQueue(qReady2); InitQueue(qReady3); InitQueue(qReady4); cout*菜单选项*endl;cout*1 创建进程（默认多级反馈）*endl;cout*2 先来先服务*endl;cout*3 短作业优先*endl;cout*4 撤销进程*endl;cout*5 阻塞进程*endl; cout*6 唤醒进程*endl;cout请输入您的选择a; while(1) switch(a) case 1:creatPro(qReady1); print(); while(1) f: cout信息提示: 选择菜单功能或按Enter键执行进程!endl; a=getchar(); if(a=n) run(); print();