Fog Creek Software
Discussion Board




Threading/Concurrent Programming

Can anyone please recommend some good texts that teach you how to do threading properly?

I know its not simple, and I would like something more than just an explanation of threading and synchronisation primitives. I really need advice on how to approach multi-threaded programming in the best manner possible.

Any advice or recommendations greatly appreciated.

Kenshi
Friday, May 24, 2002

I can recommend two:

"Programming with Threads", Kleiman, Shah, Smaalders, Prentice-Hall, 1996

"Concurrent Programming in Java", Lea, Addison-Wesley, 1997

The first covers the POSIX standard (pthreads) and is oriented towards C/C++ in a Unix (the authors were all Sun employees) environment . The second is obviously Java specific.  However, both cover general threading topics pretty well.

About the only general advice I can offer is that threads are, at the core, really just a easier way to code up state machines, trading code that is difficult to write with code that is difficult to debug. :-)

More seriously, threads can be a big performance win in a multiprocessor environment with a suitable OS, but in a sngle processor environment it's just a coding style.     

James Montebello
Friday, May 24, 2002

>>>More seriously, threads can be a big performance win in a multiprocessor environment with a suitable OS, but in a sngle processor environment it's just a coding style.<<<

In my experience, the best use of threads is actually when you have to wait for something - a network packet, mouse message, serial point, etc. In those circumstances, using a thread for each thing you're waiting for is a LOT easier than the coding you'd have to do for the alternatives.

So I'd say it's more than just a style choice.

-Chris

Chris Tavares
Friday, May 24, 2002

Depends on the os.  I like Advanced Windows by Richter.  I think its called Programming Applications for Windows now.  Gets the job done!

The Raging /.'er
Friday, May 24, 2002

Advanced Windows by Richter is an excellent book.  Not just as it relates to threading but as an operating system overview - specific to Win32 of course.  A very good book.

Unfortunately I cannot recommend a book specific to POSIX which has the coverage and clear wording of Richter's book.

Also, you'll find some advantages to programming in Win32 that you won't find in POSIX:  the heap kernel object, binary semaphores, and signalled events (called conditionals in POSIX)  which don't get dropped.

Unfortunately, life in Windows land always involves some "greater plan" and the beauty and elegance of the Win32 kernel gets lost.  It is quite simply, at its core, elegant. 

Good luck.

Nat Ersoz
Saturday, May 25, 2002

Oh, one other thing.  Stevens wrote a very nice set of TCP/IP illustrated books and I was hoping that his books related to Posix programming would be equally  useful.  Unffortunately, I found them to be almost useless.  The examples are simplistic, caveats are almost never mentioned, and he introduces very simple minded wrapper based examples which detract from the subject matter.  It was a huge dissappointment to encounter this.  Too bad.

Nat Ersoz
Saturday, May 25, 2002

Threads do not make it easier to wait on events. They make it seem easier initially (which is why this is a common belief), but sooner or later you'll find that the amount of bookkeeping you need for robust operations makes non-threaded asynchronous code significantly more attractive.

For example, if your thread is read blocking on a socket, then in some Unix variants, you have NO way to abort that block - closing the socket is not enough, and if the other side is also down (and hence no data will release the block), a "kill -9" is the only choice.

You also must not hold any lock while blocking (if you want to use the CPU to the maximum and not make the program unresponsive) -- which is a bit of a problem, because e.g., a buffer you read into during the blocking call should not be read or modified (for which a lock is the easiest solution).

Threads have their place, but 99% of the uses I've seen make the program either significantly more complex or significantly less robust than a comparable asynchronous design. A rule of the thumb - the number of synchronization primitive instances (locks, semaphores, etc.) should be bounded a-priori, independent of the input data, while at the same time, lock contention should be virtually nonexistent.

(And if you really know what you're doing, you can avoid all locks with a compare-exchange operation, thus ensuring no deadlock and no unresponsive program under any circumstance. But for that you REALLY have to know what you're doing).

Ori Berger
Saturday, May 25, 2002

http://www.oreilly.com/catalog/multithread/

I did read another in borders which was good but can't recall the publisher now. The O'Reilly book gives some good practical descriptions as well as covering the win32 specific stuff.

Tony E
Saturday, May 25, 2002

Threads are neither difficult nor magic.  In fact, they should simplify your code.  If they are not making the code simpler, then you probably did not need more than one thread (in user space, there is always at least one thread).

First, if you're going to read from a file/socket/device, then you'll need to get familiar with either the select() function (and friends), or signals.

Using the select() function is easier and more commonly used (I think).  The most common usage is to use it as a polling function.  Also, the ioctl( FIONREAD ) is very useful. It allows you do determine how much data is available for reading.  This is particularly useful when reading a UDP socket, and you need to know how much data is waiting in the next datagram.

Signals can be used if you want to avoid a polling loop (there is little detriment to polling, however, a purist might want to avoid any cpu cycles when data is not available).  So if you either want to enter the read() function (non-blocking) without the use of select, then you can use the function pthread_kill() (which has a silly name  because you have no intention for killing anything, but its what you want).  If all you want to do is exit a blocking call (like select, read, write, ioctl), then you just need pthread_kill() and an associated signal handler which does almost nothing (see sigaction() for signal handling).

If you want to notify one thread that another thread has done something useful, then use a semaphore.  They are reliable, whereas conditionals are not (if you are not waiting on the conditional when the conditional is signalled, you'll miss it - very bad).  The semaphore itself can be used as a locking mechanism if you like (typical single producer, single consumer problem).  For multiple consumers or consumers that consume at a rate different than the producer, or handling badly behaved devices in the consumer, you may need to add mutex locks to your shared memory areas.  This is not a big deal.

One place you will have to be careful is in guaranteeing thread safe performance among multi-threaded interfaces.  Suppose, I have object A and object B.  Both A and B are designed to be threadsafe (they are designed to handle asynch calls from multiple threads).  Often, this may be as simple as guarding entry and exit points to the interface calls with mutexes.  This will ensure that internal data structure changes are only changed by one thread at a time.  Now suppose A calls B for a request, and then B, needs to get information from A to satisfy that request.  Well suppose that A locks all his data down when B calls, and then B locks all his data down when  A calls.  Now nobody goes anywhere - deadlock.  It is a classic case for deadlocks and you need to be aware of the potential.  One key is to lock only what needs to be locked within A and B within a specific calling context.  Sometimes, getting the thread id for the call may be useful too.

It is a disservice to obfuscate what should be a simple tool in every software engineer's toolkit.  No wonder people dummy down to Visual Basic.

>> Threads do not make it easier to wait on events.
This is incorrect.  Every user space wait on an event, semaphore, blocking call, or signal is done within a thread context.

>> For example, if your thread is read blocking on a socket,
>> then in some Unix variants, you have NO way to abort that block.
I am not aware of any Unix variant which does not allow the use of SIGUSR1, SIGUSR2, SIGIO, or other signals for use as a handled signal.  Additionally, all real-time signals can be used (usually there are 32 of them) for handling device driver communcation to and from user space code.

Side note:  realtime signals queue up as opposed to non-RT signals, which get dropped when one signal is already pending of the same number.  So you can drop non-RT signals when you don't handle them fast enough.

>> You also must not hold any lock while blocking
This is untrue.  A typical read from a file/device/socket looks like this:

select();
mutex_lock();
read();
mutex_unlock();

OR, if you don't like selet(), use a signal when necesary to free the read().

>> Threads have their place,
Every time the CPU program counter moves in user space code its within a thread context.  Got main()?  Got threads.

>> but 99% of the uses I've seen make the program either significantly more complex or significantly less robust than a comparable asynchronous design.

I'm not sure what Ori is driving at, but any user space event which occurs that is asynchronous comes from another running thread context.  There is no other way to be asynchronous in user mode.  Ah, but someone says "what about signals?"  Yes, a signal is asynchronous in its timing but the thread context of your signal handler will be within your running thread which got signalled.  Also, the signal had to come from somewhere - either the kernel or another thread (if that last part about signals is confusing, forget it, I'm being pedantic).

Learn to use threads and other kernel objects that are either part of the POSIX or Win32 system programming environment.  To ignore a useful tool like threading is to place yourself in a very limited box.  Again, the Richter book is a very good place to start, even if you're not a Win32 fan.

Nat Ersoz
Saturday, May 25, 2002

<<  <Threads do not make it easier to wait on events.>
This is incorrect. Every user space wait on an event, semaphore, blocking call, or signal is done within a thread context.
>>

I meant "events" in the English language sense of the word. When you're waiting on a keypress, you almost never do it in a thread context. User space waits on events _in Win32_, are indeed always within a thread context - but that is not universally true (BSD's kqueue is an event notification service which is not thread context sensitive in the same sense).

<<  I am not aware of any Unix variant which does not allow the use of SIGUSR1, SIGUSR2, SIGIO, or other signals for use as a handled signal. Additionally, all real-time signals can be used (usually there are 32 of them) for handling device driver communcation to and from user space code. >>

Except that you can't decide which thread gets the signal. If you had 1000 threads all blocking on input, and wanted to cancel a specific one (pulling it out of blocking by way of EINTR or something), you can't reliably deliever it to the thread you want. It was ages ago when I had this problem, and I don't recall what OS it was (Perhaps Ultrix? I'm not sure). Modern unixes are much better behaved in this respect, but signals are still basically a process-wide rather than thread-local concept.

<< <You also must not hold any lock while blocking>
This is untrue. A typical read from a file/device/socket looks like this:
>>

okay, I admit "must" is a bit too strong, but the example you gave (select/lock/read/unlock) is perhaps the only safe way to do that, and it is seldom if ever practiced - that's what I mean when I say 99% of programs do things wrong. Pick an arbitrary source code that does threaded sockets NOT written by yourself - my experience is that at most one in twenty implementations would actually make sure a lock is not held while waiting for an external event. [And there are many other evils, in case you wonder why it isn't 95%].

One of the reasons select/lock/read/unlock is seldom practiced is abstraction - suppose you're using socket wrapped into an iostream, rather than sockets directly - this is a very common case. Now, regardless of how the stream internally blocks, you can "select" on an istream, so you have the choice of either holding a lock while waiting for data (bad), or reading into temporaries, and locking/applying/unlocking only when you can do something "atomic" (with respect to external events). Again, my experience is that the former is much popular, and as a result programs are much less robust.

<<  Every time the CPU program counter moves in user space code its within a thread context. Got main()? Got threads. >>
Let's not get lawyer-legal, ok? The fact that there's an object somewhere in the operating system called "ThreadContext" or "PTCB" is not relevant - multithreaded programming in most cases (and I take this discussion to be one of them) refers to a case in which there are several independent instances of the program executing at (effectively) the same time, and having identical access rights to each other's data. This definition DOES rule out cooperative multitasking. Multiple processes are not, in general, covered by this definition (they have separate protected address spaces), but are included once shared memory is used.

<< I'm not sure what Ori is driving at, but any user space event which occurs that is asynchronous comes from another running thread context. There is no other way to be asynchronous in user mode>>
It may be coming from another process (which, technically is another running thread context, but this is irrelevant). The problem with multiple threads in the same process is synchronization, and it goes away if the processes (technically, thread contexts) do not share any data.

And select()/WaitForMultipleObjects()/GetMessage() provide a very convinient asynchronous working regime - you wait till anything happens (possibly several things "at once") in a central location, handle everything you can, and go back to waiting at the same central location. The name may not be perfect, but this is what is generally called "asynchronous mode" - as opposed to syncrhonous mode in which you wait  for specific occurences at each different position in the program.

<<  Learn to use threads and other kernel objects that are either part of the POSIX or Win32 system programming environment. To ignore a useful tool like threading is to place yourself in a very limited box. Again, the Richter book is a very good place to start, even if you're not a Win32 fan >>

Couldn't have been better said. I must add, though, that most uses of threads one encounters _in practice_ actually make systems less robust, less responsive, less efficient and more complex.

[continued below]

Ori Berger
Saturday, May 25, 2002

Back in 1988 or so,  the most common GUIs on PCs were text mode, and almost none of them was asynchronous (or even event driven) in nature. A program would usually present a question like
"" Please type in your age in microfortnights"", and the code behind it would look something like
age = get_number("age in microfortnights");
(or more commonly, INPUT "age in microfortnights", AGE ....)

Want help (e.g., what the hell is a microfortnight)? tough luck, get_number didn't support it. Want to cancel? Tough luck again, get_number can only return numbers, not cancel. If get_number was really well written, it might return an error code ("help requested" or something to that effect) - but it required checking and handling appropriately in every place.

GUIs were working, but not intuitive, not really responsive, and extremely intolerant of non-expert users (often, no "back" or "cancel" option was coded, or was only available at very specific points in the path). Then came event driven systems like TurboVision, and Win3.0 became popular - and suddenly, everything started to behave "properly", even though there were no threads in sight.

The reason event driven systems are so much better at handling GUIs is that humans don't like to follow any well-defined interaction path. And that is also the case for any external event, such as a network connection. Like a user pressing 'F1' at any moment, a network connection can break or stall at any moment, or start feeding trash at any moment (bug at other side, or connection hijack). Contrary to common belief and most testing scenarios, these things do happen.

What I'm driving at is this: Look at your last non-Java GUI (Win32, MFC, FLTK or Visual Basic are fine examples). Did the GUI have multiple windows? Most probably yes. Did it have multiple threads? Most probably not (GUI part only, guys). Why is that? Because most mouse clicks or text entry items are handled quickly enough as atomic events. Even if you do have, e.g., one thread per  "toplevel" window, you don't have one for every control - the same thread multiplexes input from 20 input fields, and eventually (upon pressing the "submit" button or equivalent), handles it atomically. That's the simplest way there is; there is no competition for resources requiring fragile[1] synchronization.

Question: Why should socket input be different? Why should the program ever block on anything externally driven, if it doesn't do it for GUI input? There are a few constraints, e.g., gethostbyname() has no non-blocking alternative on Unixes - but this is the exception rather than the rule.

Asynchronous GUIs are responsive and better adapted to deal with human input. Asynchronous network processes are more robust and better adapted to deal with network failures and stalls. Asynchonous disk processes are usually not needed because disks are at the same time significantly faster and significantly less error prone than networks - but still, if you want to maximize performance, are essential.

To ignore a tool like threading is placing yourself in a smaller box than you should. But threads are highly overrated and misunderstood. Don't use threads unless you know how to achieve the same results without them (always possible) - and only once you do, evaluate which solution is simpler. Eventually, I usually find that a (conceptually) single threaded event driven structure works best, but it sometimes needs a bounded number of support threads in order to align all systems with the asynch regime.

[1] By fragile syncrhonization I mean e.g. the example Nat gave, of two objects each of which is thread-safe in its own right, but which are not thread-safe if used together. The contracts in such cases must carry implementation details about lock dependency, which goes against [almost] everything OO stands for.

Ori Berger
Saturday, May 25, 2002

Ori is right... Threads are for one thing and one thing only - running CPU-intensive code asynchronously (either via time slicing or on another CPU), and only when the code really needs to share all of its memory with other threads.

However, I can excuse people who use threads for waiting on things when a good non-blocking I/O API is not available. (e.g. anonymous pipes on Win32, or disk I/O on UNIXes that do not support POSIX aio).

I can also excuse the use of threads for independent parallel computations on operating systems that make it difficult to use separate processes (Win32).

Dan Maas
Saturday, May 25, 2002

I don't know if Ori is right or not, when does 'Ori in a
nutshell' come out?  Just kidding!

I always create a seperate thread for each window in my
gui apps.  Each window gets his own message pump.  He
like it that way! 

The Raging /.'er
Saturday, May 25, 2002

>> Except that you can't decide which thread gets the signal. If you had 1000 threads all blocking on input,...

Partly yes, and partly no.  Partly yes, I agree:
It is unfortunate that signals are so screwed up in this way - that what the Sys V and ANSI API specifies you signal are processes not threads, yet in every sense of the word, what you are signalling is a thread and what is blocking is a thread, so how did this get so screwed up?  Obviously, threads were (almost) non-existent prior to Win32 and POSIX standards:  only one thread ran per process.

It is also unfortunte that ANSI C decided to even include the <signal.h> header file within the standard, as it only serves to confuse, and so brain dead as to be useless (within the ANSI C landscape, not POSIX).

OK, now the no part:
POSIX supplies the library call pthread_kill() which does allow you to signal a specific thread.  This is certainly the most portable method.  Additionally, other UNIX variants saw the stupidity of signalling processes vs. threads and provide a non-portable method for doing so:
1. LynxOS provides a macro which allows you to pass in process id (pid) and thread id (tid) to all signalling functions so that it can be done right (specifically, this is important for real-time signals).
2. Linux does something very nice (IMO) in that it nukes the notion of process being a group of threads.  Each thread has a pid, which can be signalled individually.  This works very well in practice and I'm guessing is the future of POSIX.
3. These OS specific variants are really outside the scope of dealing with POSIX threads as discussed so far.  What they really overcome is the usage of threads taking signals for real-time signals - which is the only place where pthread_kill() is not specified to work.  For waking up a blocking read for example, real-time signals provide no advantage, and the price paid for non-portable code is wasted.

My Conclusion: 
1. Signals are not necessary in the socket read example, as select() gets the job done.
2. If you want signals, then portable code should dictate using pthread_kill().
3. If portability is not a requirement, you can use OS specific signal  variants - typically when using real-time signals are a necessity.

>> suppose you're using socket wrapped into an iostream, rather than sockets directly... so you have the choice of either holding a lock while waiting for data (bad),..

Iostreams are not multithreaded animals.  Associated with every istream or ostream (or derivative) is a streambuf derivative.  Even non-buffered IO involves an associated streambuf.  When data is pulled from an istream it is taken from streambuf's char buffer.  When that buffer is empty, the virtual function virtual int streambuf::underflow( void ) is called.  underflow() initiates all reads from the data device - in this case a socket.

Therefore, 1. iostreams never operate asynchronously, they read as a result of client "getfrom" operations. 2. They cannot be rewritten as multithreaded classes based on the iostream.h class declarations.  There are no virtual methods for the pull side of the operation (gptr(), ppptr(), sgetc, sgetn, ...) - these would have to be re-written as having locking mechanisms - but they are non-virtual.

But, going back to an ealier statement you made:  "(select/lock/read/unlock) is perhaps the only safe way to do that, and it is seldom if ever practiced - that's what I mean when I say 99% of programs do things wrong. Pick an arbitrary source code that does threaded sockets NOT written by yourself"

If its my responsibility to implement or debug a feature, and if existing code is broken, then I'll fix it.  I already know from past projects that I can make this work properly, and I'll write an educated estimate and make it work.  Broken code is meant to be fixed.

Something is done poorly by others does not constitute a crisis on my behalf.  Example:  COM is often poorly implemented by many programmers.  Does that mean I shoud not use COM?

>> And select()/WaitForMultipleObjects()/GetMessage() provide a very convinient asynchronous working regime...

This is merely blocking on events in one thread while waiting for other threads to do their job.  Even GetMessage(), which is a Windows messaging API call is a call into a Win32 message queue generated by a different thread.  This is multithreaded programming, nothing more, nothing less.  The only exception I know of would be if the GetMessage() call were the Win16 version.  In that case, the entire OS is all one big ugly thread - hopefully we can ignore that.

>> Win3.0 became popular - and suddenly, everything started to behave "properly", even though there were no threads in sight.,

Whoops, doesn't look like you'll let me ignore that.  First allow me to object ot the notion that "everything behaved properly".  Win16 crashed, crashed and crahed again.  Daily, hourly, by the minute.  One reason:  The entire OS, your program, and everyone else's program were all running from the same thread.  One thread, that was it.  When you called "Yield" or what was it, PeekMessage()?, you indicated to Win16 that it could now break from the monster case statement and run this one thread over there in Joe's program for a while, or maybe draw a graphic or update its page tables (whoops, sorry, no page tables).  If anything, Win16 should be the poster-boy for "why everything should not be single-threaded".

GUI's and single threading vs. multithreading.  Use what makes the most sense.  As you say, and I agree, don't add arbitrary complexity to something that doesn't require it - or may not be worth the cost.  If single threading works, use it.

However, to say that it is always possible to acheive the same results with a single thread vs. multi thread would be:
1. Like expecting a single threaded window OS (Win16) to work as well as a multithreaded OS (and window manager) like Win32.
2. Like saying I don't need virtual memory, I can acheive anything I want with a flat, unprotected address space.

There are excellent and almost unavoidable reaons for using multithreading:
1. The thread (like reading a socket) must run at real-time priority, lest data be dropped (in POSIX see <sched.h> sched_setscheduler()).
2. The thread "producing" data must buffer the data uninterrupted (lest there be loss) while the thread consuming the data is slow to respond due to high computational requirements (which is the rule in video decoders).  Note that on average, they must produce and consume at the same average rate, but in the instant, the producer (i.e. socket reader) must be given priority lest data be dropped.
3. The life support machine must maintain constant blood gases, even though the technician decided to select a menu item.
etc.

Nat Ersoz
Sunday, May 26, 2002

I agree with most of what you state, Nat, except possibly the following:

The reason win16 crashed often was mostly that everything was _shared_. The fact that multithreading/multiprocessing was cooperative had little to do with the crashes. It did mean, however, that code not Yield()ing often enough could hang other processes.

And real time threads MIGHT be reason enough to use threads in some cases, but so long as the entire O/S isn't real-time, it only reduces the probability of data loss (in the examples you gave), but does not eliminate it. You have no way to insure in user mode that kernel objects (e.g., semaphores, file objects) are paged-in. With some work you can make sure some memory is paged in, but if you want absolutely zero probability of lag, you need a different style of O/S.

In a sense, expecting single threading to be sufficient is like expecting Win16 to work as well as Win32 (assuming Win16 had address space separation) - which is probably a bad idea. But there's a difference -  one application on an O/S cannot control how other applications abuse the CPU or other aspects of the co-operative paradigm. Inside an application, it is usually possible to balance all things inside - except perhaps incompatibly designed external components you are forced to use (e.g., gethostbyname()).

And actually, while virtual memory is sometimes a godsend, it is - much like threads - overrated and misused very often. I've had a chance to speed a program 1000-fold (yes, that's three orders of magnitude) by changing loop order from something like
for (i = 0; i < LRG_NUMBER; ++i)
... for(j = 0; j < LRG_NUMBER; ++j)
...... process(data[i][j]);
into:
for (ex_i = 0; ex_i < LRG_NUMBER; ex_i += SML_NUMBER)
.for (ex_j = 0; ex_j < LRG_NUMBER; ex_j += SML_NUMBER)
..for(in_i = 0; in_i < SML_NUMBER; ++in_i)
...for(in_j = 0; in_j < SML_NUMBER; ++in_j)
.....process(data[ex_i+in_i][ex_j+in_j]);

Because the original author didn't take the effects of virtual memory into account; And once this substitution is made, virrtual memory is in fact much less useful because block-structured disk files could have been just as easily and just as efficiently prefetching and caching.

But I agree that in general, under the assumption that physical memory is sufficient to support the locality-in-time of memory access used by the program, virtual memory is extremely useful.

Apart from that - well said. One shouldn't avoid a tool just because it is mostly misused. But one should be wary that this the common practice is bad when learning how to use the new tool.

/.: Sorry, I'm too big to fit in a nut shell :). In what way does the per-window message pump affect the way your program is written or responds?

Ori Berger
Sunday, May 26, 2002

A per-window message thread will do two things: 1) slow your program down, because of the extra thread switch to handle an event, and 2) create hard-to-find bugs when one event handler pre-empts another at an unexpected time...

It reminds me of the BeOS users who believed the hype that "BeOS was fast because every window was a separate thread." This is wrong - BeOS was fast because the developers worked hard to reduce latency for common operations, and ran many tasks asynchronously. (note: asynchrony doesn't necessarily require multithreading...)

Dan Maas
Sunday, May 26, 2002

Dan my users never have noticed the slow-down! ;)
Actually, I havne't done much gui programming.  I try to stay on the server side.  But this is a plugin architecture where those dlls need to process messages.  Each dll gets to do its own thing and the main program never knows.  Just easier that way, at least for me!  Would there have been a better way?

The Raging /.'er
Sunday, May 26, 2002

>> You have no way to insure in user mode that kernel objects (e.g., semaphores, file objects) are paged-in. With some work you can make sure some memory is paged in, but if you want absolutely zero probability of lag, you need a different style of O/S.

Actually, mlock(), and munlock() work very nicely in Linux (I've not tried these in other OS's - but it is a POSIX call).

FWIW,
My favorite on line man page place:
http://www.opengroup.org/onlinepubs/007908799/xsh/mlock.html

Also, in Linux, real-time threads and mlock() require super user privs - which make some sense - you don't want to allow users to promote themselves to realtime on a whim.  However, I think having a group would be a better idea.

More later... Gonna go see Spiderman...

Nat Ersoz
Sunday, May 26, 2002

>> A per-window message thread will do two things: 1) slow your program down, because of the extra thread switch to handle an event, and 2) create hard-to-find bugs when one event handler pre-empts another at an unexpected time...

First, some context switching benchmark results pages:

http://www.atnf.csiro.au/people/rgooch/benchmarks/linux-scheduler.html
http://www.geocrawler.com/archives/3/35/1998/4/50/98906/
http://cs.nmu.edu/~benchmark/index.php?page=context

Context switches are on the order of 2-20 uS, depending on # of threads, memory usage, and what is being handled

Next, with respect to user interfaces, most of the time no threads are running, they are blocked waiting on user input.  Games or complex graphics would be the marked exception to this.  However, for a typical GUI which involves some widgets & menus, the OS is reacting only when the user acts - and as measured in computational time, it is not often.  Adding a few uS as compared to user input is insignificant.

So, if adding threads makes life easier, then by all means do it.  If maintaining a single threaded display manager was advantageous from a performance standpoint, then WinNT would have migrated to the Win9x display manager - not the other way around.  Having all device contexts wait while one window renders ray tracing is not a good design choice.

Making blanket and obtuse statements about UI threading only leads others to "design by urban lengend".  You hear things like "you can't use new and malloc in the same code", or "C runs faster than C++".  Software engirneering is nothing but specifics.  Each implementation suited and designed for a specific application.  Do not allow someone else's generalizations cloud your vision.

PS - Spiderman was lame.

Nat Ersoz
Monday, May 27, 2002

When I studied the course "Structure of Operating System" in the Electrical Engineering Department of the Technion, we covered the issues involved with Threading for some time. We were told Tannenbaum's Minix book covered them well, but I managed to get along with just the free course material.

In any case, I refer you to the following resources:

Guy Keren's Lectures about Threads for the Haifa Linux Club:

http://linuxclub.il.eu.org/lectures3.html

His POSIX Threads' Tutorial:

http://users.actcom.co.il/~choo/lupg/tutorials/multi-thread/multi-thread.html

And then, of course, Google, Google Groups, and what the other esteemed members of this forum said. What is important to remember when designing multi-threaded programs is to actually _design_ them: "prove" to yourself that they are correct and there are no deadlocks, starvations or race conditions. It's not simple, but it's one of the most challenging CS task out there.

Shlomi Fish
Saturday, June 01, 2002

Re: the following extract

If you want to notify one thread that another thread has done something useful, then use a semaphore. They are reliable, whereas conditionals are not (if you are not waiting on the conditional when the conditional is signalled, you'll miss it - very bad).
  -- Nat Ersoz Saturday, May 25, 2002


When you refer to "conditionals" you must be talking about something other than condition variables, because condition variables are quite reliable.  Perhaps you are thinking of the novice's first attempt at cv's:

  /* Producer */
  pthread_cond_signal(&cv);

  /* Consumer */
  pthread_mutex_lock(&mutex);
  pthread_cond_wait(&cv, &mutex);
  /* Incorrectly assume everything's ok. */

(You're possibly even wondering why on earth the mutex is needed at all). The correct use of condition variables is as follows:

  int ready = 0;

  /* Producer */
  pthread_mutex_lock(&mutex);
  ready = 1;
  pthread_cond_signal(&cv);
  pthread_mutex_unlock(&mutex);

  /* Consumer */
  pthread_mutex_lock(&mutex);
  while (!ready)
    pthread_cond_wait(&cv, &mutex);
  /* Now everything's ok. */

The mutex is automatically released on entry to pthread_cond_wait and re-acquired on exit. This is done to release the protection needed between data shared between the producer and the consumer. More importantly, it is done atomically inside the wait as there would be no way to avoid a race condition otherwise.

The condition needn't be a simple boolean variable.  It could test any number of conditions.  The condition variable, being stateless, is nothing more than a "bed" to sleep in while waiting for an arbitrarily complex condition to be satisfied.

Producers wishing to notify consumers of an event don't even have to be certain that the condition is fully satisfied. The producer could simply be concerned with one component, and signals the cv whenever something has happened that _might_ result in the condition being satisfied. So the signal is just a "wake up call" to tell waiters to check their conditions again. Even the pthreads implementation itself is allowed to spuriously wake up threads, rendering the original naive implementation completely useless (not just error prone).

Marcelo Cantos
Wednesday, June 05, 2002

I appreciate the help!

However, I'm confused about one thing:  suppose the consumer hits the mutex_lock() before the producer does.  Now, isn't ready blocked from being written to as the consumer waits in a while() loop?

Thanks,

Nat Ersoz
Wednesday, June 05, 2002

Oh ,sorry - never mind - it has been so long since I've used conditionals (I pretty much abandoned them).

OK, from the man page:

"atomically release mutex and cause the calling thread to block on the condition variable "

the wait releases the mutext atomically - so all is well.

Thanks for the note - I'm back in business!

Nat Ersoz
Wednesday, June 05, 2002

Which just goes to show you, that just because I don't know what I'm doing didn't cause him to have a personal crisis...

Nat Ersoz
Wednesday, June 05, 2002

After 19 years of coding for money I have come to respect the KISS principle. Keep It Simple Stupid (or Smarty). I am always on the lookout for over complication - it simply leads to bugs if not now then sometime down the road when other people (invariably) muck around with the code. So I always counsel my protoges to avoid complexity and don't assume what code needs to be optimized until the system is complete - that is the time to profile and optimize where necessary to acheive performance or other resource requirements - if there is time to do so before the release. Too many coders waste time crafting the "word processor in a single line" - high performance and inscrutable code - too bad it almost always doesn't need to be either one.
So what about threads? Use them only when necessary even if *you* are an expert because the next guy probably won't be. I like to use messages with "process to completion" i.e. single thread - one message at a time. - wherever the performance hit allows. I like to avoid function calls across threads since which requires thread synchronization because this is an extremely common source of bugs. Of course sometimes it is unavoidable - especially in driver design. Maintainability is paramount. In these days of GigaHertz and Gigabytes one now often has the luxury of slower and bigger but more maintainable code. Optimization for both speed and size is often unnecessary now - even in the embedded world.

Peter McKinnon
Thursday, June 06, 2002

*  Recent Topics

*  Fog Creek Home