操作系统实验实验三进程调度学号 1215108019 姓名李克帆班级 12电子2班华侨大学电子工程系实验目的1、理解有关进程控制块、进程队列的概念。
2、掌握进程优先权调度算法和时间片轮转调度算法的处理逻辑。
实验内容与基本要求1、设计进程控制块PCB的结构，分别适用于优先权调度算法和时间片轮转调度算法。
2、建立进程就绪队列。
3、编制两种进程调度算法：优先权调度算法和时间片轮转调度算法。
实验报告内容1、优先权调度算法和时间片轮转调度算法原理。
优先权算法:（1）当该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行。
（2）当该算法用于进程调度时，将把处理机分配给就绪进程队列中优先级最高的进程。
时间片轮转法:系统将所有的就绪进程按先来先服务的原则,排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片.时间片的大小从几ms到几百ms.当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片.这样就可以保证就绪队列中的所有进程,在一给定的时间内,均能获得一时间片的处理机执行时间.2、程序流程图。
3、程序及注释。
#include <stdio.h>#include <string.h>//使用timer()函数#include <windows.h>//时间延迟#define DELAY 200 //每次运算后的停留时间//时间片#define SJP 3 //这里的时间片是固定的，这就要求每个进程的服务时间略小于4/**********全局变量声明**********/unsigned short TIME=0; //无符号，定义时间unsigned short NUM=0; //无符号，定义进程数量char TYPE='1'; //模拟类型//PCB结构体定义typedef struct PCB// struct 结构体{char name[16];char state;//[R]Run,[F]Finish,[P]Pause,[N]Newunsigned short priority; //数字越大，优先级越高，最小为1 unsigned short t_arrive; //到达时间unsigned short t_start; //开始时间unsigned short t_finish; //完成时间unsigned short t_service; //服务时间unsigned short t_run; //运行时间unsigned short t_wait; //等待时间struct PCB *next;} pcb;pcb *now=NULL, //定义now指针，一开始不赋值。
指向现在运行的pcb*head=NULL; //pcb链头部指针/**********函数声明**********/void fcfs(); //先到先服务void sjf(); //短作业优先void gyxb(); //高优先比void sjplz(); //时间片轮转void init(); //初始化，完成pcb录入pcb *sort(pcb*); //对init()录入的pcb按到达时间排序void timer(); //定时器，每一个延迟自我调用一次void result(); //打印结果//先到先服务算法void fcfs(){if(now->t_arrive>TIME) //判断有无进程到达{printf("[时间：%d]\t无进程运行\n",TIME);return;}if(now->state=='N') //判断state的状态{now->state='R'; //如果是新的程序，将state改为Rnow->t_start=TIME;printf("[时间：%d]\t进程：%s 首次运行\n",TIME,now->name);//显示该程序第一次运行}else if(now->state=='R')//else if语句中嵌套两个if语句，用来判断进程处在运行阶段还是完成阶段{(now->t_run)++;//now取t_run中的地址，再取内容if(now->t_run>=now->t_service)//判断任务是否完成，标准时运行时间大于服务时间{now->state='F';//如果完成，则state的状态由Run改为Finallynow->t_finish=TIME;printf("[时间：%d]\t进程：%s 任务完成\n",TIME,now->name);//任务完成，跳出ifnow=now->next;if(now!=NULL) fcfs();//判断是否还有未完成的程序}else printf("[时间：%d]\t进程：%s 正在运行，已运行时间：%d\n",TIME,now->name,now->t_run);//任务未完成，返回外层语句继续循环执行}}//短作业优先算法void sjf(){pcb *p=head,*p_min=NULL;//创建p和p_min两个指针unsigned short t_min=9999;//从现在时间以前并且未结束的进程中，选出服务时间最小的进程while(p!=NULL && p->t_arrive<=TIME){if(p->state=='F')//判断程序是否结束{p=p->next;continue;}if((p->t_service-p->t_run)<t_min)//这个if语句用来筛选最短时间的程序{t_min=p->t_service;p_min=p;}p=p->next;}if(p_min==NULL) //如果为空，判断全部进程是否都已完成{char k='Y';p=head;while(p!=NULL){if(p->state!='F')//state状态为F时也被视为无程序在运行k='N';p=p->next;//p前往下一个程序进行扫描}if(k=='Y')now=NULL;else printf("[时间：%d]\t无进程运行\n",TIME);return;}if(p_min!=now)//如果选出的进程和之前的不同{if(now->state=='R')//暂停现在正在运行的程序，将state的状态改为P{now->state='P';printf("[时间：%d]\t进程：%s 暂停运行\n",TIME,now->name);}}if(p_min==NULL) now=head;else now=p_min;if(now->state=='N')//将新进程的状态改为正在运行的进程，并标显示进程正在运行{now->state='R';now->t_start=TIME;printf("[时间：%d]\t进程：%s 首次运行\n",TIME,now->name);}else{if(now->state=='P')//若进程被暂停，则将进程开启{now->state='R';printf("[时间：%d]\t进程：%s 继续运行\n",TIME,now->name);}(now->t_run)++;if(now->t_run>=now->t_service)//把服务时间赋予运行时间{now->state='F';now->t_finish=TIME;printf("[时间：%d]\t进程：%s 任务完成\n",TIME,now->name);gyxb();}else printf("[时间：%d]\t进程：%s 正在运行，已运行时间：%d\n",TIME,now->name,now->t_run);}}//高优先比算法void gyxb(){pcb *p=head,*p_min=NULL;unsigned short t_min=0;//从现在时间以前并且未结束的进程中，选出服务时间最小的进程while(p!=NULL && p->t_arrive<=TIME){if(p->state=='F')//检查运行完成的程序，标准时state的状态为Finish{p=p->next;continue;}//动态优先比if(p->state=='P')//设置动态优先比{p->t_wait++;p->priority+=p->t_wait/p->t_service+1;/////////////////////////////////////////////////////////// //////////////}if(p->priority>t_min)//如果现有的程序优先级大于先前程序的优先级，则进行替换。
{t_min=p->priority;p_min=p;}p=p->next;}//如果为空，判断全部进程是否都已完成if(p_min==NULL){char k='Y';p=head;while(p!=NULL){if(p->state!='F')//state状态为F时也被视为无程序在运行k='N';p=p->next;//运用p指针逐个扫描}if(k=='Y')now=NULL;else printf("[时间：%d]\t无进程运行\n",TIME);return;}//如果选出的进程和之前的不同if(p_min!=now){if(now->state=='R')//进程不同则暂停现在运行的程序{now->state='P';printf("[时间：%d]\t进程：%s 暂停运行\n",TIME,now->name);}}if(p_min==NULL) now=head;else now=p_min;if(now->state=='N'){now->state='R';now->t_start=TIME;printf("[时间：%d]\t进程：%s 首次运行\n",TIME,now->name);}else{if(now->state=='P'){now->state='R';now->t_wait=0;printf("[时间：%d]\t进程：%s 继续运行\n",TIME,now->name);}(now->t_run)++;if(now->t_run>=now->t_service){now->state='F';now->t_finish=TIME;printf("[时间：%d]\t进程：%s 任务完成\n",TIME,now->name);sjf();}else printf("[时间：%d]\t进程：%s 正在运行，已运行时间：%d\n",TIME,now->name,now->t_run);}}//时间片轮转算法void sjplz(){pcb* p=head,*q=now;//p,q分别取head和now的地址//每个时间片结束时的处理if(TIME%SJP==0 && TIME/SJP>0)//如果时间片结束时程序还没有完成则执行下面的语句{char k='Y';while(p!=NULL){if(p->state!='F'){k='N';break;}p=p->next;}if(k=='Y'){now=NULL;return;}if(p!=NULL){while(1){if (q->next!=NULL){if((q->next)->state=='F'){q=q->next;continue;}else{now=q->next;break;}}else{q=head;if(q->state=='F') continue;else{now=head;break;}}}}else{p=head;while(p->next!=NULL) p=p->next;now=p;}}if(now->t_arrive>TIME){printf("[时间：%d]\t无进程运行\n",TIME);return;}if(now->state=='N'){now->state='R';now->t_start=TIME;printf("[时间：%d]\t进程：%s 首次运行\n",TIME,now->name);}else if(now->state=='R'){(now->t_run)++;if(now->t_run>=now->t_service){now->state='F';now->t_finish=TIME;printf("[时间：%d]\t进程：%s 任务完成\n",TIME,now->name);if(now!=NULL) fcfs();}else printf("[时间：%d]\t进程：%s 正在运行，已运行时间：%d\n",TIME,now->name,now->t_run);}else if(now->state=='F')printf("[时间：%d]\t无进程运行\n",TIME);}void result()//结果的显示{pcb *p=head; //输出语句printf("\n=============运行结果===========\n\n");printf("名称优先级到达时间开始时间完成时间服务时间周转时间带权周转时间\n");while(p!=NULL){printf(" %s\t%d\t %d\t %d\t %d\t %d\t %d\t %.2f\n",p->name,p->priority,p->t_ar rive,p->t_start,p->t_finish,p->t_service,p->t_finish-p->t_arrive,1.0*(p->t_finish-p->t_arrive)/p->t_service);p=p->next;}getchar();}void timer()//用timer来选取即将用的函数{if(TYPE=='1') fcfs();else if(TYPE=='2') sjf();else if(TYPE=='3') gyxb();else if(TYPE=='4') sjplz();if(now==NULL) return;TIME++;Sleep(DELAY);timer();}void init(){pcb *p,*q;unsigned short i;printf("\n=====================实验3NEMO===========================\n\n");printf(" ***输入服务类型*** \n");printf("\n 1:先来先服务\n");printf("\n 2:短作业优先\n");printf("\n 3:高优先权优先\n");printf("\n 4:时间片轮转\n");scanf("%c",&TYPE);printf("输入进程数目:\n");scanf("%d",&NUM);for(i=0; i<NUM; i++)//for循环用来重复输入已确定的进程数目{p=(pcb *)malloc(sizeof(pcb));printf("[第%d个] 依次输入：名称优先权到达时间服务时间\n",i+1);scanf("%s\t%d\t%d\t %d",&p->name,&p->priority,&p->t_arrive,&p->t_service);if(head==NULL){head=p;q=p;}q->next=p;//利用确定的p，q指针进行初始化p->t_start=0;p->t_finish=0;p->t_run=0;p->t_wait=0;p->next=NULL;p->state='N';q=p;}getchar();}//按到达时间冒泡排序pcb* sort_pcb(pcb *h_head){pcb *p,*p1,*p2,*p3;//设置p,p1,p2,p3,p4四个指针pcb h, t;if (h_head == NULL) return NULL;h.next=h_head;p=&h; //p作为指针，存储了h的地址while (p->next!=NULL){p=p->next;}p=p->next=&t;while (p!=h.next)//{p3=&h;p1=p3->next;p2=p1->next;while (p2!=p){if ((p1->t_arrive)>(p2->t_arrive))//按到达的时间比较{p1->next=p2->next;p2->next=p1;p3->next=p2;p3=p2;p2=p1->next;}else{p3=p1;p1=p2;p2=p2->next;}}p=p1;}while (p->next!=&t){p=p->next;}p->next=NULL;return h.next;}void main(){init();system("CLS");head=sort_pcb(head);now=head;printf("进程正在运行……\n");timer();result();return;}4、运行结果以及结论。
