处理机调度Word格式.docx
《处理机调度Word格式.docx》由会员分享,可在线阅读,更多相关《处理机调度Word格式.docx(14页珍藏版)》请在冰点文库上搜索。
2.2短作业优先2
2.3时间片轮转调度3
2.4最低松弛度优先3
3.设计方案3
4.核心代码实现4
4.1先来先服调度算法4
4.2短作业优先5
4.3时间片轮转调度6
4.4最低松弛度优先7
5.运行效果8
5.1先来先服调度算法8
5.2短作业优先8
5.3时间片轮转调度8
5.4最低松弛度优先9
6.心得体会9
1.设计目的
在多道程序设计系统中,内存中有多道程序运行,他们相互争夺处理机这一重要的资源。
处理机调度就是从就绪队列中,按照一定的算法选择一个进程并将处理机分配给它运行,以实现进程并发地执行。
一般情况下,当占用处理机的进程因为某种请求得不到满足而不得不放弃CPU进入等待状态时,或者当时间片到,系统不得不将CPU分配给就绪队列中另一进程的时候,都要引起处理机调度。
除此之外,进程正常结束、中断处理等也可能引起处理机的调度。
因此,处理机调度是操作系统核心的重要组成部分,它的主要功能如下:
(1)记住进程的状态,如进程名称、指令计数器、程序状态寄存器以及所有通用寄存器等现场信息,将这些信息记录在相应的进程控制块中。
(2)根据一定的算法,决定哪个进程能获得处理机,以及占用多长时间。
(3)收回处理机,即正在执行的进程因为时间片用完或因为某种原因不能再执行的时候,保存该进程的现场,并收回处理机。
处理机调度的功能中,很重要的一项就是根据一定算法,从就绪队列中选出一个进程占用CPU运行。
可见,算法是处理机调度的关键。
通过本次课程设计理解进程调度的概念,深入理解进程控制的功能、进程的创建与删除以及进程各个状态之间的转换过程,实现FCFS,短作业优先,时间片轮转,最低松弛度优先算法调度进程。
1、学会使用C++语言编写和调试一个简单的时间片轮转法进行CPU调度的程序。
2、加深了解有关进程控制块和进程队列的概念。
3、并体会时间片轮转算法的具体实现方法。
2.设计原理
2.1先来先服调度算法
这是最简单的处理机调度算法,其基本思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行。
先来先服务调度算法是一种不可抢占的算法,先进入就绪队列的进程,先分配处理机运行。
一旦一个进程占有了处理机,它就一直运行下去,直到该进程完成工作或者因为等待某事件发生而不能继续运行时才释放处理机。
从表面上看,FIFO算法对所有作业都是公平的,并且一个作业的等待时间是可能预先估计的。
但实际上这种算法是不利于小作业的,因为当一个大作业先进入就绪队列时,就会使其后的许多小作业等待很长的时间。
这对小作业来说,等待时间可能要远远超出它运行的时间。
先来先服算法简单,易于程序实现,但它性能较差,在实际运行的操作系统中,很少单独使用,它常常配合其他调度算法一起使用。
2.2短作业优先
短作业优先(SJF,ShortestJobFirst)又称为“短进程优先”SPN(ShortestProcessNext);
这是对FCFS算法的改进,其目标是减少平均周转时间。
对预计执行时间短的作业(进程)优先分派处理机。
通常后来的短作业不抢先正在执行的作业。
2.3时间片轮转调度
算法的基本思想是:
对就绪队列中的每一进程分配一个时间片,时间片的长度q一般从10ms-1100ms不等。
把就绪队列看成是一个环状结构,调度程序按时间片长度q轮流调度就绪队列中的每一进程,使每一进程都有机会获得相同长度的时间占用处理机运行。
时间片轮转调度算法在分时系统中,是一种既简单又有效的调度策略。
一个分时系统有许多终端。
终端用户在各自的终端设备上同时使用计算机。
如果某个终端用户的程序长时间地占用处理机,那么其他终端用户的请求就不能得到即时相应。
一般说来,终端用户提出请求后,能在几秒钟内得到响应也就感到满意了。
采用时间片轮转算法,可以使系统即时地相应各终端用户的请求。
时间片轮转调度算法的性能极大的依赖于时间片长度q的取值,如果时间片过大。
则RR算法就退化为FIFO算法了;
反之,如果时间片过小,那么,处理机在各进程之间频繁转接,处理机时间开销变得很大,而提供给用户程序的时间将大大减少。
2.4最低松弛度优先
最低松弛度优先(LLF)算法是根据任务紧急(或松弛)的程度,来确定任务的优先级。
任务的紧急程度愈高,为该任务所赋予的优先级就愈高,使之优先执行。
在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列,松弛度最低的任务排在队列最前面,被优先调度。
松弛度的计算方法如下:
任务的松弛度=必须完成的时间-其本身的运行时间-当前时间
其中其本身运行的时间指任务运行结束还需多少时间,如果任务已经运行了一部分,则:
任务松弛度=任务的处理时间-任务已经运行的时间–当前时间
3.设计方案
4.核心代码实现
4.1先来先服调度算法
voidFCFS()//先来先服务
{
PCBp;
intlen=0;
while(!
ppro.empty())
{
p=ppro.top();
ppro.pop();
len=p.Need_time;
while(Cpu_time<
p.Arrive_time)
{
runCPU();
}
cout<
<
"
***************"
<
p.name<
开始了***********"
endl<
endl;
for(inti=0;
i<
len;
++i)
p.Need_time--;
if(p.Need_time==0)
p.State='
F'
;
show(p);
结束了***********"
}
}
4.2短作业优先
voidSJF()
add();
PCBpnow;
spro.empty()||N>
0)
if(spro.empty())
Cpu_time++;
add();
continue;
pnow=spro.top();
spro.pop();
pnow.name<
while(pnow.Need_time)
pnow.Need_time--;
if(pnow.Need_time==0)
pnow.State='
show(pnow);
4.3时间片轮转调度
voidroundrobin()//时间片轮转算法函数
while((!
pro.empty())||(!
ppro.empty()))
if(pro.empty())
pnow=pro.front();
if(pnow.Arrive_time>
Cpu_time)
pro.pop();
pro.push(pnow);
pro.pop();
Time_piece;
break;
if(pnow.Need_time==0)
pnow.State='
cout<
pro.push(pnow);
4.4最低松弛度优先
voidLLF()
PCBptmp;
intlimit=0;
while(pro.size()>
1)
pnow=pro.top();
ptmp=pro.top();
limit=ptmp.Finish_time-ptmp.Need_time;
\t线程"
开始/继续"
if(pnow.Need_time<
=(limit-Cpu_time))
Cpu_time+=pnow.Need_time;
CPU时间:
"
Cpu_time<
结束"
else
pnow.Need_time-=(limit-Cpu_time);
Cpu_time+=(limit-Cpu_time);
暂停"
pnow.weight=pnow.Finish_time-pnow.Need_time-Cpu_time;
pro.top().weight=pnow.Finish_time-pnow.Need_time-Cpu_time;
pnow=pro.top();
cout<
Cpu_time+=pnow.Need_time;
5.运行效果
5.1先来先服调度算法
5.2短作业优先
5.3时间片轮转调度
5.4最低松弛度优先
6.心得体会
通过这次课程设计,我的收获颇丰。
课程设计之初我对时间片轮转法基本上没有什么深入的研究,只是通过课堂的讲解大致了解其思想。
经过这将近两周的学习后,我对时间片轮转算法的理解有了更进一步的提高,并通过自己设计程序,自己试验,自己调试对算法的内容更进一步的深刻认识。
在课程设计初期,我仍处于懵懂阶段,老师让我们去图书馆自行查阅资料。
在这期间,我不仅重新学习了时间片轮转算法的相关知识,还在图书馆找到一些别人书写的程序段,这对我了解程序大致框架起了很大的帮助。
等到自己真正编写程序时,又是困难重重。
很多以前所学的关于C++的知识被遗忘,我不得不又重新拾起书本学习,尽管如此,编写的程序还是错误百出,尤其体现在函数的调用方面,参数经常不匹配。
在调试的过程中曾经一度想放弃,但是看见其他同学积极思考,不怕困难的神情,又让我重新拥有了走下去的力量。
此外,我第一次为自己编写的程序建立前台界面,这对我来说是一个很大的挑战。
回顾这次课程设计,虽然一路坎坷,但是我仍然坚持到最后,对我来说收获最大的莫过于这份不怕艰难的精神。
这次的课程设计让我实现了从“老师帮着走”到现在“自己走”的这一过程,相信这种经历会在以后的毕业设计甚至在以后的工作岗位上都会受益匪浅。