No Memory Abstraction

没有存储器的抽象，程序直接访问物理内存。
帕金森定律：Programs expand to fill the memory available to hold them!

在不使用内存抽象的情况下运行多道程序
将两个程序装载到内存中，但是他们指令地址不一样，因为都引用了绝对的物理地址。（重定位问题）

保护：（IBM 360）给内存块标记上一个保护键，并且比较执行进程的键和访问的每个内存字的保护键。
静态重定位：需要给b程序的指令地址全部+16380

Basic Memory Management

地址空间

地址空间是一个进程可用于寻址内存的一套地址集合，每个进程都有自己的地址空间，并且这个地址空间独立于其他的地址空间。

基址寄存器与界限寄存器（动态重定位）

把每个进程的地址空间映射到物理内存的不同部分。
基址寄存器：程序的起始物理地址装载到基址寄存器中
界限寄存器：程序的长度装载到界限寄存器中

每次访问内存，都给指令加上基址寄存器的值，然后和界限寄存器相比较，看看是否超出界限寄存器，如果超出，就发生错误了。
缺点：每次访问内存都需要进行加法和比较运算。比较可以比较快，但是加法就会慢一点。

交换技术

• 交换技术：把一个进程完整调入内存，使该进程运行一段时间，然后把它存回磁盘。
• 虚拟内存：能使程序在只有一部分被调入内存的情况下运行

  空闲内存管理

  

  使用位图的存储管理

  内存可能被划分为几个字or几千字节的分配单元
  内存的大小和分配单元的大小决定了位图的大小
  主要问题：查找位图中指定长度的连续0串是耗时的操作（目的是为了把一个占k个分配单元的进程调入内存）

  使用链表的存储管理

  维护一个记录已分配内存段和空闲内存段的链表，其中链表的一个节点是 包含一个进程or两个进程间的一个空闲区
  链表中每个节点包含：空闲区（H）or进程（P）的指示标志、起始地址、长度、指向下一个节点的指针

  为创建进程分配内存的算法

1. 首次适配（first fit）算法：
   1. 存储管理器沿着段链表搜索，直到找到一个足够大的空闲区
   2. 除非空闲区和要分配的空间大小一样，否则将空闲区分成两部分。一部分进程使用，另一部分是新的空闲区。
2. 下次匹配（next fit）算法：
   1. 类似于首次匹配，但是每次找到合适空闲区时都记录当前位置，以便在下次寻找空闲区时从上次结束的地方开始搜索。
      // 性能略低于首次匹配算法
3. 最佳适配（best fit）算法：
   1. 搜索整个链表
   2. 找出能够容纳进程的最小的空闲区
      // 比ff和nf算法都浪费内存，因为会出现小的没法用的内存块，都浪费了
4. 最差匹配（worst fit）算法：
   1. 搜索整个链表
   2. 分配最大的可用空闲区
      // 也不好使
// 上面的几个，可以改成为空闲区、进程区各维护一个链表，而且空闲块从小到大排序，就快很多，不用遍历链表
5. 快速适配（quick fit）算法：
   1. 为常用大小的空闲区维护一个单独的链表
      例如，有一个n项的表，该表的第一项是 指向大小为4KB的空闲区链表表头的指针，第二项是指向大小为8KB的 空闲区链表表头的指针，第三项是指向大小为12KB的空闲区链表表头 的指针，以此类推。

      伙伴式内存管理

      所有内存块都是$2^n$的大小，每个块都能被分成两个更小的块
      没有外碎片，只有内碎片
      将全部的内存，分为$2^0、2^1、2^2、2^3、…、2^m$的大小。
      
      link、rlink：指向节点的直接前驱和直接后继节点。
      tag：标记内存块状态，1是占用，0是空闲
      kval：记录该存储块的容量，2m的容量，记录幂次
      分配算法：
      假设用户向系统申请大小为n的存储空间，若 $2^{k-1} < n <= 2^k$，就查看可用空间表中大小为$2^k$的链表中有没有可利用的空间节点：
6. 如果该链表不为NULL，可以直接从头部取出一个节点，给用户使用
7. 如果大小为$2^k$的链表为NULL，就按需要一次查看比$2^k$大的链表，找到后从链表中删除，截取相应大小的空间（$2^k$）给用户使用，剩余的空间，根据大小插入到相应的链表中。
   回收算法：
   用户释放存储块时，需要判断该存储块的伙伴是否为空闲块，
8. 如果是空闲块，则将其合并，然后合并的新的空闲块还需要同伙伴进行判断整合
9. 如果不是空闲块，直接将空闲块根据大小插入可利用空间表中即可

Virtual Memory

每个程序拥有自己的地址空间，这个空间被分割成多个块，每一块称作一页或页面。每一页有连续的地址范围。

分页 paging

程序产生的地址称为虚拟地址（virtual address），构成的空间就是虚拟空间（virtual address space）
在虚拟内存情况下，虚拟地址是被送到内存管理单元（memory management unit，MMU），MMU把虚拟地址映射为物理内存地址。（MMU是CPU芯片的一部分）

页面（page）：虚拟地址空间按照固定大小划分成称为页面的若干段元
页框（page frame）：物理内存中的对应单元称为页框（page frame）

页表（page table）

虚拟页号可用作页表的索引，以找到该虚拟页面对应的页表项。由页表找到页框号，然后把页框号拼接到偏移量的高位，替换掉虚拟页号，形成送往内存的物理地址。
页表：页表的目的就是把虚拟页面映射为页框。也表示一个函数，参数是虚拟页号，结果是物理页框号。

页表项的结构

• 页框号
• 在/不在 位：如果是1，则表示有效，可以使用。如果是0，则表示该表项对应虚拟页面不在内存中，访问该页面回引起一个缺页中断。
• 保护位：一个页允许什么类型的访问，0表示读/写，1表示只读。或者三位，读、写、执行。
• 修改位（dirty bit）：如果一个页面被修改过（脏的），就必须把它写回磁盘，如果没被修改过（干净的），那么只需要把页面丢弃就可以了。
• 访问位：帮助系统发生缺页中断时候选择要被淘汰的页面。
• 禁止位：禁止访问Buffer一类的高速缓存，用于映射到设备寄存器而不是常规内存的页面。
  

  加速分页过程

  要解决的问题：

1. 虚拟地址到物理地址的映射要快
2. 如果虚拟地址空间很大，页表也会很大

转换检测缓冲区

设置一个小型硬件，叫转换检测缓冲区（Translation Lookaside Buffer，TLB），通常在MMU中，包含少量表项。

如果发现有效匹配，并且访问操作不违反保护位，则将页框号从TLB中取出，而不必再访问页表。如果虚拟页面号在TLB中，但指令读写不符合保护位，就会产生保护错误。
如果虚拟页号不在TLB中，就正常页表查询，接着从TLB中淘汰一个表项，用新的页表项代替它。
当表项被清除出TLB时，将修改为复制到内存中的页表项。

软件TLB管理

用软件管理TLB，高效，加速。

1. 软失效：一个页面访问在内存中，不在TLB中。要更新一下TLB，不需要I/O
2. 硬失效：页面本身不在内存中（当然不在TLB中），要进行一次磁盘I/O，装入页面。

   针对大内存的页表

   多级页表

   
   32位地址：前10 是页表1，中间10 是页表2，最后12是偏移量
   避免把全部页表一直保存在内存中
   索引顶级页表→二级页表

   倒排页表（64位机）

   实际内存中每个页框有一个表项，而不是每个虚拟页面有一个表项。
   缺点：从虚拟地址到物理地址转换必须搜索整个倒排页表来查找某个表项

局部性原理

局部性原理：CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都区域聚集在一个较小的连续区域中。

• 时间局部性：如果一个信息项正在被访问，那么在近期它可能还会被再次访问
• 空间局部性：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是邻近的

  写时拷贝（Copy on Write）

  两个进程同时指向一个页面，当一个进程对页面A进行写操作，导致页面A变化时，创建一个A的副本。

该技术提供了快速的进程创建，并最小化了必须分配被新创建进程页面的数量。
这些共享页面被标记为“写时拷贝”页面，意味着如果其中一个段进程堆共享页面进行了写操作，那么将创建一个共享页面的拷贝。

分段

虚拟内存是一维的
分段是二维的：段号+段内地址
分段存储的产生：分页一维，表随着编译不断增长，只能被分配到连续的块中。
每个段由一个从0到最大的线性地址序列构成
各个段的长度可以是0到某个允许的最大值之间的任何一个值
不同的段的长度可以不同，并且可以动态改变。

纯分段实现

页是定长的，段不是定长的

这里面的碎片叫外部碎片or棋盘型碎片

段表

段号	段长	基址

段表记录了内存中的起始位置，各个段的段表项的长度相同。

分段分页结合：MULTICS

分页、分段

	优点	缺点
分页	内存利用率高，不会产生外部碎片	不方便按照逻辑模块实现信息的共享和保护
分段	很方便按照逻辑模块实现信息共享和保护	如果段长过大，为其分配很大连续空间不方便。同时会产生外部碎片。

逻辑地址结构：

段号	页号	页内偏移量

段表

段号	页表长度	页表存放地址

把段分页的操作是由操作系统完成的，对用户不可见。
一个进程→一个段表→多个页表
3次访问内存

1. 访问段表
2. 访问页表
3. 访问对应物理单元
   如果有快表（TLB）命中，就一次访存

页面置换算法

最优页面置换算法（Optimal Replacement Algorithm）

替换掉最远会被访问的页面（最近最不会被访问的页面）

问题在于这个算法实现不了，因为不知道未来哪个页面会被访问。

先进先出页面置换算法（FIFO Replacement Algorithm）

替换掉最先读入内存的页
是最简单的页面置换算法
表现并不是一直很好

第二次机会页面置换算法（Second Chance Replacement Algorithm）

在FIFO基础上做一点点修改。
检查最老页面的R位

• 如果R位是0，那么这个页面又老又没用，就替换出去。
• 如果R位是1，就把R清0，并把这个页面放到链表的尾部（假装变成最近装入的页面），然后继续搜索

这里页面上的数字是被装入的时间

时钟页面置换算法（Simple Clock Page Replacement Algorithm）

第二次机会算法经常要在链表中移动页面，这样既降低了效率又没必要，所以把所有页面保存在一个类似钟面的环形链表中，一个表针总是指向最老的页面。

发生缺页中断时，如果R位是0，就置换新的页面，并且表针前移一个位置，如果R位是1，就清除R，并把表针前移一个位置。

最近最少使用页面置换算法（Least Recently Used Replacement Algorithm）

Least Recently Used（LRU）：最近久未使用
在缺页中断发生时，置换未使 用时间最长的页面

LRU算法的实现

1. 需要维护一个链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。但是链表需要在每次发生内存读取的时候更新一次。
2. 64位计数器C：每条指令执行完后自动+1，每个页表项必须有一个容纳这个计数器值的域，每次访问内存后，将C的值保存到被访问页面的页表项中，发生缺页中断，操作系统就检查所有页表项中计数器的值，找到值最小的页面。
3. n×n位矩阵：当访问页框k时，把k行的位都置1，然后把k列位都置0。在任何时刻，二进制数值最小的行，就是最近最少使用的。

LRU栈置换

每当一个页面被访问，就把他从栈中删除，然后加在栈顶。
这样在栈顶的就是最近最常被访问的，而在栈底的就是最近最少访问的页框。

最不常用页面置换算法（Not Frequently Used Replacement Algorithm）

软件模拟LRU

NFU（Not Frequently Used，最不常用）算法，每个页面有一个计数器，每次时钟中断时，由操作系统扫描内存中的所有页面，将每个页面的R位（0/1）加到计数器上。发生缺页中断时，置换计数器值最小的页面。
但是该算法不会忘记信息，比如在1时刻经常使用，后来不常使用，但仍然不被替换出去。

老化算法（Aging Algorithm）

修改NFU：

1. 在R位被加进之前，先将计数器右移一位
2. 将R位加到计数器最左端的位而不是最右端的位

最少使用置换算法（Least Frequently Used）

淘汰最近访问频率最小的元素
好像就是老化算法…
不对，它是各个位加起来，不是二进制串的最大值
意思是：00011111，要比10000000大。

最近未使用页面置换算法（Not Recently Used Replacement Algorithm）

改进版的Second-Change Algorithm
由两个位（Read，Modify）

• 1. （0，0）：没有被访问，没有被修改
• 1. （0，1）：没有被访问，已经被修改
• 1. （1，0）：已经被访问，没有被修改
• 1. （1，1）：已经被访问，已经被修改

第1类是第3类R位清零后的结果

R位被定期清零（比如每次时钟中断）
随机选择一个编号最小的非空类中的页面淘汰
算法思想：在最近一个时钟中，淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的“干净”页面好

页面缓冲算法（Page-Buffering Algorithm）

？？？

工作集页面置换算法

工作集：一个进程当前正在使用的页面的集合就称为工作集。
如果整个工作集都在内存中，程序知道运行到下一个执行阶段才会发生中断。
抖动（thrashing）：如果每执行几条指令程序就发生一次缺页中断，那么就称这个程序发生了抖动/颠簸。
工作集模型：设法跟踪进程的工作集，以确保在让进程运行以前，它的工作集就已在内存中了
预先调页（prepaging）：让进程预先装入其工作集页面
工作集：w（k，t）k=最近k次内存访问访问过的页面，t=在任意t时刻。

算法思路：找出一个不在工作集中的页面并淘汰它。
需要两条信息：上次使用该页面的近似时间、R位

扫描页面检查R位

1. 若R==1，设置上次使用时间为当前实际时间
2. 若R==0 && 生存时间 > τ，移出这个页面
3. 若R==0 && 生存时间 ≤ τ，记住最小时间（生存时间最长的时间）

如果扫描完仍然没有空位，就淘汰生存时间最长的页面。

工作集时钟页面置换算法

WSClock：实现简单，性能较好
和Clock一样，是一个页框为元素的循环表
表项有：上次使用时间、R位、M位

缺页中断 发生，检查指针指向页面

• 如果R位是1，则置0，指向下一个元素
• 如果R位是0，且页面生存时间＞τ，且页面干净，则不在工作集中，置换该页面。如果页面被修改过（脏的），就不能立即置换，指针继续前进，检查下一个。

Summary

最好的两个是：老化算法、工作集时钟算法

Stack Algorithm——栈式算法

Belady’s Anomaly

对于某些页面置换算法，页框增加，缺页中断次数反而增加
FIFO会出现，内存越大，反而发生缺页中断的次数变多的情况

如果内存中页数更小的集合是内存页数更大的集合的子集，这个算法被称为stack algorithm。可以证明stack algorithm(如LRU)不会出现belady现象，FIFO会出现。

Stack Algorithm

Distance Strings

距离字符串，描述同一个页面两次访问操作的距离（即上次访问后的几次页的访问再次访问同一页）
Depends on：

• Reference String
• Page Replacement Algorithms
• To forecast page fault rate in different memory sizes

  Predicting Page Fault Rates

  

Design Issues for Paging Systems

局部分配策略与全局分配策略

• 局部页面置换算法：有效地为每个进程分配固定的内存片段
• 全局页面置换算法：全局算法在可运行进程之间动态地分配页框，因此分配给各个进程的页框数是随时间变化的
  

使用PFF缺页中断率算法，指出何时增加or减少分配给一个进程的页面，但是没说应该替换哪个页面，只是说分配集的大小。
缺页中断率：计算每秒的缺页中断数。
FIFO、LRU，既适应局部置换算法，也可以全局置换算法。

Thrashing 抖动

每次发生缺页中断，就说是一次抖动/颠簸
交换 进出
高频页面活动也是抖动
如果进程换页的时间比执行时间占比高，就是进程抖动

发生原因

1. 多进程
   全局页面置换算法
   循环从另一个过程中获取页框
   进程换页的时间比执行时间占比高，就是抖动

2. 操作系统监视CPU使用率，如果CPU利用率过低，就让多进程执行多一些
   使用全局置换算法，不考虑这些也属于哪个进程
   现在假设进程进入新的执行阶段，并且需要更多页框

   • 开始缺页中断，抢夺其他进程需要使用的页框。那些进程页缺页中断，继续抢夺其他进程的页框。

   • 这些缺页中断的进程需要使用分页设备来换入换出页，那分页设备队列执行，准备队列就空了

     当进程等待分页设备执行，CPU利用率就低了，回到开始，再次循环。
     

     防止抖动措施

     使用局部置换算法（或优先级置换算法）
     工作集模型（工作集窗口）
     $L=S$；

• L：平均缺页中断频率
• S：平均缺页中断不止次数
• CPU：最佳利用率

L 大于 S，很少缺页，磁盘能力没有被充分利用。
L 小于 S，频繁缺页，超过磁盘的处理能力。
挂起一些进程

Load Control 负载控制

总会发生抖动
唯一的解决方案就是：暂时从内存中去掉一些进程

Page Size 页面大小

页面大小是操作系统可以选择的参数
选择小页面
好处：

• 减少内部碎片
• 更好适应多样的数据结构，代码块
• 减少内存中没用的程序
  坏处：
• 更大的页表，程序需要更多页面

进程平均大小s个字节，页面大小p个字节，每个页表需要e个字节。
开销=se/p+p/2
最优页面大小公式：$P=\sqrt{2se}$

分离指令空间和数据空间

共享页面