操作系统进程调度.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语言编写了一个进程调度模拟程序，使用优先级算法实现了进程调度。
通过这次实验加深了对进程调度算法的理解。
升级会员 