优先级法、多级反馈轮转法_进程调度模拟设计.docx

学 号： 课 程 设 计题 目进程调度模拟设计优先级法、多级反馈轮转法学 院计算机学院专 业班 级姓 名指导教师吴利军2013年1月15日课程设计任务书学生姓名： 指导教师： 吴利军 工作单位： 计算机科学与技术学院 题 目: 进程调度模拟设计优先级法、多级反馈轮转法 初始条件：1预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1模拟进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2设计报告内容应说明： 需求分析； 功能设计（数据结构及模块说明）； 开发平台及源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日进程调度模拟设计优先级法、多级轮转反馈法1设计目的与功能1.1设计目的了解进程调度中的相关知识，能够使用其中的方法来进行进程调度模拟设计。本次课程设计的重点是多级轮转反馈法和优先级法的使用，要求熟练掌握并运用他们，并能够运用一种高级语言来完成这个程序。1.2设计功能模拟进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2.需求分析，数据结构或模块说明(功能与框图)2.1需求分析无论是在批处理系统、分时系统还是实时系统，用户进程数一般都多于处理机数，这将导致用户进程互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按照一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。进程调度的主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。这次课程设计所要求使用的方法是时间片轮转和优先级法，并且能够选择不同的算法。而时间片轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例。时间片轮转法的基本概念是将cpu的处理时间分成固定大小的时间片。如果一个进程选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的cpu而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程或作业。优先级法是系统或用户按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权。优先级高的作业或进程优先调度。根据所需求，这个进程调度的实现过程如下图所示：开始选择调度方法时间片轮转优先级法输入进程信息显示进程调度队列列计算平均周转时间和平均带权周转时间并显示出来2.2数据结构和模块说明主要数据结构：struct pcb char namename_len; int priority; /优先级 intarrive_time; / 到达时间，即创建时间 int run_time;/ 需要的时间片数 int finish_time; / 完成时间 intsleep_time;/ 用于模拟进程的阻塞耗时 intswitch_time; / 切换队列的时间（srr专用） intused_run_time; / 已经用过的时间片数 short use_slices;/ 每次占用cpu将消耗的时间片数不同队列中的进程的值不一样（rrmf专用） struct pcb *next;程序中主要函数char get_command();/ 显示主菜单并接受用户令void add_process();/ 添加一个pcb结构进入预先准备队列void start_scheduling(); / 演示进程调度队列，srr版void start_scheduling_rrmf();/ rrmf版void calculate_time_costs();/ 计算并显示平均周转时间，平均带权周转时间void switch_algorithm();/ 切换调度算法（线性优先级法，多级反馈轮转法）void view_list(struct pcb *list);/查看队列中内容void help_menu();/ 显示帮助菜单void restart();/ 释放资源，重新开始void man_auto();/ 手动自动切换void append(struct pcb *head, struct pcb *node);/ 添加于所指队列的队尾void show_process(struct pcb *node);/ 显示一个pcb的内容void time_slice();/ 一个时间片void proc_run();/ 进程执行void proc_run_rrmf();/ rrmf版void proc_switch();/ 进程切换void proc_switch_rrmf();/ rrmf版void try_wakeup_procs();/ 遍历等待队列，减少sleep_time,唤醒sleep_time降至进程3.源程序的主要部分本次程序主要由三个部分组成：main函数部分，该部分主要包含main函数；lru算法部分，该部分主要包含lru函数、setm(int m,int n)函数和mini(int *b)函数；opt算法部分，该部分主要包含opt函数和getopt(int inpage)函数。3.1 main函数部分3.1.1main函数代码：int main(int argc, char *argv)char command;srand( (unsigned)time(null) );restart();while(command = get_command() != 0); 3.2 进程调度方法部分3.2.1.多级轮转反馈函数代码：/进程执行（rrmf算法）void proc_run_rrmf()short slices_out = 0;try_wakeup_procs();printf( );if(running = null) printf(没?有d进?程到?达?!n);return;printf(进程正在运行 :, running-name);running-used_run_time +;running-next = null;show_process(running);printf(n);if(running-used_run_time = running-run_time) running-finish_time = sys_clock;running-use_slices = (queue_num+1) - running-priority;append(&finished_list, &running);slices_out = 1;else if( (rand() % 100 + 1) sleep_time = (rand()%5+1);running-use_slices = (queue_num+1) - running-priority;append(&waiting_list, &running);slices_out = 1;else running-use_slices -;if(0 = running-use_slices) slices_out = 1;if(running-priority priority4)running-priority -;running-use_slices = (queue_num+1) - running-priority;append(&ready_listqueue_num-running-priority, &running);if(slices_out)running = null; 3.2.2.优先级法函数代码void proc_run()try_wakeup_procs();printf( );if(running = null) printf(没有进程抵达n);return;printf( 进程正在运行 :, running-name);running-used_run_time +; running-next = null;show_process(running);printf(n);if(running-used_run_time = running-run_time) running-finish_time = sys_clock;append(&finished_list, &running);else if( (rand() % 100 + 1) sleep_time = (rand()%5+1);append(&waiting_list, &running);else append(&serving_ready_list, &running);running = null;4.测试用例，运行结果与运行情况分析4.1测试用例运行界面 4.2运行结果用多级轮转反馈法进行进程调度的结果如下图所示：用优先级法进行进程调度所得到的结果如下图所示：5.自我评价与总结5.1本次课程设计做得比较好地方 本次课程设计条理清楚，能够运用两种不同的方法来进行进程调度。在进程调度函数的实现时运用的结构体来实现各个的功能。5.2什么地方做得不太好，以后如何改正 实验中一些不太好的部分就是本次实验虽然完成了老师所要求的任务，但是程序设计的界面还不是很优秀，用户体验不是很好。以后需要在这方面改进，一个好的程序不仅要有高效率，易读性，我认为还需要较好的用户体验，以后我要在这方面多加改进。5.3从本设计得到的收获通过这次课程设计，我对操作系统有了更进一层的理解，同时对以前学的c程序设计语言也有了更深的理解。在本次实验中我遇到了很多困难，本次实验中的程序编写花了很久。在这次课程设计中，我自己先熟悉各种知识，然后查找相关资料来实现一些所需要的功能，尤其是在那两个方法时所要运用到的一些知识。 我觉得在以后的学习过程中还应该多做这样的设计，它可以让我们把所学的理论用于实践，一方面可以检验并巩固我们所学的内容，另一方面可以让我们在实践中感到所学知识的实用性，从而提高我们的学习兴趣。6.参考文献1 张绕学，计算机操作系统教程，清华大学出版社，2005年6月2 周湘贞，操作系统原理与实践教程清华大学出版社，2006年10月3 严蔚敏，数据结构(c语言版)清华大学出版社，2004年11月4 闵联营，c+程序设计教程武汉理工大学出版社，2005年7月附：源代码common.h#ifndef _common_h_#define _common_h_#define name_len20#define inc_factor2/ 模拟时间片的延时#define delay_counter10000/ rrmf 所需常量#define queue_num4/就绪队列的条数#define priority14#define priority23#define priority32#define priority41#define use_slices11#define use_slices22#define use_slices33#define use_slices44/*全局数据结构和变量*/ 进程控制块 pcb 结构 struct pcb char namename_len; int priority; /优先级 intarrive_time; / 到达时间，即创建时间 int run_time;/ 需要的时间片数 int finish_time; / 完成时间 intsleep_time;/ 用于模拟进程的阻塞耗时 intswitch_time; / 切换队列的时间 （srr专用） intused_run_time; / 已经用过的时间片数 short use_slices;/ 每次占用cpu将消耗的时间片数，不同队列中的进程的值不一样 （rrmf专用） struct pcb *next;int sys_clock = 0;/ 模拟系统时钟int add_idx = 0;/ 第几轮添加进程int pre_list_size = 0;short algorithm = 0; / 调度算法标记, 0-srr 1-rrmf 默认为0char algo_name5 = ssr;short manual = 0; / 手动，自动标记，0-手动 1-自动 默认为0char oper_name10 = manual;int newly_factor = inc_factor;/ 新创建进程优先级增长速率int serving_factor = inc_factor / 2;/ 享受服务进程优先级增长速率struct pcb *pre_list;/ 预先准备的队列，用于模拟进程的不同时刻到达调度队列struct pcb *running;/ 指向正在运行进程struct pcb *serving_ready_list;/ 享受服务进程队列struct pcb *newly_ready_list;/ 新创建进程队列struct pcb *waiting_list;/ 等待队列struct pcb *finished_list = null;/ 完成队列/ rrmf 的多级队列/ ready_list0 优先级 priority1，占时间片 use_slices1/ ready_list1 优先级 priority2，占时间片 use_slices2/ ready_list2 优先级 priority3，占时间片 use_slices3/ ready_list3 优先级 priority4，占时间片 use_slices4/ .struct pcb *ready_listqueue_num;/*函数说明*/char get_command();/ 显示主菜单，并接受用户命令void add_process();/ 添加一个pcb结构进入pre_list(预先准备队列)void start_scheduling(); / 演示进程调度队列，srr版void start_scheduling_rrmf();/ rrmf版void calculate_time_costs();/ 计算并显示平均周转时间，平均带权周转时间void switch_algorithm();/ 切换调度算法（线性优先级法，多级反馈轮转法）void view_list(struct pcb *list);/ 查看队列中内容void help_menu();/ 显示帮助菜单void restart();/ 释放资源，重新开始void man_auto();/ 手动/自动 切换void append(struct pcb *head, struct pcb *node);/ 添加node于head所指队列的队尾void show_process(struct pcb *node);/ 显示一个pcb的内容void time_slice();/ 一个时间片void proc_run();/ 进程执行void proc_run_rrmf();/ rrmf版void proc_switch();/ 进程切换void proc_switch_rrmf();/ rrmf版void try_wakeup_procs();/ 遍历等待队列，减少sleep_time,唤醒sleep_time降至0的进程#endif /_common_h_main.c#include #include #include #include #include #include common.hint main(int argc, char *argv)char command;srand( (unsigned)time(null) );restart();while(command = get_command() != 0);/接收用户选择并转入相应的操作char get_command() char c;printf(n%d 个进程正在进行中, %s, %s,如果遇到问题，请按6查询n请选择将要进行的操作:n,pre_list_size,algo_name,oper_name);c = _getch();switch(c)case 1:add_process();break;case 2:switch_algorithm();break;case 3:if(algorithm = 0)start_scheduling();elsestart_scheduling_rrmf();break;case 4:calculate_time_costs();break;case 5:view_list(pre_list);break;case 6:help_menu();break;case 7:restart();break;case 8:man_auto();break;return c;/ 手动/自动 切换void man_auto() if(manual = 0) printf(切换为 自动模式n);strcpy(oper_name, automatic);manual = 1;else printf(切换为 手动模式n);strcpy(oper_name, manual);manual = 0;/显示帮助菜单void help_menu()printf(= process scheduler simulator =n1.添加进程n2.改变调度算法(目前算法为: %s)n3.开始调度n4.计算平均周转时间、平均带权周转时间n5.查看就绪进程列表n6.帮助 n7.重启n8.手动、自动切换(目前模式为: %s)n0.退出n,algo_name,oper_name);/ 添加node于head所指队列的队尾void append(struct pcb *head, struct pcb *node) struct pcb *p; /(*node)-next=null; if(*head=null) *head=*node; return; else p=*head;while(p-next!=null) p=p-next; p-next=*node; /添加进程void add_process()int counterpart, i;struct pcb *tmp;struct pcb *p = malloc( sizeof(struct pcb) );printf(请输入进程名称:);scanf(%s, p-name);if(algorithm = 0) / srr线性优先级调度p-priority = 0; /优先级为0，表明使用srrelse/ rrmf多级反馈轮转法p-priority = priority1;p-use_slices = use_slices1; / rrmf专用，表示占用的时间片p-arrive_time = 2 * add_idx + rand() % 1;p-used_run_time = 0;p-sleep_time = -1;p-finish_time = -1;p-next = null;printf(请输入需要的时间片数:);scanf(%d, &p-run_time); / 需要的时间片数append(&pre_list, &p); add_idx +; / 第几轮添加进程pre_list_size +;/ 是否随机增加几个同时刻的进程printf(请输入同时刻的进程数:);scanf(%d,&counterpart);if(counterpart0)for(i = 0; iname, %s_%d, p-name, i);tmp-priority = p-priority;tmp-arrive_time = p-arrive_time;tmp-run_time = p-run_time;tmp-used_run_time = 0;tmp-use_slices = p-use_slices; / rrmf专用tmp-sleep_time = -1;tmp-finish_time = -1;tmp-next = null;append(&pre_list, &tmp);pre_list_size += counterpart;elsecounterpart = 0;printf(成功增加 %d 个进程！n, 1+counterpart);/ 查看队列中内容void view_list(struct pcb *list)struct pcb *p;if(list = null)printf(n);else printf(n);p = list;while(p != null) printf( );show_process(p); /显示进程内容printf(n);p = p-next;/显示进程内容void show_process(struct pcb *node)printf(%-6s 优先级:%-3d 到达时间:%-3d 需要的时间片数:%-3d 已经用过的时间片数:%-3d 进程阻塞耗时:%-3d 完成时间:%-3d 每次占用cpu消耗的时间片数:%-3d 下一个:%-5s , node-name, node-priority, node-arrive_time,node-run_time, node-used_run_time, node-sleep_time, node-finish_time,node-use_slices,node-next=null?null:node-next-name);/ 切换调度算法（线性优先级法，多级反馈轮转法）void switch_algorithm()struct pcb *tmp;if(algorithm = 0) / 调度算法标记, 0-srr 1-rrmf 默认为0printf(切换至 多级反馈轮转算法n);strcpy(algo_name, rrmf);algorithm = 1;/ ssr 状态下添加的进程的priority默认为0，改为 priority1tmp = pre_list;while(tmp != null) tmp-priority = priority1;tmp = tmp-next;else printf(切换至 线性优先级算法n);strcpy(algo_name, ssr);algorithm = 0;/ 计算并显示平均周转时间，平均带权周转时间void calculate_time_costs()struct pcb *p;float sum = 0.0f, weighted_sum=0.0f;int num = 0; / 统计pcb个数if(finished_list = null)printf(完成队列为空!n);else p = finished_list; / 完成队列while(p != null) sum += (p-finish_time - p-arrive_time) * 1.0f;weighted_sum += (p-finish_time - p-arrive_time) * 1.0f / p-run_time;num +;p = p-next;printf(平均周转时间: %.3f线性优先级算法: %.3f, sum/num, weighted_sum/num);/时间片（模拟时间片的延时）void time_slice()int i,j;for(i=0; idelay_counter;i+)for(j=0; j 0 的进程其值减1last = p = waiting_list;while(p != null) if(p-sleep_time 0) p-sleep_time -;if(p-sleep_time = 0) if(p = waiting_list) waiting_list = waiting_list-next;move_to_ready = p;else /printf($in try_wakeup_procs 2 .n);last-next = p-next;move_to_ready = p;move_to_ready-next = null;if(algorithm = 0) / srrif(serving_ready_list = null)serving_ready_list = move_to_ready; / 享受服务进程队列elseappend(&serving_ready_list, &move_to_ready); else / rrmfif(move_to_ready-priority priority4) move_to_ready-priority -;move_to_ready-use_slices = (queue_num+1) - move_to_ready-priority; /就绪队列的条数if(ready_listqueue_num-move_to_ready-priority = null)ready_listqueue_num-move_to_ready-priority = move_to_ready;elseappend(&ready_listqueue_num-move_to_ready-priority, &move_to_ready);last = p;p = p-next;/进程切换（srr算法）void proc_switch()struct pcb *tail, *p;/ 若享受服务进程队列非空，执行其第1个进程/ 并检查新建进程第1个进程的优先级是否追上享受队列最后一个，若追上则加入享受队列if(serving_ready_list != null) running = serving_ready_list;serving_ready_list = serving_ready_list-next;/ 找到享受队列队尾元素tail = serving_ready_list;while(tail != null & tail-next != null)tail = tail-next;if(tail != null) / 检查新建队头是否追上享受队尾的优先级if(newly_ready_list != null & newly_ready_list-priority = tail-priority)p = newly_ready_list;newly_ready_list = newly_ready_list-next;p-next = null;append(&serving_ready_list, &p); / 新建队列第1个进程追加至享受队列队尾/ 若享受服务进程队列为空，新建进程队列第1个进程进入享受服务队列else if(newly_ready_list != null)serving_ready_list = newly_ready_list; / 新建队列第1个进程追加至享受队列队尾newly_ready_list = newly_ready_list-next;serving_ready_list-next = null;/ 计算各进程的优先级p = serving_ready_list;while(p != null) p-priority += serving_factor;p = p-next;/p-priority = newly_factor * (p-switch_time - p-arrive_time) + serving_factor * (sys_clock - p-switch_time);p = newly_ready_list;while(p != null) p-priority += newly_factor;p = p-next;/p-priority = newly_factor * (sys_clock - p-arrive_time);/进程切换（rrmf算法）void proc_switch_rrmf()int i;/ rrmf中，若正在运行的进程一次占用cpu消耗多个时间片且本次调度时还未用完，/ 则不调度其它进程if(running != null & running-use_slices0)return;for(i=0; inext;break;/进程执行（srr算法）void proc_run()try_wakeup_procs();/ 遍历等待队列，减少sleep_time,唤醒sleep_time降至0的进程printf( );if(running = null) / 指向正在运行进程为空printf(没有进程抵达!n);return;printf( 进程 %s 正在运行 :, running-name);running-used_run_time +; /已用时间片数+1running-next = null;show_process(running);/显示正在执行的进程printf(n);if(running-used_run_time = running-run_time) / 轮至完成队列running-finish_time = sys_clock;append(&finished_list, &running);/ 产生一个1到100之间的随机数，若小于30，则当前进程进入等待队列else if( (rand() % 100 + 1) sleep_time = (rand()%5+1);append(&waiting_list, &running);/ 添加到服务队列队尾，继续等待下次执行else append(&serving_ready_list, &running);running = null;/进程执行（rrmf算法）void proc_run_rrmf()short slices_out = 0;try_wakeup_procs();printf( );if(running = null) printf(没有进程到达!n);return;printf(进程 %s 正在运行 :, running-name);running-used_run_time +;running-next = null;show_process(running);printf(n);if(running-used_run_time = running-run_time) / 轮至完成队列running-finish_time = sys_clock;running-use_slices = (queue_num+1) - running-priority;append(&finished_list, &running);slices_out = 1;/ 产生一个1到100之间的随机数，若小于30，则当前进程进入等待队列else if( (rand() % 100 + 1) sleep_time = (rand()%5+1);running-use_slices = (queue_num+1) - running-priority;append(&waiting_list, &running);slices_out = 1;/ 添加到服务队列队尾，继续等待下次执行(单时间片进程如此，多片还需检查use_slices)else running-use_slices -;if(0 = running-use_slices) slices_out = 1;/ “多时间片”已经消耗完才转入其它队列if(running-priority priority4)running-priority -;running-use_slices = (queue_num+1) - running-priority;append(&ready_listqueue_num-running-priority, &running);if(slices_out)running = null;/ 演示进程调度队列，srr算法void start_scheduling()s