OSTEP学习笔记-内存虚拟化

Contents

1. 内存虚拟化
2. 内存分类
3. 相关API
1. 3.1. 常见错误
4. 实现机制
5. 分段
6. MMU如何区别segment
7. 共享内存
8. 内存碎片
1. 8.1. 自由空间的表示
9. 基本空间管理策略

　　近日在粗读操作系统相关书籍，接触到的一些知识点说起来在其它类似“微机原理”，“C程序设计”，“UNIX环境高级编程”的书中隐约都有接触，但是没有这么系统，总的来说收获还不错，粗略记录些摘要权当笔记。

内存虚拟化

　　无论是进程与进程之间，还是进程与OS之间的内存，都不应该互相干涉。进程之前内存存在干涉会导致运行错误，而进程干涉OS内存将直接导致系统崩溃等严重后果。
　　所以最好的方式是进行虚拟化，实现隔离，互相给出独立的内存空间，需要做到考虑三点
1、透明。
　　隔离必需对进程透明，进程不需要关系内存地址是否虚拟。保证程序设计的简洁性（无需关心内存类型、起始地址等）。
2、效率。
　　虚拟化不应该消耗太多的时间性能和额外存储空间。
3、安全
　　进程必须不能越界，保证隔离效果。

隔离是一种常用思想，例如理论上microkernels微内核就比monolithic kernel单内核更稳定。是不是想到了kernel pannic :-）

　　实际上只有OS能够访问实际的物理地址，进程使用的全是虚拟地址，也就是我们用C程序打印的指针值，都是虚拟地址。

内存分类

　　大致上一个进程的内存可以分别三块：

静态数据

堆

栈

　　实际可以更细分，静态数据包包含了代码、常量等。但对当前问题我们只需要如此分类即可。

　　静态数据的空间是固定的，运行期间不会变化；堆空间是由程序员显式管理的，而栈是由系统自动管理（自动变量、调用栈等）的。后两者在运行时是变化的，通常将二者的一个置于靠近顶部，一个置于底部，两者共同向中增长，这样能达到最大的利用率。

实现机制

　　实现这种虚拟化其实比想象中的还要简单：地址翻译。这主要是基于硬件实现的，每个CPU都有一个MMU，维持两个寄存器base,bound,它们分别代表虚拟地址与物理地址之间的offset以及分配到的内存大小。而操作这对寄存器是需要kernel mode权限的，一旦越界会产生异常，控制权就会回到OS手中。
　　当进程访问虚拟地址时，CPU会将虚拟地址与base相加，得到真实地址，当然还会与bound比对确认是否越界。

分段

　　这种简单的虚拟化有一个严重的问题：空间浪费。进程需要的内存大小是未知且变化的，但上述方式只能一次性分配足够的内存，而实际运行中往往会大部分处于闲置状态，也就是sparse address space。解决这个问题的方式也不复杂：分段。

　　所谓分段就是将静态、堆、栈分别用三对base,bound寄存器来翻译，也就是三者可以独立分配，这样堆与栈就不用担心增长方面的问题，可按实际使用量占有空间。
　　比如在C程序中，如果指针操作不当，就可能出现著名的Segmentation fault错误。

#include <stdlib.h>
main(){
    int *pi = malloc(sizeof(int));
    *(pi - 100) = 10;
}

编译运行

1
2
3

$cc seg.c
$ ./a.out
Segmentation fault (core dumped)

MMU如何区别segment

　　处理器如何知道进程的虚拟地址应与三个base中的哪个相加呢？有不同的实现方法。
1、显式分段
　　根据地址大小分割。例如如果分割3段，那么可以将前两位作为分段标识：00为code,01为heap,10为stack。剩余的位则作为offset与base相加。
　　这样分割会导致11区段空闲，所以有些系统将code，heap合并共用一段，只用1位区别segment。
2、隐性分段
　　根据地址来源决定分段，比如如果来自PC，那么是code，如果是栈+偏移或基本指针得到，则为stack段，其它归为heap。

共享内存

　　code share在当今的OS中也有在使用，实现的原理是为内存添加rwx(读写执行）标识，只读内容可以在进程间共享而不用担心破坏隔离。当然检测内存操作是否违规也要增加相应的操作。

内存碎片

　　不断地为进程分区segment会导致fragmentation。一种解决方案是“碎片整理”，暂停进程，复制数据并更新MMU中的寄存器。这种方式开销较高，更常用的方法是依赖科学的分配算法来尽量减小碎片化。
　　但是就像CPU调度算法一样，虽然实现方式繁多，但是没有一个是完美的，所有算法还在不停地进化当中。

自由空间的表示

　　可以用一个类似链表结构来表示。下图表示了两个长度为10的空闲段，即0->9, 20->29，它们中间有一个10->19长度为10的已使用段。

　　如果要分配一个<10的空间，比如5，那么将一个节点分割（此处使用第二个为例），其中原起始地址addr作为malloc返回，并更新链表节点，比如将第二个节点更新为addr:25,len=5。

　　在调用free()函数的时候，并没有传入长度值，系统使用了额外的内存空间来记录区块信息，所以malloc时实际会消耗少量额外字节。

ptr是malloc返回值，free操作时，使用ptr-sizeof(header_t)就能得到头信息，size记录了区块大小，magic用于校验ptr有效性（确实是malloc分配出去的，而不是任意值）。

　　另外free操作时，系统会检查相邻的区块是否可以合并，从而提供更大单块可分配空间。

　　最后需要指出的是，这些管理工作都是由库执行的。

基本空间管理策略

Best Fit
　　遍历所有节点找出空间足够同时最小的空闲段用于分配
Worse Fit
　　遍历所有节点找出空间最大的空闲段用于分配。（挺奇怪不是吗？这样做初衷是让让碎片尽量少，但实际表现往往糟糕）
First Fit
　　使用第一个找到的空闲段。因为不需要遍历，所以速度佳，但频繁操作列表前段，所以节点的排序方式很重要。比如按地址大小排序方便合并操作。
Next Fit
　　上述方法的改进型，使用第二个空闲段。性能基本相同，但可使空间分配遍布整个空闲列表。

　　以上都是原始的管理策略，与实际OS管理方式差别很大。

Segregated Lists

　　这是一种已有一段历史的方式：为最常出现的size的空间请求设计专门的allocator,因为大小固定，速度和防碎片化方面有很好表现。但需要安排好特定size和其它通用请求间内存的分配问题。

　　例如kernel启动时，会分配许多object cache作为lock,inode等的存储，于是它们分别属于不同的特定size的segregated list。当特定size的内存配额用完时，也可以向通用allocator请求slabs of memory,反向亦可。slab allocator还会预留一些自由的初始化对象，以避免高消耗的频繁初始化/析构过程。

binary buddy allocator

　　此设计针对碎片处理设计。初时将整个内存看作2^n次大小，当内存请求到来时，找到区块大小为2^k （0 < k < n）中samllest fit大小块进行分配。从而也不可避免的存在内部碎片化问题（分配大小与实际使用大小不一致）。
　　此方式强大在于free时可以方便地检查相邻区块（地址只有一位有效位不同）是否空闲，是则合并，如此递归。

其它

　　使用列表扩展性差，特别遍历效率低。因而经常会用数据结构的复杂度来换取时间性能，比如平衡二叉树、伸展树或者半序树等。
　　另外多线程设计和多核系统的流行也使得相关方面的内存分配工作研究很多。

AzYet's Notebook

Just writing some notes as memo, nothing complicated.