操作系统进程调度.docx
《操作系统进程调度.docx》由会员分享,可在线阅读,更多相关《操作系统进程调度.docx(16页珍藏版)》请在冰点文库上搜索。
操作系统进程调度
淮海工学院计算机工程学院
实验报告书
课程名:
《操作系统原理》
题目:
进程调度
班级:
软件111
学号:
2011122578
姓名:
梁元龙
一、实验目的
进程是操作系统最重要的概念之一,进程调度是操作系统内核的重要功能,本实验要求用C语言编写一个进程调度模拟程序,使用优先级或时间片轮转法实现进程调度。
本实验可加深对进程调度算法的理解。
实验环境
TurboC2.0/3.0或VC++6.0
实验学时
4学时,必做实验。
二、实验内容
1、设计有5个进程并发执行的模拟调度程序,每个程序由一个PCB表示。
2、模拟调度程序可任选两种调度算法之一实现。
3、程序执行中应能在屏幕上显示出各进程的状态变化,以便于观察调度的整个过程。
3、实验说明
1、优先级算法说明
(1)PCB的结构:
Id
Span
Used
Need
Satus
Next
优先级算法中,设PCB的结构如右图所示,其中各数据项的含义如下:
Id:
进程标识符号,取值1—5。
Prior:
优先级,随机产生,范围1—5。
Used:
目前已占用的CPU时间数,初值为0;当该进程被调用执行时,
每执行一个时间片,Used加1。
Need:
进程尚需的CPU时间数,初值表示该进程需要运行的总时间,取值范围为5—10。
并随机产生,每运行一个时间片need减1;need为0则进程结束。
Status:
进程状态R(运行),J(就绪),F(完成);初始时都处于就绪状态。
Next:
指向就绪队列中下一个进程的PCB的指针。
(2)初始状态及就绪队列组织:
5个进程初始都处于就绪状态,进程标识1—5,used初值都为0。
各进程的优先级随机产生,范围1—5。
处于就绪状态的进程,用队列加以组织,队列按优先级由高到低依次排列,队首指针设为head,队尾指针设为tail。
(3)调度原则以及运行时间的处理:
正在执行的进程每执行一个时间片,其优先级减1(允许优先级为负)。
进程调度将在以下情况发生:
当正在运行的程序其优先级小于就绪队列队首进程的优先级时。
程序中进程的运行时间以逻辑时间片为单位。
2、时间片轮转算法说明
(1)PCB的结构(如下图所示):
轮转法中,设PCB的结构如右图所示,其中各数据项的含义如下:
Id
Span
Used
Need
Satus
Next
Id:
进程标识符号,取值1—5。
Span:
在某一轮中,分配给先运行进程的时间片数,取值1—3。
Used:
现运行进程在本轮执行过程已用的时间片数。
Need:
进程尚需的CPU时间数,初值表示该进程需要运行的总时间,
取值范围5—10。
并随机产生,每运行一个时间片need减1;
need为0则进程结束。
Status:
进程状态R(运行),J(就绪),F(完成);初始时所有进程处于就绪状态。
Next:
指向就绪队列中下一个进程的PCB的指针。
(2)初始状态及就绪队列组织:
Span、Used在每轮开始时赋初值,Used初值值为0,Span初值要求随机产生。
(3)调度原则:
当一个进程被调度程序执行时,每经过一个时间片,Need减1,Used加1,如果Need为0,表示该进程结束,如果Need不为0,并且Used小于本轮Span值,则该进程可继续运行,若Need不为0,且Used等于Span值,则该进程本轮运行时间已到,应调度下一个队首进程运行。
4、实验步骤
1、理解本实验中关于两种调度算法的说明。
2、根据调度算法的说明,画出相应的程序流程图。
3、按照程序流程图,用C语言编程并实现。
五、分析与思考
1、逻辑时间片该如何实现?
系统将所有的就绪进程按先来先服务算法的原则,排成一个队列,每次调度时,系统把处理机分配给队列首进程,并让其执行一个时间片。
当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序根据这个请求停止该进程的运行,将它送到就绪队列的末尾,再把处理机分给就绪队列中新的队首进程,同时让它也执行一个时间片。
2、如果不使用指针操作,是否也可以使用数组实现进程就绪队列的组织?
可以。
六、测试数据与实验结果
采用先来先服务调度算法的进程调度流程图如图
(1)
图
(1)采用先来先服务调度算法的进程调度流程图
代码:
#include
#include
#include
#definegetpch(type)(type*)malloc(sizeof(type))
#defineNULL0
#defineTIME2//时间片长度
typedefstructpcb{//进程管理块
charname[10];//进程名字
charstate;//进程状态
intqueue;//进程所在的队列
intntime;//进程需要运行的时间
intrtime;//进程已经运行的时间
intetime;//进程在本队列可运行的时间片
structpcb*link;
}PCB;
PCB*ready=NULL,*pinsert=NULL,*pfend=NULL,*p=NULL;//就绪队列,进程插入位置的变量
intgeti()//使用户仅能输入整数
{
charch;
inti=0;
fflush(stdin);
ch=getchar();
while(ch=='\n'){
printf("\tf输入不能为空..请重新输入\n");
fflush(stdin);
ch=getchar();
}
while(ch!
='\n'){
if(ch>'9'||ch<'0'){
printf("\t输入有误!
!
输入只能为正整数,请重新输入...\n");
fflush(stdin);
i=0;
ch=getchar();
}else{
i=i*10+(ch-'0');
ch=getchar();
}
}
returni;
}
voidfindpos()//更新状态量
{
PCB*ps=pfend;
if(!
ps||!
ps->link||(ps->link->queue-ps->queue)>1)
pinsert=ps;
else{
while(ps->link&&ps->link->queue!
=(pfend->queue+2))
ps=ps->link;
pinsert=ps;
}
}
voidinsert()//插入进程
{
if(!
ready){
ready=p;
pfend=p;
pinsert=p;
}elseif(ready->queue==1){//第一队列存在
p->link=pfend->link;
pfend->link=p;
pfend=p;
findpos();
}
else{
p->link=ready;
ready=p;
findpos();
}
}
voidinput()/*建立进程控制块函数*/
{
inti,num;
printf("\n请输入进程的个数?
");
num=geti();
for(i=0;i{
printf("\n进程号No.%d:
\n",i+1);
p=getpch(PCB);
printf("\n输入进程名:
");
scanf("%s",p->name);
printf("\n输入进程运行时间:
");
p->ntime=geti();
printf("\n");
p->rtime=0;
p->state='w';
p->queue=1;
p->etime=TIME;
p->link=NULL;
insert();/*调用insert函数*/
}
}
voiddisp(PCB*pr)/*建立进程现实函数,用于显示当前进程*/
{
printf("\nname\tstate\tqueue\tntime\trtime\t在队列可停留时间\t\n");
printf("|%s\t",pr->name);
printf("|%c\t",pr->state);
printf("|%d\t",pr->queue);
printf("|%d\t",pr->ntime);
printf("|%d\t",pr->rtime);
printf("|%d\t",pr->etime);
printf("\n");
}
voidcheck()/*建立进程查看函数*/
{
PCB*pr;
printf("\n****当前正在运行的进程是:
%s",ready->name);/*显示当前运行的进程*/
disp(ready);
pr=ready->link;
printf("\n****当前就绪队列状态为:
\n");/*显示就绪队列状态*/
while(pr!
=NULL)
{
disp(pr);
pr=pr->link;
}
}
voidsort()//调整进程队列
{
if(!
ready->link||ready->queuelink->queue)return;
p=ready->link;
ready->link=pinsert->link;
pinsert->link=ready;
pinsert=ready;
ready=p;
if(ready&&ready->queue==pinsert->queue){
findpos();
}
}
voidaddnew()//添加新的进程
{
if(ready->queue!
=1){
(ready->queue)++;
ready->etime*=2;
ready->state='w';
sort();/*调用sort函数*/
input();
}
else{
input();
}
}
voiddestroy()/*建立进程撤销函数(进程运行结束,撤销进程)*/
{
printf("\n进程[%s]已完成.\n",ready->name);
p=ready;
ready=ready->link;
free(p);
if(ready&&ready->queue==pinsert->queue)
findpos();
}
voidrunning()/*建立进程就绪函数(进程运行时间到,置就绪状态)*/
{
(ready->rtime)++;
ready->etime--;
if(ready->rtime==ready->ntime){
destroy();
return;
}elseif(ready->etime==0){
inttime=2;
(ready->queue)++;
for(inti=2;i!
=ready->queue;++i)
time*=2;
ready->etime=time;
ready->state='w';
sort();/*调用sort函数*/
}
}
voidmain()
{
charch;
input();
while(ready!
=NULL)
{
printf("\nTheexecutename:
%s\n",ready->name);
ready->state='R';
check();
running();
printf("\n按i键添加新进程....按其他任意键继续运行...");
fflush(stdin);
ch=getchar();
if(ch=='i'||ch=='I')
addnew();
}
printf("\n\n进程已经完成\n");
getchar();
}
测试数据与结果
1.初始化队列如图(3)
图(3)初始化队列
2.输入所有进程后的进程信息如下如图(4)
图(4)进程信息
3.按除i键以外的任意键继续运行进程如图(5)
图(5)继续运行
4.继续运行进程如图(6)
图(6)继续运行
5.运行若干次后的状态如图(7)
图(7)运行若干次后的状态
6.添加新的进程如图(8)
图(8)添加新进程
七、实验心得与体会
通过这次实验,知道了,.界面设计应该在编写之前确定,因为本程序是用来模拟一个调度算法,需要不断地刷新显示结果,其清晰性很重要,界面不能很潦草,固然需要一开始就设计好。
而不是作为一个中间环节在程序中不断调试。
关键算法的编写。
通常在编写时都是在IDE下直接写代码,如果有问题就进行调试,直到正确通过。
但是有的关键算法稍微有点复杂,在运行出错时候多次调试后仍然不能正确,此时静下心来,在纸上画一下算法流程,以及数据结构图示,并将代码写到纸上修改,实践证明,如此方法效率更高。
用C语言编写了一个进程调度模拟程序,使用优先级算法实现了进程调度。
通过这次实验加深了对进程调度算法的理解。