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 = (double *) malloc(sizeof(double))
  • int *x = malloc(10 * sizeof(int))
  • char *s = (char *) 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 都一样大比 physical memory 小

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

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/