操作系统-加深对进程概念和进程调度的过程,算法的理解

山东工商学院

实验(上机)报告

实验题目: 进程调度模拟程序

2014年4月20日

一. 实验目的

加深对进程概念和进程调度的过程/算法的理解 二. 实验内容

(1) 给出进程调度算法的描述(如基于动态优先级和时间片轮转调度算法的描述)

(2) 用C语言设计一个对n个并发进程进行调度的程序,每个进程由一个进程控制块PCB结构表示,该进程控制块应包含下述描述信息:进程标识ID,进程优先数priority(并规定优先数和优先权成正比),时间片数chip,进程已经占用CPU的时间cputime,进程还需要运行的时间alltime(当进程运行完毕时,其值为0),进程的状态state(为简化起见,设每个进程处于运行E(Executing),就绪R(Ready)和完成F(Finished)3中状态之一,并假设起始状态都是就绪状态R),以及进程队列指针next(用来将PCB排成队列)等,可按照调度算法的不同而增删.

(3) 调度程序应当包含两种不同的调度算法,运行时可以任选一种,以利于各种方法的分析和比较.

(4) 程序应能显示或打印各种进程状态和参数变化情况,便于观察.既要显示每个时间片内各进程的情况,并且指出运行进程就绪和阻塞队列中的内容

三. 实验步骤

(1) 算法描述

时间片轮转调度算法描述:

使用LENGTH(宏定义为100)个元素的PCB数组作为进程队列,使用一次所有进程状态输出作为一个时间片.从队列的队头开始,一个时间片改变一个进程信息(cputime++,alltime--,state由Ready转为Executing,最后转为Ready或者Finished),直到所有的进程状态全部为Finished(宏定义为F)

动态优先级调度算法描述:

使用LENGTH 个元素的PBC数组作为进程队列,使用一次所有进程的状态输出作为一个时间片,定义十个优先级,从1到10,10为最高优先级,定义了10个优先级队列,分别名为one , two , three , four , five , six , seven , eight , nine ,ten,队列长度为LENGTH.在进程信息输入到进程队列后,进行进程优先级排序,将相应优先级进程的id值存入相应优先级队列.在调度处理函数中,从ten优先级队列开始遍历,如果不空,则取优先级进程队列队首元素作为进程队列id,调度处理该id值的进程(priority-- , cputime++ , alltime-- ,state由Ready转为Executing,最后转为Ready或者Finished;将该进程id从原优先级队列移除,然后添加到低一优先级队列的队尾),同一进程队列的进程id,从队头开始调度,如果进程优先级全部将为1,则进行时间片轮转调度,直到所有进程状态为Finished(宏定义为F).

(2) 编译环境

在Linux下使用gcc进行编译调试

(3) 代码

#include

#define EXECUTING 69 #define READY 82 #define FINISHED 70 #define TRUE 1 #define FALSE 0 #define LENGTH 100

typedef struct {

int id; //进程ID int priority; //进程优先数 int chip; //需要的时间片数 int cputime; //进程已占用CPU的时间 int alltime; //进程还需要运行的时间 int state; //进程状态

//struct process *next; //Next 指针 }PCB;

PCB q_process[LENGTH]; int top=0; //指向队头 int last=0; //指向队尾 int flag=1;

//动态优先级调度算法使用的 int

one[LENGTH],two[LENGTH],three[LENGTH],four[LENGTH],five[LENGTH],six[LENGTH],seven[LENGTH],eight[LENGTH],nine[LENGTH],ten[LENGTH];

int

top_one,last_one,top_two,last_two,top_three,last_three,top_four,last_four;

int

top_five,last_five,top_six,last_six,top_seven,last_seven,top_eight,last_eight;

int top_nine,last_nine,top_ten,last_ten; int dy_time=0;

void time_round(); void dy_priority(); int if_empty_dy(); int if_empty_time();

void enter_last(int *topPoint,int *lastPoint,int id,int x[]);

void del_top(int *topPoint,int x[]); void deal_proc(int top_m);

/*时间片轮转调度算法*/ void time_round(int t){ int time=t; int i;

while(if_empty_time()){ for(i=0;iprintf(\" %d\ %d\\%d\\ %d\\\%d\ %c\\n\ss[j].priority,q_process[j].chip,q_process[j].cputime,q_process[j].alltime,q_process[j].state);

} q_process[i].cputime++; q_process[i].alltime--; if(q_process[i].alltime == 0){ q_process[i].state=FINISHED; } else{ q_process[i].state=READY; } } } }

printf(\"第 %d 个时间片:\\n\ int j;

for(j=0;jprintf(\" %d\ %d\\%d\\ %d\\\%d\ %c\\n\ss[j].priority,q_process[j].chip,q_process[j].cputime,q_process[j].alltime,q_process[j].state);

} }

/*如果队列为bu空，返回TRUE，否则返回FALSE*/ int if_empty_time(){ int i=0;

for(;ireturn FALSE; }

int if_empty_dy(){ int i;

for(i=0;ireturn FALSE; }

/*动态优先级调度算法*/

//10个优先级，从1到10，分别设10个数组队列，分别存储这些优先级进程id，

void print(int x[]){ int i;

for(i=0;ivoid del_top(int *topPoint,int x[]){ x[*topPoint]=0; (*topPoint)++; }

void enter_last(int *topPoint,int *lastPoint,int id,int x[]){ if(*lastPoint == LENGTH-1){ int flag,i,point; *topPoint =0; for(i=0;x[i] == 0;i++){ point=flag=i; }

if(!i){ printf(\"进程队列已满！\\n\"); return; } for(i=0;ix[*lastPoint]=id; (*lastPoint)++; }

void dy_priority(){ int i;

for(i=0;i1:enter_last(&top_one,&last_one,q_process[i].id,one);break;

case

2:enter_last(&top_two,&last_two,q_process[i].id,two);break;

case

3:enter_last(&top_three,&last_three,q_process[i].id,three);break;

case

4:enter_last(&top_four,&last_four,q_process[i].id,four);break;

case

5:enter_last(&top_five,&last_five,q_process[i].id,five);break;

case

6:enter_last(&top_six,&last_six,q_process[i].id,six);break;

case

7:enter_last(&top_seven,&last_seven,q_process[i].id,seven);break;

case

8:enter_last(&top_eight,&last_eight,q_process[i].id,eight);break;

case

9:enter_last(&top_nine,&last_nine,q_process[i].id,nine);break;

case

10:enter_last(&top_ten,&last_ten,q_process[i].id,ten);break;

default:printf(\"\\n进程优先级错误!\\n\");return; } }

while(if_empty_dy()){

if(top_ten != last_ten){//ten shifou wei kong

deal_proc(ten[top_ten]);

enter_last(&top_nine,&last_nine,q_process[ten[top_ten]].id,nine);

del_top(&top_ten,ten);

}else if(top_nine != last_nine){//nine shi fou wei kong deal_proc(nine[top_nine]);

enter_last(&top_eight,&last_eight,q_process[nine[top_nine]].id,eight);

del_top(&top_nine,nine);

}else if(top_eight != last_eight){//eight shi fou wei kong deal_proc(eight[top_eight]);

enter_last(&top_seven,&last_seven,q_process[eight[top_eight]].id,seven);

del_top(&top_eight,eight);

}else if(top_seven != last_seven){//seven shi fou wei kong deal_proc(seven[top_seven]);

enter_last(&top_six,&last_six,q_process[seven[top_seven]].id,six);

del_top(&top_seven,seven);

}else if(top_six != last_six){//six shi fou wei kong deal_proc(six[top_six]);

enter_last(&top_five,&last_five,q_process[six[top_six]].id,five);

del_top(&top_six,six);

}else if(top_five != last_five){//five shi fou wei kong deal_proc(five[top_five]);

enter_last(&top_four,&last_four,q_process[five[top_five]].id,four);

del_top(&top_five,five);

}else if(top_four != last_four){//four shi fou wei kong deal_proc(four[top_four]);

enter_last(&top_three,&last_three,q_process[four[top_four]].id,three);

del_top(&top_four,four);

}else if(top_three != last_three){//three shi fou wei kong deal_proc(three[top_three]);

enter_last(&top_two,&last_two,q_process[three[top_three]].id,two);

del_top(&top_three,three);

}else if(top_two != last_three){//two shi fou wei kong deal_proc(two[top_two]);

enter_last(&top_one,&last_one,q_process[two[top_two]].id,one);

del_top(&top_two,two);

}else if(top_one != last_one ){ flag=0;

time_round(dy_time); break; } } }

void deal_proc(int top_m){

if(q_process[top_m].state == READY){ printf(\"第 %d 个时间片:\\n\ q_process[top_m].state=EXECUTING; int j; for(j=0;jprintf(\" %d\ %d\\%d\\ %d\\\%d\ %c\\n\ss[j].priority,q_process[j].chip,q_process[j].cputime,q_process[j].alltime,q_process[j].state);

} q_process[top_m].cputime++; q_process[top_m].alltime--; q_process[top_m].priority--; if(q_process[top_m].alltime == 0){ q_process[top_m].state=FINISHED; } else{ q_process[top_m].state=READY; } }

return; }

int main(){

int p_id=0,i=0;

int p_priority=0,p_chip=0;

printf(\"输入进程信息(进程优先数，时间片数),以-1 -1结束输入\\n\");

while(TRUE){ scanf(\"%d%d\ if(p_priority < 0 || p_chip < 0){ break; }

q_process[i].id=p_id++; q_process[i].priority=p_priority; q_process[i].chip=p_chip; q_process[i].cputime=0; q_process[i].alltime=p_chip; q_process[i].state=READY; last++; i++; }

printf(\"选择调度算法（1.动态优先级调度算法 2.时间片轮转调度算法）：\\n\");

int choosed=0;

scanf(\"%d\

printf(\"进程ID 进程优先级 进程所需时间片 进程已占用CPU时间 还需要运行时间 进程状态\\n\");

if(choosed == 1){ printf(\"动态优先级调度算法：\\n\"); dy_priority(); if(flag){ int j; printf(\"第 %d 个时间片:\\n\ for(j=0;jprintf(\" %d\ %d\\%d\\ %d\\\%d\ %c\\n\ss[j].priority,q_process[j].chip,q_process[j].cputime,q_process[j].alltime,q_process[j].state);

} }

}else if(choosed == 2){ printf(\"时间片轮转调度算法\\n\"); time_round(0); }else{ printf(\"输入不合法，程序结束！\\n\"); }

return 0; }

(4) 程序运行截图

四. 存在的问题及解决方法

存在的问题:

1) 如何去模拟一个时间片 2) 队列的维护问题

3) 函数参数值传递并且改变的问题 4) 重复输出最终状态问题

解决方法:

(1) 使用一次所有进程状态的输出模拟一个时间片 (2) 设置全局变量,使用全局变量维护队列 (3) 函数参数传递时使用传递参数地址的方法 (4) 设置flag ,根据flag的值判断是否进行输出

五. 体会

通过进程调度模拟程序,再一次认识到了C语言的强大.在程序实现过程中,清楚地明白进程调度的过程很重要,有了相应的运行过程,才能合理地设计算法,然后实现算法.使用合理的数据结构,在算法实现时也是很重要的,它可以使算法实现变得更加容易,运行时效率更高!