OSTEP 学习笔记 —— Virtualization

Operating Systems: Three Easy Pieces第一部分 Virtualization 的学习笔记

A Dialogue on Virtualization

我觉得这个比喻很怪peach 怎么能 virtualize感觉不如举个别的例子但挑 og:image 的时候想了想这不桃 channel

The Abstraction: The Process

所谓 process就是 a running program

一个 process 的 machine state 包括 memoryregister包括 PCstack pointer 等I/O information例如打开的文件列表

在创建 process 时OS 需要 (lazy) load program code 和 data初始化 stack 和 heap设置 argcargv设置 stdinstdoutstderr 三个 file descriptor

一个 process 有三种 staterunningblockedready

initiate I/O

finish I/O

schedule

deschedule

Running

Blocked

Ready

OS 的 scheduler 需要决定如何调度 process state以优化性能例如一个 process initiate I/O 后应当 schedule 到另一个 ready 的 process

OS 需要维护 process list记录 process memory addresskernel stack addressregister contextprocess statepidparentkilledopened filescwdtrap frame 等信息

Interlude: Process API

fork()wait()exec() 以及 signals 参见 CS:APP 第八章

fork()exec() 通常配合使用而被设计成了分离的两个 API所以可以在它们之间插入其他代码以修改 child process 的执行环境例如在 shell 中执行命令可以创建 child process 然后 wait如果需要 redirect output可以在 fork()exec() 之间执行 close()open()

Mechanism: Limited Direct Execution

direct execution 就是直接执行一个 program但这样做无法对 user program 进行限制例如可能访问包括 kernel memory其他 process 在内的任意 memory一直运行而不把 control 交给 OS所以OS 需要采用 limited direct execution对 process 施加限制这样做虽然 limited但依然是 CPU 直接执行 user program instruction所以不会有太多的 overhead

Problem #1: Restricted Operations

为了限制 user program 的行为CPU 的执行分为 user modekernel modekernel mode 具有更高的权限例如可以直接访问 memory执行 I/O

user program 需要通过 system call 来进入 kernel mode由 OS 执行相应的操作system call 是一种特殊的 trapexception通过 trap instruction 进入 trap handler 并把 register 等状态存下来操作执行完毕后再 return-from-trap 回到 user program 调用 system call 之后的位置并恢复 register 等状态

在系统启动时OS 会设置 trap table即各种 trap 对应的 handler addresssystem-call number放在特定 register 或 stack 特定位置用来指定要执行哪个 system calltrap table 只能由 OS 设定以避免 user program 任意指定 kernel mode 下跳转到的位置

Problem #2: Switching Between Processes

在一个 process 占用着 CPU 时OS 没有运行自然无法实现 control所以需要 user program 把 control 交给 OS这有两种方式一种是 cooperative approach即调用 system call一种是 non-cooperative approach即使用 timer interrupt每隔一段时间就把 control 强制交给 OS以避免单个 process 连续运行过长时间甚至进入死循环而只能重启

决定了要切换 process 时OS 会进行 context switch主要操作是从 process A 的 registers 和 kernel stack 切换到 process B 的 registers 和 kernel stack之后 return-from-trap 时就会返回到 process B 之前离开的地方

Scheduling: Introduction

OS scheduler 需要决定 schedule 到哪个 process这表现为 scheduling policy (discipline)

Workload Assumptions

在这一部分我们先对 workload即需要运行的 processes即 jobs作一些不切实际的assumption 以简化问题后面再逐步丢弃这些 assumption

  1. 每个 job 用时相同
  2. 每个 job 同时 arrive
  3. 每个 job 一旦开始就一直运行到结束不被打断
  4. 每个 job 都只使用 CPU不使用 I/O没有 system call不会 blocked
  5. 每个 job 的用时是已知的

其中4 和 5 是最不切实际的没有 I/O 的 program 运行了没有任何意义scheduler 无法预知 job 要运行多久连是否停机都无法预知

Turnaround Time

turnaround time 是一个 scheduling metric它指的是一个 job 从 arrival 到 completion 的用时用来衡量总体性能

FIFO (first in first out / FCFS, first come first served) 是一种最简单的 scheduling policy在所有 5 个 assumption 下任何 scheduling policy 都是一样的FIFO 就可以达到最优

如果丢弃 assumption 1 而继续使用 FIFO当排在最前的 job 用时很长时会造成 convoy effect堵住后面用时短的其他 job使得 turnaround time 变得很大此时可以采用 SJF (shortest job first) 达到最优解

如果进一步丢弃 assumption 2有可能最长的 job 最先到短的 job 紧随其后SJF 就失效了此时需要再丢弃 assumption 3来允许 scheduler preempt 一个 job 而 schedule 到另一个不这样做的 scheduler 被称作 non-preemptive scheduler然后就可以采用 STCF (shortest time-to-completion first / PSJF, preemptive shortest job first) 达到最优解在新 job arrive 时如果它的总用时比当前 job 的剩余用时还短可以 schedule 到新 job

Response Time

为了让用户在交互中获得更好的体验turnaround time 是不够的还需要引入新的 metricresponse time它可以用一个 job 从 arrival 到 first run 的用时衡量

上面提到的各种 scheduling policy例如 STCFresponse time 都很差被排到后面运行的 job 需要等待很久

Round-Robin (RR) policy 会让每个 job 运行一个 time slice (scheduling quantum)然后切换到下一个 job所以 RR 也被称作 time-slicingtime slice 越小 response time 也就越小但如果 time slice 过小context switching包括存储/恢复 register以及 cache miss penalty在用时中的占比就会过大从而显著影响性能所以需要一定大小的 time slice 来 amortize 掉 context switching costRR 的 response time 较小但 turnaround time 很大比 FIFO 还大

一般来说如果一个 policy 是 fair均等地将 CPU 分配给各个 job就会有较差的 turnaround time 和较好的 response time如果一个 policy unfair就可以有较好的 turnaround time但 response time 会较大这是一个固有的 trade-off鱼与熊掌不可兼得1

Incorporating I/O

如果进一步丢弃 assumption 4即允许 job 进行 I/O则需要处理 blocked 的情况

一般来说可以将一个 job 视作被 I/O 分割成的多个 sub-job然后按照之前的 policy 进行 schedule例如使用 STCF 时在 sub-job 的视角下会优先运行 I/O 密集的 job这可以达成 overlap让 CPU 和 I/O 同时工作更加充分地利用系统资源

Scheduling: The Multi-Level Feedback Queue

之前这些简单的 scheduling policy 面临两大问题一是 turnaround time 和 response time 之间的矛盾二是 SJF/STCF 对 perfect knowledgeassumption 5的依赖

Multi-level Feed-back Queue (MLFQ) 是目前被广泛使用的一种 scheduling policy同时解决了这两大问题

Basic Rules

MLFQ 的基本思路是workload 可以分为两类一类是 short-running interactive job被 I/O 切成了小块一类是 long-running CPU-intensive jobinteractive job 更需要优先运行这既是 SJF/STCF 的基本思想同时也是因为 interactive job 对 response time 的要求更高

MLFQ 的基本运行规则为有多个不同 priority 的 job queue每次会选择 priority 最高的 queue在同一个 queue 内使用 RR

理想情况下interactive job 的 priority 会更高从而逼近 STCF

Priority Adjustment

因为 scheduler 无法预先知道 job 的类型priority 是根据程序的运行情况动态设置的

job arrive 时会先放在 priority 最高的 queue如果运行太久就会降低 priority具体来说一个 job 在每一级 queue 会获得一段 time allotment在这一级 queue 的累计运行时长如果超过 allotment 就会降低 priority 到下一级 queue

在这样的机制下会有两个问题

  • CPU 可能被几个 interactive job 占满导致 priority 低的 long-running job 一点 CPU 都拿不到这被称作 starvation
  • 一个 job 的行为可能随时间变化如果经过一段 CPU-intensive 后 priority 到了最低然后变为 interactivepriority 无法恢复

为了解决这两个问题可以每隔一段时间进行 priority boost将所有 job 的 priority 设为最高

Tuning MLFQ

MLFQ 有很多可以设置的参数queue (level) 的数量每个 level 的 time slice 和 allotment多久进行一次 priority boost一般来说priority 越高time slice 和 allotment 越短

MLFQ 不一定真的要实现为多个 queue也可以统计每个 job 的 CPU usage根据 usage 计算出 priority而让 usage 随时间 decay 来代替 priority boost这称作 decay-usage scheduling

priority 不一定要完全基于 feedback也可以参考由用户提供的 advice例如使用 nice 命令可以设置 niceness 来影响 job priority

Scheduling: Proportional Share

这章讨论的是一种不同的 scheduler它的主要目标是按一定的比例将 CPU 分配给各个 job例如在 virtualized data center / cloud 中可以将 CPU 均等地分配给各个用户

Lottery Scheduling

lottery scheduling每个 job 被分配了一定数量的 ticket每个 time slice 结束时随机选择一个 winning ticketschedule 到对应的 job时间久了之后会趋近于按 ticket 数量的 CPU 分配

lottery scheduling 还会提供一些 ticket mechanism

  • 可以给每个 user 一些 ticket每个 user 再将 ticket 分给各个 job
  • 一个 job 可以将自己的 ticket transfer 给其他 job
  • 如果各个 job 之间互相信任可以进行 ticket inflation一个 job 需要更多 CPU 时直接给自己更多 ticket 即可不需要和其他 job 沟通

Stride Scheduling

stride scheduling 不依赖于随机可以确定性地达到设定的比例

用一个大数除以每个 job 的 ticket value 得到每个 job 的 stride对每个 job 维护一个 pass每次运行一个 job 后将 pass 加上 strideschedule 到 pass 最低的 job每个循环内都会精确地达到设定的比例

stride scheduling 的一个劣势是新加入的 job 的 pass 不好设定而 lottery scheduling 不需要维护状态可以轻松地添加新的 job

The Linux Completely Fair Scheduler (CFS)

Linux 的 Completely Fair Scheduler (CFS) 高效而 scalable 地实现了 fair-share scheduling

CFS 会记录每个 job 的 virtual runtime (vruntime)每次运行后加上这次运行的时长schedule 到 vruntime 最低的 jobtime slice 是不固定的sched_latency 除以 job 数量决定并会与 min_granularity 取较大值防止 time slice 过小导致 context switching 过多time slice 可能不是 timer interrupt 的整数倍vruntime 会精确记录实际用时

可以通过设置 niceness 调整一个 job 的 weightniceness 越低 weight 越高呈指数降低的关系设置了 nicenesstime slice 会按照 weight 分配vruntime 每次增加的值会再调整回来weight 大的会获得更大的 time slice 而增长同样多的 vruntime

CFS 使用 red-black tree 维护各个 job 的 vruntime 以快速取出最小值一个 job blocked 时会从树上移除而再插入到树上时其 vruntime 会设为此时树上的最小值以避免一个长期 blocked 的 job 恢复后独占 CPU但这样会导致 I/O 频繁或长期 sleep 的 job 实际上没有拿到 fair share

作为一个得到了广泛实际应用的 schedulerCFS 还有很多其他 feature例如通过一些手段优化了 cache performance可以高效处理有多个 CPU 的情形可以将多个 process 视作一个 group 而不是对每单个 process 进行 schedule

Multiprocessor Scheduling

The Abstraction: Address Spaces

为了支持 time sharing需要在 physical memory 中同时存放多个 process 的 memory为了便于使用OS 需要将 physical memory virtualize提供称作 address space 的 abstraction

一个 process 的 address space 包括 codestackheapdata 等部分各个部分一般有较为固定的 layout但其对应的 physical memory address 是不固定的

virtual memory (VM) 需要达到若干个目标

  • transparency: process 感受不到 VM 的存在像是独占了整个巨大的 physical memory
  • efficiency: time 和 space 两方面的 overhead 都不能太大需要 hardware 的配合
  • protection / isolation: 每个 process 只能访问自己的 address space不能访问其他 process 或者 OS 自身的 memory

user-level program 使用的所有 address 都是 virtual address只有 OS以及 hardware能接触到 physical address

Interlude: Memory API

C program 可以使用 stack memory 或 heap memory

stack memory 的 allocation 和 deallocation 都是 implicit 的又称作 automatic memory

heap memory 需要使用 malloc() allocate使用 free() deallocate例如

  • double *d = malloc(sizeof(*d))
  • int *x = malloc(sizeof(*x) * 10)
  • char *s = malloc(strlen(buf) + 1)
  • free(x)

heap memory 的使用很容易出错例如

null pointer dereference
使用前没有 allocate
uninitialized read
没有初始化内容就读取以为内容会是 0
buffer overflow
allocate 的 memory 不够大例如字符串没有在长度的基础上加一
memory leak
long-running program 的 heap memory 使用完毕后没有 free
use after free
在 free 之后继续使用 dangling pointer
double free
free 之后再次 free

malloc()free() 不是 system call而是 library callmalloc library 使用 system call brk()/sbrk() 设置 program 的 breakheap 末尾的 address来获取 memory进而分配给用户

另外还有 calloc 可以用来初始化 malloc 得到的 memoryrealloc 可以用来调整一块已分配的 heap memory 的大小

可以用 mmap 进行 memory mapping例如可以 map 到 anonymous file 来获取一块 memory

Mechanism: Address Translation

为了高效且灵活地 virtualize memory基本思想是 (hardware-based) address translation将 memory access 从 virtual address 翻译为 physical addressOS 会管理 memory配置 hardware最终由 hardware 高效地进行 address translation

我们先做一些简化假设

  • 每个 process 的 address space 都映射到了 physical memory 中连续的2一段
  • 各个 process 的 address space size 相同
  • physical memory 足够大能装下所有 process 的 address space

Base and Bounds

在 1950s当时的计算机使用了被称作 base and bounds3 / dynamic relocation 的技术实现简单高效且能提供 protection 的 VM

CPU 中添加两个 registerbaseboundsbase 即 virtual address 0 对应的 physical address在 access memory 时进行 address translation用 base 加上 virtual address 计算 physical addressbounds 是 address space 的大小会检查 virtual address 不超过 bounds

Hardware Support

为了实现 base and bounds需要若干 hardware support

  • 支持 kernel mode 和 user mode
  • memory management unit (MMU) 中提供 base register 和 bounds register
  • 提供特殊的 privileged instruction 来修改 base 和 bounds只有 OS 能修改它们否则一个 user process 将可以 wreak havoc4
  • 在 memory access 超出 bounds 时 generate exception调用 exception handler

Operating System Issues

OS 需要做的工作有

  • 在 create process 时为其分配 memory
  • 在 terminate process 时回收 memory
  • 在 context switch 时存储设置 base 和 bounds此时可以进行 relocate将 base 修改为与上次 schedule 到这个 process 时不同的位置并将数据复制过去
  • 提供 out-of-bounds memory access 的 exception handler一般会 kill 掉这个 process

在我们简单的假设下可以使用一个 free list 维护空闲的 memory slots

Segmentation

在 Base and Bounds 中heap 和 stack 之间的空位一般不会用满但没有使用的空间也会占用 physical memory这会造成严重的浪费internal fragmentation并且Base and Bounds 不支持运行 address space 比 physical memory 大的 program所以我们需要更灵活高效的机制来支持 large address space

我们可以使用 segmentation将 memory space 划分成多个 segment例如 codestack 和 heap每个 segment 是连续的但整体不必连续从而可以更加灵活地进行分配减少 internal fragmentation

Hardware Support

为了支持 segmentation需要将整体的一对 base and bounds register 变成每个 segment 各一对

在进行 address translation 时需要先识别一个 address 属于哪个 segmentexplicit approach 通过 address 的最高几位作为 segment 标识而 implicit approach 通过地址的生成方式是否来自 PC / stack pointer判断 segment

stack 是 grow backwards 的需要特殊支持可以在 hardware 中添加表示 grow 方向的 flag bit对于 grow backwards 的 segment其 base 是这段 address 的上界offset 是负数越界判断也有所不同

为了支持 shared memory尤其是 code sharing需要添加 protection bits表示一个 segment 是否可以 read / write / execute进行 code sharing 时可以将权限设为 read-execute禁止修改从而既能 share 又能 isolate这也能避免 stack / heap 被执行一定程度上避免一些攻击

只分成 codestackheap 等少量几个 segment 被称作 coarse-grained segmentation有的系统支持成百上千个 segment称作 fine-grained segmentation这需要存储 segment table

OS Support

为了支持 segmentationOS 需要做的事情有

  • 在 context switch 时存储切换 segment registers
  • 管理 physical memory 的 free space从而支持
    • 创建新的 address space
    • segment grow例如 sbrk()

由于 segment 的 size 是不固定的physical memory 中各个 segment 之间可能会出现很多空洞这被称作 external fragmentation导致 free space management 非常困难

一种解决方式是进行 compact通过挪移 segment 来消除 external fragmentation但这需要频繁移动大量数据非常 expensive效率很低所以一般不会进行 compact而是会使用其他方式尽量减少 internal fragmentation

Free-Space Management

如果 memory 被分成了 fixed-size units以 unit 为分配的基本单位则 free-space management 会比较容易如果分配出的每一块 memory 大小各异则容易造成 external fragmentation需要一些机制来优化

参见 CS:APP 第九章 Dynamic Memory Allocation

Paging: Introduction

将 memory 分成 variable-sized pieces 会使 free-space management 比较困难所以在 virtual memory 中一般实际上会分成 fixed-size unitsaddress space 中的每个 unit 称作一个 page对应的 physical memory 称作 page frame这个做法称作 paging

paging 可以避免 external fragmentation并且更加 flexible可以支持 sparse address space也不需要对 program 如何使用 address space 进行假定例如不需要对 stack 的 grow 方向进行特殊处理

page table 用来记录 virtual page 和 physical frame 的对应关系用于 address translation每个 process 都各有自己的 page tablecontext switch 时需要切换 page table

在进行 address translation 时需要将 address 分成 virtual page number (VPN) 和 offset 两部分其中 offset 位于低位位数对应一个 page 的大小VPN 作为 page table 的索引来访问对应的 page table entry (PTE)从而得到 physical frame number (PFN, or PPN)再将 PFN 和 offset 拼接就可以得到最终的 physical address

page table 比较大不像 base and bounds 可以存在专门的 hardware 里而是要存在 physical memory 中

page table 可以使用各种数据结构存储最简单的是 linear page table就是一个一维数组以 VPN 作为下标但无论如何page table 的基本数据单位是 PTE

一个简化的 PTE 需要存储 PFNvalid bit 和 protection bits其中valid bit 表示有的 page 是 invalid 的没有分配 physical frame可以节约 memory另外实际的 PTE 还会有 present bitdirty bitreference bit 用于 swapping根据具体实现可能还会存一些别的信息

在现在这个简单的 page table 设计下每次 memory access 都需要访问两次 physical memory先访问 page table 再访问实际目标而且 address space 较大时 page table 也会很大也就是说它的 time 和 space overhead 都很大需要进一步优化

Paging: Faster Translations (TLBs)

为了解决 page table 的 time overhead需要 hardware 的帮助即使用 translation lookaside buffer (TLB)5 来加速 page table access

TLB 中存储了少量 PTE进行 address translation 时首先查找 TLB找到了称作 TLB hit否则称作 TLB miss需要再读取 page table返回结果并更新 TLBTLB miss 代价高昂需要尽可能避免

Locality: Why is TLB Hit Rate High?

TLB 利用了 program 的 spatial locality即一小段时间内访问的 address 一般是邻近的很多 address 位于同一个 page从而可以 TLB hit也利用了 temporal locality即一小段时间内同一个 address 可能被多次访问从而可以 TLB hit

locality 是 program 的性质不同 program 有着不一样的 locality这会影响其性能如果 program 短时间内访问的 page 数量超过了 TLB 的容量就可能产生大量 TLB miss这称作 exceeding the TLB coverage有的 program 由于其特殊性就是需要随机大范围访问 memory例如使用了复杂数据结构的 DBMS可以为它们设置更大的 page size来缓解这一问题

Who Handles The TLB Miss?

TLB miss 可以由 hardware 或 software 处理

在 hardware-managed TLB 中page table 有固定的格式OS 需要设置 page table base register由 hardware 进行 TLB miss 的处理page table 的访问

在 software-managed TLB 中TLB miss 会触发 trap由 OS 提供的 trap handler 进行处理使用特殊的 privileged instruction 修改 TLB这样 OS 可以灵活设计 page table不受 hardware 的限制这个 trap handler 有两点需要注意

  • 返回到 user program 时要返回到触发 trap 的那条 instruction而非像 system call 一样返回到下一条 instruction
  • trap handler 自身不能再触发 TLB miss要么 trap handler 直接访问 physical memory 绕开 TLB要么在 TLB 中设置一些 wired translation永久保留在 TLB 中不被清除

TLB Contents: Whats In There?

TLB entry 的内容一般包括

  • PTE 的信息PFNprotection bitsdirty bit 等
  • VPNTLB 一般是 fully associative需要存储 VPN 作为 cache tag
  • valid bit表示这个 TLB entry 存储的信息是否 valid和 page table 的 valid bit 不同
  • wired表示这个 entry 永远 valid不被清除/替换
  • ASID

TLB Issue: Context Switches

由于每个 process 的 page table 不同context switch 时需要处理 TLB 的更新

一种方法是在 context switch 时完全清空 TLB将 valid bit 全部置 0但这样的话每次 context switch 后都会 TLB miss性能较差

另一种方法是在 TLB 中存储 address space identifier (ASID)它与 PID 类似用来表示这个 TLB entry 对应于哪个 address space查找 TLB 时需要同时比较 VPN 和 ASID这样既保证了不同 process 访问到不同的 page table又不至于在 context switch 时完全损失掉 TLB

Issue: Replacement Policy

如果 TLB 满了添加新的 entry 时需要替换掉一个旧的需要根据 replacement policy 进行选择

Paging: Smaller Tables

接下来还需要优化 page table 的 space overhead即减小 page table 自身占用的 memory在优化前一个 32-bit address space 在 page size 为 4KBPTE 占用 4B 时需要占用 4MB 的空间

Simple Solution: Bigger Pages

增大 page size 可以让 PTE 数量变少从而减小 page table 占用的空间但更大的 page size 可能导致严重的 internal fragmentation所以不能盲目扩大

有的 OS 确实支持更大的 page size但其目的是降低 TLB 的占用提升 TLB hit rate而非减小 page table size

Hybrid Approach: Paging and Segments

可以尝试将 paging 和 segmentation 的优点结合起来整体进行 segmentation在 segment 内部使用 paging每个 segment 各有一个 page tablebase 和 bounds 指向 page table这样的话address space 中不属于任何一个 segment 的部分无需占用 page table 的空间

然而这种做法依然有很多问题

  • 需要 segmentation损失了一些 flexibility
  • 一个 segment 的内部如果太 sparse其 page table 依然会很大
  • 虽然分配给 program 的 memory 是以 page 为单位的但现在 page table 变成了 variable-sized为 page table 分配空间又变得困难会产生 external fragmentation

Multi-level Page Tables

很多 modern system 使用的都是 multi-level page table将 page table 分成多级形成树状结构上一级 PTE 在 valid 时指向下一级 page table访问上一级使用的 index 是对应的下一级的 index 的公共前缀

这样做既省下了大量 invalid PTE 占用的空间又避免了上述 hybrid approach 的缺点一个 page table 的 size 可以控制在一个 page这也使得为 page table 自身分配 memory 更加容易

但它也有一些缺点在 TLB miss 时需要访问多个 level 的 page table即多次 memory access开销更大实现起来更复杂

Inverted Page Tables

普通的 page table 是对每个 VPN 有一个 entry 存 PFN而 inverted page table 则是对每个 PFN 有一个 entry 存 VPN并且所有 process 共用一张 inverted page table每个 entry 还会记录对应的 process为了快速查询需要用一些数据结构维护这张 table例如 hash table

Swapping the Page Tables to Disk

实际上page table 不一定放在 physical memory 中也可能它自身就使用 virtual memory这使得 page table 自身可以被 swap 到 disk 上避免 physical memory 放不下 page table

Beyond Physical Memory: Mechanisms

physical memory 可能装不下整个 virtual memory所有 process 的 address space这时可以将一部分 page 存在 disk 上支持更大的 virtual memory一方面可以让 programmer 无需考虑 memory 不够用要怎么办另一方面可以在 physical memory 有限的情况下支持更多 process 同时运行

Swap Space

为了将 page 存储在 disk 上需要在 disk 上预留出一块 swap spaceOS 可以通过 disk address 读写 swap space

只不过swap space 并不是 swapping 在 disk 上唯一的数据来源例如program 存储在 disk 上所以可以从 disk 上 load无需再保存到 swap space

Page Fault

为了支持 swapping需要在 PTE 中增加 present bit表示这个 page 是否在 physical memory 中如果访问了不在 physical memory 中的 page则会触发 page fault6

无论使用 software-managed TLB 还是 hardware-managed TLBpage fault 都是由 OS 提供的 page fault handler 处理的这是因为 page fault 不适合由 hardware 处理一方面disk 速度慢访问耗时长另一方面这涉及到 swap space 的使用以及 disk I/O 的处理流程复杂

在进行 disk I/O 的过程中process 会处于 blocked state此时 OS 可以运行其他 process

When memory is full

page in 的时候如果 physical memory 满了则需要先 page out 一些 pageOS 通过 page-replacement policy 选择这些 page

只不过一般并不会等到 physical memory 完全耗尽才进行 page out而是会在剩余的 physical memory 不多时就在 background 运行 swap daemonevict 掉一些 page来保持 physical memory 有一定量的空余这样一方面可以批量处理效率更高尤其是 disk I/O另一方面在 background 运行可以更好地利用 idle time

Beyond Physical Memory: Policies

由于 disk 访问速度非常慢page hit rate 略微提高一点average memory access time 就可以下降很多所以使用一个好的 replacement policy 非常重要

当然为了获得更好的性能也可以选择增大 physical memory

Replacement Policies

为了衡量 replacement policy 的优劣由于 hit rate 受到具体 sample 的影响光看 hit rate 会缺少一些 context可以和 optimal policy (OPT) 进行比较假设可以预知未来可以证明最优的 policy 是 furthest in the future即每次 evict 掉最远会被再次访问的 page当然实际上是无法预知未来的所以需要使用其他尽量优的 policy

FIFO 和 random 是两种简单的 policy他们实现简单但比较笨容易 evict 掉频繁访问的 important page

scheduling policy 一样可以基于历史预测未来来逼近最优replacement policy 主要关注 page 的 frequencyrecency其原理是 program 的 localityleast-frequently-used (LFU)least-recently-used (LRU)以及相反的 MFUMRU 等 policy其中 LRU 是最常用效果较好的实现相对简单的

Workload Examples

完全随机访问没有 localityFIFOrandomLRU 表现相同hit rate 和 cache size 成正比

Figure 22.6: The No-Locality Workload

80% 的访问集中在 20% 的 hot pageLRU 的性能介于 FIFO/random 和 OPT 之间

Figure 22.7: The 80-20 Workload

循环访问若干个 page在 cache size 足够大时各种 policy 都是 100% hit在 cache size 较小时LRU 和 FIFO 会退化至 100% missrandom 仍有合理的性能

Figure 22.8: The Looping Workload

也就是说LRU 虽然一般性能较好但在 corner case 下性能会很差现在的 OS 一般会采取一些额外的措施来做到 scan resistant避免 worst-case behavior

Implementing LRU

LRU 的实现需要记录每一次 memory access精确实现比较 expensive所以一般只是取近似

在 page table 中会为每个 page 存一个 reference bit访问一个 page 时 hardware 会将 reference bit 置为 1

OS 可以用各种方式使用 reference bit 来逼近 LRU例如 clock algorithm循环扫描所有 page如果 reference bit 为 1 则置为 0 然后继续扫描直到 reference bit 为 0选择这个 page也不一定要循环扫描可以随机选择

Figure 22.9: The 80-20 Workload With Clock

Considering Dirty Pages

page replacement 还需要考虑一个 page 是否 dirty即是否被修改过dirty page 被 evict 时需要将数据写回到 disk 上clean page 则不需要所以 evict dirty page 更加 expensivereplacement policy 一般会考虑优先选择 clean page例如在 clock algorithm 中可以先扫描一轮 clean page没找到再扫描 dirty page

Other VM Policies

除了 replacement policyOS 还需要考虑何时将一个 page 放进 physical memory普通的做法是 demand paging即等到真的使用的时候才 page in有时也可以进行 prefetch例如在使用一个 page 的同时 load 相邻的下一个 page或者在 program 提供 hint 时进行 prefetch

另一个 policy 是何时将 page 写回到 disk 上可以进行 clustering (grouping)进行少次多量的 disk write性能更好

Thrashing

如果 running processes 的 working set正在使用的 page太大physical memory 装不下就会出现 thrashing会一直进行 paging极大影响系统性能

早期的系统 physical memory 较小出现这种情况比较正常可以使用 admission control暂停一部分 process 的运行以减小 working set

现在的系统则一般会使用 out-of-memory killer在 memory 占用过高时 kill 掉一些 process

Complete Virtual Memory Systems

VAX/VMS Virtual Memory

VAX/VMS 是 1970/80 年代的系统有很多 idea 延续至今

address space 被分成 process spacesystem space 两部分process space 又被分成 P0 用来放 code 和 heap以及 P1 用来放 stack而 system space (S) 用来放 OS code 和 data在 protection bits 中设置了更高的 privilege level

page size 只有 512B因此优化 page table 占用的空间非常重要它使用的是 hybrid of paging and segmentation并且 page table 放在 kernel virtual memory 中可以 swap 到 disk 上

code segment 的 address 并非从 0 开始从而可以检测到 null-pointer access

kernel address space 是 user address space 的一部分在 context switch 时只更改 P0 和 P1 的 base and bounds不更改 S为 kernel 使用 virtual address 便于 swap page table to disk也便于在 kernel 和 user program 之间 copy data

VAX 的 hardware 不维护 reference bitVMS 实现的也不是 LRU而是 segmented FIFO

  • 每个 process 有自己的 FIFO list另有 global 的 clean page list 和 dirty page list
  • 对每个 process 限制了 resident set size (RSS)以防止单个 process 占用过多 memory
  • 一个 process 使用的 page 数量超过 RSS 之后会将 process FIFO list 里的 page 移到 global list保留在 physical memory 中不 evict
  • 需要进行 page replacement 时从 global clean page list 取
  • 如果 access 了一个在 global list 的 page则将其移回 process FIFO list
  • 定期将 dirty page list 批量写回到 disk然后移动到 clean page list

有两个 lazy optimization

demand zeroing
request 一个 page 时为了 security 需要将其内容清空但不需要立即清空而是可以等到真正被使用了再清空如果最后没被使用就不用清空了
copy-on-write
复制 page 时先将两边都设为 read-only 并指向相同的 physical memory写入时会触发 trap然后再真的进行 copy 并设为 writable这对 fork() 尤其有用

The Linux Virtual Memory System

Linux address space 分为 user portion 和 kernel portion

kernel virtual address 分为两种

  • kernel logical address使用 kmalloc 获取不能 swap to disk和 physical address 是相差固定 offset 的简单对应关系所以对应的 physical address 是连续的适用于 direct memory access 等场景
  • kernel virtual address使用 vmalloc 获取更容易分配大块的 memory对应的 physical address 不一定是连续的

Linux 支持 huge page以前需要 program 主动请求使用 huge page后来又有了 transparent huge page可以自动使用更大的 page size以在 working set 很大时减少 TLB miss只不过更大的 page size 也可能造成更严重的 internal fragmentation

Linux 中有两种 memory mappingmemory-mapped file 和 anonymous memory前者可以 map file to memory常用于 load program 以及 shared library从而一个 page 等到真正使用才会从 disk 读取称作 depand paging后者用于 heap 和 stack

Linux 使用 2Q replacement policy以解决 LRU 的 worst-case behavior

  • 有两个 queueinactive listactive list分别近似 LRU
  • 首次访问 page 会进入 inactive list再次访问则进入 active list
  • 定期将一些 page 从 active list 移入 inactive list
  • evict 时优先选择 inactive list

这样的话inactive page 就不会将 active page 挤出 physical memory

为了缓解 buffer overflow attackpermission bits 中需要添加 NX bit (no-execute)并且使用 address space layout randomization (ASLR)

为了缓解 Meltdown/Spectre attack可以创建单独的 kernel address space称作 kernel page-table isolation (KPTI)在切换到 kernel mode 时需要切换 page table这对性能有一定的影响

Footnotes

  1. 作者推荐阅读You can't have your cake and eat it - Wikipedia
    The best part of this page is reading all the similar idioms from other languages.

  2. 注意是 contiguous 而不是 continuousdiscrete topology 下随便 map 都 continuous

  3. bound noun (formal) 蹦跳跳跃
    bounds noun [pl.] 限制范围极限

  4. Is there anything other than havoc that can be wreaked?
    我想作者可能需要一本牛津词典或者 http://www.just-the-word.com/

  5. lookaside buffer 是 cache 的历史名称后来 lookaside buffercache 取代TLB 保留了下来现在看来一个更合理的名称或许应当是 address-translation cache

  6. page fault 虽然叫做 fault但它其实是 legal access称它为 page miss 或许会更好只不过hardware 需要将这作为一种异常情况交给 OS 处理和其他 illegal action 类似所以称它是 fault另外有时人们也会将 illegal memory access 一并统称为 page fault可能会将 page fault 分成几类其中一类是 page miss需要根据上下文进行判断