Concurrency: Processes & Threads

以下是 CS162 课程的整体结构:

前面几节课完成了 intro 和 OS Concepts 两部分,本节将进入 Concurrency 的第一个话题:Processes & Threads

Traditional UNIX Process

传统的 UNIX Process 通常称为 "HeavyWeight Process",在 Process 内部不存在并发。它主要由两个部分构成:

  • 顺序执行的程序

  • 被保护的资源

    • Main memory state (contents of address space)

    • I/O state (i.e. file descriptors)

每个 Process 的运行状态被保存在 Process Control Block(PCB)中,PCB 中始终保存着 Process 的一个快照,包括它的执行环境和被保护的资源。在 OS 调度的过程中,始终只有 1 个 PCB 处于活跃状态,OS 的职责就是在分配 CPU 和 Non-CPU 资源的过程中尽量实现公平与效率。

OS 切换 Processes 的过程,被称为 context switch,下图所示的是 OS 在两个 Processes 之间切换的过程:

切换的过程需要 save P0 state、reload P1 state,会带来开销。

Lifecycle of a Traditional Process

Process 的生命周期包括以下几种状态:

  • New:新创建的 Process

  • Ready:Process 准备完毕,等待 CPU 资源,随时可以执行

  • Running:执行中

  • Waiting:等待其它事件的发生,如 I/O

  • Terminated:Process 完成执行,保存执行返回值,等待 parent process 回收

Traditional Process Scheduling

在 kernel 中维护者若干个 queues,如下图所示:

PCBs 状态的改变就是从一个 queue 移动到另一个 queue 的过程,如:

  • ready queue => CPU:ready => running

  • CPU => I/O queue:running => waiting

  • I/O => ready queue:waiting => ready

实际上 I/O queue 还可以继续细分为 USB Unit 0、Disk Unit 0、Disk Unit 2、Ethernet 0 等等各种 queues。

Modern Process With Threads

将 Process 的执行抽象成一个新的概念,即 thread,且 Process 中能有多个 threads 共存:

  • Thread:在 Process 中的单个顺序执行的命令流,不可再分

    • Thread 使用 Process 的 Address Space

    • Threads 之间不存在隔离保护,因为它们共用 Address Space,且它们可以修改 Process 中的共享信息

  • Multithreading:一个 Process 中有多个 Threads 并发执行,完成各自的工作

如下图所示:

  • Thread 是并发的最小单元

  • Address spaces 是保护的最小单元

Thread State

Thread state 主要包括 2 部分:

  • State shared by all threads in process/address space

    • Content of memory

    • I/O State (file descriptors, network connections, etc)

  • State "private" to each thread

    • TCB

    • CPU registers

    • Execution stack(具体可以翻阅 CS107 相关课程,介绍地很透彻)

      • Parameters, temporary variables

      • Return PCs are kept while called procedures are executing

Motivational Example for Threads

想象如下程序:

main() {
ComputePI("pi.txt");
PrintClassList("clist.text");
}

由于计算 pi 的过程不会结束,PrintClassList 永远不会被执行,利用 Threads 修改程序:

main() {
ThreadFork(ComputePI("pi.txt"));
ThreadFork(PrintClassList("clist.text"));
}

这样两个 Threads 就可以并发执行,而这时候 Process 的 memory footprint 如下图所示:

此时在 Process 中可以看到两套 CPU registers、Execution stacks,但这也会引入新的问题:

  • 如何放置两个 stacks 的位置

  • stacks 的最大限制怎么定

  • 如何检查 stacks 之间发生重叠

这些都是 thread package 需要解决的问题。

Actual Thread Operations

threads 标准支持的基本操作如下所示:

  • thread_fork(func, args):创建一个新的 thread,执行 func(args)

  • thread_yield():主动放弃 CPU 使用权

  • thread_join(thread):在 parent 中,等待 forked 的 thread 执行结束

  • thread_exit():关闭 thread 并清理,唤醒等待 join 的 thread

pThreads 是符合 POSIX 标准的 thread package。

Dispatch Loop

OS 的调度程序:

Loop {
RunThread();
ChooseNextThread();
SaveStateOfCPU(curTCB);
LoadStateOfCPU(newTCB);
}

当 OS 启动时,这个 loop 就会被启动,直到系统关机。

Running a Thread

Dispatcher 如何运行一个 thread?

  • 加载 thread 的状态到 CPU,包括 registers、PC 和 SP

  • 加载运行环境 --- virtual memory space

  • 跳到 PC 处启动 thread 运行

Dispatcher 如何重新获取控制权?

  • Internal events:thread 主动返回控制权

  • External events:thread 被剥夺控制权

Internal Events

  • Blocking on I/O

  • Waiting on a "signal" from other thread

  • Thread executes a yield()

yield

computePI() {
while (true) {
ComputeNextDigit();
yield();
}
}

程序的运行栈如下图所示:

假设有两个 threads,S 和 T,S yield 之后,dispatcher 将 cpu 控制权交给 T,整个过程如下所示:

有趣的是,当 dispatcher 在 S 的 stack 中执行 switch 之后,返回到了 T 的 stack 中的 switch。

blocking on I/O

thread 请求一块数据的过程:

  • user code invokes a system call

  • read operation is initiated

  • run new thread/switch

与 switch 有关的统计值

  • 每个 10~100ms 之间就会有一次 switch

  • thread switching 操作的时间大约为 3-4 μs,比 process switching 快约 100 ns

  • 跨核 switching 大约花费核内 switching 两倍的时间

  • context-switching 的时间随着 working set 的大小增大而增大,甚至可以花费原来 100x 以上的时间(这里 working set 指的是 process 一段时间中使用的 memory 大小)

External Events

thread 不可能永久占用 CPU 资源,OS 通过外部事件(interrupts)来剥夺 thread 的 CPU 资源。

Network Interrupt

Timer Interrupt

一些 interrupts 的工作逻辑可以概括为:

TimerInterrupt() {
DoPeriodHouseKeeping();
run_new_thread();
}
IOInterrupt() {
ServiceIO();
run_new_thread();
}
// ...

How does Thread get started?

run_new_thread 后 dispatcher switch 到 ThreadRoot 中,后者是 thread 执行的起点:

ThreadRoot() {
DoStartupHousekeeping();
UserModeSwitch();
Call fcnPtr(fcnArgPtr);
ThreadFinish();
}

注意:本节插图中的 stack,蓝色表示 user stack,红色表示 kernel stack,二者逻辑上是两个不同的被保护的区域,请勿认为二者是连续的。

Thread Abstraction

在 thread 看来:

计算机中有无限个 CPU

threads 的执行速度不能保证,因此程序的设计不应该依赖于 scheduler 调度的方式

Thread Lifecycle

与 Process Lifecycle 非常类似:

Shared vs. Per-Thread State

如下图所示:

OS 为每个 thread 建立一个 TCB,里面包含:

  • Execution State:CPU registers, program counter (PC), pointer to stack (SP)

  • Scheduling Info:state, priority, CPU time

  • Various Pointers for implementing scheduling queues

  • Pointer to enclosing process (PCB)

  • etc

Multithreaded Processes

一个 Process 总有一个或多个 threads,对应到 PCB 与 TCB,就是一个 PCB 指向多个 TCBs:

  • 在同一个 process 中的 threads 之间做 context switch 开销小

  • 在不同 processes 中的 threads 之间做 context switch 则同时需要改变 memory 和 I/O address tables

典型的 multithreaded 程序举例如下:

  • Embedded systems

    • Elevators, Planes, Medical systems, Wristwatches

    • Single Program, concurrent operations

  • Most modern OS kernels

    • Internally concurrent because have to deal with concurrent requests by multiple users

    • But no protection needed within kernel

  • Database Servers

    • Access to shared data by many concurrent users

    • Also background utility processing must be done

  • Network Servers

    • Concurrent requests from network

    • Again, single program, multiple concurrent operations

    • File server, Web server, and airline reservation systems

  • Parallel Programming/Multiprocessing

    • Split program into multiple threads for parallelism

以 Client/Server 为例:

client/browser:

  • 可以同时用多个线程在多个 tabs 中访问同一个网站

  • 可以同时利用多个线程下载同一个页面的多个文件,最后渲染结果

web server:

  • 为每个 connection 创建 (fork) 一个 process

  • 每个 process 利用一个 thread 获取 request,处理并返回 response

  • 如果需要其他 I/O 操作,则 fork threads 完成相关工作,join 结果后返回

现实中,许多 processes 都是 multi-threaded 的,因此 thread context switches 即可能发生在 process 内部,也可能发生在 processes 之间:

如图中 Google Chrome process 内部就有 13 个线程。

Putting it together: Process

演变过程

传统的 Unix Process 如下图所示:

多个 Processes 并发如下图所示:

每个 Process 可以有一个到多个 Threads,如下图所示:

multi-cores

hyper-threading

Kernel/User Mode Threads

上文中介绍的都是 kernel threads:

  • kernel 原生支持的 threads

  • 每个 thread 之间相互独立地运行或者暂停

  • 一个 process 可能同时包含多个等待不同资源的 threads

kernel threads 的缺点在于,一切与它相关的操作都需要进入到 kernel mode 中,等待 kernel 调度。为了克服这个缺点,又诞生一种更轻量级的 thread,即 user threads:

  • 由用户程序提供 threads 的 scheduler 和 package

  • 可能存在多个 user threads 对应单个 kernel thread 的情况

  • user threads 可以只在 yield 的时候 switch,控制权自定义

  • 开销更小

但世上没有免费的午餐,由于多个 user threads 对应单个 kernel thread,一旦 kernel thread 被剥夺 CPU 资源,所有 user threads 就都无法继续运行。当然,对于这一问题也有折衷方案,即 scheduler activations,让 kernel 在 thread blocks 的时候提醒 user level threads 事情即将发生,用户进程可以使用其它 kernel threads 继续运行,此时多个 user threads 对应多个 kernel threads,如下图所示:

  • user-level library, single-threaded process:early Java

    • library does thread context switch

    • kernel time slices between processes

  • green threads:SunOS, Unix variants

    • user-level library does thread multiplexing

  • scheduler activations:Windows

    • kernel allocates processors to user-level library

    • thread library implements context switch

    • system call I/O that blocks triggers up-call

  • Linux, MacOS, Windows:use kernel threads

    • system calls for thread fork, join, exit (and lock, unlock ...)

    • kernel does context switching

    • simple, but a lot of transitions between user and kernel mode

High-level Example:Web Server

没有 thread 的版本:

serverLoop() {
con = AcceptCon();
ProcessFork(ServiceWebPage(), con);
}

有 thread 的版本:

serverLoop() {
con = AcceptCon();
ThreadFork(ServiceWebPage(), connection);
}

虽然看起来一样,但有本质的区别:

  • 使用 ThreadFork 可以在不同连接之间共享文件、CGI scripts、以及其它信息

  • Threads 很便宜,因此降低了 overhead/request

Thread Pools

上一个 thread-based web server 仍然存在问题,如果连接太多,threads 的增加没有被限制,容易由于频繁地为短时任务创建、删除 threads 出现性能下降、延迟增加的问题,导致 throughput 下降,因此使用一个有界的 thread pool,来表示最大并发的限制,如下图所示:

master.c
master() {
allocThreads(worker, queue);
while(True) {
con = AcceptCon();
Enqueue(queue, con);
wakeUp(queue);
}
}
worker.c
worker(queue) {
while(TRUE) {
con = Dequeue(queue);
if (con == null)
sleepOn(queue);
else
ServiceWebPage(con);
}
}

小结

  • Processes have two parts

    • Threads (Concurrency)

    • Address Spaces (Protection)

  • Concurrency accomplished by multiplexing CPU Time:

    • Unloading current thread (PC, registers)

    • Loading new thread (PC, registers)

    • Such context switching may be voluntary through yield(), I/O operations, or involuntary from timer and other interrupts

  • Protection accomplished restricting access

    • Memory mapping isolates processes from each other

    • dual-mode for isolating I/O, other resources

参考

slides, wikipedia page of thread pool, video