操作系统二——资源分配与调度

1. 资源管理概述

1.1 资源管理的目的和任务

资源的静态分配和动态分配
- 资源的静态分配
  - 系统对作业一级采用资源静态分配方法。
  - 系统在调度作业时，根据作业所需资源进行分配；并在作业运行完毕时，收回所分配的全部资源。称为资源的静态分配。
- 资源的动态分配
  - 系统对进程一级采用资源动态分配方法。
  - 系统在进程运行中，根据进程提出的资源需求，进行资源的动态分配和回收。称为资源的动态分配。
资源管理的目的
- 目的：为用户提供一种简单而有效地使用资源的方法，充分发挥各资源的作用。
- 应达到的目标：
  - 保证资源的高利用率
  - 在”合理”时间内使所有顾客有获得所需资源的机会
  - 对不可共享的资源实施互斥使用
  - 防止由资源分配不当而引起死锁
资源管理的任务
- 任务：解决资源分配问题，防止死锁；解决对资源的存取、使用方法问题
- 资源管理的功能
  - 资源数据结构的描述
  - 确定资源的分配原则和调度原则
  - 执行资源分配
  - 存取控制和安全保护

1.2 资源的分类方法

物理资源和程序资源(处理器、外设等；消息或文件等)
单一访问入口资源(不可重入，只能为一个进程使用)和多访问入口资源(可以为多个进程共享使用)
等同资源(多个完全相同的设备)
虚拟资源(cpu、一定容量的主存、数量有限的外设)，如虚拟存储器

1.3 虚拟资源

虚拟资源是用户使用的逻辑资源，是经过操作系统改造的、使用方便的虚拟资源，而不是那些物理的实际的资源，这样做的目的，一是要提高资源利用率，二是为了方便用户的使用

2. 资源管理的机制和策略

机制：进行资源分配的必需的基本设施和部件，它包括描述资源状态的数据结构、保证资源互斥的同步机构及资源请求排队的手段。
策略：这些机构所使用的方法，资源分配的原则

2.1 资源分配机制

资源描述器
- 什么是资源描述器
  描述各类资源的最小分配单位的数据结构称为资源描述器 RD (resource descriptor)。如：
  - 主存最小分配单位：在分区分配中—主存分区
  - 磁盘最小分配单位：磁盘面中的一个扇区
- 描述器的组织方式取决于资源分配单位的数量和这一数量是固定不变的、还是可以变化的这一特征。
- 资源描述器的内容
  - 资源名
  - 资源类型
  - 最小分配单位的大小
  - 最小分配单位的地址
  - 分配标志
  - 描述器链接信息
  - 存取权限
  - 密级
  - 最后一次存取时间
  - 记账信息
  - 资源信息块
    - 什么是资源信息块(rib)
      描述某类资源的请求者、可用资源和该类资源分配程序等必要信息的数据结构。
      - 对于每一类可利用的资源，可将其组织成可利用资源队列。在资源信息块中有指向这两个队列的队列指针，另外还有一项为该类资源分配程序的入口地址。
    - 资源分配程序是接收分配命令把资源分配给请求者的例程。
      - 资源分配程序包括：分配程序和回收程序。
    - 资源信息块的内容
    - 资源分配的方式取决于设计者所选择的目标，以及与应用每一类资源相联系的特定限制。目的是使吞吐率尽可能地高，响应时间尽可能地短，即既要充分地利用系统各种资源，又要尽可能地满足用户要求。
    - 一个资源进行分配的问题，在一般情况下，是由这样两个方面组成的：管理请求的排队站（分配策略）与在等同资源间选择资源。
    - 分配程序可以用不同的策略选择进程请求
      - 按照请求来到的次序进行查看
      - 将进程请求者的优先权结合到每一个请求中
      - 满足能更合理地应用这一资源的那个请求

2.2 资源分配策略

1)先请求先服务(FIFO(First In First Out))
- 排序原则：按请求的先后次序排序。
- 每一个新产生的请求均排在队尾，而当资源可用时，资源分配程序则从队列中选取第一个请求，并满足其需要。
- 这种策略可用于对进程或作业的调度，或外设、主存分配
2)优先调度
- 在优先调度策略下，对于每一个进程要指定一个优先级，优先级反映了进程要求处理的紧迫程度。
- 排序原则：按优先级的高低排序。
- 每一个新产生的请求，按其优先级的高低插到相应的位置上。而当资源可用时，选取队列中第一个请求，并满足其需要。
3)针对设备特性的调度
对具有高速度、大容量的存储设备(如磁盘)而言，在繁重的输入输出负载下，会有大量的I/O请求在等待。操作系统应该采取有效的调度策略从众多的请求中按最佳的排序原则去选择。确定最佳排序的目标是降低为完成这些I/O请求服务的总时间，从而提高系统效率。
- 移臂调度
  所谓移臂调度是指在满足某一个磁盘请求时，总是选取与当前移动臂前进方向上最近的那个请求，使移臂距离最短。
  针对设备特性的调度是I/O调度。I/O调度程序是在磁盘硬件层实施的，磁盘硬件看到的是磁盘面、磁道、块号(对磁盘组为: 柱面号、盘面号、块号)。如下例所示，若磁盘组同时有5个访问请求，它们按请求的先后次序排序，要求访问的盘区位置如表1所示：
  如果当前移动臂处于1号柱面上，若按上述次序访问磁盘，移动臂将从1号柱面移动到6号柱面，再移至48号柱面，然后回到3号柱面。显然这样移臂很不合理。
  若按表2次序访问则可节省移动臂时间(注：当前移动臂方向是由外向里，即柱面号由小到大)
- 旋转调度
  所谓旋转调度是指在满足一个磁盘请求时，总是选取与当前读写头旋转方向上最近的那个请求，使旋转圈数最少。
  对于上述示例，使用表3排序则旋转次数更少：
4)几种移臂调度算法
- 最短寻道时间优先算法
- 扫描算法

柱面号	盘面号	块号
6	3	2
6	5	9
6	5	4
48	8	16
3	9	28

表1

柱面号	盘面号	块号
3	9	28
6	3	2
6	5	9
6	5	4
48	8	16

表2

柱面号	盘面号	块号
3	9	28
6	3	2
6	5	4
6	5	9
48	8	16

表3

3. 死锁

3.1 死锁的定义与例子

操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度地利用计算机系统的资源，操作系统应用动态分配系统各资源的策略。然而，采用这种策略时，若分配不当，一旦出现对某类资源的申请数目超过了这类资源的入口数目时，就是造成进程相互封锁的危险。事实上，不同进程对资源的申请可能按某种先后次序得到部分满足，这就可能造成其中的两个或几个进程彼此间相互封锁的情况。即每个进程“抓住”一些为其它进程所等待的资源不放，其结果谁也得不到它所申请的全部资源，所有这些进程都无法继续运行。

例子：
- OS系统中的死锁例子
- I/O设备共享时的死锁情况
  
  此图可描述I/O设备共享时的死锁情况。
  方框代表资源，圆圈表示进程；从资源到进程的箭头(有向边)，表示该资源分配给进程，过程资源分配边；而从进程到资源的箭头表示进程请求边。
  由图可见，进程P1、P2的资源分配边和资源请求边形成一个环路。
- 存储器共享时的死锁情况
  
  我们可以这样说，如系统中由一个包含有m个分配单位的存贮器，它为n个进程所共享，且每个进程都要求I个分配单位，当m<=n(I-1)时，可能发生死锁。
  上图绘出了一个大大简化了的存贮器共享的情况，其中m=5,n=3,I=3。当P1、P2分别获得2个单元、P3获得1个单元时，内存被分配完毕。此时，系统进入一个不安全状态，因为在它们要求下一个所需要的单元资源时，便发生死锁(此时，它们都指望其它进程释放出内存空间，但谁都也不能再向前推进一步)。
死锁的定义：
- 若一个进程集合中的每一个进程都在等候只能由本集合中的另一进程才能引发的时事件则这种情况被视为死锁。
- 死锁是并发进程彼此互相等待对方拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有得资源，这就造成了各并发进程想得到不可能得到的资源，从而不能继续向前推进进程的状态。

3.2 产生死锁的原因和必要条件

死锁产生的原因
并发进程共享系统资源，在竞争资源时可能会产生称为死锁的附带后果。产生死锁的根本原因是系统能够提供的资源个数比要求该资源的进程数要少。所以，当系统中两个或多个进程没能力进一步执行时，系统就发生死锁。
资源竞争现象是具有活力的、是需要的，虽然它存在着发生死锁的危险，但是，竞争并不等于死锁。在并发进程的活动中，存在着一种合理的联合推进路线，这种推进路线可使每个进程都运行完毕。但如果进程推进不合理则会出现死锁。
由此可知，产生死锁的原因是：
- a. 系统资源不足
- b. 进程推进顺序非法。
死锁发生的必要条件
- a. 互斥条件，每一资源或者被分配给一个进程，或者空闲。
- b. 部分分配条件，已分配到了一些资源的进程可以申请新的资源。
- c. 非剥夺条件，已分配给一进程的资源不可剥夺，只能被占有它的进程显式地释放。
- d. 循环等待条件，存在一种进程的循环链，链中的每一个进程以获得的资源同时被链中下一个进程所请求。

3.3 死锁模型

资源分配图的成分：
eighth
用资源分配图分析死锁例：
nineth
用资源分配图分析无死锁例：
tenth

3.4 解决死锁的策略

并发进程共享系统资源时如处理不当可能发生死锁。死锁不仅会在两个进程之间发生，也可能在多个进程之间、甚至在系统全部进程之间发生。此外，死锁不仅在动态使用外设时发生，也可能在动态使用存贮器和数据库时发生，或在进程通信过程中以及在利用信号灯作同步工具时由于p操作顺序不当而产生。在早期的操作系统中，系统规模较小，结构简单，而且资源的分配常常采用静态方法，使得操作系统尚未暴露死锁问题的严重性。但是，随着系统规模的增大，软件系统变得异常庞大而复杂，系统资源的种类亦日益增多，因而，死锁的可能性将大大增加。由于死锁的发生会给系统带来严重的后果，因此，处理系统死锁问题引起了人们的普遍注意，并对它进行了深入的研究。
但某些类别的死锁问题的发生概率极小，这时大多数用户宁可承受在极偶然情况下发生的死锁，也不愿使其工作不便或系统性能受损–因解决这类死锁要花费很大的代价。所以，在设计上，我们不得不在方便性与正确性之间作出折衷，即象驼鸟一样对此类死锁视而不见,这就是驼鸟算法。
为了使系统不发生死锁，必须设法破坏产生死锁的四个必要条件之一。可以采用下列策略之一来解决死锁问题：

1)采用静态分配方法来预防死锁
2)采用有控分配方法来避免死锁
3)当死锁发生时检测出死锁，并设法修复

3.5 死锁的预防

基本思想：静态防止发生死锁的方法。
预先分配所有共享资源是预防死锁的一种安全而由简单的方法。这种方法的基本思想是：每个用户向系统提交作业时，需一次说明它所需要的资源；并且作业调度程序只能在满足该作业所需的全部资源的前提下才能将它投入运行。当资源一旦分配给该作业后，在其整个运行期间这些资源为它独占。这样就摒弃”部分分配”了条件,摒弃”不剥夺”了条件 ,摒弃”环路等待”了条件。
死锁预防的缺点：

a.一个用户在作业运行之前可能提不出他的作业时间、将要使用的全部设备。
b.用户作业必须等待，直到所有资源满足时才能投入运行。
c.一个作业运行期间，对某些设备的使用时间很少，甚至不会用到。故这种分配技术对系统来说是浪费的。

3.6 死锁的避免

基本思想：动态防止发生死锁的方法
预防死锁和避免死锁的不同在于，前者所采用的分配策略本身就否定了必要条件之一，这样来保证死锁不可能发生；而后者是在动态分配资源的策略下采用某种算法来预防可能发生的死锁，从而拒绝可能引起死锁的某个资源请求。

有序资源分配法
系统若采用有序资源分配法，则需要为系统中的每一类资源分配唯一的号码，且系统要求每个进程：
- 对它所必须使用的而且属于某一类的所有资源，必须一次性申请完
- 在申请不同类的资源时，必须按照各类的编号依次申请。
  优缺点：
- 缺点：进程实际需要资源的顺序不一定与资源的编号相一致，因而仍然会造成资源的浪费。
- 优点：对资源进行合理的排序，这种方法是有一定实用价值的。
银行家算法：
存在一种算法总能作出正确的选择从而避免死锁单种资源的银行家算法(Dijkstra,1965)
- 问题描叙：
  一个领域的银行家，他向一群客户分别承若了一定的货款额度，具体而言，假设有4个客户，每个客户都有一个货款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只能保留10个单位的资金来为客户服务，而不是22个单位。这里的背景是，将客户比作进程，货款比作设备，银行家比作OS。
- 问题图示
- 算法：
  对每一个请求进行检查，检查如果满足它是否会导致不安全状态，若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个跟最大需求最近的客户，如果可以，则这笔投资认为是能够收回的，然后接着检查下一个跟最大需求最接近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。

3.7 死锁的检测与忽略

检测死锁并恢复
- a.基本思想：
  检测系统是否发生死锁,检测出死锁之后,寻找排除死锁的方法，使系统恢复正常的工作状态。
  本策略的指导原则是允许死锁产生，且当死锁发生时能检测出死锁，并有能力实现恢复。本策略的价值取决于死锁发生的频率和能够修复的程度。
  发现死锁的原理是考查某一时刻系统状态是否合理，即是否存在一组可以实现的系统状态，能使所有进程都得到它们所申请的资源而运行结束。
- b.检测死锁算法的基本思想：
  得到某时刻t时，系统中各类可利用资源得数目向量w(t)对于系统中的一组进程｛P1,P2,…Pi,…,Pn｝,找出那些对各类资源请求数目均小于系统现在所拥有的各类资源数目的进程。并认为这样的进程可以获得它们所需要的全部资源并运行结束。当它们运行结束后释放所占有的全部资源，从而使可用资源数目增加，这样的进程加入到可运行结束的进程序列之中，然后对剩下的进程再作上述考查，如果一组进程｛P1,P2,…,Pn｝中有几个进程不属于序列L中，则它们会被死锁。
- c.排除死锁的实用办法：
  - 将那些陷于死锁的全部进程一律撤消。
  - 逐个作废死锁进程，直至不再存在死锁为止。
  - 从死锁进程中逐个地强迫强占一些资源,直至死锁不再存在。
死锁的忽略
如果系统可能发生死锁，且不提供进行死锁的预防的方法、死锁的检测与恢复的机制，那么可能会出现这种情况：系统已经出现死锁，而又不知道发生了什么。这种情况下，死锁的发生会导致系统性能的下降，因为资源被不能运行的进程锁占有，而越来越多的进程会因为申请资源而进入死锁状态。最后整个系统停止工作需要人工重新启动。
由于检测死锁的算法太复杂，系统开销大，所以使用很少。实际中对死锁的检测常常由计算机操作员来处理。而不是由系统本身来完成。通常修复方法是人工抽去一些作业，释放它们占的资源，再重新启动系统。