Portable thread-safety in C?

Purpose

I'm writing a small library for which portability is the biggest concern. It has been designed to assume only a mostly-compliant C90 (ISO/IEC 9899:1990) environment... nothing more. The set of functions provided by the library all operate (read/write) on an internal data structure. I've considered some other design alternatives, but nothing else seems feasible for what the library is trying to achieve.

Question

Are there any portable algorithms, techniques, or incantations which can be used to ensure thread-safety? I am not concerned with making the functions re-entrant. Moreover, I am not concerned with speed or (possibly) wasting resources if the algorithm/technique/incantation is portable. Ideally, I don't want to depend on any libraries (such as GNU Pth) or system-specific operations (like atomic test-and-set).

I have considered modifying Lamport's bakery algorithm, but I do not know how to alter it to work inside of the functions called by the threads instead of working in the threads themselves.

Any help is greatly appreciated.

Lamport's bakery algorithm would probably work; unfortunately, there are still practical problems with it. Specifically, many CPUs implement out-of-order memory operations: even if you've compiled your code into a perfectly correct instruction sequence, the CPU, when executing your code, may decide to reorder the instructions on the fly to achieve better performance. The only way to get around this is to use memory barriers, which are highly system- and CPU-specific.

You really only have two choices here: either (1) keep your library thread-unsafe and make your users aware of that in the documentation, or (2) use a platform-specific mutex. Option 2 can be made easier by using another library that implements mutexes for a large variety of platforms and provides you with a unified, abstract interface.

Does Lamport's algorithm also require coherent memory caches? I haven't seen the proof but it looks to me as though the current thread relies on seeing each Entering[j] as true in the period between thread j writing true to it, and thread j writing false to it. So even if the write order can be dealt with, this code might not work on for example multi-core ARM machines. Again, memory barriers or atomic CAS are needed.

Steve Jessop 2009-08-02 23:38:23

Where can I get more information on libpthread? A simple Google search seemed to turn up a bunch of junk.

Anthony Cuozzo 2009-08-02 20:02:41

You can use pthreads on Windows with pthreads-win32; see http://sourceware.org/pthreads-win32/

Adam Rosenfield 2009-08-02 20:08:34

pthreads is natively available for just about any *nix out there, and the windows implementation is at http://sourceware.org/pthreads-win32/The authoritive dpcumentation is here: http://opengroup.org/onlinepubs/007908799/xsh/pthread.h.htmlIf you go that route, it's quite easy to expose pthreads to the users of your library, which might not always be desirable

nos 2009-08-02 20:08:39

I am now considering abstracting the lock and unlock procedures and using some pre-processor macros to support a variety of different thread libraries.

Anthony Cuozzo 2009-08-02 20:13:44

That's probably the best way to do it. I just provide mutex_init(void**); mutex_lock(void*); and mutex_unlock(void *); that my project use. Stuff the implementation of those in mutex_posix.c and mutex_win32.c which naturally are conditonally compiled, providing a different implementation for something as simple as mutexes is easy provided there's a native implementation available (which there almost always is if the platform supports threading)

nos 2009-08-02 20:21:25

For that matter, as long as you don't need any fancy scheduler behaviour like priority-inversion avoidance (which I'm guessing the questioner doesn't since he's considering a form of spinlock), you don't even need a mutex to implement a critical section. A unary semaphore will do fine. There might be a C implementation out there somewhere which has threads but no primitive which can easily implement exclusion, but if so I don't want to meet it ;-)

Steve Jessop 2009-08-02 23:35:28

ansaurus

tags:

views:

answers:

Portable thread-safety in C?

related questions