计算机与操作系统-03-存储管理

本文主要内容来自 SpriCoder的博客，更换了更清晰的图片并对原文的疏漏做了补充和修正。

1. 存储管理是操作系统的重要组成部分，负责管理计算机系统的重要资源——内存储器。
2. 内存空间一般分为两部分：
   1. 系统区：存放操作系统内核程序和数据结构等。
   2. 用户区：存放应用程序和数据。
3. 存储管理包括以下功能：
   1. 存储分配：位进程分配内存空间以便运行，完成内存区的分配和去配工作。
   2. 地址映射：内存被抽象为一维或二维地址空间；逻辑空间到物理空间映射。
   3. 存储保护：系统隔离分配给进程的内存区，防止地址越界或操作越权。
   4. 存储共享：系统允许多个进程共享内存区。
   5. 存储扩充：形成虚拟存储器。

存储管理的基础

逻辑地址

1. 逻辑地址：又称相对地址，即用户编程所使用的地址空间
2. 逻辑地址从零开始编号，有两种形式：
   1. 一维逻辑地址（地址）
   2. 二维逻辑地址（段号：段内地址）

段式程序设计

1. 把一个程序设计成多个段：代码段、数据段、堆栈段等等
2. 用户可以自己应用段覆盖技术扩充内存空间使用量，这一技术是程序设计技术，不是 OS 存储管理的功能：只是用一些段构成一个比较小的程序，然后动态来调整。
3. 结合虚存完成内存部分的扩充

物理地址

从处理器角度看到的物理内存单元

1. 物理地址：又称绝对地址，即程序执行所使用的地址空间
2. 处理器执行指令时按照物理地址进行

主存储器的复用

1. 多道程序设计需要复用主存
2. 按照分区复用：
   1. 主存划分为多个固定/可变尺寸的分区
   2. 一个程序/程序段占用一个分区
3. 按照页架复用：
   1. 主存划分成多个固定大小的页架
   2. 一个程序/程序段占用多个页架

存储管理的基本模式

1. 单连续存储管理：一维逻辑地址空间的程序占用一个主存固定分区或可变分区
2. 段式存储管理：段式二维逻辑地址空间的程序占用多个主存可变分区
3. 页式存储管理：一维逻辑地址空间的程序占用多个主存页架区
4. 段页式存储管理：段式二维逻辑地址空间的程序占用多个主存页架区
5. 注意是否可以虚拟化

存储管理模式示意图

1. 应用级程序员直接面对的是逻辑地址，而最后运行需要使用的是物理地址（从处理器角度看到的物理内存单元）
2. 一般目前常用的是动态重定位，将逻辑地址转换为对应的物理地址。
3. 分页：形成页框加载程序，页框和页框之间可以是不连续的。
4. 分段：每一个段有相应分区，使用段表完成逻辑段向物理段的映射
5. 段页式：在分段基础上，还实现了页框部分。

存储管理的功能

地址转换

地址转换：又称重定位，即把逻辑地址转换成绝对地址。

1. 静态重定位：在程序装入内存时进行地址转换，将逻辑地址转换为物理地址，再装入内存；由装入程序执行，早期小型 OS 使用，基于地址固定值进行偏移。
2. 动态重定位（主流）：在 CPU 执行程序时进行地址转换，将逻辑地址转换为物理地址；从效率出发，依赖硬件地址转换机构，运行时正确的将其逻辑地址转换为物理地址。

解释执行指令的时候才进行地址的转换，必须要借助硬件电路完成，而不能用软件完成（效率考量）

能够装入内存任何位置（都能够正确运行）的代码程序必须是可动态链接的。

能够装入内存任何位置的代码是指地址无关代码（position-independent code，PIC），又称地址无关可执行文件（position-independent executable，PIE），它可以在主存储器中任意位置正确地运行，而不受其绝对地址影响的一种机器码。PIC 本身是动态链接的产物。

以下内容来自 chatGPT：

一个程序需要在计算机上运行时，其代码和数据必须被装载到内存中。在操作系统中，内存被分成许多不同的区域，每个区域都有其特定的用途。如果一个程序的代码可以被装载到内存的任何位置，那么它必须能够在不同的内存地址中正确地执行。

动态链接是一种在程序运行时将不同的模块或库文件链接到程序中的方式。这些模块或库文件包含程序所需的函数和数据，但是它们并不是在程序编译时直接嵌入到程序中的。因此，当程序运行时，操作系统将会根据需要将这些模块或库文件加载到程序的内存中。这就使得程序的代码可以被装载到内存的任何位置，因为程序在运行时能够正确地找到并使用链接的模块或库文件中的函数和数据。

如果一个程序不能被动态链接，那么它必须在编译时将所有的函数和数据嵌入到程序中，这就意味着程序的代码必须被装载到特定的内存位置才能正确地执行。这会导致代码的可移植性降低，因为它只能在特定的内存地址中运行。而动态链接则可以提高代码的可移植性，因为它可以允许程序在不同的内存地址中正确地执行。

主存储器空间的分配与去配

1. 分配：进程装入主存时，存储管理软件进行具体的主存分配操作，并设置一个表格记录主存空间的分配情况
2. 去配：当某个进程撤离或主动归还主存资源时，存储管理软件要收回它所占用的全部或者部分存储空间，调整主存分配表信息

主存储器空间的共享

1. 多个进程共享主存储器资源：多道程序设计技术使若干个程序同时进入主存储器，各自占用一定数量的存储空间，共同使用一个主存储器
2. 多个进程共享主存储器的某些区域：若干个协作进程有共同的主存程序块或者主存数据块

存储保护

为避免主存中的多个进程相互干扰，必须对主存中的程序和数据进行保护：

1. 私有主存区中的信息：可读可写
2. 公共区中的共享信息：根据授权
3. 非本进程信息：不可读写

这一功能需要软硬件协同完成：CPU 检查是否允许访问，不允许则产生地址保护异常，由 OS 进行相应处理：

1. 地址越界保护依赖于硬件设施、常用的有界地址和存储键。
2. 进程在访问分配给自己的内存区时，要对访问权限进行检查

主存储器空间的扩充

存储扩充：把磁盘作为主存扩充，只把部分进程或进程的部分内容装入内存：扩大多道程序设计的道数

1. 对换技术：把部分不运行的进程调出
2. 虚拟技术：只调入进程的部分内容，对单个进程不使用对换技术完成，特点是自动化、透明

这一工作需要软硬件协作完成：

1. 对换进程决定对换，硬件结构完成调入
2. CPU 处理到不在主存的地址，发出虚拟地址异常，OS 将其调入，重执指令

进程的内存为 4MB，一个页框 4KB，有 1024 个页框，页框表一共 16 个页框，页的压缩比是\(\frac{1024}{16} = 64\)。

虚拟存储器的概念

之前所介绍的存储管理，我们称为实存管理，必须为进程分配足够内存空间，装入其全部信息，否则无法运行。

虚拟存储器思想的提出

主存容量限制带来诸多不便：

1. 用户编写程序必须考虑主存容量限制
2. 多道程序设计的道数受到限制

用户编程行为分析：

1. 全面考虑各种情况，执行时有互斥性
2. 顺序性和循环性等空间局部性行为
3. 某一阶段执行的时间局部性行为

因此可以考虑部分调入进程内容

分区存储的限制 *

1. 每个进程（每个连续逻辑地址空间）必须获得物理地址上的完全连续，突破：分区，分段
2. 必须一次性满足满足每个进程运行时的全部内存需求，突破：虚拟存储，部分装入对换
3. 注：一旦发生缺页，则会从运行态调整到阻塞态，可能会导致部分进程的速度被拖慢，但是整体效率会提高

程序运行的局部性原理 *

在一个周期内，这个进程在运行时会集中访问一些存储区：某存储单元被访问，该单元机器相邻存储单元很可能会被访问（空间局部性），或者最近访问过的存储单元很快又能被访问（时间局部性）。

根据程序运行的局部性原理，会保证程序的访问效率比较高，缺页率相对低，以时间换取空间

虚拟存储器的基本思想

1. 部分装入：存储管理把进程全部信息放在辅存中，执行时先将其中一部分装入主存，以后根据执行行为随用随调入
2. 按需调出：如主存中没有足够的空闲空间，存储管理需要根据执行行为把主存中暂时不用的信息调出到辅存上去

虚拟存储器的实现思路

需要建立与自动管理两个地址空间：

1. （辅存）虚拟地址空间：容纳进程装入
2. （主存）实际地址空间：承载进程执行

对于用户，计算机系统具有一个容量大得多的主存空间，即虚拟存储器

虚拟存储器

在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理内存容量大得多的、可寻址的内存储器。

虚拟存储器是一种地址空间扩展技术，通常意义上对用户编程是透明的，除非用户需要进行高性能的程序设计。

1. 逻辑地址：进程角度看到的逻辑内存单元。
2. 物理地址：从处理器角度看到的物理内存单元。

对换技术和虚存管理的区别：对换技术以进程为单位，虚存管理以页或段为单位。

存储管理的硬件支撑

存储器的组织层次

越处于顶端，访问速度越快，容量越小，单位字节价格会越高。我们根据实际情况，选择使用什么样子的存储器。

1. 寄存器、缓存和内存属于操作系统存储管理的范畴，掉电后信息丢失。
2. 磁盘和磁带属于稳健管理和设备管理的管辖对象，信息永久保存。

可执行程序必须被保存在内存中，与设备交换的信息也依托于内存地址空间。

由于程序处理数据时存在顺序性和局部性，故执行时仅需调入当前运行使用的一部分，其他部分待需要时再逐步调入。

存储管理涉及的存储对象

1. 存储管理是 OS 管理主存储器的软件部分
2. 为获得更好的处理性能，部分主存程序与数据（特别是关键性能数据）被调入 Cache，存储管理需要对其进行管理，甚至包括对联想存储器的管理
3. 为获得更大的虚拟地址空间，存储管理需要对存放在硬盘、固态硬盘、甚至网络硬盘上的虚拟存储器文件进行管理，首选固态硬盘

高速缓存存储器（Cache）

1. Cache 是介于 CPU 和主存储器间的高速小容量存储器，由静态存储芯片 SRAM组成，容量较小但比主存 DRAM 技术更加昂贵而快速，接近于 CPU 的速度
2. CPU 往往需要重复读取同样的数据块，Cache 的引入与缓存容量的增大，可以大幅提升 CPU 内部读取数据的命中率，从而提高系统性能

高速缓存存储器的构成

高速缓冲存储器通常由高速存储器、联想存储器、地址转换部件、替换逻辑等组成

1. 联想存储器：根据内容进行寻址的存储器
2. 地址转换部件：通过联想存储器建立目录表以实现快速地址转换。命中时直接访问 Cache；未命中时从内存读取放入 Cache
3. 替换逻辑部件：在缓存已满时按一定策略进行数据块替换，并修改地址转换部件

MMU：硬件，存储管理单元

高速缓存存储器的组织

1. 由于 CPU 芯片面积和成本，Cache 很小
2. 根据成本控制，划分为 L1、L2、L3 三级

高速缓存存储器的分级

1. L1 Cache：分为数据缓存和指令缓存；内置；其成本最高，对 CPU 的性能影响最大；通常在 32KB-256KB 之间
2. L2 Cache：分内置和外置两种，后者性能低一些；通常在 512KB-8MB 之间
3. L3 Cache：多为外置，在游戏和服务器领域有效；但对很多应用来说，总线改善比设置 L3 更加有利于提升系统性能

早期奔腾处理器架构 *

Intel 在最初的奔腾处理器中只包含 L1 Cache（含 Code Cache 和 Data Cache）

奔腾 4 处理器架构 *

奔腾 4 的处理器中包含 L1 Cache 和 L2 Cache

i5 处理器架构 *

i7 处理器架构 *

i7 处理器中包含 L1 至 L3 三级 Cache，如果是包含了三级 Cache，那么意味着 CPU 与 Cache 之间的链接在 CPU 内部，Core i7 处理器方案是将 L3 Cache 设计为包含在处理中的多个核心 Cache

地址转换/存储保护的硬件支撑

1. 限长寄存器来检查越界中断
2. 相加体现了动态重定位
3. 比较体现了存储保护

存储管理与硬件支撑

1. 鉴于程序执行与数据访问的局部性原理，存储管理软件使用Cache可以大幅度提升程序执行效率
2. 动态重定位、存储保护等，若无硬件支撑在效率上是无意义的，即无实现价值
3. 无虚拟地址中断，虚拟存储器无法实现
4. 无页面替换等硬件支撑机制，虚拟存储器在效率上是无意义的

虚拟存储与硬件支撑 *

1. 操作系统的存储管理依靠底层硬件支撑来完成任务，该硬件是存储管理部件（Memory Managment Unit， MMU），提供地址转换和存储保护并支持虚存管理和多任务管理。
2. MMU 由一组集成电路芯片组成，逻辑地址作为输入，物理地址作为输出，直接送达总线，对内存单元进行寻址。

主要功能：P217

1. 管理硬件页表基址寄存器
2. 分解逻辑地址
3. 管理快表
4. 访问页表
5. 发出异常
6. 管理特征位

连续存储管理

单连续分区存储管理

1. 每个进程占用一个物理上完全连续的存储空间（区域）
2. 单连续分区存储管理细分：
   1. 单用户连续存储管理
   2. 固定分区存储管理
   3. 可变分区存储管理
3. 分区方式不能实现虚拟存储。

单用户连续分区存储管理

1. 适用于单用户单任务操作系统，如 DOS
2. 主存区域（内存空间）划分为系统区与用户区
   • 系统区用于存放操作系统内核程序和数据结构等
   • 用户区用于存放应用程序和数据
3. 设置一个栅栏寄存器界分两个区域，硬件用它在执行时进行存储保护
4. 一般采用静态重定位进行地址转换
5. 硬件实现代价低

单用户连续分区存储管理示意

静态重定位：在装入一个作业时，把该作业中程序的指令地址和数据地址全部转换成绝对地址

界限地址：放置软件访问到操作系统的部分

固定分区存储管理

固定分区存储管理又称静态分区模式。

固定分区方式的基本思想

内存空间被划分为数目固定不变的分区，各分区大小不等，每个分区只装入一个作业，若多个分区中都装有作业，则它们都可以并发执行。

1. 支持多个分区
2. 分区数量固定
3. 分区大小固定
4. 可用静态重定位
5. 硬件实现代价低
6. 早期 OS 采用

固定分区方式的主存分配

1. 主存分配表：包含起始地址、长度、占用标志
2. 内存分配方法很简单，其任务有何时把内存空间划分成分区：由系统管理员和操作系统初始化模块协同完成。

作业进入分区的排队策略：

1. 每个分区有自己的作业等待队列，作业等待能装下自身的最小分区。
2. 所有等待处理作业排成等待队列，每当有空闲，找到队列中能进入的最大的一个。

固定分区方式的地址转换

固定分区存储管理的缺点

1. 由于预先规定了分区的大小，使得大作业无法装入，而不得不采用覆盖技术，带来负担。
2. 内存空间利用率不高，作业很少填满分区：固定分区存储管理不够灵活，既不适应大尺寸程序，又存在内存内零头，有浪费。内存内零头是因为在分区内部有零头。
3. 如果作业在运行中要求动态扩展内存空间是困难的。
4. 分区数目是操作系统初启动时确定的，会限制多道运行程序的道数。

可变分区存储管理

可变分区存储管理又称动态分区模式，按照作业大小划分分区，但划分的时间、大小和位置都是动态的。

创建一个进程时，根据进程所需主存量查看主存中是否有足够的连续空闲空间

1. 若有，则按需要量分割一个分区
2. 若无，则令该进程等待主存资源

由于分区大小按照进程实际需要量来确定，因此分区个数是变化的

可变分区方式的内存分配示例

可变分区方式的主存分配表

管理的数据结构：已分配区表与未分配区表，采用链表实现

可变分区方式的内存回收

1. 可变分区方式的内存回收会导致内存空间的转换
2. 作业 X 撤离后有且仅有如上 4 种情况。

可变分区方式的内存分配

最常用的是最先适应分配算法，其次是邻近适应分配算法和最优适应分配算法。

最先适应分配算法

1. 最先适应就是从上向下查找，找到第一块区域放进去，将剩下的区域分割后仍作为空闲区。
2. 有利于大作业装入，但也使得内存低地址和高地址两端的分区利用不均衡，回收分区麻烦。

邻近适应分配算法

1. 从上次查找结束的地方开始执行最先适应分配算法。
2. 缩短平均查找时间，且存储空间利用率更均衡，不会使得小空闲区集中在内存一侧。

最优适应分配算法

1. 每次都是分配最接近需要使用大小的部分，会生成很多很小的内存内零头。
2. 通常会将空闲区按照长度递增顺序排列，等同于最先适应分配算法，查找时间最长。

最坏适应分配算法

1. 每次都是挑选最大的一块区域进行分配。
2. 有利于中小型作业。
3. 可把空闲区按长度递减顺序排列，等同于最先适应分配算法。

快速适应分配算法：课本补充

1. 为经常用到的长度的空闲区设立单独的空闲区链表，查找非常快速
2. 归还内存空间时和邻近空闲区的合并复杂且耗时。

地址转换与存储保护

1. 硬件实现机制与动态重定位
2. 进程的程序和数据的地址由硬件完成
   1. 基址寄存器：分配进程的起始地址
   2. 限长寄存器：进程占用的连续存储空间的长度

分区方式的内存零头

1. 固定分区方式会产生内存内零头
2. 可变分区方式也会随着进程的内存分配产生一些小的不可用的内存分区，称为内存外零头，内存外零头是指分区内部是没有零头的，而是在外面的零头。
3. 最优适配算法最容易产生外零头
4. 任何适配算法都不能避免产生外零头

内存不足的存储技术

移动技术（程序浮动技术）

1. 碎片：内存中的小空闲区，移动分区来解决内存外零头问题。
2. 当未分配区表中找不到足够大的空闲区来装入新进程时，我们使用移动技术来完成内存紧凑，实现方法：
   1. 全部移动到一侧
   2. 移动直到有足够大的空闲区
3. 需要动态重定位支撑：静态重定位无法解决内存外零头
4. 问题：移动技术有极大的系统开销，而且并不是任何时间下都可以进行的，比如通道或 DMA 等按照绝对物理地址交换信息时。

5. 移动技术的工作流程

6. 注意如果剩余空间地方不足，那么是不会移动分区的

对换技术 *

1. 对换技术广泛应用于分时系统的调度，用来解决内存容量不足的问题，也可以应用于批处理系统，以平衡系统负载。
2. 如果当前一个或多个驻留进程都处于阻塞态，此时选择其中一个进程，将其暂时移出内存，腾出空间给其他进程使用；同时把磁盘中的某个进程换入内存，让其投入运行，这种互换称为对换。
3. 被对换出去的进程的状态会调整为就绪态，并且通知存储管理程序，一旦内存可用，立即将该进程对换回内存。
4. 对换技术关键点：
   1. 被对换进程：通常系统选择时间片耗尽或优先级较低的进程对换出去。
   2. 对换的进程信息：将数据区和堆栈通过文件系统转换为特殊文件保存。
   3. 被对换的时机：
      1. 批处理系统中：进程需要扩充内存空间但不能被满足时
      2. 分时系统：
         1. 时间片结束时
         2. 执行 I/O 操作时
5. 对换需要访问磁盘，是 I/O 集中型操作，但是操作系统可以让计算型任务与对换并行，不会造成系统效率显著下降。
6. 详见 P205

覆盖技术 *

1. 移动和对换技术解决因多个程序存在而导致内存区不足问题。
2. 但是如果程序长度超过物理内存的总和，或者超出固定分区大小，则会出现内存永久性短缺，大程序无法运行，解决方案是覆盖技术。
3. 覆盖是指程序执行过程中程序的不同模块在内存中相互替代，以达到小内存执行大程序的目的。
4. 基本的实现技术是把用户空间分成固定区和一个或多个覆盖区，把控制或不可覆盖的部分放到固定区，其余按照调用结构以及先后关系分段并存放在磁盘上，运行时依次调入覆盖区。
5. 不足是将存储管理工作转给程序员，他们必须根据可用物理内存空间来设计和编写程序。

页式存储管理

页式存储管理的基本原理

页面：把逻辑地址空间分成大小相等的区，每个区称为页面或页，页号从 0 开始编号。比如出版一本书，出版受到页大小影响，最后由若干页组成，一般大小为 4KB

页框：又称页帧，把内存物理地址空间分成大小相等的区，其大小与页面大小相等，每个区都是一个页框（物理块），块号从 0 开始。

逻辑地址：分页存储器的逻辑地址由页号 + 页面偏移组成（地址总线 32 位）

1. 页号：32-12 = 20 位，则包含页 2²⁰ 位
2. 页面偏移：页面大小为 4KB，则需要 12 位

内存页框表：该表长度取决于内存划分的物理块数，表项中给出物理块使用情况，0 为空闲，1 为占用，有的系统还会添加保护位、脏位等等。

页表：将页装入到内存中，页未必连续，我们需要为每一个页面设立一个重定向寄存器，这个寄存器的集合就是页表。

1. 数学角度：页面号 \(\rightarrow\) 页框号
2. 系统设置页表基址寄存器，存放当前运行进程的页表起始地址。
3. 物理地址 = 页框号 * 块长 + 页内偏移，实际转换时，我们将页内偏移作为低地址，根据页号从页表中查找到页框号并作为高地址即可。
4. 页表不存储页号，只存储页框号和相应标志位

页式存储产生的碎片是内部碎片：

1. 可以类比固定分区
2. 比如 19KB 的程序，加载到页大小为 4KB 中，会产生 1KB 的内存内零头。

页式存储管理中的地址

页式存储管理的逻辑地址由两部分组成，页号和单元号（页内偏移），逻辑地址形式：

页式存储管理的物理地址也有两部分组成：页架号（页框号）和单元号（页内偏移），物理地址形式：

地址转换可以通过查页表完成。用户不必关心页的具体存储，系统帮助用户完成从页号/页架号映射到物理地址来完成。

页式存储管理的地址转换例子

逻辑地址页号，作为偏移量到页表中进行偏移，得到页架号（页框号）。

对页架号（页框号）进行二进制移位操作（补充 12 个 0），映射到物理空间中本页的首地址，然后根据 offset（单元号）在页内进行偏移，从而获取到绝对地址（物理地址：从处理器角度看到的物理内存单元）中的值。

页式存储管理的内存分配/去配

页式存储管理，系统要建立一张内存物理块表，用来记录页框状态，管理物理内存的而分配，所包含的信息包含内存总块数、哪些为空闲块、哪些已经分配以及分配给哪个进程等。

最简单方法是用一张位示图来记录主存分配情况，使用一位来标记一个页框的使用或空闲的状态（压缩的思想）

1. 如果够，则去查找一个标记为 0 的装入
2. 如果不够，采用一定的策略

建立进程页表维护主存逻辑完整性

分页存储管理页框分配算法：

1. 进行内存分配时，先检查空闲块数是否满足用户进行要求
   1. 若不能则使进程等待。
   2. 若能则查位示图，将位 0 置为占用标志，从空闲块数中减去本次占用块数，找到对应的页框号，写入页表。
2. 归还时逆操作。

页的共享

1. 页式存储管理能够实现多个进程共享程序和数据
2. 数据共享：不同进程可以使用不同页号共享数据页，但是必须解决共享信息保护问题，常用的是在页表中添加标记位。
3. 程序共享：不同进程必须使用相同页号共享代码页，共享代码页中的（JMP <页内地址>）指令，使用不同页号是做不到，进程一和二都要跳转到页内的位置，程序共享要求页号相同。

页式存储管理的地址转换

快表 TLB，Translation Look_aside Buffer

页式存储管理的地址转换代价

页表放在主存： 每次地址转换必须访问两次主存

1. 按页号读出页表中的相应页架号
2. 按计算出来的绝对地址进行读写

存在问题：降低了存取速度

解决办法：利用 Cache 存放部分页表，即快表

页式存储管理的快表

为提高地址转换速度，设置一个专用的高速存储器，用来存放页表的一部分

快表：存放在高速存储器中的页表部分

快表表项：页号+页架号

这种高速存储器是联想存储器（TLB），即按照内容寻址，而非按照地址访问，根据页号进行寻址。

引入快表后的地址转换代价

采用快表后，可以加快地址转换速度

假定主存访问时间为 200 毫微秒，快表访问时间为 40 毫微秒，查快表的命中率是 90%，平均地址转换代价为 (200+40)*90%+(200+200+40)*10%=260 毫微秒

比两次访问主存的时间（400 毫微秒）下降了 36%

基于快表的地址转换流程

按逻辑地址中的页号查快表

1. 若该页已在快表中，则由页架号和单元号形成绝对地址
2. 若该页不在快表中，则再查主存页表形成绝对地址，同时将该页登记到快表中

当快表填满后，又要登记新页时，则需在快表中按一定策略淘汰一个旧登记项

快表可以理解为一个简单的账本

多道程序环境下的进程表

1. 进程表中登记了每个进程的页表
2. 进程占有处理器运行时，其页表起始地址和长度送入页表控制寄存器

页表长度就是页表项的数量

多道程序环境下的地址转换

1. 页表控制寄存器存储了当前的页表的地址和长度
2. 页表控制寄存器和进程表是有关联的，所有进程在进程表中都有一项，当这个进程占据 CPU 时，这个进程就占据页表控制寄存器。
3. 不使用快表：首先从逻辑地址中，提取出页号，比较页号是否出现越界中断，如果没有越界，则根据页表向下偏移到对应的块号，提取出页表信息和页框号，页框号结合单元号，得到物理地址
4. 快表：不是从页表中查找，而是优先从快表中查询块号。

页式虚拟存储管理

页式虚拟存储管理的基本思想

将进程信息副本存放在外存中，当它被调度投入运行时，程序和数据没有全部装入内存，仅装入当前使用页面，进程执行过程中访问到不在内存的页面时，再由系统自动调入。

页式虚拟存储是现代 OS 的主流存储管理技术

首次只把进程第一页信息装入主存，称为请求页式存储管理：由于页面在需要时是根据进程请求装入内存的

请求页式存储管理：

1. 优点：进程的程序和数据可按页分散存储在内存中，有利于内存利用率和多道程序运行
2. 缺点：需要硬件支持、处理缺页中断、机器成本增加、系统开销加大，页内存在碎片。

页式虚拟存储管理的页表

需要扩充页表项，至少包含如上信息，指出：

1. 虚拟地址、实际地址
2. 主存驻留标志：指出页面是否已经装入内存。1 表示在内存中可以被正常访问，0 表示不能立即访问，产生缺页异常。
3. 修改位：被设置后，该页被调出内存前必须先写回磁盘，保障数据一致性
4. 保护位：限制页面访问权限
5. 引用位：在页面被引用无论是读写时设置，用来帮助系统进行页面淘汰。
6. 内存块号：页面对应的页框号，用来地址转换。

32 位操作系统：32bit 标识一个页表项

页号是隐含信息，不是直接存储的信息。

页式虚拟存储管理的实现

CPU 处理地址：

1. 若页驻留，则获得块号形成绝对地址
2. 若页不在内存，则 CPU 发出缺页中断

OS 处理缺页中断：

1. 若有空闲页架，则根据辅存地址（虚存）调入页，更新页表与快表等
2. 若无空闲页架，则决定淘汰页，调出已修改页，调入页，更新页表与快表

页式虚拟存储管理的地址转换

缺页中断的处理流程

本指令没有被处理完，是在查找地址的时候发生的中断，所以要回退指令执行。 缺页中断完成后要重新执行被中断指令。

页式虚拟存储管理的地址转换全过程 *

地址转换过程：

1. MMU 接收 CPU 传送来的逻辑地址并自动按页面大小把它从某位起分解成两部分：页号和页内位移。
2. 以页号为索引快速搜索快表 TLB。
3. 如果命中，立即送出页框号，并与贾内位移拼接成物理地址，然后进行访问权限检查，如获通过，进程就可以访问物理地址。
4. 如果不命中，由硬件以页号为索引搜索页表，页表基址由硬件页表基址寄存器指出。
5. 如果页表被命中，说明访问页面已在内存中，可送出页框号，并与页内位移拼接成物理地址，然后进行访问权限检查，如获通过，进程就可以访问物理地址，同时要把这个页面和页框信息装入快表 TLB，以备再次访问。
6. 如果发现页表中的对应页面失效，MMU 发出缺页异常，请求操作系统进行处理，MMU 工作到此结束。

MMU 发现缺页并发出缺页异常，存储管理接收控制，进行缺页异常处理的过程如下：

1. 挂起请求调页的进程。
2. 根据页号搜索外页表，找到存放此页的磁盘物理地址。
3. 查看内存是否有空闲页框，如有则分配一个，转（6）。
4. 如果内存中无空闲页框，按照替换算法选择淘汰页面，检查其是否被写过或修改过，若否则转（6），若是则转（5）。

TLB（快表）*

Note：快表存储正在进行的进程的若干（非连续）的页表项，其意义在于：快表访问速度高于内存，减少访问内存的次数，提高也是寻址效率

多级页表 *

多级页表的概念

现代计算机普遍支持\(2^{32}-2^{64}\)容量的逻辑地址空间，采用分页存储管理时，页表相当大，以 Windows 为例，其运行的 Intel x86 平台具有 32 位地址，规定页面 4KB（\(2^{12}\)）时，那么，4GB（\(2^{32}\)）的逻辑地址空间由 1MB（\(2^{20}\)）个页组成，若每个页表项占用 4 个字节，则需要占用 4MB（\(2^{22}\)）连续主存空间存放页表。系统中有许多进程，因此页表存储开销很大。

做法：把整个页表分割成许多小页表，每个称为页表页，它的大小与页框长度相同，于是每个页表页含有若干页表表项。

1. 页表项从 0 开始编号，允许放到不连续的页框中，为了找到页表页，建立地质索引，称为页目录表。
2. 系统为每一个进程建立一张页目录表，他的每一个表项指出一个页表页，而页表页的每个表项给出页面和页框的对应关系。

逻辑地址结构有三部分组成：页目录、页表页和位移

解决页表页如何占用内存空间的问题，解决方法：进程运行设计到的页面的页表页放置在内存中，其他页表页使用时动态调入，因此需要添加标志位指示是否调入内存。

多级页表地址转换过程

多级页表结构的本质

1. 多级不连续导致多级索引。
2. 以二级页表为例，用户程序的页面不连续存放，要有页面地址索引，该索引是进程页表；进程页表又是不连续存放的多个页表页，故页表页也要页表页地址索引，该索引就是页目录。
3. 页目录项是页表页的索引，而页表页项是进程程序的页面索引。

页面调度

当主存空间已满而又需要装入新页时，页式虚拟存储管理必须按照一定的算法将已在主存的一些页调出去

1. 选择淘汰页的工作成为页面调度
2. 选择淘汰页的算法称为页面调度算法

交换区 *

1. 操作系统需要在磁盘上定义一个交换区用来保存临时换出的页面，交换区由磁盘上的一个或多个磁盘分区组成。
2. 简单做法：进程启动时，留出大小和进程一样大的交换分区。
3. 与进程对应的是其交换区的磁盘地址，即进程映像所保存的位置，这一信息记录在进程的外页表中。
4. 问题：进程启动可能会在增大，解决：将正文、数据和堆栈分别保留交换区，并且多留几块。
5. 交换区管理重点是维护交换区映射表，记录所有的呗换出内存的页面在交换区中的位置，以便需要时换入，第二次被换出内存时，当且仅当页面修改过才再次写入，否则直接抛弃。

页面装入策略和清除策略 *

1. 页面装入策略用来解决何时将页面装入内存
2. 请页式：当产生缺页异常时调入页面
   1. 在替换时只有发生了更改才写回。
   2. 优点：只有被访问页面才会被调入，节省内存
   3. 缺点：缺页异常处理次数多，系统开销大。
3. 预调式：在使用页面前预先调入内存，操作系统根据某种算法动态预测进程最可能访问的界面，每次调入若干页面。
   1. 在替换前需要将他们都写回磁盘，可成批进行。
   2. 优点：减少磁盘 I/O 的启动次数，节省寻道和搜索时间。
   3. 缺点：如果调入的大多数界面都没有被使用则效率很低。

页面分配策略 *

1. 请求分页虚存管理可能在缺页方面付出很大的代价，需要确定页面调度算法的作用范围是此进程的页面，还是内存中的所有进程的页面。
   1. 全局替换：不考虑进程属主
   2. 局部替换：仅限于进程本身
2. 分配方式
   1. 固定分配：进程生命周期中保持页框数固定不变，有平均分配、比例分配、优先权分配等方式。
   2. 可变分配：进程生命周期中所分得的页框数可变。
      1. 缺页率较高，说明局部性较差，可以适度提高分配的页框数。
      2. 缺页率较低，可以适度降低分配的页框数
3. 工作集（驻留集）：每个进程维护的一组页面。
4. 可变分配配合局部替换可以克服全局替换的缺点。

固定分配，本地范围

1. 分配给进程的帧数是固定的
2. 从分配给过程的框架中选择要替换的页面

变量分配，全局范围

1. 分配给进程的帧数是可变的
2. 从所有框架中选择要替换的页面
3. 最容易实现
4. 被许多操作系统采用
5. 操作系统保留空闲帧列表
6. 发生页面错误时，将空闲帧添加到驻留的进程集
7. 课本 224 全局页面替换策略和 229 局部页面替换策略

变量分配，本地范围

1. 分配给进程的帧数是可变的
2. 从分配给过程的框架中选择要替换的页面
3. 添加新流程后，请根据应用程序类型，程序请求或其他条件分配页框数量
4. 发生页面错误时，请从发生故障的进程的常驻集中选择页面。
5. 不时重新评估分配

缺页中断率

1. 页面调度算法设计不当，会出现（刚淘汰的页面立即又要调入，并如此反复），这种现象称为抖动或颠簸，主要原因是内存中同时运行的进程太多，而分配给每个进程的页框太少。
2. 假定进程 P 共有 n 页，系统分配页架数 m 个
3. P 运行中成功访问次数为 S ，不成功访问次数为 F ，总访问次数 A = S + F
4. 缺页中断率定义为： \(f = \frac{F}{A}\)
5. 缺页中断率是衡量存储管理性能和用户编程水平的重要依据

缺页中断率的影响因素

1. 分配给进程的页框数：可用页框数越多，则缺页中断率就越低
2. 页面的大小：页面尺寸越大，则缺页中断率就越低
3. 页面替换算法：算法的优劣影响缺页异常次数
4. 程序特性：程序局部性要好，它对缺页中断率有很大影响。

用户编程的例子

程序将数组清零，假定仅分得一个主存页架，页面尺寸为 128 个字，数组元素按行存放，开始时第一页在主存。

糟糕的编程范式	良好的编程范式
int A[128][128]; for (int j = 0; j < 128; j++)     for (int i = 0; i < 128; i++)         A[i][j] = 0;	int A[128][128]; for (int i = 0; i < 128; i++)     for (int j = 0; j < 128; j++)         A[i][j] = 0;
每执行一次赋值就要产生一次缺页中断 共产生（128 * 128 - 1）次	共产生（128 - 1）次

全局页面替换策略

OPT 页面调度算法

算法描述：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页。

该方法由 Belady 提出，称为 Belady 算法，又称最佳算法（OPT）

OPT 只可以模拟，不可以实现，因为永远无法预知之后的事情。

这种算法可以用作衡量其他各种算法的标准。

FIFO 先进先出页面调度算法

算法描述：首先淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页（常驻的除外）

模拟的是程序执行的顺序性，有一定合理性，并不能很好模拟程序的循环性。

根据估计，缺页中断率也是最佳算法的 2-3 倍。

FIFO 算法的 Belady 异常：更多的页框导致了更高的缺页率，页框为 3 和 4 的时候

页面缓冲算法 *

页面缓冲算法是对 FIFO 替换算法的一种改进

算法策略：

1. 系统维护两个 FIFO 队列，被替换的页面添加到如下两个队列中
   1. 修改页面队列
   2. 非修改（空闲）页面队列
2. 替换的页面仍保留在内存中
   1. 如果再次引用，则找回的费用很少
   2. 当修改页面队列中的页面到达一定数量后，页面以群集形式写回磁盘，并把空闲页框加入非修改页面队列尾部。

LRU 最近最少用页面调度算法

最近最少用页面调度算法（LRU，Least Recently Used），淘汰最近一段时间较久未被访问（即上次访问最久远）的那一页，即那些刚被使用过的页面，可以马上还要被使用到。

模拟了程序执行的局部属性，既考虑了循环性，又兼顾了顺序性

严格实现的代价大（需要维持特殊队列——页面淘汰队列），实现需要硬件支持。

LRU 算法得到模拟实现

模拟是相当的不严谨，非常粗粒度的一个模拟。

1. 引用位法：每页建立一个引用标志，供硬件使用，设置一个时间间隔中断，发生时将页引用标志置 0，访问页面时将引用标志置为 1，页面置换的时候选择标志为 0 的页面，在选中淘汰页时，将所有的页的引用为全部置为 0
2. 计数法：每页添加页面引用计数器，根据计数器选择最小的，定时清空页面引用计数器
3. 计时法：每页添加计时单元，引用时，将绝对时间记录进入计时单元，定时清空计时单元。
4. 老化算法：设置一个多位寄存器，被访问将最左侧设置为 1，定时将寄存器右移，缺页中断时找到最小值的寄存器界面淘汰，被采用较多。

1. 上图使用老化算法
2. T3 时刻替换 P2 页面，因为和 P1 他们在 3 时刻都没有被访问，但是 2 时刻 P1 被访问了

SCR 第二次机会页面替换算法 *

第二次机会页面替换算法（SCR，Second Chance Replacement），将 FIFO 算法和页表中引用位结合。

算法描述：

1. 首先检查 FIFO 页面队列队首
   1. 引用位为 0，则淘汰该页面
   2. 引用位为 1，将引用位清 0，并将该页面移到队列尾部
2. 如果第一遍全为 1，则循环

LFU 最不常用的页面调度算法

最不常用的页面调度算法（LFU，Least Frequently Used），淘汰最近一段时间内访问次数较少的页面，对 OPT 的模拟性比 LRU 更好。

算法过程：基于时间间隔中断，并给每一页设置一个计数器，时间间隔中断发生后，所有计数器清 0，每访问页 1 次就给计数器加 1，选择计数最小的页面淘汰。

CLOCK 时钟页面调度算法

CLOCK 就是 SCR 结合 FIFO 形成循环，使用页引用标志位。

算法描述：采用循环队列机制构造页面队列，形成了一个类似钟表面的环形表，队列指针则相当于钟表面上的表针，指向可能要淘汰的页面

CLOCK 算法的工作流程

1. 页面调入主存时，其引用标志位置为 1
2. 访问主存页面时，其引用标志位置为 1
3. 淘汰页面时，从指针当前指向的页面开始扫描循环队列
   1. 把所遇到的引用标志位是 1 的页面的引用标志位清 0 并跳过
   2. 把所遇到的引用标志位是 0 的页面淘汰，指针推进一步

CLOCK 算法的例子 *

灰色和星号代表 1，蓝色和无星号代表 0

1. 发生命中，指针不动
2. 指针运动是为了寻找替换的页
3. 1 \(\to\) 5 其实是循环一轮，如果为 1，指针不替换，但是会将标志位置为 0

1. 当一页被替换时，指向下一帧。虽然早就进来，但是最近使用过，所以不急着替换
2. 当需要替换一页时，扫描缓冲区，查找使用位被置为 0 的一帧。
3. 每当遇到一个使用位为 1 的帧时，就将该位重新置为 0；
4. 如果在这个过程开始时，所有帧的使用位均为 0，选择遇到的第一个帧替换；
5. 如果所有帧的使用位为 1，则指针在缓冲区中完整地循环一周，把所有使用位都置为 0，并且停留在最初的位置上，替换该帧中的页。

第三次机会时钟替换算法：结合引用位和修改位

一共四种情况：r 是引用位，m 是修改位

1. 最近未被引用，未被修改：r=0，m=0
2. 最近被引用，未被修改：r=1，m=0
3. 最近未被引用，被修改：r=0，m=1
4. 最近被引用，被修改：r=1，m=1

算法描述：

1. 扫描，不修改引用位，找到第一个 r=0，m=0 的页面替换
2. 如果 1 没有找到，则从原位置开始，修改引用位，查找 r=0，m=1 的页面替换写回
3. 如果 2 没有找到，重复 1 或 2 操作。

不同算法性能比较

整体上来讲 FIFO > CLOCK > LRU > OPT

局部页面替换算法（不考）

P229-233

MIN 局部最佳页面替换算法

1. 实现思想：进程在时刻 t 访问某页面，如果该页面不在主存中，导致一次缺页，把该页面装入一个空闲页框
2. 不论发生缺页与否，算法在每一步要考虑引用串，如果该页面在时间间隔 \((t, t+\tau )\) 未被再次引用，那么就移出；否则，该页被保留在进程驻留集中
3. t 为一个系统常量，间隔 \((t, t+\tau)\) 作滑动窗口 。例子中 \(\tau =3\)，双闭区间

WS 工作集模型和工作集置换算法

1. 进程工作集指“在某一段时间间隔内进程运行所需访问的页面集合”
2. 实现思想：工作集模型用来对局部最佳页面替换算法进行模拟实现，不向前查看页面引用串，而是基于程序局部性原理向后看
3. 任何给定时刻，进程不久的将来所需主存页框数，可通过考查其过去最近的时间内的主存需求做出估计

进程工作集

指“在某一段时间间隔内进程运行所需访问的页面集合”，\(W(t, Δ)\) 表示在时刻 \(t-Δ\) 到时刻 \(t\) 之间，即 \((t-Δ，t)\) 所访问的页面集合，进程在时刻 \(t\) 的工作集

\(Δ\) 是系统定义的一个常量。变量 \(Δ\) 称为“工作集窗口尺寸”，可通过窗口来观察进程行为，还把工作集中所包含的页面数目称为“工作集尺寸”。

示例

工作集：程序在运行过程时，程序的局部性是变更的。有的部分是比较陡的，大量调入，然后平稳期，访问替换进来的页们。

模拟工作集替换算法

缺页频率替换算法

1. 定义页面错误率的上限 U 和下限 L。
2. 如果缺页率高于 U，则为进程分配更多页框。
3. 如果缺页率低于 U，则为进程分配更少页框。
4. 驻留集的大小应该和工作集大小 W 紧密相关的。
5. 如果 PFF（缺页率）>U 并且没有更多可用帧，我们将暂停该过程，ROI（Return On Investment）

页框的大小是需要根据程序动态调整的。

通过工作集确定驻留集大小

1. 监视每个进程的工作集，只有属于工作集的页面才能留在主存；
2. 定期地从进程驻留集中删去那些不在工作集中的页面；
3. 仅当一个进程的工作集在主存时，进程才能执行。

反置页表（IPT）

页表设计的一个重要缺陷是页表的大小与虚拟地址空间的大小成正比。

对于一个 128MB 的计算机，如果页面尺寸为 4KB，页表项大小为 4B，那么其反置页表只占有 128KB 的内存。

通过这个结构，哈希表和反向表中只有一项对应于一个实存页（面向实存），而不是虚拟页（面向虚存）。因此，不论由多少进程、支持多少虚拟页，页表都只需要实存中的一个固定部分。

因此，当虚拟地址空间很大而物理地址空间很小时，页表是一个稀疏的表。

正向页表（名单）、反置页表（现场坐的是谁）：

1. 正向页表：以页号为索引（隐含），完整连续排列，页表项中不含页号，每个进程单独一个页表
2. 反置页表：以页框号为索引（隐含），完整连续排列，每个页框填入的是哪个进程的哪个页号，索引进程共用一个反置页表。其页表项不包含页框号

反置页表的提出

页表及相关硬件机制在地址转换、存储保护、虚拟地址访问中发挥了关键作用，为页式存储管理设置专门硬件机构。

内存管理单元 MMU：CPU 管理虚拟/物理存储器的控制线路，把虚拟地址映射为物理地址，并提供存储保护，必要时确定淘汰页面

反置页表 IPT：MMU 使用的数据结构

反置页表的基本设计思想

针对内存中的每个页架建立一个页表，按照块号（页架号）排序。

表项包含：正在访问该页框的进程标识、页号及特征位（标志位），和哈希链指针等。

用来完成内存页架到访问进程页号的对应，即物理地址到逻辑地址的转换。

反置页表的页表项

1. 页号：虚拟地址页号
2. 进程标志符：使用该页的进程号（页号和进程标志符结合起来标志一个特定进程的虚拟地址空间的一页）
3. 标志位：有效、引用、修改、保护和锁定等标志信息
4. 链指针：哈希链，如果某个项没有链项，则该域为空（允许用一个单独的位来表示）。

反置页表的逻辑地址 *

进程标识符：使用该页的进程。

页号：虚拟地址页号部分，页号和进程标志符结合起来标志一个特定的进程的虚拟地址空间的一页。

页内位移

反置页表的地址转换

上图 4-10 中，以页框号为索引，记录当前页框中存储的是哪个进程的哪个页

反置页表地址转换过程如下：

1. 需要访问内存地址时，地址转换机制用进程标识符与页号作为输入，由哈希函数先映射到哈希表，哈希表项存放的是指向 IPT 表项的指针
   1. 此指针可能就是指向匹配的 IPT 表项；
   2. 如果不是则遍历哈希链直至找到进程标识符与页号均匹配的 IPT 表项：因为多个页号通过哈希函数可能得到了相同的哈希值，所以我们选择使用哈希链。
2. 而此表项的序号（索引）就是页框号，通过拼接页内位移便可生成物理地址。
3. 若在反置页表中未能找到匹配的 IPT 页表项，说明此页不在内存，触发缺页异常，请求操作系统通过页表调入：发生缺页中断时需要多访问一次磁盘，速度会比较慢。

页框号是根据公式换算出来的：\(x_i = x_0 + 4 * i\)

反置页表 *

线性反置页表	反置页表
哈希线性反置页表	主存分配的位示图和链表方法

反置页表下的地址转换示意

1. 未显示选择淘汰页面，同样由 MMU 完成
2. 使用哈希提高性能 \(\to\) 不必遍历

段式存储管理

段式存储管理基于可变分区存储管理原理。

程序分段结构

高级语言采用模块化程序设计方法。应用程序由若干程序段（模块）组成，如由主程序段（M）、子程序段（X）、数据段（D）和工作区段（W）组成，每一段都从 0 开始编制，各有各自名字和长度且实现不同功能。

编译后段间地址是不连续的，段内地址是连续的。

段式存储逻辑地址

1. 分段存储器的逻辑地址由两部分组成：段号+段内偏移；
2. 页式存储管理中页的划分对程序员不可见；
3. 段式存储管理中段的划分对程序员可见。

段式存储的段表

1. 存储分配时，应该为进入内存的作业建立段表，各段在内存中的情况有段表来记录，包含了段号、段起始长度和长度。
2. 撤销进程时，回收所占用的内存空间，并清除此进程的段表。
3. 段表表项实际上起到了基址/限长寄存器的作用，设置段表控制寄存器。

段式存储管理的基本思想

1. 段式存储管理基于可变分区存储管理实现，一个进程要占用多个分区
2. 硬件需要增加一组用户可见的段地址寄存器（代码段、数据段、堆栈段，附加段），供地址转换使用
3. 存储管理需要增加设置一个段表，每个段占用一个段表项，包括：段始址、段限长，以及存储保护、可移动、可扩充等标志位

段式存储管理的地址转换流程

使用终端来完成

段的共享

1. 如果多个进程段表中的某段指向内存相同的地址，内存中以该处为起始地址的某段就可以被共享。
2. 对共享段的信息必须进行保护，如规定只能读出不能写入，不满足保护条件则产生保护中断
3. 为了方便共享，系统中常常建立一张共享段表记录所有共享段，包含段名、共享计数、段长、段首址、保护位等。

分页和分段的寻址计算

分段和分页的比较

1. 分段是信息的逻辑单位，由源程序的逻辑结构所决定，程序员可见
   1. 段长可根据用户需要来规定，段起始地址可从任何主存地址开始。
   2. 分段方式中，源程序（段号，段内位移）经连结装配后地址仍保持二维结构。
2. 分页是信息的物理单位，与源程序的逻辑结构无关，程序员不可见，
   1. 页长由系统确定，页面只能以页大小的整倍数地址开始
   2. 分页方式中，源程序（页号，页内位移）经连结装配后地址变成了一维结构

分页：逻辑地址到物理地址

段页式存储管理

段页式存储管理的基本思想

1. 段式存储管理可以基于页式存储管理实现
2. 每一段不必占据连续的存储空间，可存放在不连续的主存页架中
3. 能够扩充为段页式虚拟存储管理
4. 装入部分段，或者装入段中部分页面

段页式存储管理的段表和页表

1. 既有段表，也有页表
2. 段表中存储的是页表和页表始址

段页式存储管理的地址转换

段式虚拟存储管理

段式虚拟存储管理的基本思想

1. 把进程的所有分段都存放在辅存中，进程运行时先把当前需要的一段或几段装入主存，在执行过程中访问到不在主存的段时再把它们动态装入
2. 段式虚拟存储管理中段的调进调出是由 OS 自动实现的，对用户透明
3. 与段覆盖技术不同，它是用户控制的主存扩充技术，OS 不感知

段式虚拟存储管理的段表扩充

1. 段表的扩充
2. 特征位： 00（不在内存）01（在内存）11（共享段）
3. 存取权限： 00（可执行）01（可读）11（可写）
4. 扩充位： 0（固定长）1（可扩充）
5. 标志位： 00（未修改）01（已修改）11（不可移动）

段式虚拟存储管理的地址转换

段页式虚拟存储管理

段页式虚拟存储基本原理

1. 虚地址以程序的逻辑结构划分为段，这是段页式的段式特征。
2. 实地址划分层位置固定、大小相同的页框（块），这是段页式的页式特征。
3. 将每一段的线性地址空间划分成与页框大小相同的页面，段页式的特征
4. 逻辑地址由段号 s、段内页号 p 和页内偏移 d 组成
   1. 对用户，虚拟地址由段号 s 和段内位移 d'组成
   2. 系统内部将 d'分解为 p 和 d，d' = p * 块长 + d
5. 请求段页式虚拟存储管理的数据结构比较复杂，包含作业表、段表和页表三部分。
   1. 作业表：进入系统的作业和作业段表的起始地址
   2. 段表：是否在内存、段页表起始地址
   3. 页表：是否在内存、对应内存块号

段页式虚拟存储管理的地址转换

存储管理方案以及虚存页面替换算法小结 *

补充：关于快表问题 *

有效位为 0，不指引

1. Valid 并不全表示页表项是否在主存中
2. 发生页面替换的时候，被替换的页如果在快表中，则其的 valid 位置 0 或者将该页删除。

Linux 虚拟存储管理 *

伙伴系统（一种算法）

1. 伙伴系统（Knuth，1973），又称 buddy 算法，是一种固定分区和可变分区折中的主存管理算法
2. 基本原理是：任何尺寸为 \(2^i\) 的空闲块都可被分为两个尺寸为 \(2^{i-1}\) 的空闲块，这两个空闲块称作伙伴，它们可以被合并成尺寸为 \(2^i\) 的原先空闲块。
3. 伙伴通过对大块的物理主存划分而获得
   1. 假如从第 0 个页面开始到第 3 个页面结束的主存
   2. 每次都对半划分，那么第一次划分获得大小为 2 页的伙伴，如 0、1 和 2、3
   3. 进一步划分，可以获得大小为 1 页的伙伴，例如 0 和 1，2 和 3

例子：类似二叉树的形式进行分配

Linux 伙伴系统

1. 以 page 结构为数组元素的 mem_map[] 数组
2. 以 free_area_struct 结构为数组元素的 free_area 数组
3. 位图数组（bitmap）

Linux 基于伙伴的 slab 分配器

1. 为什么要使用 slab 分配器？
   1. 伙伴系统以页框为基本分配单位，内核在很多情况下，需要的主存量远远小于页框大小，如 inode、vma、task_struct 等，为了更经济地使用内核主存资源，引入SunOS 操作系统中首创的基于伙伴系统的 slab 分配器，其基本思想是：为经常使用的小对象建立缓存，小对象的申请与释放都通过 slab 分配器来管理，仅当缓存不够用时才向伙伴系统申请更多空间。//页内可以按 2 的幂次拆分。
   2. 优点：充分利用主存，减少内部碎片，对象管理局部化，尽可能少地与伙伴系统打交道，从而提高效率。
2. slab 的结构

struct slab{
   struct list_head;          // slab 满、半满或空闲链表
   unsigned long colouoff;    //slab 着色偏移量
   void * s_mem;              //slab 的第一个对象
   unsigned int inuse;        //已分配的对象数
   kmem_bufctl_t free;        //第一个空闲对象
}

3. slab 的操作

slab 分配器主要操作

1. kmem_cache_create() 数：创建专用 cache，规定对象的大小和 slab 的构成，并加入 cache 管理队列；
2. kmem_cache_alloc() kmem_cache_free() 数：分别用于分配和释放一个拥有专用 slab 队列的对象；
3. kmem_cache_grow() kmem_cache_reap() 数：
   1. kmem_cache_grow() 向伙伴系统申请向 cache 增加一个 slab
   2. kmem_cache_reap() 于定时回收空闲 slab
4. kmem_cache_destroy() kmem_cache_shrink()：用于 cache 的销毁和收缩；
5. kmalloc() kfree() 数：用来从通用的缓冲区队列中申请和释放空间；
6. kmem_getpages() kmem_freepages() 数：slab 与页框级分配器的接口，当 slab 分配器要创建新的 slab 或 cache 时，通过 kmem_getpages() 内核提供的伙伴算法来获得一组连续页框。如果释放分配给 slab 分配器的页框，则调用 kmem_freepages() 数。