【408&预推免复习】操作系统之处理机调度与死锁

Bertha 。 2022-09-02 01:10 199阅读 0赞

【408&预推免复习】操作系统之处理机调度与死锁  
![在这里插入图片描述][resize_m_lfit_w_962_pic_center]

文章目录
    1 作业调度和进程调度
    2 实时调度和死锁概述
    3 预防死锁和避免死锁

# 1 作业调度和进程调度 #

什么是处理机调度？  
处理机调度：如何从众多的作业队列中选择一道或几道进入内存，进入内存的若干进程又如何去竞争CPU的使用权，这称为处理机调度。

![在这里插入图片描述][f0a4da8f647e458fa510abda7ef5c1c8.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
非抢占方式：一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或阻塞时，才再把处理机分配给其他进程。  
抢占方式：允许暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。  
抢占原则：  
（1）优先级原则。优先级高的进程抢占处理机。  
（2）短进程优先原则。短作业（进程）抢占当前较长作业（进程）的处理机。  
（3）时间片原则。各进程按时间片运行，当一个时间片用完后重新调度。  
先来先服务(first-come first-served，FCFS)调度算法  
算法思想：  
对于作业调度，从后备作业中选择最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。  
对于进程调度，从就绪队列中选择最先进入该队列的进程，分配处理机，使之运行。

短作业优先(short job first，SJF)的调度算法  
算法思想：  
短作业优先是从后备队列中选择估计运行时间最短的作业，将它们调入内存。  
短进程优先是从就绪队列中选择估计运行时间最短的进程，将处理机分配给它，使之执行并一直到完成或因发生某事件而阻塞放弃处理机时，再重新调度。  
特点  
极端情况下，长作业得不到调度。  
作业或进程的长短只能估计，不准确。  
完全不考虑紧迫程度，使紧急事件得不到处理。

![在这里插入图片描述][d3a0169f98524735b6c6d003b2853178.png_x-oss-process_imagetype_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
优先级调度算法分类：  
非抢占式优先级调度算法  
把处理机分配给就绪队列中优先权最高的进程后，便一直执行下去直至完成；或发生某事件使该进程放弃处理机时，可再将处理机重新分配给另一优先级最高的进程。  
用于批处理系统和某些对实时性要求不严的实时系统中。  
抢占式优先级调度算法  
把处理机分配给优先级最高的进程，使之执行。在执行期间，只要又出现优先权更高的进程，就重新将处理机分配给新到的优先级最高的进程。  
能更好地满足紧迫作业的要求，常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

优先级的类型  
静态优先级：创建进程时确定，在进程的整个运行期间保持不变。

动态优先级： 优先级随进程推进或随其等待时间的增加而改变的，以便获得更好的调度性能。  
高响应比优先调度算法(Highest Response Ratio Next，HRRN)  
FCFS算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。而SJF算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。  
高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。  
高响应比优先算法为每个作业引入一个动态优先级，它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可描述为：

![在这里插入图片描述][26f8fc93ebd649a79d34d162a82792a0.png]  
时间片轮转调度算法  
算法思想：  
进程按FCFS在就绪队列排队，调度程序把CPU分配给队首进程，令其执行一个时间片，一个时间片执行完毕将进程排在队尾。

时间片太大，交互性差，甚至退化为FCFS算法  
时间片太小，进程切换频繁，系统开销增加

多级反馈队列调度算法(multilevel Feedback Queue,MFQ)  
算法思想：  
根据作业的性质和类型不同，将就绪队列再分为若干个子队列，每个进程分属于一个队列。  
在多级队列的基础上，不但设多个队列，且为每个队列赋予不同的优先权，第一个队列的优先权最高，第二个队列次之，其余队列的优先权逐个降低。  
各个队列中的进程执行时间片大小逐渐增大。  
![在这里插入图片描述][2d133c89d50b41e191f3c8b15c1f06e1.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

# 2 实时调度和死锁概述 #

在实时系统中，可能存在着两类不同性质的实时任务，即HRT任务和SRT任务，它们都联系着一个截止时间。为保证系统能正常工作，实时调度必须能满足实时任务对截止时间的要求。为此，实现实时调度应具备一定的条件。  
1.提供必要的信息  
(1) 就绪时间，是指某任务成为就绪状态的起始时间  
(2) 开始截止时间和完成截止时间  
(3) 处理时间  
(4) 资源要求  
(5) 优先级，如果某任务的开始截止时间错过，势必引起故障，则应为该任务赋予“绝对”优先级；如果其开始截止时间的错过，对任务的继续运行无重大影响，则可为其赋予“相对”优先级，供调度程序参考。  
根据不同方式对实时调度算法加以分类：  
根据实时任务性质，分为硬实时调度算法和软实时调度算法  
根据调度方式，分为非抢占调度算法和抢占调度算法  
**最早截止时间优先EDF（Earliest Deadline First）算法**  
算法思想：根据任务的截止时间确定任务的优先级，任务的截止时间越早，其优先级越高，具有最早截止时间的任务排在队列的队首。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机。  
最早截止时间优先算法即可用于抢占式调度方式中，也可用于非抢占式调度方式中。

![在这里插入图片描述][c0156c8f52b94ae1a6c08aacb0862004.png_x-oss-process_imagetype_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
**最低松弛度优先LLF（Least Laxity First）算法**

该算法在确定任务的优先级时，根据的是任务的紧急(或松弛)程度。任务紧急程度愈高，赋予该任务的优先级就愈高，以使之优先执行。  
例如，任务A在200ms时必须完成，本身运行时间100ms，则必须在100ms之前调度执行，A任务的紧急（松弛）程度为100ms，又如任务B在400ms是必须完成，需运行150ms，其松弛程度为250ms.  
主要用于抢占式调度。

![在这里插入图片描述][661661285c8749c6836a444f4fefd03a.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

# 3 预防死锁和避免死锁 #

![在这里插入图片描述][7809eb93564e42d69df32fe34065a465.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
消耗性资源  
可消耗性资源又称为临时性资源，它是在进程运行期间，由进程动态地创建和消耗的，它具有如下性质：  
① 每一类可消耗性资源在进程运行期间其单元数目是可以不断变化的，有时它可以有许多，有时可能为0；  
② 进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目。  
③ 进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中。

可抢占性资源  
可抢占性资源，是指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占，抢占后不会产生异常或错误。  
如：CPU、主存  
不可抢占性资源  
不可抢占性资源，即一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。  
如刻录机、打印机。  
和死锁有关

![在这里插入图片描述][55ca789d80494a22bf107054901014d3.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个，以避免发生死锁。

![在这里插入图片描述][71e571458b064e8e9bb6f37aa7b36be1.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
安全状态  
指系统能按某种顺序如(P1，P2，…，Pn) ，来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。**若系统不存在这样一个安全序列、则称系统处于不安全状态。**  
系统进入不安全状态后可能进入死锁  
只要系统处于安全状态，系统便可避免进入死锁状态。  
避免死锁的实质：如何使系统不进入不安全状态。  
**利用银行家算法避免死锁**

银行家算法中的数据结构  
为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。　　(1) 可利用资源向量Available。　　(2) 最大需求矩阵Max。　　(3) 分配矩阵Allocation。　　(4) 需求矩阵Need。

存在关系：Need=Max-Allocation  
可用资源向量 available\[m\]: available\[i\]

代表资源i的可用资源数。初值为系统中所配置的该类资源的全部可用资源数。available\[j\]=k表示Rj类可用资源有k个。  
最大需求矩阵Max\[m,n\]: Max\[i,j\]=k 表示进程i最多需要k个Rj资源。  
分配矩阵Allocation\[m,n\]: Allocation\[i,j\]=k 表示进程i已分得k个Rj资源。  
需求矩阵Need\[m,n\]: Need\[i,j\]=k 表示进程i还需要k个Rj资源。

![在这里插入图片描述][8e2a638608c84bf9b5a31aa75adaa24d.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]

安全性算法　　系统所执行的安全性算法可描述如下：　　(1) 设置两个向量：① 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work := Available；② Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish\[i\] := false；当有足够资源分配给进程时，再令Finish\[i\] := true。  
(2) 从进程集合中找到一个能满足下述条件的进程： 　　① Finish\[i\]=false;　　② Need\[i, j\]≤Work\[j\];　　若找到，执行步骤(3)，否则，执行步骤(4)。(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：　　　　Work\[j\] = Work\[j\]+Allocation\[i, j\];　　　　Finish\[i\] =true;　　　　go to step 2;(4) 如果所有进程的Finish\[i\]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。  
![在这里插入图片描述][8c34409529404189b796bca83a5e1e17.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20e0665a6dae4c638930c37dc33f77bd.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
死锁检测算法：检测系统状态，以确定系统中是否发生死锁  
死锁解除算法：当系统中发生了死锁，利用该算法将系统从死锁中解除出来。  
![在这里插入图片描述][d7ef0353851744ab89d59552e13ee184.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][12b7b40a41e74429bdd39aea14f5ccd7.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]  
终止进程的方法　　1) 终止所有死锁进程　　这是一种最简单的方法，即是终止所有的死锁进程，死锁自然也就解除了，但所付出的代价可能会很大。  
2) 逐个终止进程　　稍微温和的方法是，按照某种顺序，逐个地终止进程，直至有足够的资源，以打破循环等待，把系统从死锁状态解脱出来为止。

[resize_m_lfit_w_962_pic_center]: /images/20220829/e6c0bfa94d014eefb2e24c378f645b75.png
[f0a4da8f647e458fa510abda7ef5c1c8.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/b4dcaf2f89ba443caaa2fbd5037cce1e.png
[d3a0169f98524735b6c6d003b2853178.png_x-oss-process_imagetype_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/b79a9af8d30c4980baa0a318451f268c.png
[26f8fc93ebd649a79d34d162a82792a0.png]: /images/20220829/daba43b71f0f4d409184c014e96b337e.png
[2d133c89d50b41e191f3c8b15c1f06e1.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/5e13172f946749a7aad8bdc34ed47c9e.png
[c0156c8f52b94ae1a6c08aacb0862004.png_x-oss-process_imagetype_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/8b6f1d61b18848b4adf0f34bd0660273.png
[661661285c8749c6836a444f4fefd03a.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/72e3ce4957d44a0e8d0dc309321504e4.png
[7809eb93564e42d69df32fe34065a465.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/475be0f3f4994ade8a4a494364e77fc8.png
[55ca789d80494a22bf107054901014d3.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/092d81ca064a4ad8bd581682ce2ae259.png
[71e571458b064e8e9bb6f37aa7b36be1.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/6078f9f0035a45f1af0825e3ba672919.png
[8e2a638608c84bf9b5a31aa75adaa24d.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/71aa691e8860492091c229a072df1d21.png
[8c34409529404189b796bca83a5e1e17.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/fbb2389de34d4467b5adb54b3485a141.png
[20e0665a6dae4c638930c37dc33f77bd.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/d168dc26439e4584a63a615e708e1bea.png
[d7ef0353851744ab89d59552e13ee184.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/73b0df13d53840e6b19e9459e89ccf7b.png
[12b7b40a41e74429bdd39aea14f5ccd7.png_x-oss-process_image_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgzODc4NQ_size_16_color_FFFFFF_t_70]: /images/20220829/a5a42209f44c4e079dea08a209ab9a01.png