处理机调度实验报告1.docx
《处理机调度实验报告1.docx》由会员分享，可在线阅读，更多相关《处理机调度实验报告1.docx（26页珍藏版）》请在冰点文库上搜索。
处理机调度实验报告1
深圳大学实验报告
课程名称：
操作系统
实验项目名称：
处理机调度
学院：
计算机与软件学院
专业：
软件工程
指导教师：
报告人：
学号：
班级：
实验时间：
2013年5月7日
实验报告提交时间：
2013年5月22日
教务处制
一、实验目的与要求：
实验目的:
模拟在单处理器多进程操作系统的CPU调度。
帮助学生掌握多种CPU调度算法的知识原理和运作机制。
本实验为模拟实验，不要求实现真正的进程创建与进程调度。
主要实现各种调度算法。
实验要求:
1、阅读理解例程，掌握例程的运作流程。
运行例程，理解先来先服务算法的调度原理和运行结果。
2、参考先来先服务算法，尝试实现其他四种调度算法：
短作业优先、高响应比、时间片轮转、多级反馈队列。
要求至少实现一种算法。
a）除了多级反馈队列，其他算法采用非抢占调度
b）短作业优先算法使用例题一数据或程序内置数据，要求运行结果给出调度顺序、完成时间、周转时间、带权周转时间
c）高响应比算法使用例题二的数据，要求运行结果给出调度顺序、完成时间、周转时间、带权周转时间
d）时间片轮转算法可以使用程序内置数据，要求运行结果给出每个时间片是被哪个进程使用，每个进程完成时，要修改状态并输出提示。
e）多级反馈队列算法使用例题三的数据，要求运行结果给出正确的进程调度顺序和过程描述。
二、方法、步骤：
（说明程序相关的算法原理或知识内容，程序设计的思路和方法，可以用流程图表述，程序主要数据结构的设计、主要函数之间的调用关系等）
先来先服务算法：
按到达时间先后，选择最先来的作业最先执行
实现思想：
对作业的到达时间按大小进行排序，然后按顺序执行
短作业优先算法：
在后备队列中，选择服务时间最短的作业最先执行
实现思想：
对作业按到达时间排序，接着对到达的作业，即后备队列中的作业按服务时间排序，取服务时间最小的作业最先执行
高响应比算法：
对作业的优先权（响应时间/要求服务时间）进行计算，对优先权最高的最先执行
实现实现：
计算后备队列中作业的优先权，并排序，优先权最高的最先执行
时间片轮转算法：
将所有就绪进程按先来先服务排成队列，把CPU分配给队首进程，进程只执行一个时间片，时间片用完后，将已使用时间片的进程送往就绪队列的末尾，分配处理机给就绪队列中下一进程
实现思想：
将作业按到达时间排序，在后备队列中选择第一个作业，把CPU分配给它，执行一个时间片，时间片用完后，将作业送往后备队列的末尾，把CPU分配给下一个作业，直到所有作业完成
多级反馈队列调度算法：
设置多个就绪队列，各个队列优先级逐个降低，各个队列时间片逐个增加，优先级越高的队列执行时间片就越短，一般时间片按倍增规则，每个新进程首先进入第一个队列，遵循FCFS，在当前队列的时间片内，进程若能完成，退出，进程若未完成，降级到第二个队列，同样遵循FCFS依次类推，若在第二个队列的时间片内仍未完成，再降级到第三个队列……
实现思想：
设置多个就绪队列，各个队列优先级逐个降低，各个队列时间片逐个增加，优先级越高的队列执行时间片就越短，一般时间片按倍增规则，例如，第二队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍，整合了时间片、FCFS、优先级三种机制。
三．实验过程及内容：
（对程序代码进行说明和分析，越详细越好，代码排版要整齐，可读性要高）
#include"stdio.h"
#include
//#include
#include
#include
//#defineNULL0
#definegetpch（type）（type*）malloc（sizeof（type））
typedefstructpcbPCB;
structpcb{//定义进程控制块PCB
intid;//标示符
charname[10];//名称
inttime_start;//到达时间
inttime_need;//服务时间
inttime_left;//剩余运行时间
inttime_used;//已使用时间
charstate;//进程状态
};
//****************系统函数
void_sleep（intn）
{
clock_tgoal;
goal=（clock_t）n*CLOCKS_PER_SEC+clock（）;
while（goal>clock（））;
}
char_keygo（）
{
charc;
printf（"按任意键继续……\n"）;
c=getchar（）;
returnc;
}
//******************用户函数
inttime_unit=2;
intnum=5;//实际进程数量
PCBpcbdata[10]={
//例程内置数据
{1000,"A",0,4,4,0,'R'},
{1001,"B",1,3,3,0,'R'},
{1002,"C",2,5,5,0,'R'},
{1003,"D",3,2,2,0,'R'},
{1004,"E",4,4,4,0,'R'},
};
intnum1=4;
PCBpcbdata1[10]={
//例题一数据
{1000,"Job1",1,9,9,0,'R'},
{1001,"Job2",1,16,16,0,'R'},
{1002,"Job3",1,3,3,0,'R'},
{1003,"Job4",1,11,11,0,'R'},
};
intnum2=4;
PCBpcbdata2[10]={
//例题二数据
{1000,"P1",10,8,8,0,'R'},
{1001,"P2",12,12,12,0,'R'},
{1002,"P3",14,4,4,0,'R'},
{1003,"P4",16,6,6,0,'R'},
};
intnum3=4;
PCBpcbdata3[10]={
//例程三数据
{1000,"A",0,7,7,0,'R'},
{1001,"B",5,4,4,0,'R'},
{1002,"C",7,13,13,0,'R'},
{1003,"D",12,9,9,0,'R'},
};
intready[10];//就绪队列，存放进程在pcbdata中的位置
intorder[10];//记录排序使用哪个数值作为排序对象
voidintput（）
{
inti;
printf（"进程总数为：
"）;
scanf（"%d",&num）;
for（i=0;i{
pcbdata[i].id=1000+i;
printf（"输入第%d个进程名：
",i+1）;
scanf（"%s",&pcbdata[i].name）;
printf（"输入第%d个进程到达时间：
",i+1）;
scanf（"%d",&pcbdata[i].time_start）;
printf（"输入第%d个进程服务时间：
",i+1）;
scanf（"%d",&pcbdata[i].time_need）;
pcbdata[i].time_left=pcbdata[i].time_need;
printf（"\n"）;
pcbdata[i].time_used=0;
pcbdata[i].state='R';
}
}
//**************调度函数
voidFCFS（）
{
inti,j,temp;
doublek;
for（i=0;i{order[i]=pcbdata[i].time_start;
ready[i]=i;
}
for（i=0;ifor（j=i+1;j{
if（order[i]>order[j]）
{
temp=order[i];
order[i]=order[j];
order[j]=temp;
temp=ready[i];
ready[i]=ready[j];
ready[j]=temp;
}
}
printf（"---先来先服务算法调度：
非抢占，无时间片---\n"）;
temp=pcbdata[ready[0]].time_start;
for（i=0;i{
printf（"第%d个进程--%s,",i+1,pcbdata[ready[i]].name）;
printf（"本进程正在运行…………"）;
_sleep
（1）;
printf（"运行完毕\n"）;
temp+=pcbdata[ready[i]].time_need;
j=temp-pcbdata[ready[i]].time_start;
k=（float）j/pcbdata[ready[i]].time_need;
printf（"完成时间--%d,周转时间--%d,带权周转时间--%.1f\n",temp,j,k）;
}
printf（"------所有进程调度完毕-------------\n"）;
}
voidSJF（）
{
inti,j,temp,l,temp_num;
doublek;
inttime=0;
for（i=0;i{
order[i]=pcbdata1[i].time_start;
ready[i]=i;
}
for（i=0;ifor（j=i+1;j{
if（order[i]>order[j]）
{
temp=order[i];
order[i]=order[j];
order[j]=temp;
temp=ready[i];
ready[i]=ready[j];
ready[j]=temp;
}
}
printf（"---短作业算法调度：
非抢占，无时间片---\n"）;
intt_ready[10];//就绪队列，存放进程在pcbdata中的位置
intt_order[10];//记录排序使用哪个数值作为排序对象
for（i=0;i{
t_order[i]=pcbdata1[ready[i]].time_need;//服务时间作为排序对象
t_ready[i]=ready[i];
}
time=order[0];
for（l=0;l//判断到达的进程数，用temp_num存放
for（i=0;itemp_num=i+1;
//把到达的进程按服务时间大小进行排序
for（i=0;ifor（j=i+1;j{
if（t_order[i]>t_order[j]&&t_order[j]!
=0||t_order[i]==0）
{
temp=t_order[i];
t_order[i]=t_order[j];
t_order[j]=temp;
temp=t_ready[i];
t_ready[i]=t_ready[j];
t_ready[j]=temp;
}
}
printf（"第%d个进程--%s,",l+1,pcbdata1[t_ready[0]].name）;
printf（"正在运行…………"）;
_sleep
（1）;
printf（"运行完毕\n"）;
time+=pcbdata1[t_ready[0]].time_need;
j=time-pcbdata1[t_ready[0]].time_start;
k=（float）j/pcbdata1[t_ready[0]].time_need;
t_order[0]=0;
printf（"完成时间--%d,周转时间--%d,带权周转时间--%.1f\n",time,j,k）;
}
printf（"------所有进程调度完毕-------------\n"）;
}
voidHRF（）
{
inti,j,temp,l,temp_num;
doublek;
inttime=0;
for（i=0;i{
order[i]=pcbdata2[i].time_start;
ready[i]=i;
}
for（i=0;ifor（j=i+1;j{
if（order[i]>order[j]）
{
temp=order[i];
order[i]=order[j];
order[j]=temp;
temp=ready[i];
ready[i]=ready[j];
ready[j]=temp;
}
}
printf（"---高响应比算法调度：
非抢占，无时间片---\n"）;
intt_ready[10];
intt_order[10];
for（i=0;i{
t_order[i]=1;
t_ready[i]=ready[i];
}
time=order[0];
for（l=0;l//判断到达进程数
for（i=0;itemp_num=i+1;
for（i=0;i{
if（t_order[i]）
t_order[i]=（time-pcbdata2[t_ready[i]].time_start+pcbdata2[t_ready[i]].time_need）/pcbdata2[t_ready[i]].time_need;
}
for（i=0;ifor（j=i+1;j{
if（t_order[i]{
temp=t_order[i];
t_order[i]=t_order[j];
t_order[j]=temp;
temp=t_ready[i];
t_ready[i]=t_ready[j];
t_ready[j]=temp;
}
}
printf（"第%d个进程--%s,",l+1,pcbdata2[t_ready[0]].name）;
printf（"正在运行…………"）;
_sleep
（1）;
printf（"运行完毕\n"）;
time+=pcbdata2[t_ready[0]].time_need;
j=time-pcbdata2[t_ready[0]].time_start;
k=（float）j/pcbdata2[t_ready[0]].time_need;
t_order[0]=0;
printf（"完成时间--%d,周转时间--%d,带权周转时间--%.1f\n",time,j,k）;
}
printf（"------所有进程调度完毕-------------\n"）;
}
voidTimeslice（）
{
inti,j,temp,l,temp_num;
doublek;
inttime=0;
intdone=0;
for（i=0;i{
order[i]=pcbdata[i].time_start;
ready[i]=i;
}
for（i=0;ifor（j=i+1;j{
if（order[i]>order[j]）
{
temp=order[i];
order[i]=order[j];
order[j]=temp;
temp=ready[i];
ready[i]=ready[j];
ready[j]=temp;
}
}
printf（"---时间片轮转算法调度：
非抢占，时间片大小为2---\n"）;
intt_ready[10];
for（i=0;i{
t_ready[i]=ready[i];
}
time=order[0];
for（l=0;done//判断到达的进程数
for（i=0;itemp_num=i+1;
if（time!
=order[0]）{
//将已使用时间片的进程，即第一个移到队列末尾
for（i=1;itemp=t_ready[i];
t_ready[i]=t_ready[i-1];
t_ready[i-1]=temp;
}
}
if（pcbdata[t_ready[0]].state!
='F'）{
printf（"第%d个时间片被进程%s使用,",l+1,pcbdata[t_ready[0]].name）;
printf（"正在运行……\n"）;
_sleep
（1）;
printf（"时间片使用完，所需时间%d,",pcbdata[t_ready[0]].time_left）;
time+=2;
pcbdata[t_ready[0]].time_used+=2;
pcbdata[t_ready[0]].time_left-=2;
printf（"使用时间%d,还需时间%d,",2,pcbdata[t_ready[0]].time_left）;
//判断进程是否结束
if（pcbdata[t_ready[0]].time_left<=0）{
printf（"进程%s结束\n",pcbdata[t_ready[0]].name）;
done++;
pcbdata[t_ready[0]].state='F';
}
else
printf（"进程%s就绪\n",pcbdata[t_ready[0]].name）;
}
}
printf（"------所有进程调度完毕-------------\n"）;
}
voidMRLA（）
{
inti,j,temp,l,temp_num,temp_num2;
doublek;
inttime=0;//系统时间
intdone=0;//已完成的进程
intt_ready[10];
intqueue[10];//进程对应的队列
intqtime[10];//进程对应的时间片
for（i=0;i{
order[i]=pcbdata3[i].time_start;
ready[i]=i;
queue[i]=1;
qtime[i]=0;
}
for（i=0;ifor（j=i+1;j{
if（order[i]>order[j]）
{
temp=order[i];
order[i]=order[j];
order[j]=temp;
temp=ready[i];
ready[i]=ready[j];
ready[j]=temp;
}
}
printf（"---多级反馈算法调度：
抢占式，时间片大小为2---\n"）;
for（i=0;i{
t_ready[i]=ready[i];
}
time=order[0];
for（l=0;done//判断到达的进程数
for（i=0;itemp_num=i+1;
if（time!
=order[0]）{
for（i=0;ifor（j=1;jif（pcbdata3[t_ready[j-1]].state=='F'||（queue[j-1]>queue[j]&&pcbdata3[t_ready[j]].state!
='F'））{
temp=queue[j-1];
queue[j-1]=queue[j];
queue[j]=temp;
temp=t_ready[j-1];
t_ready[j-1]=t_ready[j];
t_ready[j]=temp;
temp=qtime[j-1];
qtime[j-1]=qtime[j];
qtime[j]=temp;
}
}
}
if（pcbdat
升级会员 