19. Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism

背景

• 并行计算的效果, 取决于创建和管理并行的开销; 开销大的话即使 coarse grained parallelism 也不划算; 开销小的话, 即使 fine grained parallelism 也划算;
• 传统 UNIX 进程 = 单地址空间 + 单执行流;
• 设计目标是单核多道程序环境(multiprogramming), 适合粗粒度并行, 不适合细粒度并行;

线程支持的两种方式

1. 用户级线程 (User-level threads)

• 通过 runtime library 库实现(不改内核);
• 优点:
  • 性能好: 上下文切换, 创建销毁的代价接近过程调用;
  • 灵活: 可以按语言/应用需求定制;
• 缺点:
  • 内核对线程不可见, 仍然只认识"进程";
  • 进程就像虚拟 CPU, 被内核调度到物理 CPU 上;
  • 遇到 I/O 阻塞, 页面缺页, 多道并发 时, 线程库感知不到真实 CPU 情况, 导致性能下降甚至错误;

2. 内核级线程 (Kernel threads)

• 内核直接提供多线程支持, 每个线程对内核可见, 内核负责调度;

• 优点:

  • 与系统资源和调度机制直接集成, 没有"virtual/real processor 错位"的问题;
  • 不会出现用户级线程那种 “一挂全挂”(比如一个线程阻塞整个进程);

• 缺点:

  • 内核操作比用户空间 heavyweight 得多;
  • 性能明显比用户级线程差 (通常差一个数量级);
  • 对于很多并行程序仍然"太重";

• ULT 库会在程序启动时调用内核 API(比如现代系统里 pthread_create())来创建一批内核线程;

  • 数量一般与物理 CPU 数接近, 用来"占位", 相当于"虚拟 CPU 池";

• ULT 线程 绑定 在这些 KLT 上运行

  • 每个内核线程里跑的是用户线程库的调度循环;
  • 库自己决定哪个用户线程在这个内核线程里执行;
  • 所以用户线程确实是基于内核线程执行的;

设计目标

他们要设计一个 kernel interface + user-level thread package, 结合两边的优势:

1. 功能性 (Functionality)

• 能表现得像内核线程系统一样, 即便有多道并发, I/O, 缺页;
• 保证:
  • 有线程 ready queue 时, 处理器不会 idle;
  • No high-prioirty thread waits for a processor while a low-priority thread runs
  • 当某个线程因为 page fault 或 I/O 阻塞进入内核, 原来的 CPU 可以立刻切去跑别的线程;

2. 性能 (Performance)

• 常见线程操作的开销接近一次 procedure call (和最好的 user-level thread 相当);
• 但同时避免了用户级线程系统的"系统整合问题";

3. 灵活性 (Flexibility)

• simplify application-specific customization
• 可以替换不同的 concurrency model (workers, actors, futures 等);

但是设计的问题在于, 用于精细化控制和调度的 info 存在于 application address space 内部, 而 kernel 需要访问这些 user-level scheduling info 来进行决策

方法论

• 为每个 APP (Process) 提供一个 "虚拟多处理机 (virtual multiprocessor)"抽象;

  • 应用能清楚知道自己有多少个处理器, 是哪几个处理器;
  • 应用完全掌控: 哪些线程运行在哪些处理器上;

• kernel 决定处理器资源如何在不同地址空间(应用)之间分配;

  • 可以动态调整一个应用的处理器数目;

• 关键点:

  • 内核不会像传统系统那样"替应用解释事件";
  • 内核只把与调度相关的事件通知到应用的用户态调度器;
    • kernel’s role is to vector events that influence user-level scheduling to the address space for the thread scheduler to handle,
  • 应用的线程库根据事件自己决定如何调度;

• Upward Communication: kernel -> addr space, functionality improved since app know its own context

• Downward Communication: addr space -> kernel, performance improved since only operations that would affect the kernel behaviors would be notified

Scheduler Activation

• execution context for an event vectored from the kernel to an address space;
• the address space thread (user level) scheduler uses this context to handle the event

为什么 kernel thread 的性能远远低于 user-level thread?

1. Protection Boundary Overhead

• 内核线程: 每次线程操作都要跨越保护边界(用户态 $\leftrightarrow$ 内核态);
  • 需要一次 trap $\rightarrow$ 大约 19 $\mu$s;
  • 内核必须 check parameters, 防止恶意或错误的程序破坏系统;
• 用户级线程:
  • 调用开销接近过程调用(7 $\mu$s);
  • 甚至可以通过编译器优化(内联, 寄存器分配)进一步降低成本;
  • 安全性仍然依靠地址空间隔离保证, 不会影响别的进程;

2. 通用性开销

• 内核线程: 一个统一实现要满足所有应用的需求 $\rightarrow$ 加入了很多"通用功能"(比如抢占式优先级调度);

  • 这对一些只需要简单 FIFO 调度的并行程序来说就是额外负担;

• 用户级线程:

  • 每个应用可以链接不同的用户线程库;
  • 库可以裁剪, 专门优化, 只保留所需功能;
  • 更灵活, 也更轻量;

• 用户级线程不但有 performance 优势, 还有 flexibility 优势;

  • 在其他系统服务里, 常常要在"性能 vs 灵活性"之间 trade-off, 但 用户级线程避免了这种权衡:
  • 性能高 $\rightarrow$ 因为避免内核切换;
  • 灵活性高 $\rightarrow$ 可以支持多种并行模型(FIFO, workers, actors, futures…), 无需改内核;

为什么传统 kernel interface 对 user-level thread 集成的效果不好?

用户级线程本身并不"天生"难集成, 问题在于 传统内核 interface 不合适:

• kernel events 对 user-level 不可见
  • 就比如 ult 调用了 read() 读取io, 会导致 klt 阻塞, 但 ult 库并不知道这个事件, 也不知道该调度哪个线程; 也无法预知这个阻塞有多久直到 klt 在 event 发生之后返回
  • 相当于每个 user-level 预定的 klt 都只知道这是一个 virtual processor, 但是不知道也无法控制这个 processor 的状态
• kernel thread 的 scheduling 对 user-level thread state 不可见

一种看似可行的办法: 创建比物理处理器更多的内核线程; 这样当一个内核线程阻塞, 另一个内核线程可以接管;
但这带来新问题: 当阻塞结束后, 内核会有 比处理器数更多的内核线程 都在 runnable 状态; 内核调度器必须选择运行哪几个内核线程; 由于每个内核线程里都装着一个用户级线程 $\rightarrow$ 内核就间接决定了哪些用户级线程能运行; 这破坏了用户级线程调度库的控制权;

• Time Slicing 调度机制下 原有 interface 的问题:
  • 内核线程可能在持有用户级线程的自旋锁时被切走, 导致别的用户线程无限 spin;
  • 也可能切换去执行一个"空闲"的用户级调度器 $\rightarrow$ 浪费 CPU;
  • 甚至可能让高优先级的用户线程被低优先级的用户线程挤掉;

Design

Abstraction Overview

1. Virtual Multiprocessor

• 内核的角色:
  • 决定每个地址空间(进程) 分配 多少个处理器; 可以动态增减分配;
• 用户态的角色:
  • 在自己获得的这些"虚拟处理器"上, 自主 决定运行 哪些用户线程; 在应用看来, 就像自己独占了一台物理机器;

2. 双向事件通知

• 内核 $\rightarrow$ 用户态
  • 当处理器分配变化时(增加/减少 CPU);
  • 当某个用户线程在内核中阻塞或唤醒时(比如 I/O 阻塞, page fault);
  • 内核不再自己"解释"这些事件, 而是把事件向上传递 (vector) 给用户态线程调度器去处理;
• 用户态 $\rightarrow$ 内核
  • 只在需要影响"处理器分配"时才通知内核;
  • 比如: 并行度增加, 需要更多 CPU; 或者: 并行度减少, 请求释放 CPU;
  • 普通的线程调度决策(哪个线程先跑)都留在用户态 $\rightarrow$ 避免频繁陷入内核, 保持高性能;

3. 对程序员的影响

• 应用程序员看到的接口还是 正常的内核线程接口 (比如 Topaz threads API);
• 只是背后换成了"用户态 virtual multiprocessor + scheduler activations"的机制;
  • 所以对开发者透明, 区别只在于性能显著提升;