操作系统之资源分配与死锁.ppt

第三章 资源分配与死锁,目录,2,1、资源数据结构的描述 包含资源的物理名、逻辑名、类型、地址、分配状态等 信息。2、确定资源的分配原则(调度原则)决定资源应分给谁，何时分配，分配多少等问题。3、实施资源分配 执行资源分配；资源收回工作。4、存取控制和安全保护 对资源的存取进行控制并对资源实施安全保护措施。,3.1 资源管理概述,一.资源管理功能,3,1、资源的静态分配 系统对作业一级采用资源静态分配方法。系统在调度作业时，根据作业所需资源进行分配；并在作业运行完毕 时，收回所分配的全部资源。这种分配通常称为资源的静态分配。2、资源的动态分配 系统对进程一级采用资源动态分配方法。系统在进程运行中，根据进程提出的资源需求，进行资源 的动态分配和回收。这种分配通常称为资源的动态分配。,3.1 资源管理概述,二.资源的静态分配和动态分配,4,1、操作系统对资源区分二种不同的概念物理资源(实资源)虚拟资源(逻辑资源)2、目的方便用户使用资源可动态分配，提高资源利用率,3.1 资源管理概述,三.虚拟资源,5,进程调度,地址映射,逻辑设备虚拟设备,文件逻辑结构,进程,设备分配动态映射,虚存(程序地址空间),磁盘空间分配文件目录查找,3、计算机系统中的物理资源与虚拟资源分析,3.1 资源管理概述,三.虚拟资源,6,1、资源描述器 资源描述器定义 描述描述各类资源的最小分配单位的数 据结构称为资源描述器 rd。如：主存分区分配方法中，最小分配单 位为主存分区。资源描述器内容 资源名、资源类型、最小分配单位的大 小、地址、分配标志、描述器链接信息、存取权限、密级、存取时间,一.资源分配的机构,内存分布状况图,3.2 资源管理的机制和策略,7,2、资源信息块 资源信息块定义 描述某类资源的请求者、可用资源和该类资源分配程序等 必要信息的数据结构。资源信息块内容,3.2 资源管理的机制和策略,一.资源分配的机构,8,3、资源信息块例 中央处理机资源信息块内容,3.2 资源管理的机制和策略,一.资源分配的机构,9,二.资源分配策略1、先请求先服务每一个新产生的请求均排在队尾；当资源可用时，取队首元素，并满足其需要。排序原则：按请求的先后次序排序。,3.2 资源管理的机制和策略,10,对每一个进程指定一个优先级；每一个新产生的请求，按其优先级的高低插到相应的 位置；当资源可用时，取队首元素，并满足其需要。排序原则：按优先级的高低排序。,3.2 资源管理的机制和策略,二.资源分配策略2、优先调度策略,三.磁盘存储器管理,数据的组织和格式：（1）基本概念：盘面号（磁头号）：0 M-1；柱面号（磁道号）：0 L-1；扇区号：1 N；,3.2 资源管理的机制和策略,数据的组织和格式：,（2）存储容量：（3）扇区编址方式 CHS（柱面/磁头/扇区）方式：磁道（柱面），磁头，扇区 DOS中称为“绝对扇区”表示法。LBA（相对扇区号）方式：以磁盘第一个扇区（0柱面、0磁头、1扇区）作为LBA的 0扇区,=磁头数磁道（柱面）数每道扇区数 每扇区字节数,三.磁盘存储器管理,3.2 资源管理的机制和策略,数据的组织和格式：,(4)LBA扇区号与（柱面号、磁头号、扇区号）间的转换：若L、M、N分别表示一个磁盘的柱面数（磁道数）、盘面数（磁头数）、扇区数，则第i柱面、j磁头、k扇区所对应的LBA扇区号为：若知道LBA扇区号，则对应的柱面号、磁头号、扇区号分别是：,LBA=(i*M*N)+(j*N)+k-1,柱面号：i=int(LBA/(M*N)磁头号：j=LBA mod(M*N)/N 扇区号：k=LBA mod(M*N)mod N+1,三.磁盘存储器管理,3.2 资源管理的机制和策略,2.磁盘的类型,1)固定头磁盘;2)移动头磁盘：串行读写,3.磁盘访问时间,1)寻道时间Ts：把磁头移动到指定磁道上所经历的时间。Ts=mn+s m：一般磁盘：0.20.3；高速磁盘：m0.1 S：磁臂启动时间，约为2ms 3ms,三.磁盘存储器管理,3.2 资源管理的机制和策略,3)传输时间Tt 把数据从磁盘读出或向磁盘写入数据所经历的时间。,因此，可将磁盘访问时间Ta表示为：,3.磁盘访问时间,2)旋转延迟时间Tr 这是指定扇区移动到磁头下面所经历的时间。Tr=1/2r,三.磁盘存储器管理,3.2 资源管理的机制和策略,4.磁盘调度 当有大量磁盘I/O请求时，恰当选择调度顺序，以降低完成这些I/O服务的总时间。,移臂调度：当同时有多条磁道访问请求时，确定磁道访问顺序，以减少平均寻道时间旋转调度：当一条磁道上有多个扇区访问请求时，确定扇区访问顺序，以减少旋转延迟时间,三.磁盘存储器管理,3.2 资源管理的机制和策略,（1）先来先服务FCFS(First-Come,First Served),假设当前磁道在100号磁道，磁头正向磁道号增加的方向（由外向里）移动。现依次有如下磁盘请求队列：,23，,376，,205，,132，,61，,190，,29，,4，,40,则磁盘调度顺序和寻道距离为：,23，,376，,205，,132，,61，,190，,29，,4，,40,Ts=,(100-23),+(376-23),+(376-205),+(205-132),+(132-61),+(190-61),+(190-29),+(29-4),+(40-4),平均寻道距离=Ts/9,三.磁盘存储器管理,5.移臂调度算法：,假设当前磁道在100号磁道，磁头正向磁道号增加的方向（由外向里）移动。现依次有如下磁盘请求队列：,23，,376，,205，,132，,61，,190，,29，,4，,40,则磁盘调度顺序和寻道距离为：,23，,376，,205，,132，,61，,190，,29，,4，,40,Ts=,(132-100),+(190-132),+(205-190),+(205-61),+(61-40),+(40-29),+(29-23),+(23-4),+(376-4),问题：（1）不能保证平均寻道距离最短；（2）会产生饥饿现象；（3）影响磁盘的机械寿命。,（2）最短寻道时间优先算法SSTF,三.磁盘存储器管理,5.移臂调度算法：,（3）扫描(SCAN)算法：（又称为电梯算法）（1）欲访问磁道与当前磁道的距离；（2）磁头当前的移动方向。,假设当前磁道在100号磁道，磁头正向磁道号增加的方向（由外向里）移动。现依次有如下磁盘请求队列：,23，,376，,205，,132，,61，,190，,29，,4，,40,则磁盘调度顺序和寻道距离为：,23，,376，,205，,132，,61，,190，,29，,4，,40,Ts=,(132-100),+(190-132),+(205-190),+(376-205),+(376-61),+(61-40),+(40-29),+(29-23),+(23-4),三.磁盘存储器管理,5.移臂调度算法：,（4）N-Step-SCAN算法,“磁臂粘着”现象算法思想：将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列；而每处理一个子队列时又采用SCAN算法。,例如：23，,376，,205，,132，,61，,190，,29，,4，,40,若子队列长度N=4，则分成3个队列：,23,376,205,132,61,190,29,40,4,FCFS,SCAN,三.磁盘存储器管理,5.磁盘调度算法：,（5）FSCAN算法 该算法实质上是N步SCAN算法的简化，它只将磁盘请求队列分成两个子队列：由当前所有请求磁盘形成的队列，由磁盘调度按SCAN算法进行处理。在扫描期间，将新出现的所有磁盘I/O请求，放入另一个等待处理的请求队列。,23,376,205,132，61,190,29，40,4,三.磁盘存储器管理,5.移臂调度算法：,13,当同一磁道（柱面）上有多个扇区请求时，总是选取与当前读写头最近的那个I/O请求，使旋转圈数最少。,例：对磁盘访问的5个请求，若磁头在1号柱面，先按SCAN算法做移臂调度，再进行旋转调度，则调度顺序如下：,柱面号 盘面号 块号 2 7 7 5 2 1 5 3 5 5 3 8 40 6 3,三.磁盘存储器管理,5.旋转调度算法：,柱面号 盘面号 块号 5 2 1 5 3 8 5 3 5 40 6 3 2 7 7,柱面号 盘面号 块号 2 7 7 5 2 1 5 3 8 5 3 5 40 6 3,一.死锁的定义,例1：两辆车过单车道桥的僵局：,3.3 死锁的基本概念,例2.竞争外部设备。设系统中有打印机、扫描仪各一台，进程A、B的申请如下：,扫描仪,进程A,进程B,打印机,一.死锁的定义,3.3 死锁,3.3 死锁的基本概念,一组进程中，每个进程都无限等待被该组进程中另一进程所占有的且永远无法释放的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。,关于死锁的一些结论：参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。,一.死锁的定义,3.3 死锁,3.3 死锁的基本概念,产生死锁的原因有两点：(1)竞争资源：为多个进程所共享的资源不够，引起它们对资源的竞争而产生死锁；(2)进程推进顺序不当：在进程运行过程中，请求资源和释放资源的顺序不当，也会产生死锁。,二.产生死锁的原因,3.3 死锁,3.3 死锁的基本概念,1、竞争资源引起的死锁可剥夺性资源：是指系统中那些已被进程占用但又可被其它进程所抢占的系统资源。如处理机、内存区等。非剥夺性资源：是指系统中那些已被进程占用后便不能被其它进程所抢占的系统资源。如：打印机、扫描仪等。,一.产生死锁的原因,3.3 死锁,3.3 死锁的基本概念,例.竞争外部设备。设系统中有打印机、扫描仪各一台，进程A、B的申请如下：,扫描仪,进程A,进程B,打印机,(1)竞争非剥夺性资源的例子,一.产生死锁的原因,1、竞争资源引起的死锁,执行顺序1：P1:Release(S1);Request(S3);P2:Release(S2);Request(S1);P3:Release(S3);Request(S2);执行顺序2：P1:Request(S3);Release(S1);P2:Request(S1);Release(S2);P3:Request(S2);Release(S3);,(2)竞争临时性资源：临时性资源是指由一个进程产生的被另一进程使用一短暂时间后便无用的资源。也称消耗性资源。如消息,中断信号，同步信号等,不会“死锁”,“死锁”,（1）进程推进顺序合法：如按曲线、和不会产生“死锁”,2.进程推进顺序不当引起的死锁,P2,P1,一.产生死锁的原因,（2）进程推进顺序非法：如曲线，产生“死锁”。,区域D称为“死锁区”,P2,P1,2.进程推进顺序不当引起的死锁,一.产生死锁的原因,二.产生死锁的必要条件,1.互斥条件：2.请求和保持条件：3.不剥夺条件：4.环路等待条件：资源分配图 这四个必要条件中只要有一个条 件不满足，都不会形成“死锁”,3.3 死锁的基本概念,预防与避免死锁 检测与解除死锁,3.4 处理死锁的基本方法,一.预防死锁：,1、静态预防死锁的方法 静态分配资源：在作业调度时为选中的作业分配它所需要的所有资源，当 资源一旦分配给该作业后，在其整个运行期间这些资源为它独占。缺点：1）资源利用率低；2）进程的运行可能被推迟；,一.预防死锁,2、动态预防死锁的方法：采用有序资源分配策略：将所有的系统资源按类型进行线性排队，并赋予不同的序号；所有进程对资源的请求应严格按资源序号递增顺序提出。,优点：较之前面两种方法资源利用率高，系统吞吐量大。缺点：(1)为系统中各种资源类型分配序号时，必须相对稳定，从而限制了 新设备的增加；(2)会出现作业使用的资源顺序与系统规定的顺序不同的情况，造成资 源的浪费,二.避免死锁,1、系统安全状态（1）安全状态定义 所谓安全状态，是指系统能按某种进程顺序(P1,P2,，Pn)(称P1,P2,Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。,3.4 处理死锁的基本方法,1、系统安全状态（2）安全状态之例 我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：,二.避免死锁,3.4 处理死锁的基本方法,1、系统安全状态（3）由安全状态向不安全状态的转换 如果不按照安全顺序分配资源，则系统可能由安全状态进入不安全状态。例：假定系统有三个进程P1、P2和P3，有12台磁带机。进程 最大需求量 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 在T0时刻P3又申请了一台磁带机，若将剩余3台中的一台分配给P3 则系统会进入不安全状态。为什么？,已分配 还需要 可用 5 5 2 2 2 3 6,二.避免死锁,3.4 处理死锁的基本方法,2、利用银行家算法避免死锁,避免死锁算法中最有代表性的算法是Dijkstra E.W 于1968年提出的银行家算法：它的模型基于一个小城镇的银行家，该算法可描述如下：假定一个银行家拥有资金，数量为，被N个客户共享。银行家对客户提出下列约束条件：,每个客户必须预先说明自己所要求的最大资金量；每个客户每次提出部分资金量申请和获得分配；如果银行满足了某客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内全部归还银行。,二.避免死锁,3.4 处理死锁的基本方法,（1）银行家算法中的数据结构,可利用资源向量Availablem。其中的每一个元素代表一类可利用的资源数目 Availablej=K，则表示系统中现有Rj类资源K个。最大需求矩阵Max1.n,1.m 该矩阵定义了系统中n个进程对m类资源的最大需求。Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。,2、利用银行家算法避免死锁,二.避免死锁,3.4 处理死锁的基本方法,分配矩阵Allocation1.n,1.m 该矩阵表示系统中每个进程当前已分配到的每类资源数量。Allocationi,j=K，表示进程i当前已分得Rj类资源的数目为K。需求矩阵Need1.n,1.m 该矩阵表示每个进程尚需的各类资源数。Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。,Needi,j=Maxi,j-Allocationi,j,请求向量Requesti of integer;某进程申请需要某类资源的资源数,（1）银行家算法中的数据结构,2、利用银行家算法避免死锁,二.避免死锁,当进程Pi提出资源申请Requesti时，系统执行下列步骤：若RequestiNeedi,转；否则错误返回；若RequestiAvailable，转；否则，表示尚无足够资源，Pi须等待；系统尝试把资源分配给进程Pi，并修改以下数据结构：Available:=Allocationi:=Needi:=执行安全性算法：检查此次资源分配后，系统是否处于安全状态。若安全，则将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,Available-Requesti;,Allocationi+Requesti;,Needi-Requesti;,（2）银行家算法描述,2、利用银行家算法避免死锁,二.避免死锁,设置两个临时向量：1）工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;2）Finishn:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false;当有足够资源分配给进程时，再令Finishi=true。,（3）安全性算法描述,2、利用银行家算法避免死锁,二.避免死锁,从进程集合中找到一个能满足下述条件的进程：1）Finishi=false;2）Needi,jWorkj；若找到，执行步骤，否则，执行步骤；当进程Pi获得资源后，可顺利执行，直至完成，并释放 出分配给它的资源，故应执行：Workj=Finishi=go to step;如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态,Workj+Allocationi,j;,true;,（3）安全性算法描述,2、利用银行家算法避免死锁,二.避免死锁,例1：假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。,（1）T0时刻的安全性；（2）P1请求资源：Request1（1，0，2）；,（4）银行家算法举例,2、利用银行家算法避免死锁,进程,资源,情况,1 2 20 1 14 3 16 0 07 4 3,3 3 25 3 27 4 37 4 510 4 7,2 0 02 1 10 0 23 0 20 1 0,5 3 27 4 37 4 510 4 710 5 7,P1P3P4P2P0,truetruetruetruetrue,Finish,由于T0时刻存在安全序列P1,P3,P4,P2,P0,故此时系统是安全的。,（2）当P1请求资源：Request1（1，0，2）时：Request1（1，0，2）Need1（1，2，2）Request1（1，0，2）Available（3，3，2）试分配资源后，修改数据结构。对试分配后状态进行安全性检查：,进程,资源,情况,0 2 00 1 14 3 16 0 07 4 3,2 3 05 3 27 4 37 4 510 4 7,3 0 22 1 10 0 23 0 20 1 0,5 3 27 4 37 4 510 4 710 5 7,P1P3P4P2P0,truetruetruetruetrue,Finish,由于此时存在安全序列P1,P3,P4,P2,P0,故系统是安全的，可为P1分配上述资源。,（3）当P4请求资源：Request4（3，3，0）时：Request4（3，3，0）Need4（4，3，1）成立；Request4（3，3，0）Available（2，3，0）不成立，故让P4等待。,（4）当P0请求资源：Request0（0，2，0）时：Request0（0，2，0）Need0（7，4，3）成立；Request0（0，2，0）Available（2，3，0）成立；试分配资源后，修改数据结构。对试分配后的状态进行安全性检查：由于Available（2,1,0）已不能满足任何进程的需要，故系统进入不安全状态，所以不能为P0分配资源，而应恢复原来的状态，让P0等待。,课堂讨论：假设有两类资源A和B，A类资源10个，B类资源14个，当前系统的资源分配情况如下表所示。根据分配表，回答下面两个问题：请填写系统的需求矩阵。使用银行家的算法，确定系统是否死锁状态？如果不死锁给出安全序列，如果死锁给出死锁的四个条件。,0 47 04 01 04 2,需求矩阵如下：进程 Need A B P0 0 4 P1 7 0 P2 4 0 P3 1 0 P4 4 2答：系统处于安全状态。安全序列为：P0，P3，P2，P1，P4,三.死锁的检测,1、资源分配图(Resource Allocation Graph),每类资源有多个时的情况,3.4 处理死锁的基本方法,简化资源分配图，如果资源分配图能完全简化，则系统中没有死锁；否则系统存在死锁。资源分配图简化过程：,2.死锁定理,（1）在资源分配图中，找出一个既不阻塞又非独立的进程节点Pi，如果找到转（2）；否则转（3）；,（2）去掉Pi的所有边，使其成为一个独立节点，并转（1）；,（3）判断是否所有节点都成为独立节点？如果是，称为资源分配图能完全简化，系统无死锁；否则系统存在死锁。,三.死锁的检测,3.4 处理死锁的基本方法,例1：,三.死锁的检测,有死锁,无死锁,例2：,（1）数据结构：可利用资源向量Availablem;资源分配矩阵Allocationn,m;资源请求向量Requesti；工作向量Work=Available 进程集合L：独立进程节点的集合,3.死锁检测算法：,三.死锁的检测,3.4 处理死锁的基本方法,3.死锁检测算法：,（2）算法描述：L=Li|Allocationi=0 Requesti=0For all Li L do for all RequestiWork do Work=Work+Allocationi;Li L;Deadlock=!(L=P1,P2,P3,Pn);,三.死锁的检测,（1）进程进行资源请求时；（2）周期性检测；如SQL SERVER（3）根据CPU的使用效率检测。,4.死锁检测时机,三.死锁的检测,四.死锁的解除,前提是能检测出死锁,当前系统中使用的解除死锁的办法有两种：(剥夺资源，撤消进程),剥夺资源：使用挂起/激活机制撤销进程 撤销进程的原则：（1）撤销的进程数最少；（2）撤销代价最小：进程优先数；进程类的外部代价；进程运行代价,3.4 处理死锁的基本方法,死锁习题举例：,某系统中有5个并发进程，每个进程都需要4个同类资源才能运行完成并释放出所占用的资源，则系统不会发生死锁的最少资源数是_个。答案：162.某系统中有11台打印机，N个进程共享这些打印机资源，每个进程要求3台，当N的值不超过_时，系统不会发生死锁。答案：5,