资源分配与调度

资源管理概述

资源 ：应用程序执行时所需要的全部硬件、软件和数据。

为什么要对资源进行管理？

• 管理好各种资源是计算机系统的重要职责。
• 随着软硬件的发展，操作系统要管理的软硬件资源和种类越来越多；
• 用户的需求和应用量也在不断增长。

资源管理的目标

• 保证资源的高利用率。
• 在“合理”时间内使所有顾客有获得所需资源的机会。
• 对不可共享的资源实施互斥使用。
• 防止由资源分配不当而引起的死锁。
• 这些目标之间需要平衡！

资源管理的任务

• 资源数据结构的描述
  应包含该类资源最小分配单位的描述信息，如资源的物理名、逻辑名、类型、地址、分配状态等信息。
• 确定资源的分配原则 (调度原则)
  决定资源应分给谁，何时分配，分配多少等问题。
• 实施资源分配
  执行资源分配；资源收回工作。
• 存取控制和安全保护
  对资源的存取进行控制并对资源实施安全保护措施。

资源资源的静态分配和动态分配

• 资源的静态分配
  系统对作业一级采用资源静态分配方法。系统在调度作业时，根据作业所需资源进行分配；并在作业运行完毕 时，收回所分配的全部资源。这种分配通常称为资源的静态分配。
• 资源的动态分配
  系统对进程一级采用资源动态分配方法。 系统在进程运行中，根据进程提出的资源需求，进行资源的动态分配和回收。这种分配通常称为资源的动态分配。

虚拟资源
操作系统对资源区分二种不同的概念

• 物理资源 (实资源)
• 虚拟资源 (逻辑资源) ：用户使用的逻辑资源，这是经过操作系统改造的、使用方便的虚资源，而不是物理的、 实际的资源。

目的

• 方便用户使用
• 资源可动态分配，提高资源利用率

计算机系统中的物理资源与虚拟资源分析

资源表格	物理资源	虚拟(逻辑)	映射
处理机	CPU	进程	进程调度
存储器	主存	虚存（程序地址空间）	地址映射
设备	外部设备	逻辑设备、虚拟设备	设备分配、动态映射
信息	文件物理结构	文件逻辑结构	磁盘空间分配、文件目录查找

资源分配结构和策略

资源管理的实质

• 资源管理的实质是资源管理的机制和资源管理的策略。
• 机制：进行资源分配所必须的基本设施和部件，包括描述资源状态的数据结构、保证不可共享资源互斥使用的同步机构以及对不能立即得到满足的资源请求进行排队的各种资源队列的结构。
• 策略：给出了实现该功能的内涵，设计资源分配的原则。

资源分配的机构

资源描述器

资源描述器 定义：描述描述各类资源的最小分配单位的数 据结构称为资源描述器 rd（resource descriptor）。 如：主存分区分配方法中， 最小分配单位为主存分区。

资源描述器内容 ：资源名、资源类型、最小分配单位的大 小、地址、分配标志、描述器链接信息、 存取权限、密级、存取时间。

• 若它具有N个资源分配器，则有N个资源描述器。这些描述器的组织是个重要问题。
• 描述器的组织方式取决于资源分配单位的数量和数量是否可变这一特征。
  • 如果数量不可变，使用表结构。
  • 如果数量可变，使用队列结构。
  • 如果数目变化范围可知且不大，使用数组。

资源信息块（rib, resource information block）

资源信息块定义：描述某类资源的请求者、可用资源和该类资源分配程序等必要信息的数据结构。

资源信息块内容

资源信息块示例：

资源分配策略

• 对某类资源而言，在多个资源有多个请求者申请的情况下，资源分配的策略包括选择请求者的策略和选择资源的策略两种。
• 选择请求者的策略：即资源分配策略，即在众多请求者中选一个满足条件的请求者的原则。
• 选择资源的策略：是在同等资源间选择一个满足条件的资源的原则。
• 具体实现：体现在队列的排队原则上。

资源分配的时机

• 请求者发出一个明确的资源请求命令时；
• 当处理机空闲时；
• 当一个存储区被释放变为空闲时；
• 当一个外存设备发生完成中断时。

常用的资源分配策略

• 先请求先服务
  • 每一个新产生的请求均排在队尾；
  • 当资源可用时，取队首元素，并满足其需要。 排序原则：按请求的先后次序排序。（有饿死现象！）
    
• 优先调度
  • 对每一个进程指定一个优先级，优先级反映了进程要求处理的紧迫程度；
  • 每一个新产生的请求，按其优先级的高低插到相应的位置；
  • 当资源可用时，取队首元素，并满足其需要。
    排序原则：按优先级的高低排序。
• 针对设备特性的调度策略
  • 移臂调度 ：总是选取与当前移动臂前进方向上最近的那个I/O请求，
    使移臂距离最短。
  • 旋转调度 ：总是选取与当前读写头最近的那个I/O请求，使旋转圈 数最少。

几种移臂调度算法

• 最短寻道时间优先算法（SSTF）
  • 从等待访问者中挑选寻找时间最短的那个请求先执行
  • 缺点：可能会引起读写头在盘面上的大范围移 动，可能会推迟请求的服务导致无限拖延
• 扫描算法（SCAN，即电梯调度算法）
  • 磁头前进方向上的最短查找时间优先算法
  • 很大程度上消除了SSTF的不公平性
  • 不仅要己组读写磁头的位置，还必须记住移动臂的当前前进方向
  • 当磁头刚从里向外移动过某一磁道时，恰有一进程访问此磁道，必须等待。
• 循环扫描算法(CSCAN)
  • 规定磁头单向移动，如果只是从里向外移动，当磁头移到最外的磁道并访问时，磁头立即返回到最里的欲访问磁道，即将最小磁道号紧接着最大磁道号循环，进行循环扫描。

死锁

死锁及起因

什么是死锁
在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否 则就不能向前推进。此时，称这一组进程产生了死锁。

引起死锁的原因

• 系统资源不足
• 进程推进顺序非法

产生死锁的必要条件

• 互斥条件
  涉及的资源是非共享的，即为临界资源。
• 不剥夺条件
  进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。
• 部分分配
  进程每次申请它所需要的一部分资源。在等待一新资源的 同时，进程继续占用已分配到的资源。

• 环路条件
  存在一种进程的循环链，链中的每一个进程已获得的资 源同时被链中下一个进程所请求。

  
  利用资源分配图可判断死锁。
  若图没有环，系统没有发生死锁；如果图有环，可能存在死锁。如果环涉及一组资源类型，而每个资源类型只有一个实例，呢么有环就意味着出现死锁，即环所涉及的进程发生了死锁。在这种情况下，环就是死锁存在的充分必要条件。

解决死锁问题的策略——破坏产生死锁的四个必要条件之一

• 采用静态资源分配方法——预防死锁。
• 采用有控资源分配方法——避免死锁
• 死锁的检测与忽略

死锁的预防

• 破坏互斥条件
  • 就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般“互斥”条件是无法破坏的。因此，在死锁预防里主要是破坏其他三个必要条件，而不去涉及破坏“互斥”条件。
• 破坏请求并保持条件
  • 在系统中不允许进程在已获得某种资源的情况下，申请其他资源。即要想出一个办法，阻止进程在持有资源的同时申请其他资源。有两种方法：
  • 方法一：所有进程在运行之前，必须一次性地申请在整个运行过程中所需的全部资源。这样，该进程在整个运行期间，便不会再提出资源请求，从而破坏了“请求”条件。系统在分配资源时，只要有一种资源不能满足进程的要求，即使其它所需的各资源都空闲也不分配给该进程，而让该进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件。
  • 该方法优点：简单、易行且安全。
  • 缺点：
    a.资源被严重浪费，严重恶化了资源的利用率。
    b.使进程经常会发生饥饿现象。
  • 方法二：要求每个进程提出新的资源申请前，释放它所占有的资源，然后再尝试一次获得所需的全部资源。
• 破环不可抢占条件
  • 允许对资源实行抢占。
  • 方法一：如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占有的资源，如果有必要，可再次请求这些资源和另外的资源。
  • 方法二：如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。只有在任意两个进程的优先级都不相同的条件下，该方法才能预防死锁。

• 破坏环路等待条件

  • 保证每一个进程在任何时刻只能占用一个资源，若要请求另外一个资源，它必须先释放第一个资源。
  • 将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出。这样做就能保证系统不出现死锁。

• 静态预防死锁的方法

  • 在作业调度时为选中的作业分配它所需要的所有资源，当资源一旦分配给该作业后，在其整个运行期间这些资源为它独占。
  • 一个用户在作业运行之前可能提不出其作业将要使用的全部设备
  • 用户作业的所有资源满足后才投入运行，实际上某些资源可能要到运行后期才会用到
  • 一个作业运行期间，某些设备的使用时间很少，甚至不会用到。
• 动态避免死锁的方法
  • 有序资源分配法
    系统中所有资源都给定一个唯一的编号，所有分配请求必须以上升的次序进行。当遵守上升次序的规则时，若资源可用，则予以分配；否则，请求者等待。（缺点：资源浪费！当有资源序列1234，实际访问序列为4321时，需要先请求1，在2，在3、4，但是123是较长时间后运行的，造成了资源的浪费。）
  • 银行家算法
    申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时，由系统审查现有该类资源的数目是否能满足当前进程的最大需求量，如能满足就予以分配，否则拒绝（缺点：要求每个进程必须事先说明对各类资源的最大需求，而且在系统运行过程中，考察每个进程对各类资源的申请需要花费较多的时间。此外，由于银行家算法总是考虑最坏情况，有时为了避免死锁，可能拒绝某一请求，实际上，即使该请求得到满足也不会出现死锁。过于谨慎以及开销较大是银行家算法的主要障碍）

死锁的检测和恢复

死锁检测

首先针对每种资源类型只有一个实例的情况。

构建资源分配图，采用深度优先遍历算法确定是否存在环路：依次将每一个节点作为一棵树的根节点，并进行深度优先搜索，如果再次碰到已经遇到过的节点，那么就算找到了一个环。如果从任何给定的节点出发的弧都被穷举了，那么就回溯到前面的节点。如果回溯到根并且不能再深入下去，那么从当前节点出发的子图中就不包含任何环。如果所有的节点都是如此，那么整个图就不存在环也就是说系统不存在死锁。

第二种情况是每种资源类型还有多个实例的情况。

构建向量矩阵，利用向量矩阵算法模拟资源分配。这种算法的第一步是寻找可以运行完毕的进程Pi，该进程的特点是它有资源请求并且该请求可被当前的可用资源满足(R矩阵第i行向量小于A)。这一选中的进程随后就被运行完毕，在这段时间内它释放自己持有的所有资源并将它们返回到可用资源库中（将C矩阵的第i行向量加到A）。然后这一进程被标记为完成。如果所有的进程最终都能运行完毕的话，就不存在死锁的情况。

假设n个进程，m种资源：

E=（E1,E2,…,Em）现有资源向量，

A=（A1,A2,…,Am）可用资源向量，

Cn*m当前分配矩阵，Rn*m请求矩阵，C(ij)表示进程i所持有的资源j的数量，R(ij)表示进程i所需要的资源j的数量。

Ej=Aj+C11+C21+……+Cn1

死锁检测：算法复杂，开销很大
忽略则后患无穷

死锁恢复

抢占：不通知原进程的情况下，将某一资源从一个进程强行取走给另一个进程使用，接着送回。

回滚：周期性对进程进行检查点检查，即将进程的状态写入一个文件以备以后重启，包括存储映象、资源状态，即哪些资源分配给了哪些进程。新的检查点不覆盖原有的文件，而是写到新文件中。检测到死锁时，从一个较早的检查点开始，将该进程复位到更早的状态。

杀死进程：杀死环中的一个或多个进程；杀死一个环外的进程以释放该进程的资源。（最好杀死可以从头开始重新运行且不会带来副作用的进程）