2022年2022年进程调度算法[收 .pdf

1 课程设计说明书设计名称：进程调度算法设计题目：进程调度算法设计学生姓名：专业：计算机应用技术班级： 09 计算机专科学号： 309104 指导教师：日期： 2011 年 5 月 5 日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 18 页 - - - - - - - - - 2 课程设计任务书计算机应用技术专业 09 年级专科班一、设计题目进程调度算法的设计二、主要内容1、设计进程控制块PCB表结构，分别适用于优先数调度算法和循环轮转调度算法。2、建立进程就绪队列。对两种不同算法编制入链子程序。3、编制两种进程调度算法：1）优先数调度； 2）循环轮转调度开发环境： VC+ 语言的编程环境三、具体要求1、本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。2、为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。3、 在 优 先 数 算 法 中 ， 优 先 数 的 值 为50 与 运 行 时 间 的 差 值 ， 即P_TIME-process-needtime 。进程每执行一次， 优先数减 3，CPU时间片数加 1， 进程还需要的时间片数减1。 在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2 个单位） ，这时，CPU 时间片数加 2，进程还需要的时间片数减2，并排列到就绪队列的尾上。4、对于遇到优先数一致的情况，采用FIFO策略解决。开发环境： VC+ 语言的编程环境四、进度安排1、资料查找、系统分析，数据流程分析，概要设计。2、系统详细设计、功能设计。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 - - - - - - - - - 3 3、算法实现、编程调试。4、资料整理、课程设计说明书编写。五、完成后应上交的材料1、课程设计说明书2、相关源程序文件六、总评成绩指导教师签名日期年月日系 主 任审核日期年月日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 18 页 - - - - - - - - - 4 目录一.设计目的 . 5二.设计内容 . 5三.设计原理 . 53.1 优先数调度算法 . 53.2 循环轮转调度算法 . 5四设计步骤 . 64.1 任务分析 . 64.2 概要设计 . 64.3 详细设计 . 64.4 流程图 .74.5 源程序.7 4.6 程序测试数据及结果 . .134.6.1 程序测试数据 . 13 4.6.2 运用优先数调度算法的执行结果（如下图）. 13 4.6.3 运用循环轮转调度算法的执行结果（如下图）. 14 五.设计总结 . 18 六.参考文献 . 18 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - - - - - - 5 一.设计目的通过这次课程设计， 加深理解有关进程控制块、 进程队列的概念， 并体会和了解优先数和循环轮转调度算法的具体实施办法。培养程序设计的方法和技巧，提高编制清晰、 合理、可读性好的系统程序的能力，同时加深对操作系统课程的理解。二.设计内容1用语言来实现对 n 个进程采用不同调度算法的进程调度。2每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：（1）进程优先数 ID，其中 0 为闲逛进程，用户进程的标识数为1，2，3。（2）进程优先级 Priority，闲逛进程（ idle ）的优先级为 0，用户进程的优先级大于 0，且随机产生，优先数越大，优先级越高。（3）进程占用的 CPU 时间 CPUtime ，进程每运行一次，累计值等于4。（4）进程总共需要运行时间Alltime ，利用随机函数产生。（5）进程状态， 0：就绪态； 1：运行态； 2：阻塞态。（6）队列指针 next ，用来将多个进程控制块PCB 链接为队列。3优先数改变的原则（1）进程在就绪队列中每呆一个时间片，优先数增加1。（2）进程每运行一个时间片，优先数减3。4在调度前，系统中拥有的进程数PCB_number 由键盘输入，经初始化后，所有的进程控制块PCB链接成就绪队列。三.设计原理3.1 优先数调度算法对每个进程确定一个优先数，该算法总是让优先数最高的进程先使用处理器。对具有相同优先数的进程， 再来采用先来先服务的次序分配处理器。系统常与任务的紧迫性和系统效率等因素确定进程的优先数。进程的优先数可以固定的，也可随进程执行过程动态变化。一个高优先数进程占用处理器后，系统处理该进程时有两种算法，一是“非抢占式” ，另一种是“可抢占式”。前者是次进程占用处理器后一直运行到结束， 除非本身主动让出处理器； 后者则是严格保证在任何时刻总是让优先数最高的进程在处理器上运行。3.2 循环轮转调度算法循环轮转调度算法的具体原理是：每个进程被分配一个时间片， 即该进程允许运行的时间。就绪的进程都存放在一个就绪链表中， 队首的进程将获得时间片。如果在时间片结束时进程还在运行，则 CPU 将剥夺并分配给下一个进程。 调度程名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 18 页 - - - - - - - - - 6 序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后， 它被移到队列的末尾。四设计步骤4.1 任务分析(1)PCB 结构通常包括以下信息：进程名，进程优先数，轮转时间片，进程已占用的 CPU 时间，进程还需要的 CPU 时间，进程的状态，当前队列指针等。可根据实验的不同， PCB 结构的内容可以作适当的增删(2) 本程序用两种算法对五个进程进行调度，每个进程可有三个状态： 就绪、执行、完成。并假设初始状态为就绪状态。(3) 为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。(4) 在优先数算法中，优先数可以先取值为一个常数减去进程所需要的时间片数目，进程每执行一次，优先数减3，CPU时间片数加 1，进程还需要的时间片数减 1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2 个单位） ，这时，CPU 时间片数加 2，进程还需要的时间片数减 2，并排列到就绪队列的尾上。(5) 对于遇到优先数一致的情况，采用FIFO策略解决。4.2 概要设计1. 本程序用两种算法对五个进程进行调度，每个进程可有三个状态， 并假设初始状态为就绪状态。2. 为了便于处理， 程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。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（） 显示结果信息函数3.int process_finish(pcb *q) 进程完成标示4.void display_round（） 显示循环轮转调度算法运行结果5.priority_cal() 优先数调度算法6.void cpu_round（）处理器的工作状态名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 18 页 - - - - - - - - - 7 4.4 流程图4.5 源程序源程序如下：#include #include 开始生成并按生成次序排列进程控制块链链首进程投入运行时间片到， 进程时间片减 1，优先级减3 撤销该进程运行进程退出，取链首进程投入运行时间片为0？优先级大于队列中优先级最高的进程？进程队列为空？结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 18 页 - - - - - - - - - 8 #include #include #include #include #define P_NUM 5 #define P_TIME 50 enum state ready, execute, block, finish ; struct pcb char name4; 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; elset-next=q;t=q; i+; /while return p; void display(pcb *p) coutname cputime needtime priority stateendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 18 页 - - - - - - - - - 9 while(p) coutname; cout ; coutcputime; cout ; coutneedtime; cout ; coutpriority; coutprocess) case ready:coutreadyendl;break; case execute:coutexecuteendl;break; case block:coutblockendl;break; case finish:coutfinishnext; 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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 18 页 - - - - - - - - - 10 t-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); 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 18 页 - - - - - - - - - 11 if (i=0) p=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; do t=t-next; while (t & t-process=finish); if(t=NULL) t=head; while (t-next!=k & t-process=finish) t=t-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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 18 页 - - - - - - - - - 12 void display_round(pcb *p) coutNAME CPUTIME NEEDTIME COUNT ROUND STATEendl; while(p) coutname; cout ; coutcputime; cout ; coutneedtime; cout ; coutcount; cout ; coutround; coutprocess) 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); /Sleep(100); getch(); system(cls); void main() display_menu(); int k; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 18 页 - - - - - - - - - 13 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 运用优先数调度算法的执行结果（如下图）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 18 页 - - - - - - - - - 14 一直按回车键，直到第27 次，运行结束。4.6.3 运用循环轮转调度算法的执行结果（如下图）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 18 页 - - - - - - - - - 15 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 18 页 - - - - - - - - - 16 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 18 页 - - - - - - - - - 17 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 18 页 - - - - - - - - - 18 五.设计总结经过这次课程设计， 把课本中的理论知识转化为实践，在一定程度上 加深了对优先级数调度和循环调度算法的理解，同时提高了我的动手编程能力。 虽然在编程的过程中， 遇到了很多的困难， 但是经过我的努力， 通过查参考书或者到网上搜索等途径， 我所遇到的困难都被我一一的解决了。过程虽然很难， 但是通过这次课程设计，结果还是让我受益匪浅。我始终相信：在前进的途中，所遇到的绊脚石，通过我的努力，它最终都会变成我脚下的垫脚石！六.参考文献1. 操作系统教程，第三版，孙钟秀主编，高等教育出版社。2. 计算机操作系统，汤子瀛主编，西安电子科技大学出版社3. 计算机操作系统，刘腾红主编，清华大学出版社4. 操作系统实验与课程设计 ，庞丽萍主编，华中科技大学出版社。5. 操作系统实验教程，袁宝华主编，北京交通大学出版社6.Visual C+ 6.0 程序设计与开发技术大全 ，求是科技主编，人民邮电出版社名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 18 页 - - - - - - - - -