# 背景

存储层次结构
寄存器 (register)
快速缓存 (cache)
主存 (primary memory)
外存 (secondary memory)

• 程序必需放入内存并放入一个进程才能被执行
• 输入队列 — 磁盘上等待进入内存并执行的进程的集合
• 用户程序在执行之前必需经历很多步骤
• 指令和数据绑定到内存地址可以在三个不同的阶段发生。
  • Compile time（编译时期）如果内存位置已知，可生成绝对代码；如果开始位置改变，需要重新编译代码
  • Load time（装入时期）如果存储位置在编译时不知道，则必须生成可重定位代码
  • Execution time（执行时期）如果进程在执行时可以在内存中移动，则地址绑定要延迟到运行时。需要硬件对地址映射的支持，例如基址和限长寄存器

# 逻辑与物理地址

• 重定位
• 逻辑地址空间的概念同物理地址空间相关联，它是正确内存管理的中心。
  • 逻辑地址 — 由 CPU 产生；也叫做虚拟空间。
  • 物理地址 — 内存设备所读入的地址
• 在编译时期和装入时期的地址绑定策略生成的逻辑地址和物理地址是相同的，而在执行时的地址绑定策略是不同的。

# 地址重定位

• 将程序装入到与其地址空间不一致的物理空间，所引起的一系列地址变换过程。
• 静态地址重定位：在装入一个作业时，把作业中的指令地址全部转换为绝对地址，在作业执行过程中就无须再进行地址转换工作。
• 动态地址重定位：动态地址重地位是在程序执行过程中，在 CPU 访问内存之前，将要访问的程序或数据地址转换成内存地址。动态重定位依靠硬件地址变换机构完成。

# Memory-Management Unit (MMU)

• 硬件把虚拟地址映射到物理地址
• 在 MMU 策略中，基址寄存器中的值被加入到用户进程所产生的每个地址中，在其送入内存的时候。
• 用户程序所对应到的是逻辑地址，物理地址对它从来都不可见。

# 动态加载

• 例程在调用之前并不加载）
• 更好的内存空间利用率；没有被使用的例程不被载入。
• 当需要大量的代码来处理不经常发生的事情时是非常有用的。
• 不需要操作系统的特别支持，通过程序设计实现

# 动态链接

• 链接被推迟到执行时期
• 小的代码片 - 存根，用来定位合适的保留在内存中的库程序。
• 存根用例程地址来替换自己，以及执行例程。
• 操作系统需要检查例程是否在进程的内存空间

# 覆盖

• 只是在内存中保留那些在特定时间所需要的指令和数据
• 当进程比所分配的内存大时，覆盖是必需的
• 由用户执行，不需要操作系统的特别支持，覆盖结构的程序设计很复杂。
• 要求用户清楚地了解程序的结构，并指定各程序段调入内存的先后次序，它是一种早期的主存扩充的方式

# 交换

• 一个进程可以暂时被交换到内存外的一个备份区，随后可以被换回内存继续执行。
• 备份区 — 是一个固定的足够大的可以容纳所有用户内存映像的拷贝；可以提供对这些内存映像的直接存取。
• 由操作系统控制，利用外存空间（进程交换区），通过对进程实体的整体交换，来满足用户进程的内存需要。它的主要特点是打破了进程运行的驻留性
• 滚入，滚出 — 交换由于基于优先级的算法而不同，低优先级的进程被换出，这样高优先级的进程可以被装入和执行。
• 交换时间的主要部分是转移时间，总的转移时间直接同交换的内存的数量成比例。
• 在许多系统如：UNIX，Windows 中，可以找到一些被修正过的交换措施。

# 存储管理方式

• 连续分配方式：为一个程序分配一段连续的内存空间，主要有：
  • 单一连续区管理方式；
  • 多分区管理方式，是一种可用于多道程序的较简单的存储管理方式，又分为:
    • 固定分区方式
    • 可变分区方式

# 连续分配

• 主存通常被分为两部分
  • 为操作系统保留的部分，通常用中断矢量保存在内存低端。(数值小的那一端)
  • 用户进程保存在内存高端。
• 单独分区分配）
• 用户区只能容纳一道作业
  • 基址寄存器策略 (Relocation-register scheme) 由来保护用户进程（同其他进程和改变的操作系统代码和数据分开。）
  • 基址寄存器包含最小物理地址的值；限长寄存器包含逻辑地址的范围，每个逻辑地址必需比限长寄存器的值小。

# 固定分区 (Fixed Partitioning) 分配

• 固定式分区是在作业装入之前，内存就被划分成若干个固定大小的连续分区。
• 划分工作可以由系统管理员完成，也可以由操作系统实现。
• 一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。
• 划分分区的方法如下：
  • 分区大小相等：只适用于多个相同程序的并发执行（处理多个类型相同的对象），缺乏灵活性。
  • 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。
• 一般将内存的用户区域划分成大小不等的分区，可适应不同大小的作业的需要
• 系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志

区号	大小	起址	标志
1	16K	20K	已分配
2	32K	26K	未分配

• 优点：易于实现，开销小。
• 缺点：
  分区大小固定：内碎片
  分区总数固定：限制并发执行的进程数目。
  采用的数据结构：分区表－－记录分区的大小和使用情况

# 多分区分配

分区的划分是动态的，不是预先确定的

• 分区 — 可用的内存块，不同大小的分区分布在整个内存中。
• 当一个进程到来的时候，它将从一个足够容纳它分区中分配内存。
• 操作系统包含以下信息:a) allocated partitions （分配的分区） b) free partitions (hole)（空的分区）

# 可变分区分配

• 分区分配算法：寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为 “占用”，而另一个分区为余下部分并标记为 “空闲”。分区的先后次序通常是从内存低端到高端。
• 分区释放算法：需要将相邻的空闲分区合并成一个空闲分区。(这时要解决的问题是：合并条件的判断

# First-fit（首先适应）: 分配最先找到的合适的分区。

• 从空闲分区表的第一个表目开始查找，把找到的第一个满足要求的空闲区分配给作业，目的在于减少查找时间。通常将空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。
• 特点：
  • 分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。
  • 随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。
  • 在系统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称为外碎片。虽然可能所有碎片的总和超过某一个作业的要求，但是由于不连续而无法分配。

# Best-fit（最佳适应）: 搜索整个序列，找到适合条件的最小的分区进行分配。

• 从全部空闲区中找出能满足作业要求的、且最小的空闲分区.
• 能使碎片尽量小
• 为提高查找效率，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配
• 特点：
  从个别来看，外碎片较小，但从整体来看，会形成较多无法利用的碎片。
  较大的空闲分区可以被保留。

# Worst-fit（最差适应）: 搜索整个序列，寻找最大的分区进行分配。

在速度和存储的利用上，首先适应和最佳适应要比最差适应好。

# 碎片

• 可变式分区的碎片问题：在系统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称为外碎片。虽然可能所有碎片的总和超过某一个作业的要求，但是由于不连续而无法分配。

• 解决碎片的方法是拼接（或称紧凑），即向一个方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。

• 分区的拼接技术，一方面要求能够对作业进行动态重定位，另一方面系统在拼接时要耗费较多的时间。

• External fragmentation（外碎片）整个内存空间用来满足一个请求，但它不是连续的。

• Internal fragmentation（内碎片）分配的内存可能比申请的内存大一点，这两者之间的差别是内部不被使用的簇

• Reduce external fragmentation by compaction（通过紧缩来减少外碎片）把一些小的空闲内存结合成一个大的块。

  • 只有重定位是动态的时候，才有可能进行紧缩，紧缩在执行时期进行
  • I/O 问题
    • 当 I/O 的时候，把工作锁定在内存中。
    • 只对操作系统的缓冲区进行 I/O。

• 动态重定位是解决存储碎片问题的一种途径，但要移动大量信息从而浪费处理机时间，代价比较高，且 必须获得硬件支持。

• 只有具有动态重定位硬件机构的计算机系统，才有可能采用动态重定位可变分区管理技术，

# 分页

• 进程的逻辑地址空间可以是不连续的，如果有可用的物理内存，它将分给进程。
• 把物理内存分成大小固定的块。
• 把逻辑内存也分为固定大小的块，叫做页。
• 保留所有空闲帧的记录。
• 运行一个有 N 页大小的程序，需要找到 N 个空的页框读入程序。
• 建立一个页表，把逻辑地址转换为物理地址。
• 内碎片。

# 地址转换模式

CPU 产生的地址被分为:

• Page number § （页号）它包含每个页在物理内存中的基址，用来作为页表的索引。
• Page offset (d) （偏移）同基址相结合，用来确定送入内存设备的物理内存地址。
• For given logical address space 2m and page size 2n

# 页表

• 页表被保存在主存中
• 页表基址寄存器指向页表
• 页表限长寄存器表明页表的长度
• 在这个机制中，每一次的数据 / 指令存取需要两次内存存取，一次是存取页表，一次是存取数据
  translation look-aside buffers (TLBs). 通过一个联想寄存器，可以解决两次存取的问题

# 有效存取时间

联想寄存器的查找需要时间
假设内存一次存取要 1 微秒
命中率 — 在联想寄存器中找到页号的比率，比率与联想寄存器的大小有关。
Hit ratio = α
Effective Access Time (EAT)（有效存取时间）
$EAT = (1 + \epsilon)\alpha + (2 + \epsilon)(1 – \alpha)= 2 + \epsilon –\alpha$

例如，假设检索联想存储器的时间为 20ns，访问内存的时间为 100ns，访问联想存储器的命中率为 85%，则 CPU 存取一个数据的平均时间:

$T=0.85*120+0.15*220=135ns$
访问时间只增加 35%。如果不引入联想存储器，其访问将延长一倍（达 200ns）。

# 地址变换机构

• 实现从逻辑地址到物理地址的转换：将用户程序中的页号变换成内存中的物理块号
• 地址变换机构：
  页表寄存器
  有效地址寄存器（逻辑地址寄存器）
  物理地址寄存器
  页表
  PCB 中增加存放页表始址和页表长度的项

# 地址变换过程

按页的大小分离出页号和位移量，放入有效地址寄存器中
将页号与页表长度进行比较，如果页号大于页表长度，越界中断；
以页号为索引查找页表：将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号；
将该物理块号装入物理地址寄存器的高址部分；
将有效地址寄存器中的位移量直接复制到物理地址寄存器的低位部分，从而形成内存地址。

# 页式地址变换

• 虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出
  将虚地址转换成二进制的数；
  按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；
  将位移量直接复制到内存地址寄存器的低位部分；
  以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。
• 虚地址以十进制数给出
  页号＝虚地址％页大小
  位移量＝虚地址 mod 页大小
• 以页号查页表，得到对应页装入内存的块号
• 内存地址＝块号 × 页大小＋位移量

# 内存保护

• 内存的保护由与每个页框相连的保护位来执行。
• 有效 - 无效位附在页表的每个表项中
  • “有效” 表明相关的页在进程的逻辑地址空间，以及是一个合法的页。
  • “无效” 表明页不在进程的逻辑地址空间中。

# 两级页表机制

• 将页表进行分页。每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块中，为此再建立一张页表，称为外层页表（页表目录），即第一级页表，其中的每个表目是存放某个页表的物理地址。第二级才是页表（其中每个物理块上的页表叫做页表分页），其中的每个表目所存放的才是页的物理块号。
• A logical address (on 32-bit machine with 4K page size) is divided into（一个逻辑地址被分为）:
  a page number consisting of 20 bits.（一个 20 位的页号。）
  a page offset consisting of 12 bits.（一个 12 位的偏移。）
• Since the page table is paged, the page number is further divided into（页表页被分为）:
  a 10-bit page number. （一个 10 位的页号。）
  a 10-bit page offset.（一个 10 位的偏移。）
  Thus, a logical address is as follows（因此，一个逻辑地址表示如下）:where pi is an index into the outer page table, and p2 is the displacement within the page of the outer page table.

page number		page offset
p1	p2	d
10	10	12

# 多级页表

• 由于每一级都分开的以表的形式存储在内存中，把一个逻辑地址转换为一个物理地址可能要进行 4 次内存存取。
• 多级页表的引入，使逻辑地址到物理地址的变换时间增加了许多：二级页表需三次访存，三级页表需四次访存，四级页表需五次访存
• 尽管每次内存存取的时间是很大的，高速缓存使执行的时间还是可以接受的。
• 如果缓存的命中率有 98%）则
  effective access time = 0.98 x 120 + 0.02 x 520
  = 128 nanoseconds.which is only a 28 percent slowdown in memory access time.（这只把内存存取时间降低了 28%。）

# 哈希页表

• 在 大于 32 位地址空间中常见
• 虚拟页码散列到页表中
  此页表包含散列到同一位置的元素链
• 在此链中比较虚拟页码以搜索匹配项
  如果找到匹配项，则提取相应的物理帧

# 倒置页表

通常的页表为每个进程设置一张页表，其不足之处是浪费内存空间
解决：倒置页表，按照整个物理内存建造一张表

• 内存中的每一块在表中占一项。
• 每项包含存储在物理内存的进程的逻辑页号和进程标示。
• 减少了页表占用的内存空间量，但是增加了查找表的时间，因为页表是按物理块的顺序组织的，而查找是按虚地址进行的。
• 使用哈希表来减少搜索。

# 共享页表

• 共享代码）
  一个只读（可再入）代码可由进程共享。
  共享代码出现在所有进程的逻辑地址空间的相同位置。
• 私有代码和数据
  每个进程保留一个代码和数据的私有拷贝。
  私有代码和数据的页可以出现在逻辑地址空间的任何地方。

# 纯分页的特点

没有外碎片，每个内碎片不超过页大小。
一个程序不必连续存放。
程序全部装入内存。

# 分段

• 内存管理机制支持用户观点的内存。
• 一个程序是一些段的集合，一个段是一个逻辑单位

# 分段结构

• 一个逻辑地址是两个向量的集合:
  <segment-number, offset>,
• 段表 - 映射二维物理地址，每个表项包括
  base– 基址 - 包括内存中段物理地址的起始地址。
  limit 限长 - 指定段的长度。
• 段表基址寄存器指向段表在内存中的地址。
• 段表限长寄存器表明被一个程序所使用的段的数目。
• Relocation.（重定位）
  dynamic（动态）
  by segment table （由段表来执行）
• Sharing.（共享）
  shared segments（共享的段）
  same segment number （同样的段号）
• Allocation.（分配）
  first fit/best fit（首先 / 最佳适配）
  external fragmentation（外碎片）
• 保护，每个段表的表项有:
  validation bit 有效位
  read/write/execute privileges（读 / 写 / 执行权利）
• 保护位同段相联系，在段的级别进行代码共享。
• 由于段的各个长度不同，内存分配是一个动态存储 - 分配问题。

# 地址变换过程

• 系统将逻辑地址中的段号 S 与段表长度 TL 进行比较。若 S≥TL，访问越界；
• 若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址；
• 然后再检查段内地址 d 是否超过该段的段长 SL。若超过，即 d≥SL，同样发出越界中断信号；
• 若未越界，则将该段的基址与段内地址 d 相加，得到要访问的内存物理地址。

# 分段的特点

• 程序通过分段 (segmentation) 划分为多个模块，如代码段、数据段、共享段。
  可以分别编写和编译
  可以针对不同类型的段采取不同的保护
  可以按段为单位来进行共享，包括通过动态链接进行代码共享
• 特点：
  没有内碎片，外碎片可以通过内存紧缩来消除。
  便于改变进程占用空间的大小。
  进程全部装入内存。

# 分段和分页比较

分页	分段
目的	为了提高内存的利用率	为了能更好地满足用户的需要
页 / 段单位划分	页是信息、的物理单位，页的大小是固定的，而且由系统确定	段是信息、的逻辑单位，它含有一组意义相对完整的信息。段的长度是不固定的，取决于用户所编写的程序﹐并由编译程序来划分。
作业地址空间	单一的线性地址空间	二维的，标识一个地址需给出段名和段内地址
内存分配	以页为单位离散分配，无外碎片，所以也无紧缩问题	以段为单位离散分配﹐类同可变分区，会产生许多分散的小自由分区 — 一外碎片，造成主存利用率低﹐需采用紧缩解决碎片问题，但紧缩需花费机时

# 段页式

• 分页和分段存储管理方式都各有其优缺点。如果对两种存储管理方式 “各取所长” 后，则可以形成一种新的存储管理方式的系统 —— 段页式系统。

• 既具有分页系统能有效地提高内存利用率的优点，又具有分段系统能很好地满足用户需要的长处，是一种有效的存储管理方式。

• 基本原理
  将整个主存划分成大小相等的物理块（页框）
  把用户程序按程序的逻辑关系分为若干个段，并为每个段赋予一个段名
  把每个段划分成若干页，以页框为单位离散分配。
  地址结构由段号、段内页号和页内地址三部分组成
  段号（S）| 段内页号（P） | 页内地址（W）

• 为了实现从逻辑地址到物理地址的变换，系统中需同时配置段表和页表。

• 由于将段中的页进行离散地分配，段表中的内容不再是段的内存始址和段长，而是页表始址和页表长度。
  | 段号 | 页表 长度 | 页表始址

# 地址转换

• 在段页式系统中，有一个段表寄存器，存放段表始址和段长 TL。
• 地址变换
  将段号 S 与段长 TL 进行比较
  若 S＜TL，表示未越界，于是利用段表始址和段号求出该段对应的段表项在段表中的位置，从中得到该段的页表始址与页表长度
  将逻辑地址中的段内页号 P 与页表长度 PL 进行比较：若 P＜PL，则用页号来获得对应页的页表项位置，从中读出该页所在的物理块号 b
  用块号 b 和页内地址构成物理地址
• 在段页式系统中，为了获取一条指令或数据，需三次访问内存。
  第一次是访问内存中的段表，从中取得页表始址
  第二次是访问内存中的页表，从中取得物理块号，并将该块号与页内地址一起形成物理地址
  第三次才是真正从第二次访问所得到的物理地址中，取得指令或数据。