操作系统2016-1-复习-张尧学-最新-New

1、齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习操作系统操作系统 齐鲁工业大学齐鲁工业大学 信息学院信息学院 刘嵩刘嵩齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习操作系统复习操作系统复习考试题型考试题型 单选题、填空题单选题、填空题 、简答题、算法题、简答题、算法题、计算题计算题 考试范围考试范围 第第1 1、2 2、3 3、4 4、5 5、8 8、9 9章章 重点章节重点章节 第第3 3、4 4、5 5、8 8、9 9章章复习内容复习内容 各

2、章主要知识点各章主要知识点齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习第1章 绪论 知识重点知识重点齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习1. 1 操作系统的概念操作系统的概念 操作系统是管理和控制计算机系统中软硬操作系统是管理和控制计算机系统中软硬件资源，合理组织计算机工作流程，方便用户件资源，合理组织计算机工作流程，方便用户操作使用机器的程序的集合。操作使用机器的程序的集合。 基本特征基本特征: （1）执行的并发性）执行的并发性

3、（2）资源的共享性）资源的共享性 （3）操作的异步性）操作的异步性 齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习1.3 操作系统的基本类型操作系统的基本类型(1). 批处理系统批处理系统主要特点：主要特点： 脱机操作；脱机操作； 成批处理；成批处理； 多道程序运行；多道程序运行； 无交互性。无交互性。(2). 分时系统分时系统所谓分时技术，就是把处理机的运行时间分成很短的所谓分时技术，就是把处理机的运行时间分成很短的 时间片时间片，从而轮流，从而轮流把处理机分配给各联机作业使用。把处理机分配给各联机作业使用。主要特点

4、：主要特点： 交互性；交互性； 同时性；同时性； 独立性；独立性； 及时性。及时性。(3). 实时系统实时系统主要特点：主要特点： 实时时钟管理实时时钟管理 ； 连续人机对话连续人机对话 ； 过载防护，安全可靠；过载防护，安全可靠； 资源利用率低资源利用率低 齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习1.3 1.3 续续: :多道程序运行及特点多道程序运行及特点多道程序设计：多道程序设计：允许多作业同时进入内存轮流交允许多作业同时进入内存轮流交替占用替占用CPU运行的技术。运行的技术。 特点：特点：（1）多道性）多

5、道性 （2）宏观上并行）宏观上并行 （3）微观上串行）微观上串行齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习1.4 操作系统的功能操作系统的功能(0).用户与计算机硬件之间用户与计算机硬件之间的接口的接口(1). 处理机管理处理机管理(2). 存储管理存储管理(3). 设备管理设备管理(4). 文件系统文件系统管理管理(5). 进程进程管理管理齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习寄存器：寄存器：1.用户可编程寄存器用户可编程寄存器2

6、.控制与状态寄存器控制与状态寄存器：主要：主要包括以下包括以下5种：种：程序程序计数器计数器PC、指令寄存器指令寄存器IR、程序状态字程序状态字PSW、中断现场保护寄存器、过程调用用堆栈。中断现场保护寄存器、过程调用用堆栈。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习第第2章章 操作系统用户界面操作系统用户界面 知识重点知识重点齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习2.2 一般用户的输入输出界面一般用户的输入输出界面1. 作业的组成作

7、业的组成作业由作业由程序、数据程序、数据和和作业说明书作业说明书三部份组成，但三部份组成，但至少包含一个程序。至少包含一个程序。其中：其中： 程序：程序：表明完成任务及操作表明完成任务及操作 数据：数据：操作的对象；操作的对象； 作业说明书：作业说明书：体现用户的控制的意图。体现用户的控制的意图。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习2.3 命令控制界面命令控制界面计算机与用户之间的接口及用途：计算机与用户之间的接口及用途：操作系统为用户提供两个操作系统为用户提供两个接口界面，一个是为用户提供的各种命令接口界面

8、。另一接口界面，一个是为用户提供的各种命令接口界面。另一个接口是系统调用个接口是系统调用 。 (1) 操作命令接口：操作命令接口：OS为用户提供的各种操作命令，供用户为用户提供的各种操作命令，供用户直接组织作业的工作流程和控制作业的运行；直接组织作业的工作流程和控制作业的运行； (2) 系统调用接口：系统调用接口：OS为用户提供的一组系统功能调用为用户提供的一组系统功能调用(广广义指令义指令)，供用户编程时调用系统的功能，请求操作系统，供用户编程时调用系统的功能，请求操作系统提供的服务。提供的服务。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作

9、作 系系 统统 复复 习习知识重点知识重点第第3章章 进程管理进程管理齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.1. 进程的概念进程的概念1.1.程序的顺序执行：程序的顺序执行：在处理机上的执行是严格按序的。在处理机上的执行是严格按序的。 顺序性顺序性 封闭性封闭性 可再现性可再现性 齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习2程序的并发执行程序的并发执行 进程在处理机上的执行时间是交叉重叠的，是进程在处理机上的执行时间是交叉重叠的

10、，是提高提高CPUCPU利用率而采取的一种同步操作技术。利用率而采取的一种同步操作技术。特点：特点： 独立性独立性 随机性随机性 资源共享性资源共享性齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3. 进程的定义及引入目的进程的定义及引入目的定义定义 一个具有独立的功能的程序关于某个数据集一个具有独立的功能的程序关于某个数据集在处理机上的一次执行过程及分配资源的基本在处理机上的一次执行过程及分配资源的基本单位。单位。引入目的引入目的 为了控制和协调并发程序对软硬件资源的共为了控制和协调并发程序对软硬件资源的共享和竞争。

11、享和竞争。 为了描述程序动态执行的过程和有个分配资为了描述程序动态执行的过程和有个分配资源的基本单位。源的基本单位。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习4. 进程的基本特征进程的基本特征 动态性动态性 并发性并发性 独立性独立性 异步性异步性齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.2 进程的描述进程的描述进程的描述包括三部分：进程的描述包括三部分： 程序程序 数据结构集数据结构集 进程控制块（进程控制块（PCBPCB）齐鲁工

12、业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.2 进程的描述进程的描述3.2.2 3.2.2 进程上下文进程上下文 进程上下文是一个抽象的概念，它包含了每个进进程上下文是一个抽象的概念，它包含了每个进程执行过的、执行时的以及待执行的指令和数据，程执行过的、执行时的以及待执行的指令和数据，在指令寄存器、堆栈、状态字寄存器等中的内容。在指令寄存器、堆栈、状态字寄存器等中的内容。我们把已执行过的进程指令和数据在相关寄存我们把已执行过的进程指令和数据在相关寄存器与堆栈中的内容称为器与堆栈中的内容称为上文上文，正在执行的指令和，正

13、在执行的指令和数据在相关寄存器与堆栈中的内容称为数据在相关寄存器与堆栈中的内容称为正文正文，待，待执行指令和数据在相关寄存器与堆栈中的内容称执行指令和数据在相关寄存器与堆栈中的内容称为为下文下文。3.2.3 进程上下文的切换进程上下文的切换齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.2 进程的描述进程的描述3.2.3 进程上下文的切换进程上下文的切换齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.2 进程的描述进程的描述3.2.4 3.

14、2.4 进程空间与大小进程空间与大小 任一进程，都有一个自己的地址空间，把该空间称任一进程，都有一个自己的地址空间，把该空间称为进程空间或虚空间。进程空间的大小只与处理为进程空间或虚空间。进程空间的大小只与处理机的位数有关。例如，一机的位数有关。例如，一个个16位长处理机的进程位长处理机的进程空间大小为空间大小为216，而，而32位长处理机的进程空间大小位长处理机的进程空间大小为为232。程序的执行都在进程空间内进行。程序的执行都在进程空间内进行。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.3 进程的状态及转换进

15、程的状态及转换 执行状态执行状态 一个进程正占用一个进程正占用CPUCPU执行。执行。 等待状态等待状态 进程因等待某事件不能使用进程因等待某事件不能使用CPU.CPU. 就绪状态就绪状态 进程已具备运行进程已具备运行条件尚未占用条件尚未占用CPU。执行执行就绪就绪等待等待调调度度时间时间片到片到等待某个事件等待某个事件发生而睡眠发生而睡眠因等待事件发因等待事件发生而唤醒生而唤醒初始初始终止终止齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.4 进进 程程 控控 制制 在操作系统中，通常把进程控制用程序段做成原在操作

16、系统中，通常把进程控制用程序段做成原语。用于进程控制的原语有：语。用于进程控制的原语有： 创建原语、撤消原语、阻塞原语、唤醒原语等。创建原语、撤消原语、阻塞原语、唤醒原语等。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.5 进程互斥进程互斥临界区：临界区：不允许多个并发进程交叉执行的不允许多个并发进程交叉执行的程序段程序段。对公共变量（或存储区）进行审查或修改的程序段，对公共变量（或存储区）进行审查或修改的程序段，均为相对于该公共变量的临界区。均为相对于该公共变量的临界区。临界资源：临界资源：一次仅允许一个进程使用

17、的资源。一次仅允许一个进程使用的资源。问题：问题：若系统中有若系统中有五五个并发进程涉及某个相同的变量个并发进程涉及某个相同的变量A，则，则变量变量A的相关临界区是由的相关临界区是由几个几个临界区构成临界区构成？齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.5 进程互斥进程互斥间接制约：间接制约：并发进程共享公有资源而引起的执并发进程共享公有资源而引起的执行速度上的制约。行速度上的制约。( ( 进程互斥进程互斥 ) )直接制约：直接制约：一组在异步环境下的并发进程，各一组在异步环境下的并发进程，各自的执行结果互为对

18、方的执行条件，从而限自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间制各进程的执行速度的过程称为并发进程间的直接制约。的直接制约。( ( 进程同步进程同步 ) )齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习 进程的同步与互斥进程的同步与互斥齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习信号量与信号量与PVPV原语原语信号量（信号量（SemaphoreSemaphore）表示系统中资源实体数目或资源使用表示系统中资源

19、实体数目或资源使用情况的整型量情况的整型量, ,其值只能由其值只能由PVPV原语操作改变。原语操作改变。n n个进程共享个进程共享m m个资源，信号量变化范围个资源，信号量变化范围 P(S) P(S) ：代表申请使用资源的操作：代表申请使用资源的操作 S SS-1S-1； 若若S S0,0,则将调用则将调用P(S)P(S)的进程置为等待态的进程置为等待态, ,调用调用P(S)P(S)原语的原语的进程继续运行；进程继续运行； 若若S0 ,S0 ,则则, ,调用调用P(S)P(S)原语的原语的进程继续运行。进程继续运行。 V(S) V(S) ：代表释放归还资源的操作：代表释放归还资源的操作 S S

20、S+1S+1； 若若S0,S0,则唤醒一个等待则唤醒一个等待S S的进程后，的进程后， , ,调用调用P(S)P(S)原语的原语的进进程继续运行；程继续运行； 若若S S0,0,则则, ,调用调用P(S)P(S)原语的原语的进程继续运行。进程继续运行。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习信号量与信号量与PVPV原语原语问题：问题： 若信号量若信号量S的初值定义为的初值定义为10，则在，则在S上调用了上调用了14次次P操作和操作和16次次V操作后操作后S的值应该为的值应该为多少多少?齐鲁工业大学齐鲁工业大学-2

21、016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习并发执行的描述并发执行的描述Begin , s: semaphore; /* 定义信号量定义信号量 */; s=XXX; /* 赋初值赋初值 */ COBEGIN Process P1; /*并发进程并发进程 */ process p2; . COENDEnd 主程序主程序齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习 P P、V V原语实现进程互斥原语实现进程互斥Process PProcess P BeginBeginP(

22、s);P(s);临界区；临界区；V(s)V(s)；EndEndProcess QProcess Q BeginBeginP(s);P(s);临界区；临界区；V(s)V(s)；EndEnd设公用信号量设公用信号量S，初值为，初值为1（或（或k）齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.6 进程同步进程同步只与制约进程及被制约进程有关而不是与整组并发进程有关。因此，称该信号量为私用信号量互斥时使用的信号量为公用信号量可以使用，原语操作实现进程间的同步。利用，原语实现进程同步的方法与利用wait和signal过程时相

23、同，也是分为三步。首先为各并发进程设置私用信号量，然后为私用信号量赋初值，最后利用，原语和私用信号量规定各进程的执行顺序。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.6 进程同步进程同步分别设私用信号量分别设私用信号量s1，初值为，初值为n； s2,初值为初值为0Process PProcess P BeginBeginP(s1);P(s1);P P推进；推进；V(s2)V(s2)；EndEndProcess QProcess Q BeginBeginP(s2);P(s2);Q Q推进；推进；V(s1)V(s1)

24、；EndEnd齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.6.4 生产者生产者-消费者问题消费者问题设公用信号量mutex保证生产者进程和消费者进程之间的互斥，设信号量avail为生产者进程的私用信号量，信号量full为消费者进程的私用信号量。信号量avail表示有界缓冲区中的空单元数，初值为n；信号量full表示有界缓冲区中非空单元数，初值为0。信号量mutex表示可用有界缓冲区的个数，初值为 1。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复

25、复 习习3.6.4 生产者生产者-消费者问题消费者问题问题： 假设将前面的部分条件改为： 生产者和生产者互斥； 消费者和消费者互斥，如何重写deposit和remove过程？齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.7 进程通信进程通信3.7.1 进程的通信方式在单机系统中，进程间通信可分为4种形式：(1) 主从式；(2) 会话式；(3) 消息或邮箱机制；(4) 共享存储区方式。进程通信的实例管道（“管道”是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件）齐鲁工业大学齐鲁工业大学-2016-2

26、017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.8 死锁问题死锁问题产生死锁的必要条件：产生死锁的必要条件：（1）互斥条件）互斥条件（2）请求和保持条件）请求和保持条件（3）不可抢占条件）不可抢占条件（4） 环路条件（循环等待条件）环路条件（循环等待条件）解决死锁的方法一般可分为解决死锁的方法一般可分为: 预防、避免、检测与恢复等三种。预防、避免、检测与恢复等三种。问题：问题：当每类资源只有一个个体时当每类资源只有一个个体时，有环不一定死锁有环不一定死锁这种说法正确吗？这种说法正确吗？p1p2R1R2齐鲁工业大学齐鲁工业大学-2016-2017-1返回首

27、页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习3.9 线程的概念线程的概念 一个进程内的基本调度单位称为线程或称为轻权进一个进程内的基本调度单位称为线程或称为轻权进程（程（Light weight process），这个调度单位既可以），这个调度单位既可以由操作系统内核控制，也可以由用户程序控制。由操作系统内核控制，也可以由用户程序控制。 一个进程可拥有若干个线程一个进程可拥有若干个线程。 线程与资源分配无关，它属于某一个进程，并与进线程与资源分配无关，它属于某一个进程，并与进程内的其他线程一起共享进程的资源。同一进程内程内的其他线程一起共享进程的资源。同一进程内的不同线

28、程共享同一地址空间。的不同线程共享同一地址空间。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习 知识重点知识重点第第4章章 处理机调度处理机调度齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习4.1 4.1 分级调度分级调度4.1.1 作业的状态及其转换作业的状态及其转换齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习4.1 4.1 分级调度分级调度4.1.2 调度的层次调

29、度的层次一般来说，处理机调度可以分为一般来说，处理机调度可以分为4级级：（1）作业调度：）作业调度：又称宏观调度，或高级调度。又称宏观调度，或高级调度。（2） 交换调度交换调度：又称又称中级调度中级调度。（3） 进程调度进程调度：又称微观调度或低级调度。又称微观调度或低级调度。（4） 线程调度线程调度。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习4.2 4.2 作业调度作业调度作业调度主要是完成作业调度主要是完成作业从后备状态到执行状态的转变；作业从后备状态到执行状态的转变；以及从执行状态到完成状态的转变。以及从执行

30、状态到完成状态的转变。4.2.1 作业调度功能作业调度功能记录系统中各作业的状况记录系统中各作业的状况。(2) 从后备队列中挑选出一部分作业投入执行从后备队列中挑选出一部分作业投入执行(3) 为被选中作业做好执行前的准备工作为被选中作业做好执行前的准备工作(4) 在作业执行结束时做善后处理工作在作业执行结束时做善后处理工作齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习4.2 4.2 作业调度作业调度1. 周转时间周转时间：作业作业i的周转时间的周转时间Ti为为 Ti=Tei-Tsi 完成时间 - 提交时间其中其中Tei

31、为作业为作业i的完成时间，的完成时间，Tsi为作业的提交时间。为作业的提交时间。对于被测定作业流所含有的对于被测定作业流所含有的n（n=1）个作业来说，其）个作业来说，其平均周转时间平均周转时间为：为：2. 带权周转时间带权周转时间为了更进一步反映调度性能，使用带权周转时间的概念。为了更进一步反映调度性能，使用带权周转时间的概念。Wi=Ti/Tr 作业周转时间与作业执行时间的比：对于被测定作业流所含有的几个作业来说，其对于被测定作业流所含有的几个作业来说，其平均带权周转时间平均带权周转时间为：为：nii = 11T =Tnnii=11W =Wn齐鲁工业大学齐鲁工业大学-2016-2017-1返

32、回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习4.3 4.3 进程调度进程调度进程调度的功能进程调度的功能(1) 记录系统中所有进程的执行情况记录系统中所有进程的执行情况(2) 选择占有处理机的进程的策略选择占有处理机的进程的策略(3) 进行进程上下文切换进行进程上下文切换问题：问题：进程调度的对象和任务分别是进程调度的对象和任务分别是什么？什么？进程，从就绪队列中按一定的调度策略选择一个进程进程，从就绪队列中按一定的调度策略选择一个进程占用占用CPU。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复

33、 习习4.4 调度算法调度算法 (1). 先来先服务算法（先来先服务算法（FCFS）将用户作业和就绪进程将用户作业和就绪进程按提交顺序按提交顺序或变为就绪状态的或变为就绪状态的先后，排成队列，并按照先来先服务先后，排成队列，并按照先来先服务(驻留时间最长驻留时间最长)的方式进行调度处理。的方式进行调度处理。 (2).轮转法（轮转法（Round RobinRound Robin） (3). 多级反馈轮转法多级反馈轮转法(4). 优先级法优先级法问题：问题：轮转法中，当进程因时间片用完而让出处理机轮转法中，当进程因时间片用完而让出处理机时，该进程应转变为时，该进程应转变为什么什么状态状态？ 图图4

34、.4 轮转法调度轮转法调度齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习4.4 调度算法调度算法(5). 最短作业优先法（最短作业优先法（SJF） 最短作业优先法（最短作业优先法（SJF）是选择执行时间最短的作业投入执）是选择执行时间最短的作业投入执行。该调度算法，可使系统在同一时间内处理的作业个数最行。该调度算法，可使系统在同一时间内处理的作业个数最多，从而吞吐量也就大于其他调度方式。但是，有可能使得多，从而吞吐量也就大于其他调度方式。但是，有可能使得那些长作业永远得不到调度执行的机会。那些长作业永远得不到调度执行的

35、机会。(6). 最高响应比优先法（最高响应比优先法（HRN） 是介于是介于FCFS方式和方式和SJF 方式的一种折中算法。该调度策略同方式的一种折中算法。该调度策略同时考虑每个作业的等待时间和执行时间，从中选出响应比最时考虑每个作业的等待时间和执行时间，从中选出响应比最高的作业投入执行。高的作业投入执行。 响应比响应比R定义如下：定义如下： R=(W+T)/T=1+W/T问题：问题：一种既有利于短小作业又兼顾到长作业的作业调度算法一种既有利于短小作业又兼顾到长作业的作业调度算法是是什么方法什么方法？齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作

36、作 系系 统统 复复 习习综合举例综合举例：先来先服务调度算法：先来先服务调度算法：作业作业 提交时间提交时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转带权周转时间时间18.002.00 28.500.5039.000.1049.500.20平均周转平均周转时间时间平均带权平均带权周转时间周转时间8.0010.002.00110.0010.502.00410.5010.601.601610.6010.801.306.5=6.9=27.5T=1.725W=6.875齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系

37、系 统统 复复 习习短作业优先调度算法：短作业优先调度算法：作业作业 提交时间提交时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转带权周转时间时间1(1)8.002.002(4)8.500.503(2)9.000.104(3)9.500.20平均周转平均周转时间时间平均带权平均带权周转时间周转时间8.0010.002.00110.0010.101.101110.1010.300.80410.3010.802.304.6=6.20=20.6T=1.55W=5.15齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系

38、统统 复复 习习最高相应比优先调度算法：最高相应比优先调度算法：作业作业 提交时间提交时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转带权周转时间时间1(1)8.002.002(3)8.500.503(2)9.000.104(4)9.500.20平均周转平均周转时间时间平均带权平均带权周转时间周转时间8.0010.02.001在在P1完后，计算响应比：完后，计算响应比：rp2=1+(10.00-8.50) / 0.50=1+3；rp3=1+(10.00-9.00) / 0.10=1+10；rp4=1+(10.00-9.50) / 0.20=1+2.5；10.0010

39、.101.1011在在P3完后，计算响应比：完后，计算响应比：rp2=1+(10.10-8.50) / 0.50=1+3.2；rp4=1+(10.10-9.50) / 0.20=1+3；10.1010.602.104.210.6010.801.306.5=6.50=22.7T=1.625W=5.675齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习知识重点知识重点第第5章章 存储管理存储管理齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习5.1 存

40、储管理的功能存储管理的功能 (1) (1) 虚拟存储器的实现虚拟存储器的实现 (2) (2) 完成地址重定位完成地址重定位 (3) (3) 内外存数据传输的控制内外存数据传输的控制 （4）内存的分配与回收）内存的分配与回收（5) 5) 内存信息的共享和保护内存信息的共享和保护 齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习1. 虚拟存储器虚拟存储器 用户程序中的代码、数据等逻辑地址组成的虚拟用户程序中的代码、数据等逻辑地址组成的虚拟空间。空间。实质是把外存当成内存使用的一种技术。实质是把外存当成内存使用的一种技术。特点

41、：特点： 虚拟存储器容量由机器虚拟存储器容量由机器地址结构地址结构和和寻址方式寻址方式以以及及外存容量外存容量确定；确定； 虚拟存储器由软件、硬件共同支撑实现：虚拟存储器由软件、硬件共同支撑实现： 软件负责内外信息交换；软件负责内外信息交换； 硬件实现虚实地址转换。硬件实现虚实地址转换。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习2. 地址地址重定位重定位 将程序中的逻辑地址转换映射成内存中物将程序中的逻辑地址转换映射成内存中物理的过程。定位方式有：理的过程。定位方式有：静态静态重定位重定位 程序执行前，由软件一次性

42、完成。程序执行前，由软件一次性完成。(2) (2) 动态重定位动态重定位 程序执行中，由专门硬件地址变换机构实现。程序执行中，由专门硬件地址变换机构实现。动态重定位提供了实现动态重定位提供了实现 虚拟存储器虚拟存储器的基础，可以部的基础，可以部分地、动态地分配内存。分地、动态地分配内存。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习5.2 分区存储管理分区存储管理(1) 固定分区分配固定分区分配 预先把主存储器空间预先把主存储器空间分成若干个连续区域。分成若干个连续区域。(2) 动态分区分配动态分区分配 根据作业的需求

43、和内存根据作业的需求和内存情况动态分配区域。情况动态分配区域。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习5.2 分区存储管理分区存储管理(2) 动态分区分配动态分区分配 根据作业的需求和内存根据作业的需求和内存情况动态分配区域。情况动态分配区域。可用分区表可用分区表或或可可用分区自由链表用分区自由链表 请求表请求表 碎片问题碎片问题齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习5.2 分区存储管理分区存储管理(2) 动态分区分配动态分区分配

44、 可用分区表可用分区表或或可用分区可用分区自由链表自由链表 请求表请求表齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习5.2 分区存储管理分区存储管理动态分区时的分配方法三种动态分区时的分配方法三种。最先适应法最先适应法(first fit algorithm)可用表或自由链的空闲区可用表或自由链的空闲区按起始地址递增按起始地址递增的次序排列的次序排列最佳适应法最佳适应法(best fit algorithm)可用表或自由链的空闲区可用表或自由链的空闲区从小到大的次序从小到大的次序排列排列。最坏适应法最坏适应法(wor

45、st fit algoriathm)可用表或自由链的空闲区按其可用表或自由链的空闲区按其从大到小的从大到小的次序排列次序排列。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习5.3 覆盖与交换技术覆盖与交换技术齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习5.4 5.4 页页 式式 管管 理理将进程逻辑地址空间分成若干大小相同将进程逻辑地址空间分成若干大小相同页，同时将内存空间分成若干块，块大页，同时将内存空间分成若干块，块大小与页相同；存储分配

46、时，以块为单位小与页相同；存储分配时，以块为单位分配，但块与块之间不一定连续；通过分配，但块与块之间不一定连续；通过页表和硬件地址转换机构实现地址转换。页表和硬件地址转换机构实现地址转换。 进程执行时，只把当前需要的页装入进程执行时，只把当前需要的页装入内存（实页），其余页暂留外存（虚内存（实页），其余页暂留外存（虚页），当进程访问虚页时，产生缺页中页），当进程访问虚页时，产生缺页中断，再由系统动态装入。断，再由系统动态装入。 动态页式管理实现了虚拟存储器。动态页式管理实现了虚拟存储器。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统

47、统 复复 习习5.4 5.4 页页 式式 管管 理理u 将进程逻辑地址空间分成若干大小相同页，将进程逻辑地址空间分成若干大小相同页，同时将内存空间分成若干块，块大小与页相同时将内存空间分成若干块，块大小与页相同；存储分配时，以块为单位分配，但块与同；存储分配时，以块为单位分配，但块与块之间不一定连续；通过页表和硬件地址转块之间不一定连续；通过页表和硬件地址转换机构实现地址转换。换机构实现地址转换。u 进程执行时，只把当前需要的页装入内存进程执行时，只把当前需要的页装入内存（实页），其余页暂留外存（虚页），当进（实页），其余页暂留外存（虚页），当进程访问虚页时，产生缺页中断，再由系统动程访问虚页

48、时，产生缺页中断，再由系统动态装入。态装入。u 动态页式管理实现了虚拟存储器。动态页式管理实现了虚拟存储器。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习5.4 5.4 页页 式式 管管 理理分页管理示意图：分页管理示意图：齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习5.4 5.4 页页 式式 管管 理理u进程的虚地址由页号进程的虚地址由页号 p与页内地址与页内地址 w所组成。所组成。通常，如果逻辑地址空间为通常，如果逻辑地址空间为2m，且页

49、的大小为，且页的大小为2n单元（字单元（字节），那么逻辑地址的高节），那么逻辑地址的高m-n位表示页号，而低位表示页号，而低n位表位表示页内偏移。示页内偏移。如：一个地址长度为如：一个地址长度为20位的计算机系统，如果每页的大小位的计算机系统，如果每页的大小为为1KB(210) ，那么可以有，那么可以有210个页。个页。其地址结构如图其地址结构如图 图图5.14 页的划分页的划分页内地址页内地址W页号页号P19 10 9 0齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习(1) 页表页表由页号与页面号组成。如图由页号与页

50、面号组成。如图5.15所示。所示。页表在内存中占有一块固定的存储空间页表在内存中占有一块固定的存储空间(页号连续，页页号连续，页面号离散面号离散)。页表的大小由进程或作业的长度决定。页表的大小由进程或作业的长度决定。每个进程拥有一张页表。每个进程拥有一张页表。图图5.15 基本页表示例基本页表示例页号页号( (虚拟空间虚拟空间) )页面号页面号(物理空间物理空间)081325齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习(2) 请求表请求表用来确定虚拟空间的各页在内存中的实际对应位置。系用来确定虚拟空间的各页在内存中的

51、实际对应位置。系统必须知道每个作业或进程的页表起始地址和长度，以统必须知道每个作业或进程的页表起始地址和长度，以便进行内存分配和地址变换。便进行内存分配和地址变换。另外，请求表中还包括每个作业或进程所要求的页面数。另外，请求表中还包括每个作业或进程所要求的页面数。请求表请求表整个系统一张，如图整个系统一张，如图5.16所示。所示。图图5.16 请求表示例请求表示例齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习(3)存储页面表存储页面表：整个系统一张，存储页面表指出整个系统一张，存储页面表指出内存内存中已被分配出去中已被

52、分配出去, 以及未分配页面数。以及未分配页面数。存储页面表有两种方法存储页面表有两种方法：1.位示图法位示图法：是在内存中划分是在内存中划分 一块固定区域，每个单一块固定区域，每个单元的每个比特（一位二进制数位）代表一个页面。元的每个比特（一位二进制数位）代表一个页面。如果该页面已被分配，则该位置如果该页面已被分配，则该位置1，否则置，否则置0。如图如图5.17所示。所示。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习 图图5.17 位示图位示图 提高效率：可在表前用若干字节表示空页面的总数位示图要占据一部分内存容量，

53、例如，一个划分为位示图要占据一部分内存容量，例如，一个划分为1 024个页面的内存，如果内存单元长个页面的内存，如果内存单元长20比特，则位示比特，则位示图要占据图要占据1024/20=52个内存单元。个内存单元。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习2.空闲页面链的方法；空闲页面链的方法；在空闲页面链中，队头结点（首页面）的第一个成员在空闲页面链中，队头结点（首页面）的第一个成员和第二个成员分别放入空闲页面和第二个成员分别放入空闲页面总数总数与指向下一个空与指向下一个空闲页面的闲页面的指针指针。其他页面的一个

54、成员中则分别存放指向下一个页面的其他页面的一个成员中则分别存放指向下一个页面的指针。指针。空闲页面链的方法由于使用了空闲页面本身的成员存空闲页面链的方法由于使用了空闲页面本身的成员存放指针，因此不占据额外的内存空间。放指针，因此不占据额外的内存空间。 .null结点数null齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习图图5.20 地址变换地址变换首先，需要有一个装置首先，需要有一个装置页表始址页表始址和和页表页表长度长度用的用的控制寄存器控制寄存器。系统把所调度执。系统把所调度执行的进程页表始址和长度从请求表中取行

55、的进程页表始址和长度从请求表中取出置入控制寄存器中。出置入控制寄存器中。然后，由控制寄存器的页表始址，可以找然后，由控制寄存器的页表始址，可以找到页表所在位置。并由虚地址到页表所在位置。并由虚地址100可知，可知，指令指令LOAD 1，2500在第在第0页的第页的第100单元单元之中。由于第之中。由于第0页与第页与第2个页面相对应，因个页面相对应，因此，该指令在内存中的地址为此，该指令在内存中的地址为2048+100=2148。当当CPU执行到第执行到第2148单元的指令时，单元的指令时，CPU要从有效地址要从有效地址2500中取数据放入中取数据放入1号寄存器中。为了找出号寄存器中。为了找出2

56、500对应的实际对应的实际物理地址，地址变换机构首先将物理地址，地址变换机构首先将2500转转换为页号与页内相对地址组成的地址形换为页号与页内相对地址组成的地址形式。即式。即p=2，w=452。由页表，可知第由页表，可知第2页所对应的页面号等于页所对应的页面号等于8。8 * 1024+452，得到待访问的物理内，得到待访问的物理内存地址存地址8644。其变换过程由图。其变换过程由图5.20所示。所示。页号页号页面号页面号021328设每个页面长度为设每个页面长度为1K，指令，指令LOAD 1，2500的虚地址为的虚地址为100。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上

57、一页上一页下一页下一页操操 作作 系系 统统 复复 习习5.4.3 动态页式管理动态页式管理分为分为请求页式管理请求页式管理和和预调入页式管理预调入页式管理。这两种方式是在作业或进程开始执行之前，都不把这两种方式是在作业或进程开始执行之前，都不把作业或进程的程序段和数据段一次性地全部装入内作业或进程的程序段和数据段一次性地全部装入内存，而只装入反复执行和调用的工作区部分。其他存，而只装入反复执行和调用的工作区部分。其他部分则在执行过程中动态装入。部分则在执行过程中动态装入。请求页式管理与预调入页式管理的主要区别在它们请求页式管理与预调入页式管理的主要区别在它们的调入方式上。的调入方式上。1.请

58、求页式管理请求页式管理的调入方式是，当需要执行某条指令的调入方式是，当需要执行某条指令和数据不在内存时，从而发生和数据不在内存时，从而发生缺页中断缺页中断，系统将外，系统将外存中相应的页调入内存。存中相应的页调入内存。齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习例例：若在一分页存储管理系统中，若在一分页存储管理系统中， 某作业的页表某作业的页表如下图所示。己知页面大小为如下图所示。己知页面大小为l024字节。试将逻辑地址字节。试将逻辑地址1011，2148，3000，4000，5012转化为相应的物理地址。转化为相应

59、的物理地址。步骤：步骤：1.将逻辑地址转换为页号和页内偏移地址；将逻辑地址转换为页号和页内偏移地址；2. 根据页表找到块号，然后根据公式，求得物理地址。根据页表找到块号，然后根据公式，求得物理地址。页号页号页面号页面号(块号块号)02132136齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习解解:设页号为设页号为P,页内偏移为页内偏移为W,逻辑地址为逻辑地址为A,页面大小为页面大小为L,则则:P = int(A / L) 取整（逻辑地址/页面大小）=页号W =A mod L 取余（逻辑地址/页面大小）=页内偏移地址*对

60、于逻辑地址对于逻辑地址10l1P=int(1011/l024)=0W=1011 mod 1024=1011查页表第查页表第0页在第页在第2块块,物理地址为物理地址为2*1024+1011=3059.*对于逻辑地址对于逻辑地址2148P=int(2l48/1024)=2 w=2148 mod 1024 =100查页表第查页表第2页在第页在第l块块,所以物理地址为所以物理地址为1124。页号页号页面号页面号02132136齐鲁工业大学齐鲁工业大学-2016-2017-1返回首页返回首页上一页上一页下一页下一页操操 作作 系系 统统 复复 习习*对于逻辑地址对于逻辑地址3000P=int(3000/