进程调度

实验一 ：单处理机系统的进程调度

1． 实验目的

（1）加深对进程概念的理解，明确进程和程序的区别。

（2）深入了解系统如何组织进程、创建进程。

（3）进一步认识如何实现处理机调度。

（4）验证用信号机制实现进程同步的方法。

2．实验预备内容

（1）进程的概念。

（2）进程的组织方式。

（3）进程的创建。

（4）进程的调度

3．实验环境

（1）一台运行Windows 20XP professional操作系统的计算机。

（2）选用turbo c、visual c++、Delphi、c++ builder或visual basic等任何一种语言。

4．实验时间：4个学时（课下准备2 个学时，实验课2个学时）。

5．实验内容

编写程序完成单处理机系统中的进程高度，要求选用先来先服务（FCFS）、短进程优先（SPF）、高响应比优先、时间片轮转调度算法。实验具体包括：首先确定进程控制块的内容，进程控制块的组成方式；然后完成进程创建原语和进程调试原诘；最后编写主函数对所做工作进行测试。

6．参考算法

/*进程调度算法，采用优先级和时间片轮换算法*/

#include

#include

#include

#include

#define M 2 //时间片为2

#define L 3 //每运行一次进程优先数降低L个单位

typedef struct node{

char name[10]; /*进程标识符*/

int prio; /*进程优先数*/

int round; /*进程时间轮转时间片*/

int cputime; /*进程占用CPU时间*/

int needtime; /*进程到完成还要的时间*/

int count; /*计数器*/

char state; /*进程的状态*/

struct node *next; /*链指针*/

}PCB; /*进程控制快PCB，用结构体说明*/

PCB *finish,*ready,*tail,*run; /*队列指针*/

int N; /*进程数*/

/*将就绪队列中的第一个进程投入运行*/

void firstin(){

run=ready; /*就绪队列头指针赋值给运行头指针*/

run->state='R'; /*进程状态变为运行态*/

ready=ready->next; /*就绪对列头指针后移到下一进程*/

}

/*标题输出函数*/

void prthead(char a){

cout<<\"***************************************************************** \";

if(a=='P'||a=='p') /*优先算法*/

cout<<\" name cputime needtime priority state \";

else /*轮转算法*/

cout<<\" name cputime needtime count round state \";

}

/*进程PCB输出*/

void prtpcb(char a,PCB *q){

if(a=='P'||a=='p') /*优先数法的输出*/

cout<name<cputime<needtime<prio

<state<else/*轮转法的输出*/

cout<name<cputime<needtime<count

<round<state<}

/*输出函数*/

void prt(char algo){

PCB *p;

prthead(algo); /*输出标题*/

if(run!=NULL) /*如果运行指针不空*/

prtpcb(algo,run); /*输出当前正在运行的PCB*/

p=ready; /*输出就绪队列PCB*/

while(p!=NULL){

prtpcb(algo,p);

p=p->next;

}

p=finish; /*输出完成队列的PCB*/

while(p!=NULL){

prtpcb(algo,p);

p=p->next;

}

cin.get(); /*压任意键继续*/

}

/*优先数的插入算法,将一Pcb结点按照优先级插入已知的就绪队列当中*/

void insert1(PCB *q){

PCB *p1,*s,*r;

int b;

s=q; /*待插入的PCB指针*/

p1=ready; /*就绪队列头指针*/

r=p1; /*r做p1的前驱指针*/

b=1;

while((p1!=NULL)&&b){ /*根据优先数确定插入位置*/

if(p1->prio>=s->prio){

r=p1;

p1=p1->next;

}

else

b=0;

}

if(r!=p1){ /*如果条件成立说明插入在r与p1之间*/

r->next=s;

s->next=p1;

}

else{

s->next=p1; /*否则插入在就绪队列的头*/

ready=s;

}

}

/*轮转法插入函数*/

void insert2(PCB *p2){

tail->next=p2; /*将新的PCB插入在当前就绪队列的尾*/

tail=p2;

p2->next=NULL;

}

/*优先数创建初始PCB信息*/

void create1(char alg){

PCB *p;

int i,time;

char na[10];

ready=NULL; /*就绪队列头指针*/

finish=NULL; /*完成队列头指针*/

run=NULL; /*运行队列指针*/

cout<<\"Enter name and time of process(the time of process is less than 50): \"; /*输入进程标识和所需时间创建PCB*/

for(i=1;i<=N;i++){

p=(PCB*)malloc(sizeof(PCB));

cin>>na;

cin>>time;

strcpy(p->name,na);

p->cputime=0;

p->needtime=time;

p->state='w';

p->prio=50-time;

if(ready!=NULL) /*就绪队列不空调用插入函数插入*/

insert1(p);

else{

p->next=ready; /*创建就绪队列的第一个PCB*/

ready=p;

}

}

cout<<\"******************************************************************** \";

cout<<\" output of priority: \";

prt(alg); /*输出进程PCB信息*/

run=ready; /*将就绪队列的第一个进程投入运行*/

ready=ready->next;

run->state='R'; /*修改运行的进程的状态*/

cin.ignore();

}

/*轮转法创建进程PCB*/

void create2(char alg){

PCB *p;

int i,time;

char na[10];

ready=NULL;

finish=NULL;

run=NULL;

cout<<\"Enter name and time of round process: \";

for(i=1;i<=N;i++){ /*动态创建N个PCB*/

p=(PCB*)malloc(sizeof(PCB));

cin>>na;

cin>>time;

strcpy(p->name,na);

p->cputime=0;

p->needtime=time;

p->count=0; /*计数器*/

p->state='w';

p->round=M; /*时间片*/

if(ready!=NULL) /*就绪队列不空则插在对尾*/

insert2(p);

else{ /*就绪队列为空则新结点可作为就绪队列的第一个结点*/

p->next=ready;

ready=p;

tail=p;

}

}

cout<<\"******************************************************************** \";

cout<<\" output of round \";

prt(alg); /*输出进程PCB信息*/

run=ready; /*将就绪队列的第一个进程投入运行*/

ready=ready->next;

run->state='R'; /*修改运行的进程的状态*/

cin.ignore();

}

/*优先数调度算法*/

void priority(char alg){

while(run!=NULL){ /*当运行队列不空时，有进程正在运行*/

run->cputime=run->cputime+1;

run->needtime=run->needtime-1;

run->prio=run->prio-L; /*每运行一次优先数降低L个单位*/

if(run->needtime==0){ /*如所需时间为0将其插入完成队列对首并运行下一个被选中的进程*/

run->next=finish;

finish=run;

run->state='F'; /*置状态为完成态*/

run=NULL; /*运行队列头指针为空*/

if(ready!=NULL) /*如就绪队列不空*/

firstin(); /*将就绪对列的第一个进程投入运行*/

}

else /*没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列*/

if((ready!=NULL)&&(run->prioprio)) {

run->state='W';

insert1(run);

firstin(); /*将就绪队列的第一个进程投入运行*/

}

prt(alg); /*输出进程PCB信息*/

}

}

/*时间片轮转法*/

void roundrun(char alg){

while(run!=NULL){

run->cputime=run->cputime+1;

run->needtime=run->needtime-1;

run->count=run->count+1;

if(run->needtime==0){ /*运行完将其变为完成态，插入完成队列*/

run->next=finish;

finish=run;

run->state='F';

run=NULL;

if(ready!=NULL)

firstin(); /*就绪对列不空，将第一个进程投入运行*/

}

else //没有运行完成

if(run->count==run->round){ /*如果时间片到*/

run->count=0; /*计数器置0*/

if(ready!=NULL){ /*如就绪队列不空将进程插入到就绪队列中等待轮转*/

run->state='W';

insert2(run);

firstin(); /*将就绪对列的第一个进程投入运行*/

}

}

prt(alg); /*输出进程信息*/

}

}

/*主函数*/

void main()

{

char algo; /*算法标记*/

// clrscr();

cout<<\"type the algorithm:P/R(priority/roundrobin): \";

cin>>algo; /*输入字符确定算法*/

cin.ignore();

cout<<\"Enter process number: \";

cin>>N; /*输入进程数*/

cin.ignore();

if(algo=='P'||algo=='p'){

create1(algo); /*优先数创建初始PCB信息*/

priority(algo);

}

else

if(algo=='R'||algo=='r'){

create2(algo); /*轮转法*/

roundrun(algo);

}

}

7．实验要求

在程序编制中，应有数据显示，最好采用图形界面显示。