问题
当一个系统在计算机引导完成后会启动几十个进程，单单一个用于查看该程序的更新进程就会吃掉几兆的内存，后台还有很多诸如此类的任务，如果计算机的内存足够大，可以保存所有进程，那么似乎就没有问题，然而实际上，所有进程所需的内存数量总和通常要远远超出储存器能够支撑的范围，当前的重要应用程序更是很容易就吃掉一两百兆甚至更多的空间，因此把所有进程一直保存在内存中是很不现实的
遇到这种情况有两种解决方案，一种通过基址寄存器和界线寄存器形成地址空间，通过交换技术解决内存超载。另外一种就是基于分页的虚拟地址技术：
1、交换技术：把一个进程完整调入内存运行一段时间，然后把他存回磁盘，空闲进程主要存储在磁盘上，使用的时候再把它们读取到内存中去。这种方式很好的使用的基址寄存器和界限寄存器。但是因为分配的是连续的物理内存，所以经过多次交换后会产生大量的内存空洞，因为每个进程分配的内存大小都不一样。并且还有一个问题是分配的内存大小为多大，因为很多程序在运行过程中会进行内存的分配，所以说为了减少因为内存不够而产生的内存交换和移动，应该为每个进程分配一些额外的内存，而且在进程空间大于内存时，不能使用
2、虚拟内存：有些应用程序的内存过大，有可能一个程序的内存就会超过计算机的物理内存，所以说计算机的数据和代码以及堆栈不可能全部放在内存中。虚拟内存的基本思路是每个进程都有自己的内存空间，这个空间被分为多个块，每个块称为一页或者页面。把一个进程的一部分调入内存中运行，当内存没有空闲空间时，将新的覆盖旧的页，同时将旧 的页写入磁盘。虚拟内存主要使用分页存储管理模式，适合多进程操作系统使用
概述
虚拟内存不只是”用磁盘空间来扩展物理内存”的意思，把内存扩展到磁盘只是使用虚拟内存技术的一个结果，它的作用也可以通过覆盖或者把处于不活动状态的程序以及它们的数据全部交换到磁盘上等方式来实现。对虚拟内存的定义是基于对地址空间的重定义的，即把地址空间定义为“连续的虚拟内存地址”，以借此”欺骗”程序，使它们以为自己正在使用一大块的”连续”地址
大部分虚拟内存系统中都使用一种称为分页的技术
在任何一台计算机上，程序引用了一组内存地址，由程序产生的这些地址称为虚拟地址，他们构成了一个虚拟地址空间。在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存总线上，读写操作使用具有同样地址的物理内存字；而在使用虚拟内存的情况下，虚拟地址不是直接被送到内存总线上，而是被送到内存管理单元(Memeory Management Unit, MMU)，MMU把虚拟地址映射为物理内存地址。虚拟地址空间按照固定大小划分成称为页面的若干单元。在物理内存中对应的单元称为页框。页面和页框大小是一样的
假设有一台可以产生16位地址的计算机，页面和页框大小都为4KB，我们的地址范围从0到64K，且这些地址是虚拟地址，而这台计算机只有32K的物理内存，他们之间的映射关系为：
因此对应于64KB虚拟地址空间和32KB的物理内存，我们得到16个虚拟页面和8个页框。虽然可以编写64KB的程序，但它们却不能被完全调入内存运行。在磁盘上必须有一个可以达到64KB的程序核心映像的完整副本，以保证程序片段在需要时能被调入内存，并且内存和磁盘之间的交换总是以整个页面为单元进行的
标记0-4K的范围表示该页的虚拟地址或物理地址是0-4095，当程序试图访问地址8203时，例如执行MOV REG 8203这条指令，将虚拟地址8203送到MMU，MMU看到虚拟地址落在页面2(8192-12287)，偏移量为11，根据其映射结果，这一页面对应的是页框6(24576-28671)，因此MMU把地址变换为24576+11=24587，并把24587送到总线上。内存对MMU一无所知，它只看到一个读或写地址24587的请求并执行它。MMU从而有效地把所有从8192-12287的虚拟地址映射到了24576-28671的物理地址
通过恰当地设置MMU，可以把16个页面映射到8个页框中的任何一个。但是这样并没有解决虚拟地址空间比物理内存大的问题。在例子中只有8个物理页框，于是只有8个虚拟页面被映射到了物理内存中。在实际的硬件中，用一个”在/不在”位来记录页面是否在内存中。例如当程序访问一个未映射的页面时执行MOV REG 32780指令，同样将虚拟地址32870送到MMU，MMU看到虚拟地址落在页面8(32768-36863)，但是该页面并没有被映射到内存中，于是计算机停止现行程序的运行，需要操作系统将其调入主存后再进行访问，称为缺页中断(又称硬错误/分页错误/寻页缺失)。操作系统调用适当的页面置换算法，找到某个页框将它的内容写入磁盘(如果它不在磁盘)，随后把页面8读到刚才回收的页框，修改映射关系，然后重新启动引起中断的指令
分页管理
页式存储管理将内存空间划分成等长的若干物理块，称为物理页面或物理块，每个物理块的大小一般取2的整数幂。内存的所有物理块从0开始编号，称作物理页号。系统将程序的逻辑空间按照同样大小也划分成若干页面，称为逻辑页面或页。程序的各个逻辑页面从0开始依次编号，称作逻辑页号或相对页号。每个页面内从0开始编址，称为页内地址。程序中的逻辑地址由两部分组成：页号P和页内位移量W
在执行一个程序之前，内存管理器需要的准备工作：
1、确定程序的页数
2、在主存中留出足够的空闲页面
3、将程序的所有页面载入主存里(静态的分页，页面无需连续)
若给定一个逻辑地址为A，页面大小为L，则页号P = INT[A/L]，页内地址W = A MOD L
对于内存分配，相邻的页面在内存中不一定相邻，即分配给程序的内存块之间不一定连续。对程序地址空间的分页是系统自动进行的，即对用户是透明的。由于页面尺寸为2的整数次幂，故相对地址中的高位部分即为页号，低位部分为页内地址
页表
分页系统中，允许将进程的每一页离散地存储在内存的任一物理块中，为了能在内存中找到每个页面对应的物理块，系统为每个进程建立一张页表，用于记录进程逻辑页面与内存物理页面之间的对应关系。页表的作用是实现从页号到物理块号的地址映射，地址空间有多少页，该页表里就登记多少行，且按逻辑页的顺序排列
虚拟地址被分成虚拟页号(高位部分)和偏移量(低位部分)。例如对于16位地址和4KB的页面大小，高4位可以指定16个虚拟页面，而低12位接着确定了页内偏移量。虚拟页号可用作页表的索引，以找到该虚拟页面所对应的页表项。由页表项可以找到页框号(如果有的话)。然后把页框号拼接到偏移量的高位端，以替换掉虚拟页号，形成送往内存的物理地址
页表项
页表项的结构是与机器密切相关的，但不同机器的页表项存储的信息都大致相同。
页表项中最重要的域是页框号。其次是“在/不在”位，其中为1时表示该表项是有效的可以使用，0表示该表项对应的虚拟页现在不在内存中，访问该页面会引起缺页中断。“保护”位指出一个页面允许什么类型的访问，其最简单的形式是这个域只有1位，0表示读/写，1表示只读,；一个更先进的方法是使用2位，各位分别对应是否启用读、写、执行该页面。“修改”位和“访问”位用于记录页面的使用情况，这2位在操作系统重新分配页框和发生缺页中断选择淘汰的页时非常有用。“高速缓存禁止”位用于禁止该页面被告诉缓存
在任何分页式系统中，都需要考虑两个主要问题：
Q1：虚拟地址到物理地址的映射必须非常快(每次访问内存时，都需要访问一次或者多次访问页表)
A1：使用“转换检测缓冲区”(Translation Lookaside Buffer,TLB)解决
Q2：如果虚拟地址空间很大，页表也会很大(现在操作系统都是32/64位的了，假设页面大小是4KB，那么32位的操作系统都需要包含100万条数据了)
A2：使用多级页表或倒排页表解决
转化检测缓冲区(Translation Lookaside Buffer)
假设一条指令把一个寄存器中的值复制到另一个寄存器中，则在没有采用分页时只需要访问一次内存，即从内存中读取指令，但是采用分页机制后，因为要访问页表则会发起更多次的内存访问，所以计算机的速度会被取指令或者数据的速度拖累。由于大多数程序对页面的访问总是集中在少量的页面，所以说只有很少量的表项会被大量访问，因此引入了一个设备叫做TLB。它可以将虚拟地址直接映射到物理地址，而不必再访问页表，TLB通常在MMU中，一般会包含64个以下的表项，当访问虚拟内存单元的所指向的内存的时候，先遍历TLB，如果找到所需要的内存就取出来，否则就遍历页表找到所需的页表项，然后从TLB中淘汰一个表项，用找到的新表项替代它
多级页表
假设在32位操作系统，32位虚拟地址被划分为10位的PT1域，10位的PT2域，12位的位偏移量，因此12位的偏移量可以说页面的大小是4KB。引入多级页表可以避免把全部的页表都保存到内存中，比如说一个进程是12M，4M程序段、4M数据段，最后4M堆栈段，如果把所有的页表都放进内存中是非常浪费的，引入多级页表就可以大大减少页表的数量，由PT1确定一级页表的页表项，一级页表项中记载了二级页表项的地址或者页框号，现在用PT2作为访问二级页表的索引。在这个例子中因为只包含3个4MB的内存段，所以一级页表只记载了3个二级页表的位置，并且实际内存中也只包含了3个二级页表，这样的话实际内存中就只包含了4个页表，只包含了少量的页表项
倒排页表
虽然说多级页表能够减少内存中的页表项，但是如果是64位的系统的话，地址空间是64位，页面大小是4KB，那么需要2^52次方的页表项，因此还需一种不同的解决方案。倒排页表是为实际内存中的每一个内存框分配一个页表项，而不是为每一个虚拟内存空间分配一个页表项，页表项中记录了哪一个进程和哪一个虚拟页面位于内存空间中，看起来是不是很像倒排索引。这种方式虽然节省了大量的内存空间，但是从虚拟地址转换到物理地址会非常的麻烦，读取一个虚拟地址的时候必须搜索整个倒排列表，可以说是非常耗时的，所以一般还是推荐使用TLB
页面的共享与保护
当多个不同进程中需要有相同页面信息时，可以在主存中只保留一个副本，只要让这些进程各自的有关项中指向内存同一块号即可。同时在页表中设置相应的”存取权限”，对不同进程的访问权限进行各种必要的限制
页面置换算法
当发生缺页中断时，操作系统必须将内存中选择一个页面置换出去，为要调入的新页面腾出空间，操作系统常用的页面置换算法有以下这些：
- 最优页面置换算法
- 选择最长时间内不会被访问的页面丢掉，时间越久越好。但是无法准确得知，理论上不能实现
- 最优算法，但不可能实现，可以作为基准
- 最近未使用页面置换算法(NRU)
- 找到最久没有使用的页面置换出去，页面被访问时设置R位，修改时设置M位，R位定期清0。系统从页编号(RM)最小的非空页随机挑选一个置换
- 最近未使用算法，LRU(6.)粗糙的近似
- 先进先出置换算法(FIFO)
- 维持一个保存当前所有页面的链表，新使用的页面插入链表尾部，使得最久进入的排在头部，从头部淘汰老旧页面
- 可能会置换重要的页面
- 第二次机会置换算法
- 改进版FIFO，淘汰旧页面时先从检查头部页面的R位，若为1，则说明此页面最近被使用过，置R=0，把它加到尾部去，重新设置其装入时间为当前时刻，继续搜寻；若为0，如果此页面被写过，把它写回磁盘再淘汰，若未被写，直接淘汰
- FIFO的较大改进，淘汰最老且最近没有使用过的页面
- 时钟页面置换算法
- 维持一个保存所有页面的环形链表，一个指针指向最老页面，发生缺页中断时，检查指针指向页面，若R=0，则更新它，若R=1，清除R位，指针前移，继续搜索
- 二次机会置换算法的实现，避免移动链表元素
- 最近最少使用页面置换算法(LRU)
- 找到最久没有使用过的页面去置换。需要特殊硬件实现(如利用一个n*n的矩阵)
- 优秀但实现成本高
- 最不常用算法(NFU)
- 为每个页面维持一个初值0的计数器，每次时钟中断，由操作系统扫描所有页面，把计数器加上当前的R位更新，这样每个计数器的值大概反映了被访问的频繁程度。缺页中断时，置换计数器数值最小的页面
- LRU(6.)近似，但是效率不高
- 老化算法
- 改进的LRU，区别在于R位加进计数器之前，先把计数器值右移一位，把R位加到计数器最左边
- 每次时钟滴答只能记下一位，因此如果两个页面在同一个时钟滴答期间被访问是不能分出的，而且由于计数器是有限位数，假设是8位，那么如果很多页面在8个时钟滴答内都未被访问的话，就都是全零位无法区分，但实际情况是，若已经这么久没有被访问了，该页面一般也不是很重要了
- LRU(6.)的高效率实现
- 工作集页面置换算法
- 定义一个工作集，在过去t秒内被访问的页面的集合。扫描所有页面，若R为1，说明在这个时钟滴答被访问了，它应该是工作集的一部分，把当前时间写入页表项的“上次使用时间“ 。若R位为0，且生存时间(当前时间-上次使用时间)>t,置换它，如果<t,记住最小时间
- 开销大
- 工作集时钟页面置换算法
- 维持一个以页框为元素的循环表，形成一个环，每个表项包括上次使用时间，拥有R位M位。缺页中断时，首先检查指针指向的页面，若R位为1，则说明它最近被访问了，把R位置为0，指针指向下一个位置，若R位为0，若它的生存时间>t且此页面干净，置换它；如果不干净，继续往前走，因为可能前方存在旧的又干净的页面
空闲内存管理
位图管理
使用位图管理的方法时候，会将内存分为几k或者几千k大小的块，每个块都用一个位标记0表示空闲，1表示已经使用，内存单元分配的越小位图越大，但是内存单元分配的越大就就会造成越大的浪费，因为进程所占用的内存不是内存单元的整数倍
链表管理
链表中节点保存了一个进程或者两个进程之间的空闲区，每个链表的节点都包含一下域，总体而言节点包含了该空闲区/进程的标识、起始地址、长度、下一个节点的地址。
当按照链表来管理内存的时候可以使用以下算法来为新进程分配内存：
1、首次适配算法：遍历链表找到第一块合适的内存，可以尽可能的减少搜索
2、最佳适配算法：遍历链表找到最合适的一块内存，但是这样的结果会产生一些特别小的内存空闲区，导致无法使用
3、最差适配算法：找到最大的空闲内存
可以为进程区和空闲区分配不同的链表，这样的搜索效率会提高，但是这样会增加内存的复杂度，因为分配后要从空闲区删除一个节点，为进程区添加一个节点。另外可以将空闲区的链表按照内存块的大小进行排列，这样的话就可以提高适配算法的速度
分段管理
页面是主存物理空间中划分出来的等长的固定区域。分页方式的优点是页长固定，因而便于构造页表、易于管理，且不存在外碎片。但分页方式的缺点是页长与程序的逻辑大小不相关。例如，某个时刻一个子程序可能有一部分在主存中，另一部分则在辅存中。这不利于编程时的独立性，并给换入换出处理、存储保护和存储共享等操作造成麻烦
因此有另一种划分可寻址的存储空间的方法称为分段。段是按照程序的自然分界划分的长度可以动态改变的区域。通常程序员把子程序、操作数和常数等不同类型的数据划分到不同的段中(c语言时用到)，并且每个程序可以有多个相同类型的段。段表本身也是一个段，可以存在辅存中，但一般是驻留在主存中。将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配
作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息，例如程序段、数据段等。每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间是二维的。
在段式虚拟存储系统中，虚拟地址由段号和段内地址组成，虚拟地址到实存地址的变换通过段表来实现。每个程序设置一个段表，段表的每一个表项对应一个段，每个表项至少包括三个字段：有效位(指明该段是否已经调入主存)、段起址(该段在实存中的首地址)和段长(记录该段的实际长度)
针对每一个虚拟地址，存储管理部件首先以段号S为索引访问段表的第S个表项。若该表项的有效位为1，则将虚拟地址的段内地址D与该表项的段长字段比较；若段内地址较大则说明地址越界，将产生地址越界中断；否则，将该表项的段起址与段内地址相加，求得主存实地址并访存。如果该表项的有效位为0，则产生缺页中断，从辅存中调入该页，并修改段表
分页对程序员而言是不可见的，而分段通常对程序员而言是可见的，因而分段为组织程序和数据提供了方便。与页式虚拟存储器相比，段式虚拟存储器有许多优点：
1、段逻辑独立性使其易于编译、管理、修改和保护，也便于多道程序共享
2、段长可以根据需要动态改变，允许自由调度，以便有效利用主存空间
3、方便编程，分段共享，分段保护，动态链接，动态增长
因为段的长度不固定，段式虚拟存储器也有一些缺点：
1、主存空间分配比较麻烦
2、容易在段间留下许多碎片，造成存储空间利用率降低
3、由于段长不一定是2的整数次幂，因而不能简单地像分页方式那样用虚拟地址和实存地址的最低若干二进制位作为段内地址，并与段号进行直接拼接，必须用加法操作通过段起址与段内地址的求和运算得到物理地址。因此，段式存储管理比页式存储管理方式需要更多的硬件支持
段页式存储
段页式存储组织是分段式和分页式结合的存储组织方法，这样可充分利用分段管理和分页管理的优点
1、用分段方法来分配和管理虚拟存储器。程序的地址空间按逻辑单位分成基本独立的段，而每一段有自己的段名，再把每段分成固定大小的若干页
2、用分页方法来分配和管理实存。即把整个主存分成与上述页大小相等的存储块，可装入作业的任何一页。程序对内存的调入或调出是按页进行的。但它又可按段实现共享和保护
3、逻辑地址结构。一个逻辑地址用三个参数表示：段号S；页号P；页内地址d
4、段表、页表、段表地址寄存器。为了进行地址转换，系统为每个作业建立一个段表，并且要为该作业段表中的每一个段建立一个页表。系统中有一个段表地址寄存器来指出作业的段表起始地址和段表长度
在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段表长TL：
1、进行地址变换时，首先利用段号S，将它与段表长TL进行比较。若S<TL，表示未越界
2、于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址
3、利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b
4、再利用块号b和页内地址来构成物理地址
在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问是访问内存中的段表，从中取得页表始址；第二次访问是访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中，取出指令或数据。显然，这使访问内存的次数增加了近两倍。为了提高执行速度，在地址变换机构中增设一个高速缓冲寄存器。每次访问它时，都须同时利用段号和页号去检索高速缓存，若找到匹配的表项，便可从中得到相应页的物理块号，用来与页内地址一起形成物理地址；若未找到匹配表项，则仍须再三次访问内存
段页式存储管理的优点：
1、它提供了大量的虚拟存储空间
2、能有效地利用主存，为组织多道程序运行提供了方便
缺点：
1、增加了硬件成本、系统的复杂性和管理上的开消
2、存在着系统发生抖动的危险
3、存在着内碎片
4、还有各种表格要占用主存空间
段页式存储管理技术对当前的大、中型计算机系统来说，算是最通用、最灵活的一种方案
扇区：磁盘的最小存储单位
磁盘块：文件系统读写数据的最小单位
页：内存的最小存储单位
一个磁盘块由连续几个（2^n）扇区组成
页的大小为磁盘块大小的2^n倍
扩展：
操作系统篇-浅析分页机制 / 两级页表结构