分页和分段是在面试过程中常被问到的两种内存管理技术。
计算机结构比较复杂，那么说到“存储”，我们一般就想到内存和外存，比如我们买手机买电脑，都要看看这些终端的内存够不够打游戏，外存够不够装照片这些。内存外存只是比较通俗的叫法，在实际的计算机存储体系当中，我们划分了四块区域：寄存器（CPU registers）、高速缓存（CPU cache）、主存（内存）、外存（磁盘）。
这篇文章主要是将这座金字塔结构自顶向下第三层的主存结构，也就是我们俗称的内存。
内存这东西不是一两篇文章就能看懂吃透的，无奈每次面试或多或少都被面试官问道这些东西，稍微捋一下这些概念性的东西。
一、内存管理
内存——内部存储器，在运行的时候存储信息，CPU可以直接寻址，区别于那些可以永久保存数据、CPU需要通过硬件控制器读取数据的“外部存储器”。这两者是从计算机架构的角度说的。在通常语境下，“内存”只有主板上插的内存条一种，内存就成了“主板上的RAM”的代称。
RAM（Random Access Memory），随机访问控制器，断电就失效，可以直接通过电流刷新数据。由于1950年代和1960年代的计算机使用微小的可磁化铁氧体磁芯作为主存储器，因此旧时有时将其称为核心存储器。所以不能在高速缓存中得到满足的内存访问请求斗湖转往RAM当中。
对应的ROM（Read-Only Memory），只读储存器，最开始的ROM真的是只读，不可写入，包括半导体ROM和CD-ROM，后来出现了紫外线擦除的EPROM，电擦除的EEPROM。
我们可以更通俗点去理解内存，内存就是暂时存储程序以及数据的地方，当我们在使用WPS处理文稿时，当你在键盘上敲入字符时，它就被存入内存中，当你选择存盘时，内存中的数据才会被存入硬（磁）盘。
我们在计算机上运行着许许多多的程序，比如QQ、QQ音乐、浏览器等等，每个程序虽然安装在磁盘上，但当用户在运行的时候，需要CPU对这些程序进行操作，显然CPU不可能直接对磁盘进行读取，所以这个时候，内存的作用就出来了。当一个程序，也就是一个进程需要运行的时候，这个进程会先加载到内存上，然后再由CPU对内存上的数据进行操作。
那我们再想想实际的情况，内存一般并不大，现在的电脑一般也就4GB-16GB，而我们的设备一般都支持多进程，同一时刻你可以听着歌QQ在线接收消息顺便打个LOL，甚至有的进程比如MATLAB十几个G来启动，所有的进程数据都保存在内存当中的话，就需要大量的内存，如果内存不足，则无法完成。
针对上面的内存不足的问题，有两种处理方式，第一种比较简单的方式就是交换（swapping）技术，也就是把一个进程完整得调入内存，在内存中运行一段时间之后，再把它放回磁盘。空闲的进程会存储在磁盘当中，所以这些进程在没有运行的时候不会占用太多的内存。这种交换技术我们在这里不多说，主要想聊的是第二种策略，虚拟内存（virtual memory）。
二、虚拟内存
正如第一节所讲，虚拟内存的出现是为了解决内存不足的问题。通过虚拟内存可以让程序拥有超过系统物理内存大小的可用内存空间。另外，虚拟内存为每个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间）。这样会更加有效地管理内存并减少出错。
虚拟内存的目的就是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。
虚拟内存是计算机系统内存管理的一种技术，我们可以手动设置自己电脑的虚拟内存。不要单纯认为虚拟内存只是“使用硬盘空间来扩展内存“的技术。虚拟内存的重要意义是它定义了一个连续的虚拟地址空间，并且 把内存扩展到硬盘空间。推荐阅读：《虚拟内存的那点事儿》
维基百科中有几句话是这样介绍虚拟内存的。
虚拟内存 使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。与没有使用虚拟内存技术的系统相比，使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如RAM）的使用也更有效率。目前，大多数操作系统都使用了虚拟内存，如Windows家族的“虚拟内存”；Linux的“交换空间”等。
我们后面讨论的内存空间的分配与回收都是基于非连续分配管理方式，也就是一个进程在实际物理内存中不一定是存在于一片连续的地址空间，而是被分割到不同的非连续的地址空间。
三、分页
在谈论分页之前，我们需要弄清楚几个地址的概念。
物理地址
物理地址：数据在主存的实际位置。
逻辑地址
逻辑地址：与当前（进程）数据在内存中与物理分配地址无关的访问地址，在执行对内存的访问之前必须转化为物理地址。
相对地址
相对地址：特殊的逻辑地址，相对于某些已知点的存储单元。
基本分页存储管理
大部分使用虚拟内存的系统中会使用一种分页（paging）的技术。
分页存储管理就是将内存空间分成一个个大小相等的分区（比如每个分区4KB），每个分区就是一个“页框”，或者“页帧”、“内存块”、“物理块”。每个页框有一个编号，即“页框号”，或者“页帧号”、“内存块号”、“物理块号”。页框号从0开始。
将用户进程的地址空间也分成和页框大小相等的一个个区域，称为“页”或者“页面”。每个页面也有一个编号，即“页号”，也是从0开始。
（注意：一个进程的最后一个页面可能没有一个页框那么大。因此页框不能太大，否则可能产生过大的内部碎片）
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。
各个页面不必连续存放，也不必按照先后顺序，可以放到不相邻的各个页框中。
那么将进程地址空间分页后，操作系统该如何实现逻辑地址到物理地址的转换？
分页系统地址映射
内存管理单元（MMU）管理者地址空间和物理内存的转换，其中的页表（Page table）存储着页（进程地址空间）和页框（物理内存空间）的映射表。
一个虚拟地址分成两部分，一部分存储页面号，一部分存储偏移量。
逻辑地址到物理地址的映射过程
- 算出逻辑地址对应的页号，即逻辑地址最左的n位；
- 以这个页号为索引，查找该进程页表中相应的帧号y，也就是该页号对应的页面在内存中的起始位置；
- 该帧的起始物理地址为y*(2^m)，被访问字节的物理地址是这个数加上偏移量。
页号 = 逻辑地址 / 页面长度
页内偏移量 = 逻辑地址 % 页面长度
物理地址 = 页面始址 + 页内偏移量
我们来看个例子：
根据上面的三个步骤可以很容易得到结果：物理地址 = 3 * 8 * 1024 + 9612 % 8192 = 25996
页表
为了能知道进程的每个页面加内存中存放的位置，操作系统要为每个进程建立一张页表。
- 一个进程对应一张页表
- 进程的每一页对应一个页表项
- 每个页表项由“页号”和“块号”组成
- 页表记录进程页面和实际存放的内存块之间的对应关系
- 每个页表项的长度是相同的，页号是”隐含“的
页面置换算法
地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断 。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统 必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
页面置换算法的作用是实现虚拟存储管理。
页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。
最佳页面置换算法(Optimal Page Replacement Algorithm)
最饥饿页面置换算法是将未来最久不使用的页替换出去，这听起来很简单，但是无法实现。根据页面被访问前所需要的指令数作为标记，根据指令数的由多到少进行置换，这个方法对评价页面置换算法很有用，但它在实际系统中却不能使用，因为无法真正的实现。这种算法可以作为衡量其它算法的基准。
最近最久使用页面置换算法(Least Recently Used)
通常在前几条指令中使用频繁的页面很可能在后面几条指令中页频繁使用。LRU算法就是在缺页发生时首先置换最长时间未被使用的页面。优秀但是难以实现。
Leetcode有一道题目是设计LRU缓存机制
最近未使用页面置换算法(Not Recently Used Replacement Algorithm)
在最近的一个时钟周期内，淘汰一个没有被访问的已修改页面，近似 LRU 算法，NRU 只是更粗略些。
这种算法给每个页一个标志位，R表示最近被访问过，M表示被修改过。定期对R进行清零。这个算法的思路是首先淘汰那些未被访问过R=0的页，其次是被访问过R=1,未被修改过M=0的页，最后是R=1,M=1的页。
先进先出的页面置换算法(First-In First-Out Page Replacement Algorithm)
这种算法的思想是淘汰在内存中最久的页，这种算法的性能接近于随机淘汰。可能抛弃重要的页面，并不好。
第二次机会页面置换算法(Second Chance Page Replacement Algorithm)
这种算法是在FIFO的基础上，为了避免置换出经常使用的页，增加一个标志位R，如果最近使用过将R置1，当页将会淘汰时，如果R为1，则不淘汰页，将R置0.而那些R=0的页将被淘汰时，直接淘汰。这种算法避免了经常被使用的页被淘汰。
时钟替换算法(Clock Page Replacement Algorithm)
虽然改进型FIFO算法避免置换出常用的页，但由于需要经常移动页，效率并不高。因此在改进型FIFO算法的基础上，将队列首位相连形成一个环路，当缺页中断产生时，从当前位置开始找R=0的页，而所经过的R=1的页被置0，并不需要移动页。
下表是上面几种算法的简单比较:
| 算法 | 描述 |
|---|---|
| 最佳置换算法 | 无法实现，最为测试基准使用 |
| 最近不常使用算法 | 和LRU性能差不多 |
| 先进先出算法 | 有可能会置换出经常使用的页 |
| 改进型先进先出算法 | 和先进先出相比有很大提升 |
| 最久未使用算法 | 性能非常好，但实现起来比较困难 |
| 时钟置换算法 | 非常实用的算法 |
四、分段
基本分段存储管理
与“分页”最大的区别就是——离散分配时所分配的地址空间的基本单位不同。
进程的地址空间：按照程序的自身的逻辑关系划分为若干段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），从0开始编址。
内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
由于按逻辑功能模块划分，用户编程更方便，程序的可读性更高。
段表
程序分多个段，各段离散地装入内存，为了保证程序能正常的运行，就必须从物理内存中找到各个逻辑段的存放位置。为此需为每个进程建立一张映射表，简称“段表”。
- 每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称“基址”）和段的长度
- 各个段表项的长度是相同的。例如：某系统按字节寻址，采用分段存储管理，逻辑地址的结构为（段号16位，段内地址16位），因此用16位即可表示最大段长。物理内存大小为4GB（可用32位表示整个物理内存地址空间）。因此，可以让每个段表项占16+32=48位，即6B。由于段表项长度相同，因此段号是可以隐含的，不占存储空间。若段表存放的起始地址为M，则K号段对应的段表项存放的地址为M+K*6.
五、分页和分段的比较
页是信息的物理单位。分页的目的主要是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
段是信息的逻辑单位。分段的目的主要是为了更好的满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且有系统决定。段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。
不能修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不可以共享的（比如有一个代码段中有很多变量，各进程并发地同时访问可能造成数据的不一致）
六、段页式
| 优点 | 缺点 | |
|---|---|---|
| 分页管理 | 内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片 | 不方便按照逻辑模块实现信息的共享和保护 |
| 分段管理 | 很方便按照逻辑模块实现信息的共享和保护 | 如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片 |
段页式系统的逻辑地址结构由段号、页号、页内地址（页内偏移量）组成
段号的位数决定了每个进程最多可以分几段
也好的位数决定了每个段最大有多少页
页内偏移量决定了页面的大小、内存块的大小是多少
