第3章 处理机调度与死锁.docx
《第3章 处理机调度与死锁.docx》由会员分享，可在线阅读，更多相关《第3章 处理机调度与死锁.docx（29页珍藏版）》请在冰点文库上搜索。
第3章处理机调度与死锁
第三章处理机调度与死锁
第一节处理机调度的基本概念与调度算法
1调度的层次
一个作业，从进入系统并驻留在外存的后备队列上开始，直到作业运行完，要经历三级调度：
高级调度，低级调度和中级调度。
也就是一个作业从提交到完成要经历三级调度。
调度的层次如图所示：
1.1高级调度（HighScheduling）（作业/长程/宏观调度）
1.1.1任务
用于把外存上处于后备队列中的作业调入内存，并为它们创建进程、分配必要资源，再讲新创建的进程挂在就绪队列。
注意：
a）在批处理系统中，大多配有作业调度；分时/实时系统中，一般不配置。
b）作业调度执行频率很低，甚至几分钟一次，甚至更久。
1.1.2高级调度需要解决的问题
a）接纳多少个作业？
主要任务是从外存后备队列中选择多少作业进入就绪队列或挂起就绪，也就是允许多少作业同时在内存中运行，它决定着多道程序的“道或度”。
若作业太多，则可能会影响系统的服务质量（如周转时间太长），若太少，又将导致系统资源利用率和吞吐量的下降。
因此，应根据系统的规模和运行速度来确定，同时要求I/O型进程与CPU型进程中和调度。
b）接纳哪些作业？
应将哪些作业从外存调入内存，将取决于调度算法（先来先服务、短作业优先等算法）
1.2低级调度（lowlevelscheduling）（短程/CPU/进程/微观调度）
1.2.1任务
主要任务就是从就绪队列中选择一个进程来执行并给其分配处理机。
注意：
a）是OS中最基本的调度。
b）调度频率非常高，一般几十毫秒一次。
c）常采用非抢占（非剥夺）方式和抢占（剥夺）方式两种。
1.2.2进程调度方式
a）非抢占式（preemptivemode）
原理：
处理机分配给某进程后，便让该进程一直执行，直到该进程完成或因某事件而被阻塞，才再把处理机分配给其它进程，决不允许某进程抢占已分配出去的处理机。
特点：
现简单，系统开销小，常用于批处理系统；但不利于处理紧急任务，故实时、分时系统不宜采用
b）抢占式（preemptivemode）
原理：
度程序根据某种原则（时间片、优先权、短进程优先），停止正在执行的进程，而将处理机重新分配给另一进程。
特点：
处理紧急任务，故实时与分时系统中常采用。
时间片、优先权、短进程优先原则见课本P71。
例1，有三个进程P1、P2、P3先后到达，它们分别需要20、4和2个单位时间运行完毕。
假如它们就按P1、P2、P3的顺序执行，且不可剥夺，则三进程各自的周转时间分别为20、24、26个单位时间，平均周转时间是23.33个时间单位。
假如用时间片原则的抢占式调度方式，可得到：
0
2
4
6
8
10
12
26
P1
P2
P3
P1
P2
P1
P1
...
P1
2
2
2
2
2
16
可见：
P1、P2、P3的周转时间分别为26、10、6个单位时间，平均周转时间为14个单位时间。
补充：
衡量进程调度性能的指标有：
周转时间、响应时间、截止时间。
概念：
◆周转时间：
作业从提交到完成（得到结果）所经历的时间。
平均周转时间T。
见课本74
平均带权周转时间（带权周转时间W是T（周转）/T（CPU执行）〕
◆响应时间：
用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间
◆截止时间：
是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。
与周转时间有些相似。
1.2中级调度（intermediate-levelscheduling）（中程/交换调度）
1.2.1任务
在内存和外存对换区之间按照给定的原则和策略选择进程对换，以解决内存紧张问题，从而提高内存的利用率和系统吞吐量，常用于分时系统或具有虚拟存储器的系统中。
详见P72。
2、调度队列模型
在OS中的任何一种调度中，都将涉及到进程队列，由此形成了三种类型的调度队列模型。
2.1仅有进程调度的调度队列模型
仅有进程调度的调度队列模型
2.2具有高级和低级调度的调度队列模型
2.3同时具有三级调度的调度队列模型
3选择调度方式和算法的若干准则
3.1面向用户的准则
周转时间短、响应时间快、截止时间的保证、优先权准则
3.2面向系统的准则
系统吞吐量、处理机利用率好、各类资源平衡利用
3.3最优准则
最大的CPU利用率、最大的吞吐量、最短的周转时间、最短的等待时间、最短的响应时间
4调度算法
调度算法：
是指根据系统的资源分配策略所规定的资源分配算法。
这里所谓的调度算法，是指批处理系统、分时系统的调度，而不包括实时系统的调度。
4.1先来先服务和短作业（进程）优先调度算法
FCFS,FirstComeFirstService；SJF,ShortestJobFirst；SPF，ShortestProcessFirst
4.1.1先来先服务调度算法
1．基本思想：
按照进程进入就绪队列的先后次序来分配处理机。
一般采用非剥夺的调度方式。
适用于作业调度也用于进程调度。
◆当作业调度采用该算法：
每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，并分配资源、创建进程，之后进入就绪队列。
◆当进程调度采用该算法：
该算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便一直执行下去，直到该进程完成或阻塞时，才释放处理机。
2．例子：
见课本。
3．优缺点：
有利于长作业进程，而不利于短作业进程。
有利于CPU繁忙型作业，不利于I/O，忙的作业。
课本p76页。
现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。
但它常被结合在其它调度策略中使用。
4.1.2短作业（进程）优先调度算法（SJF/SPF）
1、基本思想：
短作业或短进程优先调度。
◆短作业优先调度算法（SJF）
v用于作业调度
v主要任务是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。
◆短进程优先调度算法（SPF）
v用于进程调度
v主要任务是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它。
2、例子，见课本
3、优缺点：
降低作业的平均等待时间，提高系统吞吐量。
对长作业不利；未考虑作业的紧迫程度；对进程估计执行时间难以预测。
4.2高优先权优先调度算法PrioritySchedulingFirst
为了考虑作业的紧迫程度，引入了最高优先权调度算法（FPF）
4.2.1优先权调度算法类型
1非抢占式优先权算法
基本原理：
系统把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成；或因发生某时间使该进程放弃处理机时，系统才可将处理机重新分配给另一优先权最高的进程。
适用：
批处理系统，实时性要求不高的实时系统。
2抢占式优先权算法
基本原理：
系统把处理机优先权最高的进程，使之执行。
若在其执行期间，只要又出现另一个优先权更高的进程，则立即停止当前进程的执行，重新分配处理机给新来的优先权更高的进程。
适用：
实时性要求高的实时系统，对性能要求高的批处理和分时系统。
4.2.2优先权类型
1、静态优先权
静态优先权是在创建进程的时确定的，且在进程的整个运行期间保持不变。
一般，利用某一范围内的整数来表示，如，0~7或0～255中的整数。
2、动态优先权
是指在创建进程时确定的优先权，在进程的运行期间会发生变化。
4.2.3高响应比优先调度算法
思想：
利用响应比也就是优先权来决定给作业分配处理机。
为响应比。
说明：
1）如等待时间相同,则要求服务时间愈短,其优先权愈高—SPF。
2）如要求服务时间相同,优先权决定于等待时间----FCFS。
3）对长作业,若等待时间足够长，优先权也高，也能获得CPU。
4.3基于时间片的轮转调度算法RR,RoundRobin
早期的分时系统采用时间片轮转算法，90年代后，采用多极反馈队列调度算法。
4.3.1时间片轮转法
基本思想：
系统将所有就绪进程按FCFS的原则，排成一个队列，依次调度，把CPU分配给队首进程，并令其执行一个时间片/CPU时间，通常为几个毫秒～几百毫秒。
时间片用完后，该进程将被抢占并插入就绪队列末尾。
4.3.2多级反馈队列调度算法RoundRobinwithMultipleFeedback
1、基本思想：
多级反馈队列调度算法是时间片轮转算法和优先级调度算法的综合和发展，通过动态调整进程优先级和时间片大小，不必事先估计进程的执行时间，多级反馈队列可兼顾多方面的系统目标，是目前公认的一种较好的进程调度算法。
2、实现过程：
（1）设置多个就绪队列，并为每个队列赋予不同的优先级。
队列1的优先级最高，其余队列逐个降低。
（2）每个队列中进程执行时间片的大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。
（3）当一个新进程进入系统时，首先将它放入队列1的末尾，按FCFS等待调度。
如能完成，便可准备撤离系统，反之由调度程序将其转入队列2的末尾，按FCFS再次等待调度，如此下去，进入队列n按时间片轮转算法调度执行。
（4）仅当队列1为空时，才调度队列2中的进程运行。
若队列I中的进程正执行，此时有新进程进入优先级较高的队列中，则新进程将抢占运行。
原进程转移至下一队列。
如下图：
第二节实时调度和多处理机系统调度
1概念
1.1实时调度
满足实时任务各自时间约束条件的调度称为实时调度。
1.2实现实时调度的基本条件
1．提供必要的调度信息（就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级）
2．系统处理能力强（限制条件：
决定系统是否可调度，否则减少C，C是处理时间。
单处理机必须满足下面的限制条件:
（m-实时任务数目，ci—每次处理时间，pi—周期时间）
例：
若系统中有6个硬实时任务，它们的周期时间是50ms，每次的处理时间是10ms，则
1/5+1/5+1/5+1/5+1/5+1/5>1,不满足上式，则系统是不可调度的，因为转一个循环周期，有一个任务没有执行到。
上面情况的解决方案是：
方案一，提高系统处理能力，也就是减少对每一个任务的处理时间Ci。
方案二，采用多处理机系统。
多处理机必须满足下面的限制条件:
（N—处理机数目，ci—每次处理时间，pi—周期时间）
3．采用抢占式的调度机制。
当一个优先权更高的进程到达，则当前进程被挂起。
让优先权高的任务执行。
这样来满足硬实时任务对截止时间的要求。
4．具有快速切换机制。
也就是具有快速响应中断能力和快速的任务切换能力。
1.3一些概念
◆就绪时间：
实时任务产生并可以开始处理的时间。
◆开始截止时间：
实时任务最迟开始处理的时间。
◆处理时间：
实时任务处理所需要的处理机的时间。
◆完成截止时间：
实时任务最迟完成时间。
◆发生周期：
周期性实时任务的发生间隔时间。
◆优先级：
实时任务相对紧廹程序。
2实时调度算法的分类
2.1按实时任务性质（即对时间约束强弱程度）
1.硬实时调度：
必须满足任务截止期要求，错过可能导致严重后果。
2.软实时调度算法：
期望满足任务截止期要求，错过一般可容忍。
2.2按调度方式
1.非抢占式调度算法（如下图所示）实时系统要求不严格系统。
P82
▪非抢占式轮转调度算法：
用于工业生产的群控系统中。
实时系统要求不严格系统。
▪非抢占式优先调度算法：
用于有一定时间要求的实时控制系统之中。
2.抢占式调度算法（如下图所示）
按抢占发生的时间
▪基于时钟中断抢占的优先权调度算法
▪立即抢占的优先权调度算法
3常用的几种实时调度算法
3.1最早截止时间优先算法（EDF算法earliestdeadlinefirst）
基本思想：
该算法是根据任务的开始截止时间来确定任务的优先级。
开始截止时间越早，其优先级越高。
就绪队列中任务按其截止时间排列，队首任务先分配处理机。
如：
见课本p83
3.2最低松弛度优先算法（LLF算法leastlaxityfirst）
基本思想：
该算法是根据任务紧急（或松弛）的程序，来确定任务的优先级。
任务的紧急度越高，其优先级越高，并使之优先执行。
该算法主要采用抢占调度方式，其调度也即具有完成截止时间的周期性实时任务的调度。
例：
在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行，执行时间为25ms。
其最低松弛度优先算法调度如下：
如下图。
4多处理机系统中的调度
多处理机系统（MPSMultiProcessorSystem）实现对信息的高度并行处理，达到提高系统吞吐量和可靠性的目的。
4.1多处理机系统的类型了解
1．从耦合的紧密程度来分类：
◆紧密耦合MPS：
通过高速总线或高速交叉开关实现多个处理器互联。
◆松弛耦合MPS：
通过通道或通信线路实现多台计算机互联。
2．由系统中所用的处理器分类。
◆对称多处理机系统：
多处理器单元在结构和功能上都是相同的。
是当前大多数MPS采用的系统。
◆非对称多处理机系统。
一般为主/从式，也就是一个主处理机多个从处理机。
4.2进程分配方式
在多处理机系统中，进程的调度和系统结构有关。
若同构型系统中，由于所有处理机都相同，则可将进程分配到任何一个处理机上执行；若非对称多处理机系统，则对每一个进程必须分配其到某一适合其运行的处理机上去执行。
4.1.1对称多处理机系统中的进程分配方式SMP系统
在SMP系统中，所有处理机都是相同的，因此可以看作为一个处理机池。
由调度程序，将任一进程分配给池中的任意处理机去处理。
采用两种方式：
1．静态分配（SaticAssigenment）
基本思想：
指一个进程从开始执行到其完成，都被固定地分配给一个处理机去执行。
注意：
应对该处理机单独设立专用的就绪队列，该队列中的进程都是先后被分配给这个处理机执行的进程。
当进程阻塞时，也挂在该就绪队列，唤醒后仍在该处理机上执行。
缺点：
使各处理机忙闲不均。
2．动态分配（DynamicAssgement）
基本思想：
在系统中，就设置一个公共的就绪队列，这样，所有的就绪进程进入该队列中。
分配进程时，可将进程分配到任何一个处理机上。
这样，对每个进程来说，每次调度时，都被随机的分配到当前空闲的某个处理机上执行。
优点：
消除各处理机忙闲不均情况。
4.1.2非对称多处理机系统中的进程分配方式
基本思想：
对于非对称MPS，多采用主－从式OS。
OS的核心部分留在一台主机上，从机上只有用户程序，进程调度只由主机执行。
每当从机空闲时，便向主机发送索取进程信号，此后等待主机为其分配进程。
主机中有一个就绪队列，若该队列不空，则主机从队首取一进程分配给请求的从机。
优点：
使得进程同步问题简化。
进程同步都靠主机分配了。
所以简单。
4.3进程（线程）的调度方式
大多是以线程为基本调度单位。
代表性的有：
自调度方式、成组调度方式、专用处理机分配方式。
4.3.1自调度方式
1．自调度机制
基本思想：
系统中设置有一个公共的进程或线程就绪队列。
所有处理机在空闲时，都可自己到该队列中取一进程（线程）执行。
该方式中，可采用单处理机下的算法，如，先来先服务，最高优先权，抢占式最高优先权调度算法。
2．优点：
首先,系统中的公共就绪队列可按照单处理机系统所采用的方式组织，调度算法也可采用单处理机系统。
因此可以将单处理系统的调度机制移植过来即可。
其次，只要公共就绪队列不空，就不会出现处理机空闲的情况，也没有处理机忙闲不均的现象。
缺点：
首先处理器必须互斥的访问公共就绪队列，容易形成瓶颈。
其次被阻塞线程重新被唤醒，并被分配处理机，不一定会分到其阻塞前的那个处理机，因此原处理机中所保存的数据又要被重新复制。
一个线程的生存周期中可能频繁的状态转换、更改处理机，造成低效。
4.3.2成组调度方式
基本思想：
将一个进程中的一组线程，分配到一组处理器上执行。
如何为应用程序分配处理器时间，有两个方式：
1．面向所有应用程序平均分配处理器时间
思想：
假定系统中有N个处理器和M个应用程序，每个应用程序中至多含有N个线程，则每个应用程序至多可有1/M的时间去占有N个处理器。
]
例：
4台处理器，2个应用程序A，B。
A有4个线程，B有1个线程。
可以知道每个应用程序有1/2的时间去占用4台处理器。
当A运行时，4台处理器全忙，当B运行时，1台处理器忙，3台处理器空闲，因此可以得出有3/8的处理器时间是空闲被浪费了。
2．面向所有线程平均分配处理器时间
思想：
对所有线程平均分配处理器时间。
如，应用程序A中有4个线程，程序B中有1个线程。
因此，为A分配4/5的时间，为B分配1/5的处理器时间，这样只有1/5*3/4=3/20=15%的处理器时间被浪费。
可以得出，按线程平均分配算法更有效。
4.3.3专用处理器分配方式
基本思想：
在一个应用程序的执行期间，专门为该应用程序分配一组处理器，每个线程一个处理器。
这组处理器仅供应用程序专用，直到应用程序完成。
缺点：
造成处理机的浪费。
若一个线程被阻塞，则为其分配的处理机就会空闲。
造成浪费。
常把该方式用于并发程度相当高的多处理器系统。
第三节死锁
1死锁的基本概念
1.1死锁
指多个进程在运行过程中因争夺资源而造成的一种僵局（deadly-Embrace），若无外力作用，这些进程都将无法向前推进。
注意：
（1）参与死锁的进程数至少为2
（2）参与死锁的所有进程均等待资源
（3）参与死锁的进程至少有两个占有资源
（4）参与死锁的进程是系统中当前正在运行进程的一部分。
1.2产生死锁的原因
原因两点如下：
1．竞争资源。
2．进程间推进顺序非法。
其根本原因：
是系统提供的资源个数少于并发进程所要求的该类资源数。
1.2.1竞争资源引起进程死锁
1．一些概念
可剥夺资源－是指进程在获得这些资源后，该资源可以再被其他进程或系统剥夺。
如，主存、CPU
非剥夺资源－是指当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后释放。
如驱动器、打印机等
永久性资源－可再次使用，如所有硬件。
临时性资源－消耗性的资源，如消息、信号和数据
2.竞争非剥夺性资源
系统所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在竞争这些资源时陷入死锁。
如下图：
说明：
R1代表系统中仅有的一台打印机。
R2代表系统中仅有的一台磁带机。
P1、P2代表可共享资源的进程。
当箭头从资源指向进程时，表示该资源已被分配给该进程；当箭头从进程指向资源时，表示进程请求资源。
3．竞争临时性资源
竞争临时性资源时，可能引起死锁。
如下图
说明：
若按下列顺序进行无死锁产生：
P1：
…Release（s1）;Request（S3）;…
P2：
…Release（s2）;Request（S1）;…
P3：
…Release（s3）;Request（S2）;…
但若按下列顺序进行可能产生死锁：
P1：
…Request（S3）;Release（s1）;…
P2：
…Request（S1）;Release（s2）;…
P3：
…Request（S2）;Release（s3）;…
1.2.2进程推进顺序不当引起进程死锁
S和Q是两个初值为1的信号量
P0P1
P（S）;P（Q）;
P（Q）;P（S）;
V（S）;V（Q）;
V（Q）V（S）;
其它原因：
如两进程谦让即“AfterYou/AfterYou”问题。
1.3产生死锁的必要条件
产生死锁必须具备以下四个条件，这四个条件是Coffman首先提出的，所以称为Coffman条件：
v互斥条件（资源独占条件）：
指的是对所分配到的资源的排他性使用。
v请求和保持条件（部分分配条件）：
指进程已经保持了至少一个资源，但又提出了新的资源请求。
但该资源已被占用，此时进程请求阻塞，但又对已获得资源保持不放。
v不剥夺条件：
进程已获得的资源，在未使用完之前，不能被剥夺。
v循环等待条件（环路条件）：
指在发生死锁时，存在一个进程－资源的环形链。
进程集合（P0，P1，P2，…..,Pn）,其中P0正在等待P1占用的一个资源，P2正在等待P3占用的一个资源，…..，Pn正在等待P0占用的一个资源。
1.4处理死锁的基本方法
目前处理死锁的基本方法有四种：
◆预防死锁：
指通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。
◆避免死锁：
指在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。
◆检测死锁：
允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。
◆解除死锁：
当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。
2预防死锁
2.1预防死锁
——破坏死锁的四个必要条件（常针对条件2,3,4）
（1）破坏互斥条件：
即允许多个进程同时访问资源。
但由于资源本身固有特性限制，有的资源根本不能同时访问，只能互斥访问，所以破坏互斥条件来预防死锁，这不太可能。
（2）破坏请求和保持条件：
可采用预先静态分配方法，即要求进程在运行之前一次申请它所需要的全部资源，在它的资源未满足前，不把它投入运行。
一旦运行后，这些资源全归其占有，同时它也不再提出其它资源要求，这样可以保证系统不会发生死锁。
此方法虽简单安全，但降低了资源利用率，同时必须预知进程所需要的全部资源。
（3）破坏不可剥夺条件：
即一个已经获得某些资源的进程，若又请求新的资源时不能得到满足，则它必须释放出已获得的所有资源，以后需要资源时再请求。
也即一个进程已获得的资源在运行过程中可被剥夺。
从而破坏了该条件。
但这种方法实现较复杂，会增加系统开锁，降低系统吞吐量。
（4）破坏环路条件：
可采用有序资源分配方法，即将系统中的所有资源都按类型赋予一个编号，要求每一个进程均严格按照编号递增的次序来请求资源，同类资源一次申请完。
也就是，只要进程提出请求资源Ri，则在以后的请求中，只能请求Ri后的资源，这样不会出现几个进程请求资源而形成环路。
就是所有进程对资源的请求必须严格按照资源序号递增的顺序提出，从低到高申请。
该方法虽提高了资源的利用率，但编号难，加重进程负担及因使用资源顺序与申请顺序不同而造成资源浪费。
3死锁的避免
在死锁预防的几种方法中，都施加了较强的限制条件，严重降低了系统性能。
在死锁避免的方法中，所施加的限制条件较弱，则可获得让人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态。
2.1系统的安全状态
2.1.1安全状态
概念：
指在某一时刻，系统能按某种进程顺序（p1,p2,…，pn）来为每个进程Pi分配其资源,直到满足每个进程对资源的最大需求,使每个进程都可顺利地完成，则称此时的系统状态为安全状态称序列（p1,p2,…，pn）为安全序列。
若某一时刻系统中不存在这样一个安全序列，则称此时的系统状态为不安全状态。
注：
在死锁避免的方法中，允许
升级会员 