进程调度算法

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

1、课程设计说明书设计名称：进程调度算法设计题 目：进程调度算法设计学生姓名：专业：计算机应用技术班 级：09计算机专科学号：309104指导教师：日 期：2011年旦月旦日课程设计任务书计算机应用技术专业 09 年级 专科 班一、设计题目进程调度算法的设计二、主要内容1、设计进程控制块PCB表结构，分别适用于优先数调度算法和循环轮转调 度算法。2、建立进程就绪队列。对两种不同算法编制入链子程序。3、编制两种进程调度算法：1）优先数调度；2）循环轮转调度开发环境：VC + +语言的编程环境三、具体要求1、本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假 设初始状态为就绪状态。2、为了

2、便于处理，程序中的某进程运行时间以时间片为单位计算。各进程 的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给 定。3、在优先数算法中， 优先数的值为 50 与运行时间的差值， 即 P_TIME-process-needtime。进程每执行一次，优先数减3，CPU时 间片数加 1，进程还需要的时间片数减 1。在轮转算法中，采用固定时 间片（即：每执行一次进程，该进程的执行时间片数为已执行了 2 个单 位），这时， CPU 时间片数加2，进程还需要的时间片数减2，并排列到 就绪队列的尾上。4、对于遇到优先数一致的情况，采用 FIFO 策略解决。开发环境：VC+语言的编程环境四、 进度

3、安排1、资料查找、系统分析，数据流程分析，概要设计。2、系统详细设计、功能设计。3、算法实现、编程调试。4、资料整理、课程设计说明书编写五、 完成后应上交的材料1、课程设计说明书2、相关源程序文件六、 总评成绩指导教师签名日期年月日系主任审核日期年月日目录一.设计目的5二.设计内容5三.设计原理53.1 优先数调度算法53.2 循环轮转调度算法5四设计步骤64.1 任务分析 64.2 概要设计64.3 详细设计64.4 流程图.74.5 源程序.74.6 程序测试数据及结果.134.6.1程序测试数据134.6.2 运用优先数调度算法的执行结果（如下图）134.6.3 运用循环轮转调度算法的执

4、行结果（如下图）14五.设计总结21六.参考文献21一. 设计目的通过这次课程设计，加深理解有关进程控制块、进程队列的概念，并体会和 了解优先数和循环轮转调度算法的具体实施办法。培养程序设计的方法和技巧， 提高编制清晰、合理、可读性好的系统程序的能力，同时加深对操作系统课程的 理解。二. 设计内容1. 用语言来实现对n个进程采用不同调度算法的进程调度。2. 每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：(1) 进程优先数ID,其中0为闲逛进程，用户进程的标识数为1，2, 3。(2) 进程优先级Priority，闲逛进程(idle)的优先级为0，用户进程的 优先级大于 0，且随机

5、产生，优先数越大，优先级越高。(3) 进程占用的CPU时间CPU time,进程每运行一次，累计值等于4。(4) 进程总共需要运行时间All time,利用随机函数产生。(5) 进程状态， 0：就绪态；1：运行态；2：阻塞态。(6) 队列指针next,用来将多个进程控制块PCB链接为队列。 3优先数改变的原则(1) 进程在就绪队列中每呆一个时间片，优先数增加 1。(2) 进程每运行一个时间片，优先数减 3。4在调度前，系统中拥有的进程数PCB_number由键盘输入，经初始化后， 所有的进程控制块PCB链接成就绪队列。三. 设计原理3.1 优先数调度算法对每个进程确定一个优先数，该算法总是让优

6、先数最高的进程先使用处理 器。对具有相同优先数的进程，再来采用先来先服务的次序分配处理器。系统常 与任务的紧迫性和系统效率等因素确定进程的优先数。进程的优先数可以固定 的，也可随进程执行过程动态变化。一个高优先数进程占用处理器后，系统处理 该进程时有两种算法，一是“非抢占式”，另一种是“可抢占式”。前者是次进程 占用处理器后一直运行到结束，除非本身主动让出处理器；后者则是严格保证在 任何时刻总是让优先数最高的进程在处理器上运行。3.2 循环轮转调度算法循环轮转调度算法的具体原理是：每个进程被分配一个时间片，即该进程允 许运行的时间。就绪的进程都存放在一个就绪链表中，队首的进程将获得时间片。 如

7、果在时间片结束时进程还在运行，则CPU将剥夺并分配给下一个进程。调度程 序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队 列的末尾。四设计步骤4.1 任务分析(1)PCB 结构通常包括以下信息：进程名，进程优先数，轮转时间片，进程 已占用的CPU时间，进程还需要的CPU时间，进程的状态，当前队列指针等。可 根据实验的不同， PCB 结构的内容可以作适当的增删(2) 本程序用两种算法对五个进程进行调度，每个进程可有三个状态：就绪、 执行、完成。并假设初始状态为就绪状态。(3) 为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程 的优先数或轮转时间数以及进程需运行

8、的时间片数的初始值均由用户给定。(4) 在优先数算法中，优先数可以先取值为一个常数减去进程所需要的时间 片数目，进程每执行一次，优先数减 3， CPU 时间片数加 1，进程还需要的时间 片数减 1。在轮转算法中，采用固定时间片(即：每执行一次进程，该进程的执 行时间片数为已执行了 2个单位)，这时，CPU时间片数加2,进程还需要的时间 片数减 2，并排列到就绪队列的尾上。(5) 对于遇到优先数一致的情况，采用 FIFO 策略解决。4.2 概要设计1. 本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设 初始状态为就绪状态。2. 为了便于处理，程序中的某进程运行时间以时间片为单位计

9、算。各进程的 优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。3. 在优先数算法中， 优先数的值为 50 与运行时间的差值， 即 P_TIME-process-needtime。进程每执行一次，优先数减3，CPU时间片数加1， 进程还需要的时间片数减1。在轮转算法中，采用固定时间片(即：每执行一次 进程，该进程的执行时间片数为已执行了 2个单位)，这时，CPU时间片数加2, 进程还需要的时间片数减2，并排列到就绪队列的尾上。4. 对于遇到优先数一致的情况，采用 FIFO 策略解决。4.3 详细设计1. struct pcb()定义 pcb 块2. Void display()

10、显示结果信息函数3.int process_finish(pcb *q) 进程完成标示4. void display_round() 显示循环轮转调度算法运行结果5. priority_cal() 优先数调度算法6. void cpu_round ()处理器的工作状态4.4 流程图4.5 源程序源程序如下： #include #include #include #include #include #include #define P_NUM 5 #define P_TIME 50enum stateready,execute,block,finish;struct pcbchar name4;

11、int priority;int cputime;int needtime;int count;int round;state process;pcb * next;pcb * get_process();pcb * get_process()pcb *q;pcb *t;pcb *p;int i=0;coutinput name and timeendl;while (iq-name;cinq-needtime;q-cputime=0; q-priority=P_TIME-q-needtime; q-process=ready;q-next=NULL;if (i=0) p=q; t=q;els

12、et-next=q;t=q; i+; /while return p;void display(pcb *p)prioritycoutname cputime needtime stateendl;while(p) coutname; cout ; coutcputime; cout ;coutneedtime; cout ;coutpriority;coutprocess)case ready:coutreadyendl;break;case execute:coutexecuteendl;break;case block:coutblockendl;break; case finish:c

13、outfinishnext;int process_finish(pcb *q)int bl=1; while(bl&q) bl=bl&q-needtime=0; q=q-next; return bl;void cpuexe(pcb *q)pcb *t=q;int tp=0;while(q)if (q-process!=finish)q-process=ready; if(q-needtime=0) q-process=finish; if(tppriority&q-process!=finish) tp=q-priority; t=q;q=q-next;if(t-needtime!=0)t

14、-priority-=3; t-needtime-; t-process=execute; t-cputime+;void priority_cal()pcb * p; system(cls); p=get_process();int cpu=0; system(cls);while(!process_finish(p)cpu+; coutcputime:cpuendl; cpuexe(p);display(p); /Sleep(100); getch(); system(cls);printf(All processes have finished,press any key to exit

15、); getch();void display_menu()coutCHOOSE THE ALGORITHM:endl;cout1 PRIORITYendl;cout2 ROUNDROBINendl;cout3 EXITendl;pcb * get_process_round()pcb *q;pcb *t;pcb *p;int i=0; coutinput name and timeendl; while (iq-name;cinq-needtime;q-cputime=0;q-round=0;q-count=0; q-process=ready; q-next=NULL;if (i=0)p=

16、q;t=q;else t-next=q; t=q;i+; /while return p;void cpu_round(pcb *q)q-cputime+=2; q-needtime-=2;if(q-needtimeneedtime=0;q-count+;q-round+; q-process=execute;pcb * get_next(pcb * k,pcb * head)pcb * t;t=k;dot=t-next;while (t & t-process=finish); if(t=NULL)t=head;while (t-next!=k & t-process=finish) t=t

17、-next; return t;void set_state(pcb *p) while(p)if (p-needtime=0) p-process=finish;if (p-process=execute) p-process=ready;p=p-next;void display_round(pcb *p)coutNAME CPUTIME NEEDTIME COUNT ROUND STATEendl;while(p)coutname;cout ; coutcputime;cout ;coutneedtime;cout ; coutcount;cout ; coutround;coutpro

18、cess)case ready:coutreadyendl;break;case execute:coutexecuteendl;break;case finish:coutfinishnext;void round_cal()pcb * p;pcb * r;system(cls);p=get_process_round();int cpu=0;system(cls);r=p;while(!process_finish(p)cpu+=2;cpu_round(r); r=get_next(r,p);coutcpu cpuendl; display_round(p); set_state(p);/

19、Sleep(100);getch(); system(cls);void main()display_menu();int k;scanf(%d,&k);switch(k)case 1:priority_cal();break;case 2:round_cal();break;case 3:break; display_menu(); scanf(%d,&k);4.6 程序测试数据及结果4.6.1 程序测试数据4.6.2 运用优先数调度算法的执行结果（如下图）一直按回车键，直到第 27次，运行结束。4.6.3 运用循环轮转调度算法的执行结果（如下图）17181920五.设计总结经过这次课程设计

20、，把课本中的理论知识转化为实践，在一定程度上加深了 对优先级数调度和循环调度算法的理解，同时提高了我的动手编程能力。虽然在 编程的过程中，遇到了很多的困难，但是经过我的努力，通过查参考书或者到网 上搜索等途径，我所遇到的困难都被我一一的解决了。过程虽然很难，但是通过 这次课程设计，结果还是让我受益匪浅。我始终相信：在前进的途中，所遇到的 绊脚石，通过我的努力，它最终都会变成我脚下的垫脚石！六.参考文献1.操作系统教程，第三版，孙钟秀主编，高等教育出版社。2. 计算机操作系统，汤子瀛主编，西安电子科技大学出版社3. 计算机操作系统，刘腾红主编，清华大学出版社4. 操作系统实验与课程设计，庞丽萍主编，华中科技大学出版社。5. 操作系统实验教程，袁宝华主编，北京交通大学出版社6.Visual C+ 6.0程序设计与开发技术大全，求是科技主编，人民邮电出版社22