操作系统处理机调度及常见的调度算法

  • Post author:
  • Post category:其他


一.处理机调度的层次:

1.高级调度:高级调度又称为作业调度或长程调度,其主要功能是根据某种算法,把外存上处于后备队列中的那些作业调入内存,也就是说,它的调度对象是作业。

2.中级调度:中级调度又称中程调度。引入中程调度的主要目的是为了提高内存利用率和系统吞吐量。中级调度实际上就是存储器管理中的对换功能。

3.低级调度:低级调度通常也称为进程调度或短程调度,它所调度的对象是进程(或内核级线程),进程调度是最基本的一种调度,在多道批处理,分时,实时三种类型的OS中,

都必须配置这级调度。

二.调度队列模型:

1.仅有进程调度的调度队列模型:


2.具有高级和低级调度的调度队列模型:


3.同时具有三级调度的调度队列模型:


三.调度算法:

1.先来先服务和短作业(进程)优先调度算法

(1)先来先服务调度算法(FCFS):

先来先服务调度算法是一种最简单的调度算法,该算法即可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个

或多个最先进入该队列的作业,将它们调入内存,为它们分配资源,创建进程,然后放入就绪队列。在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先

进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完或发生某事件而阻塞后才放弃处理机。

FCFS算法比较有利于长作业(进程),而不利于短作业(进程)。

(2)短作业(进程)优先调度算法:

短作业(进程)优先调度算法SJ(P)F,是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列

中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。而短进程(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它,使

它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机再重新调度。

优点:SJ(P)F调度算法能有效地降低作业(进程)的平均等待时间,提高系统吞吐量。

缺点:1>该算法对长作业不利;

2>完全未考虑作业的紧迫程度,因而不能保证紧迫性作业(进程)长期不被调度;

3>由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的,而用户又可能会有意或无意地缩短其作业的估计运行时间,致使该算法不一定能真正做到

短作业优先调度;

实例:


2.高优先权优先调度算法:

优先级调度的含义:

# 当该算法用于作业调度时,系统从后备作业队列中选择若干个优先级最高的,且系统能满足资源要求的作业装入内存运行。

# 当该算法用于进程调度时,将把处理机分配给就绪进程队列中优先级最高的进程。

优先权调度算法的类型:

(1)非抢占式优先级算法:

在这种调度方式下,系统一旦把处理机分配给就绪队列中优先级最高的进程后,该进程就能一直执行下去,直至完成;或因等待某事件的发生使该进程不得不放弃处理机

时,系统才能将处理机分配给另一个优先级高的就绪进程。

使用场合:主要用于一般的批处理系统、分时系统,也常用于某些实时性要求不太高的实时系统。

(2)抢占式优先级调度算法:

在这种调度方式下,进程调度程序把处理机分配给当时优先级最高的就绪进程,使之执行。一旦出现了另一个优先级更高的就绪进程时,进程调度程序就停止正在执行的

进程,将处理机分配给新出现的优先级最高的就绪进程。

使用场合:常用于实时要求比较严格的实时系统中,以及对实时性能要求高的分时系统。

优先级的类型:进程的优先级可采用静态优先级和动态优先级两种,优先级可由用户自定或由系统确定。

(1)静态优先权:静态优先级是在创建进程时确定进程的优先级,并且规定它在进程的整个运行期间保持不变。

确定优先级的依据:①进程的类型。通常系统进程优先级高于一般用户进程的优先级;交互型的用户进程的优先级高于批处理作业所对应的进程的优先级。

②进程对资源的需求。例如,进程的估计执行时间及内存需求量少的进程,应赋于较高的优先级,这有利缩小作业的平均周转时间。

③根据用户的要求。用户可以根据自己作业的紧迫程度来指定一个合适的优先级。

优点:①简单易行 ②系统开销小

缺点:①不太灵活,很可能出现低优先级的作业(进程),长期得不到调度而等待的情况。

②静态优先级法仅适用于实时要求不太高的系统。

(2)动态优先级:动态优先级是在创建进程时赋予该进程一个初始优先级,然后其优先级随着进程的执行情况的变化而改变,以便获得更好的调度性能。

优缺点:动态优先级优点是使相应的优先级调度算法比较灵活、科学,可防止有些进程一直得不到调度,也可防止有些进程长期垄断处理机。动态优先级缺点是需要花费相当多

执行程序时间,因而花费的系统开销比较大。

3.基于时间片的轮转调度算法

时间片轮转算法:

时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法。每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间。如果在时间片结束时进程正

在运行,则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束,则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表,当进程用完它的

时间片后,它被移到队列的末尾。

时间片轮转调度中唯一有趣的一点是时间片的长度。从一个进程切换到另一个进程是需要一定时间的–保存和装入寄存器值及内存映像,更新各种表格和队列等。假如进程

切换(process switch) – 有时称为上下文切换(context switch),需要5毫秒,再假设时间片设为20毫秒,则在做完20毫秒有用的工作之后,CPU将花费5毫秒来进行进程切换。

CPU时间的20%被浪费在了管理开销上。

原理:在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则,排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片,时间片的大小从

几ms到几百ms。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就

绪队列中新的队首进程,同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程,在一给定的时间内,均能获得一时间片的处理机执行时间。

实例:





版权声明:本文为wangiijing原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。