内存管理概念

引入多道程序的并发执行后，进程之间共享的不仅仅是处理机，还有主存储器。然而，共享主存会形成一些特殊的挑战。若不对内存进行管理，则易导致内存数据的混乱，以至于限制进程的并发执行。因此，为了更好地支持多道程序并发执行，必须进行内存管理

基本原理和要求

  • 内存管理

    操作系统对内存的划分和动态分配

  • 内存管理目的

    1. 方便用户
    2. 提高内存利用率

  • 内存管理主要功能

    内存空间的分配与回收

    地址转换（逻辑 → 物理）

    内存空间的扩充（逻辑上）

    内存共享（受控访问）

    存储保护

  • 将用户程序变为可在内存中执行的程序的步骤

    1. 编译

      由编译程序(compiler)对用户源程序进行编译，形成若干个目标模块(object module)

    2. 链接

      由链接程序(linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块(load module)

    3. 装入

      由装入程序(loader)将装入模块装入内存

  • 目标文件

    目标文件有三种形式：

    1. 可重定位目标文件

      包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件

    2. 可执行目标文件

      包含二进制代码和数据，其形式可以被直接复制到内存并执行

    3. 共享目标文件

      一种特殊类型的可重定位目标文件，可以在装入或者运行时被动态地装入内存并链接

    编译器和汇编器生成可重定位目标文件（包括共享目标文件）。链接器生成可执行目标文件

    从技术上来说，一个目标模块就是一个字节序列，而一个目标文件就是一个以文件形式存放在磁盘中的目标模块，两个术语常常互换使用

  • 逻辑地址空间和物理地址空间

    编译后，每个模块都从 0 号开始编址，称为该目标模块的相对地址（逻辑地址）

    当链接程序将各模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从 0 号单元开始编址的逻辑地址空间（注意区分编译后形成的逻辑地址和链接后形成的最终逻辑地址）

    物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址

  • 程序的链接方式

    1. 静态链接

      在程序运行之前完成链接，之后不再拆开

      需要修改目标模块中的相对地址以及变换外部调用符号（将每个模块中所用的外部调用符号也都变换为相对地址）

    2. 装入时动态链接

      直接将目标模块一个个装入内存，边装入边链接

      即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，链接完成后将其装入内存

      优点：便于修改和更新（各目标模块分开存放）；便于实现对目标模块的共享

    3. 运行时动态链接

      将对某些模块的链接推迟到程序执行中需要该目标模块时才进行

      有些模块不一定/基本用不到，所以一开始就不全装进内存

      优点：加快装入过程；节省大量内存空间

  • 重定位

    在装入时对目标程序中的相对地址的修改过程（逻辑地址 → 物理地址）

  • 程序的装入方式

    1. 绝对装入

      直接按绝对地址装入内存，逻辑地址与物理地址相同

      用户程序经编译后，将产生物理地址。绝对地址既可在编译或汇编时给出，也可由程序员直接赋予，但通常是在程序中采用符号地址，在编译或汇编时再将这些符号地址转为绝对地址

      使用这种方式的前提是，计算机系统很小，且仅能运行单道程序，此时完全有可能知道程序将驻留在内存的什么位置

    2. 可重定位装入/静态重定位

      根据内存的当前状况，将装入模块装入内存的适当位置，装入时进行重定位

      特点：一次分配作业要求的全部内存空间（给不了就不装）；作业进入内存后，整个运行期间不能在内存中移动，也不能再申请内存空间

    3. 动态运行时装入/动态重定位

      地址转换推迟到程序真正执行时进行（故装入模块装入内存后所有地址仍都是逻辑地址）

      可重定位方式不允许程序运行时在内存中移动位置，但在实际运行过程中程序在内存中的位置可能经常要改变，例如在具有对换功能的系统中，一个进程可能被多次换出换入，每次换入后的位置通常是不同的，在这种情况下就应采用动态运行时装入的方式

      需要一个重定位寄存器的支持：目标模块装入内存时无需任何修改；一个程序由若干相对独立的目标模块组成时，每个目标模块各装入一个存储区域，而这些存储区域可以不相邻

      特点：可将程序分配到不连续的存储区；装入程序的部分代码即可投入运行，运行期间再根据需要动态申请分配内存；便于程序段的共享，可向用户提供一个比存储空间大得多的地址空间

重定位寄存器在整个系统中只设置一个，用来存放正在执行的程序或正在访问的数据在内存中的始址。因为 CPU 在同一时刻只能执行一条指令或访问一条数据，所以为每道程序（数据）设置一个寄存器没有必要（同时也不现实，寄存器很贵，而程序的道数很多且无法预估），只需在切换程序执行时重置寄存器内容

页表寄存器 PTR 同理

  • 进程的内存映像（虚拟地址空间）

    每个高级语言源程序经编译、汇编、链接等处理生成可执行的二进制机器目标代码时，都被映射到一个统一的虚拟地址空间。所谓“统一”是指不同的可执行文件所映射的虚拟地址空间大小一样，地址空间的区域划分结构也相同，这简化了链接器的设计和实现，也简化了程序的加载过程

    下图是 IA-32 + Linux 系统中一个进程对应的虚拟地址空间映像

    一个进程的内存映像一般有这些要素：代码段、数据段、进程控制块、堆、栈

    每个区域都有相应的起始位置

  • 内存保护的两种方法

    内存保护是内存管理的一部分，是操作系统的任务，但出于安全性和效率考虑，必须由硬件实现，所以需要操作系统和硬件机构的合作来完成

    1. 在 CPU 中设置一对上、下限寄存器，存放用户作业在内存中的上下限地址（应该是物理地址）

    2. 重定位寄存器/基址寄存器 + 界地址寄存器/限长寄存器

      内存管理机构动态地将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元访问（即读/写）重定位寄存器和界地址寄存器时必须使用特权指令

    页式管理中有页地址越界保护，段式管理中有段地址越界保护（2 次）

  • 内存共享

    进程内存空间中只有只读的区域才可以共享

  • 可重入代码/纯代码

    一种允许多个进程同时访问但不允许被任何进程修改的代码

    可重入程序主要是通过共享来使用同一块存储空间的，或通过动态链接的方式将所需的程序段映射到相关进程中去

    其最大的优点是减少了对程序段的调入/调出，从而减少了对换数量

覆盖与交换

多道程序环境下用来扩充内存的两种方法（以时间换空间）

覆盖（同一个进程）

把用户空间分成一个固定区和若干覆盖区，程序经常活跃的部分放在固定区，其余部分按调用关系分段，将那些即将要访问的段放入覆盖区，其他段放在外存中

打破了必须将一个进程的全部信息装入主存后才能运行的限制（但当同时运行程序的代码量大于主存时仍不能运行）

覆盖技术要求给出程序段之间的覆盖结构，对用户和程序员不透明，所以对于主存无法存放用户程序的矛盾，现代操作系统是通过虚拟内存技术来解决的，覆盖技术已成历史

覆盖技术是早期在单一连续存储管理中使用的扩大存储容量的一种技术，它同样可用于固定分区分配的存储管理

交换（不同进程/作业之间）

换出：把处于等待状态（阻塞/就绪）的程序从内存移到外存

换入：把准备好竞争 CPU 运行的程序从外存移到内存

中级调度采用的就是交换技术

若换出进程，须确保该进程完全处于空闲状态

为了有效使用 CPU，需要使每个进程的执行时间比交换时间长

交换需要备份存储，通常是快速磁盘，足够大，并提供对这些内存映像的直接访问

交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用起来可能很快

交换通常在有许多进程运行且内存空间吃紧时开始启动，而在系统负荷降低时就暂停

普通的交换使用不多，但交换策略的某些变体在许多系统（如 UNIX）中仍发挥作用

交换技术在现代操作系统中仍具有较强的生命力

正在 I/O 操作的进程不能被换出；处于临界区的进程不一定

对外存对换区的管理应以提高换入、换出速度为主要目标

连续分配管理方式

为一个用户分配一个连续的内存空间

单一连续分配

内存在此方式下分为系统区和用户区。系统区仅供操作系统使用，通常在低地址部分；用户区内存中仅有一道用户程序，即整个内存的用户空间由该程序独占

优点：简单、无外部碎片，无须进行内存保护（内存中永远只有一道程序），可采用覆盖技术，不需要额外的技术支持

缺点：只能用于单用户、单任务的操作系统中，有内部碎片，存储器利用率极低

固定分区分配

将用户空间划分为若干固定大小的区域，每个分区只装入一道作业

分区划分方法：

  1. 分区大小相等

    用于利用一台计算机去控制多个相同对象的场合

    缺乏灵活性

  2. 分区大小不等

    划分为多个较小的分区、适量的中等分区和少量大分区

    为便于内存分配，通常将分区按大小排队，并为之建立一张分区说明表（起始地址、大小、状态）

    未找到合适分区时，则拒绝为该用户程序分配内存

优点：可用于多道程序设计的最简单的存储分配，无外部碎片

缺点：

  1. 程序可能太大而放不进任何一个分区（此时用户得用覆盖技术）
  2. 存在内部碎片
  3. 不能实现多进程共享一个主存区，存储空间利用率低

固定分区分配很少用于现在通用的操作系统中，但在某些用于控制多个相同对象的控制系统中仍发挥着一定的作用

动态分区分配/可变分区分配

不预先划分内存，而是在进程装入内存时，动态地为之建立大小正好合适的分区

内存空闲分区的分配算法（动态分区的分配策略）：

  1. 首次适应算法(First Fit)（简单顺序查找）

    从低地址开始查找第一个能满足大小的空闲分区

    最简单，通常也是最好和最快的

    会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时都要经过这些分区，因此增加了查找的开销

  2. 临近适应算法(Next Fit)/循环首次适应算法（简单顺序查找）

    由首次适应算法演变而成，不同之处是，分配内存时从上次查找结束的位置开始继续查找

    试图解决首次适应算法的问题。但它常常导致在内存空间的尾部分裂成小碎片（因为在一遍扫描中，内存前面部分使用后再释放时，不会参与分配）

    通常比首次适应算法要差

  3. 最佳适应算法(Best Fit)（排序/遍历）

    空闲分区会按容量增序形成分区链，从链首开始查找第一个能满足大小的空闲分区

    性能通常很差，会容易产生最多的碎片，因为每次最佳的分配会留下很小的难以利用的内存块

  4. 最坏适应算法(Worst Fit)/最大适应算法(Largest Fit)（排序/遍历）

    空闲分区会按容量降序形成分区链，从链首开始查找第一个能满足大小的空闲分区（即挑选出最大的空闲分区）

与固定分区类似，可设置一张空闲分区链（表），包含空闲分区的始址和大小信息，在分配和回收内存时需相应修改。注意，回收内存时可能出现四种情况，考试常考

随着进程的换入换出，会出现更多更小的外部碎片

可使用紧凑(compaction)技术克服外部碎片，即操作系统不时地对进程进行移动和整理。这需要动态重定位寄存器的支持，且相对费时（紧凑的过程类似于 Windows 系统中的磁盘碎片整理程序，只不过后者是对外存空间的紧凑）

三种内存连续分配方式的比较：

非连续分配管理方式

基本分页存储管理方式

  • 引入目的

    固定分区会产生内部碎片，动态分区会产生外部碎片，为了内存的使用能尽量避免碎片的产生，故引入了分页的思想

  • 思想

    主存和每个进程以块为单位进行划分。进程在执行时，以块为单位逐个申请主存中的块空间

    进程中的块称为页(page)；内存中的块称为页框/页帧(page frame)；外存也以同样的单位划分，直接称为块或盘块(block)

  • 分页 vs 固定分区

    相同：不会产生外部碎片

    不同：

    1. 块相当小
    2. 进程也按照块划分
    3. 一个程序可占据多个块且不需要连续
    4. 分页管理不会产生外部碎片（内部碎片也只有进程申请的最后一个内存块才有，也称页内碎片）

  • 逻辑地址结构

    页号和页内偏移量对用户透明

    这里每页大小 $2^{12}$ B = 4KB，最多允许 $2^{20}$ = 2M 页

  • 页表

    存储进程页到内存页帧的映射

    OS 为每个进程都维护了一个页表，另外还维护一个空闲页框列表

    进程在执行时不需要将所有页调入内存页框，而只需将保存有映射关系的页调入内存（不应该是调入内存了才会有映射关系？）

    一级页表存放在内存

  • 页面大小

    应是 2 的整数幂。页面太小则页表过长，占用大量内存，增加硬件地址转换的开销，降低页面换入/换出的效率，并且不能充分利用访存的空间局部性来提高命中率；页面过大则使页内碎片增大，降低内存的利用率

    确定页面大小有很多因素，如进程的平均大小、页表占用的长度等

    页的大小固定且由系统决定

  • 页表项大小

    若逻辑地址空间 32 位、一页 4 KB，则一共有 1M 页，那么页表项至少需要 20 位才能表示完，若以字节为编址单位，则页表项至少为 3B （当然也可以取 4B，更好存储）

    我觉得应该用物理地址长度，这里应该是没考虑虚拟内存

  • 基本地址变换机构（逻辑地址 → 物理地址）

    已知页面大小 L 和 逻辑地址 A，求物理地址 E

    整个地址变换过程均由硬件自动完成

    由上图的第 ③ 步可知，页表必须在物理内存中连续存放

    ps：数组的连续存放是逻辑空间上的连续，而且要是跨页的话不一定是相邻的页

  • 页表寄存器 PTR (Page-Table Register)

    进程未执行时，页表始址和长度一开始放在本进程的 PCB 中，当调度程序调度到某进程时，才将这两个数据装入 PTR。因此在单处理机环境下，虽然系统中可运行多个进程，但只需一个 PTR

  • 存取一个数据/一条指令至少访问两次内存（不考虑 TLB 和 Cache）：

    第一次访存是访问页表，得到数据/指令物理地址；第二次根据该物理地址访存去存取数据/指令

  • 分页管理方式需要处理好的两个问题

    1. 每次操作都需要进行逻辑地址到物理地址的转换，因此地址转换过程必须足够快，否则访存速度会降低
    2. 每个进程引入页表，用于存储映射机制，页表不能太大，否则内存利用率会降低

  • 快表 TLB (Translation Lookaside Buffer)

    是一种相联存储器(Associative Memory)，具有并行查找能力的高速缓冲存储器，位于 CPU，属于 SRAM。基于局部性原理，存放有若干页表项，以减少访问内存的次数

    相应地，内存中的页表就称为慢表

    和主存（逻辑地址）的映射方式通常采用全相联或组相联方式

  • 具有快表的地址变换机构

    查页表时，可以先查快表再查慢表，也可以快慢表一起查

    一般快表的命中率可达 90% 以上

    快表才真正存储了页号（即 Tag 字段，全相联是虚页号，组相联是虚页号去除末尾 $\log_2N$ 位组号的高位的）

  • 两级页表——页表的页表

    一页 4 KB、一个页表项按 4B 来算，若要实现进程对全部逻辑地址空间（32 位）的映射，则每个进程需要 4MB（1024 页）并且连续的主存空间存放页表。即使不考虑对全部逻辑地址空间进行映射的情况，以 40MB 的进程为例，页表 40KB，若将所有页表项存放在内存中，则需要 10 个内存页框保存，而整个进程实际执行时只需要几十个页面进入内存，这无疑降低了内存利用率；从另一方面，根据局部性原理，大多数情况下映射所需要的页表项都在页表的同一个页面中，因此 10 页的页表项也并不需要同时保存在内存中

    为了压缩页表，我们进一步延伸映射的思想，就可得到二级分页

    为了查询方便，顶级页表最多一页。从上图看，二级页表显然也是最多一页，所以记住两级乃至多级页表的每一级页表都不超过一页就行了

    两级页表下，页表寄存器应是针对顶级页表设置的

    上述对页表施行离散分配的方法，只解决了对于大页表无需大片连续存储空间的问题（顶级页表还是需要连续的），并未解决用较少的内存空间去存放大页表的问题。换言之，只用离散分配空间的办法并未减少页表所占用的内存空间（甚至还增加了）

    要解决占用内存过大的问题，可利用虚拟存储器思想，即不用把所有的页表都调入内存，只在需要它时才调入。因此为了表征某页的二级页表是否已经调入内存，还应在顶级页表项中增设一个状态位

    所以采用虚拟内存 + 两级页表的情况下，会发生页表不在内存而需要产生中断去磁盘 I/O 的情况（感觉考题不会这么考，有一点点变态）

  • 多级页表

    建立两级级及多级页表的目的在于建立索引，以便不用浪费内存空间去存储无用的页表项，也不用盲目地顺序式查找页表项

    但也导致存取一次数据或指令需要多次访问内存甚至磁盘，会大大增加一次访存的时间

    优点：页表简单，调入方便

    缺点：最后一页存在页内碎片；页不是逻辑上独立的实体，所以处理、保护和共享不及段式方便

基本分段存储管理方式

  • 引入目的

    分页通过硬件机制实现，对用户完全透明。分段管理方式的提出则考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面需要

  • 段的划分

    在用户编程时，按照用户进程中的自然段划分逻辑空间，例如主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等

    每段从 0 开始编址，并分配一段连续的地址空间内存中

    段内要求连续，段间不要求

    段长不固定

    段号和段内偏移量必须由用户显式提供（高级程序设计语言中由编译程序完成）

  • 逻辑地址结构

  • 段表

  • 地址变换机构

    变换过程与分页类似

    从逻辑地址取段号和段内偏移量无法通过除法和取模得到，因为段长不固定，故需要显式提供段号和段内偏移

    越界保护除了要比较段表长度和段号，还要比较段长和段内偏移量（而分页中的页内偏移是不可能越界的）

    注意上图里是段表寄存器

  • 段的共享

    可重入代码和不能修改的数据可以共享

    分页系统也能实现程序和数据的共享，但远不如分段系统来得方便（分页太散了）

  • 优点：具有逻辑独立性（段的分界与程序的自然分界相对应），使得它易于编译、管理、修改和维护，也便于多道程序的共享

    缺点：段长可变，分配空间不便，容易在段间留下碎片

分段和动态分区很像，但分段是进程内分配，属于非连续分配；动态分区是进程间分配，属于连续分配

段页式管理方式

  • 引入目的

    页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。将这两种存储管理方法结合起来，便形成了段页式存储管理方式

    即：用分段方法来分配和管理用户地址空间，用分页方法管理物理存储空间

  • 段页的划分

    作业的地址空间先被划分成若干逻辑段，每段再分成若干大小固定的页

    对内存空间的管理和分页存储管理一样

  • 逻辑地址结构

  • 系统为每个进程建立一张段表，每个分段又分别有一张页表

    在一个进程中，段表只有一个，而页表可能有多个

  • 地址变换机构

    存取一次数据/指令一般需要访问三次内存（段表→页表→数据/指令）

    同样可以使用快表来加快查找，其关键字由段号和页号组成，值是对应的页帧号和保护码

  • 优点：兼具页式和段式的优点，可以按段实现共享和保护

    缺点：地址变换过程中需要两次查表，系统开销大

注意

  • 只有固定分区分配可采用静态重定位，其他管理方案均可能在运行过程中改变程序位置

  • 程序的动态链接与程序的逻辑结构有关，分段存储管理有利于动态链接

  • 操作系统实现分区存储管理的代价最小

    实现分页、分段和段页式存储管理需要特定的数据结构支持，如页表、段表等。为了提高性能，还需要硬件提供快存和地址加法器等，代价高

    分区存储管理是满足多道程序设计的最简单的存储管理方案，特别适合嵌入式等微型设备

  • 确定一个地址需要几个参数，作业地址空间就是几维的

    分页管理的地址空间是一维的：页号

    分段管理的地址空间是二维的：段号、段内偏移

    段页式管理的地址空间是二维的：段号、页号

  • 段表寄存器和页表寄存器的作用都有两个，一是在段表或页表中寻址，二是判断是否越界

  • 采用分页或分段管理后，提供给用户的物理地址空间大小不能确定

    页表和段表同样存储在内存中，系统提供给用户的物理地址空间为总空间减去页表或段表的长度。由于页表和段表的长度不能确定，所以提供给用户的物理地址空间大小也不能确定

虚拟内存管理

在物理上扩展内存相对有限，尝试以一些其他可行的方式在逻辑上扩充内存

基本概念

  • 传统存储管理方式的特征

    1. 一次性

      作业必须一次性全部装入内存后才能开始运行。这会导致两种情况：

      1）不能全部被装入内存的大作业永远无法运行

      2）当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序度的下降

    2. 驻留性

      作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业结束运行

  • 局部性原理

    从广义上讲，快表、页高速缓存及虚拟内存技术都属于高速缓存技术，这个技术所依赖的原理就是局部性原理。局部性原理既适用于程序结构，又适用于数据结构

    1. 时间局部性

      典型原因是程序中存在大量的循环操作

      将近来使用的指令和数据保存到高速缓存中，并使用高速缓存的层次结构

    2. 空间局部性

      因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的

      通常使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中

    虛拟内存技术实际上建立了“内存-外存”的两级存储器结构，利用局部性原理实现高速缓存

    局部性越好，虚拟存储系统越能更好地发挥作用

  • 虚拟存储器的定义

    具有部分装入、请求调入和置换功能，能从逻辑上对内存容量加以扩充的存储器系统

  • 虚拟存储器的主要特征

    1. 多次性

      一个作业中的程序和数据无需在作业运行时一次性地全部装入内存

    2. 对换性

      一个作业中的程序和数据无需在作业运行时常驻内存

    3. 虚拟性

      从逻辑上扩充内存的容量，使用户所看到的内存容量远大于实际

  • 虚存空间大小的决定因素（要满足的条件）

    1. 虚存实际容量 ≤ 内存容量 + 外存容量
    2. 虚存最大容量 ≤ 计算机的地址位数能容纳的最大容量

  • 虚拟内存技术的实现

    需要建立在离散分配的内存管理方式的基础上（采用连续分配方式时，会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量）

    虚拟内存的实现有以下三种方式：

    1. 请求分页存储管理
    2. 请求分段存储管理
    3. 请求段页式存储管理

    需要的硬件支持：

    1. 一定容量的内存和外存
    2. 页表机制/段表机制，作为主要的数据结构
    3. 中断机构（缺页中断）
    4. 地址变换机构

请求分页管理方式

建立在基本分页系统基础上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能

请求分页式目前最常用的一种实现虚拟存储器的方法

  • 页表机制

    相比基本分页，页表项增加了 4 个字段：

    1. 有效位/装入位/状态位 P

      指示该页是否已调入内存

    2. 引用位/使用位/访问字段 A

      记录本页在一段时间内被访问的次数/本页最近已有多长时间未被访问

      用来配合置换策略进行设置

    3. 脏位/修改位 M

      标识该页在调入内存后是否被修改过

      以确定页面置换时是否写回外存

    4. 外存地址

      用于指出该页在外存上的地址

      通常是物理块号，供调入该页时参考

    王道 CO3 中把物理块号和外存地址两个字段合并，使用时根据有效位来区分

  • 缺页中断机构

    缺页中断属于内中断

    若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中的相应页表项；若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）

    在指令执行期间而非一条指令执行完后产生和处理中断信号

    一条指令在执行期间可能产生多次缺页中断

  • 地址变换机构

    虚拟存储器中，地址映射由操作系统完成，但需要一部分硬件基础的支持

    TLB 命中则 Page 必然命中

  • 页式虚拟存储器中，页面很大或很小都会使操作速度变慢，但原因不同：

    页面很小：虚拟存储器中包含的页面数就会过多，导致：① 页表的体积过大；② 不能充分利用访存的空间局部性来提高命中率

    页面很大：虚拟存储器中的页面数会变少，由于主存的容量比虚拟存储器的容量小，主存中的页面数会更少，进而会导致：① 页面调入/调出时间较长；② 页面调度频率较高，换页次数增加；③ 平均页内剩余空间较大

    补充下页面大和页面小的好处：

    页面小：平均页内剩余空间较少，可节省存储空间

    页面大：减少页表空间

页面分配策略

驻留集管理

  • 驻留集：给特定进程分配的物理页框

  • 考虑因素

    1. 每个进程的帧越少，内存中进程就越多，并发度越高，增加了操作系统至少找到一个就绪进程的可能性，减少了由于交换而消耗的处理器时间；但过少会使缺页率增大
    2. 为进程增加一些内存帧，将显著降低缺页率
    1. 给特定进程分配的内存空间超过一定大小后，由于局部性原理，该进程的缺页率不会明显降低

  • 驻留集分配策略

    1. 固定分配(fixed-allocation)

      为一个进程在内存中分配固定数量的页框，在进程运行期间都不改变

      将空闲物理块分配给各个进程，可采用下述几种算法：

      1）平均分配算法

      2）按比例分配算法（根据进程的大小）

      3）优先权分配算法（为重要和紧迫的进程分配较多的物理块）

      通常采取的方法是把所有可分配的物理块分成两部分：一部分按比例分配给各个进程；一部分则根据优先权分配

    2. 可变分配(variable-allocation)

      允许分配给一个进程的页框在该进程的生命周期中不断地发生变化，根据缺页率使进程分得的页框数动态增加或减少

      看起来性能更优，但难点在于它要求 OS 评估活动进程的行为，这必然会增加 OS 的软件开销，并取决于处理器平台所提供的硬件机制

  • 置换范围

    1. 局部置换

      仅在产生这次缺页的进程的驻留集中选择，以保证分配给该进程的内存空间不变

    2. 全局置换

      把内存中所有未锁定的页都作为置换的候选页

      通常操作系统本身会保持一个空闲物理块队列，仅当空闲物理块用完时，OS 才从内存中选择一页调出（可以是任一进程中的页）

      比局部置换更加灵活，但也存在弊端，如它会盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降

  • 策略组合

    1. 固定分配全局置换：冲突，无此方案
    2. 固定分配局部置换：不灵活，难点在确定驻留集大小
    3. 可变分配全局置换：可能最容易实现，被许多 OS 使用。难点在于置换页的选择，没有任何原则用于确定应该让哪个进程的驻留集给出一页
    4. 可变分配局部置换：不时重新评价进程的分配，增加或减少分配给进程的页框以改善系统性能。需要更复杂的实现，也需要更大的开销，但对比频繁地换入换出所浪费的计算机资源，这种牺牲还是值得的

调入页面的时机

  • 预调页策略

    基于局部性原理，以预测为基础，将那些预计在不久之后便会被访问的页面预先调入内存

    目前成功率仅为 50%，因此主要用于进程的首次调入（由程序员指出应先调入哪些页）

  • 请求调页策略

    请求了再调

    优点：易于实现

    缺点：每次只调一页，调入/调出页面数多时会花费过多的 I/O 开销

    一般情况下两种调页策略同时使用：运行前预调入，运行期间请求调入

从何处调入页面

  • 请求分页系统的外存分为两部分：
    1. 文件区：存放文件（通常采用离散分配）
    2. 对换区：存放对换页面（通常采用连续分配，因此磁盘 I/O 比文件区快）
  • 三种情况：
    1. 对换区足够：全从对换区调入。进程运行前需要将与该进程有关的文件从文件区复制到对换区
    2. 对换区不够：不会被修改的文件都从文件区调入。需要调出这些文件时，因为它们未被修改而不必被调出。对于可能被修改的部分，换出时调到对换区，以后需要时就从对换区调入（因为读比写快）
    3. UNIX 方式：与进程有关的文件一开始都放在文件区，换出时再都放在对换区（因此，文件区存放的都是未运行过的页面，对换区存放的都是曾经运行过但又被换出的页面）。UNIX 允许页面共享，若某进程请求的页面已被其他进程调入内存时便无需再调入

如何调入页面

当进程所访问的页面不在内存中时（存在位为 0），便向 CPU 发出缺页中断，中断响应后便转入缺页中断处理程序。该程序通过查找页表得到该页的物理块（外存），此时如果内存末满，则启动磁盘 I/O，将所缺页调入内存，并修改页表。如果内存已满，则先按某种置换算法和置换范围从内存中选出一页准备换出；如果该页未被修改过（修改位为 0），则无须将该页写回磁盘；但若该页已被修改（修改位为 1），则必须将该页写回磁盘对换区，然后将所缺页调入内存，并修改页表中的相应表项，置其存在位为 1。调入完成后，进程就可利用修改后的页表形成所要访问数据的内存地址

先缺页中断，后续处理由缺页中断处理程序负责

页面置换算法

进程运行时，若其访问的页面不在内存中而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区（感觉有点问题，因为脏页才需要写回）

好的页面置换算法应有较低的页面更换频率

最佳置换算法 OPT

换出以后永不使用或最长时间内不再被访问的页面

理想算法（因为无法预知未来），无法实现

能得到最低的缺页率，故用来评价其他算法

先进先出页面置换算法 FIFO

优先淘汰最早进入内存的页面，即在内存中驻留时间最久的页面

实现简单（队列）

算法性能差：算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问

可能出现 Belady 异常：给进程分配的物理块增多，缺页率反而上升（只有 FIFO 算法可能出现）

最近最久未使用算法 LRU

选择最近最长时间未访问的页面予以淘汰（认为它们在最近的将来也不太可能会被访问）

为每个页面设置访问字段，来记录该页距离上次被访问的时间

算法性能较好，性能接近于 OPT 算法：利用“最近的过去”作为“最近的将来”的近似，以“过去”预测“未来”

属于堆栈类算法（其实也是变相的 FIFO，只不过用栈实现，淘汰栈底）

实现起来开销大，并需要寄存器和栈的硬件支持。开销大的原因是需要对所有的页排序，而需要硬件支持只是耗费高的体现而非原因

时钟置换算法 CLOCK

某进程的所有页面（或整个内存的页帧）排成一循环缓冲链

选择将最近未使用的页面置换出去，因此又称最近未用算法 NRU

  • 简单 CLOCK 算法

    给内存中的每帧关联一个附加位，称为使用位 U（应该是页表项的访问位）

    根据置换策略（全局/局部），将候选页通过指针链接成一个循环队列，并用一个替换指针与之关联

    当某页被装入或访问时，U 置 1

    置换时顺序查找循环链：U 为 0，置换该页；U 为 1，改置为 0；替换指针前移

  • 改进型 CLOCK 算法

    除考虑页面使用情况外，还增加了置换代价

    增加修改位 M，某页被修改时置 1

    增加使用的位数可使时钟算法更有效（位数减少至 0 则退化为 FIFO）

    注意：第一轮扫描不改变访问位，第二轮扫描期间再将所有扫描过的页面访问位置 0。若第二轮也失败，此时所有帧的访问位都已复 0，则在接下来的扫描中一定能找到被淘汰的页

    U 指示未来被访问的可能性；M 代表置换代价，被修改过的页在置换前还须写回，造成时间开销。之所以 U=0，M=1 的页要比 U=1，M=0 的页优先被淘汰，是因为 U 为首要考虑因素（操作系统中的页面置换算法都有一个原则，即尽可能保留访问过的页面）。虽然置换这样的页必须先写回，但根据局部性原理，它不会很快被用到

抖动与工作集

  • 系统并发度与处理机利用率

  • 抖动(thrashing)/颠簸

    频繁的页面调度行为（换页时间 ＞ 执行时间）

    在页面置换过程中，一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存

    可以简单理解为缺页率高

    根本原因：系统中同时运行的进程太多，使得分配给每个进程的物理块太少，不能满足进程正常运行的基本要求

    主要原因：页面置换算法不合理

  • 抖动的解决

    1. 挂起一些进程，释放它们的帧（减少多道程序的度数）
    2. 增大内存的容量

    增大交换区和使用更快的交换区都没用

  • 工作集

    工作集 W：在某段时间间隔 Δ 里，进程实际所要访问页面的集合

    一般来说，工作集 W 可由时间 t 和工作集窗口大小 Δ 来确定，即工作集 W 为 t 时刻进程的工作集为在时间间隔 (t-Δ, t) 中引用页面的集合

    实际应用中，工作集窗口会设置的很大，即对于局部性好的程序，工作集大小一般会比工作集窗口小很多

    工作集反映了进程在接下来一段时间内很有可能会频繁访问的页面集合

    为了防止抖动，一般来说分配给进程的物理块数（即驻留集大小）要大于工作集大小

  • 稳定阶段（局部性阶段）与瞬变阶段交替出现

    在瞬变阶段，来自原局部性阶段中的某些页仍留在窗口 Δ 中，导致访问新页时工作集大小剧增。当窗口滑过这些页访问后，工作集大小减小，直到它包含那些满足新的局部性的页

  • 工作集模型（工作集策略）

    1. 原理

      让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块

      落在工作集内的页面需要调入驻留集中，而落在工作集外的页面可从驻留集中换出

      若还有空闲物理块，则可再调一个进程到内存

      若所有进程的工作集之和超过了可用物理块总数，则操作系统会暂停一个进程，将其页面调出并将物理块分配给其他进程，防止出现抖动现象

    2. 问题

      过去未必能预示将来，工作集大小和成员会随时间变化

      记录工作集变化要求开销太大

      Δ 的最优值是未知的

内存映射文件

将磁盘文件全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，便可以直接访问被映射的文件，而不必执行文件 I/O 操作，也无须对文件内容进行缓存处理

而使用内存映射文件所进行的任何实际交互都是在内存中进行的，并且是以标准的内存地址形式来访问的

磁盘的周期性分页是由操作系统在后台隐蔽实现的，对应用程序而言是完全透明的。系统内存中的所有页面都由虚拟存储器负责管理，虚拟存储器以统一的方式处理所有磁盘 I/O。当进程退出或显式地解除文件映射时，所有被改动的页面都会被写回磁盘文件

多个进程允许并发地映射同一文件，以便允许数据共享

实际上很多时候共享内存就是通过内存映射实现的。进程可以通过共享内存来通信，而共享内存是通过映射相同文件到通信进程的虚拟地址空间实现的，内存映射文件充当通信进程之间的共享内存区域

内存映射文件分为两种类型：

  1. 持久化内存映射文件

    持久化文件是与磁盘上的源文件相关联的内存映射文件。当最后一个进程处理完文件或显式地解除文件映射时，所有被改动的页面会被写回磁盘文件。此类内存映射文件适用于处理非常大的源文件

  2. 非持久化内存映射文件

    非持久化文件是不与磁盘上的文件相关联的内存映射文件。当最后一个进程处理完文件时，数据会丢失，且文件被垃圾回收器回收。此类文件适合创建共享内存，以进行进程内通信(IPC)

内存映射文件总结：

虚拟存储器性能影响因素

缺页率是影响虚拟存储器性能的主要因素（缺页率高即为抖动）

缺页率又受到页面大小、分配给进程的物理块数即驻留集（取决于工作集）、页面置换算法以及程序的编制方法的影响

  • 页面较大：缺页率低、减少页表长度；页内碎片增大

    页面较小：减少了内存碎片，有利于提高内存利用率；使每个进程要求较多的页面，导致页表过长，占用大量内存

  • 分配给进程的物理块数越多，缺页率就越低，但是当物理块超过某个数目时，再为进程增加物理块对缺页率的改善是不明显的，只是浪费内存空间。只要保证活跃页面在内存中，保持缺页率在一个很低的范围即可

  • 好的页面置换算法可使进程在运行过程中具有较低的缺页率

    选择 LRU、CLOCK 等置换算法，将未来有可能访问的页面尽量保存在内存中，从而提高页面的访问速度

  • 编写程序的局部化程度越高，执行时的缺页率就越低

    如果存储采用的是按行存储，访问时就要尽量采用相同的访问方式，避免按列访问造成缺页率过高的现象

另外磁盘 I/O 次数对虚拟存储器性能造成影响。脏页攒够一定数量再成批一次换出，不仅可以显著较少磁盘 I/O 的次数，即较少换出脏页的开销，若有进程在这批脏页还未写回磁盘时需要再次访问这些页面时，还可以减少页面从磁盘读入内存的频率，减少页面换进的开销

地址翻译

系统参数

存储器按字节编址

虚拟地址 14 位，物理地址 12 位

有一个 TLB 与一个 data Cache

页面大小 64B

TLB 四路组相联，共 16 个条目

data Cache 物理寻址、直接映射，行长 4 B，共 16 行（一行一组，可视为 16 组）

地址结构分析

页面大小 64B = $2^6$B → 页内偏移 6 位 → 虚拟页号 8 位、物理页号 6 位

TLB 四路组相联，共 16 条，即分为 4 = $2^2$ 组 → TLB 组号 2 位、标记位数 = 虚拟页号 8 位 - 组号 2 位 = 6 位

data Cache 行长 4 = $2^2$ B → 行内偏移 2 位

data Cache 虽是直接映射，但这里看作一路组相连映射，16 行即为 16 = $2^4$ 组 → Cache 组号 4 位、标记位数 = 物理地址 12 位 - 行内偏移 2 位 - 组号 4 位 = 6 位

数据内容

访问过程

以访问虚拟地址 0x03d4、0x00f1、0x0229 为例

1）首先需要将虚拟地址转化为物理地址，先快表后慢表。虚拟地址化为二进制形式：

0x03d4 TLB 组索引为 3，TLB 标记为 03H，查 TLB 发现有匹配项且有效位为 1，得到物理页号 0D，拼接页内地址后得到物理地址 0x354

0x00f1 TLB 组索引为 3，TLB 标记为 00H，TLB 查无此项，再用虚拟页号 03H 去内存中的页表找，匹配的页表项有效位为 1，得到物理页号 02H，拼接页内地址后得到物理地址 0x0b1

0x0229 TLB 组索引为 0，TLB 标记为 02H，TLB 查无此项，再用虚拟页号 08H 去内存中的页表找，匹配的页表项有效位为 0，页面不在内存中，产生缺页中断

2）接下来通过物理地址访问数据，先 Cache 后主存。物理地址的二进制形式为：

0x354 Cache 组号为 5，Cache 标记为 0D，查 Cache 发现有匹配行且有效位为 1，说明要访问的数据在此行中，再根据行内偏移 0 得到要访问的数据内容为 36H

0x0b1 Cache 组号为 C，Cache 标记为 02H，查 Cache 发现有匹配行但有效位为 0，说明要访问的数据不在 Cache 中，只能去主存中取物理页号为 2、页内偏移为 31H 的内容