1、15.15.1 资源管理概述资源管理概述OSOS的资源：包括各种的资源：包括各种硬件资源硬件资源和和软件资源软件资源。根据对资源的根据对资源的使用方式使用方式，可将资源分为：，可将资源分为：共享资源。共享资源。如：如：CPUCPU、内存空间、磁头、内存空间、磁头、可重入的程序可重入的程序等等使用方式：使用方式：只让用，不让占只让用，不让占 独占资源。独占资源。如：如：打印机、卡片输入机打印机、卡片输入机 互斥的互斥的变量、队列、表格、文件变量、队列、表格、文件等等会修改会修改的数据的数据使用方式：使用方式：只要不释放，系统不能强行收回只要不释放，系统不能强行收回 2 一一资源管理的资源管理的一
2、般功能一般功能 1、构造描述资源的、构造描述资源的数据结构数据结构 操作系统通过这些数据结构而操作系统通过这些数据结构而 感知感知到资源的存在，并对资源进行到资源的存在，并对资源进行管理管理 这些数据结构，应包含描述资源的：这些数据结构，应包含描述资源的：物理名物理名(内部标识内部标识)、逻辑名逻辑名(用户定义的名称用户定义的名称)分配状态分配状态 类型、地址、等所有信息类型、地址、等所有信息 3 3.实施资源的实施资源的分配分配(及回收及回收)根据分配原则，将资源分配给请求的用户根据分配原则，将资源分配给请求的用户 并完成相应操作。并完成相应操作。如如:CPU：恢复现场恢复现场 内存：内存：
3、将程序调入内存、改内存分配标志将程序调入内存、改内存分配标志 独占资源：独占资源：上锁上锁 2.制定资源的制定资源的分配原则分配原则 决定资源应决定资源应先分给谁先分给谁(当有多个进程请求时当有多个进程请求时)何时分配，分配多少等问题何时分配，分配多少等问题 当资源使用完毕后，收回资源当资源使用完毕后，收回资源4 4.存取控制和安全保护存取控制和安全保护 对资源的存取进行控制对资源的存取进行控制 并对资源实施安全保护措施并对资源实施安全保护措施 (如：内存、文件的保护如：内存、文件的保护)5.其他的其他的特殊特殊功能功能 5 三三.资源的资源的分配方式分配方式(接受者接受者)1.静态分配静态分
4、配(接受者是接受者是作业作业)系统在调度一个作业运行时：系统在调度一个作业运行时：根据根据作业的需求作业的需求进行资源的分配进行资源的分配 在作业运行完毕后，才收回所分配的全部资源在作业运行完毕后，才收回所分配的全部资源2.动态分配动态分配(接受者是接受者是进程进程)在进程的运行过程中，根据在进程的运行过程中，根据进程提出的请求进程提出的请求 进行资源的分配进行资源的分配 资源资源使用完毕使用完毕(共享共享)、或或被进程释放被进程释放(独占独占)后后 回收该资源回收该资源 6 四四.资源的分类资源的分类 为了为了简化系统的设计简化系统的设计，对不同的资源，可采，对不同的资源，可采用不同的方式进
5、行分类。常用的分类方式有：用不同的方式进行分类。常用的分类方式有：1.硬件资源和软件资源硬件资源和软件资源 硬件：如处理机、主存、外部设备硬件：如处理机、主存、外部设备 软件：如文件、消息、数据结构软件：如文件、消息、数据结构 2.同类资源同类资源 如：打印机类、显示器类、内存区域等如：打印机类、显示器类、内存区域等.虚拟资源虚拟资源和实际资源和实际资源 虚拟资源和实际资源虚拟资源和实际资源用户用户独占资源独占资源A共享资源共享资源B请求请求用户操作用户操作系统完成系统完成实际实际资源资源虚拟虚拟资源资源目的：目的：提高独占资源的利用率提高独占资源的利用率 5.3 资源分配的策略资源分配的策略
6、 资源的分配策略资源的分配策略 指获得资源的先后次序指获得资源的先后次序 通常的实现方法是：通常的实现方法是：将资源的将资源的请求者请求者按某种原则按某种原则 形成一个具有形成一个具有先后次序先后次序的请求队列的请求队列 当资源可用时，当资源可用时，按队列的次序按队列的次序分配分配资源资源 91.先请求先服务先请求先服务(FIFO First In First Out)排序原则：排序原则：按请求的先后排序。按请求的先后排序。即：即：新产生的请求均排在新产生的请求均排在队尾队尾，分配时在，分配时在队首队首按请求的先后次序按请求的先后次序先先后后表头表头适用范围适用范围：系统中的一切资源系统中的一
7、切资源优点：优点：简单、次序不会改变，简单、次序不会改变，因此系统开销小因此系统开销小 缺点：缺点：有时显得有时显得不合理不合理、系统、系统无法无法进行进行干预干预 10 2.优先调度优先调度 系统对每个进程系统对每个进程(或作业或作业)，都，都指定一个指定一个优先级优先级 以反映请求资源的紧迫程度以反映请求资源的紧迫程度 表头表头按优先级的高低按优先级的高低高高低低 排序原则：排序原则：按优先级的高低排序按优先级的高低排序 即：即：新产生的请求，按其新产生的请求，按其优先级优先级的高低的高低 插入到队列中相应的位置插入到队列中相应的位置11优点：优点：系统可进行干预，以优化资源的使用方式系统
8、可进行干预，以优化资源的使用方式优先级的确定：优先级的确定：主要由系统定，并可动态改变。如：主要由系统定，并可动态改变。如：进程进程时间片到：时间片到：收回收回CPU，优先级降低，优先级降低 自动自动放弃放弃CPU：优先级升高优先级升高问题：问题：优先级相同的多个请求，如何排序？优先级相同的多个请求，如何排序？缺点：缺点：插入时要搜索队列、插入时要搜索队列、有时无法用队列实现有时无法用队列实现 适用的资源：适用的资源：由于系统开销较大，主要用于由于系统开销较大，主要用于 系统中的紧缺资源系统中的紧缺资源(如处理机如处理机)12多优先级队列多优先级队列 适用于：适用于：每个优先级上，有很多进程每
9、个优先级上，有很多进程 排序：排序：优先级不同，所排的队列不同优先级不同，所排的队列不同 优先级相同，在同一队列中按优先级相同，在同一队列中按FIFO排序排序 表头表头n按请求的先后次序按请求的先后次序先先后后 表头表头1按请求的先后次序先后 高高优优先先级级低低分配方式分配方式：仅当高优先级队列为空时仅当高优先级队列为空时 才考虑低优先级队列才考虑低优先级队列 优点：优点：减少了系统的排序开销减少了系统的排序开销3.针对设备特性的调度针对设备特性的调度 思想：分配策略制定的资源思想：分配策略制定的资源访问次序访问次序 应与资源的实际应与资源的实际使用次序使用次序相一致相一致 目的：目的：提高
10、资源访问的提高资源访问的平均速度平均速度 如：读、写磁盘上的多个扇区时如：读、写磁盘上的多个扇区时 对数据的访问，涉及到磁头定位的：对数据的访问，涉及到磁头定位的：柱面柱面(磁道磁道)：由磁头的直线运动得到由磁头的直线运动得到 耗时较长耗时较长 扇区：扇区：通过磁盘的旋转得到，通过磁盘的旋转得到，耗时较短耗时较短 盘面：盘面：由不同的磁头的得到，由不同的磁头的得到，不耗时不耗时 故要根据故要根据耗时的长短耗时的长短，依次决定访问次序，依次决定访问次序 例：不好的访问次序例：不好的访问次序 好的访问次序：好的访问次序：应在磁头的应在磁头的一次移动一次移动或磁盘的或磁盘的一周旋转一周旋转中完成中完
11、成 磁头磁头165.4 死锁的概念死锁的概念一一.什么是死锁什么是死锁 1.死锁的例子死锁的例子 (1)交通堵塞交通堵塞 17(2)不恰当的不恰当的 P 操作操作 当：当：mutex=1 full=0 empty=n 时时 p1()p2()while(生产未完成生产未完成)while(还要继续还要继续消费消费)p(mutex)生产一个产品；生产一个产品；p(full)；p(empty)；从缓冲区中取产品；从缓冲区中取产品；p(mutex)；v(mutex)；送一个产品到缓冲区；送一个产品到缓冲区；v(empty)；v(mutex)；v(full)；消费一个产品；消费一个产品；18 (3)设备的
12、共享设备的共享 例：设系统只有一台打印机例：设系统只有一台打印机(R1)，和一台光标，和一台光标 记阅读机记阅读机(R2)，由进程，由进程p1、p2 共享。共享。用信号灯的用信号灯的P、V操作，控制资源的申请和释放操作，控制资源的申请和释放 其信号灯的设置为：其信号灯的设置为：s1：表示：表示R1是否可用，初值为是否可用，初值为1 s2：表示：表示R2是否可用，初值为是否可用，初值为1 讨论资源分配的各个讨论资源分配的各个环节环节，看什么情况是，看什么情况是安全的安全的 先看资源的请求方式：先看资源的请求方式：19 进程进程P1 进程进程P2 p(s1)；p(s2)；申请申请R1 申请申请R2
13、 释放释放R1 释放释放R2 v(s1)；v(s2)；p(s2)；p(s1)；申请申请R2 申请申请R1 释放释放R2 释放释放R1 v(s2)；v(s1)；原因：原因：会同时封锁二个资源会同时封锁二个资源进程进程P1 进程进程P2p(s1)；p(s2)；申请申请R1 申请申请R2p(s2)；p(s1)；申请申请R2 申请申请R1 释放释放R1释放释放R2 v(s1)；v(s2)；释放释放R2释放释放R1 v(s2)；v(s1)；安全！安全！不足：不足：对同一个进程来说对同一个进程来说 资源的使用没有并发资源的使用没有并发 不安全！不安全！20进进 程程 P1 进进 程程 P2p(s1)；p(
14、s2)；申请申请R1 申请申请R2p(s2)；p(s1)；又申请又申请R2 又申请又申请R1 释放释放R1 释放释放R2 v(s1)；v(s2)；释放释放R2 释放释放R1v(s2)；v(s1)；思考思考：若二进程顺序执行，是否若二进程顺序执行，是否安全安全呢？呢？二进程如何执行，才会发生二进程如何执行，才会发生死锁？死锁？等待等待等待等待 由于系统已由于系统已没有没有它们它们所等待的资源所等待的资源 而占有资源的进程本身也在等待而占有资源的进程本身也在等待(无法无法释放资源释放资源)从而造成一种从而造成一种永久的相互等待永久的相互等待死锁死锁21 发生死锁的发生死锁的进程执行序列进程执行序列
15、:时刻时刻t1：进程进程 p1占用打印机占用打印机 时刻时刻t2：进程进程 p2占用光标记阅读机占用光标记阅读机 时刻时刻t3：进程：进程 p1又请求又请求光标记阅读机，光标记阅读机，等待等待 时刻时刻t4：进程进程 p2又请求打印机，又请求打印机，等待等待思考：思考：从从资源资源的使用角度来看的使用角度来看 对对死锁问题应如何进行死锁问题应如何进行一般性的描述一般性的描述呢？呢？22 2.什么是死锁什么是死锁 在在两个两个或多个并发进程中，如果每个进程都或多个并发进程中，如果每个进程都持有持有某种资源，而又都同时某种资源，而又都同时等待等待着着 别别的进程的进程释放它们保持着的资源释放它们保
16、持着的资源 即：即：在两个或多个并发进程中，所有的进程在两个或多个并发进程中，所有的进程 都都相互等待相互等待着其他的进程释放它们所持有的着其他的进程释放它们所持有的 某种资源，否则就不能向前推进某种资源，否则就不能向前推进 否则就不能向前推进否则就不能向前推进 称这一组进程产生了死锁称这一组进程产生了死锁(它们中它们中)23强调：强调：(1)死锁是在死锁是在n(n 2)个进程个进程 (不一定是所有进程不一定是所有进程)之间发生的一种状态之间发生的一种状态 这种状态一旦发生，就这种状态一旦发生，就永远无法改变永远无法改变?(2)系统中已没有死锁进程所等待的资源了系统中已没有死锁进程所等待的资源
17、了 (已被它们自己全占用了，或即使有也不够已被它们自己全占用了，或即使有也不够)(3)平常说系统平常说系统会死锁会死锁，是指：，是指：系统存在着死锁的可能系统存在着死锁的可能(由资源得请求序列定由资源得请求序列定)(但不一定会出现，但不一定会出现，由资源的实际使用定由资源的实际使用定)探讨：探讨：出现死锁的原因到底是什么呢？出现死锁的原因到底是什么呢？24N0R1R2R1R2 R2R1R2R1P1P2二二.死锁的起因和条件死锁的起因和条件(对设备的共享例对设备的共享例)阴影区：阴影区：资源被共享，进程的执行轨迹资源被共享，进程的执行轨迹不可能进入不可能进入从图中可看出：从图中可看出：1、死锁的
18、原因、死锁的原因 (1)系统的资源总数系统的资源总数各进程的资源总需求各进程的资源总需求 能进行一般性的表述吗能进行一般性的表述吗?因此：因此：死锁没有充分条件死锁没有充分条件!(2)进程推进的顺序不合理进程推进的顺序不合理 (对资源的对资源的申请次序申请次序、使用方式使用方式、占有方式占有方式)26 N0R1R2R1R2 R2R1R2R1P1P2 (1)避开危险区（一个进程同时得到避开危险区（一个进程同时得到全部的资源全部的资源）(2)将危险区变为阴影区将危险区变为阴影区(二进程二进程申请资源次序一致申请资源次序一致)(3)从危险区回退从危险区回退(强行收回强行收回某进程某进程占有的资源占有
19、的资源)2、解决死锁的方法：至少可看出三种、解决死锁的方法：至少可看出三种3.死锁的死锁的示意示意表示表示占有边占有边P2P1R2R1占有边占有边申请边申请边或或等待边等待边申请边申请边或或等待边等待边用途：用途：可描述资源的分配过程，若死锁则构成可描述资源的分配过程，若死锁则构成有向环有向环 可用可用资源资源 进程有向图进程有向图描述资源的使用状态描述资源的使用状态问题：问题：若若同一类型同一类型的资源有多个怎么表示？的资源有多个怎么表示？能否找到死锁的某些能否找到死锁的某些判别方法判别方法呢？呢？判别判别 (1)资源次序图的资源次序图的一般形式一般形式 当同一资源有多个时当同一资源有多个时
20、RiP1P2P3Rj 死锁的判别方法死锁的判别方法 资源的占有和申请可表示为：资源的占有和申请可表示为：4、死锁的判别方法、死锁的判别方法 (a)若资源分配图中若资源分配图中无环无环，则不存在死锁，则不存在死锁 (b)若资源分配图中若资源分配图中有环有环，且环内，且环内每类每类资源只资源只有有一个个体一个个体，则死锁发生，则死锁发生(此时此时环是充分条件环是充分条件)(c)若资源分配图中若资源分配图中有环有环，且环内有的资源有，且环内有的资源有多个个体多个个体，则无法判定死锁是否发生，则无法判定死锁是否发生(此时此时环不环不是充分条件是充分条件)(d)对资源分配图对资源分配图可进行化简可进行化
21、简，若化简后的图，若化简后的图中仍有环中仍有环(无法化简无法化简)，则，则环中的进程被死锁环中的进程被死锁 (2)死锁的判别方法死锁的判别方法例例1:P1P2P3R1R3R2R4？R1R2P1P2P3P4环环？R1R2P1P2P3P4 例例:化简后的状态：化简后的状态：死锁死锁？(a)若节点只有占有边，则若节点只有占有边，则可去掉占有边并释放资源可去掉占有边并释放资源 (b)当有了空闲的资源后，当有了空闲的资源后，等待边可变为占有等待边可变为占有边边R1R2P1P2P3P4 化化 简简 的的 方方 法法33(1)互斥条件互斥条件 涉及的资源为涉及的资源为临界资源临界资源RRPP 5、死锁的必要
22、条件死锁的必要条件(2)不剥夺条件不剥夺条件 进程占有的资源进程占有的资源 不能被其他进程强行剥夺不能被其他进程强行剥夺 (3)部分分配部分分配 每次仅申请一部分资源。在占有资源以后，每次仅申请一部分资源。在占有资源以后，还会继续申请新资源。只有还会继续申请新资源。只有不满足才等待不满足才等待 (4)环路条件环路条件 在进程与资源有向图中，存在在进程与资源有向图中，存在有向环有向环意义：意义：只要其中一条不成立，死锁就不会发生只要其中一条不成立，死锁就不会发生 34三三.死锁的预防和避免死锁的预防和避免 基本点：基本点：破坏死锁的某一个必要条件破坏死锁的某一个必要条件 (1)互斥条件互斥条件
23、(2)不剥夺条件不剥夺条件 (3)部分分配部分分配 (4)环路条件环路条件 问题：问题：破坏哪些必要条件是可行的呢？破坏哪些必要条件是可行的呢？35降低了设备的利用率降低了设备的利用率(只用很短时间，或根本不用只用很短时间，或根本不用)造成造成不必要的等待不必要的等待(一开始，可能并不用一开始，可能并不用)用户可能提不出所需的全部资源用户可能提不出所需的全部资源 1.静态静态预防预防死锁死锁(死锁不会发生死锁不会发生)在作业调度时，为选中的作业在作业调度时，为选中的作业 分配它所需要的分配它所需要的所有临界资源所有临界资源 在作业的整个运行期间，这些资源都为它在作业的整个运行期间，这些资源都为
24、它独占独占缺点缺点:思考：思考：(1)破坏了死锁必要条件中的哪一条？破坏了死锁必要条件中的哪一条？(2)资源利用率高不高？为什么？资源利用率高不高？为什么？2.有序资源分配法有序资源分配法(不让死锁出现不让死锁出现)按按资源类资源类对资源进行排序对资源进行排序 (每一类给定一个唯一的序号每一类给定一个唯一的序号)分配请求必须以分配请求必须以上升上升的次序进行；的次序进行；而且同一类型的资源必须一次申请完而且同一类型的资源必须一次申请完 思考思考：破坏了死锁的哪一个必要条件？破坏了死锁的哪一个必要条件？如何破坏的？如何破坏的？375 假定假定n个进程个进程(不妨设为不妨设为P1Pn)被死锁被死锁
25、 而且而且 Pi占有的资源占有的资源序号最高序号最高(如如5号号)P1PiPn 4 45 55 5则则Pi等待的资源等待的资源已被死锁的进程占有已被死锁的进程占有而根据分配原则：而根据分配原则：分配请求必须以分配请求必须以上升上升的次序进行的次序进行 而且而且同一类同一类的资源必须的资源必须一次一次申请完申请完 5矛盾！矛盾！38 若：资源的若：资源的使用次序使用次序与与资源类的排序资源类的排序不一致时不一致时 低序号资源必须低序号资源必须预先申请预先申请，降低了资源的利用率，降低了资源的利用率 (用户很难做到与用户很难做到与资源类的排序资源类的排序相一致相一致)例如一个进程的资源请求次序为：
26、例如一个进程的资源请求次序为：p(S2)占住占住R2 p(S5)使用使用R5 使用使用R2不足的地方？不足的地方？能否做到：能否做到：使用资源前才申请，而又不出现死锁呢？使用资源前才申请，而又不出现死锁呢？基本思想：基本思想：当系统现有的资源当系统现有的资源可保证可保证申请进申请进程完成时，才进行分配。否则，申请进程等待程完成时，才进行分配。否则，申请进程等待3.银行家算法银行家算法系统现有的资源系统现有的资源进程占有的资源进程占有的资源进程还需要的资源进程还需要的资源 进程占有的资源进程占有的资源进程还需要的资源进程还需要的资源系统现有的资源系统现有的资源 不不 进进 行行 分分 配配 进进
27、 行行 分分 配配Pi：Pj：银行家靠什么来积累财富呢银行家靠什么来积累财富呢？说明：说明：每次分配前每次分配前都要进行相应的都要进行相应的验证验证 P 0 8Q 0 4R 0 9系统资源数：系统资源数：10P 4 4系统资源数：系统资源数：8R 2 7Q 2 2系统资源数：系统资源数：4系统资源数：系统资源数：2思考：思考：这种方法破坏了哪一个必要条件这种方法破坏了哪一个必要条件?它是如何避免死锁的呢？它是如何避免死锁的呢？Q 4 0Q 系统资源数：系统资源数：0系统资源数：系统资源数：4P 8 0P 系统资源数：系统资源数：0系统资源数：系统资源数：8 例例:某系统有三个进程共享某系统有三
28、个进程共享同类型同类型的的10个资源个资源进程进程已占资源数已占资源数 还需资源数还需资源数 基本原理：基本原理：采用采用部分分配部分分配，且，且允许环允许环存在。但任何时候存在。但任何时候 都有一个都有一个占有资源的进程占有资源的进程是可完成的是可完成的进程的完成序列为：进程的完成序列为：Q P R.该进程完成后，该进程完成后，释放资源释放资源 则又有另一个进程是可完成的则又有另一个进程是可完成的如此重复，直到系统中所有的进程完成如此重复，直到系统中所有的进程完成 即：即：系统的系统的资源分配图，在任何时候资源分配图，在任何时候 都是都是可化简可化简的的(没有发生死锁没有发生死锁)如上例中：
29、如上例中：进程的申请序列为：进程的申请序列为：.R P QP 0 8Q 0 4R 0 9系统资源数：系统资源数：10P 4 4系统资源数：系统资源数：8R 2 7Q 2 2系统资源数：系统资源数：4系统资源数：系统资源数：2Q 4 0Q 系统资源数：系统资源数：0系统资源数：系统资源数：4P 8 0P 系统资源数：系统资源数：0系统资源数：系统资源数：8 进程进程已占资源数已占资源数 还需资源数还需资源数RPQ .要点：要点：(1)每次分配前都进行检测每次分配前都进行检测 (2)确保确保死锁不会发生死锁不会发生 (3)对进程的资源对进程的资源申请方式不进行任何限制申请方式不进行任何限制 不足：
30、不足：(1)还不够大胆。还不够大胆。为什么？为什么？有些还需要的资源，以后有些还需要的资源，以后可能不会再申请可能不会再申请 (2)对对每类资源每类资源都要检测，开销较大都要检测，开销较大 银行家算法的深入讨论银行家算法的深入讨论银行家算法的深入讨论银行家算法的深入讨论 进程请求资源时可分进程请求资源时可分三种情况三种情况进行处理：进行处理：(1)每类资源还需数都每类资源还需数都 系统的拥有数：系统的拥有数：分配分配 (2)每类资源还需数都每类资源还需数都 系统的拥有数：系统的拥有数：不分配不分配 (3)仅仅部分资源类部分资源类的还需数的还需数 系统的拥有数：系统的拥有数：则需判别则需判别系统
31、的状态是否安全系统的状态是否安全 若安全：若安全：不会死锁，分配不会死锁，分配 若不安全：若不安全：可能会死锁，不分配可能会死锁，不分配 问题：问题：如何对系统状态的安全进行判别呢？如何对系统状态的安全进行判别呢？系统状态的系统状态的图论图论判别方法判别方法 将进程的将进程的还需资源还需资源也作为申请边：也作为申请边：化简资源分配图化简资源分配图 化简后，若图中所有的进程都是孤立节点：化简后，若图中所有的进程都是孤立节点：则系统是则系统是安全安全的的 否则，系统是不安全的否则，系统是不安全的(可能会死锁可能会死锁)系统状态的系统状态的程序程序判别算法判别算法所需的数据结构所需的数据结构(t为时
32、间参数，参考为时间参数，参考P 113)进程进程向量：向量：P(t)=(p1、ppn)系统系统拥有的拥有的资源资源向量向量:W(t)=(r1、rrm)初值：初值：系统对每类系统对每类资源的资源的最大拥有最大拥有数数 所有所有进程占有进程占有资源资源矩阵：矩阵：A(t)=(行行:进程；进程；列列:资源资源)初值：初值：全为全为0 所有所有进程还需进程还需资源资源矩阵：矩阵：R(t)=(行行:进程；进程；列列:资源资源)初值：初值：各各进程对各类进程对各类资源资源的的最大最大需求数需求数 可完成的进程可完成的进程向量：向量：L(t)初值初值为空为空 算法的描述：对任一时刻算法的描述：对任一时刻 t
33、While （存在（存在 pi P(t)R(i,tP(t)R(i,t)W(t)W(t)P(t)=P(t)-P(t)=P(t)-pi L(t)=L(t)+L(t)=L(t)+pi W(t)=W(t)+W(t)=W(t)+A(i,t,t)If P(t)=系统是系统是安全的安全的，不会死锁，不会死锁 else 系统是系统是不安全的不安全的，其中的进程，其中的进程可能可能会死锁会死锁 对对预防预防和和避免避免死锁的评价死锁的评价 死锁出现的概率很小，而各种避免死锁的策略死锁出现的概率很小，而各种避免死锁的策略 都不同程度地都不同程度地降低了资源的利用率降低了资源的利用率 因此一般的小系统，只对用户因此
34、一般的小系统，只对用户频繁使用频繁使用的临界资源的临界资源 才进行环路检测才进行环路检测进程进程2文件文件B文件文件N进程进程3进程进程1文件文件A会被封锁会被封锁问题：问题：如果系统已如果系统已出现死锁出现死锁怎么办？怎么办？如如写文件写文件：若已上锁，进行环路检测，有环则：若已上锁，进行环路检测，有环则收回收回CPU 四、四、死锁的检测和恢复死锁的检测和恢复基本思想：基本思想：允许死锁发生允许死锁发生在适当的时机进行在适当的时机进行检测检测 若发现若发现死锁，则进行死锁，则进行恢复恢复 1、死锁检测的方法、死锁检测的方法 (1)限定限定进程进程等待的时间等待的时间 (2)由系统管理员，观测
35、进程的运行情况由系统管理员，观测进程的运行情况 (3)定期执行检测算法定期执行检测算法 (类似类似系统状态的判别系统状态的判别，但，但仅用仅用等待边等待边进行进行)2、死锁恢复的方法、死锁恢复的方法(解开环解开环)(1)逐个逐个撤销撤销死锁的进程，直到死锁打开死锁的进程，直到死锁打开优点：优点：简单、可行性较强简单、可行性较强缺点：缺点：部分进程重新执行，部分进程重新执行，代价较高代价较高(2)逐个收回逐个收回死锁进程占有的资源，直到死锁进程占有的资源，直到 死锁打开死锁打开(进程进程回退回退，要记住所有的，要记住所有的分配点分配点)(3)从从上次上次未发现未发现死锁的死锁的检测点检测点处，处
36、，重新执行重新执行 (要保存上个要保存上个检测点检测点现场现场)为什么可行？为什么可行？51 一、处理机调度的功能一、处理机调度的功能 从从资源管理资源管理的角度看，处理机调度的功包括：的角度看，处理机调度的功包括：维护有关的数据结构维护有关的数据结构 制订调度策略制订调度策略(谁能优先得到处理机谁能优先得到处理机)设计调度算法设计调度算法(实现调度策略实现调度策略)实施处理机的分配实施处理机的分配 (保护、恢复现场；修改保护、恢复现场；修改PCB、及有关的队列、及有关的队列)问题：问题：实现处理机的分配要经过那些过程呢？实现处理机的分配要经过那些过程呢？52 另外，另外，有些系统在有些系统在
37、内存紧张时，内存紧张时，会将某些会将某些进程进程的程序的程序在内、外存之间进行交换在内、外存之间进行交换 只有内存的程序只有内存的程序(进程进程)才能在才能在CPU上运行上运行内存内存二、二、处理机调度的分层处理机调度的分层运行运行就绪就绪等待等待外存外存 就绪态的进程有多个，就绪态的进程有多个，CPU分配分配给谁？给谁？53 因此，因此，处理机的调度可分为二层处理机的调度可分为二层(或三层或三层)(1)宏观调度宏观调度 对象为作业，故又称为对象为作业，故又称为作业调度作业调度 任务：任务：在已进入系统的作业中，按某种原则在已进入系统的作业中，按某种原则 挑选一个、或一批作业到内存执行挑选一个
38、、或一批作业到内存执行 完成的工作：完成的工作：为选中为选中作业的执行程序作业的执行程序建立进程建立进程 为其分配内存为其分配内存 分配其他需分配其他需静态分配静态分配的资源的资源 54 (2)微观调度微观调度 对象为进程，故又称为对象为进程，故又称为进程调度进程调度 任务：任务：确定确定哪个进程、在什么时候哪个进程、在什么时候 获得处理机，以及获得处理机，以及使用多长时间使用多长时间 完成的工作：完成的工作：选择一个选择一个在内存就绪在内存就绪的进程的进程 将其状态改为运行将其状态改为运行 若分时，给出运行的时间片若分时，给出运行的时间片 恢复该进程的现场恢复该进程的现场 55（3）中级调度
39、）中级调度 用于某些分时系统用于某些分时系统(如如Unix)中中 对象为进程对象为进程 任务：任务：确定哪些进程被允许确定哪些进程被允许参与参与处理机的竞争处理机的竞争 短期内短期内(如进程太多时如进程太多时)调整系统内存的负荷调整系统内存的负荷 完成的工作：完成的工作：56 换出：换出：在内存中最不可能得到在内存中最不可能得到CPU的进程的进程 首先首先:等待态等待态的就绪进程的就绪进程 其次：其次：优先级低优先级低且且驻驻留内存时间长留内存时间长的就绪进程的就绪进程 换入：换入：在进程调度程序挑选运行进程前在进程调度程序挑选运行进程前 换入在外存换入在外存驻驻留时间较长留时间较长的就绪进程
40、的就绪进程 说明：说明：对处理机的调度，不同的操作系统对处理机的调度，不同的操作系统 往往采用不同的实现方式往往采用不同的实现方式 57 一个一个作业，是一个用户的一次上机过程。因此作业，是一个用户的一次上机过程。因此 (1)最基本的作业：执行最基本的作业：执行一个可执行程序一个可执行程序 (2)复杂的作业：执行复杂的作业：执行一组一组可执行程序：可执行程序：如编译、连接、执行等如编译、连接、执行等 作业的表现形式：作业的表现形式：(1)批处理：用户提出的批处理：用户提出的作业申请作业申请 完成内容：在完成内容：在操作说明书操作说明书中所包含的所有中所包含的所有执行语句执行语句 (2)分时系统
41、：用户登录后的活动分时系统：用户登录后的活动(注销后结束注销后结束)完成内容：通过终端输入的一组命令完成内容：通过终端输入的一组命令(可执行的程序可执行的程序)58 二二、作业控制块作业控制块 操作系统对作业进行管理的数据结构，称为作业控操作系统对作业进行管理的数据结构，称为作业控制块制块(JCB)，它是一个作业存在的标志。它是一个作业存在的标志。JCB的主要内容包括：的主要内容包括：作作 业业 名名 对对资源的要求资源的要求 估计执行时间估计执行时间 最迟完成时间最迟完成时间 要求的主存量要求的主存量 要求外设的类型及台数要求外设的类型及台数 要求文件量和输出量要求文件量和输出量 59 资资
42、 源源 使使 用用 情况情况 进入系统的时间进入系统的时间 开始执行的时间开始执行的时间 已执行的时间已执行的时间 程序在主存的地址程序在主存的地址 占有的外部设备占有的外部设备 状状 态态 优优 先先 级级 作业类型作业类型(如：多如：多CPU、多、多IO、或均衡等、或均衡等)控制方式控制方式(如脱机、如脱机、联机联机)60 (1)设设 作业作业 i 的周转时间为的周转时间为 ti，则，则 ti=完成时间提交时间完成时间提交时间=tci tsi 或：或：ti=运行时间等待时间运行时间等待时间niti1n1t=四、四、作业调度性能的衡量作业调度性能的衡量(2)平均周转时间平均周转时间 1.周转
43、时间周转时间 从作业提交给系统，到完成所需的时间从作业提交给系统，到完成所需的时间意义：意义：描述了描述了作业作业 i 在系统中在系统中停留时间停留时间的长短的长短61例：例：作业作业 运行时间运行时间 等待时间等待时间(分钟分钟)1 5 25 30 2 20 20 40 调度算法调度算法对哪个作业有利呢？对哪个作业有利呢？(3)如何用于评价如何用于评价 对用户：对用户：周转时间越小越好周转时间越小越好(更方便更方便)对系统：对系统：平均周转时间越小越好平均周转时间越小越好(吞吐量大、吞吐量大、利用利用率高率高)原因？原因？因为因为周转时间周转时间中包含了中包含了运行时间运行时间，使评价出现误
44、差，使评价出现误差 平均周转时间平均周转时间同样同样也有类似的问题也有类似的问题 如何衡量更准确呢？如何衡量更准确呢？10 15 问题：问题：不够准确不够准确62 2.带权周转时间带权周转时间 (1)带权周转时间，指：带权周转时间，指：一个作业的一个作业的周转时间周转时间与其与其运行时间运行时间的比值的比值 wi=？(2)平均带权周转时间平均带权周转时间 t=精确度：精确度：二者都高于周转时间、平均周转时间二者都高于周转时间、平均周转时间 niwi1n1周转时间周转时间运行时间运行时间等待时间等待时间运行时间运行时间 3.其他的衡量方法其他的衡量方法 可用可用CPU利用率利用率、或、或系统吞吐
45、量系统吞吐量直接衡量直接衡量(无无满意度满意度)意义：意义：说明说明作业作业 i 在系统中的在系统中的相对等待时间相对等待时间=1+63 五、五、作业调度算法作业调度算法 1.先来先服务调度算法先来先服务调度算法(FCFSFCFS)特点：特点：简单，易实现简单，易实现 8.00 9.10 1.10 1 9.10 9.60 1.10 2.2 9.60 9.90 0.90 3 9.90 10.00 0.50 5 1 8.00 1.10 2 8.50 0.50 3 9.00 0.30 4 9.50 0.10平均周转时间平均周转时间 t=0.95 平均带权周转时间平均带权周转时间 w=2.8 提交提交
46、 执行执行 开始开始 完成完成 周转周转 带权周转带权周转 作业作业 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间例：求周转时间与带权周转时间例：求周转时间与带权周转时间(单位：单位：十进制小时十进制小时)(4)评价：评价：性能较差。性能较差。原因：原因：当当短作业排在长作业后面短作业排在长作业后面时，由于时，由于 等待时间变长等待时间变长(而运行时间不变而运行时间不变)，造成：，造成：平均平均周转时间、周转时间、平均平均带权周转时间变长带权周转时间变长短作业等待时间短作业等待时间长作业等待长作业等待 例：例：运行时间运行时间 周转时间周转时间而且短作业的而且短作业的相对等待时间
47、相对等待时间较长，较长，不满意不满意改进：改进：短作业排在长作业前面短作业排在长作业前面 2.短作业优先调度算法短作业优先调度算法 (1)策略策略 按作业按作业运行的时间运行的时间长短进行调度长短进行调度 (2)优点优点 易实现易实现 系统吞吐量高系统吞吐量高 (3)缺点缺点 只照顾短作业只照顾短作业 而没有考虑长作业的利益而没有考虑长作业的利益 66 例：求周转时间与带权周转时间例：求周转时间与带权周转时间 提交提交 执行执行 开始开始 完成完成 周转周转 带权周转带权周转 作业作业 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 8.00 9.10 1.10 1 9.10 9.
48、40 0.40 1.33问题：问题：长作业可能会饿死。如何解决呢？长作业可能会饿死。如何解决呢？希望：希望：平均周转时间平均周转时间 t=0.825 平均带权周转时间平均带权周转时间 w=2.59.40 9.90 1.40 2.8 9.90 10.00 0.50 5 1 8.00 1.10 2 8.50 0.50 3 9.00 0.30 4 9.50 0.103.相应比高相应比高(带权周转时间长带权周转时间长)者优先调度算法者优先调度算法相应比相应比等待时间运行时间等待时间运行时间运行时间运行时间1等待时间等待时间运行时间运行时间 调度策略：调度策略：既既短作业优先短作业优先，以提高效率，以提
49、高效率 又适当考虑长作业又适当考虑长作业(一个原则一个原则)相应比相应比 1K等待时间等待时间 运行时间运行时间 4.其他的优先数调度算法，如：其他的优先数调度算法，如：优先数优先数(等待时间分等待时间分)2执行时间执行时间(秒秒)16*输出行输出行 思考：思考：上述二种策略，用队列上述二种策略，用队列排序排序是否有意义？是否有意义？改进：改进：思考：思考：上述公式中，调度策略是否得到上述公式中，调度策略是否得到完整的实现完整的实现？其实质是其实质是长作业长作业优先、还是优先、还是短作业短作业优先？优先？如第二种调度策略中，有二个作业如第二种调度策略中，有二个作业 按优先数当前排序如下：按优先
50、数当前排序如下：（4210）（5220）但但1分钟后，按优先数排序变为分钟后，按优先数排序变为：（6220）（5210）5.均衡调度均衡调度目的：目的：使系统中的所有资源都保持忙碌使系统中的所有资源都保持忙碌 以达到以达到负载均衡负载均衡，提高系统的资源利用率，提高系统的资源利用率适用范围：适用范围：批处理中的作业调度批处理中的作业调度 方法：方法：(1)将作业按对将作业按对CPU的使用量进行分类：的使用量进行分类：多多CPU的的(计算量大计算量大)多多I/O的的(输入、输出量大输入、输出量大)均衡的均衡的(2)将各类作业均衡搭配起来进行调度将各类作业均衡搭配起来进行调度 70 一一.进程进程
