前言：对于操作系统，主要是了解的作用，本文大部分知识来自《现代操作系统》，个人只是对内存管理章节做总结并加入一点自己的看法，便于后续查阅。
地址空间： 是一个进程可用于寻址内存的一套地址集合。
每个进程都有一个自己的地址空间，并且这个地址空间独立于其他进程的地址空间。
处理内存超载的两种通用方法
交换（Swapping）技术：
将一个进程完整调入内存，使该进程运行一段时间，然后把它存回磁盘。空闲进程主要存储在磁盘上，所以当他们不运行时就不会占用内存。
虚拟内存（Virtual memeory):
该策略甚至能使程序只有一部分被调入内存的情况下运行。
内存紧缩（memory compaction)
交换技术在内存中产生多个空闲区（hole，可以认为是空洞），通过将所有进程向下移动，将这些空闲区合成一大块。
缺点： 耗时严重，通常不做该操作。
空闲内存管理
在动态分配内存时，操作系统必须对其管理。
1、使用位图的存储管理
在位图方法中，内存可能被划分为 几个字节到 几千个字节不等的分配单元。每个分配单元对应于位图中一位，0 表示空闲，1 表示占用。
所以分配单元的大小是一个重要的因素，分配单元越小，位图越大。
位图的缺点： 当要把一个占k个分配单元的进程调入内存时，存储管理器必须扫描位图，找到有k个连续0的串，这个操作是耗时的
2、使用链表的存储管理
维护一个记录已分配内存段和空闲内存段的链表。
链表中的每一个结点都包含以下部分：
空闲区(H) 或 进程(P) 的指示标志、起始地址、长度和指向下一个结点的指针
像上图中的 3-6C部分一样，一个链表节点 P-0-5-结点指针，P为进程标志，0为起始地址，长度为5
当然，段链表使用双向链表更易于找到上一个结点，并当一个结点为进程P被释放时，方便检查是否可以合并。
我们需要考虑一个问题，怎么给创建的进程或从磁盘换入的已存在的进程分配内存呢？
常用的三种算法：
首次适配算法：
存储管理器沿着段链表进行搜索，直到找到一个足够大的空闲区，并且将空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。
最佳适配算法：
最佳适配算法搜索整个链表（从开始到结束），找到能够容纳进程的最小的空闲区。
最差适配算法：
总是分配最大的可用空闲区，使新的空闲区比较大从而可以继续使用。
虚拟内存的基本思想：
每个程序拥有自己的地址空间，这些空间被分割多个块，每个块称作一页或页面（page）。每一页有连续的地址范围。
这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。
当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射加载进行内存。
当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存中并重新执行失败的指令。
个人理解：物理内存就是内存，磁盘是硬盘，不是物理内存
.
由程序产生的这些地址称为虚拟地址，它们构成了一个虚拟地址空间。
在使用虚拟内存的时候，虚拟内存不会直接送到内存总线上，而是被送到内存管理单元（Memory Management Unit,MMU),MMU会把虚拟地址映射为物理内存地址
分页技术
虚拟地址空间按照固定大小划分成被称为页面(page)的若干单元。在物理内存中对应的单元称为页框(page frame) （也叫页帧），页面和页框的大小通常是一样的，在本示例下为4KB,但实际系统的页面大小从512字节到1GB.
对于示例中的64KB的虚拟地址空间和32KB的物理内存，可得到16个虚拟页面和8个页帧。RAM和磁盘之间的交换总是以整个页面为单元进行的。
例如 MOV REG，8192 ,意味着将虚拟地址 8192 被映射到 物理地址 24576（对应的页框即页帧是6）
即被MMU转换成 MOV REG，24576
虚拟地址转换成物理内存的地址的过程是咋样的？
我程序运行的虚拟地址有部分要加载进物理内存了，这个能理解，因为物理内存无法装下整个程序，但是怎么理解，要替换的物理内存页帧，这部分的内容是暂时不需要的了呢？
首先会发生缺页中断，然后基于页面置换算法进行页面的置换，具体置换页面的选择要看算法的特性，下面会介绍对应的页面置换算法。
在上图3-9中只有8个物理页框，于是只有8个虚拟页面被映射到了物理内存中，图中使用 叉号表示没有映射。
当程序访问一个未映射的页面，例如 执行指令 MOV REG，32780
MMU会注意到该地址对应的虚拟页面8还未映射，于是CPU会交给操作系统处理，这个叫做缺页中断或缺页错误。操作系统会找到一个最少使用的页框且把页框中的内容写入磁盘（如果它不再磁盘上并是对应的页面置换算法），随后把要访问的页面读到刚才回收的页框中，修改映射关系，然后重新启动刚才引起陷阱的指令。
页表
从数学的角度上看，页表本质是一个映射函数，将虚拟页号与物理页框号的关系关联起来。
页表项结构
不同计算机的页表项大小可能不一样，但32位是一个常用的大小。最重要的域是页框号。毕竟页映射的目的就是找到页框号，其次是 “在/不在”位。这个位是1时表示该表项是有效的，可以使用；如果是0，则表示该表项对应的虚拟页面现在不在内存中，访问该页面会引起一个缺页中断。（再次重申：物理页框号对应的是物理内存的地址，虚拟页号对应的是磁盘的地址）
保护位指出一个页允许什么类型的访问，简单的形式是只有一位，0表示读写，1表示只读。较先进的方法是使用三位，分别对应表示是否启用读、写、执行该页面。
修改位（modified bit），这个在操作系统重新分配页框时有用，如果一个页面已经修改过(即“脏”页时),必须把它写回磁盘。如果一个页面没有被修改过，则只简单把丢弃就行，此时磁盘上的副本依旧是最新的。这一位有时也被称为脏位(dirty bit),因为它反映了该页面的状态。
不论是读还是写，系统都会在该页面被访问时设置访问位。它的值被用来帮助操作系统在发生缺页中断时选择要被淘汰的页面。不再使用的页面要比正在使用的页面值得淘汰。
高速缓存禁止位是用于禁止该页面被高速缓存。这种对一些设备寄存器的内存页面很有用，因为假如操作系统正在等待IO设备对发出的命令做出响应时，需要保证硬件是从IO设备中读取数据而不是读取高速缓存的副本这种多此一举的行为。
加速分页过程
分页系统需要考虑的两个问题
1、虚拟地址到物理地址的映射必须非常快
2、如果虚拟地址空间很大，页表也会很大
第一个问题是 因为每次访问内存都需要进行虚拟地址到物理地址的映射。
第二个问题是现在计算机使用要么是32位的虚拟地址，要么是64位的。假设页面大小为4KB，32位的地址空间将有100万页。而64位就更多了。而页表会记录虚拟空间的所有页（每个进程都需要自己的页表，因为执行的程序和存储的虚拟地址不一样）
1、转换检测缓冲区
如果将页表放在内存中，那么要访问到内存中的地址需要访问两次内存，为什么呢？第一次拿着虚拟地址去内存中找到页表上对应的物理地址返回，通过该物理内存地址第二次访问内存，返回数据。这种效率不高，所以提出了一种解决方案：
由于少量的页面会进行大量的访问，我们只需要保证少量的页面能够快速被访问到即可，于是为计算机设置一个小型的硬件设备，将虚拟直接映射到物理地址，不需要访问页表，这种设备叫做转换检测缓冲区（Translation Lookaside Buffer,TLB),又称为快表，通常在MMU中，在实际中很少会超过256个。
第二个问题，如何处理巨大的虚拟地址空间
针对大内存的页表的解决方案
1、多级页表
32位的虚拟地址被切分10位PT1域、10位的PT2域和12位的Offset(偏移量）域。因为偏移量是12位，所以页面大小为4KB，共用2的20次方个页面
页面置换算法
当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存中，以便为即将调入的页面腾出空间。
如果要换出的页面在内存驻留期间已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本。如果没有修改过，则磁盘中的副本已经是最新的，不需要回写。
最优页面置换算法
假设计算机知道页面在后续的指令中还隔多少道才会被使用，那么就能够将性能最大化，例如 A页面在500万指令不会被使用，B页面在300万指令内不会被使用，那么可以优先替换A页面。但可惜计算机是无法知道各个页面下一次将在什么时候被访问，所以只能作为一个参考的最优算法，方便其他算法与其进行比较。
最近未使用页面置换算法
在大多数具有虚拟内存的计算机中，系统为每一页面设置了两个状态位。当页面被访问（读或写）时设置R位；当页面被写入(即修改)时设置M位。这些位包含在每个页表项中
当启动一个进程时，它的所有页面的两个位都会被操作系统设置为0，R位被定期地(比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。
当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位和M位的值，把它们分为4类：
第0类：没有被访问，没有被修改
第1类：没有被访问，已被修改
第2类：已被访问，没有被修改
第3类：已被访问，已被修改
虽然第1类看起来似乎不可能，但是当一个第3类的页面在它的R位被时钟中断清零后就成了第1类。
NRU(Not Recently Used,最近未使用）算法随机地从类编号最小的非空类中挑选一个页面淘汰。这个算法隐含的意思是，在最近一个时钟滴答中(典型的时间是大约20ms)淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的”干净”页面好。
NRU的主要优点是易于理解和能够有效地被实现。
先进先出页面置换算法
由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最早进入的页面放在表头，当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾，这个FIFO算法是很常用的，但在计算机中存在一个问题，就是可能一些常用的页面在不断的置换过程后被淘汰，基于这个原因，很少使用纯粹的FIFO算法。
第二次机会页面置换算法
FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改；检查最老的页面的R位，如果R位是0，那么这个页面又老又没有被使用，可以立刻被置换掉；如果是1，就将R位清0，并将该页面放到链表的尾端，修改它的装入时间使得它就像刚装入的一样，然后继续搜索。
这个算法称为第二次机会(second chance)算法。
第二次机会算法就是寻找一个在最近的时钟间隔内没有被访问过的页面。如果所有的页面都被访问过了，该算法就简化为纯粹的FIFO算法，因为将一个时钟间隔内的所有页面移动一次后，他们的R位已经清为0了，这就意味着循环一次后第一个页面A会被淘汰。
时钟页面置换算法
虽然第二次机会算法是一个比较合理的算法，但它经常要在链表中移动页面，既降低了效率又不是很必要，有一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。
当发生缺页指端时，算法会先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置。重复这个过程直到找到了一个R位为0的页面为止。这也是为什么成为时钟(clock)算法。
最近最少使用页面置换算法
LRU(Least Recently Used,最近最少使用)页面置换算法是大家非常熟悉的算法，广泛的被应用到各个领域，它非常近似于最优算法，理论上可以实现，但代价很高。
为了实现LRU，需要在内存中维护一个所有页面的链表，最近最多的页面在表头，最近最少使用的页面在表尾。困难的是每次访问内存时都必须要更新整个链表、在链表中找一个页面删除它，然后把它移动到表头是一个非常耗时的操作。
然而，还是有一些特殊硬件实现LRU的方法。先考虑一个最简单方法，就是要求硬件有一个64位计数器C，它在每条指令执行完后自动加1，每个页表项必须有一个足够容纳这个计数器值的域。每次访问内存后，将当前的C值保存到被访问页面的页表项中，一旦发生缺页中断，操作系统就会检查所有页表项中计数器的值，找到值最小的一个页面，这个页面就是最近最少使用的页面。
工作集页面置换算法
刚启动进程时，在内存中并没有页面，在CPU试图请求第一条指令时就会产生一次缺页中断，使得操作系统装入含有第一条指令的页面。随后不断重复这个过程，直到所需的大部分页面都在内存中，进程开始在较少的缺页中断情况下运行，这个策略称为请求调页(demand paging).因为页面是在需要时调入，而不是预先装入。
一个进程当前正在使用的页面的集合称为它的工作集。如果整个工作集都被装入到了内存中，那么进程在运行到下一运行阶段之前，不会产生很多的缺页中断。如果内存在下无法装下整个工作集，那么在进程运行的过程中会产生大量的缺页中断，导致运行速度也会变得很缓慢。
在多道程序设计系统中，进程会把进程转移到磁盘上(即从内存中移走所有的页面），这样可以让其他进程有机会占有CPU。有一个问题是，当该进程再次调回来以后应该怎么办？从技术的角度上将，并不需要做什么，一直发送缺页中断直到工作集全部被装入内存。然而，这样不停的产生缺页中断，速度太慢了，有相当多的CPU时间被浪费。
所以不少分页系统都会设法跟踪进程的工作集，以确保在让进程运行以前，它的工作集就已在内存中。该方法称为工作集模型，其目的在于大大减少缺页中断率。在进程运行前预先装入其工作集页面也称为预先调页(prepaging).
在任一时刻t,都存在一个集合，它包含所有最近k次内存访问所访问过的页面。这个集合w(k,t)就是工作集，w(k,t)是k的单调非递减函数，因为 k>1次访问过的页面一定不会小于k=1次访问的页面，同时w(k,t)不会无限增大，因为程序不可能访问比它的地址空间所能容纳的页面数量上限还多的页面。
在该置换算法中，每一个页表项至少包含两条信息：该页面上次使用时间和R位。置换过程与第二次机会算法类似，在每一个时钟周期，当发生缺页中断时，扫描页表项。
如果R位是1，则将当前实际时间写入到页表项的”上次使用时间”，也表示发生缺页中断时这个页面正在被使用。
如果R位是0，表示当前时钟周期下，这个页面还没被访问过，它就是可以作为候选者被置换，然后计算它的生存时间(即当前实际时间 - 上次使用时间),然后与T(工作集指的是过去T秒内实际运行时间中它所访问的页面集合)做比较，如果生存时间大于T，则用新的页面置换它，否则仍保留在工作集中，然后继续扫描更新剩余的表项。如果扫描了一遍都小于T，则淘汰生存时间最长的页面（即上次使用时间最小的值），最坏的情况R位都为1，则随机选择一个干净的页面淘汰。
工作集时钟页面置换算法
和时钟算法一样，所需的数据结构是一个以页框为元素的循环表，最初这个表是空的，然后不断装入页面知道形成一个环。每个页表项包含来自基本工作集的上次使用时间，以及R位和M位(未标出来）。
只是变成了一个环，扫描的时候移动的是指针，本质和工作集算法是一致的，淘汰机制也是一样。
页面置换算法总结
