第5章资源分配与调度.

第5章资源分配与调度资源分配与调度资源管理概述资源分配的机构和策略死锁1资源分配与调度——主要内容资源管理概述资源分配与调度——资源管理概述21.资源管理的目的提供一种简单而有效地使用资源的方法，充分发挥各种资源的作用。(1)保证资源的高利用率(2)在“合理”时间内使所有顾客有获得所需资源的机会(3)对不可共享的资源实施互斥使用(4)防止由资源分配不当而引起的死锁资源分配与调度——资源管理概述21622.资源管理功能：解决资源分配、存取、保护问题(1)资源数据结构的描述包含资源的物理名、逻辑名、类型、地址、分配状态等(2)确定资源的分配原则(调度原则)决定资源应分给谁，何时分配，分配多少等问题。(3)实施资源分配执行资源分配；资源收回工作。(4)存取控制和安全保护对资源的存取进行控制并对资源实施安全保护措施。资源分配与调度——资源管理概述33.资源资源的静态分配和动态分配(1)资源的静态分配系统对作业一级采用资源静态分配方法。系统在调度作业时，根据作业所需资源进行分配；并在作业运行完毕时，收回所分配的全部资源。这种分配通常称为资源的静态分配。(2)资源的动态分配系统对进程一级采用资源动态分配方法。系统在进程运行中，根据进程提出的资源需求，进行资源的动态分配和回收。这种分配通常称为资源的动态分配。资源分配与调度——资源管理概述44.虚拟资源(1)操作系统对资源区分二种不同的概念物理资源(实资源)虚拟资源(逻辑资源)：如虚拟存储器(2)目的方便用户使用资源可动态分配，提高资源利用率资源分配与调度——资源管理概述5进程调度地址映射逻辑设备虚拟设备文件逻辑结构资源分配与调度——资源管理概述进程设备分配动态映射虚存(程序地址空间)磁盘空间分配文件目录查找资源类别物理资源虚拟(逻辑)映射处理机CPU存储器主存设备外部设备信息文件物理结构(3)计算机系统中的物理资源与虚拟资源分析资源分配结构和策略资源分配与调度——资源分配机构和策略6(1)资源描述器①资源描述器定义描述各类资源的最小分配单位的数据结构称为资源描述器rd。如：主存分区分配方法中，最小分配单位为主存分区。磁盘最小分配单位：扇区②资源描述器内容资源名、资源类型、最小分配单位的大小、地址、分配标志、描述器链接信息、存取权限、密级、存取时间资源分配与调度——资源分配机构和策略1.资源分配的机构20KB052KB66KB130KB230KB256KB1主存程序4程序1程序3OS内存分布状况图7(2)资源信息块①资源信息块定义描述某类资源的请求者、可用资源和该类资源分配程序等必要信息的数据结构。②资源信息块内容请求者队列可利用资源队列资源分配程序等待队列头指针可利用资源队列头指针资源分配程序入口地址资源分配与调度——资源分配机构和策略资源信息块示意图8(3)资源信息块例中央处理机资源信息块内容PCB1PCB2PCBk进程调度程序ready_q_start可用处理机信息scheduler_addrCPU资源分配与调度——资源分配机构和策略中央处理机资源信息块示意图92.资源分配策略(1)常用的资源分配策略①先请求先服务每一个新产生的请求均排在队尾；当资源可用时，取队首元素，并满足其需要。排序原则：按请求的先后次序排序。资源分配与调度——资源分配机构和策略表头按请求的先后次序先后按自然顺序排列的资源请求队列10②优先调度对每一个进程指定一个优先级；每一个新产生的请求，按其优先级的高低插到相应的位置；当资源可用时，取队首元素，并满足其需要。排序原则：按优先级的高低排序。资源分配与调度——资源分配机构和策略表头按按优先级的高低排序高低按优先级高低排列的资源请求队列11③针对设备特性的调度策略ⅰ调度的目标当有大量I/O请求时，降低完成这些I/O服务的总时间。资源分配与调度——资源分配机构和策略ⅱ例：讨论对磁盘访问的调度，有如下5个请求。柱面号盘面号块号521538535406327712ⅲ移臂调度总是选取与当前移动臂前进方向上最近的那个I/O请求，使移臂距离最短。资源分配与调度——资源分配机构和策略对磁盘访问的5个请求，按移臂调度应作如下调整。柱面号盘面号块号277521538535406313ⅳ旋转调度总是选取与当前读写头最近的那个I/O请求，使旋转圈数最少。资源分配与调度——资源分配机构和策略对磁盘访问的5个请求，再按旋转调度应作如下调整。柱面号盘面号块号2775215355384063死锁资源分配与调度——死锁14(1)死锁的例设备共享进程p1、p2共享一台打印机和一台输入机时刻t1：进程p1——占用打印机，进程p2——占用输入机；时刻t2：进程p1——又请求输入机，进程p2——又请求打印机。时刻t2后，系统出现僵持局面，即出现了死锁现象。资源分配与调度——死锁1.什么是死锁15(2)用信号灯的P、V操作描述死锁设进程p1与进程p2共享一台打印机(r1)和一台输入机(r2)，用信号灯的p、v操作表示资源的申请和释放。信号灯设置——s1：表示r1可用，初值为1s2：表示r2可用，初值为1讨论两种资源请求序列，哪种情况可能产生互相死等的局面。程序描述如下：资源分配与调度——死锁16程序描述1程序描述2进程p1进程p2进程p1进程p2p(s1)；p(s2)；p(s1)；p(s2)；占用r1占用r2占用r1占用r2v(s1)；v(s2)；p(s2)；p(s1)；又占用r2又占用r1p(s2)；p(s1)；占用r2占用r1v(s1)；v(s2)；v(s2)；v(s1)；v(s2)；v(s1)；程序描述2，有可能出现死锁。资源分配与调度——死锁17(3)什么是死锁在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，称这一组进程产生了死锁。资源分配与调度——死锁2.死锁的起因和条件(1)引起死锁的原因①系统资源不足②进程推进顺序非法18资源分配与调度——死锁(2)死锁图解A申请B申请释放A释放B获得A获得BQ进程P和Q申请A死锁不可避免P和Q申请BP进程获得A获得B释放A释放BB申请A申请19资源分配与调度——死锁①互斥条件涉及的资源是非共享的，即为临界资源。②不剥夺条件进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。③部分分配进程每次申请它所需要的一部分资源。在等待一新资源的同时，进程继续占用已分配到的资源。④环路条件存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求。(3)产生死锁的必要条件有环有死锁有环无死锁死锁定理如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。21资源分配与调度——死锁3.系统状态分析(1)初始状态描述假定一个系统包括n个进程和m类资源，表示如下①一组确定的进程集合p={p1，p2，…，pi，…，pn}②一组不同类型的资源集合r={r1，r2，…，rj，…，rm}③矢量w说明各类可利用资源的总的数目w={w1，w2，…，wj，…，wm}22资源分配与调度——死锁(2)资源请求矩阵在时刻t资源请求矩阵，表示如下11121m21222mn1n2nmdddddddddd(t)=dij表示进程pi还需要j类资源的数目23资源分配与调度——死锁(3)资源分配矩阵在时刻t资源分配矩阵，表示如下11121m21222mn1n2nmaaaaaaaaaa(t)=aij表示进程pi已占有j类资源的数目什么情况下系统是安全的？当进程请求某类资源时，进程对该类资源的需求量小于当前时刻系统所拥有的该类资源的数目，那么满足进程的这次请求，系统是安全的。24资源分配与调度——死锁4.解决死锁问题的策略①不考虑此问题：（鸵鸟政策）②让死锁发生：允许死锁发生，但能检测出死锁并实现修复。③不让死锁发生：为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一条件1：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备。条件2：容易否定，可制定相应的规则即可，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。对CPU可进行可剥夺分配，对某些设备如打印机则行不通。条件3：很容易否定，只要分配策略上规定一个进程（或程序）一次将所需资源一次申请到位。用完后释放。可以全部用完后，统一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁。但资源利用率不高。实际上系统不采用部分分配，也就破坏了环路条件。条件4：在进行资源分配前考虑是否会出现环路，预测是否会发生死锁，只要有这种可能性就不予分配。综上所述，解决死锁问题的策略包括：采用静态分配方法来预防死锁采用有控分配方法来避免死锁当死锁发生时检测出死锁，并设法修复。25资源分配与调度——死锁5.死锁的预防(1)静态预防死锁的方法在作业调度时为选中的作业分配它所需要的所有资源，当资源一旦分配给该作业后，在其整个运行期间这些资源为它独占。一个用户（进程）在程序运行之前可能很难提出将要使用的全部设备设备（资源）的浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用到，例如，一个分枝语句。讨论：这种方法破坏了产生死锁的必要条件中的哪一条？25资源分配与调度——死锁(2)动态预防死锁的方法在动态分配资源的策略下，采用某种算法来预防可能发生的死锁，从而拒绝可能引起的某个资源请求。---破坏环路条件。①有序资源分配法系统中所有资源都给定一个唯一的编号，所有分配请求必须以上升的次序进行。当遵守上升次序的规则时，若资源可用，则予以分配；否则，请求者等待。系统要求申请进程：对它所必须使用的而且属于同一类的所有资源，必须一次申请完；在申请不同类资源时，必须按各类设备的编号依次申请。例如：进程PA使用资源的顺序是R1，R2；进程PB使用资源的顺序是R2，R1；若采用动态分配有可能形成环路条件，造成死锁。采用有序资源分配法：R1的编号为1，R2的编号为2；PA申请次序应是：R1，R2；PB申请次序应是：R1、R2，这样就破坏了环路条件，避免了死锁的发生。26资源分配与调度——死锁②银行家算法DijkstraE.W于1968年提出。银行家算法银行家拥有一笔周转资金客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款银行家应谨慎的贷款，防止出现坏帐用银行家算法避免死锁操作系统（银行家）操作系统管理的资源(周转资金)进程（要求贷款的客户）26资源分配与调度——死锁银行家算法的算法思想申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时，由系统审查现有该类资源的数目是否能满足当前进程的最大需求量，如能满足就予以分配，否则拒绝。27资源分配与调度——死锁③银行家算法例系统拥有某类资源10个，现有进程P、Q、R共享该类资源，它们申请该类资源的最大需求量如下。进程最大需求量已占有资源P84Q42R92现申请资源个数111当这些进程动态申请资源时，按银行家算法应如何分配，能保证不发生死锁。目前占有量最大需求量尚需要量P1143P2462P3583系统剩余量2已分配的资源最大需求量ABCABCP1010753P2200322P3302902P4211222P5002433剩余资源ABC332P2申请（1，0，2）能否分配？为什么？P5申请（3，3，0）能否分配？为什么？P1申请（0，2，0）能否分配？为什么？27资源分配与调度——死锁③安全状态按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。能找到安全序列的状态为安全状态。安全状态的例：进程最大需求已分配可用P11053P242P392安全序列：p2p1p3进程最大需求已分配可用P11052P242P3933安全——不安全的转换上例中，若P3再申请一台，则不安全（3）死锁的检测与修