Kernel Space

January 18, 2007

编程原语之二 — 线程模型

Filed under: 编程珠玑 — agassi @ 6:10 pm

最近需要实现一个跨Linux和Windows的线程库,所以仔细研究了一下这两个平台的线程模型,收获颇丰。

 其实在实际工作中,线程的使用就跟printf一样平常。可能是以前做的东西大多数都是course project 或者根本没有想到提高效率,所以基本上没有用到多线程,所以现在才有捉襟见肘的感觉。找工作的时候看过很多多线程的东西,脑子里堆积了很多概念,但是他们到底有什么区别,各有什么特点,什么时候用却根本处于一团乱麻的状态。

首先想到的当然是UNP Vol2 这本圣典,里面专门有一个Part(包括5个章节)是介绍同步的。当然这里面的东西比较杂,包括线程同步和进程同步,POSIX和非POSIX的标准。我主要注意看的是线程同步和POSIX标准,也就是Pthread标准。同时在Windows方面,参考了一下Win32 System Programming里面关于线程同步的章节(在Windows核心编程里面好像有细致到汇编和内核的叙述,有时间一定要补上)。

言归正传,两个平台下各有一些用于同步的原语:

  • Linux (Pthread) : Mutex和Condition Variable (CV)。Semaphore不是Pthread标准的一部分,但是CV在行为上跟semaphore很相似。
  • Windows:Windows很少服从什么其它的open source的标准,这次也不例外。Windows有一套Interlocked的API用于实现一些原子操作。线程同步用到的主要有MutexEvent(当然还有Semaphore和CriticalSection,因为Pthread里面没有,所以这里略之)。这里的Event就和Pthread里面的CV很相似。

多线程模型里面最著名的就是producer-consumer模型(记得大三的时候上操作系统的时候讲过,可惜当时没有认真听,不过当时也没有什么动力去理解透彻:-))。这个模型里面重要的资源就是一个limited buffer,这个buffer空的时候consumer不能读取,buffer满的时候producer不能放入数据。

  • 单producer单consumer模型:无论是什么模型,在修改共享资源的时候都必须锁住mutex。Event或者condition variable用来通知对方一定的事件,比如:新的product放入buffer了,或者product已经被取走了;或者用于producer在buffer满时候的等待和consumer在buffer空的时候等待。最近碰到的比较典型的应用就是一个共享内存区的通信(这个是进程间同步):一块共享内存,需要一个mutex和一对Event来实现互斥访问和数据取出和放入的通知。
  • 单producer多consumer模型:多个consumer使得它们之间形成了竞争关系。当producer放入数据后,会通知(signal)consumers。有的consumer可能被唤醒了,却发现没有数据available,这个就是 spurious wakeups现象。这个现象产生的原因就是因为多个consumer同时被唤醒,而其他的consumer被唤醒后率先处理掉了所有的数据,或者producer在没有锁住mutex的情况下发送了通知。所以当consumer被唤醒后检查状态是很必须的。Pthread提供了pthread_cond_wait函数用于做到释放mutex和等待CV的原子操作,Windows在 Windows 2000/NT 以后也提供了SignalObjectAndWait 这个API来实现类似的操作。这个原子操作避免了释放了mutex后wait on CV前发生context switch,producer这时发出了通知,而consumer将错过这个signal从而错过了这次通知。
  • 多producer单consumer模型:照常还是需要一个mutex和一对Event/CV(用于当buffer空或者满的时候等待)。通常需要一个index用于协调producer之间放入data的顺序,这样保证producer不会overwrite其他放入的数据。
  • 多producer多consumer模型:由于共享资源还是一个buffer,所以一个mutex和一对Event/CV是必需的。因为producer和consumer之间都会出现竞争,所以put和get操作都需要一个index来控制buffer的顺序存和取。

除了线程模型,这些同步原语和具体的应用也有关系。比如说如果使用的不是buffer,而是一个queue,producer和consumer就不用关心index的问题。如果consumer并不是homogenous的,也就是说它们对buffer/queue里面不同的数据类型感兴趣,这个时候可能就需要使用broadcast来一次唤醒所有的consumer,让他们决定是否处理当前到来的数据。(Windows没有专门的broadcast函数,用Windows下的SetEvent/Manual-reset(MR)来实现,但是会引起unfairness,因为pthread_cond_wait保证每个waiting线程都有机会awake然后检查状态,而SetEvent/MR却不是这样,从而导致starvation。) Douglas C. Schmidt 有两篇近乎论文的讨论Pthread on Win32的文章,非常透彻:http://www.cs.wustl.edu/~schmidt/win32-cv-1.html , http://www.cs.wustl.edu/~schmidt/win32-cv-2.html

 线程的使用通常是提高程序性能的关键,也是比较容易忽略的一部分。因为基本的线程同步可以很容易实现,但是不同的实现方式涉及的fairness和serialization overhead确是不尽相同。而且线程的使用还涉及到线程的预创建,比如说线程池和Leader/Follower模式(再次奉献Schmidt的 http://deuce.doc.wustl.edu/doc/pspdfs/lf.pdf )。

竞争是残酷的,同样功能的软件拼的大多时候就是性能了,特别是企业级别的应用。线程的使用和前面提到的I/O模型都是提高整体性能的关键。深入的理解这些概念将会将你的编程水平提高到另外一个档次。

 写得比较杂,因为刚看了很多书,一时难以理出很好的条理来,以后有了新的想法(或者说“发现”)再继续补充。

Advertisements

1 Comment »

  1. I hope this will make my Open Source stocks go up so I make some money on it 🙂 http://www.trendio.fr/word.php?language=en&wordid=2012

    Comment by Snexlex — January 24, 2007 @ 9:19 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: