3.1 存储的层次结构

3.1.1 存储的层次结构

1. 存储结构的层次结构

在现代的层次结构中, 存储器是信息处理的来源与归宿, 占据重要位置. 但是, 在现有技术条件下, 任何一种存储装置, 都无法同时从速度与容量两方面, 满足用户的需求. 实际上它们组成了一个速度由快到慢, 容量由小到大的存储装置层次.

2. 各种存储器

• 高速缓存 cache:
  • 少量的, 非常快速, 昂贵, 易变的
• 内存 RAM:
  • 若干兆字节, 中等速度, 中等价格, 易变的
• 磁盘
  • 数百兆或数千兆字节, 低速, 价廉, 不易变的
• 由操作系统协调这些存储的使用

3.1.2 存储管理的目的

• 内存分配
  • 使各得其所, 提高利用率及适应动态增长要求
  • 连续分配/离散分配方式
• 地址映射
  • 逻辑地址转换为物理地址, 与分配方式相关
• 内存保护
  • 基于地址的保护, 存取访问控制保护
• 内存 “扩充”
  • 对换技术, 虚拟存储技术

3.1.3 基本概念

1. 定位 (存储分配): 为具体的程序和数据等分配存储单元或存储区工作
2. 映射: 把逻辑地址转换为相应的物理地址的过程
3. 隔离: 按存取权限把合法区与非法取分隔, 实现存储保护
4. 名空间
   • 程序员在程序中定义的标识符
   • 程序符号集合
   • 由程序员自定义
   • 没有地址的概念
5. 地址空间
   • 程序用来访问信息所用地址单元的集合
   • 逻辑地址的集合
   • 由编译程序生成
6. 存储空间
   • 主存中物理单元的集合
   • 物理地址的集合
   • 由装配程序等生成

7. 逻辑地址与物理地址

   • 逻辑地址 (相对地址, 虚地址):
     • 用户程序经过汇编或编译后形成目标代码, 目标代码通常采用相对地址的形式, 其首地址为0, 其余指令中的地址都相对于首地址而编址
   • 物理地址 (绝对地址, 实地址)
     • 内存中的存储单元的地址, 可以直接寻址

8. 存储共享

   • 内存共享: 两个或多个进程共用内存中相同区域
   • 目的: 节省内存空间, 提高内存利用率
   • 实现进程通信 (数据共享)
   • 共享内容:
     • 代码共享, 要求代码为纯代码
     • 数据共享

9. 存储保护与安全

   • 保护目的:
     • 为多个程序共享内存提供保障, 使在内存中的各道程序, 只能访问它自己的区域, 避免各道程序间相互干扰, 特别是当一道程序发生错误时, 不至于影响其他程序的运行. 通常由硬件完成保护功能, 由软件辅助实现. (特权指令不能完成存储保护)
   • 存储保护
     • 保护系统程序区不被用户侵犯 (有意或无意的)
     • 不允许用户程序读写不属于字节的地址空间的数据(系统区地址空间, 其他用户程序的地址空间)
   • 保护过程 – 防止地址越界
     • 每个进程都有自己的独立的地址空间, 如果一个进程在运行时所产生的地址在其地址空间之外, 则发生地址越界. 即当程序要访问某个内存单元时, 由硬件检查是否允许, 如果允许则执行, 否则产生地址越界中断, 由操作系统进行相应处理

10. 内存 “扩充”

• 通过虚拟存储技术实现
  • 用户在编制程序时, 不应该受内存容量限制, 所以要采用一定技术来 "扩充"内存的容量, 使用用户得到比实际内存容量大的多的内存空间
  • 具体实现是在硬件支持下, 软硬件相互协作, 将内存和外村结合起来统一使用, 通过这种方法把内存扩充, 使得用户在编制程序时不受内存限制

3.2 程序的装入和链接

程序处理的基本过程

3.2.1 程序的装入

1. 决定装入方式

程序中所使用的绝对地址, 可以编译或汇编时给出, 也可以由程序员直接赋予. 但在由程序员直接给出绝对地址时, 不仅要求程序员熟悉内存的使用的情况, 而且一旦程序或数据被修改后, 可能要改变程序中的所有地址. 因此通常是宁可在程序中采用符号地址, 然后再编译或汇编时, 在将这些符号地址转化为绝对地址

2. 可重入定位装入方式

• 静态可重定位装入方式和动态可重定位装入方式

  • 如果在程序装入时一次性地完成程序中所有地址敏感指令及数据的地址修正且以后不在改变, 则称对应的地址变换为静态重定位.
  • 如果在程序装入时并不进行相对地址到绝对地址的转换过程, 而是伴随程序执行进展来逐步进行程序中相关地址敏感指令及数据的地址修正, 则称对应的地址变换为动态重定位

• 静态可重定位装入方式不允许程序在装入之后的运行过程中发生内存位置的移动

• 动态可重定位装入方式及动态重定位过程通常需要一定的硬件机构支持以使地址转换不影响指令执行速度.

3. 动态运行时装入方式

动态运行时的装入程序, 在把装入模块转入内存后, 并不立即把装入模块中的相对地址转换为绝对地址, 而是把这种地址转换推辞到程序真正要执行时才进行

3.2.2 程序的链接

1. 静态链接方式

2. 装入时动态链接

• 装入时动态链接方式: 是指在程序装入内存之前并未进行程序各目标模块的链接, 而是在装入时, 一边装入一边链接
• 优点:
  1.便于修改和更新
  2. 便于实现对目标模块的共享

3. 运行时动态链接

这种链接方式是将对某些模块的链接推迟到执行时才执行, 即, 在执行过程中,当发现一个被调用模块尚未装入内存时, 立即由 OS 去找到该模块并将之装入内存, 把它链接到调用者模块上. 凡在执行过程中未被用到的目标模块, 都不会被调入内存和链接到装入内存, 这样不仅可加快程序的装入过程, 而且可节省大量内存空间

3.2.3 重定位

把作业地址空间中使用的逻辑地址变为内存空间中的物理地址的过程, 又称为地址 映射

1. 重定位的类型

1. 静态重定位: 当用户程序被装入内存时一次性实现逻辑地址到物理地址的转换, 以后不在转换(一般在装入内存时由软件完成) 作业i在执行前一次变址, 直到该作业完成退出内存为止.

2. 动态重定位

在程序运行过程中药访问数据时再进行地址变换, 由地址变换机构进行的地址变换, 硬件上需要重定位寄存器的支持

• 重定位寄存器: 在执行一条指令操作数时, 要将指令给出的有效地址与重定位器中的内容相加, 得到访问地址, 从而实现了地址动态修改
• 映像方式: 采用页表来描述, 实页面的对应关系

3.3 连续分配存储管理

连续内存分配: 每个进程位于一个连续的内存空间

3.3.1 单一连续内存空间管理

• 在单道环境下, 不管是单用户系统还是单道批处理系统, 进程(作业) 执行时除了系统占用一部分主存外, 剩下的主存区域全部归它占用, 主存可以画分为三部分: 系统区, 用户去, 空闲区, 用户占用区是一个连续的存储区所以又称为单一连续区存储管理
• 单用户系统在一段时间内, 只有一个进程在内存, 故内存分配管理十分简单, 内存利用率低, 内存分为两个区域, 一个供操作系统使用, 一个供用户使用.

工作流程

单一连续区分配采用静态分配和静态重定位方式, 即作业或进程一旦进入主存, 就一直等到它运行结束后才能释放主存

• 缺点
  • 不支持多道程序
  • 主存利用率不高
  • 程序的运行受主存容量限制

存储保护

• 自动地址修改 例如, 存储器的地址空间为 12K, 而操作系统位于低地址端的 4K 内, 对于这样的操作系统, 我们给用户一个 13 位的地址空间, 并对其每个寄存器访问自动加上 4K. 如果操作系统占用高地址端的 4K, 则我们取每一个存储访问 R, 而实际上, 其地址为 (R mod 8K), 从而实现了对操作系统的保护
• 0 页, 1页寻址 通过对每个用户生成的地址左端拼接上一位 1 来实现 OS 区 与用户区. 把操作系统确定在 0 页, 而把用户作业放在 1 页
• 界限寄存器 通过增加界限寄存器, 划分 OS区与用户区

3.3.2 固定分区分配

分区式管理是满足多道程序的最简单的存储管理方案。它的基本思想是将内存划分若干个连续区域，称为分区。分区只能存储一个程序，而程序也只能在它所驻留的分区中运行。

1. 固定分区

• 预先把可分配的主存储区空间分割成若干个连续区域, 称为一个分区. 每个分区的大小可以相同也可以不同. 但分区大小固定不变, 每个分区装一个且只能装一个作业

• 存储分配: 如果有一个空闲区, 则分配给进程

2. 内存分配管理

通过设置内存分配表, 内存分配简单

缺点: 内存利用率不高

3.3.3 可变分区分配

• 基本思想: 内存不是预先划分好的, 而是作业装入时, 根据作业的需求和内存空间的使用情况来决定是否分配. 若有足够的空间, 则按需要分割一部分分区给该进程; 否则令其等待主存空间
• 内存管理: 设置内存空闲块表 – 记录了空闲起始地址和长度
• 内存分配: 动态分配
• 内存回收: 当某一块归还后, 前后空间合并, 修改内存空闲块表

1. 分区分配中的数据结构

(1) 空闲分区链

系统设立空闲分区链表: 每个空闲块的前后两个单元, 放置必要的说明信息和指针. 系统只要设立一个链首指针, 指向第一个空闲块即可. 分配程序可以依照自由块链表, 来查找合适的空闲块进行分配

(2) 分区分配表

2. 分区分配操作

(1) 分配内存

(2) 回收内存

4. 分配算法

按空闲块链接的方式不同, 可以有以下四种算法:

• 最佳适应法
  • 接到内存申请时, 在空闲块表中找到一个不小于请求的最小空块进行分配
  • 为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域
  • 特点: 用最小空间满足要求
• 最坏适应法
  • 接到内存申请时, 在空闲块表找到一个不小于请求的最大空块进行分配, 与最佳适应算法相反, 它在作业选择存储块时, 总是寻找最大的空白区
  • 特点: 当分割后空闲块仍为较大空块
• 首次适应法
  • 为作业选择分区时总是按地址从高到低搜索, 只要找到可以容纳该作业的空白快, 就把该空白分配给该作业
• 循环首次适应法
  • 类似首次适应每次分区时, 总是从上次查找结束的地方开始, 使得内存空间利用更加均衡

5. 碎片问题

• 经过一段时间的分配回收后, 内存中存在很多很小的空闲块. 它的每一个都很小, 不足以满足分配要求: 但其总和满足分配要求. 这些空闲块被称为碎片
• 造成存储资源的浪费

碎片问题的解决

• 紧急技术: 通过在内存移动程序, 将所有小的空闲区域合并为大的空闲区域
• 问题: 开销大; 移动时机

6. 分区式存储管理的优缺点

• 优点
  • 便于动态申请内存
  • 便于共享内存
  • 便于动态链接
• 缺点
  • 碎片问题(外碎片), 内存利用率不高, 受实际内存容量限制

3.3.4 可重定位分区分配

2. 动态重定位的实现

3. 动态重定位分区分配算法

4.可重定位分区的优缺点

• 优点: 解决了可变分区分配所引入的 “外零头” 问题. 消除内存碎片, 提高内存利用率
• 缺点: 提高硬件成本, 紧凑时花费CPU时间

5. 多重分区

以上讨论都是基于一个作业在主存中占据的是一个连续分区的假定, 为了支持结构化程序设计, 操作系统往往把一道作业分成若干片段(如子程序, 主程序, 数据组等). 这样, 片段之间就不需要连续了, 只要增加一些重定位寄存器, 就可以有效地控制一道作业片段之间的调用

6. 分区的保护

为了防止一首作业有意或无意地破坏操作系统或其它作业. 一般来说, 没有硬件支持, 实现有效的存储保护是困难的. 通常采用:

• 界限寄存区方式
• 保护键方式
• 两种措施, 或二者兼而有之

保护过程 – 防止地址越界

• 一般由硬件提供一对寄存器:

基址寄存器: 存放起始地址
限长寄存器: 存放长度

界限寄存器保护

基址、限长寄存器保护

防止操作越权

对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权 即读写保护

保护键方式

3.4 分页存储管理

3.4.1 页式存储管理的引入

• 在动态分区的存储空间中, 存在"零头问题", 尽管采用"紧凑"计数可以解决这个问题, 但要为移动大量信息花去不少的处理事件, 代价较高.

3.4.2 页面与页表

1. 页面和物理块

分页存储管理, 是将一个进程的逻辑地址空间分成若干个大小相等的片, 称为 页面或页, 并为各页加以编号. 相应的, 也把内存空间分成与页面相同大小的若干个存储块, 称为(物理)块或页框.

• 在为进程分配内存时, 以块为单位将进程中的若干个页分别装入到多个可以不相邻的物理块中. 由于进程的最后一页经常装不满一块而形成了不可利用的碎片, 称为"页内碎片".

2. 页表

• 列出了作业的逻辑地址与其在主存中的物理地址间的对应关系
• 页面大小: 页面的大小应选择得适中, 且页面大小应是2的幂, 通常为 512B ~ 8KB
• 一个页表中包含若干个表目, 表目的自然序号对应于用户程序中的页号, 表目中的快号是该页对应的物理块号
• 页表的每一个表目除了包含指向页框的指针外, 还包含一个存取控制字段
• 表目页称为页描述子.

分页管理中页与页框的对应关系示意图

3. 地址结构

分页地址中的地址结构如下:

对某特定机器, 其地址结构是一定的, 若给定一个逻辑地址空间的地址A, 页面的大小为L, 则页号P和页内地址d可按下式求得:

3.4.3 地址变换机构

• 把虚拟地址2500转换成页号P=2, 位移量W=452;
• 如果页号2大于页表大小, 则中断; 否则继续;
• 页号2与页表地址1000运算(1000+2*20, 设页描述子大小为20) 得到页描述子地址为1040;
• 从页描述子中读取块号8;
• 根据页描述子的"存取控制" 判断该指令是否被允许访问内存, 如果不允许, 则中断; 否则继续
• 块号8与位移量452运算 (8 * 1024 + 452 = 8644, 1024 为页面大小)得到物理地址8644
• 把内存地址8644单存中数字写进寄存器1

3. 管理

1. 页表

   • 系统为每个进程建立一个页表, 页表给出逻辑页号和具体内存号相应的关系
   • 页表放在内存,属于进程的现场信息

2. 空快管理

   • 位示图
   • 内存页表

3. 内存的分配与回收

位示图法

• 建立一张位示图, 以反映整个存贮空间的分配空间,每一个字的每一位都对应一个物理块
  • 0: 未分配(空白块)
  • 1: 已分配

为了找到N个自由块, 就需要搜索位示图, 找到N个 “0” 位, 再经过一个简单的运算就得知相应的快地址(物理地址), 存贮空间的分配和回收工作较为方便, {0,1} 转换.

• 盘块的分配

  1. 顺序扫描找到一个或一组值为 “0” 的二进制位
  2. 转换成相应盘快号: $B=ni\times j$
  3. 修改位示图 map[i,j] = 1

• 盘块的回收

  1. 将回收盘块的盘块转换位位示图的行号和列好
     • $i=b÷n$
     • j = b mod n
  2. 修改位示图: 令map[i,j] = 0

内存的分配

• 计算一个作业所需要的总块数 N
• 查位示图, 看看是否还有N个空闲块
• 如果有足够的空闲块, 则页表长度设为 N, 可填入 PCB中; 申请页表区, 把页表起始地址填入PCB
• 依次分配N个空闲块, 将块号和页号填入页表
• 修改位示图

4. 快表

如果把页表放在主存中, 无疑会影响系统的性能, 这是因为每次访问主存, 首先必须访问页表, 读出页描述子, 之后根据形成的实际地址在访问主存, 这要使访问主存的次数加倍, 因而使总的处理速度明显下降.

为了解决这个问题, 人们采用一组硬件寄存器, 存放当前访问过的页的页描述子, 每次访问主存时, 首先查找快表, 若找到所需的页描述子, 则快速形成物理地址. 否则从页表中查找后形成物理地址, 同时把页描述子写入快表. 如果设计得到, 快表的命中率可以很高

3.4.4 两级和多级页表

现代的大多数计算机系统, 都支持非常大的逻辑地址空间($2^{32}$ ~ $2^{64}$). 页表就变得非常大, 要占用相当大的内存空间. 可采用两个方法来解决这一问题: ① 采用离散分配方式来解决难以找到一块连续的大内存空间的问题; ② 只将当前需要的部分页表项调入内存, 其余的页表项仍驻留在磁盘上, 需要时再调入.

1. 两级级页表

• 32 位 进程页表多大?

  设: 页面大小为: 4K, 用户空间 4GB
  则: 一个进程 1M 页
  设: 每个内存块号 4 字节
  则: 进程页表 1K 页, 共占 4M 内存空间

• 结论: 一个进程的页表的各页之间可以不用连续存放

• 解决: 页表本身使用地址索引 – 页目录

2. 多级级页表

• 64位 进程页表多大?

  设: 页表大小为4K
  则: 一个进程 $2^{52}$ 页
  设: 每个内存块号 4字节
  则: 进程页表 $2^{42}(2^{52}÷2^{10})$ 页, 两级页表不能接受

• 结论: 必须采用三级以上的多级页表

3. 反置页表

• 一般页表是按页号进行排序, 而页表内容包括物理块号. 反置页表则不然, 它为每一个物理块设置一个表项, 并将它们按物理块号进行排序, 而表的内容包括对应页号及其隶属进程的标示符

3.5 基本段存储管理

3.5.1 分段式存储管理的引入

在分页存储管理系统重, 作业的地址空间是一维线性的, 这破坏了程序内部天然的逻辑结构, 造成共享, 保护的困难. 引入分段存储管理方式, 主要是为了满足用户和程序的下述需要:

1. 方便编程
2. 信息共享
3. 信息保护
4. 动态增长
5. 动态链接

3.5.2 分段系统的基本原理

1. 分段
   程序的地址空间被分化为若干分段, 每个分段各自定义一组逻辑信息.
   分段地址中的地址具有如下结构:
   
   

2. 段表

3. 硬件支持

• 系统设置一对寄存器
• 段表始址寄存器: 用于保存正在运行进程的段表的始址
• 段表长度寄存器: 用于保存正在运行进程段表的长度

4. 地址变换机构

5. 分页和分段的主要区别

1. 页是信息的物理单位, 段则是信息的逻辑单位
2. 页的大小固定且由系统决定, 而段的长度却不固定;
3. 分页的作业地址空间是一维的, 即单一的线性地址空间, 分段的作业地址空间则是二维的

3.5.3 信息共享

分段管理的优缺点

• 优点:
  • 便于动态申请内存
  • 管理和使用统一化
  • 便于共享
  • 便于动态链接
• 缺点:
  • 产生碎片

3.6 段页存储管理

1. 产生背景: 结合了段式与页式二者优点, 克服了二者的缺点

2. 基本思想

用户程序划分: 按段式划分 (对用户来讲, 按段的逻辑关系进行划分; 对系统讲, 按页划分每一段)

内存划分: 按页式存储管理方案
内存分配: 以页为单位进行分配

3. 管理

1. 段表: 记录了每一段的页表始址和页表长度
2. 页表: 记录了逻辑页号与内存块号的对应关系(每一段有一个, 一个程序可能有多个页表)
3. 空间管理: 同页式管理
4. 分配: 同业式管理

4. 地址空间和地址结构

一个程序首先被划分成若干程序段, 每一段给予不同的分段标识符然后, 对每一分段又分成若干个固定大小的页面. 系统中的一个作业的地址空间结构页面尺寸为 4 K 字节, 该作业有三个分段, 第一段为 15K 字节, 占 4 页, 最后一页只有 1K 未用; 其他段同理. 未足一页大小的补为一页.

5.地址映射

6. 地址变换

• 从控制寄存器读取段表始址, 找到段表;
• 段号 $\times$ 段描述子大小 + 段表始址, 得到段描述子地址
• 从段描述子读取页表始址, 找到页表
• 页号 $\times$ 页描述子大小 + 页表始址, 得到页描述子地址
• 从页描述子读取物理块号;
• 物理快号 $\times$ 物理块大小 + 页内位移量, 得到物理地址

上述的地址变换要访问主存三次, 这将执行程序的速度大大降低, 为了解决上述问题, 可以采取"快表"技术

3.7 交换与覆盖

1. 交换技术与覆盖拘束

• 在多道环境下扩充内存的方法, 用以解决在较小的存储空间中运行较大程序时遇到的矛盾
• 覆盖技术主要用在早起的操作系统中
• 交换技术被广泛用于小型分时系统中, 交换技术的发展导致了虚存技术的出现

2. 交换与覆盖异同点

• 共同点:
  • 进程的程序和数据主要放在外存, 当需要执行的部分放在内存, 内外之间进行信息交换
• 不同点: 如何控制交换

3. 覆盖技术

• 把程序划分为若干个功能上独立的程序段, 按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域
• 程序段先保存在磁盘上, 当有关程序段的前一部分执行结束, 把后续程序段的前一部分执行结束, 把后续程序段调入内存, 覆盖前面的程序段(内存 “扩大” 了)
• 覆盖: 一个作业的若干程序段, 或几个作业的某些部分共享一个存储空间
• 一般要求作业各模块之间有明确的调用结构, 程序员要想系统指明覆盖结构,然后由操作系统完成自动覆盖

4. 覆盖技术的缺点

• 对用户不透明, 增加了用户负担
• 目前这一技术用于小型系统中的系统程序的内存管理上
• MS-DOS 的启动过程中, 多次使用覆盖技术, 启动之后, 用户程序区TPA的高端部分与COMMAND.COM 暂驻模块也是一种覆盖结构

5. 交换技术

当内存空间紧张时, 系统将内存中某些进程暂时移到外存, 把外存中某些进程换进内存, 占据前者所占用的区域, 这种技术是进程在内存于外存之间的动态调度. 多用于分时系统中

6. 交换机技术实现中的几个问题

1. 选择原则: 将哪个进程换出/内存
2. 交换时机的确定
3. 交换时需要做哪些工作?
4. 换入回内存时位置的确定

7. 选择原则

• 将哪个进程换出/内存?
• 例子: 分时系统, 时间片轮转发或基于优先数的调度算法, 在选择换出进程时, 要确定换出的进程是要长时间等待的
• 需要特殊考虑的是: 任何等待 IO 进程中存在的问题
• 解决: 从不换出处于等待 IO 状态的进程有些 IO 进程因 DMA 而不能换出内存或换出前需要操作系统的特殊帮助

8. 交换时机的确定

何时需发生交换?

例子:

• 只要不用就换出 (很少再用)
• 只在内存空间不够或有不够的危险时换出

9. 交换是需要做哪些工作

需要一个盘交换区: 必须足够大一存放所有用户程序的所有内存映象的拷贝; 必须对这些内存映象的直接存取

10. 换入回内存时位置的确定

• 换出后再换入的内存位置一定要在换出前的原来位置上吗?
• 受地址 “绑定” 技术的影响, 即绝对地址产生时机的限制

11. 覆盖与交换的比较

• 与覆盖技术相比, 交换技术不仅要求用户给程序之间的逻辑覆盖结构;而且, 交换机发生在进程或作业之间;
• 而覆盖发生在同一进程或作业内, 此外, 覆盖只能覆盖那些与覆盖端无关的程序段

3.8 虚拟存储器

1. 概述

问题的提出:

• 程序大于内存
• 程序暂时不执行或运行完是否还要占用内存

虚拟存储器的基本思想是: 程序, 数据, 堆栈的大小可以超过内存的大小, 操作系统把程序当前使用的部分保留在内存, 而把其它部分保存在磁盘上, 并在需要时在内存和磁盘之间动态交换

虚拟存储器支持多到程序设计技术

2. 局部性原理

程序局部性原理

在一段时间内一个程序的执行往往呈现出高度的局部