队列(一)

我刚来公司的时候,我的头lch给我以及其它的几个新毕业的同学出了一道练习题:写一个FIFO队列,要求是线程安全的。后来在新项目组招人的时候,这个被我拿来当笔试题,大多数人答的还不错。

为什么说lch是神人呢?因为这个问题可难可易,可深可浅。对于科班出身的朋友,那么在学完《数据结构和算法》这门课之后,自己用C/C++或Java写一个队列不是难事儿,但是这门课一般不考虑多线程的问题。如果把多线程的问题考虑清楚了,研究结果在国外的二流杂志上发几篇paper都行。

这个题中所说的队列,总体来说可以分为bounded和unbounded的。bounded是说在插入的时候,如果满(size()=capacity),则等待,而unbounded则没有这个问题,直接插。在lch看来,这两种队列的实现方式有很大差异。

lch当时提到说这其实是apue上的例题。我刚去翻书把代码找出来了

#include <pthread.h>

struct msg {
    struct msg *m_next;
    /* ... more stuff here ... */
};
struct msg *workq;
pthread_cond_t qready = PTHREAD_COND_INITIALIZER;
pthread_mutex_t qlock = PTHREAD_MUTEX_INITIALIZER;

void
process_msg(void)
{
    struct msg *mp;

    for (;;) {
        pthread_mutex_lock(&qlock);
        while (workq == NULL)
            pthread_cond_wait(&qready, &qlock);
        mp = workq;
        workq = mp->m_next;
        pthread_mutex_unlock(&qlock);
        /* now process the message mp */
    }
}

void
enqueue_msg(struct msg *mp)
{
    pthread_mutex_lock(&qlock);
    mp->m_next = workq;
    workq = mp;
    pthread_mutex_unlock(&qlock);
    pthread_cond_signal(&qready);
}

这里强调的是条件变量的用法。有这么几个关键点:

1、标准并没有规定说pthread_cond_signal一定只唤醒一个线程

2、调用等待条件变量的时候必然是已经获取mutex的状态。因为pthread_cond_wait的实现需要原子化的释放mutex然后等待。原子化是说这中间不会发生cond signal或者别的线程获得了mutex。

2、wait外面必须是for(或while)循环。其实这个和pthread_cond_signal是怎么触发的有关。\<

3、条件判断和条件修改必须在mutex的保护中。上面例子中的"条件"是指"workq==NULL"。这里主要考虑两个问题,一是现在多核环境下,CPU cache一致性的问题,这个线程改了那个线程未必能看见。二是保证条件修改不会发生在条件测试和pthread_cond_wait之间。否则可能会陷入无限期的wait。

4、执行pthread_cond_signal的地方却有两种选择,可以在临界区外也可以在临界区里。上面的例子是在临界区之外(释放mutex)以后。这件事情非常的微妙,主要影响的是线程调度的结果。我也正在寻找这方面讲的比较清楚的文档,目前没找到。这里最强调的就是pthread_cond_signal一定是在获取mutex之后。在释放mutex之前还是之后都行。我喜欢放在释放mutex之前,让线程调度的结果更清晰可控。

5、如果pthread_cond_signal在临界区内,那么修改条件与pthread_cond_signal谁先谁后都无所谓。

6、上面的代码没有考虑pthread_cancel的问题。如果处于等待中的线程被pthread_cancel掉了,那么锁依然保持。

意思是说上面的代码其实有很多个变种,分别能达到不同的目的,就看需要用在什么样的场合。

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥