OS课设之CPU调度算法的模拟实现文档格式.docx
- 文档编号:705083
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:23
- 大小:39.57KB
OS课设之CPU调度算法的模拟实现文档格式.docx
《OS课设之CPU调度算法的模拟实现文档格式.docx》由会员分享,可在线阅读,更多相关《OS课设之CPU调度算法的模拟实现文档格式.docx(23页珍藏版)》请在冰点文库上搜索。
在就绪队列中等待所花费时间之和
平均等待时间:
即等待时间的算数平均值
响应时间:
从提交请求到产生第一响应的时间。
需要使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
如果按照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,但是数字大小与优先级的高低没有定论。
(假设数字越小优先级越高)
优先级
10
1
2
4
P4
5
P5
画出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时间片)
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策略
对长进程的偏向。
6
8
7
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调度有时称为最短剩余时间优先调度。
这种策略下调度器总是选择预期剩余时间最短的进程。
是抢占策略。
案例分析:
到达时间
9
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<
stdio.h>
#include<
stdlib.h>
//进程剩余执行时间
//进程到达时间
//进入就绪队列的时间
//进入执行队列的时间
//进程执行结束的时间
//进程编号
//定义进程模块
time.h>
typedefstruct{
intremain_time;
intarrive_time;
intTp;
intTc;
intTo;
intnumber;
}Process_Block;
typedefstruct_Queue{
Process_BlockPB;
struct_Queue*next;
}_Block,*Process;
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;
}/*插入队列操作*/
ProcessDeQueue(Process_QueuePQ){
if(IsEmpty(PQ))
returnNULL;
Processtemp=PQ.head->
next;
next=temp->
if(PQ.end->
next==temp)
returntemp;
}/*出列操作*/
ProcessShortestProcess(Process_QueuePQ){
if(IsEmpty(PQ)){
//如果队列为空,返回
if(!
Run_Now)
returnRun_Now;
}
Processtemp,shortest,prev;
intmin_time;
if(Run_Now){
//如果当前有进程正在执行,
shortest=Run_Now;
//那么最短进程初始化为当前正在执行的进程,
min_time=Run_Now->
PB.remain_time;
else{//如果当前没有进程执行,
shortest=PQ.head->
//则最短进程初始化为队列中第一个进程min_time=PQ.head->
temp=PQ.head;
prev=temp;
while(temp->
next){
if(temp->
PB.remain_time<
min_time){//如果当前进程的剩余时间比min_time短,shortest=temp->
//则保存当前进程,min_time=shortest->
//及其前驱
}temp=temp->
if(shortest==PQ.end->
next)//如果最短剩余时间进程是队列中最后一个进程,
next=prev;
//则需要修改尾指针指向其前驱
prev->
next=shortest->
//修改指针将最短剩余时间进程插入到队头
returnshortest;
}/*调度最短剩余时间的进程至队头*/voidRun(){
Run_Now->
PB.remain_time--;
//某一时间运行它的剩余时间减
return;
}/*运行函数*/voidWait(){return;
}intsum(intarray[],intn){
inti,sum=0;
for(i=0;
i<
n;
i++)sum+=array[i];
returnsum;
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));
N;
i++){P[i]=(Process)malloc(sizeof(_Block));
P[i]->
PB.number=i+1;
P[i]->
wt[i]=0;
circle_t[i]=0;
printf(”输入第%个进程的到达时间及剩余执行时间:
i+1);
%d%d"
PB.arrive_time,&
PB.remain_time);
i++)
Total_Time+=P[i]->
printf("
\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_time){
temp=P[i];
P[i]=Run_Now;
Run_Now=temp;
//则调度它至运行队列中,
PB.Tp=t;
PB.Tc=t;
wt[Run_Now->
PB.number-1]+=Run_Now->
PB.Tc-Run_Now->
PB.Tp;
printf("
Run_Now->
PB.number);
EnQueue(PQ,P[i]);
//并将当前运行进程重新插入队列中
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_No为NULL
Run_Now=ShortestProcess(PQ)//从就绪队列中调出最短剩余时间进程至队头,if(!
Run_Now){//如果队列为空,转为等待状态if(IsEmpty(PQ)&
&
k>
=N)break;
Wait();
continue;
}else{
wt[Run_Now->
}else{//如果当前运行进程为空,那么
PB.arrive_time){//如果正好这时有进程入队
Run_Now=DeQueue(PQ);
则直接被调入运行队列中
平均等待时间是:
\n%f\n"
((float)sum(wt,N))/N);
平均周转时间是:
((float)sum(circle_t,N))/N);
//////////////////////////////////////////////////////
#include<
iostream>
string>
usingnamespacestd;
classProcess
{
public:
stringProcessName;
//进程名字
intTime;
//进程需要时间
intleval;
//进程优先级intLeftTime;
//进程运行一段时间后还需要的时间};
voidCopy(Processproc1,Processproc2);
//把proc2赋值给proc1voidSort(Proce
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- OS CPU 调度 算法 模拟 实现