原创
最近几周操作系统实习,要求完成几道题目,下面是自己敲出来的模拟在单处理器情况下的进程调度算法(说算法可能过于高大尚),
采用的是短作业优先调度算法、时间片轮转调度、最高优先级优先算法三种算法中的最高优先级算法。
题目阐述如下:
设计一:进程调度
设计目的:
进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用CPU的方法。
在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处
理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。本设计模拟在单处理器情况下的进程调度,目的是加深对进程调度
工作的理解,掌握不同调度算法的优缺点。
设计内容:
设计程序模拟单处理机系统中的进程调度算法,在短作业优先调度算法、时间片轮转调度、最高优先级优先算法三种算法中选择两种实现。
每个进程由一个进程控制块(PCB)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进
程状态等。进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数产生)。进程的到达时间为进程输入的时间。
进程的运行时间以时间片为单位进行计算。
每个进程的状态可以是就绪W(Wait)、运行R(Run)或完成F(Finish)3中状态之一。
以下是最高优先级优先算法思想:
就绪进程获得CPU后都只能运行一个时间片,用已占用CPU时间加1来表示。
如果运行一个时间片后,进程的已占用CPU时间已达到所需要的运行时间,则撤销该进程,如果运行一个时间片后进程的已占用CPU时间
还未达到所需要的运行时间,也即进程还需要继续运行,此时应将进程的优先数减1(即降低一级),然后把它插入就绪队列等待CPU。
每进行一次调度程序都打印一次运行进程、就绪队列以及各个进程的PCB,以便进行检查。
重复以上过程,直到所有进程都完成为止。
每个PCB进程包括:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态;采用结构体类型来存储一个PCB。
采用的数据结构是队列,创建的进程形成一个双向队列(采用双向队列容易寻找前驱结点的地址),遍历队列,从中找出优先级
最高的PCB取出(相当于调入CPU),将其优先数降低,增加其已用CPU时间,改变其进程状态;然后判断其已用CPU时间是否
大于等于需要运行时间,大于将其进程状态置为完成状态,否则将此PCB插入队列尾部,再次在队列中寻找优先级最高的PCB......
/* 最高优先级算法 */ #include<stdio.h> #include<stdlib.h> #include<time.h> #define N 3 #define Time_film 2 //时间片 int count = 0; //统计进程完成个数 void print(struct PCB *head); struct PCB{ int process_name; //进程名 int priority_number; //优先数,随机产生 int arrive_time; //到达时间,为进程的创建时间 int need_time; //需要运行的时间,随机产生 int used_time; //已用CPU的时间,初始值为0 int process_state; //进程状态,1表示运行,0表示完成,-1表示就绪,初始值为-1 struct PCB *cre; //前驱指针域 struct PCB *next; //后驱指针域 }; void Process_scheduling(struct PCB *head){ /* 扫描队列,寻找最高优先数的PCB,调入CPU运行; 如果 use_CPU == need_time 撤销此PCB; 否则用完一个时间片后放回队列尾部,继续扫描; */ //**************************** struct PCB *Move=head->next; struct PCB *Max_Pri=head->next; struct PCB *Tail; //尾指针 //**************************** while(Move!=NULL){ if(Max_Pri->priority_number < Move->priority_number){ Max_Pri = Move; } //寻找最高优先级进程 Move = Move->next; } //**************************** Move = Max_Pri->cre; //将最高优先级进程调出 Move->next = Max_Pri->next; if(Move->next != NULL){ Move = Max_Pri->next; Move->cre = Max_Pri->cre; } //**************************** printf(" 进程 %d 被调度: \n",Max_Pri->process_name); Max_Pri->used_time += Time_film; //增加CPU占用时间 if(Max_Pri->used_time >= Max_Pri->need_time){ Max_Pri->used_time = Max_Pri->need_time; //进程状态改变 Max_Pri->process_state = 0; count++; } else{ Max_Pri->process_state = 1; } Max_Pri->priority_number-=1; //优先数减1 printf(" %d %d %d %d %d %d \n\n",Max_Pri->process_name,Max_Pri->priority_number,Max_Pri->arrive_time,Max_Pri->need_time,Max_Pri->used_time,Max_Pri->process_state); if(count == N){ //所有进程执行完毕 printf(" 所有进程执行完毕!"); return; } printf(" 就绪队列:\n"); print(head); //输出就绪队列 printf("\n"); //**************************** if(Max_Pri->process_state !=0){ Move = head; while( Move->next!=NULL ){ //当被调出进程未完成时将其插入就绪队列尾部 Move = Move->next; } Tail = Move; Max_Pri->cre = Tail; Max_Pri->next = NULL; Tail->next = Max_Pri; Max_Pri->process_state = -1; } //**************************** Process_scheduling(head); } void print(struct PCB *head){ //输出队列函数 if(head->next == NULL){ printf("就绪队列已空\n"); return; } printf("name priority arr_time need_time use_CPU pro_state\n"); struct PCB *fry = head->next; while(fry != NULL){ printf(" %d ",fry->process_name); printf("%d ",fry->priority_number); printf("%d ",fry->arrive_time); printf("%d ",fry->need_time); printf("%d ",fry->used_time); printf("%d ",fry->process_state); printf("\n"); fry = fry->next; } printf("\n"); } int main(){ struct PCB *head; //头指针 struct PCB Pro[N+1]; //创建 N+1 个进程 head = &Pro[0]; srand(time(0)); //**************************** //设置进程参数 Pro[0].process_name = 0; Pro[0].cre = NULL; Pro[0].next = &Pro[1]; Pro[0].priority_number = 0; int i=0; for(i=1;i<=N;i++){ Pro[i].process_name = i; Pro[i].priority_number = rand()%10; while(Pro[i].priority_number == 0){ Pro[i].priority_number = rand()%10; } Pro[i].arrive_time = i; Pro[i].need_time = rand()%7; while(Pro[i].need_time == 0){ Pro[i].need_time = rand()%7; } Pro[i].used_time = 0; Pro[i].process_state = -1; } for(i=1;i<=N;i++){ //形成双向队列 if( i == N ){ Pro[i].cre = &Pro[i-1]; Pro[i].next = NULL; break; } Pro[i].cre = &Pro[i-1]; Pro[i].next = &Pro[i+1]; } //**************************** printf(" 进程初始状态: \n"); print(head); //输出初始队列状态 Process_scheduling(head); //调用进程调度函数(最高优先级) return 0; }
(运行结果部分截图)
10:58:00
2018-05-12
改进:
上面忽视了进程的到达时间这个因素,会产生致命错误:
进程没有到达,但是其优先级最高,还是会被调用!
必须从已经到达的进程中选择优先级最高的调入CPU运行,每个进程每次使用一次时间片后必须判断哪些进程已经到来,然后再
从所有到达的进程中选择优先级最高的调入CPU运行;可以设置一个动态的系统时间 system_time(初始值为最先到达进程的到
达时间)system_time 在每个进程执行完一次后都增加该进程此次执行的时间(这里不指明每次执行时间为时间片是因为当进程
剩下需要的执行时间小于一个时间片后 system_time 不会增加一个时间片),进程每次执行完一个时间片后,将 system_time
与每个进程的到达时间进行比较,大于 system_time 则未到达,反之,到达;再从已到达的进程中选择优先级最高的调入CPU运
行......值得一提的是,若遇到进程到来比较晚( system_time<进程的到达时间)前面的进程都已经执行完成(已从队列中移除)
则通过 system_time 将找不到合适的进程调入,此时必须通过 “手动”添加系统时间来达到下一个进程的到达时间,然后将其执行。
/* 最高优先级算法 */ #include<stdio.h> #include<stdlib.h> #include<time.h> #define N 5 #define Time_film 2 //时间片 int count = 0; //统计进程完成个数 int system_time=100; int flag=0; int ff=0; void print(struct PCB *head); struct PCB{ int process_name; //进程名 int priority_number; //优先数,随机产生 int arrive_time; //进程的到达时间,随机产生 int need_time; //需要运行的时间,随机产生 int used_time; //已用CPU的时间,初始值为0 int process_state; //进程状态,1表示运行,0表示完成,-1表示就绪,初始值为-1 struct PCB *cre; //前驱指针域 struct PCB *next; //后驱指针域 }; void Process_scheduling(struct PCB *head){ /* 扫描队列,将最先到达的进程调入运行,若多个进程 同时到达,选取优先级最高的进程 调入,运行状态 的进程用完一个时间片后判断是否进程是否执行完毕 或有新进程到达,加入新进程后再次选取优先级最高 的调入运行,直至进程全部调用完毕。 */ //**************************** struct PCB *Move=head->next; struct PCB *Max_Pri=head; struct PCB *Tail; //尾指针 //**************************** /* while(Move!=NULL){ if(Max_Pri->arrive_time > Move->arrive_time){ //寻找最早到达的进程 Max_Pri = Move; } Move = Move->next; } Move=hear->next; while(Move!=NULL){ //在几个同时最早时间到达的进程中选择优先级最高的 if(Max_Pri->arrive_time == Move->arrive_time){ if(Max_Pri->priority_number>Move->priority_number){ Max_Pri=Move; } } Move=Move->next; } */ flag=0; ff=0; while(++flag){ Move=head->next; Max_Pri=head; while(Move!=NULL){ if(Move->arrive_time <= system_time){ //小于等于系统时间的进程说明已经到达,小于系统时间的进程都要相互比较优先级 if(Move->priority_number>Max_Pri->priority_number){ Max_Pri=Move; } } Move=Move->next; } if(Max_Pri->cre==NULL){ //说明没有选出合适进程,需要增加系统时间 ff=1; system_time++; } else{ break; } } if(ff==1){ printf("暂无进程可执行,等待 %d 后,系统时间为: %d \n\n",flag-1,system_time); } //**************************** Move = Max_Pri->cre; //将上面选择的进程调入CPU运行 Move->next = Max_Pri->next; if(Move->next != NULL){ Move = Max_Pri->next; Move->cre = Max_Pri->cre; } //**************************** printf(" 进程 %d 被调度: \n",Max_Pri->process_name); Max_Pri->used_time += Time_film; //增加CPU占用时间 if(Max_Pri->used_time >= Max_Pri->need_time){ if(Max_Pri->used_time==Max_Pri->need_time){ system_time+=Time_film; } if(Max_Pri->used_time > Max_Pri->need_time){ system_time+=(Max_Pri->used_time-Max_Pri->need_time); } Max_Pri->used_time = Max_Pri->need_time; Max_Pri->process_state = 0; //进程状态改变 count++; } else{ system_time+=Time_film; Max_Pri->process_state = 1; } Max_Pri->priority_number-=1; //优先数减1 printf(" %d %d %d %d %d %d\n\n",Max_Pri->process_name,Max_Pri->priority_number,Max_Pri->arrive_time,Max_Pri->need_time,Max_Pri->used_time,Max_Pri->process_state); if(count == N){ //所有进程执行完毕 printf(" 所有进程执行完毕!"); return; } if(Max_Pri->process_state==1){ printf("进程 %d 未完成,进入就绪队列,系统时间为: %d \n\n",Max_Pri->process_name,system_time); } else{ printf("进程 %d 已完成,系统时间为: %d \n\n",Max_Pri->process_name,system_time); } printf(" 就绪队列:\n"); //**************************** if(Max_Pri->process_state !=0){ Move = head; while( Move->next!=NULL ){ //当被调出进程未完成时将其插入就绪队列尾部 Move = Move->next; } Tail = Move; Max_Pri->cre = Tail; Max_Pri->next = NULL; Tail->next = Max_Pri; Max_Pri->process_state = -1; } print(head); //**************************** Process_scheduling(head); } void print(struct PCB *head){ //输出队列函数 if(head->next == NULL){ printf("就绪队列已空\n"); return; } printf("name priority arr_time need_time use_CPU pro_state\n"); struct PCB *fry = head->next; while(fry != NULL){ printf(" %d ",fry->process_name); printf("%d ",fry->priority_number); printf("%d ",fry->arrive_time); printf("%d ",fry->need_time); printf("%d ",fry->used_time); printf("%d ",fry->process_state); printf("\n"); fry = fry->next; } printf("\n"); } int main(){ struct PCB *head; //头指针 struct PCB Pro[N+1]; //创建 N+1 个进程-----就绪状态队列 srand(time(0)); //**************************** //设置就绪状态进程参数 head = &Pro[0]; int i=0; for(i=0;i<=N;i++){ if(i==0){ Pro[i].process_name = 0; Pro[i].cre = NULL; Pro[i].next = &Pro[i+1]; Pro[i].priority_number = -100; continue; } Pro[i].process_name = i; Pro[i].priority_number = rand()%10; while(Pro[i].priority_number == 0){ Pro[i].priority_number = rand()%10; } Pro[i].arrive_time = rand()%10; Pro[i].need_time = rand()%7; while(Pro[i].need_time == 0){ Pro[i].need_time = rand()%7; } Pro[i].used_time = 0; Pro[i].process_state = -1; } for(i=1;i<=N;i++){ //形成双向队列 if( i == N ){ Pro[i].cre = &Pro[i-1]; Pro[i].next = NULL; break; } Pro[i].cre = &Pro[i-1]; Pro[i].next = &Pro[i+1]; } //**************************** for(i=1;i<=N;i++){ //将最先到达进程的时间设置为系统开始时间 if(Pro[i].arrive_time<system_time){ system_time=Pro[i].arrive_time; } } printf("系统时间为: %d \n",system_time); //**************************** printf(" 就绪状态进程: \n"); print(head); //输出就绪状态进程 Process_scheduling(head); //调用进程调度函数(最高优先级) return 0; }
(运行结果部分截图)
16:31:29
2018-05-18