操作系统复习:并发部分

Concurrency: An Introduction

我们之前学过的内容,是如何把单个CPU抽象化成多个。

在这一部分,我们介绍一种新的抽象:thread。多线程程序有多余一个以上的执行点,每个线程其实就是分开的进程,只不过有一个不同:线程之间共享address space,所以它们可以共享数据。

线程的状态和进程也非常像,它也有一个程序计数器,每个线程也有自己的寄存器。所以如果线程进行切换,也是有context switch发生的。之前进程会把状态保存在process control block (PCB),而线程则是会放到thread control blocks (TCBs)里面。当然在线程的context switch之间,address space是不会变的,也就是完全用不到页表。

另外一个不同的是栈的不同。之前的单线程进程是只有一个栈的,而在多线程进程中有,每个线程都有一个栈,这些栈就叫做 thread-local

为什么使用线程?

两个主要的原因,第一个是parallelism并行性,如果有多于一个CPU,那么如果进程只有一个线程,多CPU就发挥不出功效。第二个原因是可以有效避免进程被IO阻塞,一个线程被阻塞了,可以让另外一个线程执行。

当然上面的这些,都可以通过多进程来实现,然而线程因为天然共享地址空间,所以在共享数据方面有优势。

线程创建的例子

线程一旦创建完毕,可以由调度器来决定线程上面时候执行。所以除非用特定的操作,否则线程的执行顺序是不一定的,这一切都是由OS scheduler来完成的。

共享数据问题

假设有一个共享的变量x,有多个线程希望去修改它,最后的结果肯定不会如你所愿的。

问题的关键

  • race condition:多个线程想要同时进到critical section里面并且进行修改共享数据。
  • 同时可以导致race condition的代码叫critical section:这部分的代码会访问共享的资源,而且不能同时运行多个线程。
  • 一个indeterminate程序包含一个或者多个race condition,程序的结果不确定。
  • 我们真正希望的是这段代码是mutual exclusion,即当一个线程正在critical section的时候,另外所有的线程都无法进入。

原子性

一个有效的解决办法就是原子性,如果有一个指令能够把多条指令合并在一起,之前的问题就不会发生了,然而实际中我们并没有这样子的指令。

我们要求硬件提供的是一种叫synchronization primitives同步原语的东西,再加上操作系统的帮助,我们就可以得到我们想要的。

还有一个问题:等待另一个

除了上面提到的对于共享资源的访问,还有一个问题就是有些时候,一个线程必须等待另外一个线程完成,

为什么是操作系统来解决?

因为操作系统本身就是一个concurrent程序。

Interlude: Thread API

如何创建并且操作线程呢?

线程创建

pthread_create函数,有四个参数:

  • pthread_t *thread:用来指定你的创建的线程
  • pthread_attr_t *attr:指定这个线程的属性,可以在这里设定栈的大小或者优先级什么的,当然最常见的还是NULL,因为默认的就足够好用了。
  • void *(*start_routine)(void*):类似于java中的run函数。
  • void *arg:上面的函数的参数。

等待另一个线程完成

直接调用pthread_join(),传入两个参数,分别是要等待哪个线程,第二个参数是你希望线程给你返回什么,比如线程A希望线程B去做一些事,所以肯定要B的返回结果。

1
2
int pthread_mutex_lock(pthread_mutex_t *mutex); 
int pthread_mutex_unlock(pthread_mutex_t *mutex);

当你的线程有critical section的时候,需要确保正确性的时候,就可以用锁了,用法非常简单:

1
2
3
4
pthread_mutex_t lock;
pthread_mutex_lock(&lock);
x = x + 1; // or whatever your critical section is
pthread_mutex_unlock(&lock);

如果线程得到了锁,就会从第二句返回,否则就会一直卡在第二句。当然上面的代码其实是错误的,因为首先这个锁并没有被初始化,可以通过静态初始化或者运行时初始化;其次是它没有错误检查。

除此之外,还有两个函数:

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

第一个函数是尝试一次,如果能得到就得,得不到就立刻返回。第二个函数可以指定时间,如果超时了且还没获得锁就返回。这两个函数尽量少用(为什么?)

Condition Variables条件变量

1
2
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); 
int pthread_cond_signal(pthread_cond_t *cond);

如果要使用条件变量,那还需要一个相关的锁。第一个是让线程去睡眠,等待另外的线程叫醒它,第二个就是叫醒相关的条件变量的线程。这里有几点需要注意:当你去叫醒别的线程的时候,必须确保你有锁,这样不会让两个线程进入条件竞争。当你去睡眠的时候,必须释放锁;当醒来之前,必须取回锁。

总结

我们介绍了如何创建线程,如果使用锁(mutex)以及如何通过条件变量来进行线程的等待和唤醒。

Locks

之前说了只要原子性代码就不会有问题,但是没有这样的银弹,所以需要用lock机制来自己保证原子性。

基本想法

我们假设我们的critical section是这样的:balance = balance + 1;,如果要使用锁,我们只需要这样:

1
2
3
4
lock_t mutet = ...		// 初始化
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

上面的代码看上去简洁,注意的是当一个线程得到锁了,其它线程就会在得到锁的那一句卡住,直到锁被释放。锁被释放的时候,可以是线程自己注意到锁被释放了,也可以是被通知了。

Pthread Locks

POSIX库用的锁的名字叫mutex,用来提供线程之间的互斥。

制作一个锁

从程序员的角度来说,理解锁是非常简单的,但是底层呢?硬件方面是如何支持的,操作系统是如何支持的呢?

评估锁

在正式开始之前,我们需要明白我们的目标是什么,以及我们需要知道我们要如何评估锁的实现呢?

首先,锁必须要能够完成它最基本的功能——提供互斥。

其次是公平性,不能让某些线程处于饥饿状态。

最后一个是性能,因为有了锁肯定性能会下降。我们比较无锁状态,单CPU状态和多CPU状态下的锁的表现。

控制中断

最早的实现互斥的是通过关闭中断来完成的。在我们进入critical section之前,我们确保中断关闭,也就意味着我们进入到critical section中的时候不会发生线程的切换,那么自然就是原子性的。当我们从critical section出来的时候需要再次打开中断。中断的关闭和打开都是通过物理的指令来完成的。

这种方法的优点就是简单,缺点却是一大堆:首先打开中断和关闭中断需要特权操作,这需要对线程的充分信任。一旦程序执行死循环,那么只有重启系统才可以了。其次,这个方法对多处理器无效。因为你只关闭了当前线程所在的CPU的中断,另外一个CPU上面的线程照样可以访问。再有,关闭中断可能导致一些丢失问题,比如恰好一个IO完成了,但是现在中断是关闭的。最后也是最不重要的,这个方法效率很低,因为开关中断的指令CPU执行的很慢。

所以综上所述,也只有操作系统在执行自己的代码的时候(自己当然信任自己啦)会使用这个方法。

A Failed Attempt: Just Using Loads/Stores

我们可以有一个简单的想法,通过使用一个变量来控制。还别说,我当时初次接触的时候真的是这么想的。显然这个方法是错误的……因为可以同时两个线程都进入到critical section里面。其次是性能也贼低,因为不停在循环中浪费时间。当然有大佬通过两个变量真的做到了,但是意义不大..因为现在都是硬件支持了。

使用Test-And-Set来解决问题

早期的多处理器系统中提供了这么一条指令(目前就算是单处理也提供了):test-and-set (也叫 atomic exchange),思路很简单,就是把原来旧的值old_value替换成新的值,并且返回旧的值,就像下面的函数所示的一样:

1
2
3
4
5
int TestAndSet(int *old_ptr, int new) {
int old = *old_ptr; // fetch old value at old_ptr
*old_ptr = new; // store ’new’ into old_ptr
return old; // return the old value
}

最最与众不同的是,这个“函数”它本身是原子性的。

然后就可以构造出spin lock,这是最简单的锁,简单的自旋,还有一个条件是这个必须在抢占式调度器上使用,如果不抢占,那这个自旋将会永远的旋下去…

评估自旋锁

最主要的是锁的正确性:显然自旋锁满足了。第二个是公平性,自旋锁显然没有保证公平性。第三个就是性能指标,在单处理器上,性能很糟糕,因为调度器会让每个线程都跑一次,然而只有一个线程真正再跑,其它都是在虚度时间(并不会让出时间);但是如果CPU的数量和线程数相等的话,这个性能就很不错了

Compare-And-Swap

在一些系统中,另一条指令就是大名鼎鼎的compare-and-swap,这个提供三个参数,old,expected和new,如果old和expected相等,那么就把old设置成new,否则就不设置。最后返回最初的old的值。

根据上面的分析我们不难得到,compare-and-swap就是升级版的Test-And-Set,在将来,我们会用这条指令实现lock-free synchronization。但是目前,它的功能和test-and-set是一模一样的。

Load-Linked and Store-Conditional

在一些平台中提供了这么一对指令来帮忙:load-linkedstore-conditional,下面是它们的C的伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
int LoadLinked(int *ptr){
return *ptr;
}

int StoreConditional(int *ptr, int value) {
if (no update to *ptr since LoadLinked to this address) {
*ptr = value;
return 1; // succcess!
}else{
return 0; // fail to update
}
}

第一条指令就像load指令,就是把命令从内存中取来放到寄存器里。

第二条指令只有在没有更新的时候才能成功,并且成功更新。

注意!上面是伪代码,它们其实是指令,所以是原子性的。

Fetch-And-Add

这也是一条指令,同样的伪代码见下:

1
2
3
4
5
int FetchAndAdd(int *ptr){
int old = *ptr;
*ptr = old + 1;
return old;
}

同样可以用这条代码来完成上锁的操作。

经过这些指令,不难发现,只要一条指令中对值进行了修改,并且能够获得原来的值,就能够用来上锁。

自旋太多了

自旋是非常浪费时间的,因为除了空等,什么也做不了,那么要怎么做呢?

Yield

与其自旋浪费时间,不如直接把CPU时间让出来,yield能够让线程从running态转到ready态。但是到目前为止,我们都没有处理饥饿问题。如果运气差,一个线程是完全可能这辈子都在进行yield操作的。

sleep代替spin

为了避免饥饿问题的发生,我们需要控制哪个线程应该在锁被释放之后去得到锁。我们可以用一个队列来追踪所有等待相同锁的线程。

简单起见,我们使用两个调用,park()让线程去睡眠,unpakr(threadid)让其苏醒

不同的操作系统不同的支持

我们可以使用这么多的命令来完成我们的锁,但是不同的操作系统支持不一样。

两阶段锁

就是结合了上面的两种,首先先自旋一会,如果不行就进入睡眠。

总结

所以锁其实就是靠的硬件(指令,且指令本身是原子性的)加上 操作系统的算法来实现的。当然大家都有各自的区别。

Lock-based Concurrent Data Structures

通过对数据结构加锁,可以实现thread safe,如何加锁则成为了关键。既要能保证正确性,又要有高性能。

当然数据结构千千万,这里当然不可能全部涵盖。

并发计数器

就是最简单的用来计数的,每当当用increment方法的时候把value加一。只需要在每个操作的最开始添加锁,然后在操作结束的时候释放锁,就能保证正确性了。有一种数据结构,使用monitors构造,和它非常像,而且它的锁是自动获取自动释放的。

但是这个有一个性能问题,在单CPU上表现良好,但是到了多核中反而性能下降。

可扩展性

研究人员研究了如何去打造更加具有扩展性的计数器,其中的一个方法就是approximate counter,核心思路就是使用多个local counter,每个CPU核心对应一个,除此之外还有一个global counter。每个counter,包括global都有一个锁。

当运行的时候,每个CPU的counter都会各自更新,然后这个local的值会定期(记做时间S)传输给global(当然需要先获取锁0),然后把这个global的值加上自己的值,并把自己清零。

显然如果S越短,那么性能就越低,但是能够保证global的值更加准确。这也是另外一个trade-off:accuracy/performance trade-off

并发链表

我们在这一部分仅关注链表的插入,其余的诸如查找,删除的留给自己思考。

插入操作是这样的,首先锁住链表,然后创建一个新的节点,并且利用头插法插入到链表中,最后释放锁。有一个小细节就是当malloc失败的时候,也需要释放锁。

然而这种异常处理被证明了很容易出错,因为异常的路径千千万,而我们只处理了一条。所以我们需要对其进行改进,保证其不会出错。

修改方法也很简单,只有插入链表的操作才需要进行加锁,创建节点的那部分不需要上锁。

改进

现在已经可以得到正确的并发链表了,但是扩展性不够好。研究者研究了一个叫hand-over-hand locking的东西,思路也很简单,不要一次就把整个链表给锁了,而是锁其中的一个节点。在链表中遍历的时候,首先先去把下一个节点锁了,然后释放当前的这个节点,这也是hand-over-hand的来源。

但是说是改进,其实虽然锁的粒度变小了,其实效率到底有没有提升呢?因为你每次移动节点都需要获取释放锁,其实比单个锁的链表也快不到哪里去,只是支持较高的并发性。

并发队列

当然,通过一把大锁,是可以实现的,就像上面的链表一样,所以这一部分我们就省略了。

核心思路也很简单,使用两个锁,一个锁头一个锁尾,然后和链表一样,仅仅锁住操作队列的代码,而不会去锁。除此之外队列还有一个大小,如果超过了的话,线程就需要等待,这部分的内容留到条件变量中详细介绍。

并发hashtable

这一部分我们以一个固定大小的hashtable来作为例子。emmm 其实本质上就是之前开发的一个并发链表作为底层结构。

总结

我们在这一部分介绍了一下并发的数据结构,从计数器,链表到队列,最后是哈希表。我们在这一章节学习了一个重要的原则:在控制流中记得释放锁,只锁住真正操作链表的部分,其余的都不要上锁。

Condition Variables

锁不是唯一的用来构件并发程序的唯一方法。在很多情况下,线程希望在执行之前检查某一个条件是否满足。在这里可以通过一个全局变量来做,但是线程就会使用自旋,这非常消耗CPU时间。

定义

为了达成上面的条件,线程可以使用一个叫condition variable(之前被叫做private semaphores)的东西,本身是一个queue,如果条件不满足,就会放到queue里面去,另外的线程可以唤醒队列中的线程。

条件变量本身还需要锁进行配合,当使用wait的时候,会释放锁并且去sleep,且这个操作是原子性的。当线程醒来的时候,会先去获取锁然后才从函数中返回。这是为了避免race condition。

在使用wati/signal的时候牢记这几点:必须要有一个全局的变量来控制;对全局变量的控制必须加锁;使用wait的时候请配合while使用;在执行signal和wait的时候,请确保自己有锁。

生产者消费者问题

producer/consumer problem,也被称为bounded buffer problem问题,首先由Dijkstra提出,并且之后人们在此基础上发明了semaphore,一个又可以作为锁又可以作为条件变量的东西。

生产者消费者的一个典型应用就是web server,生产者不断把http request放进来,而消费者则不断取出来并且处理。同理你在shell里使用管道符,也是一个生产者一个消费者。

首先还是从最简单的出发,我们有一个长度为1的数组和一个全局变量count。生产者的任务就是确保count是0,然后把count置成1,并且把自己的数据放到数组中。而消费者则相反。

如果仅仅是单个生产者和单个消费者,那么是很简单的,代码也能很好地运行。但是如果一个生产者多个消费者就会有问题出现了:消费者1首先因为没有资源而去睡眠了;生产者生产了资源并且通知了消费者1,消费者1成功醒来,但是CPU却被别的消费者抢走并且成功的消费,而当时间片再度回到消费者1的时候,它无法完成消费。

根本原因是,生产者只是唤醒了睡眠的消费者,但是消费者不一定能真正消费到。

改进

只需要把if改成while,即当睡眠的消费者醒来的时候,再判断一下资源到底存不存在,如果存在才去消费。这也告诉我们一个道理:有的时候反复确认总是好的,因为只要消耗极少量的资源就可以确保事情万无一失。

然而,就算把if改成了while,还是有问题的。现在假设消费者都去睡眠了,然后生产者生产好了,并且唤醒了其中一个消费者(注意只是去唤醒了一下,此时线程还没醒)。然后生产者又想继续去生产,但是它发现满了,所以去睡眠了。此时消费者才真正的苏醒,然后开开心心的消费了数据,并且需要通过条件变量来唤醒,但是!目前生产者和其中一个消费者都在睡眠呢,该唤醒谁呢?假设不小心把另一个消费者唤醒了,那个消费者醒来一看没有数据,就又去睡眠了。好了,此时三个人都睡眠了,谁也唤醒不了了。

关键就在于,消费者不应该唤醒消费者,同理生产者也不应该唤醒生产者。

简单的解决方法

使用两个条件变量就行了呀。

正确的解决方法

之前的方法已经可以保证正确性了,接下来要做的就是提高性能和并发性。只需要把之前的长度为1的数组变大就行了。

Covering Conditions

类比java中的notify,如果仅仅是notify,可能有线程应该醒来但是没有醒来,而如果使用的是notifyAll,那么就可以都醒来了。这个就是covering condition,因为它覆盖了全部的线程,缺点么就是全部的线程都会醒,而其中的大部分又会马上去睡觉。而且,这个也可以用到之前的生产者消费者的问题中,这样只需要一个条件变量就可以了。

总结

在这一章里面我们介绍了一下利用条件变量完成的wait/notify机制。

Semaphores

我们介绍了lock和condition variables,Edsger Dijkstra,第一个想到把两者合二为一。

定义

本质上,信号量是一个int值,我们可以通过sem_wait()sem_post()来进行修改,而Dijkstra本人把前者称为P,后者称为V。

信号量需要初始化,而且它除了可以在同一个进程的线程之间共享,还可以在不同的进程之间共享。

sem_wait的逻辑是,把信号量减一,如果信号量是负数了就wait;sem_post的逻辑是加一,如果有一个或者多个线程在等待,那么唤醒一个。

Binary Semaphores

我们首先把信号量当成锁来用:只需要把信号量的初始值设置成1即可。

然后通过sem_wait()进入critical section,通过sem_post()来退出。

Semaphores For Ordering

在这里我们假设一个线程parent希望在子线程完成之后唤醒,那么我们应该怎么做呢?

把信号量的初始量设置成0,这样只要parent执行sem_wait()就会进入睡眠,然后子线程就会执行,当子线程执行完成之后,执行sem_post()并且唤醒parent。而且就算是子线程先执行,逻辑上也是正确的。

生产者消费者问题

初次尝试

我们使用两个信号量,emptyfull,通过使用两个信号量,可以保证数组长度是1(即只能存放一个)的情况下是正确无误的。

当数组长度大于1的时候,就会有问题了。假设了两个生产者同时执行,那么它们之中的一个就会覆盖掉另外一个。

解决方法:增加互斥量

修改数组的index和在其中填入数据其实是critical section,所以其实需要锁来解决。所以只需要在之前的代码中加入锁就可以了。真的吗?加入锁会出现这么一个情况:消费者先执行,所以先获得了锁,但是它消费不了,因为现在没东西让它消费,于是它只好阻塞(不释放锁)。然后生产者无法获得锁,自然无法生产数据。这样死锁就形成了。

最后解决办法

其实,只需要换一下信号量和锁的位置就可以了,也就是让加锁和解锁最贴近critical section。

读写锁

如果所有的线程仅仅是读取内容,那么甚至都不需要锁,所以我们需要一种新的机制来来支持更好的并发。

读写锁本质上也是通过信号量来完成的,获取读锁是很容易的,而获取写锁,需要等所有人的读锁释放了之后才可以。

The Dining Philosophers

哲学家就餐问题。我们假设5个哲学家,一共五把fork,然后每个哲学家需要两个fork才可以进餐。我们首先假设有5个信号量。

错误的方法

我们先把所有的信号量设置成1,那么获取fork的代码就很简单,只需要让左右边的fork都sem_wait即可。显然这个方法不行,一个最简单的反例:所有哲学家都拿起了自己左手边的fork,那么就无法获取到右手的fork——死锁就诞生了。

打破依赖

上面的问题之所以会发生,就是因为他们形成了一个环,所以我们只需要让最后一个哲学家稍微变一变:他是先拿右手边的fork,然后再拿左手边的。(这是Dijkstra解决问题的方法)

线程限制

另外一个信号量的作用就是限制线程的数量。

如何实现信号量

我们就用mutex和condition variables来完成信号量吧——一个结构体,里面有一个value(就是信号量的值),还有一个锁和一个条件变量。

1
2
3
4
5
6
7
8
9
10
11
12
void Zem_wait(Zem_t *s) {
Mutex_lock(&s->lock);
while (s->value <= 0)
Cond_wait(&s->cond, s->value--;
Mutex_unlock(&s->lock);
}
void Zem_post(Zem_t *s) {
Mutex_lock(&s->lock);
s->value++;
Cond_signal(&s->cond);
Mutex_unlock(&s->lock);
}

总结

信号量简单且使用,有了它我个人觉得完全就不需要锁和条件变量了。

在一章里面我们学习了一些案例和一些解决办法。

Common Concurrency Problems

并发中最常见的问题,应该就是死锁问题了吧。除了死锁,这一章我们还将学习并发下遇到的问题。

问题的类型

引用了一篇文章,该文章的作者分析了四个有名的软件并且找到了它们在并发下的问题。这四个软件分别是Mysql、Apache、Mozilla和OpenOffice。

非死锁BUG

这部分主要有两类,一类是atomicity violation的bug和order violation的bug。

Atomicity Violation Bug

违反原子性的bug。

1
2
3
4
5
6
7
// thread 1:
if(a){
fputs(a,....);
}

// thread 2:
a = NULL;

第一个线程判断a是不是NULL,如果不是则进行操作,而第二个线程把a改成了NULL。

显然,如果第一个线程成功通过了if判断,然后恰好发生时间片中断,此时到了第二个线程,然后第二个线程把a改成了null,当再次回到第一个线程的时候,由于此时a已经是Null了,所以就会出现问题。如果使用的语言是java,那就是空指针异常。

解决方法也是相当简单,只需要都加锁和解锁就可以了。

Order-Violation Bugs

1
2
3
4
5
6
7
8
9
// thread 1:
void init(){
mThread = createThread(mMain,...);
}

// thread 2:
void mMain(){
mState = mThread->State;
}

在线程2里面的代码,需要mThread为非空才可以。然而如果线程2在创建完成之后立马运行,那么可能会导致mThread目前还是空的,这样也会导致空指针异常。

为了保证有序嘛,那只需要用到条件变量即可。

非死锁bug总结

大部分的bug都是属于上面那两种的,所以我们需要尽量避免这种问题。当然现在有一堆工具可以检测这些问题,但是修复起来就不是那么容易了。

死锁bug

死锁为什么会发生呢?

首先是系统太复杂了,其次是封装,由于封装我们并不了解所有的内容,所以会发生问题。

死锁的四个条件

  • Mutual exclusion:线程声明了对资源的独占控制,锁就是最典型的例子。
  • Hold-and-wait:线程持有分配给它的资源,并且等待额外的资源。
  • No preemption:资源一旦分配给线程,就无法强制剥夺。
  • Circular wait:形成了一个环。

只要这四个条件中有一个不满足,死锁就不会发生。

避免死锁

#####Circular wait

最常用也是最有用的方法,就是你写代码永远不要有Circular wait,最直白的方法就是提供一个锁获取的顺序,然后根据锁的顺序来写代码。

当然在复杂系统中这么做可能不是很合适,所以我们需要有partial ordering。一个简单的方法就是,通过判断两个锁在内存中的地址,比如你可以规定低地址的锁优先,只要你一直保持这么干,就可以确保避免死锁。

#####Hold-and-wait

这个可以通过一次性获取锁来避免,而且必须是原子性的。 首先获取一把锁,保证在获取所有锁的过程中不会被中断。

该技术对性能的影响大,所以不推荐使用。

No Preemption

这部分最主要的原因就是只有当unlock执行的时候,锁才会被释放。很多库都提供了这么一个函数,pthread mutex trylock(),要么获取到锁,要么直接失败返回。所以我们可以去尝试一下获取别的锁,如果失败了,那么可以把自己的锁也释放掉,这样可以避免死锁。

但是在这种情况下会出现一种叫livelock活锁的东西,就是两个线程都首先获取一把锁,然后尝试去获取对方的锁,结果发现失败了,那么就释放自己的锁,不断的重复。最简单的方法就是为线程加一个随机的延时。

Mutual Exclusion

这一部分其实并不可避免,因为我们的程序必然是有critical section的。所以我们只能不加锁,那么就只剩下乐观锁这么一条路了。

通过计划避免死锁

最好能够避免死锁,而不是防止死锁。我们要做的就是根据各个线程获取锁的情况来判断。其中一个著名的算法就是银行家算法。但是这个算法大部分只有在嵌入式系统中,即知道所有任务以及知道所有的锁的情况下,才有用,所以在大型系统中,银行家算法用的并不多。

检测和恢复

最后的方法是,允许死锁偶尔出现,但是能够检测到死锁并且去处理它。

本部分没有细说怎么做,只是说数据库里用的比较多——通过构造图并且检测里面有没有回路。

总结

我们学习了一些在并发情况下会出现的问题,第一种是非死锁问题,比较容易修复。第二种就是死锁,我们可以破坏它的四个条件。

Event-based Concurrency (Advanced)

更多的并发,出现在GUI中,或者是出现在互联网的那些server中,这种称之为event-based concurrency

那么有没有办法,我们压根就不用多线程呢?只要不用多线程,这并发的问题不就解决了么?

Event Loop

思路非常简单,就是简单地等待事件发生,发生了之后你去确认下事情的类型,然后做一些工作。听上去简单,但是实现起来就没那么容易了。

系统调用——select(poll)

这个系统调用很简单,就是确认有没有传入的IO。以服务器为例子,就是检查一下有没有数据包到达,如果有的话就去进行操作。下面是select的代码:

1
2
3
4
5
int select(int nfds,
fd_set *restrict readfds,
fd_set *restrict writefds,
fd_set *restrict errorfds,
struct timeval *restrict timeout);

select会检查IO描述符的集合(就是上面的三个fd_set),来检查它们中是否有文件描述符已经准备好了。第一个数字则是用来指定数量。返回值是有多少个文件描述符已经ready了。

这个系统调用允许你检查文件描述符是否可读可写,可读相当于通知web server目前有数据包抵达了,可写则是让服务知道这已经好了。

poll系统调用和select非常像。

阻塞系统调用

如果,一个事件要求你去触发一个系统调用,而且这个系统调用可能会被阻塞呢?

一个简单的例子:客户端希望服务器去读取服务器上的文件并且返回给它,这一过程中必然有open()系统调用,然后read()系统调用。这个在多线程情况下没有所谓,但是到了这里,就会阻塞整个server了,所以在这个系统里,不能有阻塞式系统调用。

解决:异步IO

异步IO就是允许进行了IO请求之后立刻返回,并不等待结果就直接返回。一个典型的AIO的例子如下:

1
2
3
4
5
6
struct aiocb {
int aio_fildes;
off_t aio_offset;
volatile void *aio_buf;
size_t aio_nbytes;
};

这四个参数分别指定了要读取的文件标识符,要读取的偏移量,读完之后应该放到哪里,读多少个字节。

有了这个结构体,只需要进行系统调用aio_read并且把这个结构体传入即可。

那么我们怎么知道异步IO完成了呢?同样使用系统调用aio_error,同样也是传入对应的结构体,如果已经完成了那么就返回0,否则返回别的。显然如果我们要多次去确认异步IO是否完成,是很痛苦的,所以可以用信号来进行通知。

问题:State Management

在一次循环中,event handler需要打包保存程序的状态,以便接下来的event hander使用。最简单的就是使用一个hash表来记录,这样异步完成之后还能接着操作。

events还存在什么问题?

假如我们从单CPU系统扩展到了多CPU系统,那么系统会并行跑一些event handler,所以就不得不配以锁。

还有别的问题,比如缺页中断,此时操作系统不得不阻塞,那么整个系统又停下来了,虽然说了要避免显式的阻塞,但是缺页中断属于隐式阻塞。

第三个问题是,万一使用event handler处理的事务,从非阻塞变成了阻塞,你很难发现。

第四个问题是,虽然大多数系统支持异步IO,但是并不能很好的和网络IO兼容。

总结

这一部分主要是介绍了基于事件的并发,发现有很多问题,而且也不简单。


并发这一部分到这里就结束了。在这一部分,首先学习了如何创建线程,如何实现一把锁,以及如何在锁的帮助下实现一些并发的数据结构。然后通过条件变量学习了如何让一个线程等待另外一个线程,引出了经典的生产者和消费者问题。然后通过信号量,相当于串联了之前的锁和条件变量。通过实际中系统的问题引出了死锁及其解决方案,最后又拔高了一点,介绍了select这个系统调用,即不通过多线程也能完成高并发任务(虽然要求很多就是了)。