操作系统第5章第9章华中科技大学版

《操作系统第5章第9章华中科技大学版》由会员分享，可在线阅读，更多相关《操作系统第5章第9章华中科技大学版（261页珍藏版）》请在金锄头文库上搜索。

1、操作系统第操作系统第5章章-第第9章章(华中科技大学版华中科技大学版) 一一、资源管理的资源管理的一般功能一般功能 1、构造描述资源的、构造描述资源的数据结构数据结构 操作系统通过这些数据结构而操作系统通过这些数据结构而 感知感知到资源的存在，并对资源进行到资源的存在，并对资源进行管理管理 这些数据结构，应包含描述资源的：这些数据结构，应包含描述资源的： 物理名物理名(内部标识内部标识)、 逻辑名逻辑名(用户定义的名称用户定义的名称) 分配状态分配状态 类型、地址、等所有信息类型、地址、等所有信息 2 3. 实施资源的实施资源的分配分配(及回收及回收) 根据分配原则，将资源分配给请求的用户根据

2、分配原则，将资源分配给请求的用户 并完成相应操作。并完成相应操作。 如如: CPU：恢复现场恢复现场 内存：内存：将程序调入内存、改内存分配标志将程序调入内存、改内存分配标志 独占资源：独占资源：上锁上锁 2. 制定资源的制定资源的分配原则分配原则 决定资源应决定资源应先分给谁先分给谁(当有多个进程请求时当有多个进程请求时) 何时分配，分配多少等问题何时分配，分配多少等问题 当资源使用完毕后，收回资源当资源使用完毕后，收回资源3 4. 存取控制和安全保护存取控制和安全保护 对资源的存取进行控制对资源的存取进行控制 并对资源实施安全保护措施并对资源实施安全保护措施 (如：内存、文件的保护如：内存

3、、文件的保护) 5. 其他的其他的特殊特殊功能功能 4 三三. 资源的资源的分配方式分配方式(接受者接受者) 1. 静态分配静态分配(接受者是接受者是作业作业) 系统在调度一个作业运行时：系统在调度一个作业运行时： 根据根据作业的需求作业的需求进行资源的分配进行资源的分配 在作业运行完毕后，才收回所分配的全部资源在作业运行完毕后，才收回所分配的全部资源2. 动态分配动态分配(接受者是接受者是进程进程) 在进程的运行过程中，根据在进程的运行过程中，根据进程提出的请求进程提出的请求 进行资源的分配进行资源的分配 资源资源使用完毕使用完毕(共享共享)、 或或被进程释放被进程释放(独占独占)后后 回收

4、该资源回收该资源 5 四四. 资源的分类资源的分类 为了为了简化系统的设计简化系统的设计，对不同的资源，可采，对不同的资源，可采用不同的方式进行分类。常用的分类方式有：用不同的方式进行分类。常用的分类方式有： 1. 硬件资源和软件资源硬件资源和软件资源 硬件：如处理机、主存、外部设备硬件：如处理机、主存、外部设备 软件：如文件、消息、数据结构软件：如文件、消息、数据结构 2. 同类资源同类资源 如：打印机类、显示器类、内存区域等如：打印机类、显示器类、内存区域等 . 虚拟资源虚拟资源和实际资源和实际资源 6虚拟资源和实际资源虚拟资源和实际资源用户用户独占资源独占资源A共享资源共享资源B请求请求

5、用户操作用户操作系统完成系统完成实际实际资源资源虚拟虚拟资源资源目的：目的：提高独占资源的利用率提高独占资源的利用率 5. 3 资源分配的策略资源分配的策略 资源的分配策略资源的分配策略 指获得资源的先后次序指获得资源的先后次序 通常的实现方法是：通常的实现方法是： 将资源的将资源的请求者请求者按某种原则按某种原则 形成一个具有形成一个具有先后次序先后次序的请求队列的请求队列 当资源可用时，当资源可用时，按队列的次序按队列的次序分配分配资源资源 1. 先请求先服务先请求先服务 ( FIFO First In First Out) 排序原则：排序原则：按请求的先后排序。按请求的先后排序。 即：即

6、：新产生的请求均排在新产生的请求均排在队尾队尾，分配时在，分配时在队首队首按请求的先后次序按请求的先后次序先先后后表头表头适用范围适用范围：系统中的一切资源系统中的一切资源优点：优点：简单、次序不会改变，简单、次序不会改变，因此系统开销小因此系统开销小 缺点：缺点：有时显得有时显得不合理不合理、系统、系统无法无法进行进行干预干预 9 2. 优先调度优先调度 系统对每个进程系统对每个进程(或作业或作业)，都，都指定一个指定一个优先级优先级 以反映请求资源的紧迫程度以反映请求资源的紧迫程度 表头表头按优先级的高低按优先级的高低高高低低 排序原则：排序原则：按优先级的高低排序按优先级的高低排序 即：

7、即：新产生的请求，按其新产生的请求，按其优先级优先级的高低的高低 插入到队列中相应的位置插入到队列中相应的位置10优点：优点：系统可进行干预，以优化资源的使用方式系统可进行干预，以优化资源的使用方式优先级的确定：优先级的确定： 主要由系统定，并可动态改变。如：主要由系统定，并可动态改变。如： 进程进程时间片到：时间片到：收回收回CPU，优先级降低，优先级降低 自动自动放弃放弃CPU：优先级升高优先级升高问题：问题：优先级相同的多个请求，如何排序？优先级相同的多个请求，如何排序？ 缺点：缺点：插入时要搜索队列、插入时要搜索队列、有时无法用队列实现有时无法用队列实现 适用的资源：适用的资源：由于系

8、统开销较大，主要用于由于系统开销较大，主要用于 系统中的紧缺资源系统中的紧缺资源(如处理机如处理机)11多优先级队列多优先级队列 适用于：适用于：每个优先级上，有很多进程每个优先级上，有很多进程 排序：排序：优先级不同，所排的队列不同优先级不同，所排的队列不同 优先级相同，在同一队列中按优先级相同，在同一队列中按FIFO排序排序 表头表头n按请求的先后次序按请求的先后次序先先后后 表头表头1按请求的先后次序先后 高高优优先先级级低低分配方式分配方式：仅当高优先级队列为空时仅当高优先级队列为空时 才考虑低优先级队列才考虑低优先级队列 优点：优点：减少了系统的排序开销减少了系统的排序开销123.

9、针对设备特性的调度针对设备特性的调度 思想：分配策略制定的资源思想：分配策略制定的资源访问次序访问次序 应与资源的实际应与资源的实际使用次序使用次序相一致相一致 目的：目的： 提高资源访问的提高资源访问的平均速度平均速度 如：读、写磁盘上的多个扇区时如：读、写磁盘上的多个扇区时 对数据的访问，涉及到磁头定位的：对数据的访问，涉及到磁头定位的： 柱面柱面 (磁道磁道)：由磁头的直线运动得到由磁头的直线运动得到 耗时较长耗时较长 扇区：扇区：通过磁盘的旋转得到，通过磁盘的旋转得到，耗时较短耗时较短 盘面：盘面：由不同的磁头的得到，由不同的磁头的得到，不耗时不耗时 故要根据故要根据耗时的长短耗时的长

10、短，依次决定访问次序，依次决定访问次序 例：不好的访问次序例：不好的访问次序 好的访问次序：好的访问次序：应在磁头的应在磁头的一次移动一次移动或磁盘的或磁盘的一周旋转一周旋转中完成中完成 磁头磁头5. 4 死锁的概念死锁的概念一一. 什么是死锁什么是死锁 1. 死锁的例子死锁的例子 (1) 交通堵塞交通堵塞 16 (2) 不恰当的不恰当的 P 操作操作 当：当：mutex=1 full=0 empty=n 时时 p1( ) p2( ) while(生产未完成生产未完成) while(还要继续还要继续消费消费) p(mutex) 生产一个产品；生产一个产品； p(full)； ； p(empty

11、)； 从缓冲区中取产品；从缓冲区中取产品； p(mutex)； v(mutex)； 送一个产品到缓冲区；送一个产品到缓冲区； v(empty)； v(mutex)； v(full)； 消费一个产品；消费一个产品； 17 (3) 设备的共享设备的共享 例：设系统只有一台打印机例：设系统只有一台打印机(R1)，和一台光标，和一台光标 记阅读机记阅读机(R2) ，由进程，由进程p1、p2 共享。共享。 用信号灯的用信号灯的P、V操作，控制资源的申请和释放操作，控制资源的申请和释放 其信号灯的设置为：其信号灯的设置为： s1：表示：表示R1是否可用，初值为是否可用，初值为1 s2：表示：表示R2是否可

12、用，初值为是否可用，初值为1 讨论资源分配的各个讨论资源分配的各个环节环节，看什么情况是，看什么情况是安全的安全的 先看资源的请求方式：先看资源的请求方式： 18 进程进程P1 进程进程P2 p(s1)； p(s2)； 申请申请R1 申请申请R2 释放释放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

13、释放释放R1释放释放R2 v(s1)； v(s2)；释放释放R2释放释放R1 v(s2)； v(s1)；安全！安全！不足：不足：对同一个进程来说对同一个进程来说 资源的使用没有并发资源的使用没有并发 不安全！不安全！ 19进进 程程 P1 进进 程程 P2p(s1)； p(s2)； 申请申请R1 申请申请R2p(s2)； p(s1)； 又申请又申请R2 又申请又申请R1 释放释放R1 释放释放R2 v(s1)； v(s2)； 释放释放R2 释放释放R1v(s2)； v(s1)； 思考思考：若二进程顺序执行，是否若二进程顺序执行，是否安全安全呢？呢？ 二进程如何执行，才会发生二进程如何执行，才会

14、发生死锁？死锁？等待等待等待等待 由于系统已由于系统已没有没有它们它们所等待的资源所等待的资源 而占有资源的进程本身也在等待而占有资源的进程本身也在等待(无法无法释放资源释放资源) 从而造成一种从而造成一种永久的相互等待永久的相互等待死锁死锁20 发生死锁的发生死锁的进程执行序列进程执行序列: 时刻时刻t1： 进程进程 p1占用打印机占用打印机 时刻时刻t2： 进程进程 p2占用光标记阅读机占用光标记阅读机 时刻时刻t3：进程：进程 p1又请求光标记阅读机，又请求光标记阅读机，等待等待 时刻时刻t4： 进程进程 p2又请求打印机，又请求打印机，等待等待思考：思考：从从资源资源的使用角度来看的使

15、用角度来看 对对死锁问题应如何进行死锁问题应如何进行一般性的描述一般性的描述呢？呢？ 21 2. 什么是死锁什么是死锁 在在两个两个或多个并发进程中，如果每个进程都或多个并发进程中，如果每个进程都持有持有某种资源，而又都同时某种资源，而又都同时等待等待着着 别别的进程的进程释放它们保持着的资源释放它们保持着的资源 即：即：在两个或多个并发进程中，所有的进程在两个或多个并发进程中，所有的进程 都都相互等待相互等待着其他的进程释放它们所持有的着其他的进程释放它们所持有的 某种资源，否则就不能向前推进某种资源，否则就不能向前推进 否则就不能向前推进否则就不能向前推进 称这一组进程产生了死锁称这一组进

16、程产生了死锁(它们中它们中)22强调：强调： (1) 死锁是在死锁是在n ( n 2 )个进程个进程 (不一定是所有进程不一定是所有进程)之间发生的一种状态之间发生的一种状态 这种状态一旦发生，就这种状态一旦发生，就永远无法改变永远无法改变 ?(2) 系统中已没有死锁进程所等待的资源了系统中已没有死锁进程所等待的资源了 (已被它们自己全占用了，或即使有也不够已被它们自己全占用了，或即使有也不够) (3) 平常说系统平常说系统会死锁会死锁，是指：，是指： 系统存在着死锁的可能系统存在着死锁的可能(由资源得请求序列定由资源得请求序列定) (但不一定会出现，但不一定会出现，由资源的实际使用定由资源的

17、实际使用定)探讨：探讨：出现死锁的原因到底是什么呢？出现死锁的原因到底是什么呢？ 23N0R1R2R1R2 R2R1R2R1P1P2二二. 死锁的起因和条件死锁的起因和条件(对设备的共享例对设备的共享例) 阴影区：阴影区：资源被共享，进程的执行轨迹资源被共享，进程的执行轨迹不可能进入不可能进入24从图中可看出：从图中可看出： 1、死锁的原因、死锁的原因 (1) 系统的资源总数系统的资源总数各进程的资源总需求各进程的资源总需求 能进行一般性的表述吗能进行一般性的表述吗? 因此：因此：死锁没有充分条件死锁没有充分条件! (2) 进程推进的顺序不合理进程推进的顺序不合理 (对资源的对资源的申请次序申

18、请次序、使用方式使用方式、占有方式占有方式) N0R1R2R1R2 R2R1R2R1P1P2 (1) 避开危险区（一个进程同时得到避开危险区（一个进程同时得到全部的资源全部的资源） (2) 将危险区变为阴影区将危险区变为阴影区(二进程二进程申请资源次序一致申请资源次序一致) (3) 从危险区回退从危险区回退(强行收回强行收回某进程某进程占有的资源占有的资源) 2、解决死锁的方法：至少可看出三种、解决死锁的方法：至少可看出三种263.死锁的死锁的示意示意表示表示占有边占有边P2P1R2R1占有边占有边申请边申请边或或等待边等待边申请边申请边或或等待边等待边用途：用途：可描述资源的分配过程，若死锁

19、则构成可描述资源的分配过程，若死锁则构成有向环有向环 可用可用资源资源 进程有向图进程有向图描述资源的使用状态描述资源的使用状态问题：问题：若若同一类型同一类型的资源有多个怎么表示？的资源有多个怎么表示？ 能否找到死锁的某些能否找到死锁的某些判别方法判别方法呢？呢？ 判别判别 (1) 资源次序图的资源次序图的一般形式一般形式 当同一资源有多个时当同一资源有多个时RiP1P2P3Rj 死锁的判别方法死锁的判别方法 资源的占有和申请可表示为：资源的占有和申请可表示为：4、死锁的判别方法、死锁的判别方法 (a) 若资源分配图中若资源分配图中无环无环，则不存在死锁，则不存在死锁 (b) 若资源分配图中

20、若资源分配图中有环有环，且环内，且环内每类每类资源只资源只有有一个个体一个个体，则死锁发生，则死锁发生(此时此时环是充分条件环是充分条件)(c) 若资源分配图中若资源分配图中有环有环，且环内有的资源有，且环内有的资源有多个个体多个个体，则无法判定死锁是否发生，则无法判定死锁是否发生(此时此时环不环不是充分条件是充分条件) (d) 对资源分配图对资源分配图可进行化简可进行化简，若化简后的图，若化简后的图中仍有环中仍有环(无法化简无法化简)，则，则环中的进程被死锁环中的进程被死锁 (2) 死锁的判别方法死锁的判别方法例例1:P1P2P3R1R3R2R4 ？R1R2P1P2P3P4环环 ？R1R2P

21、1P2P3P4 例例:化简后的状态：化简后的状态：死锁死锁 ？ (a) 若节点只有占有边，则若节点只有占有边，则可去掉占有边并释放资源可去掉占有边并释放资源 (b) 当有了空闲的资源后，当有了空闲的资源后，等待边可变为占有等待边可变为占有边边R1R2P1P2P3P4 化化 简简 的的 方方 法法 (1) 互斥条件互斥条件 涉及的资源为涉及的资源为临界资源临界资源RRPP 5、 死锁的必要条件死锁的必要条件 (2) 不剥夺条件不剥夺条件 进程占有的资源进程占有的资源 不能被其他进程强行剥夺不能被其他进程强行剥夺 (3) 部分分配部分分配 每次仅申请一部分资源。在占有资源以后，每次仅申请一部分资源

22、。在占有资源以后， 还会继续申请新资源。只有还会继续申请新资源。只有不满足才等待不满足才等待 (4) 环路条件环路条件 在进程与资源有向图中，存在在进程与资源有向图中，存在有向环有向环意义：意义：只要其中一条不成立，死锁就不会发生只要其中一条不成立，死锁就不会发生 33三三. 死锁的预防和避免死锁的预防和避免 基本点：基本点：破坏死锁的某一个必要条件破坏死锁的某一个必要条件 (1) 互斥条件互斥条件 (2) 不剥夺条件不剥夺条件 (3) 部分分配部分分配 (4) 环路条件环路条件 问题：问题：破坏哪些必要条件是可行的呢？破坏哪些必要条件是可行的呢？ 34降低了设备的利用率降低了设备的利用率(只

23、用很短时间，或根本不用只用很短时间，或根本不用)造成造成不必要的等待不必要的等待(一开始，可能并不用一开始，可能并不用)用户可能提不出所需的全部资源用户可能提不出所需的全部资源 1. 静态静态预防预防死锁死锁(死锁不会发生死锁不会发生) 在作业调度时，为选中的作业在作业调度时，为选中的作业 分配它所需要的分配它所需要的所有临界资源所有临界资源 在作业的整个运行期间，这些资源都为它在作业的整个运行期间，这些资源都为它独占独占缺点缺点 : 思考：思考： (1) 破坏了死锁必要条件中的哪一条？破坏了死锁必要条件中的哪一条？ (2) 资源利用率高不高？为什么？资源利用率高不高？为什么？35 2. 有序

24、资源分配法有序资源分配法(不让死锁出现不让死锁出现) 按按资源类资源类对资源进行排序对资源进行排序 (每一类给定一个唯一的序号每一类给定一个唯一的序号) 分配请求必须以分配请求必须以上升上升的次序进行；的次序进行； 而且同一类型的资源必须一次申请完而且同一类型的资源必须一次申请完 思考思考： 破坏了死锁的哪一个必要条件？破坏了死锁的哪一个必要条件？ 如何破坏的？如何破坏的？ 5 假定假定n个进程个进程(不妨设为不妨设为P1Pn)被死锁被死锁 而且而且 Pi占有的资源占有的资源序号最高序号最高 (如如5号号)P1PiPn 4 45 55 5则则Pi等待的资源等待的资源已被死锁的进程占有已被死锁的

25、进程占有而根据分配原则：而根据分配原则： 分配请求必须以分配请求必须以上升上升的次序进行的次序进行 而且而且同一类同一类的资源必须的资源必须一次一次申请完申请完 5矛盾！矛盾！37 若：资源的若：资源的使用次序使用次序与与资源类的排序资源类的排序不一致时不一致时 低序号资源必须低序号资源必须预先申请预先申请，降低了资源的利用率，降低了资源的利用率 (用户很难做到与用户很难做到与资源类的排序资源类的排序相一致相一致) 例如一个进程的资源请求次序为：例如一个进程的资源请求次序为： p(S2) 占住占住R2 p ( S5 ) 使用使用R5 使用使用R2不足的地方？不足的地方？能否做到：能否做到：使用

26、资源前才申请，而又不出现死锁呢？使用资源前才申请，而又不出现死锁呢？ 38 基本思想：基本思想：当系统现有的资源当系统现有的资源可保证可保证申请进申请进程完成时，才进行分配。否则，申请进程等待程完成时，才进行分配。否则，申请进程等待3.银行家算法银行家算法系统现有的资源系统现有的资源进程占有的资源进程占有的资源进程还需要的资源进程还需要的资源 进程占有的资源进程占有的资源进程还需要的资源进程还需要的资源系统现有的资源系统现有的资源 不不 进进 行行 分分 配配 进进 行行 分分 配配Pi：Pj： 银行家靠什么来积累财富呢银行家靠什么来积累财富呢？ 说明：说明：每次分配前每次分配前都要进行相应的

27、都要进行相应的验证验证 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 例例: 某系统有三个进程共享某系统有三个进程共享同类型同类型的的10个资源个资源进程进程已占资源数已占资源数 还需资源数还需资源数 基本原理：基本原理： 采用采

28、用部分分配部分分配，且，且允许环允许环存在。但任何时候存在。但任何时候 都有一个都有一个占有资源的进程占有资源的进程是可完成的是可完成的进程的完成序列为：进程的完成序列为： Q P R . 该进程完成后，该进程完成后，释放资源释放资源 则又有另一个进程是可完成的则又有另一个进程是可完成的如此重复，直到系统中所有的进程完成如此重复，直到系统中所有的进程完成 即：即：系统的系统的资源分配图，在任何时候资源分配图，在任何时候 都是都是可化简可化简的的(没有发生死锁没有发生死锁) 如上例中：如上例中： 进程的申请序列为：进程的申请序列为：. R P QP 0 8Q 0 4R 0 9系统资源数：系统资源

29、数：10P 4 4系统资源数：系统资源数：8R 2 7Q 2 2系统资源数：系统资源数：4系统资源数：系统资源数：2Q 4 0Q 系统资源数：系统资源数：0系统资源数：系统资源数：4P 8 0P 系统资源数：系统资源数：0系统资源数：系统资源数：8 进程进程已占资源数已占资源数 还需资源数还需资源数RPQ . . 要点：要点： (1) 每次分配前都进行检测每次分配前都进行检测 (2) 确保确保死锁不会发生死锁不会发生 (3) 对进程的资源对进程的资源申请方式不进行任何限制申请方式不进行任何限制 不足：不足： (1) 还不够大胆。还不够大胆。 为什么？为什么？ 有些还需要的资源，以后有些还需要的

30、资源，以后可能不会再申请可能不会再申请 (2) 对对每类资源每类资源都要检测，开销较大都要检测，开销较大 银行家算法的深入讨论银行家算法的深入讨论银行家算法的深入讨论银行家算法的深入讨论 进程请求资源时可分进程请求资源时可分三种情况三种情况进行处理：进行处理： (1) 每类资源还需数都每类资源还需数都 系统的拥有数：系统的拥有数：分配分配 (2) 每类资源还需数都每类资源还需数都 系统的拥有数：系统的拥有数：不分配不分配 (3) 仅仅部分资源类部分资源类的还需数的还需数 系统的拥有数：系统的拥有数： 则需判别则需判别系统的状态是否安全系统的状态是否安全 若安全：若安全：不会死锁，分配不会死锁，

31、分配 若不安全：若不安全：可能会死锁，不分配可能会死锁，不分配 问题：问题：如何对系统状态的安全进行判别呢？如何对系统状态的安全进行判别呢？ 系统状态的系统状态的图论图论判别方法判别方法 将进程的将进程的还需资源还需资源也作为申请边：也作为申请边： 化简资源分配图化简资源分配图 化简后，若图中所有的进程都是孤立节点：化简后，若图中所有的进程都是孤立节点： 则系统是则系统是安全安全的的 否则，系统是不安全的否则，系统是不安全的(可能会死锁可能会死锁) 系统状态的系统状态的程序程序判别算法判别算法所需的数据结构所需的数据结构(t为时间参数，参考为时间参数，参考P 113) 进程进程向量：向量：P(

32、t)=(p1 、 ppn ) 系统系统拥有的拥有的资源资源向量向量: W (t)=(r1 、rrm ) 初值：初值：系统对每类系统对每类资源的资源的最大拥有最大拥有数数所有所有进程占有进程占有资源资源矩阵：矩阵：A (t)=(行行:进程；进程；列列:资源资源)初值：初值：全为全为0 所有所有进程还需进程还需资源资源矩阵：矩阵： R (t)=(行行:进程；进程；列列:资源资源) 初值：初值：各各进程对各类进程对各类资源资源的的最大最大需求数需求数 可完成的进程可完成的进程向量：向量：L (t) 初值初值为空为空 算法的描述：对任一时刻算法的描述：对任一时刻 tWhile （存在（存在 pi P(

33、t) R(i,t) W(t) )P(t) R(i,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) 限定限定进程进程等待的时

35、间等待的时间 (2) 由系统管理员，观测进程的运行情况由系统管理员，观测进程的运行情况 (3) 定期执行检测算法定期执行检测算法 (类似类似系统状态的判别系统状态的判别，但，但仅用仅用等待边等待边进行进行) 2、死锁恢复的方法、死锁恢复的方法(解开环解开环) (1) 逐个逐个撤销撤销死锁的进程，直到死锁打开死锁的进程，直到死锁打开优点：优点：简单、可行性较强简单、可行性较强缺点：缺点：部分进程重新执行，部分进程重新执行，代价较高代价较高(2) 逐个收回逐个收回死锁进程占有的资源，直到死锁进程占有的资源，直到 死锁打开死锁打开(进程进程回退回退，要记住所有的，要记住所有的分配点分配点) (3)

36、从从上次上次未发现未发现死锁的死锁的检测点检测点处，处，重新执行重新执行 (要保存上个要保存上个检测点检测点现场现场) 为什么可行？为什么可行？ 6. 1 处理机的多级调度处理机的多级调度 一、处理机调度的功能一、处理机调度的功能 从从资源管理资源管理的角度看，处理机调度的功包括：的角度看，处理机调度的功包括： 维护有关的数据结构维护有关的数据结构 制订调度策略制订调度策略 (谁能优先得到处理机谁能优先得到处理机) 设计调度算法设计调度算法(实现调度策略实现调度策略) 实施处理机的分配实施处理机的分配 (保护、恢复现场；修改保护、恢复现场；修改PCB、及有关的队列、及有关的队列)问题：问题：实

37、现处理机的分配要经过那些过程呢？实现处理机的分配要经过那些过程呢？51 另外，另外，有些系统在有些系统在内存紧张时，内存紧张时，会将某些会将某些进程进程的程序的程序在内、外存之间进行交换在内、外存之间进行交换 只有内存的程序只有内存的程序(进程进程)才能在才能在CPU上运行上运行内存内存二、二、处理机调度的分层处理机调度的分层运行运行就绪就绪等待等待外存外存 就绪态的进程有多个，就绪态的进程有多个，CPU分配分配给谁？给谁？52 因此，因此，处理机的调度可分为二层处理机的调度可分为二层(或三层或三层) (1) 宏观调度宏观调度 对象为作业，故又称为对象为作业，故又称为作业调度作业调度 任务：任

38、务：在已进入系统的作业中，按某种原则在已进入系统的作业中，按某种原则 挑选一个、或一批作业到内存执行挑选一个、或一批作业到内存执行 完成的工作：完成的工作： 为选中为选中作业的执行程序作业的执行程序建立进程建立进程 为其分配内存为其分配内存 分配其他需分配其他需静态分配静态分配的资源的资源 53 (2) 微观调度微观调度 对象为进程，故又称为对象为进程，故又称为进程调度进程调度 任务：任务：确定确定哪个进程、在什么时候哪个进程、在什么时候 获得处理机，以及获得处理机，以及使用多长时间使用多长时间 完成的工作：完成的工作： 选择一个选择一个在内存就绪在内存就绪的进程的进程 将其状态改为运行将其状

39、态改为运行 若分时，给出运行的时间片若分时，给出运行的时间片 恢复该进程的现场恢复该进程的现场 54 （3）中级调度）中级调度 用于某些分时系统用于某些分时系统(如如Unix)中中 对象为进程对象为进程 任务：任务： 确定哪些进程被允许确定哪些进程被允许参与参与处理机的竞争处理机的竞争 短期内短期内(如进程太多时如进程太多时)调整系统内存的负荷调整系统内存的负荷 完成的工作：完成的工作： 55 换出：换出：在内存中最不可能得到在内存中最不可能得到CPU的进程的进程 首先首先: 等待态等待态的就绪进程的就绪进程 其次：其次：优先级低优先级低且且驻驻留内存时间长留内存时间长的就绪进程的就绪进程 换

40、入：换入：在进程调度程序挑选运行进程前在进程调度程序挑选运行进程前 换入在外存换入在外存驻驻留时间较长留时间较长的就绪进程的就绪进程 说明：说明： 对处理机的调度，不同的操作系统对处理机的调度，不同的操作系统 往往采用不同的实现方式往往采用不同的实现方式 566. 2 作业调度作业调度 一个一个作业，是一个用户的一次上机过程。因此作业，是一个用户的一次上机过程。因此 (1) 最基本的作业：执行最基本的作业：执行一个可执行程序一个可执行程序 (2) 复杂的作业：执行复杂的作业：执行一组一组可执行程序：可执行程序： 如编译、连接、执行等如编译、连接、执行等 作业的表现形式：作业的表现形式： (1)

41、 批处理：用户提出的批处理：用户提出的作业申请作业申请 完成内容：在完成内容：在操作说明书操作说明书中所包含的所有中所包含的所有执行语句执行语句 (2) 分时系统：用户登录后的活动分时系统：用户登录后的活动(注销后结束注销后结束) 完成内容：通过终端输入的一组命令完成内容：通过终端输入的一组命令(可执行的程序可执行的程序) 57 二、二、作业控制块作业控制块 操作系统对作业进行管理的数据结构，称为作业控操作系统对作业进行管理的数据结构，称为作业控制块制块 (JCB)，它是一个作业存在的标志。它是一个作业存在的标志。 JCB的主要内容包括：的主要内容包括： 作作 业业 名名 对对资源的要求资源的

42、要求 估计执行时间估计执行时间 最迟完成时间最迟完成时间 要求的主存量要求的主存量 要求外设的类型及台数要求外设的类型及台数 要求文件量和输出量要求文件量和输出量 58 资资 源源 使使 用用 情况情况 进入系统的时间进入系统的时间 开始执行的时间开始执行的时间 已执行的时间已执行的时间 程序在主存的地址程序在主存的地址 占有的外部设备占有的外部设备 状状 态态 优优 先先 级级 作业类型作业类型(如：多如：多CPU、多、多IO、或均衡等、或均衡等) 控制方式控制方式(如脱机、如脱机、 联机联机) 59 (1)设设 作业作业 i 的周转时间为的周转时间为 ti ，则，则 ti = 完成时间提交

43、时间完成时间提交时间 = tci tsi 或：或：ti = 运行时间等待时间运行时间等待时间t = 四、四、作业调度性能的衡量作业调度性能的衡量 (2)平均周转时间平均周转时间 1. 周转时间周转时间 从作业提交给系统，到完成所需的时间从作业提交给系统，到完成所需的时间意义：意义：描述了描述了作业作业 i 在系统中在系统中停留时间停留时间的长短的长短60例：例：作业作业 运行时间运行时间 等待时间等待时间周转时间周转时间周转时间周转时间 (分钟分钟)1 5 25 30 2 20 20 40 调度算法调度算法对哪个作业有利呢？对哪个作业有利呢？ (3) 如何用于评价如何用于评价 对用户：对用户：

44、周转时间越小越好周转时间越小越好( (更方便更方便) ) 对系统：对系统：平均周转时间越小越好平均周转时间越小越好( (吞吐量大、吞吐量大、利用利用率高率高) )原因？原因？ 因为因为周转时间周转时间中包含了中包含了运行时间运行时间，使评价出现误差，使评价出现误差 平均周转时间平均周转时间同样同样也有类似的问题也有类似的问题 如何衡量更准确呢？如何衡量更准确呢？10 15 问题：问题：不够准确不够准确61 2. 带权周转时间带权周转时间 (1) 带权周转时间，指：带权周转时间，指： 一个作业的一个作业的周转时间周转时间与其与其运行时间运行时间的比值的比值 wi = ？ (2) 平均带权周转时间

45、平均带权周转时间 t = 精确度：精确度：二者都高于周转时间、平均周转时间二者都高于周转时间、平均周转时间 周转时间周转时间运行时间运行时间等待时间等待时间运行时间运行时间 3. 其他的衡量方法其他的衡量方法 可用可用CPU利用率利用率、或、或系统吞吐量系统吞吐量直接衡量直接衡量( (无无满意度满意度) ) 意义：意义：说明说明作业作业 i 在系统中的在系统中的相对等待时间相对等待时间= 1 +62 五、五、作业调度算法作业调度算法 1. 先来先服务调度算法先来先服务调度算法(FCFSFCFS) 特点：特点： 简单，易实现简单，易实现 8.00 9.10 1.10 1 9.10 9.60 1.

46、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 提交提交 执行执行 开始开始 完成完成 周转周转 带权周转带权周转 作业作业 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间例：求周转时间与带权周转时间例：求周转时间与带权周转时间 (单位：单位：十进制小时十进制小时)63 (4) 评价：评价：性能较差。性能较差。 原因：原因： 当当短作业排在长作业后面短作业排

47、在长作业后面时，由于时，由于 等待时间变长等待时间变长(而运行时间不变而运行时间不变)，造成：，造成： 平均平均周转时间、周转时间、平均平均带权周转时间变长带权周转时间变长短作业等待时间短作业等待时间长作业等待长作业等待 例：例： 运行时间运行时间 周转时间周转时间而且短作业的而且短作业的相对等待时间相对等待时间较长，较长，不满意不满意改进：改进：短作业排在长作业前面短作业排在长作业前面 2. 短作业优先调度算法短作业优先调度算法 (1) 策略策略 按作业按作业运行的时间运行的时间长短进行调度长短进行调度 (2) 优点优点 易实现易实现 系统吞吐量高系统吞吐量高 (3) 缺点缺点 只照顾短作业

48、只照顾短作业 而没有考虑长作业的利益而没有考虑长作业的利益 例：求周转时间与带权周转时间例：求周转时间与带权周转时间 提交提交 执行执行 开始开始 完成完成 周转周转 带权周转带权周转 作业作业 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 8.00 9.10 1.10 1 9.10 9.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.0

49、0 1.10 2 8.50 0.50 3 9.00 0.30 4 9.50 0.10663. 相应比高相应比高(带权周转时间长带权周转时间长)者优先调度算法者优先调度算法相应比相应比等待时间运行时间等待时间运行时间运行时间运行时间1等待时间等待时间运行时间运行时间 调度策略：调度策略：既既短作业优先短作业优先，以提高效率，以提高效率 又适当考虑长作业又适当考虑长作业 (一个原则一个原则)相应比相应比 1K等待时间等待时间 运行时间运行时间 4. 其他的优先数调度算法，如：其他的优先数调度算法，如： 优先数优先数(等待时间分等待时间分)2执行时间执行时间(秒秒)16*输出行输出行 思考：思考：上

50、述二种策略，用队列上述二种策略，用队列排序排序是否有意义？是否有意义？ 改进：改进： 思考：思考：上述公式中，调度策略是否得到上述公式中，调度策略是否得到完整的实现完整的实现？ 其实质是其实质是长作业长作业优先、还是优先、还是短作业短作业优先？优先？如第二种调度策略中，有二个作业如第二种调度策略中，有二个作业 按优先数当前排序如下：按优先数当前排序如下： （4210） （5220） 但但1分钟后，按优先数排序变为分钟后，按优先数排序变为 ： （6220） （5210） 5. 均衡调度均衡调度目的：目的：使系统中的所有资源都保持忙碌使系统中的所有资源都保持忙碌 以达到以达到负载均衡负载均衡，提高

51、系统的资源利用率，提高系统的资源利用率适用范围：适用范围：批处理中的作业调度批处理中的作业调度 方法：方法： (1) 将作业按对将作业按对CPU的使用量进行分类：的使用量进行分类： 多多CPU的的(计算量大计算量大) 多多I/O的的(输入、输出量大输入、输出量大) 均衡的均衡的(2) 将各类作业均衡搭配起来进行调度将各类作业均衡搭配起来进行调度 6. 3 进程调度进程调度 一一. 进程进程调度调度、及、及CPU的的分派分派 1. 进程调度进程调度按一定的策略，在就绪状态的进程中按一定的策略，在就绪状态的进程中 决定处理机分配的先后次序决定处理机分配的先后次序 (通常是形成一个通常是形成一个有序

52、的就绪队列有序的就绪队列) 70 二二. 进程调度的功能进程调度的功能 1. 记录进程的有关情况和状态特征记录进程的有关情况和状态特征(在在PCB中中) 2. 制定调度策略制定调度策略 优先调度原则：优先调度原则： 就绪队列按进程就绪队列按进程优先级高低优先级高低排序排序 先来先服务原则：先来先服务原则： 就绪队列按进程到来的就绪队列按进程到来的先后次序先后次序 (或等待时间的长短或等待时间的长短)排序排序 3. 实施处理机的分配和回收实施处理机的分配和回收 71 三三. 进程调度的方式进程调度的方式指处理机指处理机是否可剥夺是否可剥夺 可从可从广义广义(如分时如分时)或或狭义狭义的角度讨论的

53、角度讨论 狭义的狭义的是否可剥夺是否可剥夺是指：是指： 采用采用优先级优先级调度；调度； 一个进程正在处理机上运行；一个进程正在处理机上运行； 若出现若出现优先级更高优先级更高的的就绪进程：的的就绪进程： 系统是否系统是否强行收回强行收回运行进程的处理机运行进程的处理机 72 . 非剥夺方式非剥夺方式 让执行进程继续执行，直到让执行进程继续执行，直到放弃放弃CPU 后后 才把处理机才把处理机分配分配给优先级更高的进程给优先级更高的进程 即：只在分配即：只在分配CPU时，才考虑优先级时，才考虑优先级 . 剥夺方式剥夺方式 立即把立即把CPU分配给优先级更高的进程分配给优先级更高的进程 即：总是即

54、：总是优先级最高优先级最高的进程占有的进程占有CPU。问题：问题：二者都有片面性二者都有片面性解决：解决：采取采取有条件有条件的剥夺，怎么表述呢？的剥夺，怎么表述呢？ 733. 选择可抢占策略选择可抢占策略 每个进程给出一对标志每个进程给出一对标志(U，V) 根据根据高优先就绪进程高优先就绪进程和和运行进程运行进程二者的标志，二者的标志，决定是否进行抢夺：决定是否进行抢夺： U=1：表示表示可抢夺可抢夺运行进程的运行进程的CPU U=0：表示不可抢夺运行进程的：表示不可抢夺运行进程的CPU V=1：表示表示(运行进程运行进程)允许被其他进程抢夺允许被其他进程抢夺 V=0：表示不允许被其他进程抢

55、夺：表示不允许被其他进程抢夺 74 进一步的问题：进一步的问题：(1) 一个系统的进程一个系统的进程调度策略调度策略如何来描述？如何来描述？(2) 与进程调度有关的各个模块与进程调度有关的各个模块 在什么条件下在什么条件下被激活被激活执行？执行？(3) 这些模块之间有什么这些模块之间有什么联系联系呢？呢？ 75 四四. 调度用的进程状态变迁图调度用的进程状态变迁图 例：某系统的例：某系统的进程状态变迁图如下所示进程状态变迁图如下所示运行运行500ms100ms因因 IO而等待而等待高优先高优先 就绪就绪低优先低优先 就绪就绪进程进程调度调度进程调度进程调度时间片到时间片到请求请求I/OI/O完

56、成完成(一一) 通过通过进程状态变迁图进程状态变迁图 可可反映系统反映系统进程调度进程调度的各种特征的各种特征 76 1. 队列的结构队列的结构 一个一个I/O等待等待队列：队列： 进程如果请求进程如果请求I/O，则进入，则进入I/O等待队列等待队列 一个一个低优先就绪低优先就绪队列：队列： 运行进程用完了分配给它的时间片运行进程用完了分配给它的时间片 就进入低优先就绪列就进入低优先就绪列 一个一个高优先就绪高优先就绪队列：队列： 当等待态的进程被唤醒后当等待态的进程被唤醒后 则进入高优先就绪队列则进入高优先就绪队列 772. CPU的分配的分配(当当CPU空闲时空闲时) (1) 若若高优先就

57、绪队列非空高优先就绪队列非空：则从高优先就绪队列中：则从高优先就绪队列中 选择一个进程运行，分配时间片为选择一个进程运行，分配时间片为100ms 3. 调度策略调度策略 (1) 方式：方式： 采用采用非剥夺非剥夺方式、方式、 优先级优先级与时间片相结合与时间片相结合 (2) 排序：排序：IO量大的进程优先量大的进程优先 对对计算量大计算量大的进程也进行一定的的进程也进行一定的补偿补偿 (2) 若高优先就绪队列为空、若高优先就绪队列为空、低优先就绪队列非空：低优先就绪队列非空： 则从低优先就绪队列选择一个进程，时间片则从低优先就绪队列选择一个进程，时间片500ms 78CPU空闲、高优先就绪为空

58、、空闲、高优先就绪为空、低优先就绪非空低优先就绪非空运行运行因因 IO而等待而等待高优先高优先 就绪就绪低优先低优先 就绪就绪521344. 进程状态变迁的原因进程状态变迁的原因变迁变迁1 ：变迁变迁2 2：变迁变迁3：变迁变迁4：变迁变迁5 5：运行进程运行进程时间片到时间片到或或被抢占被抢占(剥夺方式剥夺方式) 例：例：运行进程运行进程请求请求IO后，等待后，等待IO的完成的完成因因 IO而等待的进程而等待的进程， 所等待的所等待的IO已完成已完成CPU空闲、空闲、高优先就绪非空高优先就绪非空 可用来描述、或了解可用来描述、或了解 系统系统相关模块相关模块的的 执行条件执行条件79 5.

59、因果变迁因果变迁 所谓的因果变迁是指：所谓的因果变迁是指： 一个状态的变迁一个状态的变迁发生后，发生后， 是否也会引起是否也会引起其他的状态变迁其他的状态变迁发生发生? 若可以，需要什么附加的若可以，需要什么附加的前提条件前提条件？ 用途：用途： 用来描述、或了解系统用来描述、或了解系统相关模块之间的联系相关模块之间的联系 即：哪些模块，在什么条件下会即：哪些模块，在什么条件下会相互调用相互调用？ 80运行运行因因 IO而等待而等待高优先高优先 就绪就绪低优先低优先 就绪就绪52134 变迁变迁3 变迁变迁5 5: : 变迁变迁1 变迁变迁3 3: : 变迁变迁4 变迁变迁5 5: : 变迁变

60、迁2 变迁变迁4 4: : 变迁变迁3 变迁变迁2 2: 不可能不可能，原因：原因： 理论：理论： 实际：实际： 理解：理解： 无因果关系无因果关系 可能，条件：可能，条件：可能，可能，条件：条件：关键是看：关键是看： 前一变迁的结果，前一变迁的结果， 对对产生产生后一变迁的后一变迁的条件条件的影响的影响 (变少、变少、不成立、不改变不成立、不改变)81运行运行500ms100ms因因 IO而等待而等待高优先高优先 就绪就绪低优先低优先 就绪就绪进程进程调度调度进程调度进程调度时间片到时间片到请求请求I/OI/O完成完成 (二二) 画进程状态变迁图画进程状态变迁图 根据调度策略根据调度策略(或

61、效果或效果)，画进程状态变迁图，画进程状态变迁图 五五. 进程调度算法进程调度算法 基本要求：基本要求： (1) 若有作业调度，若有作业调度， 应与作业调度算法尽可能一致应与作业调度算法尽可能一致(批处理中批处理中) (2) 算法应尽可能算法应尽可能简单简单，以，以减少减少系统的系统的开销开销 (3) 不能让进程长久地等待不能让进程长久地等待 1. 进程优先数调度算法进程优先数调度算法预先确定各进程的预先确定各进程的优先级优先级 (通常用一个通常用一个优先数优先数来表示来表示) 将处理机分配给将处理机分配给优先级最高优先级最高的就绪进程的就绪进程 83 () 优先数的形式优先数的形式 可分为二

62、种可分为二种: 静态优先数静态优先数在进程被在进程被创建时创建时按某种策略确定按某种策略确定 而且在整个而且在整个进程的运行期间进程的运行期间不再改变不再改变 动态优先数动态优先数在在进程被创建时先给出一个进程被创建时先给出一个初始初始的优先数的优先数 (也称为也称为基本优先级基本优先级) 在在进程的运行中进程的运行中，再按某种策略，再按某种策略进行调整进行调整 84 (2) 优先数的确定优先数的确定基本的策略基本的策略：占用占用CPU时间少的进程优先时间少的进程优先 静态优先数的确定静态优先数的确定 根据作业的根据作业的运行时间运行时间来估计来估计 根据作业所需使用的根据作业所需使用的非非C

63、PU资源资源来估计来估计 (通常使用多者优先，通常使用多者优先，为什么为什么?) 由用户提出由用户提出优点：优点：简单，系统开销小简单，系统开销小 问题：问题：不准确、不准确、不灵活不灵活 85 动动态优先数的确定态优先数的确定 在进程运行期间，优先数可改变。在进程运行期间，优先数可改变。 基本的策略是：基本的策略是： 对对预计的预计的CPU时间时间进行估算，进行估算，占用少的优先占用少的优先 一种最常用的一种最常用的估算估算方法是根据上一轮的方法是根据上一轮的 估计估计时间、时间、实际占用实际占用时间来定，用公式表示为：时间来定，用公式表示为：k n+1 = a * t n + (1 - a

64、) * k n k n ：上一次：上一次估计估计的的CPU占用时间占用时间 t n ：上一次：上一次实际占用实际占用的的CPU时间时间通过系数通过系数 a 确定权值，常见的确定权值，常见的取值取值可为：可为： a = 1： k n+1 = t n 用当前的实际用当前的实际占用时间占用时间 作为下一次作为下一次估计时间估计时间(简单、较合理、最常用简单、较合理、最常用) a = 0： k n+1 = k n 估计时间为常数估计时间为常数(时间片固定时间片固定) a = 1/2: k n+1 =(k n + t n ) / 2 取平均值取平均值(综合考虑综合考虑) 86(a) 因等待而放弃因等待而

65、放弃CPU的进程：的进程： 优先级提高优先级提高，以提高设备的利用率，以提高设备的利用率(b) 进程使用进程使用CPU超过一定时间超过一定时间(如时间片如时间片)后：后： 降低优先级降低优先级 优先调度存在的问题：优先调度存在的问题：有的进程可能会长时间地等待有的进程可能会长时间地等待(尽管可补偿尽管可补偿) 怎么解决？怎么解决？由于由于CPU的切换非常频繁，根据前面的思想的切换非常频繁，根据前面的思想 能否不通过运算，就确定优先级呢？能否不通过运算，就确定优先级呢？87 2. 按时间片循环轮转调度算法按时间片循环轮转调度算法 策略：策略： 就绪队列按就绪队列按FIFO排序排序 目的：目的：让

66、所有的进程，让所有的进程，均衡地使用均衡地使用CPU 问题：问题：时间片如何定？时间片如何定？p1 p2 p3 p4t it i+1当前响应时间当前响应时间 : t i =q * n i (n i为当前进程数为当前进程数) p1p1p4 (1) 简单循环轮转调度简单循环轮转调度(时间片时间片 q 固定固定) 就绪队列中的所有进程，等速度向前推进。就绪队列中的所有进程，等速度向前推进。88 为有一个合理的为有一个合理的平均响应时间平均响应时间 时间片时间片 q 应固定为多长才合适呢？应固定为多长才合适呢？如：如：q = 200ms = 0.2秒秒 当当n j = 60时：时： t j = 12秒

67、秒，响应时间长，响应时间长，用户不满意用户不满意 当当n k= 4时：时： t k = 0. 8秒秒 ？ 设设 t max为用户为用户容忍的响应时间容忍的响应时间，n为进程数，则有：为进程数，则有： q = = t max / n = 3000 ms / (6 60) = 50 500 ms浪费切换时间。浪费切换时间。 如何如何解决？解决？ 存在的问题：存在的问题： q 固定后，响应时间随固定后，响应时间随当前的进程数当前的进程数而变化而变化89 (2)可变时间片循环轮转调度可变时间片循环轮转调度 响应时间响应时间T固定固定 (为用户所能接受的时间，如为用户所能接受的时间，如3秒秒) 每一轮开

68、始前每一轮开始前，根据当前的就绪进程数，根据当前的就绪进程数Ni 决定该轮的时间片决定该轮的时间片Qi (即即Qi =T/ Ni )P1P2P3进一步的问题：进一步的问题： 能否同时又考虑进程的优先级呢？能否同时又考虑进程的优先级呢？ P4 P1 P2 P3P4 ( 等下一轮等下一轮) 效果：效果：不同轮的时间片可能不同不同轮的时间片可能不同 同一轮中，同一轮中，各进程的时间片相同各进程的时间片相同 90高高优优先先级级低低短短时时间间片片长长时时间间片片到到等等待待1级就绪队列级就绪队列n级就绪队列级就绪队列i级就绪队列级就绪队列 3、多重时间片循环轮转调度算法、多重时间片循环轮转调度算法

69、根据优先级的分布，采用多个就绪队列根据优先级的分布，采用多个就绪队列 进程按进程按优先级优先级，在相应就绪队列按，在相应就绪队列按FIFO排序排序问题：问题：如何避免、或补偿某些进程如何避免、或补偿某些进程 经常的、长久的等待呢？经常的、长久的等待呢？ (1) Windows NT 采用类似的就绪队列结构采用类似的就绪队列结构 因等待而放弃因等待而放弃CPU，提高提高优先级优先级 (2) UNIX 优先数优先数相同的就绪进程相同的就绪进程: 可认为是排在同一个优先级的队列中可认为是排在同一个优先级的队列中 因等待而放弃因等待而放弃CPU：置为较高的置为较高的优先级优先级说明：说明：二个系统中，

70、用户都可二个系统中，用户都可: 指定一个优先级的底线指定一个优先级的底线 进程调度实例进程调度实例7. 1 主存共享的特征主存共享的特征问题：执行程序在主存中是如何存放的？问题：执行程序在主存中是如何存放的？ 一、一、主存主存共享共享的特征的特征主存以分片的方式主存以分片的方式(按区域按区域)实现共享。实现共享。 问题：问题：指令和数据的指令和数据的地址地址是如何表示的？是如何表示的？ 根据每个区域的大小是否相等，可分为：根据每个区域的大小是否相等，可分为： 分区、分区、分段分段存储管理：存储管理：片的大小片的大小不等不等 页式页式存储管理：片的大小存储管理：片的大小相等相等 段页式段页式存储

71、管理：存储管理：两者结合两者结合93 二、编址的基本概念二、编址的基本概念 1. 逻辑地址逻辑地址 (程序地址、相对地址、虚地址程序地址、相对地址、虚地址) 指：程序中指：程序中(指令或数据指令或数据)使用的地址使用的地址主存空间01m作业作业i地址空间地址空间01n即：即：用户是在逻辑空间中，用户是在逻辑空间中， 编写自己的程序编写自己的程序 问题：逻辑地址问题：逻辑地址就是程序在就是程序在 内存中的地址内存中的地址 码？码？ 2.逻辑空间逻辑空间 (程序空间、作业的地址空间程序空间、作业的地址空间) 逻辑地址的集合所对应的空间逻辑地址的集合所对应的空间(整个程序整个程序)94主存空间主存空

72、间01m作业地址空间01n作作 业业 i5. 区域区域 由一组连续、递增的物理地址：由一组连续、递增的物理地址： n、n+1、 、nm 所对应的所对应的主存空间的一个子集主存空间的一个子集 内存是以内存是以区域区域为单位进行分配的为单位进行分配的 3. 物理地址物理地址 (绝对地址、实地址绝对地址、实地址)物理地址是计算机物理地址是计算机主存单元主存单元的地址的地址 又称为绝对地址或实地址又称为绝对地址或实地址 4. 物理空间物理空间（主存空间）（主存空间） 物理地址的集合所对应的空间物理地址的集合所对应的空间 用户程序是在物理空间中执行用户程序是在物理空间中执行95 主存管理的功能，可分为四

73、个方面：主存管理的功能，可分为四个方面： (1) 地址的映射地址的映射 (2) 主存分配主存分配 (3) 存储保护存储保护 (4) 主存扩充主存扩充 7. 2 主存管理的功能主存管理的功能96一、一、地址地址映射映射 1. 为什么要进行地址映射为什么要进行地址映射 进程运行时，程序中所要访问的进程运行时，程序中所要访问的逻辑地址逻辑地址 通常与主存空间中的通常与主存空间中的物理地址物理地址是不同的是不同的mov r1,500123mov r1,500123010050059901000110015001599256k-1作业地址空间作业地址空间主存空间主存空间 这种情况可用图来说明这种情况可用

74、图来说明97 2. 什么是地址映射什么是地址映射 将程序空间中使用的将程序空间中使用的逻辑地址逻辑地址，变换成主存中物，变换成主存中物理地址的过程，称为地址映射理地址的过程，称为地址映射 . 地址映射的方式地址映射的方式 (1) 在程序中使用物理地址在程序中使用物理地址 用物理地址编写程序用物理地址编写程序(机器语言机器语言) 或：在连接时完成或：在连接时完成逻辑逻辑地址、地址、物理物理地址间的变换地址间的变换Mov r1 , 1500优点：优点：访问速度快访问速度快缺点：缺点：程序只能在确定的机器、确定的装入点运行程序只能在确定的机器、确定的装入点运行 在多道环境下无法实现在多道环境下无法实

75、现为什么？为什么？ 98 (2) 静态静态地址映射地址映射 在在作业装入作业装入过程中，随即进行的地址变换。过程中，随即进行的地址变换。称为称为静态重定位静态重定位、或、或静态地址映射静态地址映射mov r1,500123mov r1,500+m12301005005990m256k-1作业地址空间作业地址空间主存空间主存空间m+500重定位重定位装入程序装入程序优点：优点：访问速度快；访问速度快； 可在任意装入点和其他的机器上运行。可在任意装入点和其他的机器上运行。不足：不足： 程序装入后不能在内存浮动程序装入后不能在内存浮动(难于内、外存交换难于内、外存交换) 99 (3) 动态动态地址映

76、射地址映射 在在进程的执行进程的执行期间，随着每条指令或数据的期间，随着每条指令或数据的访问，进行地址映射访问，进行地址映射 mov r1,500123 mov r1 , 500 123010050059901000256k-1作业地址空间作业地址空间存储空间存储空间重定位寄存器重定位寄存器110015001600500 1000逻辑地址逻辑地址+寄存器寄存器100优点：优点： 通过改变通过改变重定位寄存器重定位寄存器内容，可以实现：内容，可以实现： 程序在内存程序在内存可移动可移动 一个程序可放在，多个一个程序可放在，多个不连续不连续的内存区域的内存区域 一个程序一个程序仅仅装入装入部分内容

77、部分内容，就可运行，就可运行 多个进程多个进程共享共享同一个程序的内存同一个程序的内存付本付本 101 二、主存扩充二、主存扩充 计算机一出现，主存的容量就显得十分紧张计算机一出现，主存的容量就显得十分紧张 表现为二种形式：表现为二种形式： 1、 用户程序的空间用户程序的空间 主存空间主存空间程序程序 I 程序程序 j 外存外存 解决方案：解决方案：进程的进程的整个程序整个程序在内外存之间交换在内外存之间交换(分区分区)102文档文档*2、某个用户程序的空间某个用户程序的空间 主存空间主存空间 (1) 解决问题的思路解决问题的思路 例如在例如在Word中进行编辑时：中进行编辑时： 只有在屏幕的

78、窗口中只有在屏幕的窗口中 才能进行编辑才能进行编辑 因此可将该窗口看作是一个因此可将该窗口看作是一个编辑器编辑器 这个可滚动的窗口就是一个这个可滚动的窗口就是一个虚拟编辑器虚拟编辑器 当文档比窗口大时：当文档比窗口大时： 我们是如何进行编辑的呢？我们是如何进行编辑的呢？103 (2) 实现方法实现方法 (a) 采用覆盖技术采用覆盖技术无调用关系的部分程序段无调用关系的部分程序段，在内、外存之间交换，在内、外存之间交换 程序执行时：程序执行时： 一段时间内一段时间内频繁使用频繁使用的仅是程序的一部分的仅是程序的一部分因此只需装入部分内容，程序也能正确地执行因此只需装入部分内容，程序也能正确地执行

79、 main( ) sub1( ) sub2( ) func1( ) func2( ) main( ) sub1( ) sub2( ) Func不足：不足：只是局部改善只是局部改善 104 (b) 采用采用虚拟存储器虚拟存储器 程序的全部代码和数据，存放在外存中程序的全部代码和数据，存放在外存中 将当前执行的那部分将当前执行的那部分代码代码和数据和数据放入主存中放入主存中 在程序的执行过程中，当所需信息在程序的执行过程中，当所需信息不在主存时不在主存时 从从辅存调入到辅存调入到主存主存中中外存外存 程序段程序段 A 程序段程序段B 程序段程序段 C 105 (3) 什么是虚拟存储器什么是虚拟存储

80、器 由操作系统和硬件相配合，完成由操作系统和硬件相配合，完成信息在主存信息在主存和和辅存辅存之间的交换之间的交换 从而提供了一个从而提供了一个存储容量比实际主存大得多存储容量比实际主存大得多的存储器的存储器 由于这个存储器在由于这个存储器在物理上物理上并不存在，故称为并不存在，故称为 虚拟存储器，简称为虚拟存储器，简称为虚存虚存(是一种技术是一种技术)思考：思考： 虚拟存储器的容量是有限的吗？虚拟存储器的容量是有限的吗？ 虚存的最大容量，本质上由什么来决定？虚存的最大容量，本质上由什么来决定？ 106 三、主存分配三、主存分配 主存的分配涉及到：主存的分配涉及到： 1、构造分配用的数据结构、构

81、造分配用的数据结构 2、制定各种策略、制定各种策略 (1) 主存分配策略主存分配策略 (2) 放置策略放置策略 即当有多个即当有多个满足要求的空闲区满足要求的空闲区时：时： 选择哪个空闲区进行分配选择哪个空闲区进行分配 1073、实施主存的分配、实施主存的分配(及回收及回收) 申请：申请：提出所需主存的大小提出所需主存的大小 返回：返回：已分配主存的首地址已分配主存的首地址 (3) 调入策略调入策略 决定信息装入主存的时机，决定信息装入主存的时机，可分为可分为 预调：预调：在访问前将信息调入主存在访问前将信息调入主存 请调：请调：当需要信息时，才将信息调入主存当需要信息时，才将信息调入主存 (

82、4) 淘汰策略淘汰策略 当主存中没有可用的空闲区时：当主存中没有可用的空闲区时： 决定将哪些信息从主存中移走决定将哪些信息从主存中移走108 2、存储保护的方法、存储保护的方法 通常的可分为二个层次：通常的可分为二个层次： (1) 界地址保护：界地址保护：让不让访问让不让访问 (2) 存储控制保护：存储控制保护：让不让、及允许如何访问让不让、及允许如何访问 四、存储保护四、存储保护 1、什么是存储保护、什么是存储保护 在多用户环境中，必须保证：在多用户环境中，必须保证： 每道程序只能每道程序只能在指定的存储区域内、在指定的存储区域内、 进行指定的活动进行指定的活动，这种措施叫做存储保护，这种措

83、施叫做存储保护109 3、界界地址保护地址保护下界寄存器下界寄存器 20KB mov r1 , D 123020KB 256KB存储空间存储空间24KB上界寄存器上界寄存器 24KB保护方式：保护方式： 每次进行地址访问时，进行越界检测每次进行地址访问时，进行越界检测 若：若：下界寄存器下界寄存器 访问地址访问地址D 上界寄存器上界寄存器 则允许访问；则允许访问； 否则：发生越界中断否则：发生越界中断 思考：思考：适用于那种地址映射？适用于那种地址映射？ (1) 上、下界保护上、下界保护 设置设置 上、下界上、下界 寄存器寄存器110 () 基址、限长保护基址、限长保护 设置基址、限长设置基址

84、、限长 寄存器寄存器基址寄存器基址寄存器 20KB mov r1 , D 123020KB 256KB存储空间存储空间24KB限长寄存器限长寄存器 4KB保护方式：保护方式：每次进行地址访问时，进行越界检测每次进行地址访问时，进行越界检测 若：若：0 访问地址访问地址D 限长寄存器限长寄存器 允许访问；允许访问； 否则：发生越界中断否则：发生越界中断 1114、存储控制保护、存储控制保护关键是建立：进程存储区关键是建立：进程存储区允许的访问允许的访问 os 0 RWE 2 R 3 RE 2PSW2 RWE Write ( ) 程序的大小通常是不同的，程序的大小通常是不同的，这些区域怎么划分呢？

85、这些区域怎么划分呢？ 早期是早期是固定分区固定分区，以后发展为，以后发展为动态分区动态分区。7. 3 分区存储管理分区存储管理 基本思想：基本思想：内存划分成多个区域，每个程序内存划分成多个区域，每个程序完整地完整地装入到某一个区域中装入到某一个区域中(提不提供虚存？提不提供虚存？)。一、动态分区一、动态分区 1、什么是动态分区、什么是动态分区 在每个作业的装入过程中，依作业的大小，在空闲主在每个作业的装入过程中，依作业的大小，在空闲主存中建立一个分区，将作业的程序装入该分区中存中建立一个分区，将作业的程序装入该分区中特点：特点：分区的分区的位置位置、分区数分区数及及大小大小都是不都是不固定的

86、固定的 1132. 动态分区的过程动态分区的过程 (1) 动态分区的分配动态分区的分配 os 0 256KB主主 存存 20KB 作页作页 1 220KB 作页作页 2 180KB 作页作页 3 130KB 作页作页 4 60KB114 (2) 动态分区的回收动态分区的回收 20KB 0 os 作业作业4 作业作业3 作业作业2 作业作业1 52KB66KB130KB230KB256KB主存主存20KB 0 os 作业作业4 作业作业2 作业作业1 52KB66KB130KB230KB256KB主存主存作业作业3完成完成作业作业1完成完成20KB 0 os 作业作业4 作业作业2 52KB66

87、KB130KB256KB主存主存问题：问题：每个分区的属性应如何描述？每个分区的属性应如何描述？ 如何尽快地找到如何尽快地找到满足要求满足要求的空闲区呢？的空闲区呢？ 115 五、五、 碎片问题碎片问题 1、什么是碎片问题、什么是碎片问题 在已分配区之间存在着的一些在已分配区之间存在着的一些不能被利用的不能被利用的极小极小空闲区空闲区，浪费了内存，浪费了内存 os 作业作业1 作业作业3 作业作业4 主存主存2、如何解决碎片问题、如何解决碎片问题(1) 规定剩余分区的阀值规定剩余分区的阀值(2) 采用拼接技术：采用拼接技术： 移动某些已分配区中的信息移动某些已分配区中的信息将多个空闲区连成一个

88、大空闲区将多个空闲区连成一个大空闲区 116 (1) 进程的程序空间大小不同，形成的分区也大进程的程序空间大小不同，形成的分区也大小不同小不同 (由程序所决定，由程序所决定，无法解决无法解决) 4、分区存在的问题、分区存在的问题 某些程序无法装入。可分为二种情况：某些程序无法装入。可分为二种情况： (1) 存在碎片，使得存在碎片，使得本可装入的程序本可装入的程序无法装入无法装入 (降低了内存利用率，而拼接的开销大降低了内存利用率，而拼接的开销大) (2) 没有足够的空闲内存时，作业无法装入没有足够的空闲内存时，作业无法装入 如何解决呢？如何解决呢？ (2) 每个作业都要求一片每个作业都要求一片

89、连续的连续的内存区域内存区域3、产生碎片的原因是什么呢、产生碎片的原因是什么呢？5. 解决办法解决办法 (1) 允许将一个程序放在多个允许将一个程序放在多个不连续的不连续的区域中区域中 （没有不能利用的区域，消除了碎片）（没有不能利用的区域，消除了碎片） (3) 允许只装入一个作业的部分内容允许只装入一个作业的部分内容 （用来提供虚存）（用来提供虚存） (2) 将内存划分成多个大小相等的将内存划分成多个大小相等的单位区域单位区域 （便于管理）（便于管理）7. 4 页式存储管理页式存储管理 一、基本概念一、基本概念 1. 主存块主存块 主存被等分成主存被等分成大小相等的片大小相等的片 称为主存块

90、称为主存块(简称简称块块)，又称为，又称为实页实页 2. 页面页面 程序的地址空间也被等分成程序的地址空间也被等分成与块相等的片与块相等的片 称为页面称为页面(简称简称页页) ，又称为，又称为虚页虚页119 . 内存的分配内存的分配 以以页页为单位，分配为单位，分配主存块主存块 块与块之间，可以不连续块与块之间，可以不连续 思考：思考： 内存有没有内存有没有未被利用的区域？未被利用的区域？ 平均浪费率？平均浪费率？ (但不能称为碎片但不能称为碎片) 120 4. 作业的页面与主存块的关系作业的页面与主存块的关系 问题：问题： 块块的大小应该如何来定呢？的大小应该如何来定呢？ 02KB254KB

91、02KB4KB6KB主主 存存作业地址空间作业地址空间1215.页长页长页页(或块或块)的大小称为的大小称为页长页长。页长通常为：。页长通常为：512B(1000000000) 4kB (1000000000000) 1kB (10000000000) 8kB (10000000000000) 2kB (100000000000) 思考：思考： (1) 页长值有何特点？页长值有何特点？ 为什么？为什么？ (2) 能否太大、太小？能否太大、太小？太大：太大：类似于固定分区；类似于固定分区；太小：太小：页面交换频繁页面交换频繁另外，也是为了提高内存的利用率。另外，也是为了提高内存的利用率。例如：当

92、程序的平均长度为例如：当程序的平均长度为512k时，若页长为时，若页长为1k 则内存的利用率最高则内存的利用率最高(99.8%)。 确定页长确定页长 二、页式存储管理的地址变换二、页式存储管理的地址变换 思考：思考： 分区存储管理是分区存储管理是如何实现地址如何实现地址变换的？变换的？mov r1,500123 mov r1 , 500 123010050059901000256k-1作业地址空间作业地址空间存储空间存储空间重定位寄存器重定位寄存器110015001600500 1000逻辑地址逻辑地址+物理地址物理地址分区首址分区首址(基址寄存器基址寄存器)逻辑地址逻辑地址 1000基址寄存

93、器基址寄存器 500逻辑地址寄存器逻辑地址寄存器123 1. 页表页表 记录一个进程中，每一个记录一个进程中，每一个页面页面与与内存块内存块对应关系的对应关系的地址变换机构，称为页面映像表。简称为地址变换机构，称为页面映像表。简称为页表页表 02KB4KB254KB 256KB02KB4KB6KB作业地址空间作业地址空间页式系统只保留程序的页式系统只保留程序的首地址首地址行不行？行不行？100KB102KB 内内 存存必须保留每一页的必须保留每一页的首地址首地址124 2. 分页存储映像的例子分页存储映像的例子 思考：思考：如何由如何由逻辑地址逻辑地址，得到，得到页号、页内位移页号、页内位移？

94、 再得到再得到块号、块内位移块号、块内位移(页内位移页内位移？) 01KB01KB2KB3KB1主存主存作业作业2地址空间地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作业作业1地址空间地址空间01KB1作业作业3地址空间地址空间0516页号页号块号块号02140827作业作业1页表页表作业作业2页表页表作业作业3页表页表osos125 3、逻辑地址结构逻辑地址结构 设逻辑地址的长度为设逻辑地址的长度为16位，页面大小为位，页面大小为 1KB (10位位)。若给出以下的逻辑地址：。若给出以下的逻辑地址： 0000000000000010 0000110000

95、000010 其对应的其对应的页号、页内位移页号、页内位移各是多少呢？各是多少呢？ p w 页号页号页内位移页内位移15 10 9 0126 因为页长是因为页长是2的整数次方的整数次方 所以页号和页内位移所以页号和页内位移 是系统根据逻辑地址的结构是系统根据逻辑地址的结构自动形成的自动形成的 注意：注意： 用户在程序中使用的逻辑地址用户在程序中使用的逻辑地址 仍是仍是一维地址一维地址 即：分页即：分页对用户是不可见对用户是不可见(透明透明)的的 127页表 2500123+01KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmov r1 , 2500123021427

96、 000010 011100010015 10 9 0页号页号:2位移位移: 452 000111 011100010015 10 9 0块号块号P块内位移块内位移W01KB2KB3KB1作业2地址空间页表始址寄存器页表始址寄存器 4. 页的地址变换页的地址变换 逻辑地址寄存器逻辑地址寄存器物理地址寄存器物理地址寄存器128 页式地址变换的步骤页式地址变换的步骤 将访问地址将访问地址(2500)送逻辑地址寄存器送逻辑地址寄存器 由分页机构把逻辑地址由分页机构把逻辑地址自动地分为自动地分为两部分：两部分：页号页号p (2)、页内相对位移、页内相对位移w (452) 根据根据页表首址寄存器页表首址

97、寄存器给出的给出的页表首址页表首址 以页号查页表，得到对应的块号以页号查页表，得到对应的块号b(7) 将块号将块号b (7)和页内位和页内位w (452)拼接拼接在一起在一起 形成访问主存的物理地址形成访问主存的物理地址(7620) 129 (2) 页表的实现页表的实现 页表的实现有三种可能的方式页表的实现有三种可能的方式 页表在主存中：页表在主存中： 每次存取需访问主存二次，存取时间延长一倍每次存取需访问主存二次，存取时间延长一倍 页表在高速缓冲存储器中：页表在高速缓冲存储器中： 地址变换速度快，但硬件的成本较高地址变换速度快，但硬件的成本较高 综合：综合：将将当前使用的当前使用的部分部分页

98、表项页表项 放到高速缓冲存储器中，称其为放到高速缓冲存储器中，称其为快表快表 命中率命中率：816个高速缓存，命中率可达个高速缓存，命中率可达8597 % 原因：原因： 当当页长为页长为1K、字长为、字长为2B时，每页有时，每页有512条指令条指令 130快表快表 2500123+01KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmov r1 , 250012327 000010 011100010015 10 9 0页号页号2位移位移452 000111 011100010015 10 9 0块号块号P块内位移块内位移W01KB2KB3KB1页表始址寄存器页表始址

99、寄存器页表页表 内存的有效存取时间内存的有效存取时间 通过快表实现的地址变换通过快表实现的地址变换131 三、请求分页三、请求分页 1、两种页式系统、两种页式系统 (1) 简单页式系统简单页式系统(早期早期) 装入一个作业的全部页面后装入一个作业的全部页面后 才能运行才能运行(不提供虚存不提供虚存) (2) 请求分页系统请求分页系统(现代现代) 只装入一个作业的部分页面只装入一个作业的部分页面 即可运行即可运行(提供虚存提供虚存) 页式系统是如何提供虚存的呢？页式系统是如何提供虚存的呢？132 2、页面调入的方式、页面调入的方式 (1) 预调预调问题是无法预测以后要访问的页面问题是无法预测以后

100、要访问的页面 (2) 请调请调 当发现所需访问的页面不在主存时再调入当发现所需访问的页面不在主存时再调入 效果：效果： 对对页面页面是是请调请调，而对，而对指令指令基本是基本是预调预调 原因：原因：同前同前 问题问题1：该页的其他指令就是下一步要用的吗？该页的其他指令就是下一步要用的吗？ 133问题问题2： 有没有一个最佳的：命中率有没有一个最佳的：命中率/内存页面数？内存页面数？ (见见P163请求分页需解决的问题请求分页需解决的问题 如何知道所访问的页面如何知道所访问的页面在不在主存在不在主存？ 当发现访问的页面不在主存时如何处理当发现访问的页面不在主存时如何处理? 局部性原理局部性原理(

101、见见P163)： 时间局部性时间局部性 空间局部性空间局部性 为什么程序会具有局部性原理为什么程序会具有局部性原理?134 中断位中断位 ： 表示该页是否在主存表示该页是否在主存 1：不在主存；：不在主存； 0：在主存：在主存 辅存地址：辅存地址：该页在辅存的位置该页在辅存的位置(用于调入用于调入) 3、扩充的页表功能、扩充的页表功能 页页 号号 主存块号主存块号 中断位中断位 引用位引用位 改变改变位位 辅存地址辅存地址 引用位：引用位：表示该页表示该页最近最近是否被访问过是否被访问过(用于淘汰选择用于淘汰选择) 1：最近被访问过；：最近被访问过； 0：最近未被访问过；：最近未被访问过； 改

102、变位：改变位：表示该页是否被修改过表示该页是否被修改过 1：已被修改过；：已被修改过； 0：未被修改过：未被修改过 实现请实现请求分页求分页(为什么要此项？为什么要此项？) 135 置换方式：置换方式： 全局置换：在内存的全局置换：在内存的所有页面所有页面之间进行置换之间进行置换 局部置换：局部置换：规定每个进程在规定每个进程在内存的最多页面数内存的最多页面数 (工作集工作集)，进程在自己的，进程在自己的工作集工作集之内进行置换之内进行置换 4、缺页的处理、缺页的处理 一个作业被装入时，通常只一个作业被装入时，通常只建立页表建立页表(或再装入或再装入页页) 当要访问的页面不在内存时，产生一个当

103、要访问的页面不在内存时，产生一个缺页中断缺页中断 由缺页中断处理程序完成：由缺页中断处理程序完成： 将该页调入内存将该页调入内存(若没有空闲块，则若没有空闲块，则先进行淘汰先进行淘汰)问题：问题：在在哪些页面间哪些页面间进行淘汰呢进行淘汰呢136 2、颠簸、颠簸(thrashing) 将主存和辅存之间，将主存和辅存之间，频繁的频繁的页面置换现像称为页面置换现像称为 颠簸颠簸(抖动抖动)，它导致了系统的效率急剧下降，它导致了系统的效率急剧下降 四、淘汰策略四、淘汰策略 1、什么是淘汰策略、什么是淘汰策略 当要调入某个页面，而又没有空闲内存块时，当要调入某个页面，而又没有空闲内存块时， 用来选择换

104、出哪一页的规则，称为用来选择换出哪一页的规则，称为淘汰策略淘汰策略 （也称为（也称为置换算法置换算法）页面的置换会不会降低系统的效率呢？页面的置换会不会降低系统的效率呢？1370123页页 号号2 4 替换指针替换指针 (1) 先进先出算法先进先出算法(FIFO算法算法) 选择在主存中居留时间最长选择在主存中居留时间最长(最早调入最早调入)的一页淘汰的一页淘汰4、常用的页面淘汰算法、常用的页面淘汰算法实现：实现：可用一个数组，代替可用一个数组，代替 按按FIFO排序的排序的定长队列定长队列 (减少维护的开销减少维护的开销)评价：评价： 容易实现容易实现 适用于：适用于： 顺序访问顺序访问的地址

105、空间的地址空间(指令代指令代 码、数组码、数组等等) 效率较差，效率较差，原因：原因： 程序中存在大量的程序中存在大量的循环循环、转移指令转移指令、子程序调用等子程序调用等 138(2) 最久未使用淘汰算法最久未使用淘汰算法(LRU算法算法) 选择选择最长时间未被使用最长时间未被使用的那一页淘汰掉的那一页淘汰掉 实现方法：实现方法： 采用一个队列采用一个队列 新访问新访问的页面插入队尾的页面插入队尾(若已在队列，先抽出若已在队列，先抽出) 淘汰淘汰的页面为的页面为队首元素队首元素(未使用的时间最久未使用的时间最久) 评价：评价：缺页中断率较低，但要维护队列缺页中断率较低，但要维护队列 未被使用

106、时间未被使用时间 = 当前时间当前时间 最近访问时间最近访问时间 为避免计算：为避免计算： 可用可用最近访问时间最近访问时间，按，按FIFO排序排序以后访问的页号为：以后访问的页号为： 00 页面淘汰数？页面淘汰数？ 52312 1 2 3120203230304042 4 51 2 0 3 0 4 2 内存页队列内存页队列 缺页中断数缺页中断数例：某进程允许有例：某进程允许有3个内存页面，初始装入第个内存页面，初始装入第0页页140问题：问题：每次访问内存时，每次访问内存时， 都要对队列进行搜索、维护，都要对队列进行搜索、维护， 系统的开销较大。系统的开销较大。能否保留能否保留核心原则核心原

107、则，而做进一步的，而做进一步的简化简化呢？呢？(3) LRU近似算法近似算法 从最久未被使用的从最久未被使用的一批页面一批页面中，选择某一页淘汰中，选择某一页淘汰实现：实现： 在页表中加在页表中加引用位引用位 页面页面被访问时被访问时：引用位置：引用位置 1 页面页面淘汰时淘汰时：淘汰引用位为：淘汰引用位为 0 的的问题？问题？ 141解决办法：解决办法： 每隔一段时间，将所有内存页面的引用位置每隔一段时间，将所有内存页面的引用位置0 改进算法改进算法 ： 对最久未被使用的对最久未被使用的一批页面一批页面 按按FIFO进行淘汰进行淘汰仍存在的仍存在的问题：问题： 时间间隔的长短，影响为时间间隔

108、的长短，影响为0、为、为1页面的比例页面的比例如何实现呢？如何实现呢？ 对多个为对多个为 0 的页面，按什么策略进行淘汰？的页面，按什么策略进行淘汰？1421234页页 号号2 4 替换指针替换指针引用引用001 每个进程的每个进程的内存页面号内存页面号放在一个数组中放在一个数组中 用替换指针选择被淘汰的页面用替换指针选择被淘汰的页面(类似类似FIFO) 每次要淘汰时：每次要淘汰时： 选择引用位为选择引用位为 0 的淘汰；的淘汰； 否则，引用位否则，引用位改为改为思考：思考：每次淘汰时，是否总能选择一页淘汰？每次淘汰时，是否总能选择一页淘汰？ 例如：当前要调入第例如：当前要调入第 8 页页14

109、3 (4) 最不经常使用淘汰算法最不经常使用淘汰算法(LFU算法算法) 选择某段时间以来选择某段时间以来 访问次数最少的那一页淘汰掉访问次数最少的那一页淘汰掉 实现：实现：在页表中设置一记数器在页表中设置一记数器 页面被访问时：页面被访问时：页表中的记数器加页表中的记数器加1 页面淘汰时：页面淘汰时： 选择记数器值最小的选择记数器值最小的 评价：评价： 效率同效率同LRU算法接近算法接近 且不需增加另外的且不需增加另外的结构结构 如果会溢出，如果会溢出，怎么处理？怎么处理？ 定期置定期置 0 ? 问题问题2：对前面的各种页面淘汰策略：对前面的各种页面淘汰策略： 页面淘汰时都可能要页面淘汰时都可

110、能要重写外存重写外存(造成延时造成延时) 能否预先进行淘汰能否预先进行淘汰? UNIX中的页面淘汰中的页面淘汰 问题问题1： 记数器会溢出吗？记数器会溢出吗？五、存储分配的数据结构五、存储分配的数据结构 1.存储分块表存储分块表等待队列指针等待队列指针存储分块表首址存储分块表首址分配程序入口地址分配程序入口地址0空闲块首指针空闲块首指针1 OS2 OS3作业作业2的的 0页页k空闲块空闲块m空闲块空闲块n块号块号空闲块指针空闲块指针2.主存资源信息块主存资源信息块3. 作业分块表作业分块表 2 4 3104作业号作业号最多占用块数最多占用块数012页页 表表 1012页页 表表 201k2k程

111、序空间程序空间1sub0 0 1k 2k程序空间程序空间2sub0151515内存内存sub0六、页面的共享六、页面的共享 通过页表实现通过页表实现:01k2k程序空间程序空间1 0 1k 2k程序空间程序空间2012页页 表表 1012页页 表表 2sub1sub1内存内存15k15sub117k5000问题：问题：若子程序的若子程序的首地址首地址，在二个程序空间中的，在二个程序空间中的 页内偏移地址页内偏移地址不同，如何实现共享？不同，如何实现共享？15500001k2k程序程序1空间空间 0 1k 2k程序程序2空间空间sub0sub0内存内存15ksub017k2. 每个子程序都从每个

112、子程序都从 0 开始，开始，单独编址单独编址 即：程序采用即：程序采用二维的地址空间二维的地址空间 问题：问题：程序空间中可能会出现程序空间中可能会出现空洞空洞 解决方法解决方法1. 子程序的首址，必须与页的首址重合子程序的首址，必须与页的首址重合 1. 什么是段什么是段 段是程序中自然划分的段是程序中自然划分的 一组一组逻辑意义完整逻辑意义完整的信息集合的信息集合7. 5 段式存储管理段式存储管理 在段式、或页式系统中在段式、或页式系统中 程序的程序的地址空间地址空间有什么不同呢？有什么不同呢？ 一一. 段式地址空间段式地址空间 如如C语言中：主程序段、各函数子程序段语言中：主程序段、各函数

113、子程序段 DOS中：中： 代码段、数据段、代码段、数据段、 堆栈段堆栈段 Unix中：中： 正文段、数据段、用户栈段正文段、数据段、用户栈段150Sub1( )Sub2( )Sub3( )Main( )页式系统页式系统段式系统段式系统0000L1-1L2-1L3-1L4-1Main( )Sub1( )Sub2( )Sub3( )0L1L1+L2L1+L2+L3L1+L2+L3+l40页页1页页2页页3页页4页页页式系统破坏了程序的完整性：如执行页式系统破坏了程序的完整性：如执行Sub1( )1512. 段的程序空间段的程序空间 由若干个由若干个逻辑段逻辑段组成组成 每个段有自己的名称每个段有自

114、己的名称 (或标识或标识) 每个段每个段都是一个独立的都是一个独立的一维地址空间一维地址空间 因此，因此，程序空间程序空间是一个是一个二维的线性地址空间二维的线性地址空间3. 内存的分配内存的分配 以以段段为单位，分配到一个空闲的为单位，分配到一个空闲的内存区域内存区域 (类似于类似于分区分区中的一个执行程序中的一个执行程序) 多个段的内存区域之间可以多个段的内存区域之间可以不连续不连续 可仅装入可仅装入部分段部分段(类似于分页，提供类似于分页，提供虚页虚页) 152. 段的二维逻辑地址形式段的二维逻辑地址形式 段段 号号 S 段段 内内 位位 移移 W与页不同，与页不同，段段对用户是可见的、

115、对用户是可见的、且段长可不相等且段长可不相等程序空间程序空间0003k-14k-12k-1代码段代码段数据段数据段堆栈段堆栈段堆栈段堆栈段代码段代码段内存内存02k9k100M4k13k数据段数据段代码段代码段堆栈段堆栈段9K2K段表段表153二、段式地址变换二、段式地址变换 取出程序地址取出程序地址(S，W)内存内存段表段表 长度长度 基址基址 L B s w B + w第第S段段段号段号段内位移段内位移 否则：用否则：用 S 检索段表，得到段的内存首地址检索段表，得到段的内存首地址B (BW) 即为所需的内存地址即为所需的内存地址 思考：思考：为什么不进行拼接？为什么不进行拼接？ 如果：如

116、果： W 0 或或 W L ，则地址越界则地址越界154段式段式分区分区 程序程序分页分页 7. 6 段页式存储管理段页式存储管理 1. 基本思想基本思想 4KB0代码段代码段 3KB0数据段数据段 2KB0栈段栈段 例：一个用户程序的例：一个用户程序的地址空间地址空间，可分别表示为，可分别表示为即：即：内存分块内存分块、程序分段、程序分段、每个段再分页每个段再分页段段分页分页155 2. 段表、页表与主存的关系段表、页表与主存的关系 01n段号段号 页表长度页表长度 页表始址页表始址 2 页页号号01块号块号其他0段页表段页表页页号号01块号块号其他1段页表段页表主存主存段表：段表：实现实现

117、间接间接地址映射地址映射 段段表表各段页表各段页表156 3. 段页式地址变换的步骤段页式地址变换的步骤 给出访问地址：段号给出访问地址：段号S、段内位移、段内位移SW 由由段号段号S查段表，得到该段的查段表，得到该段的页表始址页表始址 由由页号页号P查页表，得到对应的块号查页表，得到对应的块号b 将块号将块号b和页内位移和页内位移w拼接在一起拼接在一起 形成主存的物理地址形成主存的物理地址 4. 缺段：缺段：仅生成该段的页表仅生成该段的页表 5. 缺页缺页：调入该页调入该页 UNIX的存储管理的存储管理 将段内位移将段内位移 SW分为两部分：分为两部分：该段内的页号该段内的页号P 、页内位移

118、、页内位移w1578. 1 I/O管理的概念管理的概念 一、一、设备的分类设备的分类 1. 按系统和用户分按系统和用户分 系统设备系统设备(标准设备标准设备) OS生成时，驱动程序已安装，如终端生成时，驱动程序已安装，如终端 用户设备用户设备(非标准设备非标准设备) 使用前必须安装驱动程序使用前必须安装驱动程序2. 按信息的基本单位按信息的基本单位(或用途或用途)分分 块设备块设备(存储设备存储设备)：如磁盘、磁带等：如磁盘、磁带等 字符设备字符设备(I/O设备设备) ：如键盘、打印机等：如键盘、打印机等 158 五、五、 设备独立性设备独立性 1. 有关的概念有关的概念(1) 物理设备名物理

119、设备名 是是系统系统为设备指定的内部标识为设备指定的内部标识 它是永久的、不可更改的它是永久的、不可更改的 (2) 逻辑设备名逻辑设备名是是用户用户为设备定义的设备名为设备定义的设备名(或设备号或设备号) 它是它是暂时的、相对的、可更改的暂时的、相对的、可更改的159 (3) 设备独立性设备独立性 所谓的所谓的设备独立性设备独立性是指：是指： 用户在程序中所使用的设备用户在程序中所使用的设备 与实际使用的物理设备无关与实际使用的物理设备无关 即：即： 在用户程序中在用户程序中 可用可用逻辑设备名逻辑设备名来使用设备来使用设备 160 2. 设备独立性的二个层面设备独立性的二个层面 独立于同一类

120、设备中的独立于同一类设备中的具体设备具体设备 如：不区分哪一台打印机如：不区分哪一台打印机 (直接用直接用Print语句使用语句使用) 独立于设备的独立于设备的类型类型 如：只分为如：只分为输入输入、输出输出设备设备 (直接用直接用 Read、Write语句使用语句使用) 1613. 实现设备独立性的优点实现设备独立性的优点 方便方便用户的使用用户的使用 提高系统资源的提高系统资源的利用率利用率 提高系统的提高系统的可扩展性可扩展性和和可适应性可适应性 (增加设备、程序与硬件环境无关增加设备、程序与硬件环境无关)要解决的问题：要解决的问题： 用户如何为设备用户如何为设备定义定义自己的逻辑设备名

121、？自己的逻辑设备名？ 如何建立逻辑设备与物理设备之间的如何建立逻辑设备与物理设备之间的映射映射？ 1624. 在程序中使用逻辑设备名在程序中使用逻辑设备名例例1: fd = open(“d1/date.txt”，O-WRONLY) number = read(fd ，buf，count)例例2: 在在UNIX 中用中用重定向重定向命令映射物理设备。如：命令映射物理设备。如： (1) 如在程序如在程序f1.c中中 fprint(“abcdefg/n”) /*隐含隐含:在在标准设备标准设备输出输出 (2) 执行程序时，与物理设备连接执行程序时，与物理设备连接 $ f1 /*缺省，输出到缺省，输出到

122、显示器显示器 $ f1 dev / lp /*指定，输出到指定，输出到打印机打印机 问题：问题：还有没有更还有没有更一般一般的映射方法呢？的映射方法呢？ 163 5. 用操作命令指定逻辑设备的映射用操作命令指定逻辑设备的映射 (1) 用用作业说明语句作业说明语句 逻辑设备名逻辑设备名= 物理设备名物理设备名逻辑设备名逻辑设备名物理设备名物理设备名设备控制块指针设备控制块指针逻辑设备名逻辑设备名物理设备名物理设备名设备控制块指针设备控制块指针PCBLDD1LDDn 6. 逻辑设备描述器逻辑设备描述器 (2) 用用键盘命令键盘命令 ASSIGN 物理设备名物理设备名 逻辑设备名逻辑设备名164 问

123、题：问题： 操作系统如何操作系统如何知道知道系统有哪些设备系统有哪些设备 进而进而了解了解每个物理设备的属性每个物理设备的属性 并对设备进行并对设备进行管理管理的呢？的呢？ 六、设备控制块六、设备控制块 每一台设备，都必须用一个用数据结构来每一台设备，都必须用一个用数据结构来 记录该设备的硬件记录该设备的硬件特性特性、连接连接和和使用使用情况情况 称其为设备控制块称其为设备控制块 其内容主要有：其内容主要有： 165设备名设备名设备属性设备属性指向指向命令转换表命令转换表的指针的指针在在I/ /O总线上的设备地址总线上的设备地址设备状态（设备状态（锁标志锁标志）当前用户进程指针当前用户进程指针

124、I/O请求队列请求队列指针指针 设备名：设备名： 即设备的物理名，是设备的内部标识即设备的物理名，是设备的内部标识 设备属性：设备属性： 描述设备物理特性的一组信息描述设备物理特性的一组信息 命令转换表：命令转换表：包含该设备的各包含该设备的各I/ /O例程地址例程地址 操作码操作码 例程的入口地址例程的入口地址OpenClose思考思考：内存的单位为内存的单位为字节字节，磁盘的单位为，磁盘的单位为扇区扇区 它们之间的它们之间的信息传输又是如何进行的呢信息传输又是如何进行的呢 ？ 命令转换表命令转换表166 磁盘文件的读写过程（分块读、写）磁盘文件的读写过程（分块读、写）为什么要借助为什么要借

125、助缓冲区缓冲区进行传输呢？进行传输呢？ * * * * * * * * * * * * * * * * *内内 存存缓冲区缓冲区逻辑文件逻辑文件现代所有外部设备都借助现代所有外部设备都借助缓冲区缓冲区进行传输进行传输8. 2 缓冲技术缓冲技术 一、缓冲的概念一、缓冲的概念 1. 为什么要使用缓冲为什么要使用缓冲快速设备快速设备慢速设备慢速设备快速设备快速设备慢速设备慢速设备中速设备中速设备 缓冲缓冲 负载不均匀负载不均匀 读写磁盘时，要读写磁盘时，要组装组装成块成块(扇区扇区) 两种设备之间传输信息时，两种设备之间传输信息时，速度不匹配速度不匹配168 . 什么是缓冲什么是缓冲 缓冲是两种不同

126、速度的设备传输信息时缓冲是两种不同速度的设备传输信息时 用来平滑传输过程用来平滑传输过程的一种常用手段的一种常用手段 I/ /O操作时，缓冲可用来操作时，缓冲可用来暂时暂时存放数据存放数据 . 缓冲的实现缓冲的实现(1) 硬件缓冲器：容量较小，主要为专用硬件缓冲器：容量较小，主要为专用 (2) 软件缓冲区：一片软件缓冲区：一片主存区域主存区域(通用通用)优点：优点：有利于实现多个设备的有利于实现多个设备的并发操作并发操作思考思考：为了提高为了提高CPU与设备的与设备的并发操作并发操作程度程度 缓冲区应该如何组织呢？缓冲区应该如何组织呢？ 169s1w二、常用的缓冲技术二、常用的缓冲技术 1.

127、双缓冲双缓冲 rs2s1w思考思考： 缓冲区更多一些，并发效果会更好缓冲区更多一些，并发效果会更好能否用有限的缓冲区，能否用有限的缓冲区，产生无穷个缓冲区的效果？产生无穷个缓冲区的效果？s2s3wr 如何实现二个缓冲区的并发？如何实现二个缓冲区的并发？rwwr要点：要点：按按相同的次序相同的次序，依次读、写二个缓冲区，依次读、写二个缓冲区问题问题1： 如何用如何用共享一个缓冲区共享一个缓冲区模型实现双缓冲的同步？模型实现双缓冲的同步？170环形缓冲环形缓冲 读读 写写 写写 写写 写写 读读B 0 B 1 B 2 B 3 B 4 思考思考：每个设备必须有一个环形缓冲每个设备必须有一个环形缓冲

128、可能可能忙、闲不等，能否对缓冲区进行忙、闲不等，能否对缓冲区进行共享共享 ？可用指针将其可用指针将其链接链接成一个环形队列成一个环形队列也可用一个数组，通过下标来实现也可用一个数组，通过下标来实现链接链接问题问题2：对读、写进程的同步限制是什么对读、写进程的同步限制是什么?读指针读指针追上追上写指针写指针后不能再读；对写也一样。后不能再读；对写也一样。原因？原因？能否用能否用生产者消费者生产者消费者模型来描述，并实现模型来描述，并实现有序有序的读写的读写 ？171外设外设写缓冲区写缓冲区进程进程读缓冲区读缓冲区进程进程空缓冲区队列空缓冲区队列 (也称为也称为缓冲池缓冲池，同类设备共享，同类设备

129、共享)输输 出出 队队 列列(每个设备每个设备) 同步控制是如何实现的呢？同步控制是如何实现的呢？ 缓冲池缓冲池例例1：一个简单的缓冲区管理系统：一个简单的缓冲区管理系统(输出数据输出数据)缓缓 冲冲 池池 (仅放仅放空缓冲区，空缓冲区，初值为初值为N）设备队列设备队列(初值为初值为空空）设备队列中设备队列中释放的释放的空空缓冲区缓冲区 重新归还到重新归还到缓冲池缓冲池中中 用设备队列来放用设备队列来放满缓冲区满缓冲区 实现：实现： 设置信号灯设置信号灯 S9，表示缓冲池中的，表示缓冲池中的空缓冲数空缓冲数 S1=S2=0，表示，表示设备队列设备队列1、2 中的中的满缓冲数满缓冲数 为实现各个

130、队列的为实现各个队列的互斥，互斥，设置设置3个个互斥信号灯互斥信号灯写缓冲区写缓冲区S = 9S1 = 0S2 = 0S = 8S = 7S = 6S = 7S1 = 1S1 = 2S1 = 1S2 = 1 空缓冲区队列空缓冲区队列 (缓缓 冲冲 池池 ) (N个缓冲区个缓冲区: S + S1 + S2 = N=9)设备设备1 队列队列设备设备2 队列队列读缓冲区读缓冲区应：应：P 缓冲池缓冲池 V 设备队列设备队列应：应：P 设备队列设备队列 V 缓冲池缓冲池思考：思考： 为了为了减少减少对外部设备对外部设备(如磁盘如磁盘)的的IO 缓冲池内的缓冲池内的空缓冲区空缓冲区中：中： 保留着的有用

131、信息，保留着的有用信息， 还能再利用吗？还能再利用吗？ 如何在如何在缓冲池内，缓冲池内，快速地找到：快速地找到： 与指定设备、指定扇区与指定设备、指定扇区 相对应的那一个相对应的那一个缓冲区呢？缓冲区呢？ UNIX中的缓冲区管理中的缓冲区管理 1. 静态分配静态分配不会死锁不会死锁 2. 动态分配动态分配 (1) 每发一个每发一个I/O请求后，必须等待请求后，必须等待不会死锁不会死锁 8. 3设备分配设备分配一、设备一、设备分配的安全性分配的安全性 (2) 允许连续发多个允许连续发多个I/O请求，不满足才等待请求，不满足才等待 会死锁会死锁 176 二二、设备、设备分配技术分配技术(如何占用如

132、何占用) 设备分配的技术有三种设备分配的技术有三种 1. 独享分配技术独享分配技术 (1) 独享设备独享设备 在一段时间内，由一个作业独自在一段时间内，由一个作业独自占用占用(即使没使用即使没使用) (2) 独享分配独享分配 在在作业作业执行前执行前(静态静态)、或、或进程进程提出申请后提出申请后(动态动态) 将所申请的设备分配给它将所申请的设备分配给它 当当作业结束作业结束、或进程、或进程释放设备释放设备后，才将设备收回后，才将设备收回 (即：即：不能强行收回不能强行收回) 问题：问题：设备的利用率低设备的利用率低 177 2. 共共享分配技术享分配技术 (1) 共享设备共享设备 由多个进程

133、由多个进程(在一段时间内在一段时间内)共同使用的设备共同使用的设备 (2) 共享分配共享分配 当进程提出资源申请时，进行分配当进程提出资源申请时，进行分配(动态动态) 进程使用完毕后，进程使用完毕后，立即收回立即收回(只让用，不让占，只让用，不让占， 类似于如类似于如CPU)优点：优点：设备的利用率高设备的利用率高 问题：问题：有些有些设备只能独享。为提高设备的利用率设备只能独享。为提高设备的利用率 能否将能否将独享设备当作共享设备来使用呢独享设备当作共享设备来使用呢 ？ 178 事实：事实：进程占有的进程占有的独享设备在很多时候是独享设备在很多时候是空闲空闲的的 实现：实现：将将进程对进程对

134、独享设备的独享设备的使用时间使用时间集中起来集中起来 即：即：只只连续使用连续使用一次，用完收回一次，用完收回 (对用户加以限制对用户加以限制 ?) 3. 虚拟虚拟分配技术分配技术 (1)(1)虚拟技术：虚拟技术：指在一类物理设备指在一类物理设备( (如如外存外存) )上上 模拟另一类物理设备模拟另一类物理设备( (如打印机如打印机) )的技术的技术 通常是用通常是用共享设备共享设备来模拟来模拟独占设备独占设备 (2) (2)虚拟设备：虚拟设备：把用来代替独占设备的那部分把用来代替独占设备的那部分 外存空间外存空间( (包括有关的控制结构包括有关的控制结构) )，称为，称为虚拟设备虚拟设备(3

135、)3)虚拟分配虚拟分配的实现的实现 179虚宽行虚宽行1虚宽行虚宽行2进程进程A进程进程B进程进程C进程进程D输入井输入井输出井输出井光字符光字符阅读机阅读机打印机打印机虚字符虚字符阅读机阅读机虚字符虚字符阅读机阅读机问题：问题：对虚拟设备的读、写对虚拟设备的读、写是如何实现的呢是如何实现的呢 ？ 虚拟分配：虚拟分配： 就是分配代替独占设备的那部分外存区域就是分配代替独占设备的那部分外存区域1804. 外部设备联机同时操作外部设备联机同时操作(SPOOL) 由三个程序模块合作完成由三个程序模块合作完成(1) 预输入程序预输入程序在作业执行前，从输入设备在作业执行前，从输入设备 预先将输入信息，

136、传送到预先将输入信息，传送到输入井输入井(3) 井管理程序井管理程序(对虚拟设备进行读写对虚拟设备进行读写)进程输入时：将进程输入时：将输入井输入井中的输入信息，中的输入信息，读读到内存到内存进程输出时：将内存中的输出信息，进程输出时：将内存中的输出信息，写写到到输出井输出井 (2) 缓输出程序缓输出程序作业完成后，将作业完成后，将输出井输出井中的信息，传送到输出设备中的信息，传送到输出设备8. 4 输入输入/ /输出控制输出控制一、一、I/O控制的方式控制的方式 主机与外部设备之间主机与外部设备之间 是如何完成信息交换的呢？是如何完成信息交换的呢？ CPU通过通过I/ /O控制器控制器(专用

137、寄存器专用寄存器) 与外部设备进行信息交换与外部设备进行信息交换按照按照I/ /O控制器智能程度的高低控制器智能程度的高低 设备的控制方式可分为四类设备的控制方式可分为四类 完成位完成位启动位启动位控制寄存器控制寄存器1. 循环测试循环测试I/ /O方式方式(早期早期) 问题：问题： CPU与外部设备与外部设备顺序操作顺序操作，利用率低，利用率低 I/O程序程序外部外部设备设备11数据寄存器数据寄存器不断测试不断测试 CPU1832. I/ /O中断方式中断方式(现代现代) 适用于字符设备，一次适用于字符设备，一次传输一个字节传输一个字节中断位中断位启动位启动位控制寄存器控制寄存器问题：问题：

138、 中断频繁，传送大量字符时，效率低中断频繁，传送大量字符时，效率低 I/O程序程序外部外部设备设备1数据寄存器数据寄存器中断处理中断处理程序程序等待等待 CPU184 3. DMA(直接存储器存取直接存储器存取)方式方式 主要用于微机的外存储设备（磁盘）主要用于微机的外存储设备（磁盘） 可控制外部设备一次可控制外部设备一次传输一组字节传输一组字节 (如一个扇区如一个扇区) 特点：特点：由由DMA代替代替CPU，控制每个字符的传输控制每个字符的传输通过记数，将通过记数，将一批字符传输到指定的内存一批字符传输到指定的内存 (如缓冲区如缓冲区)后，再向后，再向CPU发中断发中断 185中断位中断位启

139、动位启动位控制寄存器控制寄存器数据寄存器数据寄存器传输计传输计数器数器地址寄存器地址寄存器DMA方式又是如何发展出来的呢？方式又是如何发展出来的呢？ I/O程序程序外部外部设备设备1DMA控制器控制器(见见P188) 中断处理中断处理程序程序等待等待 缓缓 冲冲 区区 CPU186 字符设备字符设备 通通 道道 CPU内存内存主机主机CPU4. 通道方式通道方式 磁磁 带带 机机 磁磁 盘盘外部设备外部设备187通道：通道：指一种专门用来控制指一种专门用来控制I/O的计算机的计算机特点：特点：与主机共享内存，受主机的控制与主机共享内存，受主机的控制 执行自己的通道指令执行自己的通道指令 一个通

140、道可同时控制多个外部设备一个通道可同时控制多个外部设备 (通过控制器通过控制器)，与与CPU并发执行并发执行 主要用于：主要用于：大、中、小型计算机大、中、小型计算机188二、二、I/ /O子系统的功能子系统的功能 I/O子系统的主要功能可分为三个方面子系统的主要功能可分为三个方面 解释用户的解释用户的I/ /O系统调用命令系统调用命令（由（由I/ /O 控制接口程序完成）控制接口程序完成） 设备驱动设备驱动（由设备处理进程完成）（由设备处理进程完成） 中断处理中断处理（由（由I/ /O中断处理程序完成）中断处理程序完成）I/O子系统中，控制设备子系统中，控制设备I/O工作的核心模块工作的核心

141、模块 通常称为通常称为设备驱动程序设备驱动程序它主要完成那些工作呢？它主要完成那些工作呢？189 1、I/ /O 控制接口程序控制接口程序 它负责完成它负责完成底层底层I/O的系统调用命令的系统调用命令 (1) 系统调用命令的形式：系统调用命令的形式： doio(逻辑设备名，操作方式，逻辑设备名，操作方式， 传输字节数，内存地址传输字节数，内存地址)调用者调用者: 由文件系统的由文件系统的读、写读、写函数、或用户程序调用函数、或用户程序调用 190(2) 完成的功能完成的功能 将逻辑设备转换成物理设备将逻辑设备转换成物理设备 进行合法性检查进行合法性检查 生成生成I/ /O请求块请求块 (UN

142、IX中为一个带有描述信息的中为一个带有描述信息的缓冲区首部缓冲区首部) 将将 I/ /O请求块插入设备的请求块插入设备的I/ /O请求队列请求队列 发消息给设备处理进程发消息给设备处理进程 (唤醒唤醒) 191 重复完成：重复完成： 取取I/ /O请求块请求块 启动启动I/ /O设备设备睡眠睡眠(等待等待I/ /O的完成，由的完成，由I/ /O中断处理程序中断处理程序唤醒唤醒) 传送数据到目的地传送数据到目的地 唤醒等待唤醒等待I/ /O的进程的进程 删除该删除该I/ /O请求块请求块 2设备处理进程设备处理进程 每类每类设备一个，执行该类设备的驱动程序设备一个，执行该类设备的驱动程序 平时睡

143、眠，被平时睡眠，被I/ /O控制接口程序控制接口程序唤醒唤醒后后处理完所有处理完所有 I/ /O请求块后，请求块后，再次睡眠再次睡眠 192 3I/ /O中断处理程序中断处理程序 对传输结果进行判别：对传输结果进行判别： 成功成功：唤醒唤醒设备处理进程后设备处理进程后 返回被中断的程序返回被中断的程序 出错、出错、且出错记数且出错记数m ： 出错记数加出错记数加1，重新启动设备进行传输，重新启动设备进行传输 出错记数出错记数m时：时：设置出错标志设置出错标志 唤醒唤醒设备处理进程，返回被中断的程序设备处理进程，返回被中断的程序 三、三、输入输入/ /输出的过程输出的过程（见见P218） UNI

144、X中的快设备驱动中的快设备驱动 193 文件系统是操作系统中，负责管理和存取文件文件系统是操作系统中，负责管理和存取文件信息的软件机构。信息的软件机构。从用户的角度看：从用户的角度看： 文件系统实现了文件系统实现了“按名存取按名存取”的各种功能的各种功能 从系统的角度看：从系统的角度看： 文件系统负责对辅存空间文件系统负责对辅存空间 及存放在其上的文件及存放在其上的文件 进行管理进行管理 9 . 1 文件系统的概念文件系统的概念 文件系统的组成文件系统的组成 一个文件系统应包括下列三部分的内容：一个文件系统应包括下列三部分的内容： (1) 对对文件进行管理的各种文件进行管理的各种数据结构数据结

145、构 (2) 对文件进行管理的各种对文件进行管理的各种程序程序 (3) 为用户提供的为用户提供的一组对文件的一组对文件的操作操作 文件系统应解决的问题文件系统应解决的问题 (1) 外存空间的管理外存空间的管理(分配、回收分配、回收) (2) 实现用户与文件的物理结构无关，即：实现用户与文件的物理结构无关，即： 用户：用户：按名存取按名存取文件文件(使用使用逻辑结构逻辑结构) 系统：实现系统：实现逻辑结构逻辑结构与与物理结构物理结构之间的映射之间的映射 (3) 文件的共享文件的共享 (4) 文件的安全性：文件的安全性：存取控制存取控制、保密保密、完整性完整性 (5) 对文件的操作命令对文件的操作命

146、令 (6) 在程序中使用的文件接口在程序中使用的文件接口 问题：问题：按名存取按名存取是如何实现的呢？是如何实现的呢？9. .5 文件目录文件目录2. 文件目录的主要内容文件目录的主要内容 (1) 文件名称文件名称 (2) 文件在外存中的文件在外存中的位置信息位置信息 连续文件、串联文件：连续文件、串联文件： 指出第一个物理块的外存地址指出第一个物理块的外存地址(直接地址直接地址) 索引文件：索引文件：指出索引表的地址指出索引表的地址(间接地址间接地址) 一一. 文件目录的概念文件目录的概念 1. 什么是文件目录什么是文件目录 文件目录是记录文件目录是记录文件名称文件名称、存放地址存放地址(实

147、现按名存取实现按名存取) 以及与文件有关的以及与文件有关的说明信息说明信息的一个数据结构的一个数据结构 (3) 存取控制信息存取控制信息 文件主文件主的存取权限；允许访问的的存取权限；允许访问的用户用户及及存取权限存取权限 (5) 文件的类型文件的类型 如如Unix中分为：普通文件、目录文件中分为：普通文件、目录文件 块设备文件、字符设备文件块设备文件、字符设备文件(6) 管理信息。如：文件建立的日期、时间；管理信息。如：文件建立的日期、时间；上一次存取时间；文件保留的时间等上一次存取时间；文件保留的时间等 (4) 文件逻辑结构的描述文件逻辑结构的描述 如：若为记录文件，说明记录是否定长、如：

148、若为记录文件，说明记录是否定长、 记录的长度、及记录的个数等记录的长度、及记录的个数等 四、树型四、树型文件目录结构文件目录结构 1. 什么是树型文件目录什么是树型文件目录 树型文件目录是一个多层目录结构树型文件目录是一个多层目录结构 每个目录项，既可以登记一个每个目录项，既可以登记一个文件文件 也可以登记另一个也可以登记另一个目录目录(称为称为子目录子目录)其中：其中： 除最顶层节点外除最顶层节点外 任何一个节点任何一个节点都都唯一地唯一地对应于一个上层节点对应于一个上层节点 (树的定义树的定义) 2. 树型文件目录的结构树型文件目录的结构 (P212 图图9.11) abcfe dabca

149、hjhjmrgaacid=13id=21id=14id=15id=16id=17 id=18 id=19id=20id=1id=2id=3id=4id=11id=12id=5id=8id=9id=10id=6 id=7根目录根目录子目录子目录a子目录b子目录c子目录子目录a子目录f子目录e子目录d 3. 文件路径名文件路径名 一个文件的路径名是由：一个文件的路径名是由： 根目录到该文件的通路上根目录到该文件的通路上 所有的所有的目录名目录名和该文件的和该文件的符号名符号名所组成所组成. 文件的唯一标识文件的唯一标识 Unix等一般系统：等一般系统：路径名路径名 Windows：盘符盘符路径名路

150、径名 为什么二者不同？为什么二者不同？ . 当前目录当前目录 又称又称值班目录值班目录，它是用户，它是用户 当前正在使用的文件，所在的一个目录当前正在使用的文件，所在的一个目录 用户对文件的所有访问，都是相对于自己的用户对文件的所有访问，都是相对于自己的 当前目录当前目录进行进行(类似于二级目录的类似于二级目录的用户目录用户目录) 标识文件时，路径名中：标识文件时，路径名中： 当前目录当前目录及以上的及以上的各级目录各级目录均可省略均可省略 称其为称其为相对路径名相对路径名 abcfe dabcahjhjmrgaacid=13id=21id=14id=15id=16id=17 id=18 id

151、=19id=20id=1id=2id=3id=4id=11id=12id=5id=8id=9id=10id=6 id=7根目录子目录a子目录b子目录c子目录a子目录f子目录e子目录子目录d当指定当指定id=10的子目录为当前目录时的子目录为当前目录时 id=20的文件，相对路径名为：的文件，相对路径名为：a 例：例： 9. .6 文件的共享与安全文件的共享与安全 首先要解决的问题：首先要解决的问题： 如何标识要共享的文件？如何标识要共享的文件？一、一、文件共享文件共享 指：一个指：一个文件文件、或、或目录目录 让事先规定的多个用户共同使用让事先规定的多个用户共同使用 一般的实现：一般的实现：

152、使用全路径名使用全路径名 问题问题1 1： (1) 全路径名难于记忆全路径名难于记忆能否象能否象自己的文件一样：自己的文件一样： 给共享的文件任意命名给共享的文件任意命名 并登记在自己的任意一个目录中呢？并登记在自己的任意一个目录中呢？ (2)当前目录的优点用不上。因为当前目录的优点用不上。因为 不能在不能在其他用户的目录其他用户的目录下建立下建立自己的当前目录自己的当前目录(3) 对文件访问路径上的对文件访问路径上的所有目录所有目录，必须，必须 具有具有读读的权限（与文件的保护原则相违背）的权限（与文件的保护原则相违背）解决办法：解决办法： 用用链接链接(也称为也称为连接连接)技术实现文件的

153、共享技术实现文件的共享 2、用文件目录中的、用文件目录中的地址地址指针实现连接指针实现连接 1、创建快捷方式、创建快捷方式 建立一个快捷图标建立一个快捷图标(类似类似文件夹文件夹)，在其中保存，在其中保存 被共享文件的被共享文件的路径名路径名(也称为也称为软连接软连接) 通过通过路径搜索路径搜索，找到保存的被共享文件，找到保存的被共享文件 存在的问题：存在的问题： 当被共享文件的路径名改变后，无法实现连接当被共享文件的路径名改变后，无法实现连接 思想：思想： 同一个文件，用同一个文件，用多个目录的表目多个目录的表目来描述来描述 故可通过不同的目录，访问同一个文件故可通过不同的目录，访问同一个文

154、件 对要共享的文件，用户可以：对要共享的文件，用户可以： 任意命名任意命名、并登记在、并登记在任意的目录中任意的目录中 问题问题2 2：同一文件登记在多个目录项中：同一文件登记在多个目录项中： 描述信息冗余，可能会产生描述信息冗余，可能会产生不一致不一致实现方法：实现方法： (1) 直接链接到文件直接链接到文件abcfe dabcahfjhkjmrgaacid=13id=21id=14id=15id=16id=17 id=18 id=19id=20id=1id=2id=3id=4id=11id=12id=5id=8id=9id=10id=6 id=7根目录子目录a子目录b子目录子目录c子目录a

155、子目录子目录f子目录子目录e子目录子目录d 假定某用户的当前目录为：假定某用户的当前目录为：b:d (id=10) 则可则可用文件用文件名名f，访问子目录，访问子目录c中的文件中的文件a (id=12)优点：优点：用户可将共享的文件看成是自己的文件用户可将共享的文件看成是自己的文件 (2) 在相应的在相应的目录表目目录表目之间进行链接之间进行链接文件目录的表目中，共享文件的指针：文件目录的表目中，共享文件的指针： 指向指向被共享文件所登记的被共享文件所登记的目录表目目录表目 而不是直接指向被共享的文件而不是直接指向被共享的文件这种方法也称为这种方法也称为连访连访被共享的文件称为被共享的文件称为

156、连访文件连访文件abcfe dabcahfjhkjmrgaacid=13id=21id=14id=15id=16id=17 id=18 id=19id=20id=1id=2id=3id=4id=11id=12id=5id=8id=9id=10id=6 id=7根目录子目录a子目录b子目录子目录c子目录a子目录f子目录子目录e子目录子目录d 问题问题3 3：系统对文件、及目录的处理方式不统一系统对文件、及目录的处理方式不统一 能否找到一种保持二者优点、克服不足的方法呢能否找到一种保持二者优点、克服不足的方法呢 ？ (3) UNIX中的中的索引节点索引节点及文件共享及文件共享 将将文件的描述信息，

157、从目录中分离出来文件的描述信息，从目录中分离出来共享中还要解决的问题：共享中还要解决的问题： 如何规定如何规定谁谁能共享、能共享、怎么怎么访问？访问？ 文件名文件名指针指针FA文件名文件名指针指针TB描述信息描述信息文件文件目录目录1目录目录I 节点节点二、二、文件的安全文件的安全 文件的安全涉及文件的文件的安全涉及文件的保护、保密和完整性保护、保密和完整性 1、什么是文件的保护、什么是文件的保护 文件的保护涉及二点：文件的保护涉及二点： (1) 文件不得被文件不得被未经未经文件主文件主(文件的创建者文件的创建者) 授权的任何用户访问授权的任何用户访问 (2) 对于被授权的用户对于被授权的用户

158、 也也只能对文件进行允许的操作只能对文件进行允许的操作概括：概括：只能由只能由指定的用户指定的用户、进行、进行允许的操作允许的操作 2. 如何进行保护如何进行保护 基本的方法是：基本的方法是： 对每个文件都规定一个存取权限对每个文件都规定一个存取权限 用户访问文件时，进行用户访问文件时，进行存取权限存取权限的验证：的验证： 符合者允许使用符合者允许使用 否则拒绝否则拒绝 .制定存取权限的方法制定存取权限的方法 根据文件保护的程度，可采用多种方式根据文件保护的程度，可采用多种方式 (1) 简单的保护简单的保护 实现实现让不让让不让访问访问，可采用多种方式：可采用多种方式： C i , j 表示：

159、表示：用户用户i 能否访问能否访问 文件文件j j 1：允许访问；：允许访问； 0：不允许访问：不允许访问 01 文件文件1 文件文件j 文件文件n用户用户1用户用户i用户用户m 用用口令口令来实现来实现 用访问用访问控制矩阵控制矩阵来实现来实现 问题：问题：访问控制矩阵访问控制矩阵是一个稀疏矩阵是一个稀疏矩阵 口令口令若太简单好破译，太难容易忘记若太简单好破译，太难容易忘记 都没有解决都没有解决如何访问如何访问的问题的问题 (2) 更完善的更完善的保护保护 实现：实现：让不让让不让访问、及如何访问访问、及如何访问 (a) 将用户分为将用户分为 文件文件主主 同组同组用户用户 指定的指定的用户

160、用户 其他用户其他用户 方法：方法：对用户进行分类对用户进行分类( (实现数据的压缩实现数据的压缩) ) (b) 将文件的操作分为将文件的操作分为 R: 可读可读 W: 可写可写 E: 可执行可执行 用户名用户名存取权限存取权限 文件主文件主RWE A 组组RE User1RE 其其 他他E (c) 建立用户对文件的建立用户对文件的存取权限，可采用二种方式存取权限，可采用二种方式 存取存取控制表控制表(每个每个文件一个，相当于文件一个，相当于矩阵的矩阵的列列)A: 可添加可添加D: 可删除可删除P: 可修改存取权限可修改存取权限 N: 不可访问不可访问(对特定用户对特定用户) 为什么不隐含为什

161、么不隐含文件主有全权？文件主有全权？ 如：如： 文件名：文件名： alpha 思考思考1: 若考虑存储量，保存、及若考虑存储量，保存、及 修改修改存取权限存取权限的方便性，哪一种结构更好呢？的方便性，哪一种结构更好呢？ 用户用户权限表权限表(每个用户每个用户一个，相当于一个，相当于矩阵的矩阵的行行) 文件名文件名存取权限存取权限 sportRW testE tempR如：如： 用户名：用户名：User6 思考思考2: 存取存取控制表放在何处最好呢？控制表放在何处最好呢？ 其中其中1表示允许；表示允许； 0表示不允许表示不允许* * * * * * * * * 文件主文件主 同同 组组 其他其他

162、R W E R W E R W E例例1：在目录项的：在目录项的存取权限存取权限中，用字符串表示：中，用字符串表示：O: RWEP; G: RE; U1: E; A: N 思考思考3: 目录中的目录中的存取权限存取权限应如何表示应如何表示？例例2：UNIX中，存取权限在索引节点的中，存取权限在索引节点的文件类型文件类型中中 用用9位二进制位表示为：位二进制位表示为：如：如： (751)8 = (111 101 001)2 表示什么权限？表示什么权限？思考思考4: 删除一个文件，需要有什么删除一个文件，需要有什么权限？权限？思考思考5: 存取权限能实现文件的保密吗？存取权限能实现文件的保密吗？4

163、、存取权限的暂时转移、存取权限的暂时转移 (见补充P5、P6) 5、 文件加密文件加密 思考：思考：仅加密仅加密能保证文件的安全吗？能保证文件的安全吗？ 思考：思考：文件被破坏了怎么办？文件被破坏了怎么办？ 9 . 2 文件的逻辑结构与存取方法文件的逻辑结构与存取方法 对文件的最常用操作是读、写文件。涉及到：对文件的最常用操作是读、写文件。涉及到： 按名存取按名存取文件、文件的文件、文件的读写方式读写方式、逻辑结构到物理结构的逻辑结构到物理结构的映射映射等等想象中的文件想象中的文件物物 理理文文 件件按名按名存取存取 读写读写文件目录文件目录映射映射问题：问题：逻辑文件、物理文件的结构是如何组

164、织的呢？逻辑文件、物理文件的结构是如何组织的呢？ 读写读写 一、一、文件的组织文件的组织 对文件的组织形式，可以从二个不同的角度对文件的组织形式，可以从二个不同的角度来进行研究。来进行研究。 1、用户使用的角度用户使用的角度研究研究用户思维中的抽象文件用户思维中的抽象文件 要求：要求：为用户提供一种结构清晰为用户提供一种结构清晰 使用简便的逻辑文件形式使用简便的逻辑文件形式 用户：用户：按按逻辑文件的形式逻辑文件的形式 存储和处理文件中的信息存储和处理文件中的信息 2、系统实现的角度系统实现的角度研究研究外存储器中的实际文件外存储器中的实际文件要求：要求：选择一种工作性能良好选择一种工作性能良

165、好 设备利用率高的物理文件形式设备利用率高的物理文件形式 系统：系统：按文件的物理结构，实现：按文件的物理结构，实现： 信息在外存的信息在外存的存储存储 内存与外部设备之间的内存与外部设备之间的信息传输信息传输 、记录式文件、记录式文件 记录式文件是一种有结构的文件记录式文件是一种有结构的文件 这种文件在逻辑上，被看成是一组：这种文件在逻辑上，被看成是一组： 连续的、顺序的、连续的、顺序的、逻辑记录逻辑记录的集合的集合 二、二、文件的逻辑结构文件的逻辑结构称为称为逻辑文件逻辑文件，指的是用户思维中的文件，指的是用户思维中的文件根据有无内部结构，可分为二种根据有无内部结构，可分为二种 逻辑记录：

166、逻辑记录：是信息在逻辑含义上的划分是信息在逻辑含义上的划分 是用户对文件进行存取的是用户对文件进行存取的基本单位基本单位 、流式文件、流式文件 流式文件是一种无结构的文件流式文件是一种无结构的文件在逻辑上被看成是：在逻辑上被看成是： 一组有序的、一组有序的、字符字符的集合的集合 流式文件按字符进行存取流式文件按字符进行存取 问题：问题： 二种逻辑结构之间，有没有共同点呢？二种逻辑结构之间，有没有共同点呢？ 3、流式文件的、流式文件的逻辑块逻辑块 逻辑块逻辑块可看成流式文件中的可看成流式文件中的逻辑记录逻辑记录 而且在记录式文件中，而且在记录式文件中，逻辑记录逻辑记录也要转换为也要转换为逻辑块逻

167、辑块 因此二类文件，最终都统一到因此二类文件，最终都统一到逻辑块逻辑块 * * * * * * * * * * * * * * * * * * 物理块物理块逻辑块逻辑块L0逻辑块逻辑块L1逻辑块逻辑块L2逻辑块逻辑块Ln可将逻辑文件中：可将逻辑文件中： 与物理块相对应的部分与物理块相对应的部分称为称为逻辑块逻辑块 三、三、文件的存取方法文件的存取方法 指用户对指用户对逻辑文件逻辑文件的内容的内容 进行读、写时的进行读、写时的定位方式定位方式 实现：实现：文件打开后文件打开后 由一个由一个读写指针读写指针， 指出当前的读写位置指出当前的读写位置 每读、写一个信息单位后，每读、写一个信息单位后，指

168、针自动后移指针自动后移 1. 顺序存取顺序存取按逻辑文件中信息单位的排列次序，按逻辑文件中信息单位的排列次序，向后依向后依次存取次存取。因此，用户。因此，用户无须给出具体的读写位置无须给出具体的读写位置记录式文件记录式文件逻辑偏移量逻辑偏移量 L01L流式式文件流式式文件2、随机存取、随机存取 可按任意次序：可按任意次序： 存取存取指定位置指定位置的记录、或字符的记录、或字符 因此，用户要给出存取的因此，用户要给出存取的逻辑位置逻辑位置。如：。如： 记录号、或字符的位置记录号、或字符的位置(逻辑偏移量逻辑偏移量 ) 问题：问题： 如何将如何将逻辑偏移量逻辑偏移量 映射为外存的映射为外存的物理位

169、置物理位置呢？呢？ 物理块号物理块号文件的物理结构不同，地址映射的方式也不同文件的物理结构不同，地址映射的方式也不同 为了实现地址映射为了实现地址映射文件通常可按那几种物理结构进行组织呢？文件通常可按那几种物理结构进行组织呢？ 3、地址映射、地址映射逻辑偏移量逻辑偏移量 块块 长长逻辑块号逻辑块号 块内位移块内位移9 . 3 文件的物理结构文件的物理结构 物理记录：物理记录：指外存储介质上，一组连续信息指外存储介质上，一组连续信息 所组成的区域所组成的区域(如一个扇区如一个扇区) ，也称为，也称为物理块物理块 指文件在外存储器中的组织形式，用来描述：指文件在外存储器中的组织形式，用来描述：文件

170、在外存上的文件在外存上的位置位置、链接和编目的方法、链接和编目的方法 物理文件的存储单位是物理文件的存储单位是物理记录物理记录 一个文件通常由一个文件通常由多个物理块多个物理块组成，根据物理块组成，根据物理块之间连接方式的不同，常用的文件物理结构有：之间连接方式的不同，常用的文件物理结构有： 连续文件、串联文件、索引文件连续文件、串联文件、索引文件 一一. 连续文件结构连续文件结构 1. 什么是连续文件什么是连续文件 连续文件是是指：连续文件是是指： 文件的信息存放在磁盘上文件的信息存放在磁盘上 一组一组连续的物理块连续的物理块中中 2. 连续文件的结构连续文件的结构 文件文件A 3 100

171、r0 r1 r2 磁盘块号磁盘块号100101102文件目录文件目录文件文件A目录项目录项3. 连续文件的特点连续文件的特点 既可既可顺序存取、又可顺序存取、又可随机存取随机存取 存取速度较快存取速度较快 (1) 流式文件流式文件 物理地址文件首址物理地址文件首址逻辑偏移量逻辑偏移量 文件生成后不易改变文件生成后不易改变 因而不利于文件内容的因而不利于文件内容的增加增加、删减、删减 磁盘会产生磁盘会产生碎片碎片 . 地址映射地址映射(特别是特别是随机存取随机存取)(2) 记录文件记录文件逻辑偏移量逻辑偏移量 逻辑记录长度逻辑记录长度记录号记录号物理地址文件首址物理地址文件首址逻辑偏移量逻辑偏移

172、量 连续文件的不足连续文件的不足？二二. 串联文件结构串联文件结构 1. 什么是串联文件什么是串联文件 串联文件是指：串联文件是指： 文件的信息可存放在磁盘上文件的信息可存放在磁盘上 一组一组不连续的物理块不连续的物理块中中 每个物理块每个物理块 按逻辑的顺序，用指针进行链接按逻辑的顺序，用指针进行链接 从而可实现物理文件的从而可实现物理文件的非连续非连续分配分配 2. 串联文件的结构串联文件的结构文件文件A 100 r1 57 r2 r0 150磁盘块号磁盘块号 100磁盘块号磁盘块号 150磁盘块号磁盘块号 57文件目录文件目录文件文件A目录项目录项 问题：问题： 可进行可进行随机存取吗？

173、随机存取吗？ 为什么？为什么？ 3、 串联文件的优点串联文件的优点 易于对文件的内容进行增加、删减易于对文件的内容进行增加、删减 不不会产生碎片，能较好地利用辅存空间会产生碎片，能较好地利用辅存空间 顺序顺序存取时速度较快存取时速度较快 简单的解决方法：简单的解决方法： 4、文件映照、文件映照(DOS中的中的FAT) F13 将磁盘上每个物理块的块号和将磁盘上每个物理块的块号和链接指针链接指针，放在一数据，放在一数据结构中，以实现结构中，以实现每个文件每个文件的链接的链接64文件目录文件目录文件名文件名 位置位置 块号块号 0 1 2 3 4 5 6 访问一个文件时，只需通过目录：访问一个文件

174、时，只需通过目录： 顺序搜索顺序搜索内存中内存中的该数据结构的该数据结构(如数组如数组) 就可得到该文件的每一个物理块的地址就可得到该文件的每一个物理块的地址 评价：评价： 尽管搜索时间缩短，但与数据量成尽管搜索时间缩短，但与数据量成正比正比 还不是真正意义上的随机存取还不是真正意义上的随机存取 随机存取的关键：随机存取的关键：不通过顺序的搜索不通过顺序的搜索 即：即：用内存的用内存的顺序搜索顺序搜索，代替在外存中的，代替在外存中的 I/O操作操作(以得到链接指针以得到链接指针)三三. 索引文件结构索引文件结构 1. 什么是索引文件什么是索引文件 系统为每个文件，建立一个系统为每个文件，建立一

175、个 逻辑块号逻辑块号(逻辑记录逻辑记录)与与物理块号物理块号的对照表的对照表 (类似于分页存储管理的类似于分页存储管理的页表页表) 将这张表称为该文件的将这张表称为该文件的索引表索引表 用这种方法构造的文件称为用这种方法构造的文件称为索引文件索引文件 2. 索引文件的结构索引文件的结构 r0 r1 逻辑块号逻辑块号 物理块号物理块号 0 23 1 19 2 26 3 29 r2 r3磁盘块磁盘块 23磁盘块磁盘块 19磁盘块磁盘块 26磁盘块磁盘块 29文件索引表文件索引表 3. 对索引文件的存取对索引文件的存取 先先查文件的索引表，由逻辑块号得到物理块号查文件的索引表，由逻辑块号得到物理块号

176、 (文件打开后，索引表可放到一个内存文件打开后，索引表可放到一个内存结构结构(如数组如数组)中中) 再对再对磁盘上的物理块进行存取磁盘上的物理块进行存取 文件目录文件目录 思考：思考： (1)文件未打开前，索引表放在何处？文件未打开前，索引表放在何处？4. 索引文件的优点索引文件的优点 易于文件的增、删易于文件的增、删 可随机存取任意记录可随机存取任意记录 不会产生不会产生磁盘碎片磁盘碎片 解决办法：解决办法： 多个索引块可连续、串联、或多个索引块可连续、串联、或再索引再索引 于是有了于是有了一级索引表、二级索引表、一级索引表、二级索引表、. (2)若索引表超过一个磁盘物理块怎么办？若索引表超

177、过一个磁盘物理块怎么办？ 逻辑块号逻辑块号 物理块号物理块号 0 23 1 19 2 26 文件块文件块目目 录录N级级索引表索引表N1级级索引表索引表 1级级索引表索引表5、多级索引的、多级索引的一般结构一般结构 文件的多级索引是如何构建的呢？文件的多级索引是如何构建的呢？ 例：设一文件的长度为例：设一文件的长度为 65576 块块 物理块的大小为物理块的大小为 512B 每个索引项占每个索引项占 2B 构建出该文件的索引结构构建出该文件的索引结构 (1) 求每个物理块中容许的最多求每个物理块中容许的最多索引项数索引项数 512/2=256 (2) 求一级索引的块数求一级索引的块数 6557

178、6256=256 . 40 257 因为超过因为超过 256 块，还需再为其建索引块，还需再为其建索引 (3) 求前一级求前一级(二级二级)索引的块数索引的块数 257 256=1 . 1 2 由于该级索引的块数由于该级索引的块数 256 故可由故可由目录所指的索引块目录所指的索引块进行链接进行链接 结果：结果： 为为三级三级索引结构索引结构 而且每级索引的而且每级索引的 最后一个索引块最后一个索引块中都可能有中都可能有空项空项(由由余数余数定定) 目录目录 0 1 2 255 01 254255 0 1 2 254255 0 1 1255 0 1 1255 0 39 40255三级索引三级索

179、引二级索引二级索引一级索引一级索引文件块文件块问题：问题：每个文件的每个文件的 索引索引级数级数不统一，不统一， 造成地址映射困难造成地址映射困难 对文件长度的相关统计表明：对文件长度的相关统计表明： (1) 80的文件：的文件： 文件长度文件长度 10个物理块个物理块(小型文件小型文件)希望达到的效果：希望达到的效果： 尽量减少读磁盘，查索引的次数尽量减少读磁盘，查索引的次数 (2) 20的文件：的文件： 10个物理块个物理块 文件长度文件长度 2562个物理块个物理块 (3) 1的文件：的文件： 文件长度文件长度 2562个物理块个物理块(巨型文件巨型文件)6、UNIX的文件索引结构的文件

180、索引结构 用用索引节点索引节点中的一个数组中的一个数组i_addri_addr( (13个表目个表目)实现索引实现索引 （文件打开后，该数组在内存中）文件打开后，该数组在内存中）i_addr0i_addr9i_addr0i_addr9：称为：称为直级索引直级索引 分别指向文件的前分别指向文件的前1010个文件块个文件块( (不用不用I/OI/O读索引读索引) )i_addr10i_addr10：称为称为一级间接索引一级间接索引 指向一个指向一个一级一级间接间接索引表索引表(1次次I/O读索引读索引)i_addr11i_addr11：称为称为二级间接索引二级间接索引 指向一个指向一个二级二级间接

181、间接索引表索引表(2次次I/O读索引读索引)i_addr12i_addr12：称为称为三级间接索引三级间接索引 指向一个指向一个三级三级间接间接索引表索引表(3次次I/O读索引读索引) 三级三级索引索引 强调：强调：对一个任意的对一个任意的实际文件实际文件 最后一级索引中的每级索引，都可能有空索引项最后一级索引中的每级索引，都可能有空索引项 思考：思考：能表示文件的最大长度能表示文件的最大长度 ？ 访问一个逻辑地址，读写的磁盘块数访问一个逻辑地址，读写的磁盘块数 ？9 . 4 文件存储空间的管理文件存储空间的管理 一、一、Unix的磁盘结构的磁盘结构0块：块：引导块，存放系统初启的引导程序引导

182、块，存放系统初启的引导程序1块：块：特别块特别块(或称资源管理块或称资源管理块) 存放该磁盘的、文件资源管理的信息存放该磁盘的、文件资源管理的信息2k块：块： I节点区，存放该盘上所有文件的节点区，存放该盘上所有文件的 I 节点节点K+1n 块：块：文件文件数据区数据区, 存放存放普通文件普通文件和和目录文件目录文件二、空闲磁盘块的管理二、空闲磁盘块的管理 根据文件物理结构的不同根据文件物理结构的不同 外存中空闲块的组织，可采用不同的形式：外存中空闲块的组织，可采用不同的形式：序号序号第一块空闲块号第一块空闲块号 空闲块数空闲块数 1 20 10 2 100 34适用于适用于连续文件结构连续文

183、件结构 1. 空闲文件目录空闲文件目录 将每一组将每一组连续的空闲块连续的空闲块，都作为一个，都作为一个空闲文件空闲文件 登记在一个特殊的目录中登记在一个特殊的目录中(称其为称其为空闲文件目录空闲文件目录) 3. 位示图位示图 每一个物理块都对应一个二进制位每一个物理块都对应一个二进制位 0表示空闲；表示空闲； 1表示占用表示占用110000010100100010100010100101111001000101010100 2. 空闲块链空闲块链4、Unix 中空闲磁盘块的中空闲磁盘块的成组成组管理管理 每每100块一组块一组(第一组只有第一组只有99块，有一块，有一虚块，表示结束虚块，表示

184、结束) 每组的索引放在后一组第每组的索引放在后一组第0块中。如磁盘有块中。如磁盘有376个空闲块个空闲块770176100019910001991000 19999第一组第一组第二组第二组第三组第三组第四组第四组分配、回收分配、回收 内内 存存特别块特别块特殊：特殊：分配时只有分配时只有1 1块块( (或或虚块虚块) )；回收时已有回收时已有100块块 0 块块1 块块99块块三、对磁盘访问的调度三、对磁盘访问的调度 对数据的访问，涉及到磁头定位的：对数据的访问，涉及到磁头定位的： 柱面柱面 (磁道磁道)：由磁头的直线运动得到，由磁头的直线运动得到，耗时较长耗时较长 扇区：扇区：通过磁盘的旋转

185、得到，通过磁盘的旋转得到，耗时较短耗时较短 盘面：盘面：由不同的磁头的得到，由不同的磁头的得到，不耗时不耗时 故要根据故要根据耗时的长短耗时的长短，依次决定访问的次序，依次决定访问的次序 当对磁盘有多个访问时，对磁盘访问的当对磁盘有多个访问时，对磁盘访问的调度算法调度算法为：为： 首先：首先：按磁头的移动方向，对访问数据按按磁头的移动方向，对访问数据按磁道磁道依次排序依次排序 其次：其次：对访问同一磁道的多个扇区对访问同一磁道的多个扇区 再按磁盘的旋转方向，对访问的再按磁盘的旋转方向，对访问的扇区扇区依次排序依次排序 实例：实例：基于扫描的磁盘调度算法基于扫描的磁盘调度算法 SCAN (广泛用

186、于大、中、小型机，及服务器上广泛用于大、中、小型机，及服务器上) 思想：思想：在磁盘的一次移动中完成所有在磁盘的一次移动中完成所有可能的可能的访问访问 每次访问磁头每次访问磁头移动方向移动方向上上最靠近最靠近的磁道的磁道 如：当前的磁头在如：当前的磁头在140磁道，由外向里移动时磁道，由外向里移动时 应按如下的序列进行访问应按如下的序列进行访问 18 38 55 59 90 150 160 184 SCAN 算法也称为算法也称为 “电梯算法电梯算法” 问题：问题：在密集的访问中，磁头可能会滞留在几个磁道上在密集的访问中，磁头可能会滞留在几个磁道上 改进：改进：分分2批切换，当前已有的为一批，以

187、后到的另一批批切换，当前已有的为一批，以后到的另一批 9 . 8 文件的操作文件的操作 一、最一、最常用的文件操作命令常用的文件操作命令 create创建一个新文件创建一个新文件 delete删除一个文件删除一个文件(不一定真删除不一定真删除 ？) rename 更改文件的名称更改文件的名称 open打开文件打开文件 close关闭文件关闭文件 write写数据写数据到一个文件到一个文件(或设备或设备) read从一个文件从一个文件(或设备或设备)读数据读数据思考：思考：对同一个文件进行对同一个文件进行多次多次读、写操作时读、写操作时 是否每次都要是否每次都要访问外存访问外存目录中的描述信息？

188、目录中的描述信息？ 二、二、打开文件和关闭文件打开文件和关闭文件 1. 打开文件打开文件(open) 把该文件把该文件与操作有关的数据与操作有关的数据 (主要在目录中主要在目录中) 复制到主存复制到主存中的约定区域中的约定区域(称为称为文件控制块文件控制块) 从而建立用户和该文件的联系从而建立用户和该文件的联系 即：以后对该文件进行读、写操作时即：以后对该文件进行读、写操作时 直接从直接从文件控制块文件控制块得到有关的信息得到有关的信息 而不用再访问外存中该文件的目录而不用再访问外存中该文件的目录 2. 关闭文件关闭文件(close) 所谓关闭文件，就是当用户所谓关闭文件，就是当用户 宣布这个

189、文件以后不再使用后：宣布这个文件以后不再使用后： 将其在主存中的文件控制块删除将其在主存中的文件控制块删除 因而也就因而也就切断了用户同该文件的联系切断了用户同该文件的联系3、UNIX中中文件的打开及关闭文件的打开及关闭 如执行如下的程序：如执行如下的程序： fd1 fd1= open(f1= open(f1，r)r) number= read(number= read(fd1fd1，buffer1buffer1，size1)size1) fd2fd2= open(f1= open(f1，r) r) close(close(fd1fd1) ) close( close(fd2fd2) ) (1

190、)(1)打开文件及结构打开文件及结构活动活动 i 节点节点表表 打开文件打开文件表表(系统打开文件表系统打开文件表) 文件描述符文件描述符表表 (用户打开文件表用户打开文件表) 415i-cont: 1索引索引数组数组f-cont: 1 读写方式读写方式: r读写位置读写位置: 0f-cont: 1 读写方式读写方式: r读写位置读写位置: 02标准输入标准输入标准输出标准输出标准出错标准出错1*2 3(2)(2)关闭文件关闭文件活动活动 i 节点表节点表 打开文件表打开文件表文件描述符表文件描述符表 415i-cont: 1索引表索引表f-cont: 1 读写方式读写方式: r读写位置读写位

191、置: 0f-cont: 1 读写方式读写方式: w读写位置读写位置: 02标准输入标准输入标准输出标准输出标准出错标准出错1*2 31 000三、文件系统的三、文件系统的读、写读、写(一般先要读一般先要读)操作操作 要点：要点：(1)(1)分块读写；分块读写；(2)(2)文件系统的读写分层实现：文件系统的读写分层实现： 高层的高层的ReadRead、WriteWrite；缓冲区管理缓冲区管理、底层磁盘的、底层磁盘的读写读写 * * * * * * * * * * 内内 存存缓冲区缓冲区逻辑文件逻辑文件磁磁 盘盘文件系统的文件系统的read、write底层底层(磁盘磁盘)的的read、write