type
status
date
slug
summary
tags
category
icon
password
本篇主要是目的是进行个人知识梳理和总结，不含技术性实现的详细内容，若涉及实际技术性操作的内容，会另起一文。
本篇主要参考王道考研书籍，但内含大量个人思考。
内存管理概述
是什么？
在计算机中，内存与系统处理器和存储盘（硬盘或固态硬盘）协同工作来访问和使用数据。
RAM（发音同 ram），是指随机存取存储器（random access memory，RAM）又称作“随机存储器”，是与CPU直接交换数据的内部存储器，也叫主存(内存)。它可以随时读写，而且速度很快，通常作为操作系统或其他正在运行中的程序的短时间临时数据存储媒介。计算机首先从存储盘将用户请求的程序或文档加载到内存，然后从内存中访问每条信息。
- DRAM:动态随机存取存储器，动态部分来自不断刷新的数据。
- SRAM:静态随机存取存储器，静态指的是信息不需要刷新。SRAM 速度快，但价格也较高。
直观来讲，我们购买的手机中8G，16G就是指的内存的大小，许多个RAM存储器构成的集成电路板就是我们常说的内存条。
而我们今天要谈到的内存管理，借用维基百科的话来讲，是指软件运行时对计算机内存资源的分配和使用的技术。其最主要的目的是如何高效、快速的分配，并且在适当的时候释放和回收内存资源。
为什么？
首先，我们要了解一下存储器的层次结构。
显然，CPU比磁盘速度要快很多，但是如果我们全部选用速度最快的RAM，设备的生产成本又太高了。因此，我们用RAM作为缓存中介，将CPU经常和当下运行的内容放到缓存里，而暂时不用的就保存到磁盘里，这样，我们在速度、容量、造价三者之间就可以实现一定的平衡。
但与此同时，我们也需要考虑一个问题，如何进行内存管理，才能优化内存的使用，提高系统的性能和稳定性。这也就是操作系统中内存管理的意义所在。
怎么做？
根据需求分析的方法，我们来浅浅分析一下内存管理需要达到什么目的。
1.我们在创建进程时，所有内容（程序和数据）都需要标志好一个地址才能被找到和再次使用，因此，我们需要实现内存地址的查找。
- 针对内存地址，我们提出了直接查找和间接查找两种思路。
- 对于直接查找，也就是直接选择物理地址，我们得到一种程序装入方式“绝对装入”，这种方式只适用于单道程序环境，在编译（汇编）时给出绝对地址。
- 对于间接查找，我们给出逻辑地址这一概念（见下文前置知识），程序经过编译和链接后的始地址为0，程序所有的指令和数据都是相对于这个始地址而言的。
- 由此我们在装入时对目标程序中的相对地址（逻辑地址）修改为绝对地址（物理地址），称为重定位，又称静态重定位。
- 而我们在动态运行时装入则称为动态重定位，当程序执行时才进行地址转换（允许程序在内存中移动）。相比静态重定位而言，这种方法可以将程序分配到不连续的存储区，根据需要动态申请分配内存，便于程序段的共享。同样的，一般动态重定位需要硬件地址变换机构，系统中只有一个重定位寄存器，每次切换进程时都需要保存和恢复该寄存器的值。
MMU（Memory Management Unit，内存管理单元）是一种用于内存管理的硬件模块，用于在CPU和内存之间实现虚拟内存管理。其主要功能是将虚拟地址转换为物理地址，同时提供访问权限的控制和缓存管理等功能，同时MMU也可以通过页面表（Page Table）实现虚拟内存管理。
- 更多的，装入后如何保存，比如我们有一面书柜，地址是给每个柜口贴上标签便于查找，装入是存放，那么如何装入呢，我们装入的内容如何排布才能便于之后的存取，保证存取速度的同时也最大化的利用好空间，这就涉及到我们之后要谈到的内存空间的分配管理方式。
逻辑地址：逻辑地址（Logic Address）是指由程序产生的与段相关的偏移地址部分。比如，在C程序中，可以使用&操作读取指针变量本身的值，实际上这个值就是逻辑地址。它是相对于你当前进程数据段的地址，和绝对物理地址不相干。即逻辑地址是相对于程序而言的。物理地址：物理地址（Physical Address）是指出目前CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果地址。线性地址：线性地址（Linear Address）是逻辑地址到物理地址变换之间的中间层。程序代码会产生逻辑地址，或说是段中的偏移地址，加上相应段的基地址就生成了一个线性地址。如果启用了分页机制，那么线性地址能再经变换以产生一个物理地址。若没有启用分页机制，那么线性地址直接就是物理地址。即 逻辑地址 ——> 线性地址 ——> 物理地址。
2.当我们所需的内容存到存储器之后，我们还要保证存好的内容不会被随意的修改或删除，因此我们还要对内存进行保护，保护其不被修改同时也不修改别的内容，我们将其称之为内存保护。
3.对于程序A和程序B，他们有同一个头文件“math.h”，难道我们在运行的时候要给这相同的内容赋予两个空间段吗？这显然浪费了存储空间。但我们之前又提到，要对存储的内容进行保护，这就产生了矛盾。由此，我们提出内存共享机制，使程序A和程序B可以共享同一段内存空间。注意：共享内存只适用于那些只读的区域，对于写，则由操作系统提供同步和互斥工具来实现，当然有时我们也采用内存映射文件来解决可能造成的冲突问题。
4.现代物理内存的容量增长已经非常快速了，然而还是跟不上应用程序对主存需求的增长速度，对于应用程序来说内存还是可能会不够用，因此我们便需要一种方法来解决这两者之间的容量差矛盾。为了更高效地管理内存并尽可能消除程序错误，现代计算机系统对物理主存 RAM 进行抽象，实现了虚拟内存 (Virtual Memory, VM)技术。
接下来，我们将详细介绍内存管理实现的具体方式方法。
内存空间的连续分配管理方式
为了能将用户程序装入内存，必须为它分配一定大小的内存空间。连续分配方式是最早出现的一种存储器分配方式，分配的策略为一个用户程序分配一个连续的内存空间。程序中代码或数据的逻辑地址相邻，内存空间分配时物理地址的相邻。连续分配方式可分为四类：单一连续分配、固定分区分配、动态分区分配以及动态可重定位分区分配算法四种方式。
此处会涉及到内存碎片的概念内部碎片:是指分配给进程的内存空间有部分没有用上;外部碎片:指的是内存中某些空间分区由于太小导致难以使用。固定分区会产生内部碎片，动态分区会产生外部碎片；分页存储有内部碎片，分段存储有外部碎片，段页式存储有内部碎片；
1.单一分配方式
在单道程序环境下经常使用单一连续分配，这种方式把内存分为系统区和用户区两部分。其中系统区仅提供给 OS 使用，通常使用内存的低址部分。在用户区内存中，仅装有一道用户程序，整个内存的用户空间由该程序独占。
优点：
- 简单、无外部碎片：可以采用覆盖方式扩充内存
- 不需要进行内存保护，因为内存中永远只有一道程序
缺点：
- 只能用于单用户、单任务的操作系统中
- 有内部碎片
- 存储器的利用率较低
2.固定分区分配
固定分区存储管理
固定分区分配是最早的、最简单的一种可运行多道程序的内存管理方式，它将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该分区。
划分分区的方法
1.分区大小相等：每个分区大小相同，在系统启动时分配完毕，且运行期间保持不变；每次给进程分配一整块区域，因此进程大小必须不大于分区的大小。
2.分区大小不等：与上不同点在于分配时根据进程的大小在空闲分区选择一个大小合适的分区，在系统启动时分配完毕，且运行期间保持不变；每个进程的分区可不等长。优缺点同上。
- 优点：系统维护管理信息少，只需一个固定行数的表格，记载分区使用情况；内存分配算法简单
- 缺点：不同进程需要空间不同，内碎片多，浪费空间；分区总数固定，限制并发执行的程序数量
内存分配管理
进行内存分配时通常将分区按其大小进行排队，并建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。当有一用户程序要装入时，由内存分配程序依据用户程序的大小检索该表，找出一个能满足要求的、尚未分配的分区分配给该程序，然后将该表项中的状态置为“已分配”。若未找到大小足够的分区，则拒绝为该用户程序分配内存。回收内存时，只需要将对应表项的状态置为“未分配”即可。
例如一张分区使用表如下：
分区号 | 大小 | 起始地址 | 状态 |
1 | 12 | 20 | 已分配 |
2 | 32 | 32 | 已分配 |
3 | 64 | 64 | 未分配 |
4 | 128 | 128 | 已分配 |
实际存储空间的分配情况可能如下：
3.动态分区分配
动态分区分配又称为可变分区分配，在系统运行中，根据每个进程需要的空间大小确定分区大小。通过空闲分区链表进行组织。
优点：
- 并发执行程序数量不受限制，只取决于是否有大小合适的内存块可以分配
- 分区大小可变，进程在内存的起始位置可变，空闲分区可合并，更灵活，内存利用率更高；
- 无内部碎片；
缺点：管理空闲块的复杂度增加；分配算法的时间开销增加，可能需遍历多次才能找到合适的内存块
- 有外部碎片，外部碎片过多，可能触发“紧凑”，系统开销大；
- 一个进程需要占用连续的内存空间，相比于离散分配而言，内存利用率低（正是由于连续分配，所以容易产生外部碎片）；
数据结构
为了实现动态分区分配，系统中必须配置相应的数据结构来描述空闲分区和已分配分区的情况。常用的数据结构有以下 2 种形式，第一种是空闲分区表，它在系统每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项。
分区号 | 大小 | 起始地址 | 状态 |
1 | 12 | 20 | 空闲 |
2 | 32 | 32 | 空闲 |
3 | 64 | 64 | 空闲 |
4 | 128 | 128 | 空闲 |
第二种是空闲分区链，每个分区的起始部分设置一些用于控制分区分配的信息，通过前、后向链接指针将所有的空闲分区链接成一个双向链。
分配内存
系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为 u.size，表中每个空闲分区的大小可表示为 m.size。若 m.size - u.size ≤ size(size 是事先规定的不再切割的剩余分区的大小)，说明多余部分太小可不再切割，将整个分区分配给请求者。如果多余部分超过 size，便从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中，然后将分配区的首址返回给调用者。
例如当前的内存分配状态如图所示，内存分配表如图所示。
分区号 | 大小 | 起始地址 | 状态 |
1 | 20 | 5 | 空闲 |
2 | 5 | 35 | 空闲 |
3 | 15 | 55 | 空闲 |
现在需要插入大小为 5M 的进程三，通过某种算法后插入分区 1，修改后的内存分配表和内存状态如下。
分区号 | 大小 | 起始地址 | 状态 |
1 | 15 | 10 | 空闲 |
2 | 5 | 35 | 空闲 |
3 | 15 | 55 | 空闲 |
如果通过某种算法后插入分区 2，修改后的内存分配表可以把分区 2 删除。
分区号 | 大小 | 起始地址 | 状态 |
1 | 20 | 5 | 空闲 |
3 | 15 | 55 | 空闲 |
回收内存
当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一。
情况一：回收区与插入点前有一个空闲分区 F1。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区 F1 的大小。例如内存分配表和内存状态如下，此时要回收进程 1。
分区号 | 大小 | 起始地址 | 状态 |
1 | 20 | 5 | 空闲 |
3 | 15 | 55 | 空闲 |
将回收的空间和分区 1 和并，然后修改分区大小即可。
分区号 | 大小 | 起始地址 | 状态 |
1 | 30 | 5 | 空闲 |
3 | 15 | 55 | 空闲 |
情况二：回收分区与插入点的后有一空闲分区 F2，此时也可将两分区合并形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。例如内存分配表和内存状态如下，此时要回收进程 2。
分区号 | 大小 | 起始地址 | 状态 |
1 | 20 | 5 | 空闲 |
3 | 15 | 55 | 空闲 |
将回收的空间和分区 3 和并，除了修改分区大小还要修改起始地址。
分区号 | 大小 | 起始地址 | 状态 |
1 | 20 | 5 | 空闲 |
3 | 30 | 40 | 空闲 |
情况三：回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并，使用 F1 的表项和 F1 的首址并取消F2的表项，大小为三者之和。例如内存分配表和内存状态如下，此时要回收进程 1。
分区号 | 大小 | 起始地址 | 状态 |
1 | 15 | 10 | 空闲 |
2 | 5 | 35 | 空闲 |
3 | 15 | 55 | 空闲 |
将回收的空间和分区 1、2 和并，然后修改分区大小即可。
分区号 | 大小 | 起始地址 | 状态 |
1 | 30 | 10 | 空闲 |
3 | 15 | 55 | 空闲 |
情况四：第四种情况是回收区既不与 F1 邻接又不与 F2 邻接，这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。例如内存分配表和内存状态如下，此时要回收进程 3。
分区号 | 大小 | 起始地址 | 状态 |
1 | 20 | 5 | 空闲 |
3 | 15 | 55 | 空闲 |
这时就需要向内存分配表加入一个新条目，并且写上大小和起始地址。
分区号 | 大小 | 起始地址 | 状态 |
1 | 20 | 5 | 空闲 |
3 | 15 | 55 | 空闲 |
2 | 5 | 35 | 空闲 |
基于顺序搜索的分配算法
为了实现动态分区分配，通常是将系统中的空闲分区链接成一个链。基于顺序搜索的分配方式是依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区，主要有如下四种算法。
1、首次适应算法First Fit：空闲分区列表按地址顺序（从小到大）排序；分配过程中，搜索一个合适的分区；释放分区时，检查是否可与临近的空闲分区合并。
- 优点：简单；在高地址空间有大块的空闲分区
- 缺点：存在外部碎片；分配大块时较慢；每次查找均从低址部分开始，增加开销
2、邻近适应算法Next Fit：由于上述算法每次都需从头检查空闲分区，浪费时间。因此下一个匹配算法就是操作系统记住接下来该检查的空闲分区的位置，给进程分配分区时，系统从记录的分区开始依次向后查找直到遇到能用的分区为止，若到链表尾还未找到就从头开始。
- 优点：算法能使内存中的空闲分区分布得更均匀，减少了查找空闲分区时的开销。
- 缺点：导致高地址的大分区可能被划分为小分区来使用，使缺乏大的空闲分区给较大的进程。
3、最佳适应算法：空闲分区列表按由大到小排序；分配时，查找一个合适的分区；释放时，查找并合并临近的空闲分区。
- 优点：适合分配尺寸较小的进程(可避免大的空闲分区被拆分；可减小外部碎片的大小；相对简单)
- 缺点：外部碎片；释放分区较慢；容易产生较多无用小碎片
4、最坏适应算法：空闲分区列表按由大到小排序；分配时，选最大的分区；释放时，检查是否可与临近的空闲分区合并，进行可能的合并，并调整空闲分区列表顺序。
- 优点：中等大小的分配较多时，效果最好；避免出现太多的小碎片
- 缺点：释放分区较慢；外部碎片；容易破坏大的空闲分区，后续难以分配大分区
基于索引搜索的分配算法
基于顺序搜索的动态分区分配比较适用于不太大的系统，当系统很大时系统中的内存分区可能会很多，空闲分区链就可能很长，这时采用顺序搜索分区方法可能会很慢。为了提高搜索空闲分区的速度，在大、中型系统中往往会采用基于索引搜索的动态分区分配算法。
1、快速适应算法：快速适应(quick fit)算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。同时在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。该算法在搜索时先根据进程的长度，从索引表中去寻找到能容纳它的最小空闲区链表，然后从链表中取下第一块进行分配即可。
- 该算法在进行空闲分区分配时不会对任何分区产生分割，所以能保留大的分区，也不会产生内存碎片。优点是查找效率高，主要缺点在于分区归还主存时的算法复杂，系统开销较大。此外该算法在分配空闲分区时是以进程为单位的，一个分区只属于一个进程，因此会存在内部碎片。
2、伙伴系统:伙伴系统(buddy system)算法规定无论已分配分区或空闲分区，其大小均为 2 的 k 次幂(k 为整数，1 ≤ k ≤ m)。将这些空闲分区按分区的大小进行分类，对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。
当需要为进程分配一个长度为 n 的存储空间时，首先计算一个 i (2^i-1 < n ≤ 2^i)，然后在空闲分区大小为 2^i 的空闲分区链表中查找。若找到即把该空闲分区分配给进程。如果找不到表明长度为 2^i 的空闲分区已经耗尽，则在分区大小为 2^i+1 的空闲分区链表中寻找。若存在 2^i+1 的一个空闲分区，则把该空闲分区分为相等的两个分区，其中的一个分区用于分配，而把另一个加入分区大小为 2^i 的空闲分区链表中。如果还是找不到就继续搜索，以此类推。
在伙伴系统中，对于一个大小为 2^k，地址为 x 的内存块，其伙伴块的地址则用 buddyk(x)表示，其通式为：
- 在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比快速适应算法差.但由于它采用了索引搜索算法，比顺序搜索算法好。由于对空闲分区进行合并，减少了小的空闲分区，提高了空闲分区的可使用率，故优于快速适应算法，比顺序搜索法略差。
3、哈希算法
哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律建立哈希函数。构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小通过哈希函数计算，从中得到相应的空闲分区链表，实现最佳分配策略。
动态可重定位分区分配
紧凑
连续分配方式的一个重要特点是一个系统或用户程序必须被装入一片连续的内存空间中，当一台计算机按照此方法分配了较多的内存空间后，将会分割出许多小的分区。这会导致内存空间缺乏大分区，即使这些分散的许多小分区的容量总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。例如如图所示的 3 个空闲分区的大小总合是 10 M，但是由于这些空间并不是邻接的，所以会导致无法插入一个 10 M 大小的程序。
若想把大作业装入，可将内存中的所有作业进行移动，使它们全都相邻接，这样可把原来分散的多个空闲小分区拼接成一个大分区。这种通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区的方法称为“拼接”或“紧凑”。
虽然“紧凑”能获得大的空闲空间，但是经过紧凑后的用户程序在内存中的位置发生了变化，就需要对程序和数据的地址加以修改(变换)。系统每“紧凑”一次，就要对移动了的程序或数据的地址进行修改，这个功能不仅是实现复杂，而且还大大地影响到系统的效率。
动态重定位
为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持。需要在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。地址变换过程是在程序执行期间的，故称为动态重定位。当系统对内存进行了“紧凑”时，不需对程序做任何修改，只要用该程序在内存的新起始地址去置换原来的起始地址即可。
内存空间的非连续分配管理方式
非连续分配方式允许一个程序分散的装入不相邻的内存分区中，根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。
连续内存分配的缺点
- 分配给一个程序的物理内存必须是连续的
- 内存分配的动态修改困难
- 内存利用率较低
- 有外碎片/内碎片问题
非连续内存分配的优点
- 提高内存利用效率和管理灵活性
- 分配给一个程序的物理内存是非连续的
- 允许共享代码和数据(共享库等)
- 支持动态加载和动态链接
非连续分配需要解决的问题
- 如何实现虚拟地址和物理地址的转换
- 软件实现 （灵活，开销大）
- 硬件实现 （够用，开销小）
非连续分配的硬件辅助机制
- 如何选择非连续分配中的内存分块大小
- 段式存储管理 （segmentation）
- 页式存储管理 （paging）
1.基本分页存储管理
固定分区会产生内部碎片，动态分区会产生外部碎片，两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生，这就引出了分页思想：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。（相对而言有更小的内部碎片）
分页存储管理方式中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理和请求分页存储管理方式。
1.1. 页式存储管理的几个基本概念
1、页面和页面大小
分页存储管理将进程的逻辑地址分为大小相等的页，将内存的物理地址空间分成与页相同大小的块，因此页内地址与物理块内地址一一对应。系统在为进程分配内存时，将进程的各个页分别装入多个可以不相邻的物理块中
进程中的块称为页(Page)，内存中的块称为页框（Page Frame，或页帧）。外存也以同样的单位进行划分，直接称为块(Block)。进程在执行时需要申请主存空间，就是要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。
为方便地址转换，页面大小应是2的整数幂。同时页面大小应该适中，如果页面太小，会使进程的页面数过多，这样页表就过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入/换出的效率；页面过大又会使页内碎片增大，降低内存的利用率。所以页面的大小应该适中，考虑到耷间效率和时间效率的权衡。
2、地址结构
地址结构包含两部分：前一部分为页号P，后一部分为页内偏移量W。地址长度为32 位，其中0~11位为页内地址，即每页大小为4KB；12~31位为页号，地址空间最多允许有220页。
分页地址的逻辑地址结构：
| （12~32位）页号 P | （0~11位） 位移量 W（即业内地址d）|3、页表
根据地址，就已经可以知道页号和页内偏移量，剩下还有一个工作就是根据页号找到页号对应页面在内存中的起始地址。
对于每一个进程，可以维护一张页表，用它来记录页面号（页号）与页框号（块号）的映射关系，可以根据页号找到页号指代页面在内存中对应页框的编号：
根据地址知道页号后，从页表中找出页号对应的块号，再用块号 * 页面/页框大小，即可算出块的起始地址，再用起始地址加上偏移量，即可算出物理地址。
1.2. 基本地址变换机构
地址变换机构的任务是将逻辑地址转换为内存中物理地址，地址变换是借助于页表实现的。下图给出了分页存储管理系统中的地址变换机构。
在系统中通常设置一个页表寄存器(PTR)，存放页表在内存的始址F和页表长度M。进程未执行时，页表的始址和长度存放在进程控制块中，当进程执行时，才将页表始址和长度存入页表寄存器。设页面大小为L，逻辑地址A到物理地址E的变换过程如下：
- 计算页号P(P=A/L)和页内偏移量W(W=A%L)。
- 比较页号P和页表长度M，若P >= M则产生越界中断，否则继续执行。
- 页表中页号P对应的页表项地址 = 页表起始地址F + 页号P * 页表项长度，取出该页表项内容b，即为物理块号。
- 计算E=b*L+W，用得到的物理地址E去访问内存。
以上整个地址变换过程均是由硬件自动完成的。
例如，若页面大小L为1K字节，页号2对应的物理块为b=8，计算逻辑地址A=2500 的物理地址E的过程如下：P=2500/1K=2，W=2500%1K=452，查找得到页号2对应的物理块的块号为 8，E=8*1024+452=8644。
下面讨论分页管理方式存在的两个主要问题：
- 每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低；
- 每个进程引入了页表，用于存储映射机制，页表不能太大，否则内存利用率会降低。
1.3. 具有快表（TLB）的地址变换机构
由上面介绍的地址变换过程可知，若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存：一次是访问页表，确定所存取的数据或指令的物理地址，第二次才根据该地址存取数据或指令。显然，这种方法比通常执行指令的速度慢了一半。
为此，在地址变换机构中增设了一个具有并行查找能力的高速缓冲存储器——快表，又称联想寄存器(TLB)，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，主存中的页表也常称为慢表，配有快表的地址变换机构如下图所示。
在具有快表的分页机制中，地址的变换过程：
- CPU给出逻辑地址后，由硬件进行地址转换并将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较。
- 如果找到匹配的页号，说明所要访问的页表项在快表中，则直接从中取出该页对应的页框号，与页内偏移量拼接形成物理地址。这样，存取数据仅一次访存便可实现。
- 如果没有找到，则需要访问主存中的页表，在读出页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换。
注意：有些处理机设计为快表和慢表同时查找，如果在快表中查找成功则终止慢表的查找。
一般快表的命中率可以达到90%以上，这样，分页带来的速度损失就降低到10%以下。快表的有效性是基于著名的局部性原理。
有效访问时间（Effective Access Time）指从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据的时间总和。
假设一次访存时间为 t，查找快表时间为 q，快表命中率为 a，则
- 基本的地址变换机构的有效时间是 2t
- 具有快表的地址变换机构的有效时间是 2t+p-at
例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构，访问一次快表耗时1us，访问一次内存耗时100us，若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少？答：（1+100）0.9+（1+100+100）.0.1 = 111us如果是快表和页表同时查找，应该是（1+100）*0.9+（100+100）*0.1 = 110.9us若不采用快表机制，则需要100+100 = 200us
1.4. 两级页表
逻辑地址大（例如32位）的分页系统，每个进程页表的页表项数会很多（假设页面大小不变），需要采用多级页表，分散存储页表（仅部分调入内存）。
逻辑地址结构：两级页表的逻辑地址结构：
| 外层页号 P1 | 外层页内地址 P2 | 页内地址 d |在原来一级页表地址变换机构的基础上，需要新增一外部页表（以 P1为索引）、一外层页表寄存器（存放外存页表始址）。
对于正在运行的进程，其外层页表需调入内存，其页表则只需调入几页，在外层页表增设一状态位（用以表示页表是否调入内存）。
1.5. 反置页表
通常系统允许一个进程的逻辑地址空间很大，因此页表项很多，占用内存很大。为减少页表占用内存空间，引入反置页表。
反置页表为每一个物理块设置一个页表项，并将它们按物理块的编号排序，其中的内容是页号和其所隶属进程的标识符。
反置页表进行地址变换是根据进程标识符和页号检索反置页表，若匹配，则页表项的序号即为物理块号；否则表明此页为调入内存。
反置页表也可采用两级页表，外部页表与传统页表页表一样，其表项是每个也在外存的物理地址，通过外部页表也将所需页面调入内存。
2.基本分段存储管理
引入段式存储管理，主要是为了满足用户的一下需求：方便编程、分段共享、分段保护、动态链接和动态增长。
2.1. 分段
分段地址中的逻辑地址为：
| 段号 | 段内地址 |每个段都是从0开始编址，并采用一段连续的地址空间，段长由相应的逻辑信息组的长度决定（各段段长不同）。每个段即包含了一部分地址空间，又标识了段与段之间的逻辑关系。
2.2. 段表
分段存储管理系统为每个段分配一个连续的分区，进程的各个段可离散地装入内存的不同位置，用一张段映射表（段表）记录每段在内存的起始地址（基址）和段的长度。在配置了段表后，执行中的进程可通过逻辑地址中的段号来查询段表，找到段的对应内存区。
段表表项的结构为：
| 段长 | 基址 |2.3. 地址变换机构
与分页存储管理类似。
2.4. 信息共享
不同进程可共享同一段（物理内存），例如一些纯代码（程序中的指针、信号量、数组等可配以局部数据区，被进程私有），每个进程的段表中都建立该段的地址映射表项。
3.段页式存储管理
3.1. 分段、分页对比
3.2. 分段分页
用分段方法来分配和管理用户地址空间，用分页方法来管理物理存储空间。
页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。如果将这两种存储管理方法结合起来，就形成了段页式存储管理方式。
将用户程序分为若干段，在将每段分为若干个页。
逻辑地址为：
| 段号 S | 段内页号 P | 页内地址 W |3.3. 地址变换
为了实现地址变换，系统为每个进程建立一张段表，而每个分段有一张页表。段表表项中至少包括段号、页表长度和页表起始地址，页表表项中至少包括页号和块号。此外，系统中还应有一个段表寄存器，指出作业的段表起始地址和段表长度。
注意：在一个进程中，段表只有一个，而页表可能有多个。
在进行地址变换时，首先通过段表查到页表起始地址，然后通过页表找到页帧号，最后形成物理地址。如图所示，进行一次访问实际需要三次访问主存，这里同样可以使用快表以加快查找速度，其关键字由段号、页号组成，值是对应的页帧号和保护码。
内存空间的扩充
1.虚拟内存
1.1. 虚拟地址空间组成
用户空间：
- 代码段.text：存放程序执行代码的一块内存区域。只读，代码段头部还会包含一些只读的常量。
- 数据段.data：存放程序已初始化的全局变量和静态变量的一块内存区域。
- BSS段.bss：存放程序中未初始化的全局变量和静态变量的一块内存区域。
- 可执行程序运行时多出两个区域：堆区和栈区。
- 堆区：操作系统malloc动态申请内存。从低地址向高地址增长，连续空间。(开辟空间小于128K时，malloc底层调用brk()函数；大于128K，调用mmap())。—-malloc采用内存池管理方式，以减少内存碎片。具体实现为先申请大块内存作为堆区，然后将堆区分为多个内存块。当用户申请内存时，直接从堆区分配一块合适的内存块。采用隐式链表将所有空闲块联接，每个空闲块记录一个未分配的，连续的内存地址。
- 栈区：存储局部变量，函数参数值。从高地址向低地址增长，连续空间。
- 文件映射区：位于堆与栈之间。(mmap)内核空间：DMA区，常规区，高位区。
注：虚拟存储器的最大容量由计算机的地址结构决定，与主存容量和外存容量没有必然的联系。
1.2. 虚拟内存管理
操作系统为每一个进程分配一个独立的地址空间，这个地址空间是逻辑地址，称为虚拟内存。虚拟内存与物理内存存在映射关系，通过页表寻址完成虚拟地址和物理地址的转换。
虚拟地址空间被分割为多个块，每个块称为一个页或者页面；物理内存被分成和页面大小相同的多个区域，称为页框；程序在加载时，可将任何一个页面放入物理内存中的任何一个页框，然后由CPU硬件负责将虚拟地址映射到物理内存的地址。
程序的整个地址空间无需全部载入物理内存，可以有部分暂时存储在外存，等到需要时再换入内存；若程序引用到一部分不在物理内存中的虚拟地址时，就会发生缺页中断，由操作系统负责将缺失的页面加载到页框中，并重新执行失败的指令。
在请求分页式存储管理的系统中，地址变换过程可能会因为缺页、地址越界和访问权限错误等原因而产生中断。
2.请求分页管理
驻留集：预先给进程分配的物理块（大小等于页面）工作集：实际进程访问到的物理块驻留集大于工作集，工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合，因此，驻留集大小不能小于工作集，否则进程在运行的过程中会频繁换页。
2.1. 请求分页存储管理与基本分页存储管理的主要区别:
- 请求调页：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
- 页面置换：若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
2.2. 请求分页-缺页中断
缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此
属于内中断 一条指令在执行期间，可能产生多次缺页中断。(如:copy A to B，即将逻辑地址A中的数据复制到 逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断)
2.3. 请求分页-地址转换
- 只有“写指令”才需要修改“修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
- 和普通的中断处理一样，缺页中断处理依然需要保留CPU现场。
- 需要用某种“页面置换算法”来决定一个换出页面(下节内容)
- 换入/换出页面都需要启动慢速的I/O操作，可见，如果换入/ 换出太频繁，会有很大的开销。
- 页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中。
3.页面置换算法
在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。
页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。
页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。
在页面置换过程中，一种最最糟糕的情形是，刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出内存，这种频繁的页面调度行为称为抖动或者颠簸。无论采用什么页面置换算法，每种页面第一次访问时不可能在内存中，必然发生缺页，因此缺页次数必定大于或等于页号数。允许进程在所有页框中选择一个页面替换，而不管该页框是否已经分配给其他进程的置换方法是全局置换，它不受驻留集的影响。
3.1. 最佳置换算法(OPT)
选择以后再也不会用到的页面淘汰；如果都会用到，就选择那些再次使用的时间距离现在最远的页面淘汰。这是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。可作为评测其它淘汰策略的标准。
3.2. 先进先出置换算法(FIFO)
直接换出最早装入内存的页面。
FIFO算法还会产生当为进程分配的物理块增多，缺页次数不减反增的异常现象，称为Belady异常。
- 优点：简单
- 缺点：性能不好，该算法会将那些经常被访问的页面换出，导致缺页率升高。
- 适用场景：数据只用一次，将来不太可能使用；[redis]对数据的时效性有要求
3.3. 第二次机会置换算法(SCR)
对FIFO算法的改进，每个页面访问两次以后再淘汰。
当页面被访问 (读或写) 时设置该页面的R位（页面访问位）为1。需要替换的时候，检查最老页面的R位。如果R位是0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是1，就将R位清0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。
- 优点：在一定程度避免经常使用的页面置换出去
3.4. 时钟置换算法(Clock)
对第二次机会置换法的改进。前者需要在链表中移动页面，而时钟置换算法将页面保存在环形链表中，只需要后移队头指针，就相当于把原队头放到队尾。
- 优点：避免了移动链表节点的开销
3.5. 最近最少使用算法(LRU)
优先淘汰最久未被访问的页面。根据局部性原理，一个进程在一段时间内要访问的指令和数据都集中在一起。若一个页面很久没有被访问，那么将来被访问的可能性也比较小。
为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。
- 优点：性能较好，能够降低置换频率
- 缺点：存在缓存污染问题，即由于偶发性或周期性的冷数据批量查询，热点数据被挤出，导致缓存命中率下降
- 适用场景：访问分布未知的情况；[redis]要求热点数据有效；应用对缓存的访问符合二八定律
3.6. LRU- K
该算法核心思想是将“最近使用过1次”的判断标准拓展为“最近使用过K次”，LRU为LRU-1.
- 优点：能够降低缓存污染的问题
3.7. 最近未使用(NRU)——改进CLOCK
NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。
每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：
- R=0，M=0，没有被访问，没有被修改
- R=0，M=1，没有被访问，已被修改
- R=1，M=0，已被访问，没有被修改
- R=1，M=1，已被访问，已被修改
当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。
3.8. 最近最不经常使用算法(LFU)
优先淘汰最近访问频率最少的页面。
- 优点：避免缓存污染问题对LRU的命中影响
- 缺点：存在访问模式问题，即若访问内容发生较大变化，LFU需要用更长的时间来适应，导致缓存命中率下降；维护相关数据结构开销大
- 适用场景：数据的访问模式固定
3.9. 随机淘汰法(Random)
- 优点：实现简单，不需要保留有关访问历史记录的任何信息
- 适用场景：若应用对于缓存key的访问概率相等，则可用此算法
3.10. 工作集页面置换算法
在单纯的分页系统里，刚启动进程时，在内存中并没有页面。在CPU试图取第一条指令时就会产生一次缺页中断，使操作系统装入含有第一条指令的页面。其他由访问全局数据和堆栈引起的缺页中断通常会紧接着发生。一段时间以后，进程需要的大部分页面都已经在内存了，进程开始在较少缺页中断的情况下运行。这个策略称为请求调页(demand paging)，因为页面是在需要时被调入的，而不是预先装入。
大部分进程都表现出一种局部性访问行为，即在进程运行的任何阶段，它都只访问较少的一部分页面。一个进程当前正在使用的页面的集合称为它的工作集，如果整个工作集都被装入到了内存中，那么进程在运行到下一运行阶段(例如，编译器的下一遍扫描)之前，不会产生很多缺页中断。
所以不少分页系统都会设法跟踪进程的工作集，以确保在让进程运行以前，它的工作集就已在内存中了。该方法称为工作集模型。在进程运行前预先装入其工作集页面也称为预先调页(prepaging)。
为了实现工作集模型，操作系统必须跟踪哪些页面在工作集中。通过这些信息可以直接推导出一个合理的页面置换算法：当发生缺页中断时，淘汰一个不在工作集中的页面。为了实现该算法，就需要一种精确的方法来确定哪些页面在工作集中。根据定义，工作集就是最近A次内存访问所使用过的页面的集合。
一种常见的近似方法就是，不是向后找最近A次的内存访问，而是考虑其执行时间。一个进程从它开始执行到当前所实际使用的CPU时间总数通常称作当前实际运行时间。通过这个近似的方法，进程的工作集可以被称为在过去的实际运行时间中它所访问过的页面的集合。
该算法工作方式如下：假定使用硬件来置R位和M位，同样，假定在每个时钟滴答中，有一个定期的时钟中断会用软件方法来清除R位。每当缺页中断发生时，扫描页表以找出一个合适的页面淘汰之。在处理毎个表项时，都需要检査R位：
- 如果它是1，就把当前实际时间写进页表项的“上次使用时间”域，以表示缺页中断发生时该页面正在被使用。既然该页面在当前时钟滴答中已经被访问过，那么 很明显它应该出现在工作集中，并且不应该被删除。
- 如果R是0，那么表示在当前时钟滴答中，该页面还没有被访问过，则它就可以作为候选者被置换。为了知道它是否应该被置换，需要计算它的生存时间（即当前实际运行时间减去上次使用时间）。如果它的生存时间大于t，那么这个页面就不再在工作集中，而用新的页面置换它。扫描会继续进行以更新剩余的表项。
然而，如果R是0同时生存时间小于或等于t，则该页面仍然在工作集中。这样就要把该页面临时保留下来，但是要记录生存时间最长（“上次使用时间”的最小值）的页面。如果扫描完整个页表却没有找到适合被淘汰的页面，也就意味着所有的页面都在工作集中。在这种情况下，如果找到了一个或者多个R = 0的页面，就淘汰生存时间最长的页面。在最坏情况下，在当前时间滴答中，所有的页面都被访问过了（也就是都有R=l），因此就随机选择一个页面淘汰，如果有的话最好选一个干净页面。
3.11. 工作集时钟页面置换算法
当缺页中断发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法是比较费时的。有一种改进的算法，它基于时钟算法，并且使用了工作集信息，称为WSClock（工作集时钟）算法，由于它实现简单，性能较好，所以在实际工作中得到了广泛应用。
与时钟算法一样，所需的数据结构是一个以页框为元素的循环表，参见图a，最初，该表是空的。当装入第一个页面后，把它加到该表中。随着更多的页面的加入，它们形成一个环。每个表项包含来自基本工作集算法的上次使用时间，以及R位（已标明）和M位（未标明）。
与时钟算法一样，每次缺页中断时，首先检査指针指向的页面。如果R位被置为1，该页面在当前时钟滴答中就被使用过，那么该页面就不适合被淘汰。然后把该页面的R位置为0，指针指向下一个页面，并重复该算法。该事件序列之后的状态参见图b。
如果R位被置为0，如果页面的生存时间大于t并且该页面是干净的，它就不在工作集中，并且在磁盘上有一个有效的副本。申请此页框，并把新页面放在其中，如图d所示。另一方面，如果此页面被修改过，就不能立即申请页框，因为这个页面在磁盘上没有有效的副本。为了避免由于调度写磁盘操作引起的进程切换，指针继续向前走，算法继续对下一个页面进行操作。毕竟，有可能存在一个旧的且干净的页面可以立即使用。
3.12. 页面置换算法总结
算法 | 注释 |
OPT（最佳置换）算法 | 不可实现，但可用作基准 |
FIFO（先进先出）算法 | 开销小，但可能发生Belady现象 |
SCR（第二次机会）算法 | 比FIFO有较大的改善 |
时钟置换算法（Clock） | 现实 |
LRU（最近最少使用）算法 | 性能较好，但系统开销大 |
LRU- K | 将“最近使用过1次”的判断标准拓展为“最近使用过K次” |
Clock算法 | FIFO和LRU的折中，但开销也大 |
NRU（最近未使用）算法 | LRU的粗糙版 |
LFU（最近最不经常使用）算法 | LRU的相对粗略的近似 |
随机淘汰法 | 应用对于缓存key的访问概率相等的场景 |
工作集算法 | 实现起来开销很大 |
工作集时钟算法 | 好的有效算法 |
操作系统一般最常用的就是LRU算法；一般数据的访问模式也是随时间变化的，所以大多数缓存也都是LRU算法或其变种。
存储保护
本篇仅对内存保护做了简要的介绍，为更加详细的了解相关的内容，建议自行深入了解MPU。（等作者有空了再学学呜）
- 概念：在分配内存的时候，为了保证操作系统不受进程的影响，同时保证进程之间互不干扰，从而引出了内存保护。
- 注：即防止程序间相互越界访问，从而保证系统的正常运行和安全性。
- 方法：
- 在CPU中设置一堆上下限寄存器，存放用户作业在主存中的上限地址与下限地址。当CPU要访问内存的时候，分别用这两个地址和要访问的地址做比较。
- 重定位寄存器(基址寄存器)和界地址寄存器(限长寄存器)。重定位寄存器存储改作业的物理地址最小值；界地址寄存器存储改作业逻辑地址最大值。当CPU要访问内存的时候，分别用这两个地址数值之和与要访问的地址做比较。
内存共享
共享内存是指多个进程可以同时访问同一块内存区域的机制。在共享内存中，多个进程可以把同一块内存映射到它们自己的地址空间中，并且可以直接读写这块内存，就好像它们都拥有这块内存一样。这样可以实现进程间高效的数据共享，而不需要通过进程间通信机制进行数据传输，从而提高程序的性能。
- 每个进程都有一个虚拟地址空间，在地址空间的栈区和堆区中间有一块很大的空内存，名叫共享区。
- 在用户需要申请共享内存时，操作系统在物理内存中申请一块空间，然后映射到页表中，页表建立连接之后，再映射到进程各自的共享区中。两个进程共同映射的物理内存的操作就叫做共享内存。
需要注意的是：并不是所有进程的内存空间都适合共享，只有那些只读的区域才可以共享。
另外：基于共享内存我们还可以实现进程通信，操作系统可以提供同步互斥工具便于共享通信，内存映射文件也可以实现内存共享。
可重入程序：通过共享来使用同一块存储空间，或通过动态链接的方式将所需的程序段映射到相关进程中去，其最大的优点是减少了对程序的调入/调出，即减少了对换数量
内存扩充（补充）
在存储管理中，采用覆盖与交换技术的目的是节省内存空间。
1 覆盖技术
1.1 基本思想
由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序）， 因此可以把用户空间分成一个固定区和若干个覆盖区。
1.对于一个进程，不需要一开始就把程序的全部指令和数据都装入内存再执行。
2.程序划分为若干个功能上相对独立的程序段，按照程序逻辑结构让那些不需要同时执行的程序段共享同一块内存区。
3.当有关程序段的先头程序段已经执行结束后，再把后续程序段从外存调入内存覆盖前面的程序段。
1.2 要求
程序员提供一个清楚的覆盖结构。即程序员必须把一个程序划分成不同的程序段，并规定好它们的执行和覆盖顺序。
1.3 详细过程
思想:不相互调用的程序段可以共享同一内存区
例子:
设某进程的程序正文段由A，B，C，D，E和F等6个程序段组成.
由于程序段B不调用C，程序段C也不调用B，因此程序段B和C无需同时驻留在内存，它们可以共享同一内存区。
同理，程序段D、E、F也可共享同一内存区。
内存可以分为两个部分:
- 常驻内存区:常驻内存部分，与所有被调用程序段有关，不能被覆盖。这一部分称为根程序。图 (b)中，根程序是程序段A
- 覆盖区
1.4 覆盖技术可以节约内存空间
覆盖区0由程序段B、C共享，容量50K。
覆盖区1为程序段F、D、E共享，容量40K。
进程正文段要求内存空间：
A(20K)+B(50K)+F(30K)+C(30K)+D(20K)+E(40K)=190K
采用覆盖技术，只需110K的内存空间即可开始执行。
2 交换技术
2.1 基本思想
在多道程序环境下，一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况。另一方面，却又有着许多作业在外存等待，因无内存而不能进入内存运行的情况。显然这是对系统资源的一种严重浪费，使系统吞吐量下降，于是增设了对换（交换）设施。
- ---- 所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程调入内存。
- ---- 如果对换是以整个进程为单位的，便称之为“整体对换”或“进程对换”。解决内存紧张的问题。
- ---- 如果对换是以“页“或”段“为单位进行的，则分别称之为”页面对换“或”分段对换“。为了实现进程对换，系统必须能实现3个方面的功能：对换空间的管理、进程的换出、进程的换入。
采用交换基础的好处是以牺牲CPU时间为代价的。
2.2 进程的换入换出
- 换出：每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。
- 换入：把外存交换区中的数据和程序换到内存中。系统应定时的查看所有进程的状态，从中找出”就绪“状态但已换出的进程。将其中换出时间最久（换出到磁盘上）的进程作为换入进程，将之换入。直至已无可换入的进程或无可换出的进程为止。交换的特点是打破了一个程序一旦进入主存便一直运行到结束的限制，但运行的进程大小仍受实际主存的限制。
2.3 与覆盖技术相比
- 与覆盖技术相比，交换不要求程序员给出程序段之间的覆盖结构
- 交换主要是在进程或作业之间进行
- 覆盖主要在同一个作业或进程中进行。另外，覆盖只能覆盖与覆盖程序段无关的程序段。(以模块/函数为单位)
3 程序的局部性原理
3.1 基本概念
程序局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域，具体来说，局部性通常有两种形式：时间局部性和空间局部性。
局部性原理表现在以下两个方面：
1.时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
2.空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。
时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存一外存”的两级存储器的结构，利用局部性原理实现髙速缓存。
3.2 示例
我们知道，数组的特点是在内存中是向下图一样连续存放的。
根据代码以及局部性定义可知：
对于循环中的sum变量：有良好的时间局部性。因为在for循环结束之前，每次执行循环体都有对 sum 的访问。而 sum 没有空间局部性。因为sum 是标量（也就是说通过 sum 这个地址只能得到一个值）
对于循环体中的 v 变量：有良好的空间局部性。因为数组v是按顺序存放在内存中，每次访问 v[i]总是在 v[i-1] 的下一个位置。而v没有时间局部性，因为在循环体中，每个元素v[i]只会被访问一次。
我们再来看看一个遍历二维数组的例子：
上面的例子，fun_1和fun_2都是对一个二维数组进行遍历赋值。在fun_1函数的for循环体中，是以行序为主序对元素进行遍历。也就是说内层循环先访问第一行的元素，然后第二行......，而二维数组在存储器中也是按照行序为主序来进行存储的。也就是说先存储第一行，然后第二行......，如下图所示。本例中存储顺序和访问顺序一致。所以可以该程序对a[][]的引用有良好的空间局部性。
而fun_2函数只是在fun_1的基础上将求和函数中的双重循环的索引i和j调换一下位置，也就是说在对a[][]进行遍历的时候，以列序为主序。即先访问第一列，在访问第二列......，而前面讲了二维数组在存储器中也是按照行序为主序来进行存储；意味着每访问一个元素，就要跳过N个元素才能访问下一个。这种情况下没有良好的空间局部性。
再来看看运行结果，对于同一个数组，具有空间局部性的fun_1函数运行的效率几乎是没有局部性的fun_2函数的提高了一倍，至于为什么有良好局部性的程序有更好的性能，这个和计算机的缓存是息息相关的，将会在后面的文章中介绍。这篇文章且当作后文的铺垫吧。
参考链接
- 王道2024考研书
其实中途还查找了很多开源资料，但是内容十分繁杂并且不是本篇重点因此并未特意标注，在此感谢广大网友的热心贡献！
另外，欢迎您在底部评论区留言，一起交流~
- Author:Koreyoshi
- URL:https://Koreyoshi1216.com/article/128c7b13-c6a7-8031-9228-f3f9033a4a14
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!