现代操作系统 第三章 内存管理
无储存器抽象：没有逻辑地址，直接使用物理地址。这样是很危险的，用户很容易破坏操作系统，同时很难实现多个程序同时运行（可以使用静态重定位技术解决但是需要将地址和操作数区别对待，同时也不够高效）。主要用在单程序系统中，这种系统中的程序一旦装入就不会改变了。
抽象地址空间：每个进程拥有从0开始的抽象地址，使用基址寄存器将抽象地址转换为物理地址，使用界限寄存器确定地址的合法性
动态内存分配：内存分配表+内存分配算法
在动态内存分配时可能出现内存不足的情况，解决方法：
对换技术：当内存不足时，将阻塞的进程交换至外存，同时由外存交换入需要运行的进程
注：外存分为对换区（连续分配：提高对换速率）和文件区（离散分配：提高空间利用率）
覆盖技术：把程序分块，不会同时运行的块共享一块内存区域。但是分块的难度极大，掌握好的分块技术是很困难的
在动态内存分配时不可避免地会出现分区内碎片，解决方法：
内存紧缩技术：将所有进程尽可能地移动到一起，把小的内存空间合并为整个内存空间。但同时这也是个耗时操作，不能经常使用
伙伴系统：固定与动态分区的折衷+快速适应算法，详见：伙伴系统
空闲内存管理：
位图管理：使用固定大小的位图表示空闲内存，但是在位图中找到连续的k个0是一个耗时操作（因为想找到的串可能跨越字的边界）
链表管理：对链表中的每一项设置一个标志位表示其空闲与否，但当内存被分割的比较零散时链表会变得很长
适配算法：
首次适配算法：从头开始遍历，找到第一个足够大的空间，然后装入
下次适配算法：每次装入后记录位置，下次适配时从记录位置开始遍历查找第一个足够大的空间，然后装入。仿真程序证明下次适配算法性能略低于首次适配算法
最佳适配算法：遍历整个空间，找到能容纳进程的最小空闲区，然后装入。出乎意料的是最佳适配算法的空间利用率低于首次适配算法和下次适配算法，因为它会产生很多无用的小空闲区，而后两者产生的空闲区相对较大可以利用。
最差适配算法：与最佳适配算法恰好相反，最差适配算法找到最大的空闲区，然后装入程序。符合直觉的是最差适配算法并不是一个好的解决方案
注：可以为进程和空闲区分别建立链表，这样可以只在空闲链表中寻找适配空间，但同时释放空间的复杂度会增加，需要从进程链表删除然后插入空闲链表
注：对最佳适配算法和最差适配算法来说可以对空闲链表按大小排序，这样申请空间时可以达到常数复杂度，但是释放空间时必须遍历整个链表来合并相邻的空闲空间（如果按照地址排序，合并时只需遍历到第一个大于释放地址的块即可决定是否合并）
注：当空闲链表分离出来后可以不使用专门的空间来保存，每个空闲区的第一个字是空闲区大小，第二个字指向下个空闲区
快速适配算法：为各个常用的空闲区大小维护单独的链表，这种算法下寻找一个指定大小的空闲块是非常快的，但是回收空间时合并相邻的空闲块并将合并的结果放入相应的链表将是一个耗时操作。
注：在伙伴系统等快速适配算法中一种常见的空闲区大小的划分为2^n字节，原因是这样非常适合硬件优化。同时分配给进程空间时也会按照2^n字节分配，这样不会产生杂乱大小的空闲块，也有利于回收空闲块。
虚拟内存
分页技术
这个是设计在IO中会涉及到
页表中只保存虚拟地址相关的内存物理地址，如果一个虚拟地址指向的页面不在内存中，那么他应该指向一个无效的物理地址
快表：
硬件TLB：在硬件内部可以并行的匹配当前虚拟页号与每一个快表项，速度飞快
软件TLB：
这里所说的额外TLB失效应该只出现在多级页表这种复杂页表中，因为如果只有一个页表只需要一个寄存器保存页表的首地址即可找到页表，不需要让页表在TLB中。而多级页表可能会因为二级以上的页表不在TLB中而导致的TLB失效。个人理解，欢迎指正
软失效：页面不在TLB中，在内存中，需要更新TLB，很快，大约几十纳秒
硬失效：页面不在内存中，需要磁盘IO操作，更新页表和TLB，很慢，几毫秒
介于软硬之间的失效：
次要缺页错误：页面在内存中，但不在进程页表中，可能由别的进程调入，只用把页面映射到页表中，不用磁盘IO
严重缺页错误：即真正的硬失效
非法地址：访问了违法地址，这时只需报告一个段错误
多级页表：
1.单个页表需要一段连续的内存空间，当页表变得很大时开辟一片很大的连续内存空间变得困难，多级页表可以将使用多个分散的小的连续空间，因此更加适合虚拟地址空间很大的情况。
2.多级页表更大的用途在于可以避免把全部页表一次性全部装入内存，只需装入需要使用的页表
倒排页表：
使用物理页框到虚拟页面的映射，当虚拟地址远远大于物理地址时可大幅度节约内存。但问题在于，此时找到一个虚拟页面对应的页框需要遍历整个倒排页表。解决方案：
1.加强TLB的管理，如果可以用TLB解决大部分问题，就可以大大加速转换过程
2.使用散列，同时优化散列（减少碰撞，当某一项碰撞过多时用红黑树代替链表等）
页面置换算法
最优页面置换算法：每次都换出将最晚用到的页面，理论上最优解，但是无法实现，因为没法知道哪个页面将最晚用到，但可以最为评价其他算法的标准
最近未使用页面置换算法：存在R/W（读/写）位，R位被定时清除，以区别最近使用过的页面，换出时先换出类编号小的页面。优势在于性能还可以接受同时非常简单。
先进先出页面置换算法：淘汰最早进来的页面，问题在于会淘汰掉一些常用页面，因此很少使用
第二次机会页面置换算法：
但任然存在一个小问题，这个算法需要在链表频繁的移动页面，所以就引出了时钟页面置换算法
时钟页面置换算法：
最近最少使用页面置换算法：
使用一个链表实现LRU，但实际操作时代价很高，每次访存都要维护链表（找到一个页面删除并将他移到表头是一个耗时操作）
LRU硬件解决办法：有一个64为计数器C，每条指令执行后增加1，当访问一个页面时将C的值赋给页面的页表，需要置换页面时对应C值最小的就是最近最少使用的页面
LRU软件解决方法：
NFU：
老化算法：NFU的改进
但老化算法也有一个问题，他只能记录有限位的老化值，老化年代超过这个位数的页面之间的差距将被抹平，从而无法体现出差距，但在实践中超过这个时间的页面完全有理由被认为是不再重要的
工作集页面置换算法：为每个进程保存最近的工作集，从而实现预先调页
工作集时钟页面置换算法：
解释一点，这个算法当遍历到一个生存时间超时的页面时，如果页面是脏的，就启动磁盘IO然后设页面为干净，指针继续向前扫描
各个算法的对比：
全局分配与局部分配
局部分配算法：为每个进程分配一定的页框
全局分配算法：在可运行进程间动态的分配页框，每个进程拥有的页框数是动态变化的
通常情况下全局分配更好些，由于工作集大小随时间变化明显，在有些时刻，对于局部分配有些进程存在大量空闲页框浪费内存，有些进程页框数不足出现颠簸，整体效果不好。
这里同时也指出由于老化可能滞后于工作集变化，所以监控老化位并不一定能防止颠簸
一个解决方法是定期依照进程大小为其分配页框（设置一个最小页框数保证进程至少可以运行），当有一个进程被调出内存时可将它的页框分给其他进程。同时这种解决方案也可以是全局分配的，区别在于分配完之后再程序运行时使用PFF（缺页中断率）算法动态更新，PFF算法如下
注：当中断数在A以上时由于触发了过多的缺页中断而浪费CPU资源，在B以下时由于分配了过多的页框而浪费了内存
注：对于关于工作集的算法没有全局分配方式，因为不存在关于整个机器的工作集，那是没有意义的
负载控制：当系统出现颠簸时可以将一部分进程换出，当由于进程数过少导致CPU利用不完全时可以将一部分进程换入
页面大小：页面过小会需要更大的页表浪费储存空间，同时由于从磁盘传输一页到内存所花费的主要时间在寻道和旋转延迟上，因此传送一个小页面和一个大页面需要的时间差不多，而页面较小则需要传送更多的页面数，使用时间更长；同时页面过大会导致进程最后一页中有较大的空余，浪费储存空间。因此需要一个权衡
分离指令和数据空间：分别建立页表，使可用地址空间加倍
共享页面：共享指令页面非常简单，因为其中的内容不可改变，直接在页表中建立映射即可。而共享数据页面则复杂一些，一种尝试如下所示：
共享库：
清除策略：
前一种方法的关键在于保存一部分页框用作以后可能的恢复
指令备份：
如果在上图的指令中触发了缺页中断，那么触发时程序计数器的值可能时1000，1002，1004，而操作系统无法知道指令是从哪里开始的，这就对之后的恢复造成了问题。
一种解决的方法是通过一些内部寄存器，其中保存了用于恢复的信息，使得触发缺页中断后可以消除触发指令造成的影响
锁定内存中的页面：在全局置换算法中，包含IO缓冲区的页面可能被置换出去，如果该页面正在进行DMA传输，那么会有数据写入到新换入的页面中，造成错误。有两个解决方案：一种是锁住正在进行IO传输的页面，另一种是在内核缓冲区完成所有IO操作，再将数据复制入用户页面
注：造成这个问题的原因可能是大多数DMA使用物理地址而不是逻辑地址，因此会在DMA内部将逻辑地址转为物理地址，然而如果恰好在转换完成后出现了相应页面的换出操作，就会无法感知到内存被换出的操作。个人猜测哈，网上没查到相关的，今天刚看的IO部分，推理应该是这样
策略与机制分离：
分段：每个段是一个逻辑实体，更加有助于动态增长，信息共享，信息保护，动态链接
段页式：
挖草累死了，思路清晰了好多，OS有意思呀