操作系统复习 第三章
第三章 处理机调度与死锁
处理机调度的层次
进程:是一个程序对某个数据集的执行过程,是分配资源的基本单位。
作业:是用户需要计算机完成的某项任务,是要求计算机所做工作的集合
一个作业通常包括几个进程,几个进程共同完成一个任务,即作业。
用户提交作业以后,当作业被调度，系统会为作业创建进程, 一个进程无法完成时,系统会为这个进程创建子进程。
作业的概念更多地用在批处理系统中。
进程的概念几乎可以用在所有的多道程序系统中。
调度是多道程序的关键
调度算法的目标：
提高资源利用率
公平性。公平性是指应使诸进程都获得合理的CPU时间,不会发生进程
饥饿现象。平衡性。由于在系统中可能具有多种类型的进程,有的属于计算型作业,
有的属于I/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态,
调度算法应尽可能保持系统资源使用的平衡性。策略强制执行。对所制订的策略其中包括安全策略,只要需要,就必须
予以准确地执行,即使会造成某些工作的延迟也要执行。
批处理系统的目标：
平均周转周期更短
周转时间=作业完成时间-作业到达时间
平均周转时间=作业周转总时间/进程个数
带权周转时间:即作业的周转时间T与系统为它提供服务的时间T,之比,即.W = T/Ts。
- 可进一步反映调度的性能,更清晰地描述各进程在其周转时间中,等待和执行时间的具体分配状况.
系统吞吐量高
由于吞吐量是指在单位时间内系统所完成的作业数
它与批处理作业的平均长度有关
如果单纯是为了获得高的系统吞吐量,就应尽量多地选择短作业运行。
处理机利用率高
- 如果单纯是为使处理机利用率高,应尽量多地选择计算量大的作业运行
分时系统的目标：
响应时间快
- 响应时间指用户提交请求到系统首次响应为止的时间。
均衡性。
- 系统响应时间的快慢应与用户所请求的复杂性相适应。
实时系统的目标：
截止时间的保证
开始执行的最迟时间
必须完成的最迟时间。
可预测性
作业与作业调度
作业
作业(Job)
用户提交给计算机系统的任务。
由程序、数据、作业说明书组成。
作业步(Job Step)
作业执行期间所经历在加工步骤。
典型的作业控制过程分:“编译” “ 链接装配“ ”运行“
作业控制块(Job Control Block , JCB)
作业控制块是批处理作业存在的标志,保存有系统对于作业进行管理所需要的全部信息,位于磁盘区域中
作业开始,系统输入程序为其建立一个作业控制块,进行初始化,大部分信息取自作业说明书。
系统输入程序、作业调度程序、作业控制程序、系统输出程序等需要访问作业控制块。
作业完成后,其作业控制块由系统输出程序撤消。
作业调度
先来先服务算法（First Come First Serve）
FCFS是最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。
基本原则是按照作业到达系统的先后次序来选择,或者说它是优先考虑在系统中等待时间最长的作业,而不管该作业所需执行时间的长短。
短作业优先（Short Job First）调度算法
对短作业或短进程优先调度的算法。可以分别用于作业调度和进程调度。
SJF算法是以作业的长短来计算优先级,作业越短,其优先级越高。
SJF调度算法:从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。
缺点
(1)必须预知作业的运行时间。
(2)对长作业非常不利,长作业的周转时间会明显地增长，更严重的是,该算法
完全忽视作业的等待时间,可能使作业等待时间过长,出现饥饿现象。(3)在采用SJF算法时,人一机无法实现交互。
(4)该调度算法完全未考虑作业的紧迫程度,故不能保证紧迫性作业能得到及时处理。
优先级调度算法（Priority-Scheduling Algorithm）
- 反应作业的紧迫性
高响应比优先调度算法
高响应比优先调度算法则是既考虑了作业的等待时间,又考虑作业运行时间的调度算法,因此既照顾了短作业,又不致使长作业的等待时间过长,从而改善了处理机调度的性能
为每个作业引入一个动态优先级,即优先级是可以改变的，令它随等待时间延长而增加,这将使长作业的优先级在等待期间不断地增加,等到足够的时间后,必然有机会获得处理机。该优先级的变化规律可描述为:
$$
优先权=\frac{等待时间+要求服务时间}{要求服务时间}
$$
由于等待时间与服务时间之和就是系统对该作业的响应时间,故该优先级又相当于响应比RP。据此,优先又可表示为:
$$
R_p=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}
$$特点
(1)如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,
因而该算法有利于短作业。(2)当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时
间愈长,其优先权愈高,因而它实现的是先来先服务。(3)对于长作业,作业的优先级可以随等待时间的增加而提高，当其等待
时间足够长时,其优先级便可升到很高，从而也可获得处理机。
进程调度
任务
保存处理机的现场信息。
按某种算法选取进程。
把处理器分配给进程。
组成部分
排队器
分派器
上下文切换器
调度方式
非抢占方式：
处理机分配给某进程后,就一直让它运行下去,决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机，直至该进程完成,或发生某事件而被阻塞时,才把处理机分配给其它进程。
评价
实现简单、系统开销小
适用于大多数的批处理OS ,但在分时系统和要求比较严格的实时系统中,不宜采用这种调度方式
抢占方式
允许调度程序根据某种原则,去暂停某个正在执行的进程,将处理机重
新分配给另一进程。在现代OS中广泛采用抢占方式,这是因为:
对于批处理机系统,可以防止一-个长进程长时间地占用处理机,以确保处理机能为所有进程提供更为公平的服务。
在分时系统中,只有采用抢占方式才有可能实现人一机交互
在实时系统中,抢占方式能满足实时任务的需求。
抢占原则
优先权原则:优先权高的可以抢占优先权低的进程的处理机。
短作业(进程)优先原则:短作业(进程)可以抢占长作业(进程)的处理机。
时间片原则:各进程按时间片运行,一个时间片用完时,停止该进程执行重新进行调度。
调度算法
轮转调度算法
在分时系统中,为保证能及时响应用户的请求,必须采用基于时间片轮转式进程调度算法。
在早期,分时系统中采用的是简单的时间片轮转法
系统将所有的就绪进程按FCFS策略排成一个就绪队列
系统可设置每隔一定时间(如30 ms)便产生一次中断,去激活进程调度程序进行调度,把CPU分配给队首进程,并令其执行一个时间片。
当它运行完毕后,又把处理机分配给就绪队列中新的队首进程,也让它执行一个时间片。
这样,就可以保证就绪队列中的所有进程在确定的时间段内,都能获得一个时间片的处理机时间。
在RR调度算法中,应在何时进行进程的切换,可分为两种情况:
若一个时间片尚未用完,正在运行的进程便已经完成,就立即激活调度程序,将它从就绪队列中删除,再调度就绪队列中队首的进程运行,并启动一个新的时间片。
在一个时间片用完时,计时器中断处理程序被激活。如果进程尚未运行完毕,调度程序将把它送往就绪队列的末尾。
时间片大小：
如果太小利于短作业,但是会频繁中断,进程.上下文切换,增加系统开销;
如果太大则每个进程都能在时间片内完成,则退化为FCFS算法,无法满足交互式用户的需求。
一个比较可取的大小是,时间片略大于一次典型的交互所需要的时间。
优先级调度算法
优先级进程调度算法,是把处理机分配给就绪队列中优先级最高的进程。这时,又可进一步把该算法分成如下两种
非抢占式优先级调度算法。
抢占式优先级调度算法。
优先级类型
静态优先级是在创建进程时确定的,在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的,例如0 ~ 255中的某一整数,又把该整数称为优先数。确定进程优先级大小的依据有如下三个:
进程类型。
进程对资源的需求。
用户要求。
动态优先级
动态优先级是指在创建进程之初,先赋予其-个优先级,然后其值随进程的推进或等待时间的增加而改变,以便获得更好的调度性能。
若所有进程都具有相同的优先级初值,则最先进入就绪队列的进程会因其优先级变得最高,从而得到cpu ,等于FCFS。
若所有就绪进程具有各不相同的优先级初值,那么对于优先级初值低的进程,在等待了足够的时间后,也可以获得处理机。
也可以规定,当运行的进程随着运行时间的推移动态降低其优先级,防止一个进程长期垄断cpu。
多队列调度算法
- 在多处理机系统中可以为每个处理机设置一个单独的就绪队列
多级反馈队列调度算法
是时间片轮转算法和优先级调度算法的综合和发展,通过动态调整进程优先级和时间片大小,不必事先估计进程的执行时间。
FCFS+优先级+RR+抢占
多级反馈队列可兼顾多方面的系统目标,是目前公认的一种较好的进程调度算法
调度机制
设置多个就绪队列并为各个队列赋予不同的优先级,第一个最高,依次降低。各个队列中进程执行时间片的大小设置为:优先权越高，时间片越短
每个队列都采用FCFS算法。当新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可撤离系统。否则,即它在一个时间片结束时尚未完成,调度程序将其转入第二队列的末尾等待调度;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列, …..
依此类推。当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。按队列优先级调度。调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行;换言之,仅当第1~ (i-1)所有队列均空时,才会调度第队列中的进程运行。如果处理机正在第队列中为某进程服务时又有新进程进入任-优先级较高的队列,此时须立即把正在运行的进程放回到第队列的末尾,而把处理机分配给新到的高优先级进程。
注意
当现行进程正在执行它的C P U周期时,如果发生了时间片中断或有进程进入更高级的就绪队列时将引起剥夺,对前一-种情况,现行进程将进入下一级队列,对后一种情况,现行进程则进入本级队列末尾。
当一进程被唤醒时,它进入的是原先离开的那个队列，即与其当前优先级对
应的就绪队列。一个进程的优先级被降低,仅发生在因时间片中断而被剥夺的时候。
多级反馈队列调度算法具有较好的性能,能较好的满足各种类用户的需要。
终端型作业用户。大多属于较小的交互性作业,只要能使作业在第一队列的时间片内完成,便可令用户满意。
短批处理作业用户。周转时间仍然较短,至多在第二到三队列即可完成。
长批处理作业用户。将依次在1 ~ n级队列中轮转执行，不必担心作业长期得不到处理。
保证调度算法
在系统中有n个相同类型的进程同时运行,为公平起见,须保证每个进程都获得相同的处理机时间1/n。
跟踪计算每个进程自创建以来已经执行的处理时间。
计算每个进程应获得的处理机时间,即自创建以来的时间除以n。
计算进程获得处理机时间的比率,即进程实际执行的处理时间和应获得的处理机时间之比。
比较各进程获得处理机时间的比率。如进程A的比率最低,为0.5 ,而进程B的比率为0.8 ,进程C的比率为1.2等。
调度程序应选择比率最小的进程将处理机分配给它,并让该进程一-直运行,直到超过最接近它的进程比率为止。
公平共享调度算法
分配给每个进程相同的处理机时间，显然,这对诸进程而言,是体现了一定程度的公平,但如果各个用户所拥有的进程数不同,就会发生对用户的不公平问题。
用户1有4个进程A、B、C、D ,用户2只有一-个进程E。强制调度序列为:
A E B E C E D E A E B E C E D E如果希望用户1所获得的处理机时间是用户2的2倍,则强制调度序列为:
A B E C D E A B E C D E
实时调度
实时调度的条件
实时系统
两种任务
硬实时任务( HRT )指必须满足最后期限的限制,否则会给系统带来不可接受的破坏或者致命错误。
软实时任务( SRT)也有一个与之关联的最后期限,并希望能满足这个期限的要求,但这并不是强制的,即使超过了最后期限,调度和完成这个任务仍然是有意义的。
提供必要的信息
就绪时间。
开始截止时间和完成截止时间。
处理时间。
资源要求。
优先级。
系统处理能力强
- 单处理机实时调度条件
- $$
\sum_{i+1}^{n}\frac{C_i}{P_i}\leq1
$$ - 其中C表示处理时间，P表示周期时间
- $$
- 提高处理能力的途径
- 采用单处理机系统,增强处理能力,减少每个任务处理时间;
- 采用多处理机调度
- $$
\sum_{i+1}^{n}\frac{C_i}{P_i}\leq N
$$ - N表示处理机个数
- 单处理机实时调度条件
采用抢占式调度机制
- 在含有硬实时任务的实时系统中，广泛采用抢占机制。
- 当一个优先权更高的任务到达时,允许将当前任务暂时挂起,令高优先权任务立即投入运行,这样可满足该硬实时任务对截止时间的要求。但此种机制较复杂。
- 对于一些小的实时系统,如果能预知任务的开始截止时间,则对实时任务的调度可采用非抢占调度机制,以简化调度程序和对任务调度时所花费的系统开销。
具有快速切换机制
- 为保证要求较高的硬实时任务能及时运行,在实时系统中还应具有快速切换机制,以保证任务的快速切换。需要以下两种能力:
- 对外部中断的快速响应能力。要求系统具有快速硬件中断机构,使可在紧迫的外部事件请求中断时及时响应。
- 快速的任务分派能力。在完成任务调度后,便应进行任务切换,为提高速度,应使系统中的运行功能单位适当的小,以减少任务切换的时间开销。
- 为保证要求较高的硬实时任务能及时运行,在实时系统中还应具有快速切换机制,以保证任务的快速切换。需要以下两种能力:
实时调度算法
分类
根据实时任务性质,可将实时调度的算法分为:
硬实时调度算法
软实时调度算法
按调度方式,则可分为:
非抢占调度算法
非抢占式轮转调度算法。
非抢占式优先调度算法。
抢占调度算法
基于时钟中断的抢占式优先级调度算法。
立即抢占(Immediate Preemption)的优先级调度算法。
最早截止时间优先（Earliest Deadline First）算法
根据任务的截止时间来确定任务的优先级。截止时间越早,其优先级越高。
该算法要求在系统中保持一个实时任务就绪队列,该队列按各任务截止时间的早晚排序,调度程序在选择任务时总是选择就绪队列中的第一个任务,为之分配处理机,使之投入运行。
EDF算法既可以用于抢占式调度,也可用于非抢占式调度。
最低松弛度优先（Least Lexity First）算法
该算法是根据任务紧急(或松弛)的程度,来确定任务的优先级。任务的紧急程度越高,为之赋予的优先级就越高。
例如,任务A在200ms时必须完成,本身运行时间100ms ,则必须在100ms之前调度执行, A任务的紧急(松弛)程度为100ms ,又如任务B在400ms是必须完成,需运行150ms ,其松弛程度为250ms.
该算法主要用于抢占调度方式中。
优先级倒置（Priority Inversion Problem）
形成
- 当前OS广泛采用优先级调度算法和抢占方式,然而在系统中存在着影响进程运行的资源而可能产生”优先级倒置”的现象,即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞
死锁
死锁概述
死锁( Deadlock ) 是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时,若无外力作用,它们都将无法再向前推进。
| 共同点 | 区别 | |
|---|---|---|
| 死锁 | 都是进程无法向前推进的现象。 | 1.一定是循环等待对方手里的资源导致的 2.至少有2个或2个以上进程同时发生 3.进程处于阻塞态 4.操作系统分配资源的策略不合理导致 5.是管理者（操作系统）的问题 |
| 饥饿 | 1.只能由一个进程发生饥饿 2.可能在阻塞态，也可能在就绪态 3.操作系统分配资源的策略不合理导致 4.是管理者（操作系统）的问题 | |
| 死循环 | 1.可能只有一个 2.可以是运行态 3.由代码逻辑错误导致的 4.是被管理者的问题 |
资源
可重用性资源
每一个可重用性资源中的单元只能分配给一个进程使用,不允许多个进程共享。进程在使用可重用性资源时,须按照这样的顺序:
请求资源
使用资源。
释放资源。
系统中每一类可重用性资源中的单元数目是相对固定的,进程在运行期间既不能创建也不能删除它。
可消耗性资源
可消耗性资源又称为临时性资源,它是在进程运行期间,由进程动态地创建和消耗的,它具有如下性质:
每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的,有时它可以有许多,有时可能为0 ;
进程在运行过程中,可以不断地创造可消耗性资源的单元,将它们放入该资源类的缓冲区中,以增加该资源类的单元数目。
进程在运行过程中,可以请求若干个可消耗性资源单元,用于进程自己
的消耗,不再将它们返回给该资源类中。
可抢占性资源(CPU、内存等)
- 某进程在获得这类资源后,该资源可以再被其它进程或系统抢占。
不可抢占性资源(打印机、磁带机等)
- 一旦系统把某资源分配给该进程后,就不能将它强行收回,只能在进程用完后自行释放。
死锁原因
竞争不可抢占性资源
竞争可消耗资源
进程推进顺序不当
产生死锁的必要条件
互斥条件
请求和保持条件
不可抢占条件
循环等待条件
预防死锁
预防死锁的方法是使四个必要条件中的第2、3、4条件之一不能成立来避免发生死锁。
必要条件1 ,因为它是由设备的固有条件所决定的,不仅不能改变,还应加以保证。、
破坏请求和保持条件
第一种协议
系统规定所有进程在开始运行之前,都必须-次性的申请其在整个运行过程所需的全部资源。
优点:算法简单、易于实现且很安全。
缺点:资源浪费严重和使进程经常会发生饥饿现象。
第二种协议
进程提出申请资源前必须释放已占有的一切资源。
当一个已经保持了某些不可被抢占资源的进程,提出新的资源请求而不能得到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请。这意味着进程已占有的资源会被暂时地释放,或者说是被抢占了,从而破坏了”不可抢占”条件。
缺点：实现起来比较复杂且付出很大代价。可能会前功尽弃,反复申请和释放等情况,延长了周转时间,增加系统开销。
破坏循环等待条件
采用资源顺序分配法,可以破坏循环等待条件
采用资源顺序分配法,系统不会出现循环等待。因为在任何时刻,总有一个进程占有较高序号的资源,该进程继续请示的资源必然是空闲的。故该进程可一直向前推进。
优点:
- 有序资源分配法提高了资源利用率
缺点:
不方便增加新的设备,因为可能需要重新分配所有编号
进程实际使用资源的顺序可能和编号递增顺序不一致,会导致资源浪费;
必须按规定申请资源,用户编程麻烦,
避免死锁
系统安全状态
该方法允许进程动态地申请资源,系统在进行资源分配之前,先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程;否则不分配资源,进程必须阻塞等待。从而避免发生死锁。
安全状态:在此状态系统能按某种顺序P1, P2… Pn来为各个进程分配其所需资源,使每个进程都可顺序地一个个地完成。这个序列{P1,P….Pn}称为安全序列。
不安全状态:系统不存在任何一个安全序列
银行家算法
银行家算法的数据结构
可利用资源向量Available [m]
- m为系统中资源种类数, Available[j] =k表示系统中第j类资源数为k个。
最大需求矩阵Max[n][m]
- n为系统中进程数, Max[i][j] =k表示进程对j类资源的最大需求数为k。
分配矩阵Allocation[n][m]
- Allocation[i][j]=k表示进程i记分得j类资源的数目为k个。
需求矩阵Need[n][m]
Need[i][j]=k表示进程i还需要j类资源k个。
Need[i][j] =Max[i][j]-Allocation[i][j]
内容
设Request;[j]=k,表示进程P:需要k个R;类型的资源
如果Request;[j] <= Need[i,j],便转向步骤2 ;否则认为出错,因为它所请求的资源数已超过它所需要的最大值。
如果Request;[j] <= Available[j],便转向步骤3 ;否则,表示尚无足够资源，P需等待
系统试探着把资源分配给进程P，并修改下面数据结构中数值
Available[j] = Available[j]- Request;[j];
Allocation[ij] = Allocation[;j]+ Request;[j];
Need[ij] =Need[ij]-Request;[j];
安全性
(1 )设置两个向量:
工作向量work :表示系统可提供给进程继续运行所需的各类资源数目,含有m个元素的一维数组,初始时, work =Available;
Finish:含n个元素的一维数组,表示系统是否有足够的资源分配给n个进程,使之运行完成。开始时先令Finish[i] =false (i=1..n);当有足够资源分配给进程时,再令Finish[i]=true。
( 2 )从进程集合中找到一个能满足下述条件的进程:
Finish[i]=false;
Need[ij] < =work[j];
若找到，执行步骤( 3)，否则执行步骤( 4)。
( 3 )当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
work[j]= work[j]+ Allocation[ij] ;
Finish[i]=true;
go tostep (2);
( 4 )如果所有进程的Finish[i] =true都满足,则表示系统处于安全状态;否则,系统处于不安全状态。
检查死锁
为了能对系统中是否已发生了死锁进行检测,在系统中必须
①保存有关资源的请求和分配信息;
②提供一种算法,它利用这些信息来检测系统是否已进入死锁状态。
死锁定理
如果资源分配图中没有环路,则系统中没有死锁;
如果图中存在环路则系统中可能存在死锁
如果每个资源类中只包含一个资源实例,则环路是死锁存在的充分必要条件
如果每个资源类中资源实例个数不全为1 , 则环路是死锁存在的必要条件
死锁定理2
资源分配图化简
找到资源分配图中一个不孤立、不阻塞的进程节点,消去请求边与分配边,使之成为孤立点。
孤立点的资源释放后,可以分给其它进程,即将某进程的申请边变为分配边。
重复上述过程,当资源分配图中所有进程都成为孤立点时,称该资源分配图是可以完全简化的,否则称该资源分配图是不可完全简化的。
不孤立:是指该进程存在有与之相连的有向边;
不阻塞:是指该进程除了已经分配的资源外,对它尚需要的资源,系统都能够满足,因此该进程不会被阻塞。
孤立点:是指该进程既无请求边,也无分配边,即没有与之相连的有向边。
一种资源分配状态为死锁状态的充要条件是资源分配图是不可完全简化的。
解除死锁
当发现进程死锁时,便应立即把它们从死锁状态中解脱出来。常采用的方法是:
抢占资源:从其他进程剥夺足够数量的资源给死锁进程以解除死锁状态。
终止进程:最简单的是让全部进程都死掉;温和一点的是按照某种顺序逐个撤销进程，直至有足够的资源可用,使死锁状态消除为止。
终止所有死锁进程
- 这是一种最简单的方法,即是终止所有的死锁进程,死锁自然也就解除了,但所付出的代价可能会很大。因为其中有些进程可能已经运行了很长时间,已接近结束，一旦被终止真可谓“功亏一篑”,以后还得从头再来。
逐个终止进程
按照某种顺序,逐个地终止进程,直至有足够的资源,以打破循环等待,把系统从死锁状态解脱出来为止。
每终止一个进程,都需要用死锁检测算法确定系统死锁是否已经被解除,若末解除还需再终止另一个进程。
在采取逐个终止进程策略时,还涉及到应采用什么策略选择一个要终止的进程