优先级法、最高响应比优先调度算法
课程设计
题目进程调度模拟设计——优先级法、
最高响应比优先调度算法
学院计算机科学与技术
专业
班级
姓名
指导教师吴利军
2013 年 1 月15 日
课程设计任务书
学生姓名：
指导教师：吴利军工作单位：计算机科学与技术学院
题目: 进程调度模拟设计——优先级法、最高响应比优先调度算法初始条件：
1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。
2．实践准备：掌握一种计算机高级语言的使用。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写
等具体要求）
1．模拟进程调度，能够处理以下的情形：
⑴能够选择不同的调度算法（要求中给出的调度算法）；
⑵能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等；
⑶根据选择的调度算法显示进程调度队列；
⑷根据选择的调度算法计算平均周转时间和平均带权周转时间。
2．设计报告内容应说明：
⑴需求分析；
⑵功能设计（数据结构及模块说明）；
⑶开发平台及源程序的主要部分；
⑷测试用例，运行结果与运行情况分析；
⑸自我评价与总结：
i）你认为你完成的设计哪些地方做得比较好或比较出色；
ii）什么地方做得不太好，以后如何改正；
iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；
iv）完成本题是否有其他方法（如果有，简要说明该方法）；
时间安排：
设计安排一周：周1、周2：完成程序分析及设计。
周2、周3：完成程序调试及测试。
周4、周5：验收、撰写课程设计报告。
（注意事项：严禁抄袭，一旦发现，一律按0分记）
指导教师签名：年月日
系主任（或责任教师）签名：年月日
进程调度模拟设计
优先级法、最高响应比优先调度算法
1．设计目的与实现功能
模拟进程调度，使程序能够完成：能够输入若干进程，包括进程的一些基本信息，如进程名、优先级、到达时间和运行时间等，选择不同的调度算法（优先级法或者最高响应比法），选择算法后，根据选择的调度算法显示进程调度队列；根据选择的调度算法计算平均周转时间和平均带权周转时间。
2．需求分析
2.1实验原理
最高响应比优先算法（HRN）：最高响应比是对先来先服务和最短进程优先法德一种综合平衡。HRN调度策略同时考虑每个进程的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的进程投入执行。
响应比R定义如下：
R=(W+T)/T=1+W/T
其中T为该进程的估计需要的执行时间，W为进程在后备状态队列的等待时间。每当要进行进程调度是，系统计算每个进程的响应比，选择其中R最大者投入执行。
优先级法：系统和用户按某种原则为进程制定一个优先级来表示该进程所享有的调度优先权。根据优先级的高低来对进程加以调度。
3. 数据结构
3.1主要结构及函数
struct timer //时间类型
{
byte hour;
byte minute;
}
typedef struct process//进程结构
{
char name[20]; //进程名
byte rank; //进程等级
timer time_in; //进程到达的时间
byte use_time; //运行需要消耗时间
timer time_start;//开始运行时刻
byte used_time; //已经运行的时间
timer time_end; //进程结束时刻
bool flag; //进程运行完成标志，完成true
}process,*process_ptr;
bool search(process process_n[])//查看是否所有进程都执行完
bool compare(timer time1,timer time2) //比较两个时间类型的大小
void paixv(process process_n[])//进程按优先级有大到小排序，规定rank越小优先级越高void printf_last(process process_n[])//打印结果
void grade_first(process process_n[])//抢占式优先级调度算法
void HRN(process process_n[])//最高响应比优先算法
优先级调度的思路：
这里设计的是一个抢占式优先级调度设一个标志位作为时钟，时间一分分地走，通过每次扫描各个进程的状态，确定这一分钟该哪个进程执行，在这之间要记录某个进程的开始时间、已运行时间和结束最后，到每个进程都执行过，完成优先级调度。
最高响应比优先调度的思路：
每次调度前都计算每个作业的响应比，从而选择其中最大者投入运行。
3.2流程图
4. 源程序的主要部分
4．1查看是否所有进程都执行完
bool search(process process_n[])
{
for(int i=0;i { if(process_n[i].flag==false) { return false; } } return true; } //比较两个时间类型的大小 bool compare(timer time1,timer time2) { if(time1.hour>time2.hour) { return true; } else if(time1.hour==time2.hour&&time1.minute>=time2.minute) { return true; } else { return false; } } 4．2进程按优先级有大到小排序，规定rank越小优先级越高void paixv(process process_n[]) { int i,j; process temp; for(i=0;i { for(j=0;j { if(process_n[j].rank>process_n[j+1].rank) { temp=process_n[j]; process_n[j]=process_n[j+1]; process_n[j+1]=temp; } } } } 4.3打印结果 void printf_last(process process_n[]) { float a[MAX];//记录每个进程的周转时间 float b[MAX];//记录每个进程的带权周转时间 float out_a=0; float out_b=0; printf("进程名进程级别提交时间运行时间开始时间完成时间周转时间带权周转时间\n"); for(int i=0;i { a[i]=(float)((process_n[i].time_end.hour-process_n[i].time_in.hour)*60+process_n[i].time_end.m inute-process_n[i].time_in.minute); b[i]=a[i]/process_n[i].use_time; out_a+=a[i]; out_b+=b[i]; printf("%4s\t%4d\t",process_n[i].name,process_n[i].rank); printf(""); if(process_n[i].time_in.hour<10) { printf("0%d",process_n[i].time_in.hour); } else { printf("%d",process_n[i].time_in.hour); } printf(":"); if(process_n[i].time_in.minute<10) { printf("0%d\t",process_n[i].time_in.minute); } else { printf("%d\t",process_n[i].time_in.minute); } ///////////////////////////////////////////////// ///////////////////////////////////////////////// printf("%4d\t",process_n[i].use_time); ///////////////////////////////////////////////// ///////////////////////////////////////////////// if(process_n[i].time_start.hour<10) { printf("0%d",process_n[i].time_start.hour); } else { printf("%4d",process_n[i].time_start.hour); } printf(":"); if(process_n[i].time_start.minute<10) { printf("0%d\t",process_n[i].time_start.minute); } else { printf("%d\t",process_n[i].time_start.minute); } ///////////////////////////////////////////////// printf(""); ///////////////////////////////////////////////// if(process_n[i].time_end.hour<10) { printf("0%d",process_n[i].time_end.hour); } else { printf("%d",process_n[i].time_end.hour); } printf(":"); if(process_n[i].time_end.minute<10) { printf("0%d\t",process_n[i].time_end.minute); } else { printf("%d\t",process_n[i].time_end.minute); } /////////////////////////////////////////////// /////////////////////////////////////////////// printf("%.2f\t",a[i]); printf("%.2f\n",b[i]); } out_a=out_a/n; out_b=out_b/n; printf("平均周转时间为：%f\n",out_a); printf("平均带权周转时间为：%f\n",out_b); } 4.4抢占式优先级调度算法 /******************************************** * 抢占式优先级调度算法* ********************************************/ void grade_first(process process_n[]) { int i; bool flag;//标志位，用于控制当前时间 while(1) { flag=true; for(i=0;i<=n;i++) { if(compare(current,process_n[i].time_in)&&!(process_n[i].flag)) { flag=false; //获取开始运行时间 if(process_n[i].time_start.hour==0&&process_n[i].time_start.minute==0) { process_n[i].time_start=current; } //记录进程已经运行的时间 process_n[i].used_time++; //时钟继续一分一分走 current.minute++; if(current.minute==60) { current.hour+=1; current.minute=0; } //运行完成后，记录完成时间 if(process_n[i].used_time==process_n[i].use_time) { process_n[i].flag=true; process_n[i].time_end=current; } break; } } if(flag) { current.minute++; if(current.minute==60) { current.hour+=1; current.minute=0; } } if(search(process_n)) { break; } else { continue; } } } 4.5最高响应比优先算法 /***************************************************** * 最高响应比优先算法* *****************************************************/ void HRN(process process_n[]) { float flag_xiangxi[MAX];//记录进程的响应比 //找到最小的时间作为当前基准时间 current=process_n[0].time_in; for(int i=1;i { if(compare(current,process_n[i].time_in)) { current=process_n[i].time_in; } } /////////////////////////////////////// while(!search(process_n)) { float temp=0; for(int i=0;i { if(compare(current,process_n[i].time_start)&&process_n[i].flag==false) { flag_xiangxi[i]=((float)(current.hour-process_n[i].time_in.hour)*60+current.minute-process_ n[i].time_in.minute)/process_n[i].use_time; if(flag_xiangxi[i]>temp) { temp=flag_xiangxi[i]; } } } for(int j=0;j { if(compare(current,process_n[j].time_start)&&process_n[j].flag==false&&temp==flag_xiangxi[j]) { process_n[j].time_start=current; current.hour=(current.hour*60+current.minute+process_n[j].use_time)/60; current.minute=(current.hour*60+current.minute+process_n[j].use_time)%60; process_n[j].time_end=current; process_n[j].flag=true; break; } } } } 4.6主函数 int main() { int one_two; process process_n[MAX]; process process_n_other[MAX]; char time_string[10]; char FLAG_exit; while(1) { printf("请输入进程个数："); scanf("%d",&n); fflush(stdin); for(int i=0;i { printf("请输入第%d个进程的参数：\n",(i+1)); printf("进程名:"); scanf("%s",process_n[i].name); fflush(stdin); printf("进程等级:"); scanf("%d",&(process_n[i].rank)); fflush(stdin); printf("提交时间:"); scanf("%s",&time_string); fflush(stdin); while(strlen(time_string)!=5) { printf("输入格式不符合要求！请重新输入...\n"); printf("提交时间:"); scanf("%s",&time_string); fflush(stdin); } int a=(time_string[0]-48)*10+time_string[1]-48; while(a>24) { printf("输入格式不符合在24小时内的要求！请重新输入...\n"); printf("提交时间:"); scanf("%s",&time_string); fflush(stdin); a=(time_string[0]-48)*10+time_string[1]-48; } process_n[i].time_in.hour=a; a=(time_string[3]-48)*10+time_string[4]-48; while(a>=60) { printf("输入格式不符合在60分钟内的要求！请重新输入...\n"); printf("提交时间:"); scanf("%s",&time_string); fflush(stdin); a=(time_string[3]-48)*10+time_string[4]-48; } process_n[i].time_in.minute=a; printf("执行时间:"); scanf("%d",&(process_n[i].use_time)); fflush(stdin); process_n[i].flag=false; } L1: printf("请你选择你将采用的调度算法:\n"); printf("1--优先级调度\n2--最高响应比优先算法\n"); printf("如果想退出程序请输入其他\n"); scanf("%d",&one_two); fflush(stdin); if(one_two==1) { current.hour=0; current.minute=0; for(i=0;i { process_n_other[i]=process_n[i]; } paixv(process_n_other); grade_first(process_n_other); printf_last(process_n_other); printf("是否退出程序？退出请输入y\n"); scanf("%c",&FLAG_exit); fflush(stdin); if(FLAG_exit=='y'||FLAG_exit=='Y') return 0; else goto L1; } else if(one_two==2) { current.hour=0; current.minute=0; for(i=0;i { process_n_other[i]=process_n[i]; } HRN(process_n_other); printf_last(process_n_other); printf("是否退出程序？退出请输入y\n"); scanf("%c",&FLAG_exit); fflush(stdin); if(FLAG_exit=='y'||FLAG_exit=='Y') return 0; else goto L1; } else { return 0; } } return 0; } 5．测试 输入测试用例： 名称优先级到达时间运行时间（分） A 2 12:35 30 B 3 12:20 25 C 4 12:39 20 D 1 12:40 22 1.优先级算法 分析如下： 第3级别B进程开始运行，但由于是抢占式的，在12:35时，也就是B运行15分钟后，有第2级别的A进程到来，A只运行5分钟后，D到来，由于D是最高级别，D可以运行完，此时是13:02，A继续进行25分钟，完成A，之后B再运行10分钟，完成B，最后运行C。 2.优先级算法 分析如下： B进程先到，所以先把B进程完成，也就到时间12:45，此时A、C、D进程都到了，如果运行A: R=(W+T)/T=1+W/T=（12:45+30-12:35）/30=4/3=1.333 如果运行C: R=(W+T)/T=1+W/T=（12:45+20-12:39）/20=13/10=1.3 如果运行D: R =(W+T)/T=1+W/T=（12:45+22-12:40）/22=27/22=1.22 由于A的响应比最大，所以先运行A, 同理，A运行之后 如果运行C： R=(W+T)/T=1+W/T=（13:15+20-12:39）/20=14/5=2.8 如果运行D: R=(W+T)/T=1+W/T=（13:15+22-12:40）/22=57/22=2.59 故运行C，最后运行D 6.自我评价与总结 6.1自我认为出色的地方 在这次的操作系统课程设计中，我设计的进程的结构是合理的，其中进程结束与否这个标志位对程序的运行起到了很大的作用，结构如下： typedef struct process//进程结构 { char name[20]; //进程名 byte rank; //进程等级 timer time_in; //进程到达的时间 byte use_time; //运行需要消耗时间 timer time_start;//开始运行时刻 byte used_time; //已经运行的时间 timer time_end; //进程结束时刻 bool flag; //进程运行完成标志，完成true }process,*process_ptr; 优先级调度的算法实现过程中，取一个参考时钟对实现抢占式的优先级起到了很大的作用，原本想实现非抢占式的优先级调度，后来想挑战一下自己，就选择抢占式的算法，在实现过程中遇到一些问题，但很好的锻炼了自己。 在最高响应比优先采用另外一个数组flag_xainxi[MAX]来记录每个进程响应比，通过比较每个响应比的大小确定下一个执行的进程，没有在进程中的结构体中添加字段来反映响应比，简化了结构。 6.2不足之处 采用数组形式实现的，输入的进程的个数是有限的，不能动态的增加，可以采用链表的形式，结合malloc，realloc函数来实现动态增加进程。本程序也使用大量的for循环，不宜大数据量的计算，影响了程序的运行速度，以后要仔细观察，进行代码优化。 6.3总结 通过这次课程设计，巩固了知识，对进程调度的理解更加深刻，同时也对C语言的基本语言有了重新的认识，开阔了自己的思维。这些经典的进程调度算法很值得我自己动手去模拟、去实现，所以在做了这两个进程调度算法后，我又去模拟实现了磁盘的电梯调度和最短时间优先调度算法以及页式调度中的最近最久未使用（LRU）算法，感觉模拟这些并不困难，但在操作系统中实现这些算法就涉及的是真正的进程和硬件设备了，去实现一个操作系统还 是比较难的。但这些模拟让我明白操作系统怎么管理进程运行，管理内存空间的，也让我明白了自己的不足，为以后的深入学习奠定了基础。 7、源码 //优先级法、最高响应比优先调度算法 #include #include #include typedef unsigned char byte; #define MAX 20 //时间类型 struct timer { byte hour; byte minute; }; timer current; //标志当前时间 int n; //输入的进程数 byte FLAG; //标志当前选择的是抢占式优先--1， //还是最高响应比--2 //进程结构 typedef struct process { char name[20]; //进程名 byte rank; //进程等级 timer time_in; //进程到达的时间 byte use_time; //运行需要消耗时间 timer time_start;//开始运行时刻 byte used_time; //已经运行的时间 timer time_end; //进程结束时刻 bool flag; //进程运行完成标志，完成true }process,*process_ptr; //查看是否所有进程都执行完 bool search(process process_n[]) { for(int i=0;i { if(process_n[i].flag==false) { return false; } } return true; } //比较两个时间类型的大小 bool compare(timer time1,timer time2) { if(time1.hour>time2.hour) { return true; } else if(time1.hour==time2.hour&&time1.minute>=time2.minute) { return true; } else { return false; } } //进程按优先级有大到小排序 //规定rank越小优先级越高 void paixv(process process_n[]) { int i,j; process temp; for(i=0;i { for(j=0;j { if(process_n[j].rank>process_n[j+1].rank) { temp=process_n[j]; process_n[j]=process_n[j+1]; process_n[j+1]=temp; } } } } //打印结果 void printf_last(process process_n[]) { float a[MAX];//记录每个进程的周转时间 float b[MAX];//记录每个进程的带权周转时间 float out_a=0; float out_b=0; printf("进程名进程级别提交时间运行时间开始时间完成时间周转时间带权周转时间\n"); for(int i=0;i { a[i]=(float)((process_n[i].time_end.hour-process_n[i].time_in.hour)*60+process_n[i].time_end.minute-process_n[i].time_in.minute ); b[i]=a[i]/process_n[i].use_time; out_a+=a[i]; out_b+=b[i]; printf("%4s\t%4d\t",process_n[i].name,process_n[i].rank); printf(""); if(process_n[i].time_in.hour<10) { printf("0%d",process_n[i].time_in.hour); } else { printf("%d",process_n[i].time_in.hour); } printf(":"); if(process_n[i].time_in.minute<10) { printf("0%d\t",process_n[i].time_in.minute); } else { printf("%d\t",process_n[i].time_in.minute); } ///////////////////////////////////////////////// ///////////////////////////////////////////////// printf("%4d\t",process_n[i].use_time); ///////////////////////////////////////////////// ///////////////////////////////////////////////// if(process_n[i].time_start.hour<10) { printf("0%d",process_n[i].time_start.hour); } else { printf("%4d",process_n[i].time_start.hour); } printf(":"); if(process_n[i].time_start.minute<10) { printf("0%d\t",process_n[i].time_start.minute); } else { printf("%d\t",process_n[i].time_start.minute); } ///////////////////////////////////////////////// printf(""); ///////////////////////////////////////////////// if(process_n[i].time_end.hour<10) { printf("0%d",process_n[i].time_end.hour); } else { printf("%d",process_n[i].time_end.hour); } printf(":"); if(process_n[i].time_end.minute<10) { printf("0%d\t",process_n[i].time_end.minute); } else { printf("%d\t",process_n[i].time_end.minute); } /////////////////////////////////////////////// /////////////////////////////////////////////// printf("%.2f\t",a[i]); printf("%.2f\n",b[i]); } out_a=out_a/n; out_b=out_b/n; printf("平均周转时间为：%f\n",out_a); printf("平均带权周转时间为：%f\n",out_b); } /******************************************** * 抢占式优先级调度算法 * ********************************************/ void grade_first(process process_n[]) { int i; bool flag;//标志位，用于控制当前时间 while(1) { flag=true; for(i=0;i<=n;i++) { if(compare(current,process_n[i].time_in)&&!(process_n[i].flag)) { flag=false; //获取开始运行时间 if(process_n[i].time_start.hour==0&&process_n[i].time_start.minute==0) { process_n[i].time_start=current; } //记录进程已经运行的时间 process_n[i].used_time++; //时钟继续一分一分走 current.minute++; if(current.minute==60) { current.hour+=1; current.minute=0; } //运行完成后，记录完成时间 if(process_n[i].used_time==process_n[i].use_time) { process_n[i].flag=true; process_n[i].time_end=current; } break; } } if(flag) { current.minute++; if(current.minute==60) { current.hour+=1; current.minute=0; } if(search(process_n)) { break; } else { continue; } } } /***************************************************** * 最高响应比优先算法 * *****************************************************/ void HRN(process process_n[]) { float flag_xiangxi[MAX];//记录进程的响应比 //找到最小的时间作为当前基准时间 current=process_n[0].time_in; for(int i=1;i { if(compare(current,process_n[i].time_in)) { current=process_n[i].time_in; } } /////////////////////////////////////// while(!search(process_n)) { float temp=0; for(int i=0;i { if(compare(current,process_n[i].time_start)&&process_n[i].flag==false) { flag_xiangxi[i]=((float)(current.hour-process_n[i].time_in.hour)*60+current.minute-process_n[i].time_in.minute)/process_n [i].use_time; if(flag_xiangxi[i]>temp) { temp=flag_xiangxi[i]; } } 操作系统 采用高响应比算法 课程设计 学号： 姓名： 专业： 班级： 指导老师： 目录 一、实验题目 (1) 二、课程设计的目的............................................................................. 错误！未定义书签。 三、设计内容 (1) 四、设计要求 (1) 五、主要数据结构及其说明................................................................. 错误！未定义书签。 六、测试数据设计及测试结果分析 (2) 七、程序运行结果 (2) 八、实验体会 (4) 九、源程序文件 (4) 实验题目 采用高响应比算法的进程调度程序 课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 设计内容 设计并实现一个采用高响应比算法的进程调度演示程序 设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间的同步关系，故只有两种状态） 5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列 6. 有性能比较功能，可比较同一组数据在不同调度算法下的平均周转时间 7. 具有一定的数据容错性 五、流程图 实验报告书 课程名：《操作系统原理》题目：进程调度 班级： 学号： 姓名： 一、实验目的 进程是操作系统最重要的概念之一，进程调度是操作系统内核的重要功能，本实验要求用C/C++/Java语言编写一个进程调度模拟程序，使用优先级或时间片轮转法实现进程调度。本实验可加深对进程调度算法的理解。 二、实验内容 1、设计有5个进程并发执行的模拟调度程序，每个程序由一个PCB表示。 2、模拟调度程序可任选两种调度算法实现。 3、程序执行中应能在屏幕上显示出各进程的状态变化，以便于观察调度的整个过 程。 三、实验说明 1．先来先服务算法 FCFS调度算法需分别列出各进程的到达时间（arrivetime），要求服务时间（servertime），开始执行时间（starttime），完成时间（endtime）。并计算出相应的周转时间（turnroundtime），平均周转时间（avturnaroundtime）。这些数据都在程序中以变量的形式出现。 FCFS调度算法中的进程运行顺序由进程的到达时间所决定，即先到达的进程无论服务时间的长短优先运行。这种算法有利于长作业进程而不利于短作业进程。 2．最高响应比算法 高响应比算法是一种为各个进程引入了动态优先权的算法。优先权=（等待时间+要求服务时间）/要求服务时间。这使得进程的优先级一直随着等待时间的增加而以速率a 提高。因此高响应比算法与其他几种算法的不同在于短作业和先到达的作业会优先得到处理，但长作业在经过一定的等待时间之后，必然会有机会分配到处理机，因此长、短作业的处理得到了更加合理的分配。该算法既照顾了短作业，又考虑到了作业到达的先后顺序，不会使得长作业得不到服务，实现了一种较好的折衷。由于每次进行进程调度前都需要计算相应响应比，因此会增加系统开销。 3．实验程序流程图 淮北师范大学 计算机学院实验设计报告 操作系统程序设计 实验报告 实验课题：高响应比调度算法 所属学院：计算机科学与技术 所属班级：11级计算机非师 姓名：李志国 辅导老师：施汉琴 2014年3月20日 目录 实验设计课题 (03) 课程设计目的 (03) 课程设计内容 (03) 课程设计要求 (04) 相关知识介绍 (05) 程序功能说明 (06) 各段程序说明 (07) 设计的流程图 (09) 程序执行截图 (11) 源程序的代码 (14) 实验小结体会 (19) 实验设计课题 设计题目：采用高响应比算法的进程调度程序 指导老师：施汉琴 课程设计目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 ?进一步巩固和复习操作系统的基础知识。 ?培养学生结构化程序、模块化程序设计的方法和能力。 ?提高学生调试程序的技巧和软件设计的能力。 ?提高学生分析问题、解决问题以及综合利用 C 语言进行程 序设计的能力。 课程设计内容 问题分析： 在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。于是我们想到了一种办法解决这个问题，就是引用动态优先权、并使作业的优先级随着等待时间的增加而以速率a提高，长作业在等待一定的时间后，必然有机会分配到处理机，这样长作业也得到了运行。由此可见： （1）如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，因此该算法有利于短作业。 （2）当要求服务的时间相同时，作业的优先权取决与其等待的时间，等待时间越长，其优先权越高，因而它实现的是先来先服务。 （3）对于长作业，作业的优先权可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可以获得处理机。 设计内容： 设计并实现一个采用高响应比算法的进程调度演示程序，响应比 R 定义如下：RWT/T1W/T 其中 T 为该作业估计需要的执行时间，为作业在后备状态队列中的等待时 W间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中 R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T 也就随着增加，也就有机会获得调度执行。这种算法是介于 FCFS 和 SJF 之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF 法，从而采用 HRRN 方式时其吞吐量将小于采用 SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。 课程设计要求 1.每一个进程有一个PCB，其内容可以根据具体情况设定。 2.进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3.可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、 时间片长度、进程优先级的初始化 4.可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资 源与进程间的同步关系，故只有两种状态） 5.采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状 态以及相应的阻塞队列 保证调度算法 基本思想:向用户做出明确的性能保证,然后去实现它.如你工作时有n个用户的登录,则你将获得cpu处理能力的1/n 算法实现:跟踪计算各个进程已经使用的cpu时间和应该获得的cpu时间,调度将转向两者之比最低的进程 五,保证调度算法 思想:向用户做出明确的性能保证,然后去实现它. 算法:容易实现的一种保证是:当工作时己有n个用户登录在系统,则将获得CPU处理能力的1/n.类似的,如果在一个有n个进程运行的用户系统中,每个进程将获得CPU处理能力的1/n. 实现方法:OS应记录及计算,各个进程在一定时间段内,已经使用的CPU时间和应该得到的CPU时间,二者之比小者优先级高. 5. 保证调度 一种完全不同的调度算法是向用户作出明确的性能保证，然后去实现它。一种很实际并很容易实现的保证是：若用户工作时有n个用户登录，则用户将获得CPU处理能力的1/n。类似地，在一个有n个进程运行的单用户系统中，若所有的进程都等价，则每个进程将获得1/n的CPU时间。看上去足够公平了。 为了实现所做的保证，系统必须跟踪各个进程自创建以来已使用了多少CPU时间。然后它计算各个进程应获得的CPU时间，即自创建以来的时间除以n。由于各个进程实际获得的CPU时间是已知的，所以很容易计算出真正获得的CPU时间和应获得的CPU时间之比。比率为0.5说明一个进程只获得了应得时间的一半，而比率为2.0则说明它获得了应得时间的2倍。于是该算法随后转向比率最低的进程，直到该进程的比率超过它的最接近竞争者为止。 彩票调度算法 基本思想:为进程发放针对系统各种资源(如cpu时间)的彩票;当调度程序需要做出决策时,随机选择一张彩票,持有该彩票的进程将获得系统资源 合作进程之间的彩票交换 六,彩票调度算法 彩票调度算法: 为进程发放针对各种资源(如CPU时间)的彩票.调度程序随机选择一张彩票,持有该彩票的进程获得系统资源. 彩票调度算法的特点: 平等且体现优先级:进程都是平等的,有相同的运行机会.如果某些进程需要更多的机会,可被给予更多彩票,增加其中奖机会. 易计算CPU的占有几率:某进程占用CPU的几率,与所持有的彩票数成正比例.该算法可实现各进程占用CPU的几率. 响应迅速 各个进程可以合作,相互交换彩票. 容易实现按比例分配如图象传输率,10帧/s,15帧/s,25帧/s 优先级调度算法 1、调度算法 考虑到紧迫型作业进入系统后能得到优先处理，引入了高优先级优先调度算法。 优先级调度的含义： （1）当该算法用于作业调度时，系统从后背作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行；（2）当该算法用于进程调度时，将把处理机分配给就绪进行队列中优先级最高的进程。 2、调度算法的两种方式 非抢占式优先级算法：在这种调度方式下，系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程就能一直执行下去，直至完成；或因等待某事件的发生使该进程不得不放弃处理机时，系统才能将处理机分配给另一个优先级高的就绪队列。 抢占式优先级调度算法：在这种调度方式下，进程调度程序把处理机分配给当时优先级最高的就绪进程，使之执行。一旦出现了另一个优先级更高的就绪进程时，进程调度程序就停止正在执行的进程，将处理机分配给新出现的优先级最高的就绪进程。常用于实时要求比较严格的实时系统中，以及对实时性能要求高的分时系统。 3、优先级的类型 进程的优先级可采用静态优先级和动态优先级两种，优先级可由用户自定或由系统确定。 静态优先级调度算法 含义：静态优先级是在创建进程时确定进程的优先级，并且规定它在进程的整个运行期间保持不变。 确定优先级的依据： 1）进程的类型。 2）进程对资源的需求。 3）根据用户的要求。 优点：简单易行；系统开销小。 缺点：不太灵活，很可能出现低优先级的作业，长期得不到调度而等待的情况；静态优先级法仅适合于实时要求不太高的系统。 动态优先级调度算法 含义：动态优先级是创建进程时赋予该进程一个初始优先级，然后其优先级随着进程的执行情况的变化而改变，以便获得更好的调度性能。 优点：使相应的优先级调度算法比较灵活、科学，可防止有些进程一直得不到调度，也可防止有些进程长期垄断处理机。 缺点：需要花费相当多的执行程序时间，因而花费的系统开销比较大。 4、实时调度算法 由于在任何一个实时系统中毒存在着若干个实时进程或任务，用来反应或控制相应的外部事件，并往往具有某种程度的紧迫性，所以对实时系统中的调度算法提出了某些特殊要求。 对实时系统的要求 进程调度模拟设计 ——最高响应比优先调度算法实验报告 一、实验题目与要求 1、实验题目：加深对作业概念的理解。深入了解批处理系统如何组织作业、管理作业和调度作业。 2、实验要求：编写程序完成批处理系统中的作业调度，要求采用响应比高者优先的作业调度算法。实现具体包括：首先确定作业控制块的容和组成方式；然后完成作业调度；最后编写主函数，对所做工作进行测试。 二、总的设计思想及语言环境、工具 1、总的设计思想： 最高响应比优先法（HRRN）是对FCFS方式和SJF 方式的一种综合平衡。HRRN 调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 响应比R定义如下： R=(W+T)/T=1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。 每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF 之间的一种折中算法。由 于长作业也有机会投入运行，在同一时间处理的作业数显然要少于SJF 法，从而采用HRRN 方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。 2、语言环境： 计算机基本配置要求： 操作系统：WIN 98/2000/XP/2003 等Windows平台 存：256MB及以上 主存64KB（Memory）（以KB为单位分配） 开发语言：Visual C++ 6.0 3、工具：Windows平台＋Visual C++ 6.0 三、数据结构与模块说明（功能与框图） 作业调度的实现主要有两个问题：一个是如何将系统中的作业组织起来；另一个是如何进行作业调度。 为了将系统中的作业组织起来，需要为每个进入系统的作业建立档案以记录和作业相关的信息，例如，作业名、作业所需资源、作业执行时间、作业进入系统的时间、作业信息在存储器中的位置、指向下一个作业控制块的指针等信息。这个记录作业相关信息的数据块称为作业控制块（JCB ）,并将系统中等待作业调度的作业控制块组织成一个队列，这个队列称为后备队列。当进行作业调度时，从后备队列中查找选择作业。 由于实验中没有实际作业，作业控制块中的信息容只使用了实验中需要的数据。作业控制块中首先应该包括作业名；其次是作业所需资源（存大小、打印机的数量和磁带机的数量）；采用响应比高者优先作业调度算法，为了计算响应比，还需要有作业的估计执行时间、作业在系统中的等待时间；另外，指向下一个作业控制块的指针必不可少。 优 先 级 调 度 算 法 实 验 报 告 院系:****************学院班级:*********** 姓名:*** 学号:************ 一、实验题目：优先级调度算法 二、实验目的 进程调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解优先级算法的具体实施办法。 三、实验内容 1.设计进程控制块PCB的结构，通常应包括如下信息： 进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等。 2.编写优先级调度算法程序 3.按要求输出结果。 四、实验要求 每个进程可有三种状态；执行状态（RUN）、就绪状态（READY,包括等待状态）和完成状态（FINISH），并假定初始状态为就绪状态。（一）进程控制块结构如下： NAME——进程标示符 PRIO/ROUND——进程优先数 NEEDTIME——进程到完成还需要的时间片数 STATE——进程状态 NEXT——链指针 注： 1.为了便于处理，程序中进程的的运行时间以时间片为单位进行 计算； 2.各进程的优先数或，以及进程运行时间片数的初值，均由用户在程序运行时给定。 （二）进程的就绪态和等待态均为链表结构，共有四个指针如下：RUN——当前运行进程指针 READY——就需队列头指针 TAIL——就需队列尾指针 FINISH——完成队列头指针 五、实验结果： 六、实验总结： 首先这次实验的难度不小，它必须在熟悉掌握数据结构的链表和队列的前提下才能完成，这次实验中用了三个队列，就绪队列，执行队列和完成队列，就绪队列中的优先级数是有序插入的，当进行进程调度的时候，需要先把就绪队列的队首节点（优先级数最大的节点）移入执行队列中，当执行进程结束后，判断该进程是否已经完成，如果已经完成则移入完成队列，如果没有完成，重新有序插入就绪队列中，这就是这次实验算法的思想。 附录（算法代码）： 采用静态优先权优先算法的进程调度程序 学号： 姓名： 专业： 指导教师： 日期： 目录 第1部分课设简介 (3) 1.1 课程设计题目 (3) 1.2 课程设计目的 (3) 1.3 课程设计内容 (3) 1.4 时间安排 (3) 第2部分实验原理分析 (3) 2.1问题描述 (3) 2.2解决方法 (4) 第3部分主要的功能模块 (5) 3.1主要的函数 (5) 3.2 测试用例及运行结果 (7) 第4部分源代码 (9) 第5部分总结及参考文献 (16) 5.1 总结 (16) 5.2 参考文献 (17) 第1部分课设简介 1.1 课程设计题目 采用静态优先权优先算法的进程调度程序 1.2 课程设计目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 1）进一步巩固和复习操作系统的基础知识。 2）培养学生结构化程序、模块化程序设计的方法和能力。 3）提高学生调试程序的技巧和软件设计的能力。 4）提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 1.3 课程设计内容 设计并实现一个采用静态优先权算法的进程调度演示程序 1.4 时间安排 1）分析设计贮备阶段（1 天） 2）编程调试阶段（7 天） 3）写课程设计报告、考核（2 天） 第2部分实验原理分析 2.1问题描述 （1）每一个进程有一个PCB，其内容可以根据具体情况设定。 （2）进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 （3）可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、作业大小、进程优先级的初始化 （4）可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间的同步关系，故只有两种状态） （5）采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列 （6）有性能比较功能，可比较同一组数据在不同调度算法下的平均周转时间（7）具有一定的数据容错性 2.2程序设计流程图 ame,&p[i].arrivetime,&p[i].servicetime); } } void Print(struct zgxyb *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) {int k; printf("run order:"); printf("%s",p[0].name); for(k=1;k 最早期限优先调度算法（EDF）的特点和实现 摘要：最早期限优先调度算法是基于优先级的动态调度方法，是最优的单处理器调度算法，具有灵活性高、能充分利用CPU计算能力的特点。但是同时也具有调度开销增大、不能确定优先级低的任务截止之间能否得到满足的缺点，从而产生了EDF算法的优化算法NEDF和DPDS，较好的解决了上述问题，平衡了CPU使用率、响应时间、公平性和截止时间的问题。关键词：任务调度；动态调度；优先级；EDF 引言：随着计算机的发展，多道程序处理的出现需要强大的调度算法来对多任务进行调度，以确定多任务环境下任务的执行顺序以及占有CPU时间。相对于静态、不可抢占的调度方法，EDF的出现使之凭借灵活性高、CPU占有率高很快成为最优的单处理器调度算法。 一、任务调度的基本概念 在计算机发展的初期，需要使用计算机时，通常要集中在计算机所在的地方，人为的以作业的方式把工作内容一件一件的交给计算机处理，也就不存在调度的概念。随后，出现了计算机的批处理方式，计算机把作业按照先来先服务的方式进行处理，体现了一种非常简单的调度概念。随着多道程序处理方式的出现，调度逐渐变得重要和复杂起来。 在多任务的实时操作系统中，调度是一个非常重要的功能，用来确定多任务环境下任务执行的顺序和获得CPU资源后能够执行的时间长度。操作系统通过一个调度程序看来实现调度功能，调度程序以函数的形式存在，用来实现操作系统的调度算法。 调度程序是影响系统性能（如吞吐率、延迟时间等）的重要部分。在设计调度程序时，通常要综合考虑如下因素：CPU的使用率、输入、输出设备的吞吐率、响应时间、公平性和截止时间。这些因素之间有一定的冲突性，在设计调度程序时需要优先考虑最重要的需求，然后再各种因素之间进行折中处理。 二、调度方法的分类 对于大量的实时调度方法来说，主要存在以下几种划分方法： 1、离线（off-line）和在线（on-line）调度 根据获得调度信息的时机，调度算法可以分为离线调度和在线调度两类。对 第三章处理机调度与死锁 1．在三种基本类型的操作系统中，都设置了（），在批处理系统中还应设置（），在分时系统中除了（）外，通常还设置了（），在多处理机系统中则还需设置（） A 剥夺调度 B 作业调度 C 进程调度 D 中级调度 E 多处理机调度 2. 在面向用户的调度准则中，（）是选择实时调度算法的重要准则，（）是选择分时系统中进程调度算法的重要准则，（）是批处理系统中选择作业调度算法的重要准则，而（）准则是为了照顾紧急作业用户的要求而设置的。 A 响应时间快 B 平均周转时间短 C 截止时间的保证 D 优先权高的作业能获得优先服务 E 服务费低 3. 作业调度是从处于（）状态的队列中选取作业投入运行。 A 运行 B 提交 C 后备 D 完成 E 阻塞 F 就绪 4.（）是指作业进入系统到作业完成所经历的时间间隔。 A 响应时间 B 周转时间 C 运行时间 D 等待时间 E 触发时间 5. （）算法不适合作业调度。 A 先来先服务 B 短作业优先 C 最高优先权优先 D 时间片轮转 6. 下列算法中，（）只能采用非抢占调度方式，（）只能采用抢占调度方式，而其余的算法即可采用抢占方式，也可采用非抢占方式。 A 高优先权优先法 B 时间片轮转法 C FCFS调度算法 D 短作业优先算法 7. 如果为每一个作业只建立一个进程，则为了照顾短作业用户，应采用（）；为照顾紧急作业的用户，应采用（）；为能实现人机交互作用应采用（）；为了兼顾短作业和长时间等待的作业，应采用（）；为了使短作业、长作业以及交互作业用户都比较满意，应采用（）；为了使作业的平均周转时间最短，应采用（） A FCFS调度算法 B 短作业优先 C 时间片轮转法 D 多级反馈队列调度算法 E 基于优先权的剥夺调度算法 F 高响应比优先 8. 下述解决死锁的方法中，属于死锁预防策略的是（），属于死锁避免的策略是（） A 银行家算法 B 资源有序分配法 C 资源分配图化简法 D 撤销进程法 9. 死锁的预防是通过破坏产生死锁的四个必要条件来实现的。下列方法中，（）破坏了“请求与保持”条件，（）破坏了“循环等待”条件。 A 银行家算法 B 一次性分配策略 C 资源有序分配策略 D SPOOLing技术 10. 从下面关于安全状态和非安全状态的论述中，选出一条正确的论述。 A 安全状态是没有死锁的状态，非安全状态是有死锁的状态。 B安全状态是可能有死锁的状态，非安全状态也是可能有死锁的状态。 C安全状态是可能没有死锁的状态，非安全状态是有死锁的状态。 D安全状态是没有死锁的状态，非安全状态是可能有死锁的状态。 题目：设计一个按优先数调度算法实现处理器调度的程序 提示： (1)假定系统有5个进程，每个进程用一个PCB来代表。PCB的格式为： 进程名、指针、要求运行时间、优先数、状态。 进程名——P1~P5。 指针——按优先数的大小把5个进程连成队列，用指针指出下一个进程PCB的首地址。 要求运行时间——假设进程需要运行的单位时间数。 优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。 状态——假设两种状态，就绪，用R表示，和结束，用E表示。初始状态都为就绪状态。 (2) 每次运行之前，为每个进程任意确定它的“优先数”和“要求运行时间”。 (3) 处理器总是选队首进程运行。采用动态改变优先数的办法，进程每运行1次，优先 数减1，要求运行时间减1。 (4) 进程运行一次后，若要求运行时间不等于0，则将它加入队列，否则，将状态改为“结 束”，退出队列。 (5) 若就绪队列为空，结束，否则，重复(3)。 2．程序中使用的数据结构及符号说明： #define num 5//假定系统中进程个数为5 struct PCB{ char ID;//进程名 int runtime;//要求运行时间 int pri;//优先数 char state; //状态，R-就绪，F-结束 }; struct PCB pcblist[num];//定义进程控制块数组 3．流程图： (1)主程序流程图： (2)子程序init()流程图： (3) 子程序max_pri_process()流程图： (4)子程序show()流程图： (5)子程序run()流程图： 实验题目:响应比最高者优先算法 一、实验目的 熟悉操作系统作业管理步骤，用C语言编程模拟实现响应比最高者优先算法。 二、实验环境及仪器设备 硬件环境：IBM-PC或兼容机 软件环境：C语言编程环境 三、实验算法思想 最高响应比优先法(HRN，Highest Response_ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 响应比R定义如下：R =(W+T)/T = 1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加 (1)等待时间相等时。则服务时间越短，优先级越高，符合SJF思想。 (2)服务时间相等时，则等待时间越长，优先级越高，符合FCFS思想。 (3)对于长作业，只要其等待时间足够长，也能获得处理机。 四、实验步骤 实验中，作业控制块及队列的数据结构定义如下： struct task { string name; /*作业号*/ int arrTime; /* 作业到达时间*/ int serTime; /*作业要求服务时间*/ int waiTime; /*等待时间*/ int begTime; /*开始运行时间*/ int finTime; /*结束运行时间*/ 实验四模拟处理机HRRN调度算法 一、实验目的：用c++设计HRRN调度算法程序。 二、实验内容：本实验随机输入的进程个数、进程名称、进程提交到系统的时间、进程运行所需时间。通过模拟程序。显示以下信息： 1）处理机对进程的调度过程。 2）计算这N个进程的平均周转时间。 三、HRRN（最高响应比调度算法）原理 最高响应比调度：在每次调度作业时，先计算后备队中每个作业的响应比，然后挑选响应比高者投入运行。响应比R定义： R＝(w＋S)/S (R:响应比,W＝等待时间,S＝运行时间) 响应比R= 周转时间/ 运行时间 =（运行时间+ 等待时间）/ 运行时间 = 1 +（等待时间/ 运行时间） 四、示例 如：输入 进程个数：5 进程名称到达系统时间所需服务时间 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 显示运行结果： 进程名称到达系统时间所需服务时间开始时间结束时间 A 0 3 0 3 B 2 6 3 9 C 4 4 9 13 E 8 2 13 15 D 6 5 15 20 5个进程的平均周转时间：（3+7+9+7+14）/5=8 五、运行结果 六、代码 #include int status; int hrrn; int sum; }Node; int select(Node node[],int n) { int i,flag=0; for(i=0;i 经典调度算法的实现 学院： 专业： 姓名： 学号： 指导老师： 2014-3-18 目录 一、课设简介 (3) 1. 课程设计题目 (3) 2. 课程设计目的 (3) 3. 课程设计的内容 (3) 4. 课程设计要求 (3) 二、原理分析 (4) 1. 先来先服务算法介绍与分析 (4) 2. 短作业优先算法介绍与分析 (4) 3. 高响应比优先调度算法介绍与分析 (4) 4. 流程图 (5) 三、主要功能模块 (7) 1. 先来先服务算法实现代码 (7) 2. 短作业优先算法实现代码 (8) 3. 高响应比优先调度算法实现代码 (8) 四、测试与运行结果 (9) 1. 主界面 (9) 2. 先来先服务算法测试 (10) 3. 短作业优先算法测试 (11) 4. 高响应比优先调度算法测试 (13) 五、总结 (16) 六、参考文献 (16) 七、附录 (16) 一、课设简介 1.课程设计题目 经典调度算法的实现 2.课程设计目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 ●进一步巩固和复习操作系统的基础知识。 ●培养学生结构化程序、模块化程序设计的方法和能力。 ●提高学生调试程序的技巧和软件设计的能力。 ●提高学生分析问题、解决问题以及综合利用 C 语言进行程序设计的能力。 3.课程设计的内容 实现以下几种调度算法 1 FCFS 2 SJF 3 高响应比优先调度算法。 4.课程设计要求 1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 2．对系统进行功能模块分析、画出总流程图和各模块流程图。 3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。 4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。 5．所有程序需调试通过。 静态优先权优先算法的进程调度程序 学院 专业 学生姓名 学号 指导教师姓名 21014年3 月19 日 目录 1.系统需求分析 (1) 1.1问题描述 (1) 1.2功能要求 (1) 2.总体设计 (1) 2.1总体设计图 (2) 2.2各模块功能 (2) 2.3相关数据结构设计 (3) 3.详细设计 (3) 3.1采用C语言定义的相关数据类型 (3) 3.2调度算法的主要实现 (4) 4.运行结果 (4) 4.1系统调试 (4) 4.2功能实现界面 (5) 5.使用说明 (7) 6.心得体会 (8) 7.附录 (8) 7.1 源代码 (8) 7.2 参考文献 (17) 1.系统需求分析 1.1问题描述 1)设计并实现一个采用静态优先权算法的进程调度演示程序。并且求出每个进程的周转时间以及带权周转时间。 2)静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变. 一般地,优先权是利用某一范围内的一个整数来表示的,例如,0~7或0~255中的某一整数, 又把该整数称为优先数.只是具体用法各异:有的系统用"0"表示最高优先权,当数值愈大时,其优先权愈低;而有的系统恰恰相反. 确定进程优先权的依据有如下三个方面: a.进程类型.(系统进程/用户进程) b.进程对资源的需求.(需求量的大小) c.用户要求.(用户进程紧迫程度) 3)本程序采用优先级数字大的优先权大。 1.2功能要求 1）每一个进程有一个PCB，其内容可以根据具体情况设定。 2）进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定。3）可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、进程优先级的初始化。 4）可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间的同步关系，故只有两种状态）。 5）具有一定的数据容错性。 /* 非抢占式高优先级调度算法（优先数越大级别越高） 算法思想：在按进程达到时间由小到大的顺序输入进程信息后，先对其优先数进行排列，将最先到达的进程的到达时间设为开始时间，计算结束时间， 然后对后面到达的时间与该进程的结束时间进行比较，如若小于该进程的结束时间，记录进程的个数，再对其优先数逐个进行比较，将优 先数最大的提到前面，每次进程结束都要进行比较，得到执行序列，在依次输出结果 */ #include<> #define MAX 100 struct hrfs { char name[10]; float arrvitetime; float starttime; float servietime; float finishtime; int priority;riority; j=1; while((j 作业调度之最短作业优先算法5例题解析 例题一、某系统采用不能移动已在主存储器中作业的可变分区方式管理主存储器，现有供用户使用的主存空间100K，系统配有4台磁带机，有一批作业见下表： 作业序号进输入井时间要求计算时间需要主存容量申请磁带机数 1 10：00 25分钟15K 2台 2 10：20 30分钟60K 1台 3 10：30 10分钟50K 3台 4 10：3 5 20分钟10K 2台 5 10：40 15分钟30K 2台 按计算时间最短者优先算法如下表： 我的解释：系统首先装入1、2、4，但1结束时4沿未到达，因此先执行2；2执行完毕后，资源可以分配给3或5，考虑5的时间短优先分配5并执行，执行完5后，主存中只有4已就绪并等待执行，因此开始执行4，执行4的同时系统会将作业3装入主存，最后自然执行作业3；因此最后的顺序是： 1\2\5\4\3 作业序号进输入井时间进入主存时间开始计算时间结束计算时间周转时间解释 1 10：00 10：10 10：00 10：25 25 此时输入井中只有一个作业且满足资源要求，因此被选中运行。 2 10：20 10：20 10：25 10：55 35 作业2到达输入井，满足资源要求，装入主存，等到作业1运行完毕进入运行。 5 10：40 10：55 10： 55 11：10 30 由于作业3要求主存空间无法满足，因此作业4先行一步装入主存，当作业2让出处理器的同时，作业5满足资源要求进入主存就绪。根据算法作业5先进入处理器运行。 4 10：3 5 10：35 11：10 11：30 55 3 10：30 11：30 11：30 11：40 70 最后作业3装入主存并运行 平均周转时间：（25+35+30+55+70）/5＝43 分钟 ［分析］解答本题时应注意如下几个问题： 第一，系统采用的是多道程序设计技术，但没有限定并行工作的道数，因此，只要当前尚未分配的资源可以满足在输入井中等待的某些作业的要求时，作业调度可以按照给定的算法从中选择一个或多个作业装人主存储器； 第二，采用可变分区方式管理主存储器，但没给出主存空间的分配算法，因而，只要有合适的空间就可分配，题中还规定可用移动技术来合并分散的空闲区； 第三，对磁带机采用静态分配； 第四，进程调度采用可抢占的最高优先级调度算法，即对已被装人主存储器的作业而言优先级高的作业可抢占处理器执行； 第五，虽然作业需要使用磁带机，但题意中已提示忽略磁带机和调度所花的时间，所以，解题时不必考虑外围设备的启动二八D中断等复杂情况，只需把它们当作纯计算型的作业； 第六，由于没有规定什么时候开始进行作业调度，故在一般情况下只要输入井中有等待处理的作业就可按选定的算法去选择满足必要条件的作业。 根据本题的要求列表分析如下： UCOS优先级调度算法最详解 经过一个上午时间，终于明白UCOS系统的按优先级调度就绪任务的算法，以个人见解展示给各位，希望各位提出意见uponzw630@https://www.wendangku.net/doc/e717406110.html,。 首先说明，解释两个表格的含义。 说明 OSMapTbl就是0-7这8个数值用二进制的BIT位来表示。 OSUnMapTbl就是将0x00-0xff每个数据中最低位为1的位号全部列举出来 INT8U const OSMapTbl[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}; INT8U const OSUnMapTbl[] = { 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x00 to 0x0F*/ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x10 to 0x1F*/ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x20 to 0x2F*/ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x30 to 0x3F*/ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x40 to 0x4F*/ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x50 to 0x5F*/ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x60 to 0x6F*/ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x70 to 0x7F*/ 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x80 to 0x8F*/ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x90 to 0x9F*/ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xA0 to 0xAF*/ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xB0 to 0xBF*/ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xC0 to 0xCF*/ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xD0 to 0xDF*/ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xE0 to 0xEF*/ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 /* 0xF0 to 0xFF*/ }; Y处于BIT5-BIT3，X处于BIT2-BIT0。 我们知道优先级prio的值越小，prio的优先级越高。 X和Y的范围均为000-111，十进制数里0-7，更8个级别，为了判断X或Y的大小，我们就引入了表格OSMapTbl[]= {0x01, 0x02, 0x04, 0x08, 0x10, 0x20,操作系统高响应比调度算法
先来先服务+响应比算法
高响应比调度算法
几种操作系统调度算法
优先级调度算法
操作系统最高响应比优先调度算法实验报告(广西民大)
优先级调度算法实验报告
采用静态优先权优先算法的进程调度程序
高响应比调度算法(c语言程序实现)
最早期限优先调度算法(EDF)的特点和实现
操作系统复习题(第三章)
设计一个按优先数调度算法实现处理器调度的程序 改
响应比最高者优先算法
最高响应比调度算法代码
经典调度算法的实现
静态优先权优先算法的进程调度程序
非抢占式高优先级调度算法
作业调度之最短作业优先算法5例题解析.doc
UCOS优先级调度算法最详解