资源分配与调度
资源管理概述
资源：应用程序执行时所需要的全部硬件、软件和数据。
资源管理的目标：
- 保证资源的高利用率。
- 在“合理”时间内使所有顾客有获得所需资源的机会。
- 对不可共享的资源实施互斥使用。
- 防止由资源分配不当而引起的死锁。
资源管理的任务
(1) 资源数据结构的描述
包含资源的物理名、逻辑名、类型、地址、分配状态等信息。
(2) 确定资源的分配原则(调度原则)
决定资源应分给谁，何时分配，分配多少等问题。
(3) 实施资源分配
执行资源分配；资源收回工作。
(4) 存取控制和安全保护
对资源的存取进行控制并对资源实施安全保护措施。
资源的静态分配和动态分配
静态分配
系统对作业一级采用资源静态分配方法。系统在调度作业时，根据作业所需资源进行分配；并在作业运行完毕时，收回所分配的全部资源。这种分配通常称为资源的静态分配。
动态分配
系统对进程一级采用资源动态分配方法。系统在进程运行中，根据进程提出的资源需求，进行资源的动态分配和回收。这种分配通常称为资源的动态分配。
（1）作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。
（2）一个作业可由多个进程组成，且必须至少由一个进程组成，反过来则不成立。
（3）作业的概念主要用在批处理系统中，像UNIX这样的分时系统中就没有作业的概念。而进程的概念则用在几乎所有的多道程序系统中。
虚拟资源
物理资源(实资源)
虚拟资源(逻辑资源)：用户使用的逻辑资源，这是经过操作系统改造的、使用方便的虚资源，而不是物理的、实际的资源。
可以理解为操作系统将资源进行了封装，用户无需关心具体的资源在哪里，只要关心操作系统向用户提供的虚资源的描述。
资源分配结构和策略
资源管理的实质是资源管理的机制和资源管理的策略。
机制：进行资源分配所必须的基本设施和部件，包括描述资源状态的数据结构、保证不可共享资源互斥使用的同步机构以及对不能立即得到满足的资源请求进行排队的各种资源队列的结构。
策略：资源分配的原则。
资源分配的机构
资源描述器
描述各类资源的最小分配单位的数据结构称为资源描述器rd（resource descriptor）。如：主存分区分配方法中，最小分配单位为主存分区。资源描述器描述了资源的特性和该资源的管理方式。
用于资源分配的最重要的信息是这一资源分配单位是可用的还是已分配的。
- 若它具有N个资源分配器，则有N个资源描述器。这些描述器的组织是个重要问题。
- 描述器的组织方式取决于资源分配单位的数量和数量是否可变这一特征。
- 如果数量不可变，使用表结构。
- 如果数量可变，使用队列结构。
- 如果数目变化范围可知且不大，使用数组。
资源描述器的内容：
资源名、资源类型、最小分配单位的大小、地址、分配标志、描述器链接信息、存取权限、密级、存取时间
资源信息块
描述某类资源的请求者、可用资源和该类资源分配程序等必要信息的数据结构。
资源分配程序包括了资源分配程序和资源回收程序。当有进程请求资源的时候，先去资源分配程序中看看有没有资源，没有的话，将进程加入到等待资源队列中；当进程执行释放资源命令时，使用资源回收程序，将释放的资源加入到可利用资源的队列中。
资源分配策略
对某类资源而言，在多个资源有多个请求者申请的情况下，资源分配的策略包括选择请求者的策略和选择资源的策略两种。
选择请求者的策略：即资源分配策略，即在众多请求者中选一个满足条件的请求者的原则。
选择资源的策略：是在同等资源间选择一个满足条件的资源的原则。
具体实现：体现在队列的排队原则上。
资源分配的时机
- 当请求者发出一个明确的资源请求命令时；
- 当处理机空闲时；
- 当一个存储区被释放变为空闲时；
- 当一个外存设备发生完成中断时。
先请求先服务策略
每一个新产生的请求均排在队尾；当资源可用时，取队首元素，并满足其需要。
排序原则：按请求的先后次序排序。（有饿死现象！）
优先调度策略
对每一个进程指定一个优先级，优先级反映了进程要求处理的紧迫程度；
每一个新产生的请求，按其优先级的高低插到相应的位置；
当资源可用时，取队首元素，并满足其需要。
排序原则：按优先级的高低排序。
缺点：因为优先级不同，会存在插队的状况。所以会消耗时间，导致效率下降
针对设备特性的调度策略
目的是为了当有大量I/O请求时，降低完成这些I/O服务的总时间。
移臂调度
总是选取与当前移动臂前进方向上最近的那个I/O请求，使移臂距离最短。
移臂的方向是由外向里，即柱面号由小到大
旋转调度
总是选取与当前读写头最近的那个I/O请求，使旋转圈数最少。
几种移臂调度算法
最短寻道时间优先算法（SSTF）
从等待访问者中挑选寻找时间最短的（也就是离得最近的）那个请求先执行
缺点：可能会引起读写头在盘面上的大范围移动，可能会推迟请求的服务导致无限拖延
扫描算法（SCAN，即电梯调度算法）
磁头前进方向上的最短查找时间优先算法。
很大程度上消除了SSTF的不公平性
循环扫描算法（CSCAN）
就是在电梯算法的基础上，一个方向找完了，回到起点再找（电梯算法是一个方向找完了转身反方向找）
死锁
在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，称这一组进程产生了死锁。
死锁的起因和条件
死锁的原因
①系统资源不足
②进程推进顺序非法
产生死锁的必要条件
①互斥条件
涉及的资源是非共享的，即为临界资源。
②不剥夺条件
进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。
（根据操作系统的特性，例如windows系统就是不可剥夺的）
③部分分配
进程每次申请它所需要的一部分资源。在等待一新资源的同时，进程继续占用已分配到的资源。
④环路条件
存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求。
解决死锁问题的策略
破坏产生死锁的四个必要条件之一
- 采用静态资源分配方法——预防死锁。
- 采用有控资源分配方法——避免死锁
- 死锁的检测与忽略
死锁的预防和避免
静态预防死锁的方法
在作业调度时为选中的作业分配它所需要的所有资源，当资源一旦分配给该作业后，在其整个运行期间这些资源为它独占。
动态避免死锁的方法
有序资源分配法（破坏了部分分配和循环等待）
系统中所有资源都给定一个唯一的编号，所有分配请求必须以上升的次序进行。当遵守上升次序的规则时，若资源可用，则予以分配；否则，请求者等待。（缺点：资源浪费！）
银行家算法
申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时，由系统审查现有该类资源的数目是否能满足当前进程的最大需求量，如能满足就予以分配，否则拒绝。
死锁的检测与忽略
检测：算法复杂，开销很大
忽略：后患无穷
问题
假设一个可移动磁头的磁盘具有 200个磁道，其编号为0~199,当它刚刚结束了 125道的存取后，现正在处理143道的服务请求，假设系统当前的请求序列以请求的先后次序排列如下: 86、147、91、177、150、102、175、130。试问对以下几种磁盘IO请求调度算法而言，满足以上请求序列，磁头将分别如何移动?
（1） 先来先服务算法（FCFS）
（2） 最短寻道时间优先调度（SSTF）
（3） 扫描算法（SCAN）
（4） 循环扫描算法（CSCAN）
答：
（1） FCFS：143→86→147→91→177→150→102→175→130；
（2） SSTF：143→147→150→130→102→94→91→86→175→177；
（3） SCAN：143→147→150→175→177→130→102→94→91→86；
（4） C-SCAN：143→147→150→175→177→86→91→94→102→130。
5-9 三个进程共享四个同类资源，这些资源的分配与释放只能一次一个，已知每一进程最多需要两个资源，试问该系统会发生死锁吗？为什么？
答：该系统不会发生死锁。
因为最坏情况是每个进程都占有一个资源，申请第二个资源，而此时系统中还剩一个资源，不管这个资源分给哪个进程，都能满足它的资源要求，因此它能在有限时间内运行结束而释放它所占有的两个资源，这两个资源又可以分配给另外两个进程，使它们能够运行结束，所以系统不会发生死锁。
5-10 p个进程共享m个同类资源，每一个资源在任一时刻只能供一个进程使用，每一进程对任一资源都只能使用一有限时间，使用完便立即释放，并且每个进程对该类资源的最大需求量小于该类资源的数目，设所有进程对资源的最大需求数目之和小于p+m，试证在该系统中不会发生死锁。
解：采用“反证法”，假定max(i)为第i个进程最大资源需求量，need(i)为第i个进程还需要的资源量，alloc(i)为第i个进程已分配的资源量，则
max(i)<=m
max(i)=need(i)+alloc(i)
max(1)+L+ max(p)=(need(1)+ L…+need(p))+(alloc(1)+ L…+alloc(p))<p+m
若发生死锁，则需要满足下面两个条件，
① 全部分配，alloc(1)+…+alloc(p)=m；② 所有进程无限等待
由①②可得， need(1)+…+need(p)<p
则死锁后，p个进程需要的资源小于p，则一定存在进程i，need (i) = 0，进程已获得全部资源，进程i 可以执行完，同假设发生矛盾，所以不会发生死锁。
5-11图5.9 表示一带闸门的运河，其上有两架吊桥，吊桥坐落在一条公路上，为使该公路避开一块沼泽地而其横跨运河两次。运河和公路的交通都是单方向的，运河的基本运输由驳船担负。在一艘驳船接近吊桥A 时就拉汽笛警告，若桥上无车辆，吊桥就吊起，直到驳船尾部通过该桥为止，对吊桥B按同样次序处理
(1) 一艘典型驳船的长度为200 米，当它在河道航行时是否会产生死锁？若会，其理由是什么？
(2) 如何能克服一个可能的死锁？请想出一个防止死锁的办法。
(3) 如何利用信号灯的P、V 操作实现车辆和驳船的同步？
(1) 答：驳船长200 米，当驳船通过了A 桥，其船头到达B 桥，请求B 桥吊起，而此时它的尾部占据A 桥，若这个时候B 桥及B桥到A 桥之间的公路都被汽车占据，而汽车又要求通过A 桥。这样驳船和汽车都无法前进，形成死锁的局面。
(2) 答：方案之一。可规定资源按序申请和分配，从而破坏了死锁的循环等待条件，防止死锁的发生。规定如B 桥的序号小于A 桥的序号，驳船和汽车都必须先申请序号小的资源B 桥，申请得到满足后，再申请序号大的资源A 桥。
(3) 答：将每台车的行驶看作是进程，则有Auto1，Auto2，LAutoi i个汽车进程。将每条驳船的航行看作是进程，则有Ship1，Ship2，LShipj个驳船进程。桥A和桥B对车和船为互斥资源。
1 | main{ |
5-14在采用银行家算法管理资源分配的系统中，有A、B、C三类资源可供5个进程P1、P2、P3、P4、P5共享。3类资源的总量为(17, 5, 20)，即A类17个，B类5个，C类20个。假设T0时刻各进程对资源的需求和分配情况如下表所示。
（1） 现在系统是否处于安全状态？如是，给出一个安全序列。
（2） T0时刻，如果进程P4和P1依次提出A、B、C资源请求（2,0,1）和（0,2,0），系统能否满足它们的请求?请说明原因。
答：（1）系统处于安全状态，如P4→P2→P3→P5→P1。
（2）不能满足。由于P4与P1提出请求后，A、B、C剩余（0，1，2），此时A类无，只能等待拥有足够A类资源的进程结束释放A类资源，别的进程才能执行，而此时P4需（0，2，0），P3需（0，0，6），而剩余（0，1，2），不能满足要求，产生死锁。
1． 设有一个售票大厅，可容纳200人购票。如果厅内不足200人则允许进入，超过则在厅外等候；售票员某时只能给一个购票者服务，购票者买完票后就离开。试问：
（1） 购票者之间是同步关系还是互斥关系？
答：互斥关系。
用P、V操作描述购票者的工作过程。
1 | semaphore empty=200; |