资源分配与调度

1、第五章 资源分配与调度,（一） 资源管理功能 （二） 资源分配的机构和策略 （三） 死锁概念,5.1 资源管理功能,5.1.1 资源管理功能 1. 目的： 保证资源的高利用率； 在“合理”时间内使所有顾客有获得所需资源的机会； 对不可共享的资源实施互斥使用； 防止由资源分配不当而引起的死锁。,2. 资源管理的任务： 资源管理的描述数据结构 确定资源的分配原则（调度原则） 执行资源分配（实施） 存取控制和安全保护,5.1.2 资源的静态分配和动态分配,1. 资源的静态分配 系统对作业一级采用资源静态分配方法。 当一个进程（或程序）运行前，将它要求的资源一次分配给该进程，直到该进程终止，释放其占用

2、的所有资源。 效率太低 2. 资源的动态分配 系统对进程一级采用资源动态分配方法。 系统在进程运行中，根据进程提出的资源需求，进行资源的动态分配和回收。 资源利用率提高，但有可能造成死锁,5.2 资源分配的机构和策略,5.2.1 资源分配机构 1. 资源描述器 （1） 什么是资源描述器 描述各类资源的最小分配单位的数据结构 如：主存的最小分配单位：在分页分配中主存页面 磁盘的最小分配单位：磁盘面中的一个扇区 （2）资源描述器的内容 资源名、资源类型、 最小分配单位的大小、最小分配单位的地址、分配标志 描述器链接信息、存取权限、密级 最后一次存取时间、记帐信息,2. 资源信息块,（1） 什么是资

3、源信息块 描述某类资源的请求者、可用资源情况和该类资源分配程序等必要信息的数据结构。 （2） 资源信息块的内容,（3） 中央处理机资源信息块,5.2.2 资源分配策略,1. 先请求先服务（FIFO策略） 排序原则：按请求的先后次序排序。 每个新产生的请求均排在队尾，而当资源可用时，资源分配程序从队列中选取第一个请求，并满足其需要。,适用范围：系统中的一切资源。 优点：简单、系统开销小。 缺点：有时显得不合理，系统无法进行干预。,2. 优先调度,在优先调度策略下，对于每一个进程（或作业）要指定一个优先级，优先级反映了进程要求处理的紧迫程度。 排序原则：按优先级的高低排序。 每个新产生的请求，按优

4、先级的高低插到相应的位置。而当资源可用时，选取队列中第一个请求，并满足其需要。 优先级的确定：主要由系统来确定，并可动态改变。 使用范围：由于系统开销大，主要适用于系统中的紧缺资源。便于资源的动态分配。,3、适应调度 4、均衡调度 5、针对设备特性的调度 移臂调度 旋转调度,5.3 死锁,5.3.1 什么是死锁 1. 死锁的例子 （1） 设备共享 进程PA、PB，共享一台打印机和一台磁带机 时刻t1：进程PA占用打印机 进程PB占用磁带机 时刻t2：进程PA又请求磁带机 进程PB又请求打印机 问：以后会发生什么情况？,两个进程并发执行时，当P1进程占用R1、P2进程占用R2时，P1要求R2，由

5、于P2已占有R2而得不到，P1进程只有等待；P2申请R1，由于P1已占有R1而得不到，P2进程只有等待，就出现了死等的情况。,2,（2） 用信号灯的P、V操作描述死锁,信号灯设置： S1：表示R1可用，初值为1 S2：表示R2可用，初值为1 讨论两种资源请求序列：,2. 什么是死锁,死锁简单的定义： 两个或两个以上的进程等候着一个永远不会发生的事件时所取的一种系统状态。 教材上关于死锁的定义： 两个或两个以上并发进程，如果每个进程持有某种资源，而又等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，每个进程都占用了一定的资源，但又都不能向前推进。这种现象称为死锁。,5.3.2

6、 死锁的起因和条件,1. 引起死锁的原因 死锁的产生与资源分配策略和并发进程执行的速度有关,2. 死锁的起因和条件,(1)引起死锁的原因 进程竞争资源，而资源不足 当系统中供多个进程共享的资源不足以同时满足进程的需要时，就可能引起进程对资源的竞争而产生死锁 进程推进顺序不合适 在进程运行过程中，若请求和释放资源的顺序不当，可能会导致进程死锁,有打印机5台，N个进程竞争使用，每个进程同时使用2台打印机，则N取哪些值时，系统不会死锁？,设系统某类资源有m个，有n个进程，所有进程对资源的最大需求数据之和小于m+n时，系统不会发生死锁,N=1或2时，系统资源数大于进程要求 N=3或4时，系统资源数小于

7、进程要求，最好情形是先每个进程分配1个资源，此时剩余2个（或1个）资源，只要分配给任何一个进程，该进程就可以完成，从而释放所有资源 N=5时，当每个进程分配一个打印机，系统已无剩余资源，每个进程都没有获得需要的资源数，不能完成，也不能释放其所占资源，死锁,(2) 死锁的必要条件,资源的分类 根据资源是否可抢占 可抢占资源：指资源占有者进程虽然仍需要使用资源，但系统可以根据某原则强行将该资源剥夺，分配给其他进程 不可抢占资源：指资源一旦被进程占有，只有当进程不再使用而主动释放资源外，其他进程不得强行抢占其资源 根据资源使用方式 共享资源：指资源同时可以为多个进程共同使用 独享资源：指资源同一时刻

8、只能为一个进程单独使用 通常进程因竞争独享、不可抢占资源而发生死锁。,研究死锁问题的前提,操作系统中的死锁基于如下假定： 任意一个进程要求资源的最大数量不超过系统能提供的最大量 如果一个进程在执行中提出的资源要求能得到满足，那么它一定能在有限的时间内结束 一个资源在任何时刻最多只被一个进程所占有 一个进程一次申请一个资源，且只在资源得不到满足时才处于等待状态 一个进程结束时释放它所占有的全部资源 系统具有有限个进程和资源,产生死锁的四个必要条件：,1. 互斥条件 一个资源一次只能被一个进程所使用 2. 不可剥夺条件 一个资源仅能被占有它的进程释放，而不能被其他的进程强行抢占 3. 部分分配 一

9、个进程已占有分给它的资源，但仍然要求其他资源 4.环路条件 系统中存在一个由若干个进程形成的环形请求链，其中每一个进程均占有若干种资源中的某一种，同时还要求下一个进程所占有的资源,3. 死锁的预防和避免,基本点：破坏死锁的某一个必要条件 (1) 解决死锁问题的几个策略 为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。,条件2 不可剥夺条件：容易否定，制定相应的规则即可。如当一个进程（程序）申请某资源被拒，则必须释放已占用的资源，如需要再与其它所需资源一起申请,条件1 互斥条件：难以否定，但可采用相应的技术（如假脱机技术），即利用可共享使用的设备模拟非共享的设备,条件4（环路条件）：实际

10、上不采用部分分配，也就破坏了环路条件。,条件3 部分分配：也很容易否定。规定一个进程（或程序）一次将所需资源一次申请到位，用完后释放。 全部用完后，可以统一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁。,处理死锁的三种基本方法： 死锁的预防 死锁的避免 死锁的检测和恢复,(2) 静态预防死锁的方法,在作业调度时为选中的作业分配它所需的所有资源，当资源一旦分配给该作业，在其整个运行期间这些资源为它独占。 讨论： （1） 这种方法破坏了死锁的必要条件中的哪一条？ （2）这种方法的资源利用率高不高？为什么？,这种方法安全而简单，但设备的使用效率太低： 1. 一个用户（进程）在程

11、序运行之前很难提出要使用的全部设备需求； 2. 用户作业必须等待，直到所有资源满足时才能投入运行； 3. 设备（资源）浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用到（如分支语句）。,(3) 动态避免死锁的方法,为了提高设备的利用率，可采用动态的设备分配方法，但应设法避免发生死锁，若存在发生死锁的可能性，则拒绝分配。 预防死锁： 采用的分配策略本身就否定了产生死锁的四个必要条件之一，这就保证了不会发生死锁； 死锁避免： 在动态分配资源的策略下采用某种算法来预防可能发生的死锁，从而拒绝可能产生死锁的某个资源请求。,系统中所有资源按某种规则统一编号，所有分配请求以上升次

12、序进行。若资源可用，则预以分配；否则，请求者等待。 讨论：这种方法破坏了死锁必要条件中的哪一条？为什么？,a. 有序资源分配法,优点：资源利用率提高 缺点： 由于资源序号必须相对稳定，限制新设备类型的增加 资源申请次序与实际使用次序不一致时，利用率不高,例如：进程PA，使用资源R1，R2；进程PB，使用资源R2，R1；若采用动态分配有可能形成环路条件，造成死锁。采用有序资源分配法：R1的编号为1，R2的编号为2； PA：依次申请R1，R2 PB：依次申请R1，R2 这样就破坏了环路条件，避免了死锁的发生。,b. 银行家算法,避免死锁算法中最有代表性的算法是Dijkstra E.W于1968年提

13、出的银行家算法： 银行家（操作系统）拥有一笔周转资金（系统资源） 客户（进程）要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款 银行家应谨慎的贷款，防止出现坏帐 检查申请者对资源的最大需求量，若系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。 这样申请者就可以很快完成其计算，然后释放它占用的资源，从而保证系统中的所有进程都能完成，避免死锁的发生。,单种资源的银行家算法,对每个请求进行检查，是否会导致不安全状态。若是，则不满足该请求；否则便满足 检查状态是否安全的方法：看他是否有足够的资源满足一个距最大需求最近的客户，如此反复下去。如果所有投资最终都

14、能被收回，则该状态是安全的，最初的请求可以批准,多资源银行家算法,实际系统中可能有多种资源，每类资源有不同的个数 多资源银行家算法中定义 分配矩阵 请求矩阵 请求向量 可用资源向量（剩余资源向量）,总的资源E 已分配资源P 剩余资源A,多资源银行家算法,查找请求矩阵是否有一行，其未被满足的设备数均小于或等于向量A。如果找不到，则系统将死锁，因为任何进程都无法运行结束 若找到这样一行，则可以假设它获得所需的资源并运行结束，将该进程标记为结束，并将资源加到向量A上 重复以上两步，直到所有进程都标记为结束。若达到所有进程结束，则状态是安全的，否则将发生死锁,假定系统有5个进程P0,P1,P2,P3,P4和三种资源A,B,C,每一种资源的数量分别为10，