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

第五章 资源分配与调度,5.1 资源管理概述,5.1.1 资源管理的目的和任务 什么是资源？ 资源包括硬件资源和软件资源。是指执行一个用户程序所需要的全部硬件设备、软件设施和数据。,5.1 资源管理概述,5.1.1 资源管理的目的和任务 什么是资源管理？ 根据不同资源的不同特点，按用户要求对资源实行合理的分配，监察资源的使用情况，回收空闲资源，并保护资源不受非法使用。,5.1 资源管理概述,5.1.1 资源管理的目的和任务 资源管理的目标（从它的反面谈起） 高效（例：CPU的利用） 合理（例：内存的分配） 安全（例：网络访问，死锁）,5.1 资源管理概述,5.1.1 资源管理的目的和任务 资源管理的任务 资源数据结构的描述 确定资源的分配原则和调度原则 执行资源分配 存储控制和安全保护,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） 资源信息块包含如下内容： 等待进程队列 可利用资源队列 资源分配程序入口地址,5.3 资源分配策略,5.3.1 概述 资源分配的两个目标： 吞吐率：在单位时间内完成工作量的量度。 响应时间：提交请求和返回该请求的响应之间所使用的时间。 吞吐率和响应时间是服务系统（如：数据库服务器、web服务器等）的两个最为重要的评价指标，所追求的目标就是高吞吐率和短响应时间。,5.3 资源分配策略,5.3.1 概述 在其他条件不变的情况下，吞吐率与响应时间往往存在矛盾的，即以牺牲响应时间来获取高吞吐率，或以牺牲吞吐率来获取短响应时间。系统设计时需要根据应用环境作出平衡。,5.3 资源分配策略,5.3.2 先请求先服务 ( FIFO First In First Out) 排序原则：按请求的先后次序排序。即：新产生的请求均排在队尾，分配时在队首。 适用范围：系统中的一切资源。 优点：简单、次序不会改变、系统开销小 。 缺点：未对请求特征、占用资源时间长短等因素加以考虑，不利于短作业，系统无法进行干预。,5.3 资源分配策略,5.3.3 优先调度：系统对每个进程(或作业)，都指定一个优先级以反映请求资源的紧迫程度 排序原则：按优先级的高低排序。即：新产生的请求，按其优先级的高低插入到队列中相应的位置。 优点：系统可进行干预，以优化资源的使用方式 缺点：插入时要搜索队列、有时无法用队列实现，另外如何合理地分配优先级也是一个问题。 适用的资源：由于系统开销较大，主要用于系统中的紧缺资源(如处理机的分配)。,5.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 进 程 P2 p(s1) ；申请R1 p(s2)；申请R2 p(s2) ；又申请R2 p(s1)；又申请R1 v(s1) ；释放R1 v(s2)；释放R2 v(s2) ；释放R2 v(s1)；释放R1,5.4 死锁,5.4.1 死锁的概念 在两个或多个并发进程中，如果每个进程都持有某种资源，而又都同时等待着别的进程释放它们保持着的资源否则就不能向前推进。称这一组进程产生了死锁。 思考：是什么导致了死锁？是因为进程间的竞争吗？,5.4 死锁,5.4.2 死锁的起因 (1) 系统的资源总数各进程的资源总需求 (2) 进程推进的顺序不合理 (资源的使用方式、及占有资源的顺序) 练习：p137，5-4,5.4 死锁,5.4.2 死锁的起因 例：对打印机（R1）-输出机（R2）死锁问题的解释,5.4 死锁,5.4.2 死锁的起因 死锁的必要条件： 互斥条件：涉及的资源为临界资源 部分分配：进程每次仅申请所需资源的一部分，在占有资源以后，还会继续申请新的资源，只有不满足才等待。 不剥夺条件：进程占有的资源，不能被其他进程强行剥夺 环路条件：在进程与资源有向图中，存在有向环。 只要其中一条不成立，死锁就不会发生,5.4 死锁,5.4.4 解决死锁的策略 基本点：破坏死锁的某一个必要条件 思考：破坏哪些必要条件是可行的呢？ 互斥条件 不剥夺条件 部分分配 环路条件,5.4 死锁,5.4.3 解决死锁的策略 互斥条件：由硬件本身性质决定了难于否定该条件。,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便可申请占用） 缺点：进程实际需要资源未必与编号一致。 实质：破坏了死锁的环路条件,导致死锁,不导致死锁,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，j,5.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)从进程