Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am a fairly good programmer, my boss is also a fairly good programmer. Though he seems to underestimate some tasks such as multi-threading and how difficult it can be (I find it very difficult for anything more than running a few threads, waiting for all to finish, then return results).

The moment you start having to worry about deadlocks and race conditions, I find it very difficult, but the boss doesn't seem to appreciate this - I don't think he has ever come across this. Just slap a lock on it is pretty much the attitude.

So how can I introduce him, or explain why he might be underestimating the complexities of concurrency, parallelism, and multi-threading? Or maybe I am wrong?

Edit: Just a bit on what he has done - loop through a list, for each item in that list create a thread that executes a database update command based on the information in that item. I'm not sure how he controlled how many threads executed at once, I guess he must have added them to a queue if there were too many running (he wouldn't have used a semaphore).

share|improve this question
11  
Multi-threading is easy. Correct synchronization is hard. –  Vineet Reynolds Jun 2 '11 at 15:45
24  
Bring three people into the room, preferably with different accents, and have them explain different, overlapping parts of the problem of concurrency.... concurrently. –  greyfade Jun 2 '11 at 16:03
    
Multithreading can be very hard or very easy, depending on the problem at hand and on the language support. Clojure makes it easy clojure.org/concurrent_programming –  Job Jun 2 '11 at 19:35
4  
@Job Concurrent programming is always hard (in real world projects), no matter of what language you are using. Scala, Clojure or Erlang make it a little bit sane when you want to compare it with languages that use and encourage mutable states. –  Chiron Jun 2 '11 at 22:58
4  
My favorite metaphor for this is : "Would you take a sleeping pill and a laxative at the same time?" Even using complex message queues, order is the fruit of concurrency done right. That, unless you have a great deal of experience with it, is hard for many people. –  Tim Post Jun 2 '11 at 23:16
show 1 more comment

10 Answers 10

up vote 9 down vote accepted
  1. If you can count on any mathematical experience, illustrate how a normal execution flow that is essentially deterministic becomes not just nondeterministic with several threads, but exponentially complex, because you have to make sure every possible interleaving of machine instructions will still do the right thing. A simple example of a lost update or dirty read situation is often an eye-opener.

  2. "Slap a lock on it" is the trivial solution... it solves all your problems if you're not concerned about performance. Try to illustrate how much of a performance hit it would be if, for instance, Amazon had to lock the entire east coast whenever someone in Atlanta orders one book!

share|improve this answer
1  
+1 for the discussion of the mathematical complexity - this is how I came to understand the difficulty in shared-state concurrency, and is the argument I generally make in advocating message-passing architectures. -1 for "slap a lock on it"... The phrase connotes an unthinking approach to the use of locks, which will very likely lead to deadlock, or to inconsistent behavior (as clients of your code that live in different threads make conflicting requests, but do not synchronize between themselves, the clients will have incompatible models of your library's state). –  Aidan Cully Jun 2 '11 at 11:04
1  
Amazon does have to lock the inventory of an individual item at one warehouse briefly while processing an order. If there's a sudden, huge run on one particular item, ordering performance for that item will suffer until the supply is exhausted and access to the inventory becomes read-only (and therefore 100% sharable). One thing Amazon has going for it that other programs don't is the ability to queue orders until a re-stock happens and the option of servicing queued orders before a re-stock is made available to new orders. –  Blrfl Jun 2 '11 at 13:19
    
@Blrfl: Programs can do that if they're written to use message passing via queues. There's no need to have all messages to a particular thread going via a single queue… –  Donal Fellows Jun 2 '11 at 14:21
3  
@Donal Fellows: If there are 1M widgets in stock in one warehouse and 1M orders arrive at the same instant, all of those requests are serialized at some level while matching items to orders no matter how they're handled. The practical reality is that Amazon probably never has so many widgets in stock that the latency in processing a crush of orders gets unacceptably high before the inventory runs out and everyone else in line can be told (in parallel), "we're out." Message queues are a great way to prevent deadlocks, but they don't solve the problem of high contention for a limited resource. –  Blrfl Jun 2 '11 at 15:22
add comment

Multi-threading is simple. Coding an application for multi-threading is very, very easy.

There's a simple trick, and this is to use a well-designed message queue (do not roll your own) to pass data among threads.

The hard part is trying to have multiple threads magically update a shared object in some way. That's when it gets error-prone because folks don't pay attention to the race conditions that are present.

Many folks don't use message queues and try to update shared objects and create problems for themselves.

What becomes difficult is designing an algorithm that works well when passing data among several queues. That's difficult. But the mechanics of co-existing threads (via shared queues) is easy.

Also, note that threads share I/O resources. An I/O bound program (i.e., network connections, file operations or database operations) is unlikely to go any faster with lots of threads.

If you want to illustrate the shared object update problem, that's simple. Sit across the table with a bunch of paper cards. Write down a simple set of calculations -- 4 or 6 simple formulas -- with lots of room down the page.

Here's the game. You each read a formula, write an answer and put a card down with the answer.

Each of you will do half the work, right? You're done in half the time, right?

If your boss doesn't think much and just starts, you'll wind up conflicting in some way and both writing answers to the same formula. That didn't work because there's an inherent race condition between both of you reading before writing. Nothing stops you from both reading the same formula and overwriting each other's answers.

There are many, many ways to create race conditions with badly- or un-locked resources.

If you want to avoid all conflicts, you cut the paper up into a stack of formulas. You take one off the queue, write the answer down, and post the answers. No conflicts because you both read from a one-reader-only message queue.

share|improve this answer
add comment

Multi-threaded programming is probably the most difficult solution to concurrency. It basically is quite a low level abstraction of what the machine actually does.

There's a number of approaches, such as the actor model or (software) transactional memory, that are much easier. Or working with immutable data structures (such as lists and trees).

Generally, a proper separation of concerns makes multi-threading easier. Something, that is all to often forgotten, when people spawn 20 threads, all attempting to process the same buffer. Use reactors where you need synchronisation and generally pass data between different workers with message queues.
If you have a lock in your application logic, you did something wrong.

So yes, technically, multi-threading is difficult.
"Slap a lock on it" is pretty much the least scalable solution to concurrency problems, and actually defeats the whole purpose of multi-threading. What it does is to revert a problem back to a non-concurrent execution model. The more you do it, the more it is likely, that you have only one thread running at the time (or 0 in a deadlock). It defeats the whole purpose.
This is like saying "Solving the problems of the 3rd world is easy. Just throw a bomb on it." Just because there is a trivial solution, this doesn't render the problem trivial, since you care for the quality of the result.

But in practice, solving these problems is just as hard as any other programming problems and is best done with appropriate abstractions. Which makes it quite easy in fact.

share|improve this answer
add comment

I think there's a non technical angle to this question - IMO it's an issue of trust. We commonly get asked to reproduce complex apps like - oh, I don't know - Facebook for example. I have come to the conclusion that if you are having to explain the complexity of a task to the uninitiated/management - then something's rotten in Denmark.

Even if other ninja programmers could do the task in 5 minutes, your estimates are based on your personal ability. Your interlocutor should either learn to trust your opinion on the matter or hire someone whose word they are willing to accept.

The challenge is not in relaying the technical implications, which people either tend to ignore or are unable to grasp through conversation, but in establishing a relationship of mutual respect.

share|improve this answer
    
Interesting answer, though it is a technical question. I however do agree with what you say... in this case though, my manager is a pretty good programmer, however I just think because he hasn't come across the complexities of multi-threaded apps, he underestimates them. –  Mr Shoubs Jun 2 '11 at 15:38
add comment

One simple thought experiment to understand deadlocks is the "dining philosopher" problem. One of the examples I tend to use to describe how bad race conditions can be is the Therac 25 situation.

"Just slapping a lock on it" is the mentality of someone who hasn't come across difficult bugs with multi-threading. And it is possible that he thinks you are overstating the seriousness of the situation (I don't - it is possible to blow stuff up or kill people with race condition bugs, especially with embedded software that ends up in cars).

share|improve this answer
    
ie the sandwich problem: you make a heap of sandwiches, but there's only 1 butter dish and 1 knife. Generally all's fine but eventually someone will grab the butter while someone else grabs the knife.. and then they both stand there waiting for the other to let go of their resource. –  gbjbaanb Jun 2 '11 at 20:24
    
Could deadlock issues like that be solved by always acquiring resources in a set order? –  compman Jun 11 '11 at 19:15
    
@compman, no. Because it is possible for 2 threads to try to grab for the same resource at the same moment, and those thread don't necessarily need the same set of resources - just an overlap enough to cause problems. One scheme is to put the resource "back" and then wait for a random period before grabbing for it again. This backoff period happens in a number of protocols, the earliest of which was Aloha. en.wikipedia.org/wiki/ALOHAnet –  Tangurena Jun 11 '11 at 20:29
    
What if every resource in the program had a number, and when a thread/process needs a set of resources, it always locked resources in increasing numerical order? I don't think that deadlock could happen. –  compman Jun 11 '11 at 22:02
add comment

Concurrent applications are not deterministic. With the exceptionally small amount of overall code the programmer has recognized as vulnerable, you do not control when a part of a thread/process executes in relation to any part of another thread. Testing is harder, takes longer, and is unlikely to find all concurrency related defects. Defects, if found, are ofhen subtle cannot be consistently reproduced, hence fixing is difficult.

Therefore the only correct concurrent application is one that is provably correct, something not often practiced in software development. As a result, the answer by S.Lot is the best general advice, as message passing is relatively easy to prove correct.

share|improve this answer
add comment

In Java I can strongly recommend using Executors for this. This require you to create a Callable for each task element, and then submit them all to an executor with the desired threading behaviour.

And regarding why it is hard. Locks are easy until you reach a deadlock situation. Ask your boss if he had ever encountered such a situation.

share|improve this answer
    
Everybody who regularly drives a car has encountered deadlocks. I know I have. –  Jörg W Mittag Jun 2 '11 at 12:51
5  
@Jörg W Mittag: Those are bottlenecks, not deadlocks. If they were deadlocks you'd still be there. –  btilly Jun 2 '11 at 13:38
    
@Jörg, you might want a better car then :-S –  user1249 Jun 2 '11 at 14:04
3  
@btilly @Thorbjørn Ravn Andersen: You've never been at an intersection? The reason why I'm not still there is because one of the drivers decided to deviate from the locking protocol. If we had all followed the locking protocol, we would indeed still be there. Seriously, has noone experienced the situation where two cars with right-of-way arrive at an intersection at the same time? –  Jörg W Mittag Jun 2 '11 at 15:05
1  
@Jörg W Mittag: The protocol (at least as taught in North America) handles all common situations. The person arriving first has priority. In case of simultaneous arrival at an intersection, the person on the left has priority. If they arrive from opposite directions, the person going straight has priority. If both want to turn into the same lane, the person turning right has priority. If both want to turn left, normally both can go at the same time. These rules also apply to the case of simultaneous arrivals of 3 people. –  btilly Jun 2 '11 at 16:06
show 7 more comments

Try using several hammers to mash in a bunch of closely spaced nails at once without some communication between those holding the hammers... (assume that they're blindfolded).

Escalate this to building a house.

Nowtry to sleep at night imagning you're the architect. :)

share|improve this answer
add comment

Easy part: use multithreading with contemporary features of frameworks, operating systems and hardware, like semaphores, queues, interlocked counters, atomic boxed types etc.

Hard part: implement the features themself using no features in first place, may be except few very limited capabilities of hardware, relying say only on clocking coherence guarantees across multiple cores.

share|improve this answer
1  
The hard part is indeed harder, but even that easy part isn't so easy. –  PeterAllenWebb Jun 2 '11 at 20:23
add comment

I was first taught that it could bring up issues by seeing a simple program that started 2 threads and had them both print to the console at the same time from 1-100. Instead of:

1
1
2
2
3
3
...

You get something more like this:

1
2
1
3
2
3
...

Run it again and you may get totally different results.

Most of us have been trained to assume that our code will execute sequentially. With most multi-threading we cannot take this for granted "out of the box".

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.