实验相关知识
1、进程调度算法:采用动态最高优先数优先的调度算法(即把处理机分配给优先数最高的进程)
动态最高优先数优先调度算法是一种进程调度算法,它根据进程的动态优先级来分配处理机。每个进程都被分配一个优先级数,该数值随时间的推移而变化。当一个进程等待时间较长时,其优先级就会提高,以增加它被选中执行的机会。以下是该算法的一般工作原理:
初始化优先级: 每个进程在进入就绪队列时被分配一个初始优先级。这通常可以基于进程的属性,如等待时间、资源需求等。
动态调整优先级: 随着时间的推移,等待时间增加的进程的优先级逐渐提高。这是为了避免长时间等待的进程饥饿,因为等待时间越长,该进程的优先级就越高,增加了它被选中执行的机会。
选择最高优先级进程: 在每次调度时,选择具有最高优先级的进程来执行。这确保了被认为是最紧急的进程首先获得处理机。
降低优先级: 一旦进程被选中执行,其优先级通常会降低,以确保其他等待时间较长的进程有机会被选中。
这种调度算法的优势在于它可以适应系统的动态变化,更好地处理等待时间较长的进程。然而,可能存在的问题包括可能导致优先级逆转的情况,即优先级较低的进程长时间无法执行的问题。
2、每个进程有一个进程控制块(PCB)表示
进程控制块可以包含如下信息:
- 进程名----进程标示数ID;
- 优先数----Priority,优先数越大优先权越高;
- 到达时间----进程的到达时间为进程输入的时间;
- 进程还需要运行时间----AllTime,进程运行完毕AllTime =0;
- 已用CPU时间----CPUTime;
- 进程的阻塞时间StartBlock----表示当进程在运行StartBlock个时间片后,进程将进入阻塞状态;
- 进程的阻塞时间StartTime----表示当进程阻塞StartTime个时间片后,进程将进入就绪状态;
- 进程状态----State;
- 队列指针----Next,用来将PCB排成队列。
3、调度原则
- 进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数产生)。进程的到达时间为进程输入的时间;
- 进程的运行时间以时间片为单位进行计算;
- 进程在就绪队列中带一个时间片,优先数加1;
- 每个进程的状态可以是就绪R(Ready)、运行R(Run)、阻塞B(Block)、或完成F(Finish)四种状态之一;
- 就绪进程获得CPU后都只能运行一个时间片,用已占用CPU时间加1来表示;
- 如果运行一个时间片后,进程的已占用CPU时间已达到所需要的运行时间,则撤消该进程,如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间,也就是进程还需要继续运行,此时应将进程的优先数减3,然后把它插入就绪队列等待CPU;
- 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB,以便进行检查;
重复以上过程,直到所要进程都完成为止。
实验设备与软件环境
安装环境:分为软件环境和硬件环境
硬件环境:内存ddr3 4G及以上的x86架构主机一部
系统环境:windows 、linux或者mac os x
软件环境:运行vmware或者virtualbox
软件环境:Ubuntu操作系统
实验内容
一、一个简单的进程调度模拟程序的实现
1.程序需要运用进程调度算法:采用动态最高优先数优先的调度算法(即把处理机分配给优先数最高的进程)
对进程的优先调度不清楚,代码执行会混乱。
解决方法:通过Sort()函数对进程进行优先级排列(这里体现的是优先数最高的进程排到最前面)
通过Sort()函数对进程进行优先级排列(这里体现的是优先数最高的进程排到最前面)。
Sort()函数
2.每个进程有一个进程控制块(PCB)表示
本程序里面进程控制块包含如下信息:
进程名——进程标示数ID;
优先数——Priority,优先数越大优先权越高;
到达时间——Time,进程的到达时间为进程输入的时间;
进程还需要运行时间——AllTime,进程运行完毕AllTime =0;
进程的总时间——totletime,计算该进程的总时间,最开始就是该进程需要的完成时间。每经过了一次时间片,所需要完成的时间就相继-1。
已用CPU时间——CPUTime;
进程的阻塞时间StartBlock——表示当进程在运行StartBlock个时间片后,进程将进入阻塞状态;
进程的阻塞时间StartTime——表示当进程阻塞StartTime个时间片后,进程将进入就绪状态;
进程状态——State;每个进程都会有对应着四种状态:Ready(就绪):W、Run(运行):R、Block(阻塞):B、Finish(结束):F。
队列指针——Next,用来将PCB排成队列。
进程控制块PCB
程序通过OutPut(struct PCB * pr)函数在每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB,以便进行检查。
会显示当前进程的进程ID,状态(state)、优先数(Priority)、进程还需要运行时间(ALLTime)、已用 CPU 时间(CPUTime)。
值得注意的是,当totletime(进程的总时间)等于0的时候,代表该进程完成了,此时进程的状态为结束,即F(Finish )。
否则此时进程的状态根据运行的情况来得知是就绪W(Ready))、运行R(Run)还是堵塞B(Block)。
显示当前进程
3. 调度原则
3.1 进程的优先数及需要的运行时间可以事先人为地指定
通过Input()函数输入进程控制块信息。输入进程的信息包括进程优先数和进程需要运行时间。接着对于CPUTime、StartBlock、StartTime进行初始化为0。
初始化进程状态(State)–> Ready(就绪),以及将 进程需要运行时间赋值给totletime。
Input()函数输入进程控制块信息
3.2 进程的运行时间以时间片为单位进行计算;进程在就绪队列中带一个时间片,优先数加1
Check()函数查看进程情况,如果进程在就绪队列中带一个时间片,优先数加1;
Check()函数建立进程查看
3.3 每个进程的状态可以是就绪 R(Ready)、运行 R(Run)、阻塞 B(Block)、或完成 F(Finish)四种状态之一
因为就绪和运行的首字母都是R,为了方便区分,我设置就绪为W、运行为R。阻塞还是B,结束还是F。
进程状态
3.4 如果运行一个时间片后,进程的已占用CPU时间已达到所需要的运行时间,则撤消该进程,如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间,也就是进程还需要继续运行,此时应将进程的优先数减3,然后把它插入就绪队列等待CPU
Destroy()和Running()函数
3.5 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB,以便进行检查
通过OutPut(struct PCB * pr)函数能显示当前进程的进程ID,状态(state)、优先数(Priority)、进程还需要运行时间(ALLTime)、已用 CPU 时间(CPUTime)。
值得注意的是,当totletime(进程的总时间)等于0的时候,代表该进程完成了,此时进程的状态为结束,即F(Finish )。
否则此时进程的状态根据运行的情况来得知是就绪W(Ready))、运行R(Run)还是堵塞B(Block)。
OutPut(struct PCB * pr)函数
二、进程调度模拟程序的程序代码
优化过后的程序代码:
#include<stdio.h> #include<stdlib.h> //ZShiJ //每个进程都会有对应着四种状态:就绪:W、运行:R、阻塞:B、结束:F,在每个时间片时,都会有对应的状态显示。 enum STATE {//就绪:W、运行:R、阻塞:B、结束:F Ready='W',Run='R',Block='B',Finish='F' }; struct PCB { int ID; //进程名 int Priority; //优先数 int Time; //到达时间 int AllTime; //进程还需要运行时间 int totletime; //进程的总时间 int CPUTime; //已用 CPU 时间 int StartBlock; //进程的进入阻塞时间 int StartTime; //进程的等待阻塞时间 enum STATE State; //进程状态 struct PCB* Next; //队列指针 }*ready=NULL,*p; void Sort() { // 该程序采用最高优先级数优先的调度算法。 // 建立对进程进行优先级排列函数 PCB *first, *second; int insert=0; if(ready==NULL||(p->Priority>ready->Priority)) { //优先级最大者,插入队首 p->Next=ready; ready=p; } else { // 进程比较优先级,插入适当的位置中 first=ready; second=first->Next; while(second!=NULL) { if(p->Priority>second->Priority) { //若插入进程比当前进程优先数大 //插入到当前进程前面 p->Next=second; first->Next=p; second=NULL; insert=1; } else { // 插入进程优先数最低,则插入到队尾 first=first->Next; second=second->Next; } } if(insert==0) first->Next=p; } } void Input() { // 输入进程控制块信息 int i,num; //clrscr(); /*清屏*/ //采用动态最高优先数优先的调度算法的进程调度模拟程序 printf(" ________________________________________________________________\n"); printf("| |\n"); printf("| 欢迎使用采用动态最高优先数优先的调度算法的进程调度模拟程序 |\n"); printf("| 作者:ZShiJ |\n"); printf("|________________________________________________________________|\n"); printf("\n注意:进程(state)有四种状态:就绪:W、运行:R、阻塞:B、结束:F。\n"); printf("__________________________________________________________________\n"); printf("\n 请输入进程数量:"); scanf("%d",&num); for(i=0; i<num; i++) { p=(struct PCB*)malloc(sizeof(struct PCB)); //动态生成 p->ID=i+1; printf("\n 输入进程 %d 的信息:\n",p->ID); printf("\n 进程优先数:"); scanf("%d",&p->Priority); printf("\n 进程需要运行时间:"); scanf("%d",&p->AllTime); p->Time=3*i; p->CPUTime=0; //初始化 已用CPU时间=0 p->StartBlock=0;//初始化 进程的阻塞时间=0 p->StartTime=0; //初始化 进程的阻塞时间=0 p->State=Ready;//初始化 进程状态 --> Ready(就绪) p->Next=NULL; p->totletime=p->AllTime;/*计算该进程的总时间,最开始就是该进程需要的完成时间*/ p->Next=NULL; /*让队列持续进行*/ printf("\n"); Sort(); /* 调用 sort 函数*/ } } int Length() { int l=0; struct PCB* pr=ready; while(pr!=NULL) { l++; pr=pr->Next; } return(l); } void OutPut(struct PCB * pr) { //显示当前进程 //四种状态:就绪:W、运行:R、阻塞:B、结束:F printf("\n进程ID 状态 优先数 进程还需要运行时间 已用 CPU 时间"); printf("\n ID state Priority ALLTime(还需要运行的时间) CPUTime \n"); printf(" %d\t",pr->ID); if(pr->totletime==0) printf("F\t"); else printf("%c\t",pr->State); printf(" %d\t",pr->Priority); printf(" %d\t\t\t\t",pr->totletime); printf(" %d\t",pr->CPUTime); printf("\n\n"); } void Check() { // 建立进程查看函数 struct PCB* pr; printf("\n ·········当前正在运行的进程如下显示·········\n\n"); //显示当前运行进程 OutPut(p); pr=ready; printf("\n ·········当前就绪队列状态如下显示·········\n"); //显示就绪队列状态 if(pr==NULL) { printf("\n -------------------当前就绪队列没有进程啦!------------------- \n"); } else { while(pr!=NULL) { OutPut(pr); (pr->Priority)++;//进程在就绪队列中带一个时间片,优先数加 1*/ pr=pr->Next; } } } void Destroy() { //建立进程撤消函数(进程运行结束,撤消进程) printf("\n\n 该时间片后进程 [%d] 已完成,信息如下:\n",p->ID); OutPut(p); // printf("\n"); free(p); } void Running() { // 建立进程就绪函数(进程运行时间到,置就绪状态 p->CPUTime++; p->totletime--;/*每经过了一次时间片,所需要完成的时间就相继-1*/ p->State=Run; if(p->CPUTime==p->AllTime) Destroy(); //调用 Destroy() 函数 else { // (p->Priority)--; (p->Priority)-=3;/*当进程还需要继续运行,此时应将进程的优先数减 3*/ p->State=Ready; Sort(); //调用 sort 函数 } } int main() { //主函数 int len,h=0; char ch; Input(); len=Length(); while((len!=0)&&(ready!=NULL)) { ch=getchar(); h++; printf("\n ! ! !目前执行的是第【%d】个时间片! ! ! \n",h); p=ready; ready=p->Next; p->Next=NULL; // p->State=Ready; p->State=Run;/*开始运行程序*/ Check(); Running(); printf(" ________________________________________________________________ \n"); printf(" ---------------------------------------------------------------- \n"); printf("\n 按任意键继续......"); //ch=getchar(); } printf("\n\n 所有进程已经完成.\n"); ch=getchar(); }
三、进程调度模拟程序执行结果与分析
1.运行结果
(1)单进程运行情况
进程信息:
进程ID:1
优先级:6
所需要的运行时间:3
运行截图:
输入单进程控制块信息
第1个时间片
第2个时间片
单进程运行结束
(2)双进程运行情况
进程信息:
进程 ID:1
优先级:6
所需要的运行时间:2
进程 ID:2
优先级:3
所需要的运行时间:2
运行截图:
输入双进程控制块信息
第1个时间片
第2个时间片
第3个时间片
双进程运行结束
(3)多进程运行情况
进程信息:
进程 ID:1
优先级:6
所需要的运行时间:2
进程 ID:2
优先级:3
所需要的运行时间:2
进程 ID:3
优先级:9
所需要的运行时间:2
输入多进程控制块信息
第1个时间片
第2个时间片
第3个时间片
第4个时间片
第5个时间片
多进程运行结束
2.运行结果分析(以双进程为例)
输入双进程控制块信息:
输入双进程控制块信息
分析:
通过Input()函数输入进程控制块信息。输入进程的信息包括进程优先数和进程需要运行时间。
值得注意的是:每个进程都会有对应着四种状态:就绪W(Ready)、运行R(Run)、堵塞B(Block)、结束F(Finish ),在每个时间片时,都会有对应的状态显示。
程序采用动态最高优先数优先的调度算法(即把处理机分配给优先数最高的进程)。即通过Sort()函数对进程进行优先级排列(这里体现的是优先数最高的进程排到最前面)。
时间片1:
第1个时间片
分析:
如图可以发现,进程1的优先级数为6明显大于进程2的优先级数3,所以会先运行进程1,让进程2进入就绪队列,并且显示就绪状态W(Ready)。
正在运行的进程1在经过时间片1后,进程1的CPUTime会加 1。
时间片2:
第2个时间片
分析:
通过实验要求,我们设计的程序对于要进行的进程有如下要求:
- 进程的运行时间以时间片为单位进行计算;
- 进程在就绪队列中带一个时间片,优先数加1;
- 就绪进程获得CPU后都只能运行一个时间片,用已占用CPU时间加1来表示;
- 如果运行一个时间片后,进程的已占用CPU时间已达到所需要的运行时间,则撤消该进程,如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间,也就是进程还需要继续运行,此时应将进程的优先数减3,然后把它插入就绪队列等待CPU;
在经历时间片1之后,进程1未达到所需要的运行时间,所以还需要持续运行,此时应该将进程1的优先数减3,接着插入就绪队列等待CPU,此时进程1的优先级数变为3;而经过第一个时间片后,CPU 时间就相对应加1,还需要的时间相应减 1。
同时进程2在时间片1的时候是在就绪队列当中,带了一个时间片,所以优先数加1,此时进程2的优先级数为4;
因此,在时间片2时,进程2的优先级数4大于进程1的优先级数3,因此进程2会显示运行状态,进程1显示就绪W(Ready)状态,插入就绪队列。后面依次类推。
运行的进程 2 在经过时间片后,CPUTime 会加 1。
时间片3:
第3个时间片
分析:
如同时间片2分析的一样,进程2经过第二个时间片后,仍未达到所需要的运行时间,还需要持续运行,因此进程2的优先数减3,插入就绪队列。
同时,进程1在就绪队列带有了一个时间片,所以优先级数加1。
在时间片3时。进程1的优先级数4大于进程2的优先级数1,因此进程1进行运行,进程2插入就绪队列。运行的进程1在经过时间片后,CPUTime会加1。
执行完第3个时间片后,会发现进程1的CPU时间等于2,已经达到了所需要的运行时间,因此,进程1已经完成,显示状态为结束F(Finish ),CPUTime 为2。
时间片4:
双进程运行结束
分析:
在第三个时间片后,目前就只剩下进程2仍未结束,因此直接进行运行进程2。运行的进程2在经过第四个时间片后,CPUTime 会加1,此时会发现也达到了需要的运行时间,至此,进程2的状态为结束F(Finish )。
最后,所有进程均已完成。