操作系统原理实验2：进程调度（在Ubuntu虚拟机gcc编译环境下

实验目的与要求

通过一个简单的进程调度模拟程序的实现，加深对各种进程调度算法，进程切换的理解。

实验原理与内容

1、进程调度算法：采用动态最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）。

2、每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：

1. 进程名----进程标示数ID；
2. 优先数----Priority，优先数越大优先权越高；
3. 到达时间----进程的到达时间为进程输入的时间；
4. 进程还需要运行时间----AllTime，进程运行完毕AllTime =0；
5. 已用CPU时间----CPUTime；
6. 进程的阻塞时间StartBlock----表示当进程在运行StartBlock个时间片后，进程将进入阻塞状态；
7. 进程的阻塞时间StartTime----表示当进程阻塞StartTime个时间片后，进程将进入就绪状态；
8. 进程状态----State；
9. 队列指针----Next，用来将PCB排成队列。

3、调度原则

1. 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间；
2. 进程的运行时间以时间片为单位进行计算；
3. 进程在就绪队列中带一个时间片，优先数加1；
4. 每个进程的状态可以是就绪R（Ready）、运行R（Run）、阻塞B(Block)、或完成F（Finish）四种状态之一；
5. 就绪进程获得CPU后都只能运行一个时间片，用已占用CPU时间加1来表示；
6. 如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减3，然后把它插入就绪队列等待CPU；
7. 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查；
8. 重复以上过程，直到所要进程都完成为止。

老师给的代码（具有不少错误的）：

#include<stdio.h>

#include<stdlib.h>

enum STATE{ Ready=1,Run,Block,Finish };

struct PCB{

int ID; //进程名

int Priority; //优先数

int Time; //到达时间

int AllTime; //进程还需要运行时间

int CPUTime; //已用CPU时间

int StartBlock; //进程的进入阻塞时间

int StartTime; //进程的等待阻塞时间

STATE State; //进程状态

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 请输入进程数量:");

scanf("%d",&num);

for(i=0;i<num;i++)

{

p=(PCB*)malloc(sizeof(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;

p->StartBlock=0;

p->StartTime=0;

p->State=Ready;

p->Next=NULL;

printf("\n");

Sort(); /* 调用sort函数*/

}

}

int Length()

{

int l=0; PCB* pr=ready;

while(pr!=NULL)

{

l++;

pr=pr->Next;

}

return(l);

}

void OutPut(PCB * pr) //显示当前进程

{

printf("\n ID \t state \t Priority \t ALLTime \t CPUTime \n");

printf("%d\t",pr->ID);

printf("%d\t",pr->State);

printf("%d\t",pr->Priority);

printf("%d\t",pr->AllTime);

printf("%d\t",pr->CPUTime);

printf("\n");

}

void Check() // 建立进程查看函数

{

PCB* pr;

printf("\n **** 当前正在运行的进程是:\n"); //显示当前运行进程 

OutPut(p);

pr=ready;

printf("\n ****当前就绪队列状态为:\n"); //显示就绪队列状态

while(pr!=NULL)

{

OutPut(pr);

pr=pr->Next;

}

}

void Destroy() //建立进程撤消函数(进程运行结束,撤消进程)

{

printf("\n 进程 [%d] 已完成.\n",p->ID);

free(p);

}

void Running() // 建立进程就绪函数(进程运行时间到,置就绪状态

{

p->CPUTime++;

p->State=Run;

if(p->CPUTime==p->AllTime)

Destroy(); //调用Destroy函数

else

{

(p->Priority)--;

p->State=Ready;

Sort(); //调用sort函数

}

}

void 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;

Check();

Running();

printf("\n 按任一键继续......");

ch=getchar();

}

printf("\n\n 进程已经完成.\n");

ch=getchar();

}

在老师代码中遇到的问题：

问题1：类型错误，定义进程状态的类型错误

解决：所以将STATE State;改为char state

问题2：队列指针错误类错误

解决方案：因为直接用gcc编译的代码，无法直接将pcb认为成一个类，所以将pcb* Next改为struct pcb* Next

问题3:因为直接用gcc编译的代码，无法直接将pcb认为成一个类,所以后面输入input函数的动态生成内存空间（p=(struct PCB *)malloc(sizeof(PCB));）会发生错误

解决方案：查阅很多资料后，发现只需要定义一下标识符的别名，然后进行使用就好，typedef struct是定义一个标识符及关键字的别名

所以将

struct PCB{

int ID; //进程名

int Priority; //优先数

int Time; //到达时间

int AllTime; //进程还需要运行时间

int CPUTime; //已用CPU时间

int StartBlock; //进程的进入阻塞时间

int StartTime; //进程的等待阻塞时间

STATE State; //进程状态

PCB* Next; //队列指针

}*ready=NULL,*p;

改为：

struct pcb{

int ID; //进程名

int Priority; //优先数

int Time; //到达时间

int AllTime; //进程还需要运行时间

int CPUTime; //已用CPU时间

int StartBlock; //进程的进入阻塞时间

int StartTime; //进程的等待阻塞时间

char State; //进程状态

struct pcb* Next; //队列指针

}*ready=NULL,*p;

typedef struct pcb PCB;

完善可用成功运行的代码：

#include<stdio.h>

#include<stdlib.h>

enum STATE{Ready=1,Run,Block,Finish };

struct pcb{

int ID; //进程名

int Priority; //优先数

int Time; //到达时间

int AllTime; //进程还需要运行时间

int CPUTime; //已用CPU时间

int StartBlock; //进程的进入阻塞时间

int StartTime; //进程的等待阻塞时间

char State; //进程状态

struct pcb* Next; //队列指针

}*ready=NULL,*p;

typedef struct pcb PCB;

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 请输入进程数量:");

scanf("%d",&num);

for(i=0;i<num;i++)

{

p=(struct PCB *)malloc(sizeof(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;

p->StartBlock=0;

p->StartTime=0;

p->State=Ready;

p->Next=NULL;

printf("\n");

Sort(); /* 调用sort函数*/

}

}

int Length()

{

int l=0;

     PCB* pr=ready;

while(pr!=NULL)

{

l++;

pr=pr->Next;

}

return(l);

}

void OutPut(PCB * pr) //显示当前进程

{

printf("\n ID \t state \t Priority \t ALLTime \t CPUTime \n");

printf("%d\t",pr->ID);

printf("%d\t",pr->State);

printf("%d\t",pr->Priority);

printf("%d\t",pr->AllTime);

printf("%d\t",pr->CPUTime);

printf("\n");

}

void Check() // 建立进程查看函数

{

PCB* pr;

printf("\n **** 当前正在运行的进程是:\n"); //显示当前运行进程

OutPut(p);

pr=ready;

printf("\n ****当前就绪队列状态为:\n"); //显示就绪队列状态

while(pr!=NULL)

{

OutPut(pr);

pr=pr->Next;

}

}

void Destroy() //建立进程撤消函数(进程运行结束,撤消进程)

{

printf("\n 进程 [%d] 已完成.\n",p->ID);

free(p);

}

void Running() // 建立进程就绪函数(进程运行时间到,置就绪状态

{

p->CPUTime++;

p->State=Run;

if(p->CPUTime==p->AllTime)

Destroy(); //调用Destroy函数

else

{

(p->Priority)--;

p->State=Ready;

Sort(); //调用sort函数

}

}

void 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;

Check();

Running();

printf("\n 按任一键继续......");

ch=getchar();

}

printf("\n\n 进程已经完成.\n");

ch=getchar();

}