实验一 进程管理 昆工版

昆明理工大学信息工程与自动化学院学生实验报告

（ 2013 — 2014 学年 第二学期 ）

课程名称：操作系统 开课实验室：信自楼444 2014 年3月25日 年级、专业、班 计科122班 学号 201210405204 姓名 邹华宇 成绩 实验项目名称 教师评语 一、实验目的

通过编写进程管理的算法，要求学生掌握整个进程管理的各个环节，进程的数据结构描述，进程的各种状态之间的转换，以及进程的调度算法。以加深对进程的概念及进程调度算法的理解，并且提高链表的应用能力，达到提高编程能力的目的。

二、实验原理及基本技术路线图（方框原理图）

用C语言或C++语言开发。需要定义PCB的数据结构，用链表的形式管理进程，采用多级反馈队列调度的算法模拟进程的控制。要求有创建、撤销、调度、阻塞、唤醒进程等功能。

进程的状态转换图：

进程管理 指导教师 杨云飞 教师签名： 年 月 日 调度选中 就绪 剥夺处理机 运行 结束 事件发生 等待事件 终止 等待 创建 创建 第 1 页

各原语句的功能说明：

进程创建原语：进程创建是调用创建原语来实现。创建原语扫描系统的PCB链表，在找到一定PCB链表之后，填入调用者提供的有关参数（这些参数包括：进程名、进程优先级P0、进程正文段起始地址d0、资源清单R0等），最后形成代表进程的PCB结构。

进程撤销（终止）：撤消原语首先检查PCB进程链或进程家族，寻找所要撤消的进程是否存在。如果找到了所要撤消的进程的PCB结构，则撤消原语释放该进程所占有的资源之后，把对应的PCB结构从进程链或进程家族中摘下并返回给PCB空队列。如果被撤消的进程有自己的子进程，则撤消原语先撤消其子进程的PCB结构并释放子进程所 占用的资源之后，再撤消当前进程的PCB结构和释放其资源。

阻塞原语：当发生引起阻塞的事件时，该原语被该进程自己调用来阻塞自己。阻塞原语在阻塞一个进程时，由于该进程正处于执行状态，故应先中断处理机和保存该进程的CPU现场。然后将被阻塞进程置“阻塞”状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行。

唤醒原语：当等待队列中的进程所等待的事件发生时，等待该事件的所有进程都将被唤醒。一个处于阻塞状态的进程不可能自己唤醒自己。唤醒一个进程有两种方法：一种是由系统进程唤醒。另一种是由事件发生进程唤醒。当由系统进程唤醒等待进程时，系统进程统一控制事件的发生并将“事件发生”这一消息通知等待进程。从而使得该进程因等待事件已发生而进入就绪队列。等待进程也可由事件发生进唤醒。由事件发生进程唤醒时，事件发生进程和被唤醒进

第 2 页

程之间是合作关系。因此，唤醒原语既可被系统进程调用，也可被事件发生进程调用。我们称调用唤醒原语的进程为唤醒进程。

多级反馈队列调度算法的描述：

多级队列调度算法也称多级反馈队列调度算法，它是时间片调度算法与优先数调度算法的结合。实行这种调度算法时，系统中将维持多个就绪队列，每个就绪队列具有不同的调度级别，可以获得不同长度的时间片。例如，系统维持N个就绪队列，第1级就绪队列中进程的调度级别最高，可获得的时间片最短，第N级就绪队列中进程的调度级别最低，可获得的时间片最长。

具体的调度方法是：创建一个新进程时，它的PCB将进入第1级就绪队列的末尾。对于在第1级到第N-1级队列中的进程，如果在分配给它的时间片内完成了全部工作，那么就撤离系统；如果在时间片没有用完时提出了输入/输出请求或要等待某事件发生，那么就进入相应的阻塞队列里等待。在所等待的事件出现时，仍回到原队列末尾，参与下一轮调度（也就是每个队列实行先来先服务调度算法）；如果用完了时间片还没有完成自己的工作，那么只能放弃对CPU的使用，降到低一级队列的末尾，参与那个队列的调度。对位于最后一个队列里的进程，实行时间片轮转调度算法。

整个系统最先调度1级就绪队列；只有在上一级就绪队列为空时，才去下一级队列调度。当比运行进程更高级别的队列中到达一个进程（可以肯定，在此之前比运行进程级别高的所有队列全为空）时，系统将立即停止当前运行进程的运行，让它回到自己队列的末尾，转去运行级别高的那个进程。

第 3 页

流程图：

进程调度 N 处理机空Y 从就绪队列取下一N Y 正确取得就绪进程 是否有更高优先级进程 Y Y 正确取得就绪进程 N 进程优先级减1 N 执行进程的时间片释放处理机放等待队列 N 时间片用完 Y 进程优先级减1 进程结束 Y 释放处理机放完成队列 N 处理资源请求 放入就绪队列让处理机 第 4 页

数据结构定义：

char name[20]; int supernumber; int round; int cputime; int needtime; char state; int count;

/*进程的名字*/ /*进程的优先级*/ /*分配CPU的时间片*/ /*CPU执行时间*/ /*进程执行所需要的时间*/

/*进程的状态，W—就绪态，R—执行态，F—完成态*/ /*记录执行的次数*/ /*链表指针*/

struct node *next;

主要变量的说明：

PCB *run=NULL,*finish=NULL; /*定义三个队列，就绪队列，执行队列和完成队列*/

ReadyQueue *Head = NULL; int num;

/*定义第一个就绪队列*/ /*进程个数*/ /*就绪队列个数*/

int ReadyNum; 函数的说明： void Output();

/*进程信息输出函数*/

/*将进程插入到完成队列尾部*/

/*创建就绪队列，规定优先

void InsertFinish(PCB *in);

void Insertsupernumber(ReadyQueue *in); 数越小，优先级越低*/

void supernumberCreate();

/*创建就绪队列输入函数*/

void GetFirst(ReadyQueue *queue); /*取得某一个就绪队列中的队头进程*/ void InsertLast(PCB *in,ReadyQueue *queue); /*将进程插入到就绪队列尾部*/ void ProcessCreate();

/*进程创建函数*/

第 5 页

void RoundRun(ReadyQueue *timechip); void MultiDispatch();

/*时间片轮转调度算法*/

/*多级调度算法，每次执行一个时间片*/

三、所用仪器、材料（设备名称、型号、规格等）。 计算机一台

四、实验方法、步骤 # include # include # include # include

typedef struct node {

char name[20];

/*进程的名字*/ /*进程的优先级*/ /*分配CPU的时间片*/ /*进程节点信息*/

int supernumber; int round;

int cputime; int needtime; char state;

/*CPU执行时间*/

/*进程执行所需要的时间*/

/*进程的状态，W——就绪态，R——执行态，F——

完成态*/

int count;

/*记录执行的次数*/

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

}PCB;

第 6 页

typedef struct Queue {

PCB *LinkPCB;

/*多级就绪队列节点信息*/

/*就绪队列中的进程队列指针*/ /*本就绪队列的优先级*/ /*本就绪队列所分配的时间片*/

int supernumber; int round;

struct Queue *next; /*指向下一个就绪队列的链表指针*/

}ReadyQueue;

PCB *run=NULL,*finish=NULL; 和完成队列*/

ReadyQueue *Head = NULL; int num;

/*定义第一个就绪队列*/

/*定义三个队列，就绪队列，执行队列

/*进程个数*/ /*就绪队列个数*/ /*进程信息输出函数*/

/*将进程插入到完成队列尾部*/

int ReadyNum; void Output();

void InsertFinish(PCB *in);

void Insertsupernumber(ReadyQueue *in);/*创建就绪队列，规定优先数越小，优先级越低*/

void supernumberCreate();

/*创建就绪队列输入函数*/

void GetFirst(ReadyQueue *queue); /*取得某一个就绪队列中的队头进程*/

void InsertLast(PCB *in,ReadyQueue *queue); 绪队列尾部*/

void ProcessCreate();

/*进程创建函数*/

/*将进程插入到就

void RoundRun(ReadyQueue *timechip);/*时间片轮转调度算法*/

第 7 页

void MultiDispatch();

void Output() {

/*多级调度算法，每次执行一个时间片*/

/*进程信息输出函数*/

ReadyQueue *print = Head; PCB *p;

printf(\进程名\\t优先级\\t轮数\\tcpu时间\\t需要时间\\t进程状态\\t

计数器\\n\

while(print) {

if(print ->LinkPCB != NULL) {

p=print ->LinkPCB; while(p) {

printf(\

p->round,p->cputime,p->needtime,p->state,p->count);

}

}

}

p = p->next;

print = print->next;

p = finish;

第 8 页

while(p!=NULL) {

printf(\

p->round,p->cputime,p->needtime,p->state,p->count);

printf(\

} p = run; while(p!=NULL) {

p = p->next;

p->round,p->cputime,p->needtime,p->state,p->count);

}

p = p->next;

}

void InsertFinish(PCB *in) {

/*将进程插入到完成队列尾部*/

PCB *fst; fst = finish; if(finish == NULL) {

in->next = finish; finish = in;

第 9 页

}

} else { }

while(fst->next != NULL) { }

in ->next = fst ->next; fst ->next = in;

fst = fst->next;

void Insertsupernumber(ReadyQueue *in) 优先数越小，优先级越低*/

{

/*创建就绪队列，规定

ReadyQueue *fst,*nxt; fst = nxt = Head; if(Head == NULL) { } else {

if(in ->supernumber >= fst ->supernumber)

第 10 页

/*如果没有队列，则为第一个元素*/

in->next = Head; Head = in;

/*查到合适的位置进行插入*/

/*比第一个还

要大，则插入到队头*/

{ } else {

while(fst->next != NULL)

/*移动指针查找第一个别它小

in->next = Head; Head = in;

的元素的位置进行插入*/

{ }

if(fst ->next == NULL)

/*已经搜索到队尾，则其优先级

nxt = fst; fst = fst->next;

数最小，将其插入到队尾即可*/

{ } else { }

第 11 页

in ->next = fst ->next; fst ->next = in;

/*插入到队列中*/

nxt = in; in ->next = fst;

}

}

}

void supernumberCreate() {

ReadyQueue *tmp; int i;

static int j=0;

/*创建就绪队列输入函数*/

printf(\输入就绪队列的个数：\\n\scanf(\

printf(\每个就绪队列的CPU时间片：(优先级和时间片成反比)\\n\for(i = 0;i

if((tmp = (ReadyQueue *)malloc(sizeof(ReadyQueue)))==NULL) { }

tmp->round=int(pow(2.0,(++j)));

/*输入此就绪队列中给每

perror(\exit(1);

个进程所分配的CPU时间片*/

printf(\

tmp ->supernumber = 50 - tmp->round;

/*设置其优先级，

时间片越高，其优先级越低*/

第 12 页

tmp ->LinkPCB = NULL; tmp ->next = NULL;

/*初始化其连接的进程队列为空*/

Insertsupernumber(tmp); /*按照优先级从高到低，建立多个

就绪队列*/

}

void GetFirst(ReadyQueue *queue) 头进程*/

{ }

void ProcessCreate() {

}

/*取得某一个就绪队列中的队

run = queue ->LinkPCB; if(queue ->LinkPCB != NULL) { }

run ->state = 'R';

queue ->LinkPCB = queue ->LinkPCB ->next; run ->next = NULL;

/*进程创建函数*/

PCB *tmp; int i;

static int j=1;

printf(\输入进程的个数：\\n\scanf(\

第 13 页

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

if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL) { }

printf(\输入%d进程名字：\\n\scanf(\getchar();

printf(\输入%d进程时间：\\n\ scanf(\tmp ->cputime = 0; tmp ->state ='W';

tmp ->supernumber = 50 - tmp->needtime;

/*设置其优先

/*吸收回车符号*/

perror(\exit(1);

级，需要的时间越多，优先级越低*/

tmp ->round = Head ->round; tmp ->count = 0; InsertLast(tmp,Head);

/*按照优先级从高到低，插入到就

绪队列*/

}

system(\}

/*将进程插入到就

void InsertLast(PCB *in,ReadyQueue *queue)

第 14 页

绪队列尾部*/

{ PCB *fst;

fst = queue->LinkPCB; if( queue->LinkPCB == NULL) { in->next = queue->LinkPCB; queue->LinkPCB = in;

} else { while(fst->next != NULL) { fst = fst->next; }

in ->next = fst ->next; fst ->next = in;

}

}

void RoundRun(ReadyQueue *timechip) { int flag = 1;

GetFirst(timechip);

第 15 页

/*时间片轮转调度算法*/

本文来源：https://www.bwwdw.com/article/kz7x.html