操作系统原理 Operating System Principles

Presentation on theme: "操作系统原理 Operating System Principles"— Presentation transcript:

1 操作系统原理 Operating System Principles
四川大学计算机学院 段 磊 2014 Spring

2 第6章 存储器管理 计算机的存储系统主要包括内存储器和外存储器。 外存储器保存的信息必须进入内存储器后才能被处理器运行。
第6章 存储器管理 计算机的存储系统主要包括内存储器和外存储器。 外存储器保存的信息必须进入内存储器后才能被处理器运行。 存储器管理是操作系统的主要功能之一。 内存管理分为连续管理方式和离散管理方式。

3 知识点分布 实践教学 难点 高级知识 进程 同步 信号量 分页分段 文件系统 I/O 磁盘管理 虚存 页面分配 页面置换 2019/2/23
中级知识 基础知识 进程 同步 信号量 分页分段 文件系统 I/O 磁盘管理 虚存 页面分配 页面置换 实践教学 2019/2/23 《计算机操作系统》- 第6章

4 讲在前面－存储管理目的 操作系统的“方便”性 操作系统的“合理”性 操作系统的“有效”性 便于用户装入程序，无须了解底层细节
可实现动态的存储空间伸缩，适应不同程序的需要 操作系统的“合理”性 合理分配内存空间，保证多道程序的顺利运行 合理保护内存空间，防止各种可能的破坏泄漏 操作系统的“有效”性 有效保持内存空间的可用性，防止对资源的浪费 有效实现“小空间大容量”，提高计算机的适应性 有效配合CPU的调度过程，实现系统运行的稳定 2019/2/23 《计算机操作系统》- 第6章

5 使得用户和用户程序不涉及内存物理的细节。 为用户程序完成程序的装入。 提高内存的利用率，弥补用户对内存容量的需求与内存实际容量之间的差距。
讲在前面－存储管理目的 使得用户和用户程序不涉及内存物理的细节。 为用户程序完成程序的装入。 提高内存的利用率，弥补用户对内存容量的需求与内存实际容量之间的差距。 解决内存速度与CPU速度不匹配的问题。 实现内存共享。 2019/2/23 《计算机操作系统》- 第6章

6 讲在前面－存储管理的功能 内存的管理、分配与回收 地址重定位（地址映射） 共享与保护 内存的扩充 空间的使用情况记录—位图、分配表、分区表
空间的分配与回收—定长与不定长、静态与动态 地址重定位（地址映射） 物理地址与逻辑地址的差别 实模式与保护模式 共享与保护 内存共享：进程与线程、中间件应用 内存保护：如何防止地址越界或操作越权？ 内存的扩充 虚拟存储：如何使用小内存空间来运行大的程序？ 2019/2/23 《计算机操作系统》- 第6章

7 讲在前面－地址空间 程序的名空间 用户编程所用的地址称为逻辑地址(或程序地址，或虚地址)。
由逻辑地址组成的空间称为逻辑地址空间(或程序地址空间)。 内存的每个存储单元都有一个编号，这种编号称为内存地址(或称为物理地址，绝对地址)。 内存地址的集合称为内存空间(或物理地址空间)。 2019/2/23 《计算机操作系统》- 第6章

8 讲在前面－地址空间 地址映射 物理地址空间 源程序 编译 连接 逻辑地址空间
Load A 200 3456 。 物理地址空间 Load A data1 data1 3456 源程序 编译 连接 逻辑地址空间 源程序经过汇编或编译后，形成目标程序，每个目标程序都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据——单元号取代。 这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。 在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。 2019/2/23 《计算机操作系统》- 第6章

9 讲在前面－地址空间 源程序 逻辑地址空间 物理地址空间 编译 连接 地址映射
Load A data1 data1 3456 Load A 200 3456 Load A 200 3456 。 BA=1000 把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址、绝对地址、实地址），存储单元占8位，称作字节（byte）。 物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。 100 编译 连接 地址映射 1200 200 2019/2/23 《计算机操作系统》- 第6章

10 讲在前面－存储管理的方案 分区存储管理 段式存储管理 页式存储管理 段页式存储管理 交换和覆盖技术
是一种连续存储管理方案，但需要一次性全部装入内存。 是一种不连续存储管理方案，段和段之间可以不连续，但需要一次性全部装入内存。 是一种不连续存储管理方案，也需要一次性全部装入内存。 是一种不连续存储方案，如果采用纯分页和分段思想，需要一次性全部装入内存；如果采用虚拟存储思想，则不需要一次性全部装入内存。 是存储扩充的两种技术，其中交换技术的优点是编写程序时不需要特殊的控制，也不会影响程序的结构。 2019/2/23 《计算机操作系统》- 第6章

11 本章目录 6.1 存储器管理概述 6.2 连续存储空间管理 6.3 分页式存储管理 6.4 分段式存储管理 存储器的层次 程序准备执行
6.1 存储器管理概述 存储器的层次 程序准备执行 覆盖技术 紧凑技术 对换技术 6.2 连续存储空间管理 6.3 分页式存储管理 6.4 分段式存储管理 2019/2/23 《计算机操作系统》- 第6章

12 6.1.1 存储器的层次 存储空间的分类与性质 2019/2/23 《计算机操作系统》- 第6章

13 计算机系统存储层次示意 解决主存访问速度 vs CPU指令执行速度的矛盾 减少访存次数，提高程序执行速度
减少访问磁盘的次数,并提供对主存空间的扩充 2019/2/23 《计算机操作系统》- 第6章

14 6.1.2 程序的准备执行 相关知识回顾 程序的执行过程 进程创建 高级调度（作业调度） 编译：源代码形成（多个）目标模块
链接：链接相关库函数，形成装入模块 装入：装入内存 运行 2019/2/23 《计算机操作系统》- 第6章

15 程序的准备执行 2019/2/23 《计算机操作系统》- 第6章

16 程序的准备执行--链接 静态链接 装入时链接 运行时动态链接 对相对地址的修改 变换外部调用符号 便于修改和更新 便于实现对目标模块的共享
形成一个完整的装入模块，即可执行文件，运行时直接装入内存。 静态链接 对相对地址的修改 变换外部调用符号 装入时链接 便于修改和更新 便于实现对目标模块的共享 运行时动态链接 统称“动态链接”，被链接的共享代码称为动态链接库DLL(Dynamic Link Library)或共享库(shared library)。 边装入，边链接，即在装入过程中发生调用事件，由装入程序找到对应模块，装入内存。 执行过程中发生调用事件，找到对应模块装入内存并链接到调用模块上。 2019/2/23 《计算机操作系统》- 第6章

17 程序的准备执行--静态链接 (a)目标模块 (b)装入模块 模块A CALL B； RETURN JSR L; L-1 L 模块B
CALL C； 模块C L-1 M-1 N-1 (a)目标模块 JSR L; JSR L+M; L L+M-1 L+M L+M+N-1 (b)装入模块 2019/2/23 《计算机操作系统》- 第6章

18 程序的准备执行--动态链接 动态链接 缺点 优点 共享：多个进程可以共用一个DLL，比较节省内存，从而可以减少文件的交换。
增加了程序执行时的链接开销。 程序由多个文件组成，因此增加了管理复杂度。 部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作的DLL装入内存。 便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数(输入和输出)不变，则修改函数及其DLL时，无需对可执行文件重新编译或链接。 便于适应运行环境：调用不同的DLL，就可以适应多种使用环境并提供不同的功能。 2019/2/23 《计算机操作系统》- 第6章

19 程序的准备执行--装入 绝对装入方式 静态重定位装入方式 动态重定位装入方式 逻辑地址与实际内存地址一致 适用于单道程序环境 物理地址空间
Load A 200 3456 。 物理地址空间 逻辑地址空间 2019/2/23 《计算机操作系统》- 第6章

20 程序的准备执行--装入 绝对装入方式 静态重定位装入方式 动态重定位装入方式 地址映射/地址重定位
把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址的地址映射，或称为地址重定位。 静态地址映射 动态地址映射 2019/2/23 《计算机操作系统》- 第6章

21 程序的准备执行--装入 静态地址映射（静态重定位） 程序被装入内存时，由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换。
假定程序装入内存的首地址为BR，程序地址为VR，内存地址为MR，则地址映射按下式进行：MR=BR+VR 。 例如，程序装入内存的首地址为1000，则装配程序就按MR=1000+VR对程序中所有地址部分进行修改，修改后指令Load A，200就变为Load A，1200 优点：不需要硬件的支持。 缺点：程序必须占用连续的内存空间， 一旦程序装入后不能移动。 2019/2/23 《计算机操作系统》- 第6章

22 . 程序的准备执行--装入 动态地址映射（动态重定位） +
动态地址重定位是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。一般来说这种转换是由专门的硬件机构来完成的。 最简单的硬件机构是重定位寄存器。 在地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。 3456 . LOAD A 200 100 200 300 1100 1200 1300 VR + 1000 BR 2019/2/23 《计算机操作系统》- 第6章

23 程序的准备执行--装入 动态地址映射（动态重定位）
动态地址重定位是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。一般来说这种转换是由专门的硬件机构来完成的。 最简单的硬件机构是重定位寄存器。 在地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。 2019/2/23 《计算机操作系统》- 第6章

24 程序的准备执行--装入 动态地址映射（动态重定位）过程描述： 程序装入内存后，它所占用的内存区的首地址 由系统送入基地址寄存器BR中。
在程序执行的过程中，若要访问内存，将访问 的逻辑地址送入VR中。 地址转换机构把VR和BR中的内容相加，并将 结果送入MR中，作为实际访问的地址。 2019/2/23 《计算机操作系统》- 第6章

25 相对地址 重定位寄存器 load 1,2500 365 10000 load 1,2500 365 2500 10000 100 10100 12500 2500 + 15000 5000 作业J 处理机一侧 存储器一侧 2019/2/23 《计算机操作系统》- 第6章

26 程序的准备执行-装入 动态地址映射（动态重定位）优点：
程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。 一个程序不一定要求占用一个连续的内存空间。 可以部分地装入程序运行。 便于多个进程共享同一个程序的代码。 2019/2/23 《计算机操作系统》- 第6章

27 程序的准备执行-装入 动态地址映射（动态重定位）缺点： 需要硬件的支持。 实现存储管理的软件算法较为复杂。 2019/2/23
《计算机操作系统》- 第6章

28 当内存空间有限时，某些大的用户程序不能一次全部装入内存时，系统需要采取覆盖技术解决这一问题。
覆盖技术 当内存空间有限时，某些大的用户程序不能一次全部装入内存时，系统需要采取覆盖技术解决这一问题。 将大的用户程序划分为一个个相对独立的程序单位 将程序执行时不需要同时装入内存的程序单位组成覆盖段。 覆盖段的长度不能超过已有内存空间大小，每个覆盖段分先后顺序进入到所分配的内存空间，后进入内存空间的段将先进入内存空间的段覆盖。 2019/2/23 《计算机操作系统》- 第6章

29 采用了覆盖的程序执行比没有采用覆盖的程序执行慢
覆盖技术 采用了覆盖的程序执行比没有采用覆盖的程序执行慢 采用覆盖程序执行过程中增加了读覆盖段的过程（输入操作），需要花费相当多的时间。 覆盖技术要求程序员具有完整的程序指令、代码和数据结构方面的知识。 覆盖仅限于微型计算机和物理内存有限而又不支持更先进技术的系统 2019/2/23 《计算机操作系统》- 第6章

30 6.1.4 紧凑技术 紧凑技术通过改变进程在内存中的位置，移动存储器中某些已分配分区中的信息，使分散在内存中的“碎片”能够汇集成一片，再分配给进程使用，达到充分利用内存的目的。 提高内存的利用率 2019/2/23 《计算机操作系统》- 第6章

31 紧凑技术 操作系统 用户程序1 用户程序3 用户程序6 用户程序9 操作系统 用户程序1 用户程序3 用户程序6 用户程序9 80kb
2019/2/23 《计算机操作系统》- 第6章

32 紧凑技术 紧凑技术的缺点： 增加了系统的开销 影响进程正常运行 需要重新定义内存地址 移动已分配的内存区域会花费处理器大量的时间。
当系统进行紧凑时，必须停止所有进程的执行。 外设与内存交换数据的进程，不可随便移动 实时操作系统，会影响实时任务的完成。 需要重新定义内存地址 在紧凑之后，作业在内存中的地址发生了变化，需要重新定义内存地址。 2019/2/23 《计算机操作系统》- 第6章

33 2019/2/23 《计算机操作系统》- 第6章

34 对换技术是为了提高系统的性能和多道度而采取的进程在内存和外存之间的换出与换入。
6.1.5 对换技术 当内存空间紧张时，将某些暂时不运行的进程从内存移到外存，并将内存空间分配给其他进程或新创建的进程；当内存空间富余时再给被移出到外存的进程重新分配内存，让进程进入内存，这样的方式称为对换技术。 对换技术是为了提高系统的性能和多道度而采取的进程在内存和外存之间的换出与换入。 2019/2/23 《计算机操作系统》- 第6章

35 对换技术 对换的引入 所有可运行的进程必须小于内存空间 当进程处于阻塞或就绪时交换到磁盘 进程在运行过程中将多次进出内存 进程A 操作系统
未用内存区 进程A 操作系统 未用内存区 进程B 进程A 操作系统 未用内存区 进程B 进程C 未用内存区 操作系统 进程B 进程C 未用内存区 操作系统 进程B 进程C 进程D 进程D 操作系统 未用内存区 进程C 2019/2/23 《计算机操作系统》- 第6章

36 问题 存储器系统包括哪些基本层次？ 层次之间的关系是怎样的？ 解释逻辑地址和物理地址； 为什么要实现地址变换？ 什么是紧凑技术？
该技术有何缺点？ 覆盖技术和对换技术有何不同？ 2019/2/23 《计算机操作系统》- 第6章

37 本章目录 6.1 存储器管理概述 6.2 连续存储空间管理 6.3 分页式存储管理 6.4 分段式存储管理 单一连续分配 固定分区分配
6.1 存储器管理概述 6.2 连续存储空间管理 单一连续分配 固定分区分配 可变分区分配 6.3 分页式存储管理 6.4 分段式存储管理 2019/2/23 《计算机操作系统》- 第6章

38 引起内存分配和回收的原因 进程的开始的结束。 进程运行的过程中，它所占用的内存也可能发生变化，如栈的变化。
进程映像在内存和外存之间传递。由于内存有限，系统中不可能容纳所有进程，有些进程的映像可以存放在外存，当要运行这些进程时，必须把它们调入内存。 系统为了充分利用内存空间，有时可能对内存空间进行调整。 2019/2/23 《计算机操作系统》- 第6章

39 存储保护 上、下界存储保护： 基址—限长存储保护： 上、下界保护是一种简单的存储保护技术。
系统可为每个作业设置一对上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，用它们来限制用户程序的活动范围。 基址—限长存储保护： 上、下界保护的一个变种是采用基址-限长存储保护。 上下界保护 基址－限长保护 2019/2/23 《计算机操作系统》- 第6章

40 6.2.1 单一连续分配 最简单的管理方式（只有分配与回收） 操作系统和用户程序共享RAM 除了嵌入式系统外，其他的计算机不再使用这种方式
RAM中的OS ROM：DEV 用户程序 RAM中的OS 用户程序 ROM中的OS 早期大型机使用的内存管理方式 少数掌上电脑和嵌入式系统使用的内存管理方式 早期PC使用的内存管理方式（MS-DOS) 2019/2/23 《计算机操作系统》- 第6章

41 6.2.2 固定分区分配 早期支持多道程序的管理方式 将用户可使用内存区划分为固定大小，根据作业长度分配内存
支持多道程序的大型机使用，目前几乎不再使用 可用分区1 RAM中的OS 可用分区2 可用分区3 分区号 起始地址 终止地址 分区大小 分区1 100K 200K 分区2 400K 分区3 700K 300K 2019/2/23 《计算机操作系统》- 第6章

42 有n个分区，则可同时装入n个作业/任务。 分区大小：
固定分区分配 有n个分区，则可同时装入n个作业/任务。 分区大小： 相等 不相等，利用率较高 内存分配： 数据结构 将分区按大小排序，并将其地址、分配标识作记录 特点： 简单 有碎片（内零头） 2019/2/23 《计算机操作系统》- 第6章

43 固定分区分配 ~ 操作系统 作业A 作业B 作业C 分区号 大小(K) 起址(K) 状态 1 12 20 已分配 2 32 3 64 4
128 24K 32K 64K 128K ~ 256K 分配情况 2019/2/23 《计算机操作系统》- 第6章

44 固定分区分配 ~ 操作系统 作业A 作业B 作业C 分区号 大小(K) 起址(K) 状态 1 12 20 已分配 2 32 3 64 4
128 性能分析 在作业大小和出现频率均已知的情况下，固定分区是合适的。在这种情况下分区的大小选择与作业大小相当，这样内存的使用效率较高。 但是若作业的大小和出现的频率不知道时，势必造成分区的大小和作业的大小相差甚远，这样就会造成存储空间的浪费，从而影响整个系统的效率。 24K 32K 64K 128K ~ 256K 分配情况 2019/2/23 《计算机操作系统》- 第6章

45 固定分区分配 内存分配与回收 内存地址的重定位与保护 多队列最优适配、最小适配、合理适配（种种变化）
内存回收机制非常简单，只需要进行分区表操作 内存地址的重定位与保护 最简单的策略：在调入内存时直接修改指令 最严格的办法：密码校验，PSW的使用 最普遍的做法：引入硬件基址和界限存储器 2019/2/23 《计算机操作系统》- 第6章

46 6.2.3 可变分区分配 要点 空闲区表或队列的排序 按空闲区首址递增的次序 按空闲区大小的递增或递减次序 无满足要求的空闲区
在运行的过程中建立分区 使分区的大小刚好与作业 的大小相等 空闲分区的组织方式 分配的三种情况 分配算法 回收方法 空闲区表或队列的排序 按空闲区首址递增的次序 按空闲区大小的递增或递减次序 无满足要求的空闲区 空闲区大小 = SIZE 空闲区大小 > SIZE 首次适应：地址递增 最佳适应：大小递增 最坏适应：大小递减 上相邻 下相邻 上下均相邻 上下均不相邻 2019/2/23 《计算机操作系统》- 第6章

47 在系统运行的过程中建立分区，并使分区的大小刚好与作业的大小相等。 可解决固定分区严重浪费内存的问题。 是一种较为实用的存储管理方法。
可变分区分配 在系统运行的过程中建立分区，并使分区的大小刚好与作业的大小相等。 可解决固定分区严重浪费内存的问题。 是一种较为实用的存储管理方法。 要解决的问题 数据结构 分区分配算法 分区分配操作 2019/2/23 《计算机操作系统》- 第6章

48 描述分区的数据结构 数据结构 在动态分区存储管理中，要有相应的数据结构来登记空闲区的说明信息，它包括空闲区的大小和位置。
不同系统根据设计要求采用不同的结构。 常用的有表结构和队列结构。 系统还要设置了等待分区队列，当系统中无空闲区或无满足要求的空闲区时，则把申请者送入等待队列中，等待别的进程释放内存之后再唤醒队列中的进程。 2019/2/23 《计算机操作系统》- 第6章

49 描述分区的数据结构 2019/2/23 《计算机操作系统》- 第6章

50 可变分区分配 分配算法 在采用分区存储管理的系统中，系统初启后，除操作系统占用一个分区外，其余存储区为一个大的空闲区。
分区的分配是指系统根据用户的请求，在空闲区表或空闲区队列中寻找一个满足用户要求的空闲区，把这个空闲区分配给用户。 以空闲区表为例，当用户要求一个大小为SIZE的存储空间时，系统查询空闲区表，找一个大于或等于SIZE的空闲区。 2019/2/23 《计算机操作系统》- 第6章

51 可变分区分配 分配算法 空闲区表或队列的排序 按空闲区首址递增的次序 按空闲区大小的递增或递减次序 2019/2/23
《计算机操作系统》- 第6章

52 可变分区分配 分区分配的三种情况 系统中无满足要求的空闲区，则分配失败。
空闲区大小与SIZE相等，则修改空闲区表相应表目，向用户返回该空闲区首址，表示此空闲区已分给了要求的用户。 空闲区大于SIZE，这时将空闲区一分为二。 2019/2/23 《计算机操作系统》- 第6章

53 可变分区分配 分区分配的三种情况 策略一：从空闲区的上部开始划出SIZE大小的空闲区给用户；
一般常采用第二种办法，因为这样划分时，余下的部分在空闲区表中的首地址不变，只需要修改一下大小就行了。 2019/2/23 《计算机操作系统》- 第6章

54 可变分区分配 分区分配的算法 首次适应算法FF：原理、优点、缺点 要求空闲区按首址递增的次序组织空闲区表（队列）
循环首次适应算法：原理、优点、缺点 最佳适应算法：原理、优点、缺点 要求按空闲区大小从小到大的次序组成空闲区表（队列）。 最坏适应算法：原理、优点、缺点 要求空闲区按大小递减的顺序组织空闲区表（或队列）。 2019/2/23 《计算机操作系统》- 第6章

55 可变分区分配 分区分配的算法：首次适应法 分配：当进程申请大小为SIZE的内存时，系统从空闲区表的第一个表目开始查询，直到首次找到等于或大于SIZE的空闲区。从该区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区表中，但要修改其首址和大小。 回收：按释放区的首址，查询空闲区表，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区，将其大小和首址按照首地址大小递增的顺序插入到空闲区表的适当位置。 2019/2/23 《计算机操作系统》- 第6章

56 可变分区分配 分区分配的算法：首次适应法 注意：每次分配和回收后空闲区表或空闲区队列都要按首址递增的次序排序。 首次适应法的优点：
释放某一存储区时，若与空闲区相邻则合并到相邻空闲分区中去，这种情况并不改变该区在表中的位置，只要修改其大小或首址。 这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。 2019/2/23 《计算机操作系统》- 第6章

57 可变分区分配 分区分配的算法：最佳适应法 分配：当进程申请一个存储区时，系统从表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且这个空闲区是最佳的空闲区。 所谓最佳即选中的空闲区是满足要求的最小空闲区。 回收：按释放区的首址，查询空闲区表（队列） ，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列）。 分配和回收后要对空闲区表（队列）重新排序。 2019/2/23 《计算机操作系统》- 第6章

58 可变分区分配 分区分配的算法：最佳适应法 优点： 在系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不一定。
若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。 缺点： 空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储区的大量浪费。 2019/2/23 《计算机操作系统》- 第6章

59 可变分区分配 分区分配的算法：最坏适应法 分配：进程申请一个大小为SIZE的存储区时，总是检查空闲区表的第一个空闲区的大小是否大于或等于SIZE。若空闲区小于SIZE，则分配失败；否则从空闲区中分配SIZE的存储区给用户，然后修改和调整空闲区表。 回收：按释放区的首址，查询空闲区表（队列） ，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列）。 分配和回收后要对空闲区表（队列）重新排序。 2019/2/23 《计算机操作系统》- 第6章

60 可变分区分配 分区分配的算法：最坏适应法 最坏适应法看起来公似乎有些荒唐，但在更加严密地考察后，还是有它的优点：
当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较大的程序。 另一方面每次仅作一次查询工作。 2019/2/23 《计算机操作系统》- 第6章

61 分配方法举例 分配前的状态 2019/2/23 《计算机操作系统》- 第6章

62 首次适应法 分配后的状态 2019/2/23 《计算机操作系统》- 第6章

63 最佳适应法 分配后的状态 2019/2/23 《计算机操作系统》- 第6章

64 最坏适应法 分配后的状态 2019/2/23 《计算机操作系统》- 第6章

65 不同分配算法的对比 分配前的状态 2019/2/23 首次分配 《计算机操作系统》- 第6章 最佳分配 最坏分配

66 可变分区分配 分配算法的分析 分配算法各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。
对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。 对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。 2019/2/23 《计算机操作系统》- 第6章

67 可变分区分配 碎片问题 由于空闲区的大小与申请内存的大小相等的情况是很少的，绝大多数情况是从一个空闲区中切去一块，剩下的部分作为一个空闲区仍留在空闲区表中，随着时间的推移，空闲区的发展趋势是越来越小，直至不能满足任何用户要求。 这种不能被任何用户使用的极小的空闲区称为碎片。碎片的出现造成了存储空间的浪费。 2019/2/23 《计算机操作系统》- 第6章

68 规定门限值（由操作系统规定，如1K），分割空闲区时，若剩余部分小于门限值，则不再分割此空闲区。
可变分区分配 解决方案 规定门限值（由操作系统规定，如1K），分割空闲区时，若剩余部分小于门限值，则不再分割此空闲区。 定期压缩存储空间，将所有空闲区集中到内存的一端，但这种方法的系统开销太大。 2019/2/23 《计算机操作系统》- 第6章

69 可变分区分配 内存分配 流程图 2019/2/23 《计算机操作系统》- 第6章

70 分区回收 内存回收 F1 回收区 F2 回收区 F2 F1 回收区 F2 F1 回收区 2019/2/23 《计算机操作系统》- 第6章

71 碎片的产生 固定分区－碎片（内零头） 碎片的处理
思考 碎片的产生 固定分区－碎片（内零头） 动态分区－外部零头 碎片的处理 2019/2/23 《计算机操作系统》- 第6章

72 思考 关于内存空间的分配与回收 关于内存空间的共享和保护 关于内存空间的扩充 关于内存管理面临的性能问题 如何定义内存管理的数据结构？
如何设计内存管理的基本算法？ 关于内存空间的共享和保护 你能够想象到哪些硬件保护机制？ 你能够想象到哪些软件保护机制？ 关于内存空间的扩充 你能够想象到哪些可以运行大程序的方法？ 关于内存管理面临的性能问题 有哪些性能参数？如何保证内存管理的性能？ 2019/2/23 《计算机操作系统》- 第6章

73 课堂练习：可变分区分配 例1：有作业序列：作业A要求18K；作业B要求 25K，作业C要求30K。系统中空闲区按不同算法 组成的空闲区队列
2019/2/23 《计算机操作系统》- 第6章

74 课堂练习：可变分区分配 例1：有作业序列：作业A要求18K；作业B要求 25K，作业C要求30K。系统中空闲区按不同算法 组成的空闲区队列
经分析可知：最佳适应法对这个作业序列是合适 的，而其它算法对该作业序列是不合适的。 经分析可知：最佳适应法对这个作业序列是合适的，而其它算法对该作业序列是不合适的。 2019/2/23 《计算机操作系统》- 第6章

75 课堂练习：可变分区分配 有作业序列：作业A要求21K；作业B要求30K，作业C要求25K。 2019/2/23 《计算机操作系统》- 第6章

76 课堂练习：可变分区分配 已知主存有256KB容量，其中OS占用低址20KB，可以有这样的一个作业序列：作业1要求 80KB；作业2要求16KB；作业3要求140KB；作业1完成；作业3完成；作业4要求 80KB；作业5要求120KB。试用首次适应算法和最佳适应算法分别处理上述作业序列(在存储分配时，从空白区高址处分割作为已分配区)，并完成以下各步： (1) 画出作业1、2、3进入主存后，主存的分配情况。 (2) 作业1、3完成后，画出主存分配情况。 (3) 画出两种算法中空白区的分区描述器信息(假定分区描述器所需占用的字节数已包含在作业所要求的主存容量中)及空白区链接情况。 (4) 哪种算法对该作业序列而言是适合的？ 2019/2/23 《计算机操作系统》- 第6章

77 本章目录 6.1 存储器管理概述 6.2 连续存储空间管理 6.3 分页式存储管理 6.4 分段式存储管理 分页存储管理的基本原理 页表
6.1 存储器管理概述 6.2 连续存储空间管理 6.3 分页式存储管理 分页存储管理的基本原理 页表 地址变换机构 快表 多级页表 反置页表 页面共享和保护 6.4 分段式存储管理 2019/2/23 《计算机操作系统》- 第6章

78 6.3 分页式存储管理 连续分配方式 碎片 紧凑 代价 离散分配方式 分页 分段 段页式 基本的分页存储管理方式（纯分页存储管理方式）
连续分配方式 碎片 紧凑 代价 6.3 分页式存储管理 分页技术是由曼彻斯特大学提出，并于1960年前后在Atlas计算机上实现。这种技术对操作系统的发展产生了深远影响。 离散分配方式 分页 分段 段页式 基本的分页存储管理方式（纯分页存储管理方式） 2019/2/23 《计算机操作系统》- 第6章

79 6.3.1 分页存储管理基本思想 用户程序划分 逻辑地址
把用户程序按逻辑页划分成大小相等的部分，称为页（page）。从0开始编制页号，页内地址是相对于0编址。 逻辑地址 用户程序的划分是由系统自动完成的，对用户是透明的。 通常，一页的大小为2的整数次幂。因此，地址的高位部分为页号，低位部分为页内地址 2019/2/23 《计算机操作系统》- 第6章

80 分页存储管理基本思想 内存空间 内存分配 按页的大小划分为大小相等的区域，称为块或内存块（物理页面，页框）
以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻 2019/2/23 《计算机操作系统》- 第6章

81 页地址映射 页表 页大小的选择 页地址映射 分页存储管理中的信息保护 快表和联想存储器 两级页表和多级页表 2019/2/23
《计算机操作系统》- 第6章

82 6.3.2 页表内容 页表包含以下几个表项： 页号：登记程序地址空间的页号。 块号：登记相应的页所对应的内存块号
其它：登记与存储信息保护有关的信息。 页号 块号 其它 5 … 1 65 2 13 2019/2/23 《计算机操作系统》- 第6章

83 页面与页表 页面 地址结构 页号P 位移W 页面和物理块：逻辑空间和内存空间 由机器的地址结构决定 31 12 11 0
页太大，页内碎片大。 页太小：页表可能很长，换入/出效率低 地址结构 设: 逻辑地址A; 页大小L(设为1024); 页内偏移d; 页号P P＝INT（A/L） d＝A mod L 如： A＝2170B. 则P＝2，d＝122 页号P 位移W 2019/2/23 《计算机操作系统》- 第6章

84 页面与页表 设：逻辑地址A；页大小L(设为1024)；页内偏移d；页号P
P＝INT（A/L） d＝A mod L 又如：页面大小为4KB的系统中，若逻辑地址为28024，则由上式求得页号为6，页内偏移量为3448。 如何得到页号和页内地址呢？ 28024的二进制用32位表示为： 因为页面大小为4KB，则取低12位为页内地址，剩余高位是页号。 2019/2/23 《计算机操作系统》- 第6章

85 页面与页表 用户程序 1 2 3 4 5 6 7 8 9 页表 内存 页号 块号 0页 1页 2页 3页 4页 5页 n页 2 1 3 6 8 4 9 5 2019/2/23 《计算机操作系统》- 第6章

86 6.3.3 地址变换机构 完成以下任务： 基本地址变换机构： 逻辑页号——物理块号的映射，由页表完成。 越界保护
每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址装入页表寄存器。 2019/2/23 《计算机操作系统》- 第6章

87 地址变换机构 分页系统的地址变换机构 2019/2/23 《计算机操作系统》- 第6章

88 ① 页号3与页表寄存器中的页表长度比较判断是否越界，如果越界，则转错误中断处理，否则转②；
2019/2/23 《计算机操作系统》- 第6章

89 ② 页表中该项在内存中的对应地址=页表始地址R+页号3×页表项长度i，访问该地址R+3i，得到物理块号11；
2019/2/23 《计算机操作系统》- 第6章

90 ③ 11(块号)×1024(块大小)+723(页内地址) = 11987(物理地址)； 2019/2/23 《计算机操作系统》- 第6章

91 ④ 访问内存11987单元，得到需要的数据365。 2019/2/23 《计算机操作系统》- 第6章

92 6.3.4 快表 具有快表的地址变换机构 不具快表，则需两次访问内存。 有快表，速度提高。 快表贵，不能太多。 第一次：访问页表
第二次：得到绝对地址内容 有快表，速度提高。 快表贵，不能太多。 2019/2/23 《计算机操作系统》- 第6章

93 快表 2019/2/23 《计算机操作系统》- 第6章

94 ① 如果对主存的一次存取需要1.5μs，试问实现一次页面访问的存取时间是多少?
快表 例：有一页式系统，其页表存放在主存中： ① 如果对主存的一次存取需要1.5μs，试问实现一次页面访问的存取时间是多少? ② 如果系统加有快表，平均命中率为85%，当页表项在快表中时，其查找时间忽略为0，试问此时的存取时间是多少? 2019/2/23 《计算机操作系统》- 第6章

95 快表 答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。 页表在主存的存取访问时间 = 1.5*2 =3(μs) 增加快表后的存取访问时间 = 0.85*1.5+(1-0.85)*2*1.5 = 1.725(μs) 2019/2/23 《计算机操作系统》- 第6章

96 页表可能很大，将其离散存放在不同页块 中。
6.3.5 两级和多级页表 页表可能很大，将其离散存放在不同页块 中。 建一“外部页表”来管理这些离散页表块。 相当于单级页表中的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。 64位机器页表一般>3级，最外层页表常驻。 2019/2/23 《计算机操作系统》- 第6章

97 两级和多级页表 2019/2/23 《计算机操作系统》- 第6章

98 举例 例：某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：
页号 物理块号 5 1 10 2 4 3 7 则逻辑地址0A5C（H）所对应的物理地址为：125C 2019/2/23 《计算机操作系统》- 第6章

99 举例 0A5C＝0000,1010,0101,1100 ＝0000,1010,0101,1100 页号为2，对应块号为4，有： 物理地址：0001,0010,0101,1100 即：125C 2019/2/23 《计算机操作系统》- 第6章

100 分页存储管理方案的评价 优点： 缺点1： 缺点2： 缺点3： 缺点4： 采用动态地址映射会增加计算机成本和降低处理机的速度。
便于多道程序设计，提高了内存的利用率，而不必像动态分区分配那样执行紧凑操作。 缺点1： 采用动态地址映射会增加计算机成本和降低处理机的速度。 缺点2： 各种表格要占用一定容量的内存空间，而且还要花费一部分处理机时间来建立和管理这些表格。 缺点3： 虽然消除了大量碎片，但每个作业的最后一页一般都有不能充分利用的空白区；减少页面大小，可以减少内存的浪费，但页表的长度又增加了，这也是一个矛盾。 缺点4： 存储扩充问题仍未得到解决。当没有足够空间能装下整个作业地址空间时，该作业还是无法运行。 2019/2/23 《计算机操作系统》- 第6章

101 一维虚拟存储管理--分页式 逻辑地址、虚拟地址、物理地址 一个程序经编译得到的指令地址空间，叫做逻辑地址空间
当逻辑地址空间大于物理地址空间时，叫做虚拟地址空间 逻辑地址空间—虚拟地址空间—MMU单元—物理地址空间 2019/2/23 《计算机操作系统》- 第6章

102 一维虚拟存储管理--分页式 分页式存储管理的核心思想 制定统一的地址空间描述机制：页与页表
对逻辑地址而言，使用分页机制实现对虚拟地址空间的划分 对物理地址而言：使用分页机制实现对物理地址空间的管理 虚拟存储的核心思想：以页为基本单位，不同地址空间的转换和映射 2019/2/23 《计算机操作系统》- 第6章

103 一维虚拟存储管理--分页式 分页式存储管理的困难和问题 地址映射与保护：如何快速、有效的实现地址映射？
虚拟存储的关键：如何实现页面的置换？如何保证程序运行的效率？ 2019/2/23 《计算机操作系统》- 第6章

104 二维虚拟存储管理--分段式 分页式虚拟存储管理的难题 设计与实现机制复杂，需要软件和硬件的精妙配合
影响性能因素多样化，保证存储体系的高效很困难 仅从计算机角度出发，人难以理解、监控和管理 2019/2/23 《计算机操作系统》- 第6章

105 二维虚拟存储管理--分段式 分段式存储管理思想的产生 遵循程序的逻辑化特性，将其分为不同的“段”，易于理解和监控
继承虚拟地址的思想，以“段号＋段内偏移”实现地址映射 对物理内存进行一维分割，内存使用则体现二维逻辑性 2019/2/23 《计算机操作系统》- 第6章

106 二维虚拟存储管理--分段式 分段式存储的优点和缺点 优点1：存储管理过程简单、灵活简便的适应各类程序
优点2：易于程序的编译、链接，易于不同程序间的共享 缺点：管理粒度较大，操作系统的管理职能不深入，无法保证稳定性 2019/2/23 《计算机操作系统》- 第6章

107 问题 反置页表的基本原理 分页方式中的共享与保护 2019/2/23 《计算机操作系统》- 第6章

108 本章目录 6.1 存储器管理概述 6.2 连续存储空间管理 6.3 分页式存储管理 6.4 分段式存储管理 分段存储管理 段表和地址变换机构
6.1 存储器管理概述 6.2 连续存储空间管理 6.3 分页式存储管理 6.4 分段式存储管理 分段存储管理 段表和地址变换机构 分段与分页的区别 具有分页的分段 段的共享和保护 2019/2/23 《计算机操作系统》- 第6章

109 分段系统的基本原理 分段 在分段式存储管理中，段名用段号代替，段地址从0开始编址，因为各段的逻辑信息内容不同，所以段长度不同。
当一个用户程序装入内存时，系统为每个段分配一个连续的内存区域，而各个段之间可以离散存放。 2019/2/23 《计算机操作系统》- 第6章

110 6.4.1 分段系统的基本原理 分段： 段表： 地址变换机构 分页与分段： 对用户而言，分段是2维的。 段号+段内地址。
逻辑段—map—物理段 地址变换机构 分页与分段： 页是信息的物理单位，段是逻辑单位 页长度固定，段长度不固定（由用户指定） 一维与二维 2019/2/23 《计算机操作系统》- 第6章

111 分段系统的基本原理 2019/2/23 《计算机操作系统》- 第6章

112 分段系统的基本原理 2019/2/23 《计算机操作系统》- 第6章

113 6.4.2 地址变换机构 ①段号3与段表寄存器存放的段表长度比较以判断是否越界，如果越界，则转错误中断处理，否则转②； 2019/2/23
《计算机操作系统》- 第6章

114 6.4.2 地址变换机构 ②计算：段表始地址+段号×段表项长度，得到段表中3号段这一项在内存中的地址，访问该地址得到对应段基址为8 K；
2019/2/23 《计算机操作系统》- 第6章

115 6.4.2 地址变换机构 ③ 8 K(段基址)+723(段内地址) = 8915(物理地址)； 2019/2/23
《计算机操作系统》- 第6章

116 6.4.2 地址变换机构 ④访问内存8915单元，得到需要的数据365。 2019/2/23 《计算机操作系统》- 第6章

117 共享 段式系统易于共享 分页与分段共享比较 可重入码（纯代码） 各个进程应保留局部数据区 2019/2/23 《计算机操作系统》- 第6章

118 分页系统中共享editor 进程1 页表 主存 进程2 页表 … ed1 ed2 ed40 data1 data10 ed1 ed2 …
21 22 … 60 61 70 主存 … ed1 ed2 ed40 data1 data10 进程2 页表 21 22 … 60 71 80 ed1 ed2 … ed40 data1 data10 分页系统中共享editor 2019/2/23 《计算机操作系统》- 第6章

119 分段系统中共享editor editor data1 段长 基址 160 80 40 240 editor data1 … data2 段长
380 editor data2 2019/2/23 《计算机操作系统》- 第6章

120 段页式存储管理 段号S 段内页号P 页内位移量W 分页优点：提高内存利用率 分段优点：方便用户，易于共享，保护，动态链接。
段页式系统基本原理 段号 + 段内页号 + 页内地址 注意：对用户而言，仍然是二维编址。 对系统而言，则是三维编址 段号S 段内页号P 页内位移量W 2019/2/23 《计算机操作系统》- 第6章

121 段页式存储管理 地址变换 三次访内存操作 为提高速度，在地址变换机构中增设一高速缓冲寄存器（Cache） 2019/2/23
《计算机操作系统》- 第6章

122 例如给定某个逻辑地址中，段号为2，段内地址为6015，若系统规定块大小为1 KB，则采用段页式管理，该逻辑地址表示：段号为2，段内页号为5，页内地址为895。
地址变换机构 2019/2/23 《计算机操作系统》- 第6章

123 自学 分段中的共享与保护 分页与分段的区别 2019/2/23 《计算机操作系统》- 第6章

124 段是依据程序的逻辑结构划分的，页是按内存线性空间物理划分的。 段式技术中程序地址空间是二维的，分页技术中程序地址空间是一维的。
回顾：分段与分页技术的比较 段是依据程序的逻辑结构划分的，页是按内存线性空间物理划分的。 段式技术中程序地址空间是二维的，分页技术中程序地址空间是一维的。 段是面向用户的，页对用户而言是透明的。 段长由用户决定，且各段的大小一般不相等，唯一的限制是最大长度。而页长是由系统决定的，各页的长度必须相等。 段的共享比页的共享更容易。 2019/2/23 《计算机操作系统》- 第6章

125 存储管理方案的评价--分段 优点： 方便用户编程：多个逻辑段形成作业这种组织方式，使用户可以清晰地设计和了解程序的结构。
便于实现程序和数据的共享与保护：段的逻辑单位性质使分段共享与保护是现实和有意义的。 程序的动态链接实现方便：当程序在执行过程中需要某段时，才将其调入内存链接。 可解决应用中无法预知的数据动态增长的问题。 2019/2/23 《计算机操作系统》- 第6章

126 存储管理方案的评价--段页 优点： 缺点： 保留了分段存储管理和分页存储管理的全部优点，满足了用户和系统两方面的需求。
性能提升是有代价的，增加了硬件成本、系统的复杂性和管理上的开销，程序碎片在每个段都存在，段表、段内页表等表格占用相对较大的内存空间，存在着系统发生抖动的危险。 2019/2/23 《计算机操作系统》- 第6章

127 碎片的产生 固定分区－碎片（内零头） 碎片的处理
再次思考 碎片的产生 固定分区－碎片（内零头） 可变分区－外部零头 碎片的处理 紧凑 分页、分段、段页 2019/2/23 《计算机操作系统》- 第6章

128 作业通过发送电子邮件附件形式提交到助教老师邮箱：
练习 6.10，6.11，6.12，6.13 作业通过发送电子邮件附件形式提交到助教老师邮箱： 赵 静 作业文件名命名要求： OS_学号_姓名_n.doc （n为当章节序号） 如一个合法文件名： OS_95002_张三_6.doc 2019/2/23 《计算机操作系统》- 第6章

129 Any Question? Thank you ! 2019/2/23 《计算机操作系统》- 第6章