并发 - 引言

通过前面的一大节,我们了解了操作系统是如何给进程提供一个独占 CPU 、独占大部分地址空间的虚拟假象。

这部分,书中重点发关注另外一个虚拟抽象,线程(Thread)

前面的文章我们都是的执行流都只有一个,想要另外一个执行流,唯有多进程的方式。而多线程程序,运行一个进程拥有多个执行流。不同的是,进程是独立的,线程是共享所属进程的资源的。

线程的并发执行当然涉及到上下文切换。类比进程,操作系统把进程状态保存在一个叫做 PCB(Process Control Block)结构里,对应的线程的结构是 TCB(Thread Control Blocks),但这其中又有很大的不同。

01

相比单进程单线程的虚拟地址空间,支持多线程的地址空间有点不一样,进程的地址空间被切成单独的各个小块分配给不同的线程,这部分内存都是线程独有的,用于栈上变量的分配、参数/返回值的存储,这部分是 thread-local 的空间,独立于其他线程的。

线程的创建

大家可以参考不同平台的实现,书中列出的是 Linux 中的代码,我直接截图了。

02

共享数据:让事情更难了

我们看下面的例子,

03

两个线程 p1 和 p2 都要访问一个全局变量 counter,然而线程的切换是不受我们控制的,是受操作系统控制的,因此在执行线程代码对应的指令的任何时候都可能发生线程切换,那么问题就来了,我们预期结果是 20,000,000。然而实际并不如我们所愿。

04

问题的根源:不受控制的调度

让我们看下对 counter 加一的指令序列是怎样的:

mov     0x8049a1c, %eax
add     $0x1, %eax
mov     %eax, 0x8049a1c

这段指令序列很简单,CPU 可以在执行到 1、2、3 的任意时候终端当前线程的执行流而去执行另外一个,因此会导致一个线程的当前操作还没完成就被另一个线程修改了。

原子操作

为了解决这个问题,我们想借助硬件的帮助。

比如说,加一个数,memory-add 0x8049a1c, $0x1,让硬件保证它只有一条指令,而且完成这条指令所需的CPU 时钟内不能被中断,我们把这种行为叫做 原子的(atomically)

但是通常情况下,我们的处理器可能不提供这样的指令,因为这样的需求会使得硬件的设计变得很复杂,如果我们想要并发的修改一个 B-Tree,也想硬件帮我们一下,那怎么办,要硬件提供“原子化地更新 B-Tree 的指令”?

现代的做法是,操作系统提供一些帮助,但同时也需要操作系统设计者配合。所以关键点在于如何支持同步原语(synchronization primitives)呢?

先列出些关键的概念

  • A critical section is a piece of code that accesses a shared resource, usually a variable or data structure.
  • A race condition arises if multiple threads of execution enter the critical section at roughly the same time; both attempt to update the shared data structure, leading to a surprising (and perhaps undesirable) outcome.
  • An indeterminate program consists of one or more race conditions; the output of the program varies from run to run, depending on which threads ran when. The outcome is thus not deterministic, something we usually expect from computer systems.
  • To avoid these problems, threads should use some kind of mutual exclusion primitives; doing so guarantees that only a single thread ever enters a critical section, thus avoiding races, and resulting in deterministic program outputs.

另外一个问题:等待另一个

上面只列出了一个问题,就是对共享数据的访问问题,其实还有另外一个,那就是一个线程需要等待某个操作完成能够接受到通知。

比如说线程执行一个 I/O 操作,这时候线程的执行流是不会继续走的,想等操作完成,操作系统可能会把它休眠,但是同时操作系统也需要把它唤醒。

这会在接下去的章节讲到,就是 condition variables

线程创建

int pthread_create(..., // first two args are the same
                   void * ( * start_routine)(int),
                   int arg);

线程完成

想等待一个线程完成的话,可以用 pthread_join()

int pthread_join(pthread_t thread, void ** value_ptr);

重要的 API 之一,给 critical section 提供 mutual exclusion 的。

int pthread_mutex_lock(pthread_mutex_t * mutex);    // 加锁

int pthread_mutex_unlock(pthread_mutex_t * mutex);  // 释放锁

下面这段代码就是一个 critical section:

pthread_mutex_t lock;
pthread_mutex_lock(&lock);
x = x + 1; // or whatever your critical section is pthread_mutex_unlock(&lock);
  • 如果没有其他线程拥有 lock,当前线程会获得这把锁,并且进入 critical seciton
  • 如果其他线程已经拥有了此 lock,想获取此 lock 的线程不会从这函数中返回,直到它能获取到锁为止
  • 不一定呆呆的等待,也可以设置一个超时时间。

然而,上面的代码不完善,
第一,锁没有被初始化,应该 pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;,或者

int rc = pthread_mutex_init(&lock, NULL);
assert(rc == 0); // always check success!

第二,它没有对加锁失败和成功有判断,如果失败,代码可能会走到我们不想走的分支,应该这样

// Use this to keep your code clean but check for failures
// Only use if exiting program is OK upon failure
void Pthread_mutex_lock(pthread_mutex_t * mutex) {
    int rc = pthread_mutex_lock(mutex);
    assert(rc == 0);
}

其实还有另外两个加锁的 API 版本,顾名思义可以猜出他们的意思,

int pthread_mutex_trylock(pthread_mutex_t * mutex);

int pthread_mutex_timedlock(pthread_mutex_t * mutex, struct timespec * abs_timeout);

条件变量 Condition Variables

int pthread_cond_wait(pthread_cond_t * cond, pthread_mutex_t * mutex);

int pthread_cond_signal(pthread_cond_t * cond);

条件变量在类似信号通知的场景中使用会比较有用,如果一个线程在等待其他线程完成某些事情之后希望收到通知,那么条件变量就可以发挥作用。

pthread_cond_wait() 会使得调用当前线程的休眠(sleep),直到其他线程完成某些任务,通过 cond 变量通知到它,然后把它唤醒。

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

Pthread_mutex_lock(&lock);
while (ready == 0)
    Pthread_cond_wait(&cond, &lock);
Pthread_mutex_unlock(&lock);

上面的代码一直在等待 ready 变量能够改变(等于非 0),否则就 wait and sleep until other thread wakes it up。下面是唤醒的代码,

Pthread_mutex_lock(&lock);
ready = 1;
Pthread_cond_signal(&cond);
Pthread_mutex_unlock(&lock);

这里值得注意的是,Pthread_cond_wait 函数需要那个 lock 作为参数,然而这里的 Pthread_cond_signal 并不需要,原因是 Pthread_cond_wait 会让线程去 sleep,同时会把锁给释放了,等到它被唤醒的时候会再次去 acquire 这个锁。

如果不这样做,其他线程是没有机会能拿到锁的,因此 CPU 时间将会无限的浪费在休眠线程上。
另外,在被唤醒之前也得先获取到锁,因为得保证同一时刻只有一个线程拥有着这把锁。

还有,被唤醒的线程是用 while 循环重现 check 条件,而不是 if。

总结

好啦,基本概念介绍完毕,现在让我们继续吧!

Comments
Write a Comment