OSTEP: Virtualization 学习笔记

「Operating Systems: Three Easy Pieces」第一部分 Virtualization 学习笔记.

同时也参考了 ouuan 大佬的笔记.

还没学完 qwq

---

The Abstraction: The Process

process 指的就是 running program.

一个 process 的 machine state 包括: memory (它的 address space 内的内容)、registers (包括 program counter、stack pointer 等)、I/O information (能被读/写的 open files).

创建一个 process 时, OS 需要 load program code & static data into memory, 初始化 run-time stack (stack) 填入 argv 和 argc; 初始化 heap; 初始化 I/O 相关信息, 例如 stdin、stdout、stderr 三个 file descriptor.

process 有 3 种 state: running、ready、blocked.

stateDiagram-v2

s0: Running

s1: Ready

s2: Blocked

s0 --> s1: Descheduled

s0 --> s2: I/O initiate

s1 --> s0: Scheduled

s2 --> s1: I/O done

OS 的 scheduler 需要通过调度来优化性能.

OS 还会维护 process list 来记录所有 ready processes 已经一些附加信息以便跟踪 running processes. 另外 OS 也会通过某些方式跟踪 blocked processes.

Interlude: Process API

• pid_t fork(void): 复制当前状态创建子进程, 新的进程拥有和原进程相同的代码、数据、文件, 但 PID 不同, 并且后续对数据的修改是独立的.
  • 调用一次 fork() 会返回两次, 一次在父进程返回子进程的 PID, 一次在子进程返回 0, error 则返回 -1
  • 一般通过判断 fork() 的返回值来判断当前进程是父进程还是子进程
  • 由于 OS scheduler 的存在, fork() 会导致一些 undeterministic 的行为产生
• pid_t waitpid(pid_t pid, int *statusp, int options): 等待子进程结束
  • pid_t wait(int *statusp): waitpid(-1, statusp, 0)
• int execve(const char *filename, char *const argv[], char *const envp[])
  • 希望子进程干一些与父进程不同任务时很有用
  • 工作原理是加载你想要执行的 executable 的代码并直接 overwrite 到当前的 code segment 中; 当前程序的 memory space (包括 heap、stack 等) 会 re-initialize; 成功调用 exec() 则永远不会返回原程序之后的指令
• kill(): 给进程发送 signals
  • Ctrl + C: SIGINT, 一般会直接停止 (terminate) 该进程
  • Ctrl + Z: SIGTSTP 中途暂停该进程, 可以通过 fg 等 command 复原
• signal(): 进程通过 signal() 来捕捉不同的 signals

一般将 fork() 和 exec() 配合使用, 可以通过在它们之间插入其他代码来修改子进程的执行环境. shell 程序就是通过 fork() 创建子程序然后 wait() 直到子程序通过 call exec() 执行完键入的 command, 接着回到父进程再次弹出 prompt 等待用户输入新的 command. 另一个例子是 redirect output, 即在 fork() 与 exec() 之间插入 open() 和 close().

UNIX 还通过用一个 pipe (pipe() system call) 将一个进程的 output 连接到另一个进程的 input 来达到重定向的目的.

Mechanism: Limited Direct Execution

CPU 通过 time sharing 来达到 virtualization, 达到 high performance 的同时维持 control 是主要挑战.

“direct execution” 就是直接在 CPU 上运行程序, 但是这样无法限制程序的不可控行为, 所以 OS 需要采用 limited direct execution 来对程序加以限制.

Problem #1: Restricted Operations

为了限制 user program, CPU 将 processor mode 分为 user mode 和 kernel mode 两种. 其中 kernel mode 由 OS (或 kernel) 来运行, 可以执行更高权限的 operations, 例如 I/O 读写请求和访问 memory.

user program 通过 system call 交给 OS 来执行权限更高的 operation. system call 是一种特殊的 trap (exception), 它通过 trap instruction 进入 kernel 内对应的 trap handler, 这个过程由 hardware 将 program 的 register 信息存储进这个 program 的 kernel stack 中并根据 trap table 来决定应该跳转到 kernel 的位置, 然后转变为 kernel mode 执行相应操作后, 通过 return-from-trap 回到 user program, 同样也由 hardware 来恢复 registers 的状态.

trap table 由 OS 在系统启动时设置给 hardware, 即各种 trap 对应的 handler address, 为了防止 user program 能随意进入 kernel 的任意位置, trap table 只能由 OS 进行设置. 进行 system call 需要指定 system-call number, 由 user code 负责将其放在特定 register/stack 中.

limited direct execution (LDE) protocol 可以分为两个阶段:

1. kernel 在系统启动时初始化 trap table, CPU 记住它的位置
2. kernel 在执行 return-from-trap instruction 前分配好 process list 和 memory 等信息, 然后将 CPU 切换到 user mode 开始 run process. 当 process 发出 system call 时 trap 进入 OS, 由 OS 执行完相应操作后通过 return-from-trap 返回 process. process 完成所有工作后, 通过返回一些 stub code 来退出 (例如会 trap 进 OS 的 exit() )

Problem #2: Switching Between Processes

当一个 process 占用着 CPU 时, OS 不在运行状态, 自然无法实现 control, 因此需要 user program 将 control 交给 OS. OS 重新获取 control 有两种方式:

1. cooperative approach: 等待 system calls.
2. non-cooperative approach: 用一个 timer 定时进行 timer interrupt 强制收回 control.
   • 这里也需要 interrupt handler, 与 system-call handler 同属于 trap handler, 会在系统启动时由 OS 设置
   • 同样也会将 register 存储到当前 program 的 kernel stack 中
   • OS 的 scheduler 会决定切换哪一个 process, 若确定切换则会进行 context switch: 从 process A 的 registers 和 kernel stack 切换到 process B 的 registers 和 kernel stack, 之后 return-from-trap 就会回到 process B 中断的地方

Scheduling: Introduction

OS scheduler 使用一系列的 scheduling policies 来决定 schedule 哪个 job.

Workload Assumptions

先对 workload 即要运行的 processes (也即 jobs) 作一些 assumptions 以简化问题, 后面再逐步抛弃这些 assumptions 得到一个 fully-operational scheduling discipline.

1. 每个 job 运行时间相同
2. 所有 jobs 同时到来
3. 每个 job 一旦开始就会一直运行到结束, 终途不被打断
4. 所有 jobs 只使用到 CPU
5. 每个 job 的 run-time 是已知的

Turnaround Time

我们使用 scheduling metric 来比较不同的 scheduling policies. turnaround time 定义为 $T_{\text{turnaround}}=T_{\text{completion}}-T_{\text{arrival}}$, 用来衡量总体性能.

First In, First Out (FIFO) / First Come, First Served (FCFS) 是最简单的一种 scheduling policy. 在 5 个 assumption 下, FIFO 表现很好.

当丢弃第 1 个 assumption 时, FIFO 就会发生 convoy effect, 即 large job 排在前面堵住后面的 small job 从而使 turnaround time 变得很大. 此时采用 Shortest Job First (SJF) 可以达到最优.

进一步丢弃第 2 个 assumption, 若 large job 先来, small job 后来, 那么 SJF 就会失效. 此时我们丢弃第 3 个 assumption, 允许 scheduler preempt 一个 job 然后运行另一个 job (不进行 preempt 的 scheduler 被称为 non-preemptive scheduler) 便可以使用 Shortest Time-to-Completion First (STCF) / Preemptive Shortest Job First (PSJF) 来达到最优: 若新到来的 job 的总用时比当前运行 job 需要的剩余运行时间还短, 则切换运行新 job.

Response Time

response time 定义为 $T_{\text{response}}=T_{\text{firstrun}}-T_{\text{arrival}}$, 用来衡量 fairness, 让用户在交互式环境下有一个更好的体验.

上述的几种 policy 在这个 metric 下表现都很差, 被排到后面的 job 会需要等待很久.

Round-Robin (RR) 让每个 job 运行一个 time slice (也称为 scheduling quantum) 然后切换到下一个 job, 因此 RR 也被称为 time-slicing. time slice 越小, response time 也就越小, 且 time slice 必须是 timer-interrupt period 的整数倍. 当 time slice 过小时, context switching (包括存储/恢复 registers, cache miss penalty 等) 就占用过多时间, 继而显著影响整体性能, 所以需要一个合适大小的 time slice 来 amortize 掉 switching cost. 另外, RR 虽然 response time 很小, 但是 turnaround time 很大, 甚至比 FIFO 还大.

Incorporating I/O

丢弃第 4 个 assumption, 运行 job 进行 I/O, 就需要处理 blocked 的情况: 当前运行的 job 在 I/O 时不会使用 CPU, 而是会被 blocked 等待 I/O 完成, scheduler 需要在此时 schedule 另一个 job, 另外还需要决定 I/O 完成时 schedule 哪一个 job.

可以将一个 job 看作用 I/O 分割成的一些 sub-jobs, 然后继续用之前的 policy. 例如, 使用 STCF 时, 会优先运行需要 I/O 密集的 job 使得有大量 I/O 期间能运行其它 job, 这可以达成 overlap, 让 CPU 和 I/O 同时工作, 更充分利用系统资源.

Scheduling: The Multi-Level Feedback Queue

前面的 scheduling policy 往往不能兼顾 turnaround time 和 response time 两者的优化, 并且 SJF/STCF 依赖于对 job 不切实际的预知.

Multi-level Feedback Queue (MLFQ) 是目前被广泛使用的一种 scheduling policy, 它同时解决了上述两个问题.

Basic Rules

MLFQ 的思想是通过观测 job 的行为将其动态地分为两类: short-running interactive jobs (被 I/O 切分为小块) 和 long-running CPU intensive jobs. short-running interactive jobs 需要更高的优先级, 这既符合 SJF/STCF 的思想, 也满足这类 job 需要更小的 response time 的要求.

MLFQ 动态地将 jobs 放进不同 priority 的 job queues 中, 每次选择优先级高的 queue, queue 内部使用 RR.

Change Priority

MLFQ 首先默认新到来的 job 是 interactive job, 将其放在 priority 最高的 queue, 若运行太久就放到下一级 queue. 具体而言, 在每一级 queue 给 job 一个 time allotment, job 在这个 queue 中运行时间超过 allotment 就会降级, 如果在 allotment 用完之前 job 放弃使用 CPU 就留在当前 queue 并重置 allotment.

这种方式存在三个问题:

• 如果 short-running jobs 太多占满了 CPU, 那么在 low priority queues 中的 long-running jobs 就会一点 CPU 都拿不到 (称为 starvation)
• jobs 可能会在之后 change behavior 成为 interactive, 而降级之后无法升级
• jobs 可以每次在 allotment 快用完的时候放弃 CPU 从而一直留在当前 queue 来获取更高的 CPU 使用率 (称为 game the scheduler)

The Priority Boost

前两个问题的解决方案是每隔一个 time period $S$ 就进行 priority boost, 将所有 jobs 都放回 priority 最高的 queue 中.

系统中类似 $S$ 这样看上去需要用一些黑魔法才能正确设置的值被 John Ousterhout 称为 voo-doo constants: $S$ 设置的太高会出现 starvation, 太低则影响 response time.

Better Accounting

第三个问题可以通过 better accounting 来解决: 相比于在 I/O 之后就抛弃此次使用的 allotment, 而改成累计 allotment, 即不进行重置而是在下一次除了这个 job 时继续使用之前的 allotment, 当 allotment 累积用完时则降级.

Tuning MLFQ

MLFQ 有很多可以设置的参数: queue 的数量、每个 queue 中 RR 的 time slice 和 allotment、boost 的 time period $S$. 一般来说, priority 越高, time slice 和 allotment 越小.

MLFQ 也可以不实现多个 queue, 而是统计每个 job 的 CPU usage, 根据 usage 计算 priority, 让 usage 随时间 decay 来代替 priority boost, 这种方法称为 decay-usage scheduling.

priority 不一定完全依赖 feedback, 也可以由 user 给出 advice, 例如使用 nice 命令设置 niceness 来调整 priority.

Scheduling: Proportional Share

本章讨论 proportional-share (或 fair-share) scheduler, 它的主要目标是确保每个 job 能得到确定比例的 CPU time.

Lottery Scheduling

lottery scheduling 给每个 job 分配一些 tickets, 经过一个 time slice 就随机选择一个 winning ticket, 然后 schedule 到相应的 job, 最后 CPU time 会按照分配的 tickets 数量的比例分给 jobs.

lottery scheduling 还提供了一系列 ticket mechanisms 来分配 tickets:

• ticket concurrency: user 自行分配 tickets 给他的 jobs, 最后 scheduler 将其转化一个 global value
• ticket transfer: process 可以将它的 tickets 转交给另一个 process
• ticket inflation: 在一组互相信任的 processes 中, process 可以不通知其他 processes 按需多na拿一些 tickets

Stride Scheduling

stride scheduling 使用确定性算法进行 schedule.

它给每个 job 定一个 stride, stride 与 ticket value 成反比 (bushi), 例如定为 jobs 的 ticket value 的最小公倍数除以该 job 的 ticket value 的值. 然后为每个 job 维护一个 pass, 每次 schedule 到 pass 值最小的 job, 单次运行完这个 job 后给它的 pass 加上 stride. 这样最终 job 获得的 CPU time 的比例等于 ticket value 的比例.

The Linux Completely Fair Scheduler (CFS)

CFS 可以高效且 scalable 地实现 fair share scheduling, 是目前 Linux 使用的 scheduler.

CFS 维护每个 job 的 virtual runtime (vruntime), 每次 schedule 到 vruntime 最小的 job, 运行完就加上这次的 runtime. 单次运行的 time slice 由 sched_latency 除以 job 数量动态决定, 为了防止 time slice 过小导致 context switching 过多影响性能, time slice 设有一个最小值 min_granularity. scheduler 会使用一个 timer 来决定下一个 schedule 的对象, 若 time slice 不是 timer interrupt 的整数倍也没有关系, 因为 vruntime 会精确记录 job 实际的 runtime.

CFS 还拥有以下 features:

• weighting (niceness): user 可以用 nice command 来调整 job 权重, 默认为 0, 取值范围在 $[-20, +19]$, niceness 越低, weight 越高, 且呈指数式变化, 最后 time slice 由 sched_latency 按照 weight 占比分配
• red-black trees: 利用 red-black trees 维护 vruntime, 保证每次查询与修改操作复杂度. 为了避免 job 被 block 后 wake up 时 vruntime 明显小于其他 jobs 从而独占 CPU 造成 starvation, 重新插入 job 时会将 vruntime 设为此时树上的最小值, 但是这个操作会导致 I/O 频繁或长期 sleep 的 job 无法得到 fair share.
• other: CFS 还有很多其他的 features, 例如优化 cache performance 的特殊手段、高效处理多个 CPU 的情况、可以将多个 process 视为一个 group 进行 schedule 而不是对单个 process

Multiprocessor Scheduling (Advanced)

As this topic is relatively advanced, it may be best to cover it after you have studied the topic of concurrency in some detail (i.e., the second major “easy piece” of the book).

后面 memory virtualization 的中很多概念在上学期的计组中多少接触了一些, 所以先跳过看第二部分 Concurrency 之后有时间再补, 不然真完全没法赶上课程进度了(悲)