《现代操作系统》读书笔记（三）——存储管理

3.1 无存储器抽象

早期的计算机的存储器没有抽象，程序引用的内存地址都是物理地址，这样的话程序中只可以运行一个进程，如果说运行两个进程的话就容易造成一个进程访问另一个进程的地址空间，然后两个进程同时崩溃。
还可以把一个进程暂停运行后把信息保存在磁盘中，然后把另一个进程的信息从磁盘中中读取到内存中，当这个进程暂停运行后，再把另一个进程的信息从磁盘中读取到内存中，这样就会发生大量的内存交换，效率低下。

3.2 一种存储器抽象：地址空间

3.2.1 地址空间的概念

地址空间（address space）是一个进程可用于寻址内存的一套地址集合。

3.2.2 交换技术

处理内存超载的通用办法之一是交换（swapping）技术，即把一个进程完整调入内存，使该进程运行一段时间，然后把它存回磁盘，空闲进程主要存储在磁盘上，所以当它们不运行时就不会占用内存，尽管它们的一些进程会周期性地被唤醒以完成相关工作，然后就又进入睡眠状态。
交换在内存中产生了多个空闲区（hole，即空洞），通过把所有的进程尽可能向下移动，有可能将这些小的空闲区合成一大块，该技术称为内存紧缩（memory compaction）。这个操作通常不进行，因为它要耗费大量的CPU时间。
考虑到进程空间会增长，在给进程分配内存空间之初，就可为此进程预留适当大小的增长空间，这样就不用通过移动相邻地址进程的的内存空间来增长自己的内存空间了。

3.2.3 空闲内存管理

使用位图的存储管理
内存可能被划分成小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位，0表示空闲，1表示占用（或者相反）。
内存分配时搜索位图、查找位图中指定长度连读串都较费时，是位图的缺点。
使用链表的存储管理
维护一个记录已分配内存段和空闲内存段的链表。其中链表中的一个结点或者包含一个进程，或者是两个进程间的一个空的空闲区。链表中的每一个结点都包含以下域：空闲区或进程的指示标志、起始地址、长度和指向下一结点的指针。若被释放的地址空间的相邻地址空间是空闲区，则需要合并这两个空闲区。
内存分配算法有（若进程和空闲区使用不同的链表，并对链表每个节点进行从小到大排序，第2种和第3种效果一样，都很快）：
(1) 首次适配（first fit）算法
搜索链表，直到找到一个足够大的空闲区，除非空闲区大小和要分配的空间大小正好一样，否则将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。
(2) 下次适配（next fit）算法
在下次寻找空闲区时从上次搜索链表结束的地方开始搜索，工作方式与首次适配法的一样。
(3) 最佳适配（best fit）算法
搜索链表，找出能够容纳进程的最小的空闲区。试图找出最接近实际需要的空闲区，以最好地区配请求和可用空闲区，而不是先拆分一个以后可能会用到的大的空闲区。
(4) 最差适配（worst fit）算法
总是分配最大的可用空闲区，使新的空闲区比较大从而可以继续使用。
(5) 快速适配（quick fit）算法
为常用大小的空闲区维护单独的链表。

内部碎片（internal fragmentation）是由于采用固定大小的内存分区，当一个进程不能完全使用分给它的固定内存区域时就产生了内部碎片，通常内部碎片难以完全避免。外部碎片（external fragmentation）是由于某些未分配的连续内存区域太小，以至于不能满足任意进程的内存分配请求，从而不能被进程利用的内存区域。

3.3 虚拟内存

虚拟内存（virtual memory）的基本思想是：每个程序拥有自己的地址空间，这个空间被分割成多个块，每一块称作一页或页面（page），每一页有连续的地址范围，这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序运行到一部分在物理内存中的地址空间时，由硬件立即执行必要的映射；当程序运行到的一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的命令。
虚拟内存是对基址寄存器和界限寄存器的一种综合。

3.3.1 分页

大部分虚拟内存系统中都使用了一种称为分页（paging）的技术。
由程序产生的这些地址称为虚拟地址（virtual address），它们构成了一个虚拟地址空间（virtual address space）。在使用虚拟内存的情况下，虚拟地址不是被直接送到内存总线上，而是被送到内存管理单元（Memory Management Unit，MMU），MMU把虚拟地址映射为物理内存地址。
虚拟地址空间按照固定大小划分成称为页面的若干单元。在物理内存中对应的单元称为页框（page frame）。页面和页框大小通常是一样的。
当MMU接收到一个虚拟页面时发现该页面未被映射时，CPU陷入到操作系统，这个陷阱称为缺页中断（page fault），操作系统找到一个很少使用的页框且把它的内容写入磁盘（如果它不在磁盘上），随后把需要访问的页面读到刚才回收的页框中，修改映射关系，然后重新启动引起陷阱的指令。
可用页号作为页表的索引，以得出对应于该虚拟页面的页框号。

3.3.2 页表

分页转换功能由驻留在内存中的表来描述，该表称为页表（page table），存放在物理地址空间中。
虚拟地址到物理地址的映射：虚拟地址被分成虚拟页号（高位部分）和偏移量（低位部分）两部分，虚拟页号可用作页表的索引，以找到该虚拟页面对应的页表项，由页表项可以找到页框号（如果有的话），然后把页框号拼接到偏移量的高位端，以替换掉虚拟页号，形成送往内存的物理地址。
页表的目的是把虚拟页面映射为页框。
当前进程的页表起始地址存放在页表基址寄存器（Page Table Base Register，PTBR）中。

3.3.3 加速分页过程

在任何分页式系统中，都需要考虑两个主要问题：1)虚拟地址到物理地址的映射必须非常快；2)如果虚拟地址空间很大，页表也会很大。前一个问题的解决办法就是设置一个小型的硬件设备，将虚拟地址直接映射到物理地址，而不必再访问页表。这种设备成为转换检测缓冲区（Translation Lookaside Buffer，TLB），有时又称为相联存储器（associate memory）或快表。
将一个虚拟地址放入MMU中进行转换时，硬件首先通过将虚拟号与TLB中所有表项同时（即并行）进行匹配，判断虚拟页面是否在其中。如果发现了一个有效的匹配并且要进行的访问操作并不违反保护位，则将页框号直接从TLB中取出而不必再访问页表；如果虚拟页面号确实是在TLB中，但指令试图在一个只读页面上进行写操作，则会产生一个保护错误，就像对页表进行非法访问一样。如果MMU没有检测到TLB中有有效的匹配项，就会进行正常的页表查询，接着从TLB中淘汰一个表项，然后用新的页表项代替它。当一个表项被清除出TLB时，将修改位复制到内存中的页表项，而除了访问位，其他的值不变。
TLB管理和失效处理可以用硬件也可以用软件。
TLB失效比缺页中断更加频繁。当一个页面访问在内存中而不再TLB中时，将产生软失效（soft miss）。当页面访问既不在TLB中也不在页表中时，将产生硬失效（hard miss）。

3.3.4 针对大内存的页表

引入TLB可以用来加快虚拟地址到物理地址的转换。
处理巨大的虚拟地址空间的方法：

多级页表
通过上一级页表为下一级页表提供索引，最后一级页表的内容才是其物理地址。这样降低了线性查找的次数。
倒排页表
64位机中，多级页表所占内存过大，需要其他解决方案。
在倒排页表（inverted page table）这种设计中，使用页框号而不是虚拟页号来索引页表项，虚拟地址的页号部分使用一个简单的散列函数映射到散列表中，散列表包含一个指向倒排表的指针，而倒排表中含有页表项。通过这个结构，散列表和倒排表中各有一项对应于一个实存页。因此，不论有多少个进程、支持多少虚拟页，页表的大小都是固定的。

3.4 页面置换算法

当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本。如果没被修改过，直接用调入的页面覆盖被淘汰的页面就可以了。
在计算机设计的许多场景如高速缓存更新数据、Web服务器更新页面，“页面置换”问题也会同样发生。

3.4.1 最优（Optional，OPT）页面置换算法

页面数达上限时，将内存中未来将最少使用的页面换出内存（若有更改则需更新磁盘中相应内容），将需要的页面替换进内存。
这种算法是无法实现的。

3.4.2 最近未使用（Not Recently Used，NRU）页面置换算法

该算法为每个页面设置两个硬件位——访问位和修改位，开始时所有页的访问位和修改位都设为0，访问或修改时再置1，访问位会定期（如每次时钟中断时）清0，根据两位分四类（优先级由高到低）：未被访问且未被修改、未被访问且已被修改、已被访问且未被修改、已被访问且已被修改，从优先级最高的类中挑一个页面进行置换。
这种算法性能不是最好但已够用。

3.4.3 先进先出（First-in First-out，FIFO）页面置换算法

每次置换出存在内存中时间最久的页面。
这种算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

3.4.4 第二次机会（Second Chance，SC）页面置换算法

是对NRU算法和FIFO算法的改进，每个页面设置一个脏位初始化为0代表未使用过，若使用则赋为1，页面数量达上限后置换时将从头开始遍历，若脏位为0则正常置换，若脏位为1则将其清0且移植最尾端然后继续搜寻合适的被置换页面。
这种算法算比较可以，但是移动页面的操作效率较低且不是太有必要。

3.4.5 时钟（Clock）页面置换算法

是对SC算法的改进，将线性的页面数据结构变成环形的，用指针指向一个页面作为遍历的起点，规定只能向一个方向进行遍历，页面数量达上限后置换时，若脏位为0则正常置换，若脏位为1则将其清0且将指针指向下一个页面继续搜寻合适的被置换页面。

3.4.6 最近最少使用（Least Recently Used，LRU）页面置换算法

达页面数上限时将最久未使用的页面置换出去，每次都检查页面是否已经存在，若存在则将其移至头部，若不存在则丢弃尾部页面（若有更改则需更新磁盘中相应内容）且将新页面加至头部。
这种算法理论上可实现，且最接近OPT算法，但是代价高。

3.4.7 用软件模拟LRU

使用哈希表存储所有页面号，可快速查出此页面是否存在；用双向链表作为内存中所有页面串联的数据结构，方便头部和尾部的增删，也方便中部项的移动。
可引入脏位，修改后的算法称为老化（Aging）页面置换算法。
还有最少/不常用（Least/Not Frequently Used，LFU/NFU）页面置换算法，即置换过去使用频率最低的页面出去。

3.4.8 工作集（Working Set，WS）页面置换算法

引入工作集的概念，将多个在内存中的同进程的页面放入一个滑动窗口中，一旦一个页面不属于当前进程了就换出，缺页则换入窗口中。

3.4.9 工作集时钟（Working Set Clock，WSClock）页面置换算法

将页面用环形数据结构存储起来，搜索方式与Clock算法类似，当工作集缺页中断时，进行Clock算法。

3.4.10 页面置换算法小结

OPT算法不可实现，可作为基准；NRU算法是与LRU算法很粗糙的近似；FIFO算法可能要抛弃重要页面；SC算法比FIFO算法有很大的改善；Clock算法是SC算法的优化；LRU算法很优秀，但很难实现；LFU/NFU算法是LRU算法的相对粗略地近似；Aging算法是与LRU算法非常近似的算法；WS算法实现起来开销很大；WSClock算法是好的有效的算法。
Aging算法和WSClock算法是最好的两种算法，分别基于LRU算法和WS算法。

3.5 分页系统中的设计问题

3.5.1 局部分配策略和全局分配策略

局部（local）页面置换算法就是将每个进程的页面置换过程分开，每个进程单独进行；全局（global）页面置换算法就是将所有进程页面置过程换合并为同一个过程，将所有页面集中管理。通常来说全局页面置换更好，尤其是在工作集的大小随进程运行时间发生变化时这种现象更加明显。若使用局部算法，即使有大量空闲页框存在，工作集的增长也会导致颠簸。如果工作集缩小了，局部算法又会浪费内存。
使用一个进程分配页框的算法，定期确定进程运行的数目，并为其分配内存。平均分配并不合适，因为进程大小不同，比较明智的做法是对每个进程都规定一个最下的页框数，不论多小的内存都可以运行。管理内存动态分配的一种方法是使用缺页中断率（Page Fault Frequency，PFF）算法，它指出了合适增加或者减小分配给一个进程的页面，但却完全没有说明在发生缺页中断的时候应该替换掉哪一个页面。PFF尽力让每个进程的缺页中断率控制在可接受的范围内。

3.5.2 负载控制

短时间内频繁发生缺页中断称为页面抖动（page thrashing，即页面颠簸）。
进程物理页面太少，不能包含工作集，造成大量缺页，频繁置换，进程运行速度变慢；随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。
操作系统需在并发水平和缺页率之间达到一个平衡，选择一个适当的进程数目和进程需要的物理页面数。
在进程过多的情况下，必须要从内存中暂时去掉一些进程。将其交换到磁盘，并释放他们所占有的所有页面。

3.5.3 页面大小

选择大页面：1)会产生许多内部碎片，2)会使过多没用的程序留在内存中；选择小页面：1)页表会很大，2）内存和硬盘间传输页面次数会很多。
常见的页面大小是4KB。

3.5.4 分离的指令空间和数据空间

为指令和数据设置分离的地址空间。

3.5.5 共享页面

使不同用户不用进程共同使用某一个页面。

3.5.6 共享库

共享库是更加通用的技术，如果程序调用了未定义外部函数（undefined externals），链接器会在库中寻找这些未定义外部函数，如果找到了则将他们加载到可执行二进制文件中。
使用共享库的好处是：1)降低可执行文件大小，2)共享库中的函数被更新不需重新编译源程序。

3.5.7 内存映射文件

内存映射文件（memory-mapped file）机制：进程可以通过发起一个系统调用，将一个文件映射到其虚拟地址空间的一部分。
如果两个进程同时访问了一个问题文件，可以通过共享内存来通信，这个机制为进程间通信提供了一个高带宽通道。

3.5.8 清除策略

称为分页守护进程（paging daemon）的后台进程：在大多数时候睡眠，但定期唤醒已检查内存状态。如果空闲页框过少，分页守护进程通过预定的页面置换算法选择页面换出内存，分页守护进程保证至少所有空闲页框是干净的，所有空闲页框在被分配时不需要在着急写回磁盘。可以使用一个双指针时钟，前指针由分页守护进程控制，当它指向一个脏页面时候，就把页面写会磁盘，前指针向前移动，当它指向一个干净页面时，仅仅指针向前移动，后指针用于页面置换。

3.5.9 虚拟内存接口

允许程序员对内存映射进控制的一个原因就是为了运行两个或者多个进程共享一部分内存。共享页面可以用来实现高性能的消息传递系统（一般地，传递消息的时候，数据被从一个地址空间复制到另一个地址空间，开销很大，如果进程可以控制它们的页面映射，就可以这样来发送一条消息：发送进程清除哪些包含消息的页的映射，而接受进程把它们映射进来，这里只需要复制页面的名字，而不需要复制所有数据）。

3.6 有关实现的问题

3.6.1 与分页有关的工作

进程创建时：创建页表，在磁盘交换区中分配空间以便在一个进程换出时在磁盘上有放置此进程的空间，用程序正文和数据对交换区进行初始化以便当新进程发生缺页中断时可以调用需要的页面，把有关页表和磁盘交换区的信息储存在进程中；
进程执行时：为新进程设重置MMU且刷新TLB以清除以前进程遗留下的痕迹（进程的页表必须称为当前的页表），把进程的一部分或全部页面装入内存已减少缺页中断；
缺页中断时：通过读硬件寄存器来确定是哪个虚拟地址造成了缺页中断并计算出页面在硬盘的位置，找到合适的页框来存放新页面且置换老的页面，把所需要的页面读入页框，备份程序计数器使程序计数器指向引起缺页中断的指令并重新执行该指令；
进程终止时：操作系统释放进程的页表、页面和页面在硬盘上占用的空间（如果这些页面是与其他进程共享的，当最后一个使用他们的进程终止的时候，才可以释放内存和磁盘上的页面）。

3.6.2 缺页中断处理

硬件陷入内核，在堆栈中保存程序计数器，大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中；
启动一个汇编代码例程来保存通用寄存和其他易失的信息，以免被操作系统破坏（这个例程将操作系统作为一个函数来调用）；
发生缺页中断时，尝试发现需要哪个虚拟页面；
操作系统检查发生缺页中断的虚拟地址是否有效、存取与保护是否一致（如果不一致，则杀死进程或发出一个信号；如果有效且没有保护错误发生，则检查是否有空闲页框，如果没有空闲页框，则执行页面置换算法寻找一个页面来淘汰）；
如果选择的页框“脏了”，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束，该页框需要被标记为忙；
一旦页框干净后（无论是立刻还是写回磁盘后），操作系统查找需要页面在磁盘上的地址，通过磁盘操作将其装入，此时该进程仍然被挂起，可以运行其他进程；
当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态；
恢复发生缺页中断前的状态，程序计数器重新指向这条指令；
调度引发中断的程序，操作系统返回调用它的汇编语言例程；
该例程恢复寄存器和其他状态信息，返回到用户空间继续执行，就好像缺页中断没有发生过一样。

3.6.3 指令备份

通过使用一个隐藏的内部寄存器，在每条指令执行之前，把程序计数器的内容复制到该寄存器。有些计算机还有第二个寄存器，用来提供哪些寄存器已经自动增加或者减少已经增减的信息数量。

3.6.4 锁定内存中的页面

有虚拟内存，并不意味着I/O就没用了，I/O用于读取文件或读取设备信息。
有时候I/O缓冲区和缺页调用有冲突，I/O缓冲区很小的几率被选出调出缓冲区，通常这样的情况的解决办法是锁住正在做I/O操作的内存中的页面以保证它不会被移出内存（锁住一个页面通常称为在内存中钉住（pinning））。

3.6.5 后备存储

页面从内存换出的时候应该放到哪：在磁盘上设置一个特殊的交换分区，甚至从文件系统划分一块独立的磁盘（以平衡I/O负载）。可以对静态交换区分页或动态备份页面，但都不能保证总是实现固定的交换分区。

3.6.6 策略和机制的分离

优势是有更多模块化代码和更好的适应性，劣势是多次交叉“用户-内核”边界会引起额外开销。

3.7 分段

在机器上提供多个互相独立的称为段（segment）的地址空间。每个段都构成了一个独立的地址空间，可以独立地增长或减小而不会影响到其他的段。段是一个逻辑实体。

3.7.1 纯分段的实现

会产生很多外部碎片。

3.7.2 分段和分页结合：MULTICS

用分段方法来分配和管理虚拟存储器，程序的地址空间按逻辑单位分成基本独立的段，而每一段有自己的段名，再把每段分成固定大小的若干页；用分页方法来分配和管理实存，即把整个主存分成与上述页大小相等的存储块，可装入作业的任何一页，程序对内存的调入或调出是按页进行的。但它又可按段实现共享和保护。

3.8 有关存储管理的研究

3.9 小结

内存和磁盘上的空闲空间使用位图或空闲区列表来记录。
Aging算法和WSClock算法是两种较好的页面置换算法。
为了使分页系统工作良好，仅选择算法是不够的，还要关注诸如工作集的确定、存储器分配策略以及所需要的页面大小等问题。
将分页和分段结合的段页式储存是一种二维的虚拟内存。

博文补充（转）：
《Linux内核设计与实现》读书笔记（十二）- 内存管理
 《Linux内核设计与实现》读书笔记（十五）- 进程地址空间（kernel 2.6.32.60）