作业调度算法(含详细计算过程)和进程调度算法浅析

简介: 作业调度算法(含详细计算过程)和进程调度算法浅析

一.作业调度

作业调度算法需要知道以下公式

周转时间=完成时间 - 到达时间

带权周转时间=周转时间/运行时间

注:带权周转时间越大,作业(或进程)越短;带权周转时间越小,作业(或进程)越长。带权周转时间越小越好

平均周转时间=作业周转总时间/作业个数;

平均带权周转时间=带权周转总时间/作业个数

同时,作业调度算法会涉及一个概念:


饥饿:


作业饥饿(Job Starvation)或被饿死(Starvation)就是一个或多个低优先级的作业无法获得系统资源,无法得到执行的机会,从而长时间处于等待状态的情况。这种情况下,这些作业就会被饿死或者饥饿,因为它们无法得到所需的系统资源而无法完成执行。


看如下例子:

1.FCFS(先来先服务算法)

谁先到达,谁就先运行,所以作业运行顺序为1->2->3->4

第一个作业完成后,第二个作业才能开始运行,所以第二个作业开始的时间是10:00

以此类推得到:

先来先服务算法的特点

先来先服务算法实现简单,但是可以看到排在长作业后面的短作业需要等待很长时间,对短作业来说用户体验不好。

是否导致饥饿:此算法较为公平,不会导致饥饿

2.SJF(短作业优先调度算法)

谁的运行时间最短,谁就先运行

首先也从第一个开始,因为2,3,4都没有到达

第一个的完成时间是10:00,这时候2,3,4都到达了,但是作业3的运行时间最短,所以接下来运行作业3

作业4的运行时间最短,所以接下来运行作业4,以此类推,最终的执行顺序为:1->3->4->2

SJF算法的特点

短作业优先算法拥有“最短的”平均等待时间和平均周转时间


是否导致饥饿:此算法会导致饥饿,如果有源源不断的短作业进来,可能使长作业长时间得不到服务。如果一直得不到服务,则称为“饿死”。


注:在实际情况下,作业的运行时间往往是由用户提供的估计值,并不一定真实准确。这意味着在实际应用中,我们可能无法完全实现真正的短作业优先。

3.HRRF(高响应比优先算法)

(等待时间+运行时间)/运行时间

注:较高的响应比意味着作业等待时间相对较短,或者作业的服务时间相对较长,这可以确保作业尽快得到响应并完成。因此,响应比越高通常表示作业具有更好的调度优先级

从作业1开始:

若下一个执行的作业为作业2,那么响应比就是:(10:00-8:30)+40/40=13/4


若下一个执行的作业为作业3,那么响应比就是:(10:00-9:00)+25/25=85/25


若下一个执行的作业为作业4,那么响应比就是:(10:00-9:30)+30/30=2


因为85/25>13/4>2,下一个执行的作业是作业3

执行完后,要重新计算高响应比,响应比最高的运行,得到


若下一个执行的作业为作业2:(10:25-8:30)+40/40=155/40=3.875


若下一个执行的作业为作业4:(10:25-9:30)+30/30=85/30=2.8333...


所以下一个执行的作业为作业2,则最终执行的顺序是:1->3->2->4

高响应比优先算法的特点

综合考虑了等待时间和运行时间(要求服务时间)

等待时间相同时,要求服务时间短的优先(SJF 的优点)

要求服务时间相同时,等待时间长的优先(FCFS 的优点)

对于长作业来说,随着等待时间越来越久,其响应比也会越来越大,从而避免了长作业饥饿的问题。


二.进程调度

以上的作业调度,我没有提到进程二字,就是怕大家混淆起来,进程调度和作业调度是两个不同的调度方法:


1、作业调度

作业调度又称为高级调度,频度较低。其主要工作是将位于外存后备队列中的某个(或某几个)作业调入内存,排在就绪队列上。注意了,这个时候仅仅是将作业调入内存,并为作业创建进程、分配资源,此时进程处于就绪态,并没有执行。



2、进程调度

进程调度又称为低级调度,是最基本的、频度最高的调度方式。其主要任务是从就绪队列中选取一个(或几个)进程,并分配处理机的过程,这时候才可以理解为“执行”。



3、区别

作业调度和进程调度最主要的区别在于,前者是为作业建立进程的过程,是将作业由外存调入内存的过程;而后者整个过程并没有跑出内存的范围,是将就绪态的进程变为运行态的过程。


进程调度也有饥饿的概念,同时进程调度中还有一个重要的概念:


抢占式/非抢占式:


抢占式调度:

•抢占式调度是指操作系统允许正在运行的进程被强制中断,以便让更高优先级的进程获得CPU资源并开始运行。

•在抢占式调度中,操作系统会定期检查所有正在运行的进程的优先级,并且如果有更高优先级的进程出现,操作系统会立即中断当前进程的执行,将CPU资源分配给更高优先级的进程。

•例如,在抢占式调度中,当一个进程正在执行一个关键任务时,如果有更高优先级的进程需要运行,操作系统会立即中断当前进程的执行,并将CPU资源分配给更高优先级的进程。


非抢占式调度:


•非抢占式调度是指一旦一个进程获得处理器,它就会一直运行直到完成或者自愿让出CPU。

•在非抢占式调度中,高优先级的进程必须等待当前正在运行的进程结束或者主动让出CPU后,才能获得CPU资源并开始运行。

•例如,在非抢占式调度中,当一个进程正在执行一个关键任务时,其他高优先级的进程需要等待该进程完成或者主动让出CPU,才能获得CPU资源并开始执行。


正因为进程调度有这两个性质,所以除了拥有作业调度的三种算法(FCFS,SJF,HRRF),还有其他常见的算法:


1.SRTF(最短剩余时间优先调度算法)

SRTF与SJF最大的区别就是其是抢占式的算法。

运行原理:每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列等待下一次调度。


2.RR(时间片轮转调度算法)

算法思想:公平地、轮流地为各个进程服务,让每个进程在一定时间间隔内都可以得到响应。

调度程序每次把CPU分配给就绪队列首进程/线程使用一个时间间隔(称为时间片),就绪队列中的每个进程/线程轮流运行一个时间片。


算法规则:按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片(每次选择的都是排在就绪队列队头的进程)。若进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队。

时间片的选取:时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等方面考虑。

常用轮转法:

① 最常用的轮转法是等时间片轮转法,每个进程轮流运行相同时间片。

② 改进的轮转法对于不同的进程分配不同的时间片,时间片的长短可以动态修改。


是否抢占式:抢占式


是否会产生饥饿:不会


优点:公平,响应快,适用于分时操作系统。

缺点:由于高频率的进程切换,因此有一定开销;不区分任务的紧急性。


对于时间片轮转调度算法的实现,建议观看如下视频:


RR时间片轮转调度算法 ~相同到达时间_哔哩哔哩_bilibili


RR时间片轮转调度算法~不同到达时间_哔哩哔哩_bilibili


时间片太大或太小

① 如果时间片太大,使得每个进程都可以在一个时间片内就完成,则时间片轮转调度算法退化为先来先服务调度算法,并且会增大进程的响应时间。

② 如果时间片太小,进程调度、切换是有时间代价的,会导致进程切换过于频繁,系统会花大量的时间来处理进程切换,从而导致实际用于进程执行的时间比例减小。


3.PSA(优先级调度算法)

算法思想:根据任务的紧急程度来决定处理顺序。

算法规则:根据确定的优先级选取进程/线程,每次总是选择就绪队列中优先级最高者运行。

用户进程/线程优先级的规定者有两种:

① 用户:用户自己提出优先级,称为外部指定法。优先级越高,费用越高。

② 系统:由系统综合考虑有关因素来确定用户进程/线程的优先级,称为内部指定法。

进程/线程优先级的确定方式:

根据优先级是否随时间而变,进程/线程优先级的确定有静态和动态两种方式:

① 静态优先级:在进程/线程创建时确定,此后不再改变。优先级主要由进程类型、资源需求、时间需求和用户需求决定。

优点:比较简单,开销小。

缺点:不够公平不太灵活,可能出现优先级低的作业/进程长时间得不到调度的情况。

② 动态优先级:随时间而变,基本原则是:

a. 正在运行的进程/线程随着占有CPU时间的增加优先级逐渐降低;

b. 就绪队列中等待CPU的进程/线程随着等待时间增加优先级逐渐提高。

优点:公平性好,灵活,资源利用率高。

缺点:需要花费比较多的执行程序时间,因而花费的系统开销比较大。


是否可抢占:抢占式,非抢占式都有。


是否导致饥饿:会

若源源不断地有高优先级进程到来,则可能导致饥饿。

区别在于:非抢占式只需在进程主动放弃处理机时进行调度即可,而抢占式还需在就绪队列变化时,检查是否发生抢占。

优点:用优先级区分紧急程度、重要程度,适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。

缺点:若源源不断地有高优先级进程到来,则可能导致饥饿。


优先级调度算法:


速通操作系统优先级调度算法_哔哩哔哩_bilibili


4. MLFQ(多级反馈队列调度算法)

算法思想:对其他调度算法的折中权衡。

算法规则:

1、建立多级就绪进程队列,各级队列优先级从高到低,时间片从小到大。每个队列赋予不同优先级,较高优先级队列一般分配给较短的时间片。


2、新进程到达时先进入第1级队列,按先来先服务原则排队等待被分配时间片,若用完时间片进程还未结束,则进程进入下一级队列队尾;若此时已经在最下级的队列,则重新放回该队列队尾。


3、处理器调度每次先从高优先级就绪队列中选取可占有处理器的进程,只有在选不到时,才从较低优先级就绪队列中选取进程。即只有第k级队列为空时,才会为k+1级队头的进程分配时间片。


4、任务可以根据自身的行为(如CPU使用时间、等待时间等)在不同的队列之间移动,实现动态优先级的调整。


是否可抢占:抢占式

在k级队列的进程运行过程中,若更上级的队列(1~k-1级)中进入了一个新进程,则由于新进程处于优先级更高的队列中,因此新进程会抢占处理机,原来运行的进程放回k级队列队尾。


是否导致饥饿:会

优点:对其他调度算法的折中权衡。

对各类进程相对公平(FCFS的优点);

短进程只用较少的世界就可完成(SPF的优点);

每个新到达的进程都可以很快得到响应(RR的优点);

不必实现估计进程的运行时间(避免用户作假);

可灵活地调整对各类进程的偏好程度,比如:CPU密集型进程、I/O密集型进程(拓展:可以将因I/O而阻塞的进程重新放回原队列,这样I/O型进程就可以保持较高优先级)。

缺点:可能会导致饥饿

目录
相关文章
|
7天前
|
算法 调度 Python
【调度算法】并行机调度问题遗传算法
【调度算法】并行机调度问题遗传算法
19 2
|
7天前
|
算法 调度
【调度算法】NSGA III(2)
【调度算法】NSGA III
19 1
|
7天前
|
算法 测试技术 调度
【调度算法】DTLZ问题家族
【调度算法】DTLZ问题家族
14 1
|
7天前
|
算法 数据挖掘 调度
【调度算法】NSGA III(1)
【调度算法】NSGA III
14 0
|
4天前
|
存储 负载均衡 算法
深入理解操作系统的进程调度
【6月更文挑战第20天】本文将探讨操作系统中的进程调度,包括其定义、重要性以及常见的调度算法。我们将通过具体的例子和代码片段来深入理解进程调度的工作原理和实现方式。最后,我们将讨论进程调度在现代操作系统中的应用和挑战。
|
6天前
|
调度
操作系统之进程调度机制
操作系统之进程调度机制
9 1
|
7天前
|
算法 调度
【调度算法】Boltzmann选择
【调度算法】Boltzmann选择
37 1
|
7天前
|
算法 调度 Python
【调度算法】开放车间调度问题遗传算法
【调度算法】开放车间调度问题遗传算法
12 1
|
7天前
|
算法 调度
【调度算法】NSGA II
【调度算法】NSGA II
23 1
|
7天前
|
人工智能 算法 网络性能优化
【调度算法】服务组合优选问题的指标选择与评估
【调度算法】服务组合优选问题的指标选择与评估
16 0