实验一进程调度实验.doc

实验一，进程调度实验一、实验目的用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解二、实验内容及要求1编写并调试一个模拟的进程调度程序，采用“最高优先数优先”调度算法对五个进程进行调度。可以采用静态或动态最高优先数优先的算法。矚慫润厲钐瘗睞枥庑赖賃軔。2、编写并调试一个模拟的进程调度程序，采用简单轮转法和多队列轮转法的“轮转法”调度算法对五个进程进行调度。 聞創沟燴鐺險爱氇谴净祸測。三、实验主要仪器设备和材料 硬件环境：IBM-PC或兼容机 软件环境：C语言编程环境四、实验设计方案及原理每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。就绪进程获得 CPU后都只能运行一个时间片。残骛楼諍锩瀨濟溆塹籟婭骒。“最高优先数优先”调度算法的基本思想是把CPU分配给就绪队列中优先数最高的进程。（静态优先数是在创建进程时确定的，并在整个进程运行期间不再改变；动态优先数是指进程的优先数在创建进程时可以给定一个初始值，并且可以按一定原则修改优先数。例如：在进程获得一次CPU后就将其优先数减少1或者，进程等待的时间超过某一时限时增加其优先数的值，等等。）酽锕极額閉镇桧猪訣锥顧荭。简单轮转法的基本思想是：所有就绪进程按 FCFS排成一个队列，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。如果运行进程用完它的时间片后还为完成，就把它送回到就绪队列的末尾，把处理机重新分配给队首的进程。直至所有的进程运行完毕。彈贸摄尔霁毙攬砖卤庑诒尔。多队列轮转法的基本思想是：设置多个就绪队列，每个队列的优先级不同，每个队列的CPU时间片大小不等；一个新的进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度；仅当第一队列空闲时，调度程序才调度第二队列中的进程运行，后面的队列同理。謀荞抟箧飆鐸怼类蒋薔點鉍。采用链表的形式存储各进程，表头就是将要执行的进程，对于新到进程或是还未完成的进程按各调度算法进行寻位、插入。厦礴恳蹒骈時盡继價骚卺癩。五、程序流程图（图一）“最高优先数优先”调度算法开始初始化PCB，输入进程信息各进程按到达时间先后排序就绪队列空否？结束就绪队列首获得CPU，执行运行的进程占有CPU时间+1运行进程的占用CPU时间满足进程完成所需时间？插入到就绪队列尾部进程完成，撤消该进程YYNN茕桢广鳓鯡选块网羈泪镀齐。（图二）简单轮转法调度算法开始初始化PCB，输入进程信息各进程按到达时间先后排序所有就绪队列空否？结束当前就绪队列首获得CPU，执行运行的进程占有CPU时间+N运行进程的占用CPU时间满足进程完成所需时间？插入到下一就绪队列进程完成，撤消该进程YYNN鹅娅尽損鹌惨歷茏鴛賴縈诘。（图三）多队列轮转法调度算法六、源程序清单“最高优先数优先”调度算法，源程序名为：FPF.c，可执行程序名为：FPF.exe。#include "stdio.h"#include <stdlib.h>#include <conio.h># define getpcb(type) (type*)malloc(sizeof(type)struct pcb/定义进程控制块PCB char state;/进程状态 char name10;/进程名字 int super;/进程优先级 int total_time;/服务时间 int run_time;/已运行时间 struct pcb *next;*p,*ready=NULL;/ready 就绪队列typedef struct pcb PCB;sort()/对进程按优先级数进行排队 int flag=1; PCB *tm1,*tm2;/用flag标志进程有没有插到就绪队列中 if(ready=NULL)/就绪队列为空时，直接插入 ready=p; ready->next=NULL; else if(p->super>ready->super) /优先级数最大时，插入到队首 p->next=ready; ready=p; else/比较优先级数，插入到合适的位置 tm1=ready; tm2=ready->next; while(tm2) if(p->super>tm2->super) /找到进程插入的位置，进行插入 p->next=tm2; tm1->next=p; flag=0; break; tm2=tm2->next; tm1=tm1->next;/继续查找插入位置 if(flag) /优先级数最小时，插到队尾 tm1->next=p; p->next=NULL; input()/建立控制块，输入进程信息 int i,num;printf("n 请输入进程数:"); scanf("%d",&num); for (i=0;i<num;i+) printf("n 进程号：No.%d:n",i+1); p=getpcb(PCB); printf("n 输入进程名："); scanf("%s",p->name); printf("n 输入进程优先级："); scanf("%d",&p->super); printf("n 输入进程运行时间："); scanf("%d",&p->total_time);籟丛妈羥为贍偾蛏练淨槠挞。 p->run_time=0; p->state='w' p->next=NULL; sort();/调用排序函数，每输入一个进程就排序一次 display(PCB *q)/建立进程显示函数,用于显示进程当前的状态printf("n namet statet supert total_timet run_timen");預頌圣鉉儐歲龈讶骅籴買闥。printf("%st%ct%dtt%dtt%dn",q->name,q->state,q->super,q->total_time,q->run_time);渗釤呛俨匀谔鱉调硯錦鋇絨。destroy()/建立进程撤消函数(进程运行结束,撤消进程) printf("n 进程%s已完成.n",p->name); free(p); p=NULL;running()/建立进程运行函数(进程运行时间结束后,置就绪状态) p->run_time+;/占有CPU时间+1 if(p->run_time=p->total_time) destroy();/进程完成，撤消该进程铙誅卧泻噦圣骋贶頂廡缝勵。 else p->super-; p->state='w' if(p)sort();/每运行一个CPU时间调度一次check()/建立进程查看函数 PCB *pr; printf("n 当前正在运行的进程是：%s",p->name);/显示当前运行的进程信息 display(p); pr=ready; printf("n当前就绪队列状态为：n");/显示就绪队列中进程信息 while(pr) display(pr); pr=pr->next; main()/主函数 int h=0;/记录所有进程运行的次数system("cls");/清屏printf("n模拟进程调度系统最高优先数优先调度算法n"); input(); while(ready) getchar(); h+; printf("n The execute number:%d n",h);p=ready;ready=ready->next;/就绪队列首进程获得CPUp->next=NULL;p->state='R'check(); running(); printf("n 按任键继续."); printf("nn 所有进程已经完成.n");简单轮转调度算法，源程序名为：simple.c，可执行程序名为：simple.exe。#include "stdio.h"#include <stdlib.h>#include <conio.h># define getpcb(type) (type*)malloc(sizeof(type)struct pcb/定义进程控制块PCB char state;/进程状态 char name10;/进程名 int total_time;/服务时间 int run_time;/已运行时间int arrive_time;/到达时间 struct pcb *next;*p,*ready=NULL;/ready就绪队列typedef struct pcb PCB;sort()/对进程按FCFS原则进行排队int flag=1; PCB *tm1,*tm2; if(ready=NULL)/就绪队列为空时，新进程直接插入 ready=p; ready->next=NULL; else if(p->arrive_time < ready->arrive_time ) /先到达的进程排在队首擁締凤袜备訊顎轮烂蔷報赢。 p->next = ready;ready=p; else /按进程到达的时间插入到就绪队列中 tm1=ready; tm2=ready->next; while(tm2) if(p->arrive_time<tm2->arrive_time) p->next=tm2; tm1->next=p; flag=0; break; tm2=tm2->next; tm1=tm1->next;/查找合适的位置 if(flag) /进程插入到队尾 tm1->next=p; p->next=NULL; input()/建立控制块，输入进程信息 int i,num;printf("n 请输入进程数:"); scanf("%d",&num); for (i=0;i<num;i+) printf("n 进程号：No.%d:n",i+1); p=getpcb(PCB); printf("n 输入进程名："); scanf("%s",p->name);printf("n输入进程到达的时间：");scanf("%d",&p->arrive_time);贓熱俣阃歲匱阊邺镓騷鯛汉。 printf("n 输入进程运行时间："); scanf("%d",&p->total_time);坛摶乡囂忏蒌鍥铃氈淚跻馱。 p->run_time=0; p->state='w' p->next=NULL;sort();/调用Sort（）对新进程进行排序 display(PCB *q)/建立进程显示函数,用于显示进程当前的状态printf("n namet statet arrive_timet total_timet run_timen");蜡變黲癟報伥铉锚鈰赘籜葦。 printf(" %st %ct %dtt %dtt %dn",q->name,q->state,q->arrive_time,q->total_time,q->run_time);買鲷鴯譖昙膚遙闫撷凄届嬌。destroy()/建立进程撤消函数(进程运行结束,撤消进程) printf("n 进程%s已完成.n",p->name); free(p); p=NULL;running()/建立进程运行函数(进程运行时间结束后,置就绪状态)PCB *temp; p->run_time+;/占有CPU时间+1 if(p->run_time=p->total_time) destroy();/进程完成，撤消该进程綾镝鯛駕櫬鹕踪韦辚糴飙钪。 else p->state='w' if(p)/每运行一个CPU时间调度一次temp=ready;if(!temp)ready=p;p->next=NULL;Elsewhile(temp->next )temp=temp->next;temp->next =p;p->next =NULL;check()/建立进程查看函数 PCB *pr; printf("n 当前正在运行的进程是：%s",p->name);/显示当前运行的进程信息 display(p); pr=ready; printf("n当前就绪队列状态为：n");/显示就绪队列中进程信息 while(pr) display(pr); pr=pr->next; main()/主函数 int h=0;/记录所有进程运行的次数system("cls");/清屏printf("n模拟进程调度系统简单轮转法调度算法n"); input(); while(ready) getchar(); h+; printf("n The execute number:%d n",h); p=ready; ready=ready->next;/就绪队列首进程获得CPU p->next=NULL; p->state='R' check(); running(); printf("n 按任键继续."); printf("nn 所有进程已经完成.n");多队列轮转法调度算法，源程序名为：multi.c，可执行程序名为：multi.exe。#include "stdio.h"#include <stdlib.h>#include <conio.h># define getpcb(type) (type*)malloc(sizeof(type)# define N 5/定义多级队列的级数struct pcb/定义进程控制块PCB char state;/进程状态 char name10;/进程名 int total_time;/服务时间 int run_time;/已运行时间int arrive_time;/到达时间 int count;/所在队列数 struct pcb *next;*p,*readyN=NULL;/readyN 就绪队列typedef struct pcb PCB;sort()/在任一就绪队列中对进程按FCFS原则进行排队，而且队列优先级从高到低 int flag=1,i; PCB *tm1,*tm2;if(p->count<N-1) i=p->count;/记录该进程的所在的就绪队列else i=N; if(readyi=NULL) /当前队列为空时，进程直接插到队列中 readyi=p; readyi->next=NULL; else if(p->arrive_time<readyi->arrive_time)p->next=readyi; readyi=p;/当前队列进程按FCFS原则排队 else tm1=readyi; tm2=readyi->next; while(tm2) /按进程到达的时间插入到就绪队列中if(p->arrive_time<tm2->arrive_time)p->next=tm2; tm1->next=p;flag=0;break;tm1=tm1->next; tm2=tm2->next;/查找合适的位置 if(flag) /进程插入到当前就绪队列的队尾 tm1->next=p; p->next=NULL; input()/建立控制块，输入进程信息 int i,num;printf("n 请输入进程数:"); scanf("%d",&num); for (i=0;i<num;i+) printf("n 进程号：No.%d:n",i+1); p=getpcb(PCB); printf("n 输入进程名："); scanf("%s",p->name);printf("n输入进程到达的时间：");scanf("%d",&p->arrive_time);驅踬髏彦浃绥譎饴憂锦諑琼。 printf("n 输入进程运行时间："); scanf("%d",&p->total_time);猫虿驢绘燈鮒诛髅貺庑献鵬。 p->run_time=0; p->state='w' p->next=NULL;p->count=0;锹籁饗迳琐筆襖鸥娅薔嗚訝。sort();/调用Sort（）对新进程进行排序 display(PCB *q)/建立进程显示函数,用于显示进程当前的状态printf("n namet statet arrive_timet total_timet run_timen");構氽頑黉碩饨荠龈话骛門戲。 printf(" %st %ct %dtt %dtt %dn",q->name,q->state,q->arrive_time,q->total_time,q->run_time);輒峄陽檉簖疖網儂號泶蛴镧。destroy()/建立进程撤消函数(进程运行结束,撤消进程) printf("n 进程%s已完成.n",p->name); free(p); p=NULL;running()/建立进程运行函数(进程运行时间结束后,置就绪状态) p->count+;/标识进程要插入哪级队列中 if(p->count<N) p->run_time=p->run_time+p->count;/当前进程占有CPU时间增加（按该级队列的CPU时间片大小增加）尧侧閆繭絳闕绚勵蜆贅瀝纰。 else p->run_time=p->run_time+N;/最低级队列进程占有CPU时间的增加识饒鎂錕缢灩筧嚌俨淒侬减。 if(p->run_time>=p->total_time) destroy();/进程完成，撤消该进程凍鈹鋨劳臘锴痫婦胫籴铍賄。 else p->state='w' if(p) sort();/每运行一个CPU时间调度一次check()/建立进程查看函数 int i; PCB *pr; if(p->count<N)/显示每级队列的CPU时间 printf("n 当前执行的就绪队列分配的CPU时间片为：%d",p->count+1); else printf("n 当前执行的就绪队列分配的CPU时间片为：%d",N); printf("n 当前正在运行的进程是：%s",p->name); /显示当前运行的进程信息 display(p); for(i=0;i<N-1;i+) /显示每级就绪队列中进程信息pr=readyi; printf("n第%d就绪队列状态为：n",i+1); while(pr) display(pr); pr=pr->next; printf("n第%d就绪队列状态为：n",N);pr=readyN; while(pr) display(pr); pr=pr->next; main()/主函数 int h=0,i;/记录所有进程运行的次数system("cls");/清屏printf("n模拟进程调度系统多队列轮转法调度算法n"); input();for(i=0;i<=N;i+)while(readyi)getchar();h+;printf("n The execute number:%d n",h);p=readyi;readyi=p->next ;/当前就绪队列首进程获得CPUp->next=NULL; p->state='R'check();running();printf("n 按任键继续."); printf("nn 所有进程已经完成.n");七、运行结果八、结果分析与调试过程小结运行结果一切在意料中。只要掌握了各种进程调度的算法，实现起来很容易的。因为用到指针，要很清楚任一时刻它指向哪里，要不然很容易会出错。恥諤銪灭萦欢煬鞏鹜錦聰櫻。九、思考题分析不同调度算法的调度策略，比较不同调度算法的优缺点，总结它们的适用范围。答：高优先权优先调度算法，能照顾紧迫型作业，常用于批处理系统中，也作为多种操作系统中的进程调度算法，还可用于不严格的实时系统中；简单轮转法调度算法，实现起来简单，可以保证就绪队列中的所有进程在一定的时间内都能获得一时间片处理执行时间，可以用于批处理系统中；多队列轮转法调度算法，能较好地满足各种类型用户的需要，能比较及时响应新到来的进程，可以用于批处理系统中。鯊腎鑰诎褳鉀沩懼統庫摇饬。