进程调度算法模拟带答案版.doc

实验二 进程管理2.5 作业（进程）调度算法模拟1实验目的与要求本实验的目的是通过作业或进程调度算法模拟设计，进一步加深对作业或进程调度算法的理解，通过计算平均周转时间和带权平均周转时间，进一步加深对算法的评价方法的理解。2. 实验类型：验证型3. 实验学时：44. 实验原理和知识点（1） 掌握作业或进程调度算法。（2） 平均周转时间和带权平均周转时间计算。5. 实验环境（硬件环境、软件环境）：（1） 硬件环境：Intel Pentium III 以上CPU，128MB以上内存，2GB以上硬盘。（2） 软件环境：linux操作系统gcc编译器或windows操作系统vc+集成开发环境。6. 实验内容设定一组作业或进程，给定相关参数，对这组进程或作业按调度算法实施调度，输出调度次序，并计算平均周转时间和带权平均周转时间。使用的调度算法有： 先来先服务调度算法。 优先级调度算法。 短作业（或进程）优先调度算法。 响应比高优先调度算法6.1 使用的主要数据结构：（1） 定义一个结构体，结构体的主要成员有：序号、作业（进程）号或名称、提交时间、运行时间、优先数、进入输入井时间、开始运行时间、尚需运行时间、运行结束时间、周转时间、带权周转时间、运行次序等。（2） 利用定义的结构体，定义一个结构体数组，用来记录系统中的作业或进程。6.2 算法描述：1主控程序算法描述进程（作业）参数输入选择调度算法0 1 2 3 4调用先来先服务调度程序调用短作业（进程）调度程序调用响应比高者优先调度程序重复执行输出调度结果2数据输入算法输入进程或作业个数对每一个进程或作业输入进程或作业名输入进程或作业号输入进程或作业到达时间输入进程或作业运行时间输入进程或作业优先级3数据输出算法对每个作业执行输出进程（或作业）号、进程（或作业）名、到达时间、开始运行时间、运行结束时间、优先级、运行次序、周转时间、带权周转时间计算并输出平均周转时间、带权周转时间平均4先来先服务调度算法描述系统中有未运行的作业在未运行的作业中选择一个提交时间最早的作业把运行次序填入数组相应位置；分别计算出该作业进入输入井时间、开始运行时间、运行结束时间、周转时间、带权周转时间，并填入数组相应位置。调用输出程序输出结果先来先服务调度算法5优先级调度算法系统中有未运行的作业把运行次序填入数组相应位置；分别计算出该作业进入输入井时间、开始运行时间、运行结束时间、周转时间、带权周转时间，并填入数组相应位置。调用数据输出程序输出结果优先级调度算法在数组中找第一个未运行的作业Pmin该作业的优先数（当前最小的）k该作业的在数组中的下标作业的优先数与Pnim比较有未运行的作业未找到找到Pmin该作业的优先数k该作业的在数组中的下标大6短作业（或进程）优先调度算法作业的运行时间与Rnim比较有未运行的作业未找到找到Rmin该作业的运行时间k该作业的在数组中的下标长短选择运行时间最短作业的算法7响应比高优先调度算法系统中有未运行的作业在未运行的作业中选择一个响应比最高的作业运行（响应比相同按先来先服务进行选择）把运行次序填入数组相应位置；分别计算出该作业进入输入井时间、开始运行时间、运行结束时间、周转时间、带权周转时间，并填入数组相应位置。调用数据输出程序输出结果响应比高优先调度算法6.3 C语言程序实现#include/using namespace std;#define MAX 10struct task_struct char name10; /*进程名称*/ int number; /*进程编号*/ float come_time; /*到达时间*/ float run_begin_time; /*开始运行时间*/ float run_time; /*运行时间*/ float run_end_time; /*运行结束时间*/ int priority; /*优先级*/ int order; /*运行次序*/ int run_flag; /*调度标志*/ tasksMAX;int counter; /*实际进程个数*/int fcfs(); /*先来先服务*/int ps(); /*优先级调度*/int sjf(); /*短作业优先*/int hrrn(); /*响应比高优先*/int pinput(); /*进程参数输入*/int poutput(); /*调度结果输出*/void main() int option; pinput(); printf(请选择调度算法（04）:n); printf(1.先来先服务n); printf(2.优先级调度n); printf( 3.短作业优先n); printf( 4.响应比高优先n); printf( 0.退出n); scanf(%d,&option); switch (option) case 0: printf(运行结束。n); break; case 1: printf(对进程按先来先服务调度。nn); fcfs(); poutput(); break; case 2: printf(对进程按优先级调度。nn); ps(); poutput(); break; case 3: printf(对进程按短作业优先调度。nn); sjf(); poutput(); break; case 4: printf(对进程按响应比高优先调度。nn); hrrn(); poutput(); break; int fcfs() /*非抢占式先来先服务，该程序段默认进程已经按到达先后顺序排成了队列，如果考虑输入为乱序，还需要根据come_time对进程进行排队，形成一个先来后到的队列。*/float time_temp=0; int i; int number_schedul; time_temp=tasks0.come_time; for(i=0;icounter;i+) tasksi.run_begin_time=time_temp; tasksi.run_end_time=tasksi.run_begin_time+tasksi.run_time; tasksi.run_flag=1; time_temp=tasksi.run_end_time; number_schedul=i; tasksnumber_schedul.order=i+1; return 0;/*非抢占式优先级调度，默认tasks0是最早到达的进程，进程已按到达先后顺序排成了队列。*/int ps()float temp_time=0; int i=0,j; int number_schedul,temp_counter; /*正在被调度执行的进程编号和已经调度完成的进程个数*/ int max_priority; max_priority=tasksi.priority; j=1; /* 从从到达时间最早且相同的进程中遍历，查找第一个被调度的进程*/ while (jtasksi.priority) max_priority=tasksj.priority; i=j; j+; /*对第一个被调度的进程求相应的参数*/number_schedul=i; tasksnumber_schedul.run_begin_time=tasksnumber_schedul.come_time;tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; tasksnumber_schedul.run_flag=1; temp_time=tasksnumber_schedul.run_end_time; tasksnumber_schedul.order=1; temp_counter=1; /*循环查找下一个被调度的进程，直到所有的tasksj.run_flag =1*/ while (temp_countercounter) max_priority=0; for(j=0;jcounter;j+) if(tasksj.come_timemax_priority) max_priority=tasksj.priority; number_schedul=j; /*对找到的下一个被调度的进程求相应的参数*/ tasksnumber_schedul.run_begin_time=temp_time; tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; tasksnumber_schedul.run_flag=1; temp_time=tasksnumber_schedul.run_end_time; temp_counter+; tasksnumber_schedul.order=temp_counter; return 0;int sjf() /*非抢占式短作业优先，默认tasks0是最早到达的进程，进程已按到达先后顺序排成了队列。*/float temp_time=0; int i=0,j; int number_schedul,temp_counter; /*正在被调度执行的进程编号和已经调度完成的进程个数*/ float run_time; /*借助该局部变量可以帮助找到执行时间run_time最短进程*/ run_time=tasksi.run_time; j=1;/*从到达时间最早且相同的进程中查找第一个被调度的进程*/ while (jcounter)&(tasksi.come_time=tasksj.come_time) if (tasksj.run_timetasksi.run_time) run_time=tasksj.run_time; i=j; j+; /*对第一个被调度的进程求相应的参数*/number_schedul=i; tasksnumber_schedul.run_begin_time=tasksnumber_schedul.come_time; tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; tasksnumber_schedul.run_flag=1; temp_time=tasksnumber_schedul.run_end_time; tasksnumber_schedul.order=1; temp_counter=1; /*循环查找下一个被调度的进程，直到所有的tasksj.run_flag =1*/ while (temp_countercounter) /*找到在上一个进程执行期间（到“目前”为止）到达时间最晚的一个进程*/ for(j=0;jcounter;j+) if(tasksj.come_time=temp_time)&(!tasksj.run_flag) run_time=tasksj.run_time;number_schedul=j;break; /* 找到到“目前”为止，最短的进程，即run_time 最小的进程*/ for(j=0;jcounter;j+) if(tasksj.come_time=temp_time)&(!tasksj.run_flag) if(tasksj.run_timerun_time) run_time=tasksj.run_time; number_schedul=j; /*对找到的下一个被调度的进程求相应的参数*/ tasksnumber_schedul.run_begin_time=temp_time; tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; tasksnumber_schedul.run_flag=1; temp_time=tasksnumber_schedul.run_end_time; temp_counter+; tasksnumber_schedul.order=temp_counter; return 0;/*非抢占式响应比高优先，默认tasks0是最早到达的进程，进程已按到达先后顺序排成了队列。*/int hrrn() int j,number_schedul,temp_counter; float temp_time,respond_rate,max_respond_rate; /*第一个进程被调度，系统刚开始运行时，同时到达的进程响应比都为0（按该程序所采用的等待时间/运行时间这个公式算），因此按队列顺序必然是第一个进程最先被调度*/tasks0.run_begin_time=tasks0.come_time; tasks0.run_end_time=tasks0.run_begin_time+tasks0.run_time; temp_time=tasks0.run_end_time; tasks0.run_flag=1; tasks0.order=1; temp_counter=1; /*调度其他进程*/while(temp_countercounter) max_respond_rate=0; /*找响应比高的进程*/for(j=1;jcounter;j+) if(tasksj.come_timemax_respond_rate) max_respond_rate=respond_rate; number_schedul=j; tasksnumber_schedul.run_begin_time=temp_time; tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; temp_time=tasksnumber_schedul.run_end_time; tasksnumber_schedul.run_flag=1; temp_counter+=1; tasksnumber_schedul.order=temp_counter; return 0;int pinput() /*进程参数输入*/ int i; printf(please input the process counter:n); scanf(%d,&counter);for(i=0;icounter;i+) printf(*n); printf(please input the process of %d th :n,i+1); printf(please input the name:n); scanf(%s,tasksi.name); printf(please input the number:n); scanf(%d,&tasksi.number); printf(please input the come_time:n); scanf(%f,&tasksi.come_time); printf(please input the run_time:n); scanf(%f,&tasksi.run_time); printf(please input the priority:n); scanf(%d,&tasksi.priority); tasksi.run_begin_time=0; tasksi.run_end_time=0; tasksi.order=0; tasksi.run_flag=0; return 0;int poutput() /*调度结果输出*/int i; float turn_round_time=0,f1,w=0; printf(name number come_time run_time run_begin_time run_end_time priority order turn_round_timen); for(i=0;icounter;i+) f1=tasksi.run_end_time-tasksi.come_time; turn_round_time+=f1; w+=(f1/tasksi.run_time); printf( %s, %d, %5.3f, %5.3f, %5.3f, %5.3f, %d, %d, %5.3fn,tasksi.name,tasksi.number,tasksi.come_time,tasksi.run_time,tasksi.run_begin_time,tasksi.run_end_time,tasksi.priority,tasksi.order,f1); printf(average_turn_round_timer=%5.2fn,turn_round_time/counter); printf(weight_average_turn_round_timer=%5.2fn,w/counter);return 0;7. 验证与设计（1）用程序验证下列题目，结果与理论课所讲是否一致，如果不一致，请分析原因：题1:下表给出作业1，2，3的到达时间和运行时间。采用短作业优先调度算法和先来先服务调度算法，试问平均周转时间各是多少？123412801周转时间完成时间开始时间运行时间到达时间作业号Rmin该作业的运行时间（当前最短的）k该作业的在数组中的下标在数组中找第一个未运行的作业把运行次序填入数组相应位置；分别计算出该作业进入输入井时间、开始运行时间、运行结束时间、周转时间、带权周转时间，并填入数组相应位置。调用优先级调度程序退出程序题2、在下表中给出进程的到达时间、执行时间和优先级，请给出三种种调度算法的进程执行次序和三种调度算法的平均周转时间。这三种调度算法是：短作业优先调度算法、优先级高者优先调度算法和简单轮转法（简单轮转法中的时间片为2个单位）。（抢占式调度策略）（目前，只需要验证短作业优先调度算法、优先级高者优先调度算法）轮转调度算法首次运行运行情况记录开始运行时间是否计算尚需运行时间时间片到运行结束 系统中存在未运行完的作业记录开始时间计算运行结束时间计算周转时间记录结束次序计算平均周转时间输出结果（2）参考给出的源代码，试设计时间片轮转调度算法，并验证题2中的简单轮转法（简单轮转法中的时间片为2个单位）.参考源代码：#include/using namespace std;#define MAX 10struct task_struct char name10; /*进程名称*/ int number; /*进程编号*/ float come_time; /*到达时间*/ float run_begin_time; /*开始运行时间*/ float run_time; /*运行时间*/ float run_end_time; /*运行结束时间*/ int priority; /*优先级*/ int order; /*运行次序*/ int run_flag; /*调度标志，在轮转中，0表示没有运行完，1表示已经运行完*/ tasksMAX;int counter; /*实际进程个数*/int fcfs(); /*先来先服务*/int ps(); /*优先级调度*/int sjf(); /*短作业优先*/int hrrn(); /*响应比高优先*/int pinput(); /*进程参数输入*/int poutput(); /*调度结果输出*/int rr(); /*轮转*/void main() int option; float rr_time; pinput(); printf(请选择调度算法（04）:n); printf(1.先来先服务n); printf(2.优先级调度n); printf( 3.短作业优先n); printf( 4.响应比高优先n); printf( 5.轮转调度算法n); printf( 0.退出n); scanf(%d,&option); switch (option) case 0: printf(运行结束。n); break; case 1: printf(对进程按先来先服务调度。nn); fcfs(); poutput(); break; case 2: printf(对进程按优先级调度。nn); ps(); poutput(); break; case 3: printf(对进程按短作业优先调度。nn); sjf(); poutput(); break; case 4: printf(对进程按响应比高优先调度。nn); hrrn(); poutput();break; case 5: printf(进行时间片轮转调度。n); rr(); poutput(); break; int rr() /*轮转*/ float rr_time; /* */ int i,temp_counter=0; int run_begin_flagMAX=0; /*循环变量、已经全部完成的进程数量、进程是否第一次运行用于计算进程的开始运行时间*/ float time_temp,rest_timeMAX=0; /*当前时间、被调度的进程还剩下多少时间没被执行*/ printf(请输入时间片包含的单位时间个数：n); scanf(%f,&rr_time); time_temp=tasks0.come_time; /计算各个进程的初始剩余时间 for(i=0;icounter;i+) rest_timei=tasksi.run_time; /*轮转调度*/while (temp_countercounter) for(i=0;icounter;i+) if(tasksi.run_flag=0) /判断是否运行完，为0表示还没有运行完 if(run_begin_flagi=0)/如果是第一次轮转 tasksi.run_begin_time=time_temp; run_begin_flagi=1; /*如果开始第一次运行标志为0，记录开始运行时间、改变标记*/ if(rest_timei=rr_time) /如果是最后一次轮转 time_temp=time_temp+rest_timei; tasksi.run_end_time=time_temp; rest_timei=0; temp_counter+; tasksi.order=temp_counter; tasksi.run_flag=1; else /如果不是最后一次轮转 rest_timei=rest_timei-rr_time; time_temp=time_temp+rr_time; return 0;int fcfs() /*非抢占式先来先服务，该程序段默认进程已经按到达先后顺序排成了队列，如果考虑输入为乱序，还需要根据come_time对进程进行排队，形成一个先来后到的队列。*/float time_temp=0; int i; int number_schedul; time_temp=tasks0.come_time; for(i=0;icounter;i+) tasksi.run_begin_time=time_temp; tasksi.run_end_time=tasksi.run_begin_time+tasksi.run_time; tasksi.run_flag=1; time_temp=tasksi.run_end_time; number_schedul=i; tasksnumber_schedul.order=i+1; return 0;/*非抢占式优先级调度，默认tasks0是最早到达的进程，进程已按到达先后顺序排成了队列。*/int ps()float temp_time=0; int i=0,j; int number_schedul,temp_counter; /*正在被调度执行的进程编号和已经调度完成的进程个数*/ int max_priority; max_priority=tasksi.priority; j=1; /* 从从到达时间最早且相同的进程中遍历，查找第一个被调度的进程*/ while (jtasksi.priority) max_priority=tasksj.priority; i=j; j+; /*对第一个被调度的进程求相应的参数*/number_schedul=i; tasksnumber_schedul.run_begin_time=tasksnumber_schedul.come_time;tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; tasksnumber_schedul.run_flag=1; temp_time=tasksnumber_schedul.run_end_time; tasksnumber_schedul.order=1; temp_counter=1; /*循环查找下一个被调度的进程，直到所有的tasksj.run_flag =1*/ while (temp_countercounter) max_priority=0; for(j=0;jcounter;j+) if(tasksj.come_timemax_priority) max_priority=tasksj.priority; number_schedul=j; /*对找到的下一个被调度的进程求相应的参数*/ tasksnumber_schedul.run_begin_time=temp_time; tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; tasksnumber_schedul.run_flag=1; temp_time=tasksnumber_schedul.run_end_time; temp_counter+; tasksnumber_schedul.order=temp_counter; return 0;int sjf() /*非抢占式短作业优先，默认tasks0是最早到达的进程，进程已按到达先后顺序排成了队列。*/float temp_time=0; int i=0,j; int number_schedul,temp_counter; /*正在被调度执行的进程编号和已经调度完成的进程个数*/ float run_time; /*借助该局部变量可以帮助找到执行时间run_time最短进程*/ run_time=tasksi.run_time; j=1;/*从到达时间最早且相同的进程中查找第一个被调度的进程*/ while (jcounter)&(tasksi.come_time=tasksj.come_time) if (tasksj.run_timetasksi.run_time) run_time=tasksj.run_time; i=j; j+; /*对第一个被调度的进程求相应的参数*/number_schedul=i; tasksnumber_schedul.run_begin_time=tasksnumber_schedul.come_time; tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; tasksnumber_schedul.run_flag=1; temp_time=tasksnumber_schedul.run_end_time; tasksnumber_schedul.order=1; temp_counter=1; /*循环查找下一个被调度的进程，直到所有的tasksj.run_flag =1*/ while (temp_countercounter) /*找到在上一个进程执行期间（到目前为止）到达时间最晚的一个进程*/ for(j=0;jcounter;j+) if(tasksj.come_time=temp_time)&(!tasksj.run_flag) run_time=tasksj.run_time;number_schedul=j;break; /* 找到到目前为止，最短的进程，即run_time 最小的进程*/ for(j=0;jcounter;j+) if(tasksj.come_time=temp_time)&(!tasksj.run_flag) if(tasksj.run_timerun_time) run_time=tasksj.run_time; number_schedul=j; /*对找到的下一个被调度的进程求相应的参数*/ tasksnumber_schedul.run_begin_time=temp_time; tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; tasksnumber_schedul.run_flag=1; temp_time=tasksnumber_schedul.run_end_time; temp_counter+; tasksnumber_schedul.order=temp_counter; return 0;/*非抢占式响应比高优先，默认tasks0是最早到达的进程，进程已按到达先后顺序排成了队列。*/int hrrn() int j,number_schedul,temp_counter; float temp_time,respond_rate,max_respond_rate; /*第一个进程被调度，系统刚开始运行时，同时到达的进程响应比都为0（按该程序所采用的等待时间/运行时间这个公式算），因此按队列顺序必然是第一个进程最先被调度*/tasks0.run_begin_time=tasks0.come_time; tasks0.run_end_time=tasks0.run_begin_time+tasks0.run_time; temp_time=tasks0.run_end_time; tasks0.run_flag=1; tasks0.order=1; temp_counter=1; /*调度其他进程*/while(temp_countercounter) max_respond_rate=0; /*找响应比高的进程*/for(j=1;jcounter;j+) if(tasksj.come_timemax_respond_rate) max_respond_rate=respond_rate; number_schedul=j; tasksnumber_schedul.run_begin_time=temp_time; tasksnumber_schedul.run_end_time=tasksnumber_schedul.run_begin_time+tasksnumber_schedul.run_time; temp_time=tasksnumber_schedul.run_end_time; tasksnumber_schedul.run_flag=1; temp_counter+=1; tasksnumber_schedul.order=temp_counter; return 0;int pinput() /*进程参数输入*/ int i; printf(please input the process counter:n); scanf(%d,&counter);for(i=0;icounter;i+) printf(*n); printf(please input the process of %d th :n,i+1); printf(please input the name:n); scanf(%s,tasksi.name); printf(please input the number:n); scanf(%d,&tasksi.number); printf(please input the come_time:n); scanf(%f,&tasksi.come_time); printf(please input the run_time:n); scanf(%f,&tasksi.run_time); printf(please input the priority:n); scanf(%d,&tasksi.priority); tasksi.run_begin_time=0; tasksi.run_end_time=0; tasksi.order=0; tasksi.run_flag=0; return 0;int poutput() /*调度结果输出*/int i; float turn_round_time=0,f1,w=0; printf(name number come_time run_time run_begin_time run_end_time priority order turn_round_timen); for(i=0;icounter;i+) f1=tasksi.run_end_time-tasksi.come_time; turn_round_time+=f1; w+=(f1/tasksi.run_time); printf( %s, %d, %5.3f, %5.3f, %5.3f, %5.3f, %d, %d, %5.3fn,tasksi.name,tasksi.number,tasksi.come_time,tasksi.run_time,tasksi.run_begin_time,tasksi.run_end_time,tasksi.priority,tasksi.order,f1); printf(average_turn_round_timer=%5.2fn,turn_round_time/counter); printf(weight_average_turn_round_timer=%5.2fn,w/counter);return 0;8.心得体会