Fog Creek Software
Discussion Board




Multi-threading resources?


I’m an experienced developer and I understand the basics of multi-threaded programming, but I don’t feel confident that I understand all the implications of writing multi-threaded code.  Can anyone recommend books or resources that discuss multi-threading?  I know what a mutex is, why you need to use lock on some variables and I have a basic understanding of the Pulse (C#) and Notify (Java) methods.  But I don’t feel confident writing or reviewing code that will be accessed by multiple threads. 

I haven’t needed multiple threads in my applications so far, but as I’m a consultant to lots of different projects I feel I should understand multi-threading better than I do.

Ted Graham
Monday, September 29, 2003

In my experience, the best first step to multithreading is to write your code to be completely independent. In other words, give it the capability to run as an independent .exe.

That will make multithreading practically painless in .Net - you avoid concurrency, contention, racing, etc, etc.

Of course, this isn't always possible. But treat "breaking the thread walls" like denomalization - you do it if you have to, but avoid it if at all possible.

Incidentally, it also makes testing and debugging easier, since you just throw the class you plan to thread in a winform or test harness and you can beat on it all you like.

Just a broad philosophical comment; not sure how much it helps.

Philo

Philo
Monday, September 29, 2003

Ted,

Please see the link below for a free online chapter from my recent book. It deals with understanding the most important problems involved with multi-threading, and how to avoid (and debug) these problems in .NET.

HTH,

Mark
----
Author of "Comprehensive VB .NET Debugging"
http://www.apress.com/book/bookDisplay.html?bID=128

Mark Pearce
Monday, September 29, 2003

Doug Lea has a great book[1] on concurrent programming in Java.  It is a must read for anybody seriously interested in the subject. 

Also, Doug's home page[2] has some great libraries that help with concurrency and a bunch of other goodies.  He is a big contributor to JSR-166 (An extension to Java which will provide better tools for concurrency).


[1] http://www.amazon.com/exec/obidos/tg/detail/-/0201310090/qid=1064848141/sr=8-1/ref=sr_8_1/002-2486754-2758468?v=glance&s=books&n=507846

[2] http://gee.cs.oswego.edu/dl/

Joe Blandy
Monday, September 29, 2003

The main thing to keep uppermost in mind in writing a multi-threaded application is that statements in each thread will run interleaved with statements being executed in other threads. IE, in between any two  statements in thread A, one or more statements of thread B may execute. And actually, thread B may preempt thread A in the middle of one statement. And all such threads can share the same variables. That's what "multithreaded" means.

Therefore, if two or more threads try to make concurrent write access to the same shared variables, the shared variable may be corrupted, left in an inconsistent state, or read incorrectly.  This is particularly true if the shared variable is complex, consisting or more than one primitive data type.  Mutexes, semaphores, and critical sections are ways of guarding accesses to shared variables or resources that fit this description.

The "best" reason for multithreading is functional: an API blocks when called, but the user interface that needs to interact with the API needs to be kept updated in real time, for one common example.

The worst reason to implement multithreading is because the designer is trying to appear "cool" and have an undue amount of complexity built into the program. Each thread is a drag on the overall performance of the processor. 

IE: if there is no "influence" outside the program for any thread to block on, then there is probably no good reason to have multiple threads.

Bored Bystander
Monday, September 29, 2003

"The main thing to keep uppermost in mind in writing a multi-threaded application is that statements in each thread will run interleaved with statements being executed in other threads."

You may be doing yourself a disservice. Thinking of it this way may lead you to believe that this:

foo += 12;

is atomic, when it's not. The interrupt happens between INSTRUCTIONS (i.e., assembler instructions), not between STATEMENTS (i.e., lines of high level source code).

Brad Wilson (dotnetguy.techieswithcats.com)
Monday, September 29, 2003

Er, Cat guy Brad: I said...

>> And actually, thread B may preempt thread A in the middle of one statement.

Yes, I was quite aware of that... good point worth emphasizing, tho.

Bored Bystander
Monday, September 29, 2003

Jeffery Richter, "Advanced Windows Programming" 2nd Edition is the one I have (The newest edition is "Advanced Windows, 3rd Edition). Excellent book.  Covers Win32 Thread Syncrohization plus a whole lot of other Win32 techniques.

MikeG
Monday, September 29, 2003

There are several reasons you might want to multithread (I'm speaking in relation to other posts rather than relating to your question, which itself is more of a "when I've decided to multi-thread, what then?")

-Where certain calls are blocking - perhaps it's a library/system call that only has synchronous blocking calls - and during the interval of execution you'd like the application to be able to do other things (which might be simply to kill the busy thread if the user decides to)

-Where you want to take advantage of multiple processors in a single application.  A single thread will use only a single processor at one time.

-Where it simplifies the design of the application. While many are fearful of multithreading, once you've got a grasp of it, it often can greatly simplify your design (rather than having state logic or boolean checks all over the place for various conditions and branching, each condition has a thread that is sitting on a wait event for a condition to occur. The resource required for this is very close to 0 and is a non-factor).

Jimmy Chonga
Monday, September 29, 2003

>>Where it simplifies the design of the application. While many are fearful of multithreading, once you've got a grasp of it, it often can greatly simplify your design

Good point. One way to do this is to get more "fibre" in your diet. :-)

In straight Win32 programming, the OS has available a different multiprocessing concept called a "fibre". A fibre is a subdivision of a thread. Multiple fibres in a given thread can be treated by the developer as concurrent processes but they actually execute as "coroutines". IE, they do not prempt or timeslice each other, rather they hand control to each other in a programmer-controlled way at discrete OS calls. So a fibre based application isn't subject to the premption hassles and need for critical sections that a threaded design is.

I don't know if C# or Java has a feature like this available, but when you need it it's handy. And new fibre creation is even lower overhead than thread creation.

Bored Bystander
Monday, September 29, 2003

Threads are for people who don't understand state machines. Often, a better solution is to write an event queue for asynchronous events.

runtime
Monday, September 29, 2003

State machines are for people who don't understand threads.

Jimmy Chonga
Monday, September 29, 2003

The following are all quite old, but still very useful in understanding the concepts

"Principles of Concurrent and Distributed Programming", M Ben-Ari
"Communicating Sequential Processes", CAR Hoare (The paper, not the later book, which is very heavy going)
"Co-operating Sequential Processes", online at: http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF

as
Monday, September 29, 2003

State machine vs. threads debate: I've witnessed a couple of really poor threaded designs over the years that were owing to the developer believing that a thread was the only way to implement what was really a state machine. So you'd see several threads aka state machines basically doing busy work or polling most of the time and introducing interactions into the software that had nothing to do with the state machine logic.

State machines implemented as ordinary variables sound lame and boring to some people...so they use threads instead, which really don't fit the problem being solved, but threads sound like "cool little programs" to some people who use them believing that they are simplifying their task... when they're not simplifying anything at all.

Whereas a state machine "folds" a multistep procedure in a way that superficially *seems* hard to understand and design. What I find is that designing a state machine tests my understanding of the problem. If I can't design the state machine, then I don't really understand what is going on...

Bored Bystander
Monday, September 29, 2003

ah yes, runtime...threads are for people who don't understand a finite state machine.  Care to explain how a  state machine will take advantage of a multiprocessor machine?

Vince
Monday, September 29, 2003

And one more piece of advice: when you write your first system using multiple threads, don't make the newbie mistake of thinking that tossing in another thread will solve whatever problem you have.

Another thread will *appear* to solve your problem, but before (or soon after) you release you'll discover it didn't do what you want.

Exception guy
Monday, September 29, 2003

In general, the easiest way to take advantage of multiple processors is to just launch more processes.

It's not as sexy as writing a multithreaded application, but it's a hell of a lot simpler and less dangerous, and is applicable to the majority of cases.

Sometimes you really do need threads, but that should be a last resort (and unfortunately the design of the win32 API means you have to sometimes go that way earlier than you otherwise would like).

Sum Dum Gai
Monday, September 29, 2003

No, cross-process communication is a lot more complex (and slower). Threads can share memory, but data across processes needs to be marshalled.

Pepe LePieu
Monday, September 29, 2003

Every O/S worth its salt (and some that don't) have shared memory.

Explicitly stating what is shared is usually better than implicitly sharing everything and hoping you remember to lock everything which might be used accross threads.

Ori Berger
Tuesday, September 30, 2003

That your memory is protected is the benefit of seperate processes, not the drawback.

Programming with threads is like programming on an OS without memory protection - you can touch stuff that you have no rights to touch all to easily.

Sure, having no memory protection between processes makes some things easier, and more efficient, but that doesn't make it good. There's a good reason why the trend has been towards memory protection.

I view threading vs multiple processes the same way. You may take some performance hit from it, but most times the reliability and maintainability gained from such an approach is well worth it.

Besides, the performance penalty can be largely avoided with shared memory, although that still opens up some sharing, so consider it an optimisation. You may not need it - a lot of things that benefit from multiple CPUs do so because there isn't much communication.

But as always, horses for courses - some things really do benefit from threading. I just think it's a poor first choice - see if you can do it another way first.

Sum Dum Gai
Tuesday, September 30, 2003

The first rule about mulit-threaded applications: wherever possible, don't.

The second rule, if you can't avoid the first: rely MUCH more on code reviews than on testing.  In a multithreaded application, successful tests mean almost nothing.  Something could run 1000 times perfectly with the same data, then fail or behave strangely on the 1001st time.  Intensive code review is the only way to assure the threading is handled correctly.

T. Norman
Tuesday, September 30, 2003

Ori and Sum Dum, OO concepts of public and private is meant to make you explicity declare what's shared anyway, so having more threads doesn't mean free reign for anybody to change things. 

No question if there's a simpler way to do things then do it, but with networking or command and control apps especially, there's usually just no better way than threads. You're at the mercy of OS or API calls that might take 3-5 seconds to return, when you have to make 100 of them in a row every time the user presses "OK".  100 threads might take 3 seconds, one thread 300 seconds, fancy state machine or not.  And forget separate processes, that's just poor engineering to launch 100 processes (or 200 or 300) each consisting of a single function, and each with their own stacks and heaps and 100 copies of the same DLL's duplicated through memory.

And who's not tired of apps that say "connecting..." or "calculating..." and the cursor turns hourglass (or even not) and you can't cancel it, window doesn't repaint, you're just stuck staring at a half-drawn GUI till it decides to finish 30 seconds later.  Maybe it's just a Windows thing, but that's why you often need a separate GUI thread and worker thread.

But I've found proper method naming is especially important when multithreading -- call it InitiateDataRetrieval instead of GetData, or StartCalculation instead of CalculateValue, otherwise it gets too confusing when you're in that mindset of "call function, get result".

Pepe LePieu
Tuesday, September 30, 2003

Pepe, you appear to be uninformed. Bored Bystander observed earlier that: "I've witnessed a couple of really poor threaded designs over the years that were owing to the developer believing that a thread was the only way to implement what was really a state machine."

You state: "No question if there's a simpler way to do things then do it, but with networking or command and control apps especially, there's usually just no better way than threads"

Specifically, for network apps, there is a MUCH better way: it's called "non blocking sockets". The only operation you can't make nonblocking is DNS lookups (gethostbyname / gethostbyaddr) on Unix, and to some extent on Win32.

Can you give an example of a "Command and Control" process that requires you to use threads?

When you DO have something that must block, the right thing to do is wrap it in a thread, and make that thread communicate with your main logic through messages. That's what I do with gethostbyname() for example.

With all due respect to OO encapsulation and hiding, the burden of proof that object integrity is maintained is on the programmer,  in more or less _each and every line of code_. Unless _every_ method you use locks _every_ object it refers to, there's still a risk of race. And if you do handle all these locks, You're probably spending 80% of your resources just on synchronization.

There's also a one-stack-per-thread overhead. They share the heap, which is not necessarily a good thing. See, e.g., the hoard memory allocator for details on why this often works much worse than giving each an individual heap.

And finally, there's no substitute to good design. qmail is built out of 5 processes, each of which is single thread and more or less asynchronous. It's not the most feature complete mail server out there, but it's probably the fastest, probably the most secure, and definitely the most robust one. It's also extremely short, and extremely simple.

Ori Berger
Tuesday, September 30, 2003

"Can you give an example of a "Command and Control" process that requires you to use threads?" --

Sure, your app receives events from several hundred remote units on a network. Upon receipt of a certain event, you have to call a function on a provided LargeMilitaryContractor DLL, which can take up to ten seconds to return (processing, remote logging, etc). Only one instance of that DLL can exist on a machine, per their technical requirements.

If you make that call on the same thread that receives the events (which is from another contractor's single-threaded module), all of the other units time out. You can't buffer it for later, because you constantly get events, and you can't ask LargeMilitaryContractor to change their function to be asynchronous, because that will never happen in the next decade.

Or for example a remote procedure call. In response to a user selection, you must call a function on one of five hundred remote hardware black boxes. It's a legacy system, or already designed by LargeMilitaryContractor, and has no callback or outgoing call mechanism -- you have to call it through a single-instance, high level RPC layer you have no control over, wait for it to do its thing, then it will return with the results you have to display to the user. And your requirements say the UI shall respond immediately (i.e. no hourglass cursors) and allow simultaneous transmission of commands to connected units. You can't make the function call and process UI events without another thread.

et al...

Pepe LePieu
Wednesday, October 01, 2003

*  Recent Topics

*  Fog Creek Home