OS虚拟化

Posted on

进程抽象

  • 如果程序只完成“计算”的任务而不做任何输入输出，它就可以看成是一个状态机。程序的内存M和寄存器R构成了程序任意时刻的状态(M,R).
  • 进程的机器状态：内存（地址空间）、寄存器（PC、IP、栈指针、帧指针等）、IO信息等。
  • 每个线程有它自己的资源
    • const char *name - 它的名字
    • _Context context - 保存的寄存器现场
    • char stack[4096] - 堆栈
  • 进程 = 线程 + 地址空间

分时复用处理器

  • 只要我们能在某一个时刻，把M和R从处理器上拆下来，换上(M’,R’).

  • 把处理器“拆下来”的机制就是中断/系统调用。

  • 操作系统实际从一开始就驻留在内存中，并且配置了中断处理程序的入口地址，一旦进程发生中断/异常/系统调用，操作系统代码就立即接手执行。
  • 每个进程有自己的R, 因此需要寄存器现场的保存.

操作系统：实现虚拟化

  • 现代计算机系统实现虚拟化里最重要的两个想法就是：
    1. 使用虚拟地址空间VM让多个程序共享一个物理内存；
    2. 把(M,R)中寄存器现场R当做数据保存，并在寄存器现场R之间切换。

管理应用程序有序执行

  • 应用程序(进程)在计算时，没有任何权限访问不属于自己的内存
  • 应用程序想从外界输入/输出任何信息、请求操作系统完成任何功能，都需要通过系统调用

进程管理API

  • fork():创建一个与当前进程几乎完全相同的进程(同样的地址空间、同样的内存数据)，为了区别新旧进程，父进程(执行fork的进程)返回被创建进程(子进程)的进程号(pid)，而子进程返回0。
  • execve(const char *path, char *argv[], char *envp[]): 在不改变当前进程拥有资源的前提下，“替换”当前进程为path，并且调用main(argc, argv, envp)执行。除了地址空间被完全重建，很多进程拥有的操作系统相关状态都不发生改变：
    1. 进程号(pid)不变；
    2. 文件描述符照用；
    3. 进程当前目录不变；
    4. 访问权限不变；
    5. 附属终端不变；
    6. 信号掩码不变；
    7. ……
  • _exit()结束进程的一生。注意exit()和_exit()是不同的，前者是libc提供的函数，而后者是操作系统提供的系统调用。在libc库中会执行一些额外的操作，例如执行atexit()注册的call backs，以及清空printf的缓冲区。
  • 新建(create)；
  • 销毁(destroy)：主动退出或者被杀死；
  • 等待(wait)：等待进程直到运行结束；
  • 混合操作(miscellaneous control)：睡眠、恢复等；
  • 状态(status)：获得进程状态。

进程状态

  • 简单来说，进程可能处于以下三个状态之一：
    • Running：进程在处理器上执行指令；
    • Ready：进程准备执行，但由于某些原因OS决定现在不让它运行；
    • Blocked：进程此前执行了某些操作，让它在其他事件发生前停止执行。
  • 决定当前执行什么程序是系统调度的任务

直接执行限制

  • 内核态和用户态
  • 自陷, 系统调用
  • 进程切换:
    • 等待系统调用;
    • 利用时钟中断OS接管
  • 保存和恢复上下文

终端和Shell

文件描述符

  • File descriptor: 一个操作系统中打开的文件 (一个指向操作系统内对象的“指针”)
    • stdin: 0, stdout: 1, stderr: 2
    • open()会返回没有被占用的第一个文件描述符
    • int dup(int oldfd); - 复制oldfd
    • int dup2(int oldfd, int newfd); - 关闭newfd，并复制oldfd到newfd

管道：进程间通信

  • lhs-cmd | rhs-cmd: 运行lhs-cmd，把stdout连接到rhs-cmd的stdin

    • int pipe(int pipefd[2]); 在操作系统中创建一个管道
    • pipefd[0] - 读口；pipefd[1] - 写口

  • 默认情况下，管道是有限大小、blocking的

    • 管道满，write将等管道空出数据
    • 管道空，read将等数据
  • fork() 不复制管道
  • Shell的主要功能是将执行命令的脚本翻译成系统调用的序列
    • cmd > file < file - 使用fork-open-dup-execve
    • cmd1; cmd2, cmd1 && cmd2, cmd1 || cmd2 - 按顺序执行
    • cmd1 | cmd2 - 使用pipe-fork-dup-execve
    • 预处理：$() - 创建一个shell，将输出重定向到管道中读出

信号机制

  • 在应用层实现的中断

    1
    2
    typedef void (*sighandler_t)(int);
    sighandler_t signal(int signum, sighandler_t handler);

  • 在程序执行到一半时“跳转”到某个函数执行

  • 接收到Ctrl-C的终端驱动程序会给终端对应的进程组发送 SIGINT

    (所有进程都会收到)

    • Shell也可以选择使用raw mode，读取Ctrl-C，然后使用kill()发送SIGINT
    • 此时shell还需要把其他输入转发给jobs (tmux的实现)

  • Shell关闭时

    • 给所有jobs发送SIGHUP (hang up)，默认行为是结束进程
    • nohup就是忽略这个信号

输出到终端和重定向到文件的区别

  • 输出到终端, 输出条件为:

    • 满1024字节/换行/程序结束/手动fflush/stdin的scanf

  • 输出重定向到文件, 输出条件为:

    • 程序结束

进程调度

  • 周转时间 turnaround time:

  • First In, First Out(FIFO)

    • 在任务所需时间不同的时候效果很差
    • 护卫效应(convoy effect)

  • Shortest Job First (SJF)

    • 在长的任务先来的时候还是有很差

  • Shortest Time-to-Completion First (STCF)

    • 每当新任务到来, 判断谁先完成, 调度最先完成的那个

  • 响应时间response time:

  • Round Robin (Good For Response Time)

    • 时间片time slice
    • 每次花一段时间(time slice/scheduling quantum)执行一个任务，然后切换到队列的下一个任务。

  • Incorporating I/O

    • 任务执行I/O操作时会被阻塞，直到I/O操作完成。如果进行硬件读写，就可能会导致几毫秒的等待。因此，调度算法必须在I/O操作出现时合理的切换到别的任务。
    • 当I/O操作完成时，会产生硬件中断，此时OS接管并将发起请求的进程调回ready状态。

  • Multi-level Feed-back Queue (MLFQ):

    • 2条规则:

      • 规则1: 如果A比B优先级高,就跑A

      • 规则2: 如果AB优先级相同, 用RR

    • 优先级改变:

      • 规则3: 一个任务刚进入系统, 则最高优先级

      • 规则4a: 一个任务用完了一整个时间片, 则降低优先级

      • 规则4b: 一个任务在时间片用完之前放弃了CPU, 则优先级不变
    • 避免starvation:
      • 问题1：如果系统中有太多交互型的程序，他们的优先级高，会保持对CPU的占用，那么低优先级的程序就永远无法得到CPU时间(starve)
      • 问题2: 进程的行为可能随时间改变，一个计算型程序可能会变为交互型程序。此时这个程序无法重新获得优先级，响应时间高。
      • 规则5: 经过一段时间S, 系统中所有任务优先级提到最高
    • 避免用户恶意利用调度规则
      • 问题: 恶心人的用户会破坏调度算法的合理性(game the scheduler)，在时间截止前进程发起一个（不关心结果的）I/O请求来放弃CPU，就可以保持在同一个优先级队列中，获得更多的CPU时间。
      • 改写规则4: 一旦一个任务用完了某个等级分配的所有时间, 优先级就降低.

Proportional Share

  • 每个进程都有一定的tickets(彩票), 彩票越多中奖率越高, 用随机数来选择调度哪一个(中奖)

  • ticket currency:

    • 每个user给自己的进程发tickets, 按比例兑换成global ticket

  • ticket transfer:

    • 一个进程暂时把自己的tickets给另一个进程
    • 尤其出现于 client/server
  • ticket inflation:
    • 一个进程可以暂时增加或者减少自己的彩票数.
    • 仅适用于互相信任的进程之间
  • stride scheduling:
    • 确定的.
    • 不好, 因为有global state. 当一个新进程进入的时候，pass的初始值决定了它是否能够霸占CPU；而在彩票方法中，添加一个新进程并不会影响其他进程的执行。彩票方法更容易处理新的进程。

The Linux Completely Fair Scheduler (CFS)

  • 引入了virtual runtime(vruntime)

  • 进程运行的时候增加vruntime

  • 每次选择vruntime最低的
  • 切换进程的时间选择:
    • sched_latency(48 ms):
      • 决定多久后考虑是否要切换
      • 这个值 / 进程数 决定时间片的长度
      • 进程过多会导致时间片太小
    • min_granularity(6 ms):
      • 最小时间片长度
  • Weighting (Niceness)
    • UNIX世界允许用户调整进程的优先级(nice)
      • -20 (最高优先级)：非常不nice (是个坏人)
      • 19 (最低优先级)：非常nice (是个礼让的好人)
    • 时间片长度按照weight加权
    • vruntime 增加速度和weight相关, weight越大, 时间流逝越慢.
  • 红黑树来了, 飘过
  • I / O 处理和长时间睡眠进程: 进程醒了以后, vruntime最小为运行进程的最小vruntime减一个定值

多处理器

  • 进程是属于处理器的，只被某个处理器调度(最大化cache locality)
  • 只有在workload imbalance的时候，才进行cross-core migration
  • Scheduling threads on a multicore machine is hard

虚存抽象

地址翻译

  • 是一个函数 $f(x) \in [0,M)$
    • 把地址空间中的任何一个地址映射到另一个地址
    • 任何指令访问地址 x (包括取指令)，经过地址翻译后访问 f(x)
    • 访问未映射的页面 $f(x)=\bot$ 将会触发异常 (Segmentation Fault)

分段

  • 段 (segment)：仅允许几段连续的虚拟内存

    • x86: GDT, LDT描述“段”的内存映射

  • 就是虚拟内存分成一个个段, 比如堆区, 栈, 代码, 分别映射到物理内存中的一段区域

空闲内存管理

  • 主要介绍free list:
    • 内存区域里面, 每一块空闲内存头上存着size和next, 已分配区域存size和魔数magic
    • malloc就是在free list中找到一块适宜的, 标记为已经分配
    • free就是将一块内存重新连回free list之中
    • malloc的时候有分裂, free的时候有合并
  • buddy system:
    • 每一块内存都是2的幂次大小, 用线段树存

分页

  • 页 (page)：可以以页为单位自由映射
    • x86: “页目录-页表”数据结构描述内存映射
    • 内存越大，页表层数越多：PML4 (48bit)

  • 复习：

    • MMU
    • 多级页表
    • 反置页表IPT
      • 我们实际希望的是在系统中创造多个地址空间$as$，并且维护$f_{as}(x)$
      • 我们不如让硬件维护一个全局的hash table，计算$f(as, x)$
    • TLB (Translation Lookaside Buffer);
    • page table entry (PTE)
    • physical page number(PPN), virtual page number(VPN)
    • valid bit, protection bit, present bit, dirty bit, reference bit

mmap

  • 操作系统应该如何为进程提供虚拟内存管理？因为Everything is a File，所以只要能把操作系统里的对象“映射”到进程地址空间，就足够了！

    1
    2
    3
    void *mmap(void *addr, size_t length, int prot, int flags,
               int fd, off_t offset); // 映射
    int mprotect(void *addr, size_t length, int prot); // 修改映射权限
    • 将文件fd从offset开始的length长度映射到进程地址空间中虚拟地址addr开始的部分
    • 如果addr == NULL, os选一个地址
    • prot: 是否可读, 可写, 可执行
    • flags: 是否可共享, …
    • 成功则返回指向映射区域的一个指针, 失败则返回(void *) -1.

  • 不映射任何文件(fd=-1, MAP_ANONYMOUS)，等同于内存分配 (mmap可以直接分配几十GB的内存；用户空间的内存分配是基于mmap实现的)

  • 可以映射任何支持mmap的文件/设备

    • ELF文件中间的那么多“空白”: 为了填满一页

  • 可以以各种权限(PROT_READ, PROT_WRITE, PROT_EXEC)映射

  • 操作系统会管理好一切(偶尔你需要msync (2))

  • mmap并不需要真的映射

    • 操作系统只需要记下这一次mmap操作，并将页面标记为“不存在”
    • 缺页时操作系统就“知道”该给这个页面填入什么值
      • 找到映射的文件
      • 如果没有文件，直接返回一个全0的页面
      • 如果有文件，从文件处读取数值
      • msync或页面回收时写回文件
    • 我们允许进程使用的内存大于物理内存
    • 只要有一个大容量的设备，在物理内存紧缺时，swap out一些不常用的物理页(思考题：换出哪一页？)
    • 缺页时再从设备换回

fork: 写时复制

  • fork并不需要复制完整的M
  • 让父子进程只读共享所有页面；写时复制一份

指针

  • 它本质上就是个整数
  • 在指针背后，实际是进程的“地址空间”
1
2
uintptr_t value;
*(char *)value // ...
  • value = 0 -> Segmentation Fault
  • 代码：只读、可执行
  • 数据/堆栈：可读、可写、不可执行

静态链接程序的地址空间

  • pmap查看

  • 1
    2
    3
    4
    5
    6
    7
    8
    00400000-004b6000                 r-xp  /tmp/a.out (代码)
    006b6000-006bc000                 rw-p  /tmp/a.out (数据)
    006bc000-006bd000                 rw-p  [bss](通过end查证)
    0131f000-01342000                 rw-p  [heap]
    7fff993c9000-7fff993ea000         rw-p  [stack]
    7fff993f4000-7fff993f7000         r--p  [vvar] 
    7fff993f7000-7fff993f9000         r-xp  [vdso] 
    ffffffffff600000-ffffffffff601000 r-xp  [vsyscall]

  • Virtual System Call: 系统调用，但不需要int $0x80/sysenter

    • gettimeofday/time
    • getcpu

    以上系统调用可以在只读内核数据的基础上实现

    • 时间：内核维护中断时的时间，用户程序加上rdtsc的结果
    • getcpu：为每个CPU上的进程映射不同的页面

  • vvar, vdso: 加强版用户空间系统调用

    • vvar: 3 pages (ro, 内核数据); vdso: 2 pages (rx, 统调用代码)
    • 基本等于vsyscall
    • 注意到它们的地址是紧接着堆栈的 (随机值)

动态链接程序的地址空间

  • 启动动态链接器
  • 装载所有需要的共享对象
  • 重定位和初始化
  • ELF中入口点就是动态链接器
  • 动态链接复习: GOT, PLT, …