操作系统—资源分配与调.pptx

第五章第五章 资源分配与调度资源分配与调度5.1 资源管理概述资源管理概述5.1.1 资源管理的目的和任务资源管理的目的和任务什么是资源？什么是资源？资源包括硬件资源和软件资源。是指资源包括硬件资源和软件资源。是指执执行一个用户程序行一个用户程序所需要的全部硬件设备、所需要的全部硬件设备、软件设施和数据。软件设施和数据。5.1 资源管理概述资源管理概述5.1.1 资源管理的目的和任务资源管理的目的和任务什么是资源管理？什么是资源管理？根据不同资源的不同特点，按用户要求根据不同资源的不同特点，按用户要求对资源实行合理的对资源实行合理的分配分配，监察监察资源的使资源的使用情况，用情况，回收回收空闲资源，并空闲资源，并保护保护资源不资源不受非法使用。受非法使用。5.1 资源管理概述资源管理概述5.1.1 资源管理的目的和任务资源管理的目的和任务资源管理的目标（从它的反面谈起）资源管理的目标（从它的反面谈起）1.高效（例：高效（例：CPU的利用）的利用）2.合理（例：内存的分配）合理（例：内存的分配）3.安全（例：网络访问，死锁）安全（例：网络访问，死锁）5.1 资源管理概述资源管理概述5.1.1 资源管理的目的和任务资源管理的目的和任务资源管理的任务资源管理的任务1.资源数据结构的描述资源数据结构的描述2.确定资源的分配原则和调度原则确定资源的分配原则和调度原则3.执行资源分配执行资源分配4.存储控制和安全保护存储控制和安全保护 5.1 资源管理概述资源管理概述5.1.2 资源的分类方法（资源的分类方法（p120）物理资源与程序资源物理资源与程序资源单一访问入口资源和多访问入口的资源单一访问入口资源和多访问入口的资源等同资源等同资源虚拟资源虚拟资源5.1 资源管理概述资源管理概述5.1.3 资源管理的机构和策略（资源管理的机构和策略（p121）机构：机构：操作系统实现资源管理的部分操作系统实现资源管理的部分策略：策略：关于这部分操作系统的具体设计关于这部分操作系统的具体设计注意：由于每种资源具有各自的特点，注意：由于每种资源具有各自的特点，分配的机制和策略不尽相同，本章主要分配的机制和策略不尽相同，本章主要从资源的一般共性出发，着重讨论资源从资源的一般共性出发，着重讨论资源分配的一般机制和策略，具体的实施将分配的一般机制和策略，具体的实施将在后续各章中陆续展开讨论。在后续各章中陆续展开讨论。5.2 资源分配机制资源分配机制5.2.1 资源描述器（资源描述器（resource descriptor，RD）资源描述器（资源描述器（表表5.1，p121）：）：描述资源的数据结构描述资源的数据结构。操作系统通过这些数据结构而感知到资源的存在，并操作系统通过这些数据结构而感知到资源的存在，并对资源进行管理。对资源进行管理。最小分配单位：某一类资源根据需要最小分配单位：某一类资源根据需要划分为不可再分划分为不可再分割的基本分配单位割的基本分配单位。一个最小分配单位通过一个资源。一个最小分配单位通过一个资源描述器加以描述。描述器加以描述。5.2 资源分配机制资源分配机制5.2.1 资源描述器资源描述器资源描述器的组织方式：资源描述器的组织方式：表表：适合于分配单位数量固定不变：适合于分配单位数量固定不变队列队列：适合于分配单位数量是变化的：适合于分配单位数量是变化的最大数组法最大数组法：适合于分配单位的最大数：适合于分配单位的最大数量是已知的。如一个硬盘空间是不变的，量是已知的。如一个硬盘空间是不变的，当确定最小分配单位后，便可生成所有当确定最小分配单位后，便可生成所有的资源描述器。的资源描述器。5.2 资源分配机制资源分配机制5.2.2 资源信息块（资源信息块（rib）（）（p122，图，图5.1）资源信息块包含如下内容：资源信息块包含如下内容：1.等待进程队列等待进程队列2.可利用资源队列可利用资源队列3.资源分配程序入口地址资源分配程序入口地址5.3 资源分配策略资源分配策略5.3.1 概述概述资源分配的两个目标：资源分配的两个目标：吞吐率：吞吐率：在单位时间内完成工作量的量度在单位时间内完成工作量的量度。响应时间：响应时间：提交请求和返回该请求的响应之间提交请求和返回该请求的响应之间所使用的时间所使用的时间。吞吐率和响应时间是服务系统（如：数据库服吞吐率和响应时间是服务系统（如：数据库服务器、务器、web服务器等）的两个最为重要的评价服务器等）的两个最为重要的评价指标，所追求的目标就是高吞吐率和短响应时指标，所追求的目标就是高吞吐率和短响应时间。间。5.3 资源分配策略资源分配策略5.3.1 概述概述在其他条件不变的情况下，吞吐率与响应时间在其他条件不变的情况下，吞吐率与响应时间往往存在矛盾的，即以往往存在矛盾的，即以牺牲响应时间来获取高牺牲响应时间来获取高吞吐率，或以牺牲吞吐率来获取短响应时间吞吐率，或以牺牲吞吐率来获取短响应时间。系统设计时需要根据应用环境作出平衡。系统设计时需要根据应用环境作出平衡。ABAABAB5.3 资源分配策略资源分配策略5.3.2 先请求先服务先请求先服务(FIFO First In First Out)排序原则：按请求的先后次序排序。即：新产生的请排序原则：按请求的先后次序排序。即：新产生的请求均排在队尾，分配时在队首。求均排在队尾，分配时在队首。适用范围：系统中的一切资源。适用范围：系统中的一切资源。优点：优点：简单简单、次序不会改变、系统开销小、次序不会改变、系统开销小。缺点：未对请求特征、占用资源时间长短等因素加以缺点：未对请求特征、占用资源时间长短等因素加以考虑，考虑，不利于短作业不利于短作业，系统无法进行干预。，系统无法进行干预。5.3 资源分配策略资源分配策略5.3.3 优先调度优先调度：系统对每个进程：系统对每个进程(或作业或作业)，都指定一个优先级以，都指定一个优先级以反映请求资源的紧迫程度反映请求资源的紧迫程度排序原则：按优先级的高低排序。即：新产生的请求，按其优先排序原则：按优先级的高低排序。即：新产生的请求，按其优先级的高低插入到队列中相应的位置。级的高低插入到队列中相应的位置。优点：系统可进行干预，以优化资源的使用方式优点：系统可进行干预，以优化资源的使用方式缺点：插入时缺点：插入时要搜索队列要搜索队列、有时无法用队列实现，另外、有时无法用队列实现，另外如何合理如何合理地分配优先级也是一个问题地分配优先级也是一个问题。适用的资源：由于系统开销较大，适用的资源：由于系统开销较大，主要用于系统中的紧缺资源主要用于系统中的紧缺资源(如处理机的分配如处理机的分配)。5.3 资源分配策略资源分配策略资源分配策略的总原则：资源分配策略的总原则：1.保证紧急事务优先处理保证紧急事务优先处理2.保证低级事务得到处理保证低级事务得到处理3.保证轻量事务及时处理保证轻量事务及时处理5.4 死锁死锁5.4.1 死锁的概念死锁的概念死锁是一个较为复杂的概念，在讲这个概念之死锁是一个较为复杂的概念，在讲这个概念之前，先看一些例子。前，先看一些例子。例例1：网上交易支付问题：网上交易支付问题卖方与买方谈妥后，买方交付了卖方与买方谈妥后，买方交付了60%的货款，的货款，然后卖方向买方发货。当收到货物后，买方不然后卖方向买方发货。当收到货物后，买方不满意货物提出退货，然而卖方认为理由不合理，满意货物提出退货，然而卖方认为理由不合理，不予退货。交易无法推进下去。不予退货。交易无法推进下去。思考：你认为应该怎样解决？思考：你认为应该怎样解决？5.4 死锁死锁例例2：十字路的交通问题：十字路的交通问题 （练习题（练习题 P138 5-7）思考：它们是如何导致死锁的？思考：它们是如何导致死锁的？5.4 死锁死锁例例2：回顾：生产者消费者问题：回顾：生产者消费者问题消费者消费者在未检查缓冲区是否为空的时候便申请了读写许可在未检查缓冲区是否为空的时候便申请了读写许可mutex，当缓冲区为空时，消费者需要等生产者生产产品，然而生产者同当缓冲区为空时，消费者需要等生产者生产产品，然而生产者同样因为在等待消费者释放缓冲区而陷入了死锁。样因为在等待消费者释放缓冲区而陷入了死锁。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)；消费一个产品；消费一个产品；5.4 死锁死锁5.4.1 死锁的概念死锁的概念例例3：设系统只有一台打印机：设系统只有一台打印机(R1)，和一台光标记阅，和一台光标记阅读机读机(R2)，由进程，由进程p1、p2 共享。用信号灯的共享。用信号灯的P、V操操作，控制资源的申请和释放。其信号灯的设置为：作，控制资源的申请和释放。其信号灯的设置为：s1：表示：表示R1是否可用，初值为是否可用，初值为1。s2：表示：表示R2是否可用，初值为是否可用，初值为1。进进 程程 P1 进进 程程 P2p(s1)；申请；申请R1 p(s2)；申请申请R2p(s2)；又申请；又申请R2 p(s1)；又申请又申请R1 v(s1)；释放；释放R1 v(s2)；释放；释放R2 v(s2)；释放；释放R2 v(s1)；释放；释放R15.4 死锁死锁5.4.1 死锁的概念死锁的概念在两个或多个并发进程中，如果每个进程都持有某种在两个或多个并发进程中，如果每个进程都持有某种资源，而又都资源，而又都同时等待着别的进程释放它们保持着的同时等待着别的进程释放它们保持着的资源资源否则就不能向前推进。称这一组进程产生了死锁。否则就不能向前推进。称这一组进程产生了死锁。思考：是什么导致了死锁？是因为进程间的竞争吗？思考：是什么导致了死锁？是因为进程间的竞争吗？5.4 死锁死锁5.4.2 死锁的起因死锁的起因 (1)系统的资源总数系统的资源总数各进程的资源总需求各进程的资源总需求 (2)进程推进的顺序不合理进程推进的顺序不合理 (资源的使用方式、及占有资源的顺序资源的使用方式、及占有资源的顺序)练习：练习：p137，5-45.4 死锁死锁5.4.2 死锁的起因死锁的起因例：对打印机（例：对打印机（R1）-输出机（输出机（R2）死锁）死锁问题的解释问题的解释p1p2R1R2分配申请申请分配5.4 死锁死锁5.4.2 死锁的起因死锁的起因死锁的必要条件：死锁的必要条件：1.互斥条件互斥条件：涉及的资源为临界资源：涉及的资源为临界资源2.部分分配部分分配：进程每次仅申请所需资源的一部分，在占有资源以：进程每次仅申请所需资源的一部分，在占有资源以后，还会继续申请新的资源，只有不满足才等待。后，还会继续申请新的资源，只有不满足才等待。3.不剥夺条件不剥夺条件：进程占有的资源，不能被其他进程强行剥夺：进程占有的资源，不能被其他进程强行剥夺4.环路条件环路条件：在进程与资源有向图中，存在有向环。：在进程与资源有向图中，存在有向环。只要其中一条不成立，死锁就不会发生只要其中一条不成立，死锁就不会发生5.4 死锁死锁5.4.4 解决死锁的策略解决死锁的策略 基本点：破坏死锁的某一个必要条件基本点：破坏死锁的某一个必要条件 思考：破坏哪些必要条件是可行的呢？思考：破坏哪些必要条件是可行的呢？1.互斥条件互斥条件 2.不剥夺条件不剥夺条件 3.部分分配部分分配 4.环路条件环路条件 5.4 死锁死锁5.4.3 解决死锁的策略解决死锁的策略1.互斥条件：由硬件本身性质决定了难于否定该条互斥条件：由硬件本身性质决定了难于否定该条件。件。5.4 死锁死锁5.4.3 解决死锁的策略解决死锁的策略2不剥夺条件：很容易否定。但是：不剥夺条件：很容易否定。但是：（1）否定该条件是在发生了死锁之后。）否定该条件是在发生了死锁之后。（2）并且需要保护和恢复被剥夺的进程现场。）并且需要保护和恢复被剥夺的进程现场。（3）不是所有资源都可以剥夺的（如正在打印的打印）不是所有资源都可以剥夺的（如正在打印的打印机）机）思考：更重要的是，思考：更重要的是，要防死锁于未然要防死锁于未然。5.4 死锁死锁3部分分配：很容易否定，由此得到部分分配：很容易否定，由此得到静态预防死锁静态预防死锁。4环路条件：可以否定。由此得到环路条件：可以否定。由此得到有序资源分配法有序资源分配法。5.4 死锁死锁5.4.5 死锁的预防和避免死锁的预防和避免静态预防死锁静态预防死锁：在作业调度时，为选中的作业分配它所需要：在作业调度时，为选中的作业分配它所需要的所有临界资源在该的所有临界资源在该作业的整个运行期间，这些资源都为它作业的整个运行期间，这些资源都为它独占独占。实质：实质：破坏了死锁必要条件中的部分分配破坏了死锁必要条件中的部分分配缺点：缺点：降低了设备的利用率降低了设备的利用率(只用很短时间，或根本不用只用很短时间，或根本不用)造成不必要的等待造成不必要的等待用户可能提不出所需的全部资源用户可能提不出所需的全部资源5.4 死锁死锁5.4.5 死锁的预防和避免死锁的预防和避免有序资源分配法有序资源分配法(避免死锁，避免死锁，p134)：所有的资源类都给定一个：所有的资源类都给定一个唯一的序号（如打印机为唯一的序号（如打印机为1，阅读机为，阅读机为2），），分配请求必须以上分配请求必须以上升的次序进行升的次序进行；而且同一类型的资源必须一次申请完。；而且同一类型的资源必须一次申请完。优点：提高了资源利用率（优点：提高了资源利用率（p1使用完打印机后使用完打印机后p2便可申请占便可申请占用）用）缺点：进程实际需要资源未必与编号一致。缺点：进程实际需要资源未必与编号一致。实质：破坏了死锁的环路条件实质：破坏了死锁的环路条件p1p2R1R2申请1申请2申请1申请2p1p2R1R2分配申请申请分配导致死锁不导致死锁5.4 死锁死锁小结：处理死锁的四种策略小结：处理死锁的四种策略1检测死锁并恢复检测死锁并恢复2静态预防死锁静态预防死锁3有序的分配资源有序的分配资源4忽略死锁（鸵鸟算法）忽略死锁（鸵鸟算法）5.4 死锁死锁银行家算法（避免死锁）银行家算法（避免死锁）当进程申请一组资源时，需要检查申请者对当进程申请一组资源时，需要检查申请者对资源的最大需求量，如果系统现存的各类资源的资源的最大需求量，如果系统现存的各类资源的数量满足当前它对各类资源的最大需求量时，则数量满足当前它对各类资源的最大需求量时，则满足其申请；满足其申请；否则，进程必须等待，直到其他进程释放足够的否则，进程必须等待，直到其他进程释放足够的资源为止。资源为止。即：仅当申请者可以在一定时间内无条件的即：仅当申请者可以在一定时间内无条件的归还它所申请的全部资源时，才进行资源分配。归还它所申请的全部资源时，才进行资源分配。5.4 死锁死锁 假设有假设有n个进程个进程m类资源，则有如下数据结构：类资源，则有如下数据结构：可利用资源向量可利用资源向量Available。这是一个含有。这是一个含有m个个 元素的数组，其中的元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Availablej=K，则表示系统中现有，则表示系统中现有Rj 类资源类资源K个。个。最大需求矩阵最大需求矩阵Max。这是一个。这是一个n*m的矩阵，它定义了系统中的矩阵，它定义了系统中n个进程个进程中的每一个进程对中的每一个进程对m类资源的最大需求。如果类资源的最大需求。如果Maxi，j=K，则表示进程，则表示进程i需要需要Rj类资源的最大数目为类资源的最大数目为K。分配矩阵分配矩阵Allocation。这也是一个。这也是一个n*m的矩阵，它定义了系统中每一的矩阵，它定义了系统中每一类资源类资源 当前已分配给每一进程的资源数。如果当前已分配给每一进程的资源数。如果Allocationi，j=K，则表，则表示示 进程进程i当前已分得当前已分得Rj类资源的数目为类资源的数目为K。需求矩阵需求矩阵Need。这也是一个。这也是一个n*m的矩阵，用以表示每一个进程尚需的矩阵，用以表示每一个进程尚需的各类资源数。如果的各类资源数。如果Needi,j=K，则表示进程，则表示进程i还需要还需要Rj类资源类资源K个，方个，方能完成其任务。能完成其任务。上述三个矩阵存在如下关系：上述三个矩阵存在如下关系：Needi,j=Maxi，j-Allocationi，j5.4 死锁死锁 设进程设进程I提出请求提出请求RequestN，则银行家算法按如下规则进，则银行家算法按如下规则进行判断。行判断。(1)如果如果RequestN=NeedI，N，则转，则转(2)；否则，出错。；否则，出错。(2)如果如果RequestN=Available，则转，则转(3)；否则，出错。；否则，出错。(3)系统试探分配资源，修改相关数据：系统试探分配资源，修改相关数据：Available=Available-Request Allocation=Allocation+Request Need=Need-Request (4)系统执行安全性检查，如安全，则分配成立；否则试探险系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。性分配作废，系统恢复原状，进程等待。5.4 死锁死锁安全性检查安全性检查 (1)设置两个工作向量设置两个工作向量Work=Available；FinishM=False (2)从进程集合中找到一个满足下述条件的进程，从进程集合中找到一个满足下述条件的进程，Finishi=False Need=Work 如找到，执行如找到，执行(3)；否则，执行；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。设进程获得资源，可顺利执行，直至完成，从而释放资源。Work=Work+Allocation Finish=True goto 2 (4)如所有的进程如所有的进程FinishM=true，则表示安全；否则系统不安全。，则表示安全；否则系统不安全。银行家算法示例银行家算法示例5.4 死锁死锁考研真题：考研真题：09年年 选择题选择题2511年年 选择题选择题2712年年 选择题选择题2713年年 选择题选择题32