OS课设之CPU调度算法的模拟实现.docx
《OS课设之CPU调度算法的模拟实现.docx》由会员分享，可在线阅读，更多相关《OS课设之CPU调度算法的模拟实现.docx（23页珍藏版）》请在冰点文库上搜索。
OS课设之CPU调度算法的模拟实现
调度算法的模拟实现
一、设计目的
利用C++编写CPU调度算法，实现先来先服务调度算法FCFS、优先级调度算法PS、短作业优先调度算法SJF、时间片轮转调度算法RR的运行过程和实现的结果，针对模拟进程，利用编写的CPU调度算法对需要运行的进程进行调度。
进行算法评价，计算平均周转时间和平均等待时间。
二、设计要求
针对模拟进程，利用CPU调度算法进行调度，最后要进行算法评价，计算平均周转时间和平均等待时间，并且输出调度结果和输出算法评价指标。
调度所需的进程参数由输入产生（手工输入
或者随机数产生）。
三、设计说明？
CPU调度决策可在如下4种情况环境下发生：
（1）当一个进程从运行切换到等待状态（如：
I/O请求，或者调用wait等待一个子进程的终止）
（2）当一个进程从运行状态切换到就绪状态（如：
出现中断）
（3）当一个进程从等待状态切换到就绪状态（如：
I/O完成）
（4）当一个进程终止时
对于第1和4两种情况，没有选择而只有调度。
一个新进程（如果就绪队列中已有一个进程存在）必须被选择执行。
对于第2和第3两种情况，可以进行选择。
当调度只能发生在第1和4两种情况下时，称调度是非抢占的（nonpreemptive）或协作的
（cooperative）；否则，称调度方案为抢占的（preemptive）。
采用非抢占调度，一旦CPU分配给一个进程，那么该进程会一直使用CPU直到进程终止或切换到等待状态。
抢占调度对访问共享数据是有代价（如加锁）的，有可能产生错误，需要新的机制（如,同步）
来协调对共享数据的访问。
抢占对于操作系统内核的设计也有影响。
在处理系统调用时，内核可能忙于进程活动。
这些活动可能涉及要改变重要内核数据（如I/O队列）。
因为根据定义中断能随时发生，而且不能总是被内核所忽视，所以受中断影响的代码段必须加以保护以避免同时访问。
操作系统需要在任何时候都能
够接收中断，否则输入会丢失或输出会被改写。
为了这些代码段不被多个进程同时访问，在进入时就要禁止中断，而在退出时要重新允许中断。
调度准则
为了比较CPU调度算法所提出的准则：
CPU使用率:
需要使CPU尽可能忙
吞吐量:
指一个时间单元内所完成进程的数量
周转时间:
从进程提交到进程完成的时间段称为周转时间，周转时间是所有时间段之和，包括等待进入内存、在就绪队列中等待、在CPU上执行和I/O执行
平均周转时间:
即周转时间的算数平均值
等待时间:
在就绪队列中等待所花费时间之和
平均等待时间:
即等待时间的算数平均值
响应时间:
从提交请求到产生第一响应的时间。
需要使CPU使用率和吞吐量最大化，而使周转时间、等待时间和响应时间最小化。
绝大多数情况下需要优化平均值，有时需要优化最大值或最小值，而不是平均值
四、详细设计
4.1先到先服务调度（First-Come，First-Servedscheduling）
最简单的CPU调度算法是先到先服务算法（First-Come，First-Servedscheduling:
先请求CPU的进程先分配到CPUoFCFS策略可以用FIFO队列来容易实现。
当一个进程进入就绪队列，其PCB链接到队列的尾部。
当CPU空闲时，CPU分配给位于队列头的进程，接着运行进程从队列中删除。
FCFS策略的代码编写简单且容易理解，不过采用FCFS策略的平均等待时间通常比较长。
当进程CPU区间时间变化很大，平均等待时间会变化很大。
算法原理:
假设有n个进程分别在T1,?
Tn时刻到达系统，它们需要的服务时间分别为S1,?
Sn分别采用先来先服务FCFS调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
程序要求如下：
1）进程个数n；每个进程的到达时间T1,?
Tn和服务时间S1,?
Sn=
2）要求采用先来先服务FCFS调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间；
3）输出：
要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3:
进程B开始运行”等等；
4）输出：
要求输出计算出来的每个进程的周转时间，带权周转时间，所有进程的平均周转时间，带权平均周转时间。
实现简要过程：
1）变量初始化；
2）接收用户输入n，T1,?
Tn，S1,?
Sn；
3）按照选择算法进行进程调度，计算进程的完成时间、周转时间和带权周转时间；
4）按格式输出调度结果。
测试结果：
案例分析：
进程
区间时间
P1
24
P2
3
P3
3
如果按照P1P2P3顺序到达，Gantt图如下:
平均周转时间：
（24+27+30）£=27
如果按照P2P3P1顺序到达，
平均等待时间：
（0+3+6）£=3
平均周转时间：
（3+6+30）七=13
另外考虑在动态情况下的性能，假设有一个CPU约束进程和许多I/O约束进程，CPU约束进程会移回到就绪队列并被分配到CPU。
再次所有I/O进程会在就绪队列中等待CPU进程的完成。
由于所有其他进程都等待一个大进程释放CPU，这称之为护航效果（convoyeffect）。
与让较短进程最先执行相比，这样会导致CPU和设备使用率变的很低。
FCFS调度算法是非抢占的。
对于分时系统（每个用户需要定时的等待一定的CPU时间）是特别
麻烦。
允许一个进程保持CPU时间过长是个严重错误。
4.2优先级调度（priorityschedulingalgorithm）
算法：
每个进程有一个进程控制块（PCB）表示。
进程控制块可以包含如下信息：
进程名、优先数、到达时间、需要运行时间、已用CPU时间、
进程状态等等。
进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。
进
程的到达时间为进程输入的时间。
进程的运行时间以时间片为单位进行计算。
每个进程的状态可以
是就绪W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。
就绪进程获得CPU后都只能运行一个时间片。
用已占用CPU时间加1来表示。
如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还
未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。
每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。
重复以上过程，直到所要进程都完成为止。
SJF算法可作为通用的优先级调度算法的一个特例。
每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU。
具有相同优先级的进程按FCFS顺序调度。
SJF，其优先级（P）为下一个CPU区间的倒数。
CPU区间越大，则优先级越小，反之亦然。
优先级通常是固定区间的数字，如0〜7,但是数字大小与优先级的高低没有定论。
测试结果：
案例分析：
（假设数字越小优先级越高）
进程
区间时间
优先级
P1
10
3
P2
1
1
P3
2
4
P4
1
5
P5
5
2
画出Gantt图:
（0+1+6+16+18）弋=8.2
平均周转时间：
（1+6+16+18+19）吒=12
优先级可通过内部或外部方式来定义。
内部定义优先级使用一些测量数据以计算进程优先级。
外部优先级是通过操作系统之外的准则来定义，如进程重要性等。
优先级调度可以是抢占的或非抢占的。
优先级调度算法的一个重要问题是无限阻塞（indefiniteblocking）或饥饿（starvation）。
可以运行但缺乏CPU的进程可认为是阻塞的，它在等待CPU。
优先级调度算法会使某个有低优先级无穷等待CPU。
低优先级进程务求等待问题的解决之一是老化（aging）。
老化是一种技术，以逐渐增加在系统中等待很长时间的进程的优先级。
4.3时间片轮转调度算法（round-robin,RR）
专门为分时系统设计。
它类似于FCFS调度，但是增加了抢占以切换进程。
定义一个较小的时间单元，称为时间片（timequantum,ortimeslice）。
将就绪队列作为循环队列。
CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片段的CPU。
系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首
进程，并令其执行一个时间片。
时间片的大小从几ms到几百ms。
当执行的时间片用完时，由一
个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末
尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。
如果在时间
片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。
如果进程在时间片结束前阻塞或
结束，则CPU当即进行切换。
调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。
RR策略的平均等待时间通常较长
测试结果：
案例分析：
（使用4ms时间片）
进程
区间时间
P1
24
P2
3
P3
3
画出Gantt图:
P1
P2
P3
P1
P1
P1
P1
P1
0471********
平均等待时间：
［0+4+7+（10-4）］七=5.66平均周转时间：
（7+10+30）£=15.67
如果就绪，那么每个进程会得到1n的CPU时间，其长度不超过q时间单元。
每个进程必须等待CPU时间不会超过（n?
1）xq个时间单元，直到它的下一个时间片为止。
RR算法的性能很大程度上依赖于时间片的大小。
在极端情况下，如果时间片非常大，那么RR算
法与FCFS算法一样。
如果时间片很小，那么RR算法称为处理器共享，n个进程对于用户都有它自己的处理器，速度为真正处理器速度的1/n。
小的时间片会增加上下文切换的次数，因此，希望时间片比上下文切换时间长，事实上，绝大多数
现代操作系统，上下文切换的时间仅占时间片的一小部分。
周转时间也依赖于时间片的大小。
4.4最短作业优先调度（shortest-job-firstscheduling,SJF）
将每个进程与下一个CPU区间段相关联。
当CPU为空闲时，它会赋给具有最短CPU区间的进程。
如果两个进程具有同样长度，那么可以使用FCFS调度来处理。
注意，一个更为适当地表示是
最短下一个CPU区间的算法，这是因为调度检查进程的下一个CPU区间的长度，而不是其总长度。
?
这种策略是下一次选择所需处理时间最短的进程。
是非抢占策略，目的也是为减少FCFS策略
对长进程的偏向。
测试结果：
案例分析：
进程
区间时间
P1
6
P2
8
P3
7
P4
3
画出Gantt图:
P4
P1
P3
P2
0391624
SJF平均等待时间：
（0+3+9+16）詔=7
SJF平均周转时间：
（3+9+16+24）詔=13
FCFS平均等待时间：
（0+6+14+21）岂=10.25
FCFS平均周转时间：
（6+14+21+24）詔=16.25
SJF算法的平均等待时间最小。
SJF算法的真正困难是如何知道下一个CPU区间的长度。
对于批处理系统的长期（作业）调度，可以将用户提交作业时间所制定的进程时间极限作为长度。
SJF
调度经常用于长期调度。
它不能在短期CPU调度层次上加以实现。
我们可以预测下一个CPU区间。
认为下一个CPU区间的长度与以前的相似。
因此通过计算下一个CPU区间长度的近似值，能选择具有最短预测CPU
区间的进程来运行。
下一个CPU区间通常可预测为以前CPU去剪的测量长度的指数平均
（exponentialaverage）。
4.5最短剩余时间优先调度（shortest-remaining-time-firstscheduling）
SJF算法可能是抢占的或非抢占的。
抢占SJF算法可抢占当前运行的进程，而非抢占的SJF算法会允许当前的进程先完成其CPU区间。
抢占SJF调度有时称为最短剩余时间优先调度。
这种策略下调度器总是选择预期剩余时间最短的进程。
是抢占策略。
测试结果：
案例分析：
进程
到达时间
区间时间
P1
0
8
P2
1
4
P3
2
9
P4
3
5
画出Gantt图:
P1
P2
P4
P1
P3
015101726
平均等待时间：
［0+0+（5-3）+（17-2）］岂=6.5
平均周转时间：
［（17-0）+（5-1）+（26-2）+（10-3）］-4=13
非抢占的SJF平均等待时间：
［0+（8-1）+（12-3）+（17-2）］4=7.75
源代码
//最短剩余时间优先算法的实现
#include
#include
//进程剩余执行时间
//进程到达时间
//进入就绪队列的时间
//进入执行队列的时间
//进程执行结束的时间
//进程编号
//定义进程模块
#includetypedefstruct{
intremain_time;
intarrive_time;
intTp;
intTc;
intTo;
intnumber;
}Process_Block;typedefstruct_Queue{
Process_BlockPB;
struct_Queue*next;
}_Block,*Process;typedefstruct{
Processhead;
Processend;}Process_Queue;Process_QueuePQ;intt;ProcessRun_Now;
//定义一个进程模块队列中结点
//队列头指针
//队列尾指针
//进程队列
//定义一个全局队列变量
//全局时间
//当前正在运行的进程，作为全局变量
voidInitQueue（Process_QueuePQ）{
PQ.head->next=NULL;
PQ.end->next=PQ.head;
}/*初始化队列*/intIsEmpty（Process_QueuePQ）{if（PQ.end->next==PQ.head）
return1;//队列空的条件为头指针指向尾指针并且尾指针指向头指针
else
return0;
}/*判定队列是否为空队列*/voidEnQueue（Process_QueuePQ,ProcessP）{
Processtemp=（Process）malloc（sizeof（_Block））;temp=PQ.end;
temp->next->next=P;
PQ.end->next=P;
}/*插入队列操作*/
ProcessDeQueue（Process_QueuePQ）{
if（IsEmpty（PQ））
returnNULL;
Processtemp=PQ.head->next;
PQ.head->next=temp->next;
if（PQ.end->next==temp）
PQ.end->next=PQ.head;
returntemp;
}/*出列操作*/
ProcessShortestProcess（Process_QueuePQ）{
if（IsEmpty（PQ））{
//如果队列为空，返回
if（!
Run_Now）
returnNULL;
else
returnRun_Now;
}
Processtemp,shortest,prev;
intmin_time;
if（Run_Now）{
//如果当前有进程正在执行，
shortest=Run_Now;
//那么最短进程初始化为当前正在执行的进程，
min_time=Run_Now->PB.remain_time;
}
else{//如果当前没有进程执行，
shortest=PQ.head->next;//则最短进程初始化为队列中第一个进程min_time=PQ.head->next->PB.remain_time;
}
temp=PQ.head;
prev=temp;
while（temp->next）{
if（temp->next->PB.remain_timenext;//则保存当前进程，min_time=shortest->PB.remain_time;
prev=temp;//及其前驱
}temp=temp->next;
}
if（shortest==PQ.end->next）//如果最短剩余时间进程是队列中最后一个进程，
PQ.end->next=prev;//则需要修改尾指针指向其前驱
prev->next=shortest->next;//修改指针将最短剩余时间进程插入到队头
returnshortest;
}/*调度最短剩余时间的进程至队头*/voidRun（）{
Run_Now->PB.remain_time--;//某一时间运行它的剩余时间减
return;
}/*运行函数*/voidWait（）{return;}intsum（intarray[],intn）{
inti,sum=0;
for（i=0;ireturnsum;
}
intmain（）{
PQ.head=（Process）malloc（sizeof（_Block））;PQ.end=（Process）malloc（sizeof（_Block））;
Run_Now=（Process）malloc（sizeof（_Block））;
Run_Now=NULL;
InitQueue（PQ）;
inti,N,Total_Time=0;//Total_Time为所有进程的执行时间之和printf（"请输入计算机中的进程数目:
\n"）;
scanf（"%d",&N）;
Process*P,temp;
P=（Process*）malloc（N*sizeof（Process））;
int*wt,*circle_t;
wt=（int*）malloc（N*sizeof（int））;circle_t=（int*）malloc（N*sizeof（int））;
for（i=0;iPB.number=i+1;
P[i]->next=NULL;
wt[i]=0;circle_t[i]=0;
printf（”输入第％个进程的到达时间及剩余执行时间：
\n",i+1）;
scanf（"%d%d",&P[i]->PB.arrive_time,&P[i]->PB.remain_time）;
}
for（i=0;iTotal_Time+=P[i]->PB.remain_time;
printf（"\n进程按顺序运行依次为:
\n"）;
i=0;
intk=0;
for（t=0;;t++）{
if（Run_Now）{//如果当前有进程正在执行
Run（）;
if（t==P[i]->PB.arrive_time）{//如果当前时间正好有进程进入if（P[i]->PB.remain_timePB.remain_time）{
temp=P[i];
P[i]=Run_Now;
Run_Now=temp;//则调度它至运行队列中，
Run_Now->PB.Tp=t;
Run_Now->PB.Tc=t;wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;printf（"%d",Run_Now->PB.number）;
}
EnQueue（PQ,P[i]）;//并将当前运行进程重新插入队列中
P[i]->PB.Tp=t;
k++;
i=（i+1）>（N-1）（N-1）:
（i+1）;
}
if（Run_Now->PB.remain_time==0）{//如果当前进程运行结束，Run_Now->PB.To=t;//进程运行结束的时间circle_t[Run_Now->PB.number-1]+=t-Run_Now->PB.arrive_time;free（Run_Now）;//则将它所占资源释放掉，
Run_Now=NULL;//并修改Run_No为NULL
Run_Now=ShortestProcess（PQ）//从就绪队列中调出最短剩余时间进程至队头，if（!
Run_Now）{//如果队列为空，转为等待状态if（IsEmpty（PQ）&&k>=N）break;
Wait（）;
continue;
}else{
Run_Now->PB.Tc=t;
wt[Run_Now->PB.number-1]+=Run_Now->PB.Tc-Run_Now->PB.Tp;printf（"%d",Run_Now->PB.number）;
}
}
}else{//如果当前运行进程为空，那么
if（t==P[i]->PB.arrive_time）{//如果正好这时有进程入队
k++;
EnQueue（PQ,P[i]）;
Run_Now=DeQueue（PQ）;则直接被调入运行队列中
Run_Now->PB.Tp=t;
Run_Now->PB.Tc=t;
printf（"%d",Run_Now->PB.number）;
i=（i+1）>（N-1）（N-1）:
（i+1）;
}else{
Wait（）;
continue;
}
}
}
printf（"\n"）;
printf（"平均等待时间是:
\n%f\n",（（float）sum（wt,N））/N）;
printf（"平均周转时间是:
\n%f\n",（（float）sum（circle_t,N））/N）;
return0;
}
//////////////////////////////////////////////////////
#include
#includeusingnamespacestd;
classProcess
{
public:
stringProcessName;//进程名字
intTime;//进程需要时间
intleval;//进程优先级intLeftTime;//进程运行一段时间后还需要的时间};
voidCopy（Processproc1,Processproc2）;//把proc2赋值给proc1voidSort（Proce
升级会员 