Multi-threaded Programming Makes You Crazy?

gduranceau writes "Help! My program deadlocks! I got several concurrent threads that write the same variable! Everything goes well on my mono processor but becomes an incredible mess on that 16 CPU monster! And of course, as soon as I add traces, problems disappear... Don't panic! Calm down and take a deep breath. "

Comments

Use the right tool

[AKAImBatman]

And of course, as soon as I add traces, problems disappear... Don't panic! Calm down and take a deep breathe...

...and get yourself a technology designed for multi-threaded programming. Java will give each thread its own cache of variables to prevent deadlocking on concurrent modifications. If you need to do something that requires more than one statement (thus creating a race condition), then you need to create yourself a semaphore-based lock:

synchronized(objectToModify)
{
    if(objectToModify.getX() == myObj.getX()) objectToModify.setY(myObj.getY());
}

Of course, such synchronizations can carry a huge penalty on multi-CPU systems. i.e. If you manage to stop every CPU, you could be wasting MASSIVE amounts of CPU time. As a result, you should always strive to push locks down as far in the code as possible. They must execute extremely quickly, and should only be called when absolutely necessary. Follow those guidelines and you'll find it fairly easy to write multi-threaded code.

Oh wait. I was supposed to praise the NPTL tool, wasn't I. Um... well... it's very nice. And they've got... um... penguins on the homepage. Oh, and look! It's GPLed! Wow. Just... um... wow. Hey, did you know that the author of Minix wrote a book on OS Design? Really. It even covers the basics of multi-threading. It's pretty cool, you should... um... check it out. Yeah, that's the ticket!

Re:Use the right tool

[lbrandy]

Why use Java when you can use Ada.... very good threading capabilities, builtin support for atomic operations... fast and clean.

And the best part is you avoid that feeling... ya know.. much like that time you saw the Donkey Show in Mexico on Spring Break... that really strange feeling you get when you use Java... and no matter how much you shower... it just won't wash off...

Re:Use the right tool

[LWATCDR]

Funny I have never seen this donkey show of which you speak but there is nothing wrong with java. Ada is an interesting language. It was supposed to be the next big thing back in the early 80s since the DOD was going to make it a standard. It never really caught on in the US outside of the military.
I think that was because of a lack of good, cheap and or free tools. Back in the early 80s you could buy Turbo Pascal, Turbo C, and Turbo Basic for under a hundred dollars each. Then came Microsoft's Quick Basic and Quick c. Ada was very expensive and the only system I remember back then that ran on the PC required a 286 and a big memory board to run.
Java like C++, Ruby, Perl, PHP, and Python are all more popular than Ada because of libraries that support them. You can find a library for just about any need for those languages.
To bad really. I learned pascal as my first language so I would like to learn Ada to see just how go it is. The problem is I have too much work to do.

Re:Use the right tool

[moro_666]

I agree, java has great tools for avoiding deadlocks and great tools for multithreaded programming. But i have still seen people who manage to create incredibly bad code on java in multithreaded environments and also people who don't take advantage of the threaded design of the language at all :)
  Java has a noticeable initial coding and running overhead, but while the application starts to grow, it fades away. The only *free* and open alternative in these terms is python, which somewhat provides the same capalibilites but is somewhat limited on other features (network class loading as one example). C# i don't consider free, sure mono is free, but mono isn't pointing out where C# is going tomorrow, there's a redmond company who is giving orders on that one. Ruby just lacks performance, perl's threads aren't that complete (serious problems with objects and streams).

  The language itself doesn't really solve the problem. Educating the programmers does. It is even possible to write an (i)threaded perl application and get it running across boxes. From the `popular` languages, php seems to be only one who is totally ignoring threading and just focuses on having a single process for it all.

  However, for the program author, why exactly are you running a threaded app across 16 cpu-s ? I know lagging behind the synchronization of caches between 16 cpu-s is fun but wouldn't it be way more efficient to have a forked application instead that just send messages across to synchronize the data you really need to share ? Pulling data out of registries and pushing it in all the time doesn't seem to brightest idea of the day.

  From the ideological point of view, threading is a nice idea how to deploy an application, but if you run across many many cpu-s, threads in real life aren't so perfect anymore. They are close though.

In no way i claim that the information provided above is the ultimate truth, but it should be rather close ;)

Re:Use the right tool

[stienman]

Use the right tool

The correct tool is called a brain, but first the brain must be configured properly.

Deadlocks are one symptom of poor program logic, and are designed into the program due to lack of proper controls. They frequently occur when a program is not designed before it is written.

See "dining philosophers" for an explanation of this, and several methods to prevent this situation.

Tracing tools are all well and good, but if one starts out with correct logic in the first place then one won't spend more time debugging than programming.

Always remember that a digital computer is a logical computing device. If you give it a series of instructions which do not ALWAYS have a logical solution, then it will choke ... eventually.

-Adam

Re:Use the right tool

[Anonymous Brave Guy]

There are some good tools for the job. Relatively speaking, Java isn't one of them.

While Java does include some built-in support for multithreading primitives, its underlying model (using locks on data to prevent simultaneous access) is the same as many other mainstream languages today. Thus it suffers from the same weaknesses, including deadlocking, and potentially also things like potential priority inversion, depending on how clever the implementation of the concurrency tools is.

If you want serious multithreaded programming, there are languages practically built around it (Erlang, for example), and for that matter whole approaches that lend themselves to it much better than those used by today's popular commercial languages (e.g., functional programming without side effects). But right now, you still have to look out of the mainstream to find them, and be prepared to accept a fundamental shift in how you look at program construction if you want to take advantage of them.

Re:Use the right tool

[dpilot]

I hope you realize that the Ada situation has changed. Look for 'gnat'.

I've wanted to try Ada, but have never had the time.
I was quite profficient with Modula-2, even to the point of writing a TSR/ISR with it, back in the DOS days.
IMHO many, though far from all, of today's securty problems would never exist with decent type checking.

Re:Use the right tool

[Anonymous Coward]

Even better, use Doug Lea's excellent concurrency package, which has been integrated into Java 1.5 but can also be used with older Java versions.

Re:Use the right tool

[GileadGreene]

You're right! It would be better to get a technology designed for multi-threaded programming. But then you go on to push Java? I'm confused.

Now, granted, Java does provide builtin support for concurrency. Although that support is an implementation of the 30-year old monitor concurrency primitive, which even one of its principal inventors (Tony Hoare) long ago abandoned in favor of better things. Not to mention that Java's implementation of monitors is known to be broken (or at least was - maybe they've fixed it now?).

Doug Lea's util.concurrent package (now part of Java 1.5) certainly helps things on the Java front, but it's hardly a panacaea. Depending on the application, you may want to take a look at JCSP instead - it provides for an almost direct translation of ideas from Tony Hoare's CSP into Java. For languages with good concurrency support out of the box, you might try Erlang, Ada, Mozart/Oz, E, or Eiffel.

Re:Use the right tool

[elFarto the 2nd]

Also in Java 1.5, there were a whole slew of new tools added:

http://java.sun.com/j2se/1.5.0/docs/api/java/util/ concurrent/package-summary.html

Regards
elFarto

Re:Use the right tool

[Anonymous Coward]

FYI, as of 1.5, there's a new batch of concurrency libraries. I particularly like the flexibility of ReentrantLock and it's support for non-blocking (or even time-limited blocking) lock attempts.

Re:Use the right tool

[Kupek]

I know lagging behind the synchronization of caches between 16 cpu-s is fun but wouldn't it be way more efficient to have a forked application instead that just send messages across to synchronize the data you really need to share ?

Not always. If the level of parallelism is very fine, then the synchronization costs would overwhelm any gains from running in parallel. I really don't understand your overall point, either. Running a scalable multithreaded app over as many CPUs as possible is exactly what you want to do.

Re:Use the right tool

[Omnifarious]

Ahh, a member of the 'Java is the solution to everything.' guild. I went from thinking Java was a fantastic idea, to being unenthused because it was overly verbose, unexpressive and slow. And now, thanks to people like you, I despise the language and think it's one of the worst things to hit the computer industry in years, mostly because some people seem to think it's the solution.

If you want a real garbage collected, platform independent language that works with your environment and OS instead of misguidedly trying to replace it, use Ruby or Python. Both are less verbose, more expressive and all-around more powerful. They aren't screamingly fast, but if you really cared about that you wouldn't be using Java and it's bloated multi-megabyte operating system masquerading as a VM either.

Re:Use the right tool

[Stocktonian]

I'm shocked, just shocked! All this time I thought programming was for the masses and it turns out that when you just copy stuff books and websites, it doesn't always work.

Really when are people going to get over this multithreading problem? Concurrency issues have been around for years with plenty of solutions for those who bother to learn about the principles.
While the parent poster mentioned Tanenbaum's Minix book with his tongue in his cheek, I think it's actually a very good introduction. "Principles of Concurrent and Distributed Programming" by M. Ben-Ari is also worth a read for anyone serious about programming these days.

Re:Use the right tool

[Greyfox]

It might be the right tool for threads, but you can still allocate a semaphore in C, C++ or any language that can call out C code.

It is most definitely not the right tool if you want to do anything outside the java VM. Sun seems to feel that their language should represent the lowest common denominator of system level functionality across all operating systems. Unfortunately that means that if you want to do anything at the system level you'll have to work around fundamental limitations in Java. And the minute I need to employ a JNI solution to do that, I may as well have written my entire application in C.

Don't get me wrong, Java's good for some stuff. Anything where you're just pushing data around and not trying to do UNIX job or file control is a likely java candidate. Trying to treat it as a silver bullet and shoehorn it into tasks where it's not suited will only lead to misery, though.

Threading takes careful planning in any language and although java has built in synchronization functionality, it's still easy to run into problems in Java, too.

Re:Use the right tool

[Anonymous Coward]

Indeed. I don't hate Java. Just the apologists who put it on a pedestal.

Re:Use the right tool

[Marxist Hacker 42]

Either that or just use LOCAL variables, and make sure your code is re-enterant. Don't they teach CS students to avoid global variables and global files anymore?

Re:Use the right tool

[fm6]

If you're going to tout Java as a concurrent programming platform, the books you should link to should be about Java. Such as:

• Concurrent Programming in Java: Design Principles and Pattern (2nd Edition), by Doug Lea.
• Java Concurrency in Practice by Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, and Doug Lea.
• Effective Java Programming Language Guide, by Joshua Bloch. Though this is a general programming guide, its chapter on Threads contains essential "best practices" for concurrent programming.
• Concurrency: State Models & Java Programs (2nd Edition), by Jeff Magee & Jeff Kramer.

I would also call attention the impending Fourth Edition of the Java Tutorial, which is supposed to be in print at the same time as the general release of Java 6 (Mustang), and will be available on the web slightly before. Its chapter on Concurrency is not nearly as thorough or authoritative as the above books, but it has a certain accessibility. Besides, it was written by (ahem) me.

You should also note that your complaints about the limitations of Java concurrency are addressed in JSR 166, which has been part of the Java platform since 5.0. This defines a new package with many nifty features. There's excellent coverage in this JavaOne talk.

Re:Use the right tool

[Anonymous Coward]

Hansen's diatribte is somewhat comical. Java's synchronization model isn't shown to be broken it merely fails to enforce at the language level that all multithreaded access is correct. It reads more like he's distraught that Pascal went the way of the dinosaurs. He spends most of the piece talking about himself in such a way as to ask, "Why isn't anyone looking at me?"

Re:Use the right tool

[slamb]

Java will give each thread its own cache of variables to prevent deadlocking on concurrent modifications.

This is nonsense. Java has no per-thread cache of variables. I don't even know what you are misdescribing. I can only guess that it's one of these things:

• Each processor has a cache of memory. It's for speed, not preventing concurrency bugs. In fact, it frequently causes bugs - when one processor reads a memory location to which another has recently written, the cache can mean that you get stale data. Of course, there are ways for handling this correctly (memory barriers) but they're worthless if you don't understand them and use them properly. The short version is that, in Java, if you're don't have a particular lock that you're consistently holding when you're accessing any particular memory location that ever could be touched by more than one thread, your code is almost certainly wrong.
• Java has the concept of thread-local data, but it's not a cache, it's not transparent (if you don't know what it's called, you can't possibly be using it), and it's generally a last resort for working around code that was designed to use globals back before threading. (In C, errno is the canonical example.)
• Java's memory allocators tend to put small objects into blocks allocated in larger chunks per-thread, which I guess you could call a per-thread cache of free memory. Again, strictly for speed.

... you should always strive to push locks down as far in the code as possible. ...

Increasing the complexity of your locking and making it more likely you'll cause deadlocks.

From your first sentence, I suspect you don't know what deadlocks are. Textbook definition: thread A has resource 1 and is waiting for resource 2; thread B has resource 2 and is waiting for resource 1. Consequently, both threads hang forever. Typically the resources are two mutexes (a.k.a binary semaphore, a.k.a the things you synchronize on in Java). If you have two threads that can acquire the same two mutexes in opposite orders, you have a potential deadlock.

The more mutexes you have, the more likely you'll cause a deadlock if you don't know what you're doing. If you have one big mutex for your whole system, deadlocking on mutexes is impossible. You should probably stick to that design until you research concurrency a little more.

Re:Use the right tool

[LnxAddct]

Woah now, slow down there. I'm a big fan of python, but also a fan of Java. Java's JVM is on par with the size of Python. Java's redistributables, in particular with the new pak200, can easily be around 2 megs in size. Python is ridiculously slow, but still faster than ruby. I've done a ton of coding in both languages and there are plenty of cases where "Java is the solution" because no other platform provides its capabilities. Python's libraries also are laughable in comparison to Java's. Java has defined standards, a great set of APIs (granted the gui sucks, but the api is wonderful), and the only major complaint I even hear from people is about Swing. Swing in the upcoming java JVM is finally fully threaded and just about all of the problems people complained about are fixed (including pretty good support for native themeing). Java is a very nice language, but it is alot more. It is an entire platform and it has a set of tools that just don't exist with any other language. It is very well designed, speed hasn't been a concern for ages, modern jvms might run a few percent slower than native performance... but it's still (depending on what benchmarks you use) around 1000 times faster than python. You're right that if you need high performance, you don't necessarily use java (although modern jvms are fast enough that they are used in some cases), but if you're writing a program that does a fairly common task of say walking through a directory tree of a couple hundred thousand files... the user will notice the couple of seconds that it takes python... but java will seem much snappier. Both languages have their place, but until python gets a hell of alot faster, a better standard set of libraries, and more enterprise tools, you can't even really compare them... they are for entirely different needs. And far as memory goes, Python can be just as big of a bitch about it as Java can be.
Regards,
Steve

Re:Use the right tool

[renoX]

Yes, concurrency isn't a new problem, but saying that it has 'plenty of solution' is going way overboard IMHO.
There are many ways to attack the problem true, but it remains a very difficult thing to do..
Especially for 'normal' programs say a game engine which must be changed quickly because of a new idea, that is to say not 'multiplying two matrices' types of programs.

Re:Use the right tool

[Anonymous Coward]

This is nonsense. Java has no per-thread cache of variables.

Really? Then would you like to explain what exactly the Volatile keyword does?

From your first sentence, I suspect you don't know what deadlocks are.

I suspect you don't know what the fuck anyone's talking about. Come back when you're out of school, young man.

Re:Use the right tool

[LWATCDR]

"I hope you realize that the Ada situation has changed. Look for 'gnat'."
Yes there is now a few free and or cheap Ada development tools. But there are many more C, C++, Java, Perl, Python, Ruby, and PHP bindings, libraries, development environments and a much larger code base to work from.
Ada is much like Scheme, Haskell, and SmallTalk. Very good tools, not often used. I wonder what would have happened if Borland had made a TurboAda. Would it have become super popular or would it have done as well as Turbo Prolog?

Re:Use the right tool

[moro_666]

what does the level of parallelism have to do with it ?

i give you a simple example, your application is using a third party library that you have not optimized for threading. the api contains a block like this :

while (condition) {
  x++;
}

now imagine that you have shared the x between your threads and that it gets incremented 1000 times. this means 15 000 low level threading messages sent between the cpus that "yo you cpu, this equals now to this". the x may be buried into some deep hierarchy of structs so duplicating it for temporary use is not possible.

it's an extreme example , i know, but still , this is not an unusual situation.

if you know that the x itself won't be accessed any time soon by the others at all and you are using a forked model, you can just later send a message to the others once that hey, x was incremented by 1k.this is exactly what you can achieve, 15 messages vs 15k messages. in addition the operating systems copy the variables that are actively used into the cache of the cpu and into the registers inside the cpu, using the standard threading model on this will create a lot of movement, even in one smp box.

ofcourse this just shows bad design, but are you willing to rewrite all the 3rd party libs that you need ?
i don't think so.

Re:Use the right tool

[Gr8Apes]

volatile - causes a read or write out to main memory, ie, not the local CPU cache. It's slower, obviously. The implementation is supposed to be pretty consistent since JDK 1.4.

now go eat your porridge, you babbling idiot troll.

Re:Use the right tool

[dpilot]

Yes, there are obviously more C, C++, etc tools available. But you said you were interested in learning Ada, if you ever found the time. All you need is at least 1 toolset in order to play, and that exists.

I heard once that Turbo-Modula2, which was released for Z80, eventually became JPI Modula2 on X86. I did my stuff with the latter.

Re:Use the right tool

[Stocktonian]

You're right some types of program will never be suitable for concurrent programming. That's down to the nature of the problem rather than the skill of the programmer.

I also didn't mean to imply there were 'enough' solutions the concurrency issues. More elegant and sophisticated ideas will always be searched for.

The only thing I don't agree with is that concurrent programming is hard. To some people printing "Hello World" is hard, it's all about the learning curve. Personally I think anyone who calls themselves a (competent) programmer needs to be able to handle concurrency, if not it's a major tool lacking from their skill set.
Perhaps if you could give me an example of one way that a game engine would be hindered by multithreading I'd be more convinced. I don't mean current engines, I mean ones written correctly, to take advantage of multiple cores or processors.

Re:Use the right tool

[slamb]

volatile - causes a read or write out to main memory, ie, not the local CPU cache.

Not even that, actually.

In C, it tells the compiler that the read or write to memory can't be reordered. If you do a read, it has to get it from memory right then, rather than reusing one from before that it might have stuck in a register. It doesn't tell the CPU anything about synchronizing its cache or executing the instruction in order, however. You've gotta have both.

In Java, it actually depends on the version of the language. third edition (Java 1.5, I believe). second edition (the first is the same; so Java 1.1-1.4). It appears to say what you said, but I don't buy it. Look at this article by a bunch of Java synchronization experts on double-checked locking. In particular, this sentence:

The consensus proposal extends the semantics for volatile so that the system will not allow a write of a volatile to be reordered with respect to any previous read or write, and a read of a volatile cannot be reordered with respect to any following read or write.

This change might have made it into the third edition. The second and first read like it provides this guarantee, but if these guys say not, then I'm not going to be depending on that without reading all of the chapter on thread interactions (not just the one section on volatile), reading everything they say, and doing some experiments. If that means my software runs 0.5% slower because I have more synchronization overhead than I need, then so be it.

Re:Use the right tool

[Doctor Memory]

While Java does include some built-in support for multithreading primitives, its underlying model (using locks on data to prevent simultaneous access) is the same as many other mainstream languages today.

In other words, Java provides built-in support for traditional concurrency methods, rather than making you reinvent that particular wheel. Which means that if you've done multi-threaded programming before, Java probably supports whatever techniques you've (presumably successfully) used. I fail to see how this is the bad thing that previous posters seem to make it out to be. I don't think anyone is saying that Java has some wonderful new mutithreading paradigm, it just provides support directly within the language for threads and basic concurrency control. Yes, I'm sure there are better things out there, but the point is that Java is a mainstream general-purpose language with threading support. How many of those are there?

Re:Use the right tool

[Doctor Memory]

I wonder what would have happened if Borland had made a TurboAda.

I think they would have, if the DOD hadn't mandated that there be NO subsets of Ada. That meant that every implementation had to support multithreading (among other things), which would have been difficult on DOS since it didn't even have a scheduler, let alone threads.

Re:Use the right tool

[lbrandy]

Yes there is now a few free and or cheap Ada development tools. But there are many more C, C++, Java, Perl, Python, Ruby, and PHP bindings, libraries, development environments and a much larger code base to work from.

Ada is tightly knit with C. You can import C functions with primitive data-types directly into Ada. You could write a script that will convert a C header file into an Ada header file (ads) containing all the wrapper code necessary to import all of the C functions.

OpenGL, for instance, especially version 2.0 where they switched everything to GLints, is pretty straightforward to wrap into Ada. I'm not really sure what "tools" means... Ada compiles into the same intermediete language in gcc as C and C++ do.. so all of the post-compile tools will still work... like gprof, oprofile, gdb, etc. This is a non-issue. If IDE is the concern... well.. I can't help you there... I use emacs.. and it's scripts to set it up for ADA is available.

The biggest concern with using Ada is incompatibility with a large C++ codebase. If you have existing code you want to reuse, and it's in C++, then Ada is not a good choice. However, C and Ada work very well together.

Re:Use the right tool

[LWATCDR]

Could have had it for the Amiga. I am still mad at Borland for not making TurboPascal for the Amiga like they promised.

Re:Use the right tool

[KidSock]

get yourself a technology designed for multi-threaded programming. Java will give

.. will give you a headache. Java thread support is bad. Because you can only lock around the synchronized() block you can't unlock the lock if you call out from that block. And what's worse, is the way they deal with the problem is to introduce bloated java.util.concurrent.* packages. It would have been much better to start with a small simple ReentrantLock type class.

Java is such a great langange it really pisses me off to see them put these huge bloated libs in it like all the logging crap and the overdesigned nio packages.

Re:Use the right tool

[julesh]

The only *free* and open alternative in these terms is python, which somewhat provides the same capalibilites but is somewhat limited on other features (network class loading as one example).

I wouldn't recommend Python for work on multi-cpu systems. It has a global lock that means that only one thread may be executing python code at a time. Python only scales in a cluster-like fashion, not with big & fast systems.

From the `popular` languages, php seems to be only one who is totally ignoring threading and just focuses on having a single process for it all.

Yeah, well, you only have to look at what the language was designed for to realise that multithreading in that environment just isn't particularly useful. Not to mention that they still have problems with dependencies on non-threadsafe libraries.

Re:Use the right tool

[renoX]

>More elegant and sophisticated ideas will always be searched for.

Currently it is Software transactional memory (STM), the hot topic (see
  http://en.wikipedia.org/wiki/Software_transactiona l_memory ), it remains to be seen if it will be really useful..

That said, even currently even normal SW projects are difficult, concurrent projects are harder to make, much harder to debug, plus exploiting efficiently concurrency needs to be aware of the number of core: now your software must run efficiently on both single core and bi-core CPUs, which is of course harder, and when they will be 4-way cores..

Re:Use the right tool

[TapeCutter]

I agree, someone will probably throw a brick at me for mentioning MSVC/C++ but it libraries all come in thread safe versions and it is common practice in Windows to start a thread to efficently handle messages from such things as the service manager. Also casting off a thread for a lengthy operation resulting from an MFC button press ensures you dialog does not stop responding while it backs up the hard drive.

I see alot of screwed up code because the coder did not understand the basics (granted the old/new API thing can be confusing). None of these "everyday" threading techniques seems to rate a mention in this disscussion (probably since they don't run on a cluster in the basement).

Re:Use the right tool

[Gr8Apes]

volatile means pretty much the same thing in Java - use the main memory value only. And many many texts, and the new concurrency package in Java 5 (JSR166), as well as the oswego concurrent utils and the backport of JSR166 for JDK 1.4 show that you don't need both cache synchronization and in-order execution in order to write reliable multi-threaded code.

Double checked locking is commonly used to show why you cannot get away without synchronizing certain types of actions.

Namely, something along the lines of

MyClass c = new MyClass();

where the construction of MyClass is non-atomic.

The out-of-order execution allows the assignment to occur at any point during the construction of the new instance of MyClass. The only way to force in order execution is via synchronized blocks, but even then there are issues. While there is a class of applications that benefit greatly from lazy loading (the primary reason to have the double checked locks)

Volatile works fine in most common JVMs post 1.3.x for work with primitives and existing objects (those created elsewhere and guaranteed complete, usually via synchronization). This is one reason why multi-threaded code can be very fast when locking can be removed with long-lived objects. Architectures that contain lots of object churn and attempt to share short-lived objects across multiple threads perform more poorly as they require synchronization, at least in the general case.

In Java 1.5, or Java 5, the volatile keyword got a new guarantee or two, but I'm hazy on what it was. The double-locking algorithm still won't work, though, and can't work, because of the way synchronization itself is defined in the spec. The compiler/vm can move the start of the block ahead in the codestream, only the exit point of the block is guaranteed.

Synchronization was improved in JDK 1.4, IIRC. So its impact is considerably reduced in the latest JVMs, and smart use of synchronization will have minimal impact on your code's performance.

I think we agree in principal, I just didn't write enough to be perfectly clear in my first response (to a troll, no less).

Re:Use the right tool

[tricorn]

What I don't like about Java's concurrency is a) it forces ALL objects to have a mutex/condition variable structure (stupid wasteful overhead), and b) the condition variable support doesn't allow you to do things like share a mutex for separate condition variables. Yes, it makes it easier to not screw up (by using the wrong mutex entirely), but it also takes away a lot of flexibility.

For example, it is more difficult and less efficient to implement reader/writer interlock models without the ability to have a single mutex with two separate condition variables.

I'd rather have explicit semaphore, mutex and condition variable objects, explicit requests for atomic operations and memory barriers, and explicit support for a conditional-write (can be protected with a mutex on platforms that don't support it in hardware). This avoids the overhead on the majority of operations that just don't need it, and allows a 2GHz processor to actually run as if its fast.

Then include a good native inter-thread message-queue facility with support for single and multiple readers/writers, blocking/non-blocking with waiting on multiple queues, and you thread synchronization would be a snap. Of course, you'd still have to understand what you're doing, or the multi-threading isn't going to gain you anything, but that's going to be true no matter what facilities are available.

Re:Use the right tool

[Fulcrum of Evil]

What I don't like about Java's concurrency is a) it forces ALL objects to have a mutex/condition variable structure (stupid wasteful overhead),

Who cares? A Mutex that nobody uses is something like 4 bytes/object. The lack of good condition variables is a pain - gotta make your own.

I'd rather have explicit semaphore, mutex and condition variable objects, explicit requests for atomic operations and memory barriers,

So, what language support is missing that would help memory barriers?

Does this article have any useful info?

[dennism]

It looks like it's just a link to a sourceforge project... was there supposed to be something else?

Re:Does this article have any useful info?

[Virak]

Useful information? On slashdot? You must be new here.

Re:Does this article have any useful info?

[Anonymous Coward]

No. It's useless, especially if you are programming with newer higher level languages such as Java or C#/.NET because they offer you ready thread safe information structures (such as lists and queues) and other superb thread management tools.

All good programmers...

[Nephroth]

Are a little mad anyway ;)

Re:All good programmers...

[Frozen Void]

No, only programmers who live to program ,Technomagi of their own world.
Such people dedicate all possible time to get better at programming and their programs.
A programming Otaku,feels like he needs
to be a 'Good Programmer' at any cost.
Most programmers of course just work for money and many hate the job,writing and debuging pages of code,arguing on implementations and drinking coffee.
Good Programmers are rare
and they usually the type i described,this "stereotype" isn't changing any time soon(it is applies to specialists in many areas outside programming,though usually hobbies: amateur perpeetuum mobile constructors and such 'crazy' people,mathemathicians in active research,radical philosophers,etc).
I wonder if they dream in C++

Re:All good programmers...

[temojen]

No proberen and no verhogen make software something something

Go crazy?

Don't mind if I do!!!

Re:All good programmers...

[KlomDark]

Was that supposed to be some kind of fucked-up Haiku?

Re:All good programmers...

[Beryllium Sphere(tm)]

Bunkum.

The voices in my head jus told me I'm perfectly sane.

Since when was this freshmeat?

[D. Taylor]

I was expecting a bit more substance to the article than something that sounds like it came from a (bad) marking department (what's a "deep breathe" anyway?), and a link to some sourceforge project.

What's going on?

Re:Since when was this freshmeat?

[Anonymous Coward]

>> What's going on?

You're reading Slashdot?

Multi-threaded Programmation Makes Me Crazy?

[Mortice]

No, this title does. Is a Sentence? Is a Question? Why There a Space Before the Question Mark? What 'Programmation'?

Re:Multi-threaded Programmation Makes Me Crazy?

[zhiwenchong]

The poster is a French-speaking person. Programmation is the French word for "programming".
Notice also: take a deep *breathe*.

But I agree... multi-threaded programming can drive people crazy. Message passing-based programming is less prone to nastiness than shared-state concurrency. (Languages like Erlang come to mind).
http://en.wikipedia.org/wiki/Concurrent_programmin g_language
http://www2.info.ucl.ac.be/people/PVR/bookcc.html

You can also do Erlang-style message passing in Python using Candygram
http://candygram.sourceforge.net/

Re:Multi-threaded Programmation Makes Me Crazy?

[Anonymous Coward]

"The poster is a French-speaking person."

That's what editors are supposed to be for.

Re:Multi-threaded Programmation Makes Me Crazy?

[mooingyak]

Title is description! Describes producte! Tells you what does! How it helpes you! Programmation is programming with exclamation!

Re:Multi-threaded Programmation Makes Me Crazy?

[feijai]

The poster is a French-speaking person. Programmation is the French word for "programming". Notice also: take a deep *breathe*.

When chiding Americans for pointing out English errors, it's probably wise to not make hillarious ones yourself. I guess it's time to "notice also" and "take a deep breathe" myself. :-) And I speak French, though it's not my native language. Does that make me a "French-speaking person"? :-)

Re:Multi-threaded Programmation Makes Me Crazy?

[Anonymous Coward]

Another indication of the same thing: In French you can ask questions by stating something and when writing it adding a question mark or when saying it by sounding like you ask a question (or somewhat "surprised"). The latter part is hard - I've tried to learn it, my teacher has told us that we should really exaggerate it when we practice and that it should become natural later on. Admittedly it is also possible to ask questions in French by preceding it with a question that you can ask - i.e. when you only combine a verb and a pronoun you can do that like you do in English ("is it?") - in this case something like "Is it, multi-threaded programming makes you crazy?" I think that multi-threaded programming is significantly easier than French is, though.

Re:Multi-threaded Programmation Makes Me Crazy?

[zhiwenchong]

When chiding Americans for pointing out English errors, it's probably wise to not make hillarious ones yourself. I guess it's time to "notice also" and "take a deep breathe" myself. :-) And I speak French, though it's not my native language. Does that make me a "French-speaking person"? :-)

Firstly, I had no intention of chiding anyone. I was merely giving information.

"Notice also" is another way of saying "Please note also" and "take a deep breathe" was an verbatim quote from the original post (which has since been corrected). As for "French-speaking person", I was trying to avoid being too presumptuous in assuming that the author was French. He/she could be a Quebecker, Morroccan, Algerian etc.

Re:Multi-threaded Programmation Makes Me Crazy?

[Anonymous Coward]

Programmation is programming with exclamation!

Ah, so it's a portmanteau word. Must be French, indeed!

Link to the home page would be nice

[technoextreme]

I was wondering what was this program was about. Fortunately, here is there website. http://nptltracetool.sourceforge.net/

Re:Link to the home page would be nice

[Andy Dodd]

Sadly, even the project's home page has spelling errors. I'd be willing to take a look at the project in the future if the original /. posting (which is full of blatant spelling and grammar errors) didn't come from a core developer of the project, but even the project's home page hasn't been checked for spelling or grammar errors at all.

I agree that a spellchecker is not the end-all of looking for mistakes (their vs. there and so on aren't caught), but for the developers of the project to put "developper" on their front page doesn't say much about their skill set.

Re:Link to the home page would be nice

[IDontAgreeWithYou]

Fortunately, here is there website.

Here is there?... then where is there?
Here?
What happened to there?
Who's on first?

Re:Link to the home page would be nice

[StikyPad]

There is here.

Five words...

[Inverted Intellect]

Slashvertismentation.

These words are fillers.

Re:Five words...

[RingDev]

Is it still a slashvertisement if the product is "free"?

-Rick

May I be the first to say...

[Anonymous Coward]

Whaaaaaaaaaa?

Correct grammer and word choice drive you crazy?

[alecf]

Then read slashdot!

"Programmation" isn't even a word.

"Take a deep breathe?"

No thanks, I think I'll go loose my mind instead.

Re:Correct grammer and word choice drive you crazy

[Mortice]

"Correct grammer"

Heh. :P

Probably going to download it anyway...

[19thNervousBreakdown]

Looking at the list of functions that it hooks into, I don't see pthread_rwlock*. Are the pthread_rwlock functions implemented using other pthread_* funcs? I haven't run into any problems yet with the project I'm working on, but it would be nice to run through this and make sure everything's working as expected.

"breathe"?

[danbeck]

Take a deep "breathe"?

May I be the first to ask...

[carlos92]

...what's so original about this issue, that deserves to be posted to Slashdot? There isn't even a FA! If the guy wanted to publicize his work (he is a developer for the linked SF project), he could at least have written an article with a concrete problem (even if the problem was made up in order to show the solution), not just some generic rant about how tricky multithreaded "programmation" is.

More Info on the Home Page?

[soloset]

You can probably get a better idea of the purpose of the program on their home page (click the link in the menu of the sourceforge page that says, "Home Page").

Not sure why they didn't link directly to it?

Java no panacea -- must know what you're doing

[Chuck Messenger]

Java's "builtin thread saftey" is simply a poor hack. The idea is to give _every_ structure a mutex. Any access to the structure requires a mutex lock.

First off, that in itself will not prevent deadlock. Secondly, it's damned inefficient.

Look: there's just no way around it. If you want to do effective (i.e. low bug, high performance) multithreaded programming, you simply have to understand what you're doing. Ultimately, the tools of your trade will be mutexes, condition variables, semaphores, etc -- the O/S primitives. Don't rely on your programming language to "automatically" use these for you, blasting out mutexes machinegun-style. Instead, figure out the logic of your program. You probably need only a small number of mutexes.

A key to effective multithreaded programming is to adhere rigidly to certain programming practices. It must _NEVER_ be the case that 2 threads have write access to a given item at the same time. Duh. But you can use fancy programming tricks to, in effect, automatically add run-time assertions to your code which assure that this practice is being adhered to. In production mode, you remove these runtime assertions.

Another good practice is, if you really need to have multiple mutexes, to arrange them into a hierarchy. When a top-level mutex is locked, no other mutex can be locked. When a second-level mutex is locked, only top-level mutexes can be locked. Etc. This hierarchy can be verified at runtime, in debug mode. Adhering to this regime will go a long way to removing the possibility for deadlocks.

Bottom line: you really have to know what you're doing in order to write good multi-threaded code. You should take the time to really study that problem space. An excellent book I've found for this purpose is "Concurrent Programming in ML". (I know -- nobody uses ML. So what? Learn the language just for the purpose of understanding the book. Then, you can apply your knowledge to any domain you're working in).

Re:Java no panacea -- must know what you're doing

[0xABADC0DA]

No, Java does not give every structure a mutex (as if Java even had structures). It only creates a mutex if synchronization is used on an object, so if you never use locking there are no locks. And no, it is actually perfectly fine for 2 or more threads to have read or write access to the same variable as long as it's atomic read/write... you just have to know what that means for your program.

Batman was right that after using Java's threading this NTPL trace looks pretty lame. Not only is the threading and locking in Java braindead simple, but the JVM actually tells you what is wrong. For instance it detects deadlocks and gives you the complete call trace of each deadlocked thread.

Other languages have good locking too (ruby for instance), so it's more that everything is difficult and crappy in C and its kind. I guess if you are stuck writing a threaded application in C in the first place this tracing library could be useful. Of course if you use the heap you're going to also want to replace malloc/free with a fast multithreaded version and then do a bunch of hacks so that it isn't ridiculously slow (locking on every free()... now *that's* inefficient).

Re:Java no panacea -- must know what you're doing

[swillden]

And no, it is actually perfectly fine for 2 or more threads to have read or write access to the same variable as long as it's atomic read/write... you just have to know what that means for your program.

This isn't necessarily true on multiprocessor machines. One of the extra things that mutexes do under the covers is execute memory barriers as needed to ensure the semantics are always what the programmer would expect. Without those barriers, even updates that are guaranteed to be atomic may be seen out of order by other threads running on different CPUs. The individual updates are still atomic, but code that, say, atomically sets a variable x and then atomically sets a flag f to indicate to another thread that x is ready for reading may not work, because the other thread may see the f change but still read the old value of x.

Re:Java no panacea -- must know what you're doing

[swillden]

It must _NEVER_ be the case that 2 threads have write access to a given item at the same time.

Two clarifications:

First, it's okay to allow multiple threads write access as long as the writes are guaranteed to be atomic and as long as the order of atomic writes doesn't matter. In practice, that second restriction usually means you need locking.

Second, it's often important that one thread not be writing an object while one or more threads are reading it. In other words, multiple writers aren't the only problem.

Re:Java no panacea -- must know what you're doing

[Anonymous Coward]

Yes what you say it true, but these are all implications of atomic read/write. This stuff is taught in school no? It follows logically from having caches... similar effects happen with all systems using a cache of some sort, whether CVS/SVN or HTTP cache or package manager cache, etc. I really don't think it is the concept that is hard, it's the implementation in C.

Re:Java no panacea -- must know what you're doing

[Chuck Messenger]

No, Java does not give every structure a mutex (as if Java even had structures). It only creates a mutex if synchronization is used on an object, so if you never use locking there are no locks.

So, if you're doing multithreaded programming with Java, you're "encouraged" to have helter-skelter mutexes (i.e. a mutex on each "structure", aka whatever-you-like-to-call-it). That's dangerous and inefficient. On a surface level, it seems kinds of nice. Because of that feature, you can say "Java is multithreading-safe" -- threads will take turns accessing members. And yet, your program is unsafe against deadlock. Indeed, the profusion of mutexes would tend to _increase_ the likelihood of deadlock, in my opinion. Nothing but actually understanding what you're doing will get you true safety.

In my experience, only a very small number of mutexes are required (often one will suffice). One per structure is way too much. It makes it next-to-impossible to have a deep understanding of the program logic (at a multithreading level).

In short, Java's language-supported-automatic-one-mutex-per-structu re shotgun approach may have marketing cachet, but it actually sucks (IMHO, etc).

Re:Java no panacea -- must know what you're doing

[swillden]

Yes what you say it true, but these are all implications of atomic read/write... It follows logically from having caches

Umm, no, it has nothing to do with atomicity, nor is it because of caching.

Atomicity just guarantees that the atomic change is seen fully or not at all. It makes no guarantees about what other changes will be seen. And the problem doesn't have anything to do with caching, assuming the caches work properly (and they do). The caches maintain coherency as needed between each other and with main memory. The issue is all about what goes into main memory, and when.

The problem actually arises from operation *reordering*. There are at least three levels of reordering that may happen. First, the compiler may reorder things. In theory, given:

x=45;
f=true;

The compiler may choose to set f before setting x. Even assuming both are atomic, that's a problem if another thread is doing something like:

while (!f)
;
do_something(x);

Compilers take care not to reorder things in ways that might cause problems, though, so that's not generally an issue. Even if the compiler doesn't reorder like that, though, the processor might. Most processors these days do operation reordering. But even if the processor doesn't do it, the memory management unit *also* reorders writes. I'm speaking here of the unit that writes to main memory, not to any cache management logic (though I suppose it's entirely possible that they may reorder writes as well).

This stuff is taught in school no?

I think the better question is whether or not it is *learned* in school :-)

I really don't think it is the concept that is hard, it's the implementation in C.

I think it's the concept that's hard. The difficulties in correct implementation almost never come from the specific programming language APIs that are provided, and most bad multithreading designs in C are just as bad and just as tempting in any language, including Java.

Re:Java no panacea -- must know what you're doing

[Clueless Moron]

You are perfectly free to use a single object as a mutex, shared between as many classes or threads as you want in Java. And of course, this includes making a single global lock if you want to. It's trivial to do.

I have certainly never felt that java has "encouraged" me in any way to make lots of mutexes.

Re:Java no panacea -- must know what you're doing

[Chuck Messenger]

That's fine. But then, what feature of Java, that you make use of, qualifies it as a "multithreading-safe language"?

Re:Java no panacea -- must know what you're doing

[Joe U]

Surround everything in an exclusive lock, and problems will magically go away. Well, so will your performance, but lock lock lock lock lock, developers developers developers...nevermind.

Seriously though, being overly cautious with exclusive locking of resources will hurt performance but reduce the possibility of deadlocks and those all too entertaining memory corruption issues that we don't like to talk about (Example: don't delete the structure you are currently looping through... yeah, that wasn't smart, what was I thinking?). I like to start with a very conservative locking system and then go thru it a few hundred times to improve performance.

Re:Java no panacea -- must know what you're doing

[Anonymous Coward]

"Don't rely on your programming language to "automatically" use ..."

That's what those features are there for. They might not be perfect but they generally do the job. If you know so much about the topic and potential problems please go join the Sun JDK development and improve the tools. Seriously.

Re:Java no panacea -- must know what you're doing

[swillden]

I like to start with a very conservative locking system and then go thru it a few hundred times to improve performance.

Exactly. "Correctness first, speed after" is always good advice, but it's really important in concurrent programming, just because it's so easy to get wrong.

Where possible, when tuning for performance I like to leave the more conservative locking structure in place, so I can turn it back on with a compiler (or even run-time) switch. Then whenever I start adding features or fixing bugs, I re-enable the conservative locking until I'm sure that the software is running correctly, then go back to the optimized locks and test again.

Re:Java no panacea -- must know what you're doing

[Clueless Moron]

I haven't seen anybody around here except you claim that Java is a "multithreading-safe language". I can't even imagine what such a concept is.

The only claims I've seen by others is that it is easy to do multithreaded coding in Java, because the language was designed with it in mind. For example, consider this:

synchronized (myMutex) { ... }

"myMutex" can be any object. "synchronized" is syntax. Only the thread that "won" the myMutex object will be running the code inside the braces; any other thread trying to synchronize on myMutex will block. Note that if the code in that block indirectly tries to synchronize on myMutex again, it will quietly succeed, which is nice. Also, if you get something like a null pointer exception inside that block, you can still rest assured that myMutex will be automatically un-owned when you exit the block.

There are loads of other features too of course (somebody else already mentioned that it'll actually show you deadlocks), but really the point is just that it's awfully easy to do the basics.

Re:Java no panacea -- must know what you're doing

[Chuck Messenger]

I haven't seen anybody around here except you claim that Java is a "multithreading-safe language". I can't even imagine what such a concept is.

Refer to the post to which I originally responded:

...and get yourself a technology [sun.com] designed for multi-threaded programming.

What does that mean -- "designed for multi-threaded programming" -- except that the language itself has native capabilities to support multithreading? Java does have such capability, but my argument is that the native capability is insufficient, dangerous, and inefficient. I say it is dangerous because Java "encourages" you to believe that you can get safety thru willy-nilly use of those synchronizing features which are built into the language; in reality, the only real safety comes from a deep understanding of multithreaded programming and proper use of O/S-level sychronizing primitives (or in the case of Java, the primitives supplied by the runtime).

The only claims I've seen by others is that it is easy to do multithreaded coding in Java, because the language was designed with it in mind. For example, consider this:

        synchronized (myMutex) { ... }

"myMutex" can be any object. "synchronized" is syntax. Only the thread that "won" the myMutex object will be running the code inside the braces; any other thread trying to synchronize on myMutex will block. Note that if the code in that block indirectly tries to synchronize on myMutex again, it will quietly succeed, which is nice. Also, if you get something like a null pointer exception inside that block, you can still rest assured that myMutex will be automatically un-owned when you exit the block.

Compare that to corresponding C++ code:

        {
                Lock lock(someMutex);
                do stuff;
        }

Does the same thing. If an exception kicks you out, the mutex unlocks. You can use a mutex that allows multiple locking by the same thread, if you like. Etc. No need for any native language support here (beyond what C++ offers). What about this example lets Java claim native multithreading support (as compared to C++, that is)?

The reason people think of Java-the-language as having multithreading support is that you can declare things (objects or what have you) where all references result in automatic (hidden) mutex (or other synchronization primitive) protection. That, in my book, would qualify as native language support. But, I argue, that is very bad programming practice. In laying out a multithreaded program, the very core of the design should revolve around those primitives. There should be a very small number of these, used in a disciplined way, so that you can maintain a deep understanding of what's going on. Supplying a built-in way to have E-Z mutexes all over the place is just a bad idea.

You could say that, No, Java has native multithreading because, in effect, Java is a miniature O/S, and supplies its own threading and synchronization primitives. Or, it has native multithreading because of the cool debugging features for multithreaded programs. But then you're disavowing the language-level support. What you're then saying is that Java has multithreading primitives (like all major OS's) and a great debugger. There's nothing really special about the _language_ which makes it especially suitable for expressing multithreaded logic (beyond what C++ offers). In fact, because C++ has much tighter semantics about object destruction, I think C++ is more suitable than Java.

In short, C++ (combined with a decent underlying O/S and development environment) is just as much a "technology designed for multithreaded programming". There's nothing about support for multithreading which is particularly compelling about Java vs. C++ (that I'm aware of). There are things about C++ which make it superior, however (object destruction semantics).

Re:Java no panacea -- must know what you're doing

[larry bagina]

If the CPU or MMU reording causes problems, you're probably doing something wrong/stupid in the first place. I have been bitten by compiler optimizations though:

while (!*someExternPtr) ...

being optimized to:

temp = *someExternPtr; while (!temp) ...

volatile is your friend.

Re:Java no panacea -- must know what you're doing

[try_anything]

In short, C++ (combined with a decent underlying O/S and development environment) is just as much a "technology designed for multithreaded programming". There's nothing about support for multithreading which is particularly compelling about Java vs. C++ (that I'm aware of).

I would +1 the rest of your comment but must take exception here. The Java language standard makes useful sequencing and atomicity guarantees that make it clear exactly when a mutex is needed. C++ does not. A dumbed-down version (because I don't know the precise version, nor know any C++ programmers who do) of what C++ guarantees is that externally observable operations occur in object code in the same order that they occur in the source code. So if the source code says

write A to file F;
write B to file F;

then A will indeed be written to the file before B. However, writes to memory are not deemed to be externally observable. If your code says

a = fooA;
b = fooB;

then other threads may see the value of b change before the value of a changes. So the sequence of operations can only be ensured by using explicit synchronization.

Likewise, atomicity of operations is not guaranteed by the C++ standard. The atomicity of an operation in C++ can only be depended on if you know the compiler will compile the operation to a machine word that you know will execute atomically on the target platform(s).

Because of this lack of guarantees, some synchronization techniques that rely on sequencing or atomicity must be accomplished using mutexes or platform-specific directives. You must explicitly protect pretty much all shared data in C++, and for portability, that means mutexes. In Java, you can safely perform unsynchronized reads and writes to an int member variable without worrying that on some platform, somewhere, a thread might read garbage from that variable because of concurrency. (This statement dates to 2001; now I hear strange terms like "64-bit Java," so this might no longer be true.) Java really acts like a single very well documented platform in that respect. In C++, you might have some degree of confidence that an assignment to an int will be atomic on your target platform, but you probably wouldn't depend on it unless you had a lot of confidence in your knowledge of the compiler, the platform, and the fact that your program would NEVER need to be ported by anyone less expert than you.

Also, most people assume that C++ makes stronger guarantees than it really does, so they write crappy code. Java has always been designed for average programmers, and C++ was designed for experts, but in the case of concurrency, C++ really overshot the mark. C++ dates from a time when only gurus did concurrency, and it shows, especially in the lack of documentation and the failure of most popular C++ programming books to include BIG FLASHING WARNINGS about all the surprising gotchas like reordering of writes to memory, or indeed the failure of most C++ learning resources to address concurrency in any way.

C and C++ are slowly losing their status as common first languages. Programmers raised on modern languages chafe at the lack of consideration for concurrency in the C++ language. This will hurt C++ (and the Lisps), as there are many people who categorize all such languages as being essentially from another time period and not worth learning. Right now, people have to abandon that attitude when they leave school, but what if they didn't have to?

Signed, a proud and happy C++ programmer. I'll repeat, +1 to most of your post, but -1 to the idea that C++'s concurrency support is on par with Java.

Re:Java no panacea -- must know what you're doing

[swillden]

If the CPU or MMU reording causes problems, you're probably doing something wrong/stupid in the first place.

Not at all. There are all kinds of common, proper usage scenarios where reordering will screw you without a memory barrier. A more realistic example than the one I already gave is a linked list. When inserting an entry into a linked list, if you're careful about the order in which you make the pointer assignments -- and if you know that pointer assignments are atomic -- you can theoretically allow one thread to insert or remove nodes while other threads are traversing the list, all without any locking.

But if the CPU or MMU happen to reorder your carefully sequenced pointer updates, a thread on another CPU may see a broken link. You don't actually need locking to make sure the insertion is safe, but you do need appropriate memory barriers. Using a mutex will cause the memory barriers to be executed.

I have been bitten by compiler optimizations though... volatile is your friend.

Yes, but keep in mind that on multiprocessor systems, without appropriate memory barriers even a change to a volatile variable may take a little while to be seen by a thread running on another CPU. Whether or not that matters depends on the rest of the code.

Interestingly, Java 1.5 strengthens the meaning of the "volatile" keyword so that it guarantees consistent views across multiprocessor systems. The way that works is that the JVM inserts memory barriers before and after accesses to volatile variables. There is discussion of adding something similar to C and C++ in upcoming versions. It's not clear whether the approach will be to strengthen "volatile", or to add a new keyword that means "volatile + memory barriers".

Re:Java no panacea -- must know what you're doing

[try_anything]

First, the compiler may reorder things.... The compiler may choose.... Compilers take care.... Even if the compiler doesn't reorder like that, though, the processor might.... the memory management unit *also* reorders writes.... I think it's the concept that's hard.

None of these things are given; there's no such thing as "the concept." The designer of the language decides what guarantees to give the programmer and what latitude to give to the compiler, as well as what structures are provided to manage concurrency. Essentially, the language designer decides what concepts the users of the language must understand and employ. C and C++ expose the programmer to the full complexity of machine behavior because efficiency has always been their overriding concern, and in any case, those decisions were made at a time when threading was a niche concern. Newer languages typically strike a different balance between efficiency and support for concurrency.

Re:Java no panacea -- must know what you're doing

[Decaff]

In Java, you can safely perform unsynchronized reads and writes to an int member variable without worrying that on some platform, somewhere, a thread might read garbage from that variable because of concurrency. (This statement dates to 2001; now I hear strange terms like "64-bit Java," so this might no longer be true.)

It is still true. Java guarantees the size of things like int no matter what the platform, and guarantees atomicity of accessing such variables. Of course, on 64-bit platforms you naturally get safe access to larger structures, but that is not guaranteed portable.

Re:Java no panacea -- must know what you're doing

[swillden]

Essentially, the language designer decides what concepts the users of the language must understand and employ. C and C++ expose the programmer to the full complexity of machine

In this case, so does Java. Java also gives you no guarantees that reordering won't occur unless you use some synchronization primitives. Java 1.5 provides a richer set of primitives, including a definition of "volatile" that is safe from reordering, but the programmer still has to understand the issues.

None of these things are given; there's no such thing as "the concept."

There are many concepts, but they're ultimately hardware platform-dependent, not language-dependent. Languages can try to hide some of the issues, but ultimately can't hide all of them without potentially destroying performance. And I don't mean taking a small, or occasional hit, I mean making multiprocessor systems no different than uniprocessor systems. Java is allowed to be a little slow, but if it turns a 16-way box into a 1-way box, it's not usable. And there's no way it can fully hide the underlying realities of write reordering without risking exactly that.

Re:Java no panacea -- must know what you're doing

[the_hoser]

C++ is a nightmare to work with when multi-threading. After a while of mucking with posix threads I just gave up.

Multi-threading in Java is just too easy. Its not bullet-proof, but it has such a set of functionality that it makes it hard(er) to write deadlocking code.

And Id continue to write about it, except firefox just decided that an apostrophe means ctrl+f

*sigh*

Re:Java no panacea -- must know what you're doing

[0xABADC0DA]

Compare that to corresponding C++ code:

Or how about these:

{ Lock(someMutex); do stuff; } // not locked
{ Lock lock(someMutex); exit thread; } // deadlock
{ Lock lock(obj->mutex); delete obj; } // crash
{ subclassed->method(); } // subclass forgot to synchronize ... etc.

In Java, Smalltalk, Ruby, and pretty much any language that isn't C/C++ there is basically no way to screw up in any way except making a deadlock or not locking something important. Of course C++ gives you the 'power' to screw up locking, you know in case you *really* need to have fast but undefined results.

Re:Java no panacea -- must know what you're doing

[TummyX]

So, if you're doing multithreaded programming with Java, you're "encouraged" to have helter-skelter mutexes (i.e. a mutex on each "structure", aka whatever-you-like-to-call-it). That's dangerous and inefficient


Spoken like someone who knows nothing about Java. Firstly, just cause the language makes it easy to use any object as a point of reference for locking, it doesn't make it any worse than any other language. A programmer will generally only use an object for a lock if it is needed. No worse than C, just easier to do.

Secondly, modern JVMs don't require mutexes to be created at all. Most times, synchronization statements occur when the object isn't actually locked by another thread (no contention). Because of the high level abstractions that the JVM provides, it can replace a mutex and use a spinlock instead. One or more bits in every object's header is used as a lock marker or counter. This fast-path optimisation accounts for over 95% of lock statements and makes what would otherwise be a context-switch into the kernel, a few userland operations. All this allows programmers to make their code thread-safe (by always using locks) rather than not using locks out of fear that it will cause speed issues.

I was the developer who wrote the threading/monitor/locking code for dotgnu. Synchronization in modern VM based languages is usually much more efficient than anything almost all C users will write.

Java and C# a *more* thread oriented than languages like C/C++. Garbage collection removes almost all worries about object lifetimes and native language support for not just simple mutex-like synchronization but for monitors with wait/pulse/notify semantics are supported by default. No extra libraries or system calls are required.

Re:Java no panacea -- must know what you're doing

[TummyX]

Just wanted to add that the locking optimisation uses a spinlock to aquire the lock-bit(s) on an object but if that fails (another thread locked the object using the lock bit) then the thread without the lock will create a mutex and wait on that. A thread will not spin indefninitely waiting for an object's lock to be released. The mutex is only created if an object has already been locked (which, in many applications is not the common case). Most VMs that implement this also implement a mutex recycling scheme where a pool of mutexes from released objects is mainted. This speeds up cases where there is contention as a lock doesn't need to be created from scratch.

Bah

[grindcorefan]

Aha, so I can only do multithreaded programming on GNU/Linux with NPTL'ed glibc or what? Other programming langunguages than C/C++ don't exist or don't do threading. What about other operating systems? Specific solutions to general problems only apply to specific manifestations of the general problem and are therefore useless for most of us.

The only good general advice about learning how to develop software on distributed systems I can give is: Read some of Andrew S Tanenbaum's books about operating systems and distributed systems in particular. The books contain knowledge you'll be able to apply to almost every system you develop software for.

Why all the negativism in the posts?

[kclittle]

Developing multithreaded is infact difficult, and any tool claiming to make it easier is worth looking at. If it works, these guys have done us all a favor. If it doesn't, at least they've made an attempt, and it may inspire others to do improve on it. Better tools are always welcome.

Come on....

[g1zmo]

No screenshots???!!!!

Re:Come on....

[Anonymous Brave Guy]

Sorry, someone else is looking at them. You'll have to wait until later.

Re:Come on....

[g1zmo]

I'd mod you up 'cause that's funny.

Maybe they should write a spellcheck first...

[xxxJonBoyxxx]

"take a deep breathe"

Don't know how to multi-thread, can't spell: these fellows practically ooze competence. Perhaps the title should just be "soon-to-be ex-comp-sci majors vent"

Re:Maybe they should write a spellcheck first...

[Anonymous Coward]

A spellchecker wouldn't pick this up as all the words are valid. Some sort of context analyiser would be needed.

Threads considered harmful...

[Stradenko]

Moshe Zadka said it better than I ever could.

Re:Threads considered harmful...

[wizbit]

Really? Because klash gave that article the treatment it deserved better than I ever could.

Re:Threads considered harmful...

[Sloppy]

Yeah, and he's not crazy. He's merely twisted!

Re:Threads considered harmful...

[anomalous cohort]

Good point. Multi-threaded development is more difficult and should be left to the smarter programmers. The alternatives given in that original kiro5han article are bogus with regards to solving the problems that multi-threaded development is intended to solve.

Also, there is the problem of choosing multi-threading inapropriately because of its coolness factor. I remember once this job interview where the interviewers were concerned about hiring developers who are multi-threading gurus. Their situation was a tool oriented MFC application with multiple GUI threads. I asked why you would ever want to do that.

I didn't get the job but I still wonder what possible reason could there be for multiple GUI threads outside of game programming. I can easily see the need for one GUI thread and muliple background threads but why multiple GUI threads that have synchronization needs?

Multithreaded Haiku

[pauljlucas]

There was a time when I was doing a lot more multithreaded programming (using the pthreads API, FYI). At the time, I was inspired to write some Haiku:

Threaded programming
is not for the faint of heart
or for the sober.

A small locked mutex
mistakenly left alone
results in deadlock.

Here's your problem...

[sakti]

I got several concurrent threads that write the same variable!

Here's your problem. Shared state/variables is the anathema of good concurrent programming.

Here's a good place to start if you want to learn a better way...

http://www2.info.ucl.ac.be/people/PVR/bookcc.html

Re:Here's your problem...

[sakti]

Realized that link wasn't as helpful as I remembered. But here are some other good general links that should get you going.

http://en.wikipedia.org/wiki/Concurrent_computing
http://en.wikipedia.org/wiki/Message_passing
http://en.wikipedia.org/wiki/Actor_model

The E lang has some good documentation on concurrency, even if you don't use it.
http://www.erights.org/elib/concurrency/

As does Erlang.
http://www.erlang.org/download/erlang-book-part1.p df

Re:Here's your problem...

[Kupek]

Many algorithms don't scale using a message-passing paradigm. They can be implemented and will produce correct results, but the overhead of passing around the messages overwhelms the benefits of parallelism. Message passing is fine for coarse-grain parallelism, but it's not practical for fine-grain parallelism.

Re:Here's your problem...

[sakti]

This is a implementation/compiler issue. There is no real reason why message passing can't be as fast as shared-state parallelism.

Re:Here's your problem...

[Kupek]

Yes, there is a real reason. Sometimes it's inherent in the algorithm that the amount of data that must be shared is impractical to send using messages. Parallelization does not come for free; there are communication costs. If the communication costs are greater than the benefit you get from doing the computation in parallel, then you get no benefit from parallelization. Message passing will always have more overhead than shared memory multithreading. Hence, shared memory multithreading allows you to exploit finer grain parallelism than message passing.

Your point that message passing is generally a cleaner design choice is valid, but it's not always a practical option.

Re:Here's your problem...

[after fallout]

Funny, I have yet to come across an algorithm that cannot be altered to scale very well with message passing (or be replaced with an algorithm that is better for large n and does scale with message passing). The algorithm may fair poorly when given only 2 or 3 threads in parallel or with less than say 10000 things that need to be done, but really that isn't much of a parallel problem at all.

Could you point me to some algorithm that doesn't scale and has no better replacement? I would really like to understand why it doesn't.

Re:Here's your problem...

[Kupek]

The algorithm may fair poorly when given only 2 or 3 threads in parallel or with less than say 10000 things that need to be done, but really that isn't much of a parallel problem at all.

Bingo. It has to do with the granularity of parallelism. You can take a look at this paper written by people I work with, Multigrain Parallel Delaunay Mesh Generation: Challenges and Opportunities for Multithreaded Architectures. But understanding why is simple: if the cost of communication overwhelms the gain from doing the computation in parallel, then it doesn't scale.

Re:Here's your problem...

[after fallout]

You should never have to share an amount of data that it becomes impractical to send.

Message passing parallelism is not shared variable parallelism. They have different goals:
Message passing is to do as much independant work as possible and then report on what happenned.
Shared variable is to do as many instructions at the same time as possible.

Most of the shared variable algorithms I have come across are message passing in disguise. These implementations work very well for limited numbers of processors, and for limited amounts of data. After a certain point (depending on the algorithm) the shared variable implementations tend to be overtaken by the message passing implementations.

However this could just be my experience of implementing the algorithms on an 18 machine (dual xeon 3Ghz) cluster interconnected with a gigabit ethernet switch. The parallel "computer" isn't exactly designed so every processor has access to every byte of the 72GB of ram. If I was running on whatever today's equivalant to the Cray X-MP is I may have a different opinion.

Re:Here's your problem...

[convolvatron]

i think you are missing parents point (or what i infer to be parents point).

if 'messaging' is a compile-time abstraction rather than a runtime library, then this copy only needs to be made if the caller maintains a reference to the data and may mutate it afterwards. think of it is compile-time cow. this property of 'linearity' (bad term) is very helpful in composing abstractions, but it doesn't need to cost.

it's helpful to disambiguate the processor-visible data sharing model from the programming model. they most often map directly, but they dont necessarily need to.

Re:Here's your problem...

[Kupek]

In my world, "message passing" implies that you're going to scale to multiple nodes. But my point still stands even on a single node. Calling it simply an "implementation issue" is naive, because I'm unaware of any languages, libraries or compilers that are sophisticated enough to completely remove the overhead of passing messages.

Re:Here's your problem...

[Kupek]

I still think you're missing my point about granularity of parallelism. Any problem that is coarse-grain enough to be implemented with message passing should be. But some problems are too fine-grain to be implemented with message passing and inherently won't scale beyond a single node.

Re:Here's your problem...

[convolvatron]

going back to the comment about disambiguation, i'm assuming here that we're talking about a shared memory hardware implmentation (a precondition for your 'scalable shared memory model' in the first place). and its its a tightly coupled distributed memory machine, then much of the overhead you're talking about is handled by the message passing hardware (especially if it can be handled by a polling model)

and no, i'm not talking about MPI, which is basically imposssible to get any kind of static niceness out of. but rather languages like concurrent smalltalk, oz, erlang, concurrent prologs, derviates of the pi calculus etc.

it's not a trivial issue, but coming out with a blanket statement that 'shared memory scales and message passing doesn't' is what is naive. large heirarchical cached shared memory machines have had a real problem exploiting concurrency. the MTA scaled very well on paper, but had such poor constant time performance that it was difficult to really evaluate in practice.

Re:Here's your problem...

[after fallout]

if the cost of communication overwhelms the gain from doing the computation in parallel, then it doesn't scale.

Then the computation shouldn't be done in parallel. Instead, multiple instances of the computation should be done with different inputs.

I think we are talking about 2 different aspects of parallel computing. When I first read above I took it as if you are trying to solve parallel problems with shared variable computations (problems where the process of computing a set of results from a set of inputs is independant). Instead it appears that you are talking about using multiple processors to solve single instances of a parallel problem.

If this is the case, then you really are not looking for scalibility at all, the number of aspects of the problem that can be done in parallel is fixed for the problem. This being the case, shared memory is likely to be a very suitable aid in solving the problem.

Re:Here's your problem...

[convolvatron]

actually there is another class of machines which is shared-memory non-coherent. this breaks the programming model which you're apparently so fond of, but may provide a good middle ground. the synchronization primitives are implemented with atomic ops serialized by the target memory system. i dont think there has been much programming model work in this area.

Re:Here's your problem...

[Kupek]

it's not a trivial issue, but coming out with a blanket statement that 'shared memory scales and message passing doesn't' is what is naive.

That would be naive, so it's a good thing I did not say that. My point all along has been about granularity of exploitable parallelism, and that shared memory parallelism allows you to exploit a finer granularity. I said nothing about scalability. It's not always true, but in general, the finer the granularity you try to exploit, the less scalability you're going to get because there's less parallelism to exploit.

Re:Here's your problem...

[convolvatron]

actually there is parallelism at all sorts of grain sizes, all the way down to instruction level parallelism and loop unrolling/vectorization.

but the interaction between grain size and the shared memory/message passing paradigms is much weaker than you suggest in theory. of course if you're talking about marshalling messages over ethernet clusters then i have to agree with you.

Re:Here's your problem...

[after fallout]

By the way, I like the paper. I have wondered if anyone had decided to actually tried to do some of the very things that the paper discusses.

  We investigate a multigrain parallelization approach
for clusters built from: (1) conventional, single-thread, single-core
processors, (2) low-end, commercially available SMTs and (3) simulated
SMTs using modest and realistic architectural extensions for
fine-grain synchronization and thread spawning

Having not finished reading the paper yet (only on the second page), is there a discussion in there about implementing multiple threads that share variables each individual computer (dual xeon HT, so 4 SMP threads should be able to run in tandem) and using message passing to send to other nodes in the cluster (a node now being a set of 4 threads on a machine) (that is what I am reading it to suggest in the italics above)? Does this yeild advantages over a system with 4 actual processors rather than 2?

valgrind used to be able to do this

[blackcoot]

http://valgrind.org/ used to include a tool called hellgrind for finding just such problems. unfortunately, hellgrind has gone away for a bit (it broke when the VM was re-done to support non-x86 platforms), but julian & co are working hard to get it working again Real Soon Now (tm). if you're using x86, you can use an old release of valgrind (2.2.0 i think) and you should be fine.

personally, i can't say enough good things about valgrind. there are a couple non-obvious issues (support for sse/sse2/sse3 is still in the works, so if you get an inexplicable SIGILL, this is probably the problem), but it's saved me hundreds of hours over the past year (and i'm sure it'll save me even more in the future).

that all said, my (admittedly limited) experience with threading is that it's best to design the deadlocks away before you even touch the editor. i wonder if there are any design tools which support deadlock / contention checking at the model or design level?

Re:valgrind used to be able to do this

[wfeick]

At my previous company we built a system with on the order of 10 threads working on a combined dataset consisting of many hundreds of thousands of objects and occupying a couple hundred meg of memory in a large installation. There could be hundreds of thousands of instantiated locks in the system, although they fell into maybe 30 classes of lock. The large number of objects and locks was manageable because there were a small number of objects (say on the order of 25) that modeled something in the real world, but the system would then model a few hundred thousand of those real world things.

Anyway, suffice it to say it was a reasonably complicated realtime system with different threads having different responsibilities (receiving change data from the real world, work queues between different computation threads, pushing results back out to the real world).

To address the deadlock problem, we took the standard approach of defining an order in which locks must be taken to avoid deadlock. In our case, that really meant defining an ordering for the 30 or so distinct classes of locks and then defining a suborder for the few cases where we needed to lock multiple objects within a given class. Think of a class of lock/data as being a particular bit of subinformation for each of the real world things we were modeling.

Defining that order is hard, so I built a perl script that would extract partial orderings from comments in the code (e.g. "A : B C" would state that lock class A is taken while holding lock classes B and C) and then build a system wide ordering that obeys all the partial orderings. It's the same algorithm that make goes through to build things in the correct order.

Given that ordering, I then created a system to ensure we never took a lock out of order. First off, we wrapped the standard POSIX locking primitives with C++ classes, and created a smart lock handle we could instantiate on the stack and know that the lock would be released in its destructor no matter how you left the function (either through a return or an exception). We even went so far as to ensure that if you canceled a thread the locks would be released.

Given that wrapping, it was pretty straight forward to create a per-thread array to count how many locks were currently held at each level, and verify at lock time that no locks later in the hierarchy were currently held. In the event of an out of order lock attemt, it would throw a LockError exception. All of our exception classes included a stack trace, making it very easy to identify lock order violations just by looking at the logs.

Note that we weren't detecting actual deadlocks, we were detecting out of order locking that could potentially lead to deadlock at some point. This showed design errors very early on in development, rather than having the system deadlock on us at a customer site where things are difficult to debug.

I was going to open source the tools, but we were acquired by a large phone company and I ran head long into bureaucracy when I tried. I decided I'd rather just reimplement it all at some later point in time. I think I've given enough of a description here that you could do something similar if you want. I highly recommend it if you're building anything serious. It's very easy to accidentally take locks out of order if you're not careful, and that needs to be caught early on in development rather than at a customer.

Re:Ada

[booch]

Man, I wish I still had mod points to give you.

Ada was considered a BIG language when it came out. Big as in complexity. The C++ folks used to make fun of it. That's before they added templates to C++, which makes Ada look simple by comparison. Ada also came with a large set of libraries. But nowhere near what Java now comes with standard.

Anyway, when I first started learning Java, I thought that it was almost more similar to Ada in spirit than C or C++. The set of libraries seemed similar, as well as the multi-threading capabilities. To me, the biggest difference was C versus Pascal style syntax. I guess the other big difference is the JVM.

I haven't used Ada or Java enough recently to know too much about their relative merits. But it seems to me that Java doesn't give us a whole lot more than Ada had about 10 years earlier.

Re:Correct grammer and word choice drive you crazy

[HunterZ]

No thanks, I think I'll go loose my mind instead.

Keep your mind to yourself, please. ;)

Single statements are not atomic!

[babbling]

Single statements in Java are not atomic. You should use locks even on single statement operations. There is no guarantee that you won't get interference, otherwise.

Re:Correct grammer and word choice drive you crazy

[Anonymous Coward]

you forgot "loose my mind"...

Monitors

[wandazulu]

I always use a monitor class with multithreaded programming; the class handles all the synching and nothing is shared between the threads. In essence, the monitor is a singleton and each thread makes a call to something like g_monitor.getwork(&work) and inside getwork() I do (in pseudocode) wait on mutex, get mutex, pop work off queue, release mutex, hand work back to caller.

Googling doesn't get me a good link to post, but I know it's a common concept in multithreaded programming and has always worked for me...I have never encountered a race condition or a deadlock and I've used this on some pretty intense server apps.

Just my $0.02.

Re:Use the right tool - Erlang

[Anonymous Coward]

Well, yeah, you could use Java I suppose. But it's still using a shared-state concurrency model, which is inherently complex no matter what you do. Instead of that, you could use Erlang, a functional language using message-passing concurrency, and make all that complexity go away. Ericsson uses it to run telephone switches. Someone else wrote a first-person shooter with it. It can handle thousands of lightweight threads at once, and does distributed apps transparently too. For an intro to Erlang from a Java guy's perspective, check out this article by Bruce Tate.

Interesting tags

[DarthChris]

The tags for this topic currently are:

[+] stupid, programming, thread

Wouldn't expect such a statement here.

No that's just common sense.

[Valdrax]

that all said, my (admittedly limited) experience with threading is that it's best to design the deadlocks away before you even touch the editor.

That's not "limited" experience. That's common sense. Trying to find deadlocks, race conditions, and accidental serialization in an application by experimentally compiling and running is like trying to build a house by nailing the boards together only after they've collapsed on you.

Seriously, threads cannot be bolted on as an afterthought. You have to consciously design threads in in the first place, and if you ignore this advise and attempt to retrofit your code, then you must audit the code fully first to see where execution can be grouped into the smallest safe units for locking.

I've seen what happens when you ad hoc threading in large library that was never designed to be reentrant. Worse, I've seen what happens when you get it working on Windows but fail to realize that the UNIX version never was successfully locking the library for 3-4 years before a customer tried to build an aggressively multithreaded app on top of it and only then discover all the deadlocks that lay hidden inside.

Re:Use the right tool. Forget ADA!

[BLAG-blast]

It's all about OCCAM!

Re:Use the right tool. Forget ADA!

[Grab]

Oh man - blast from the past, big time! We used Transputers at GEC Alsthom for ages. Occam2 was actually my first industrial-level language, rather than C (which I learnt at uni but then didn't use for a couple of years). Eventually Inmos tanked, the supply dried up (GEC bought practically all the remaining stock to keep them in spares) and we had to start again with a new platform and RTOS.

Shame really. Transputers were a great bit of kit, just underfunded, over-expensive and too far ahead of their time.

Grab.

How Ironic....

[valdis]

Slashdot reported the summary line thusly:

Developers: Multi-threaded Programming Makes You Crazy? 79 of 78 comments

What's wrong with this picture?

Explanations...

[gduranceau]

Firstly, I apologize for my English (I'm doing my best).

I perfectly agree with some of you: this article is a slashvertisment! The main reason for that is that I previously tried to submit something more descriptive, but it was rejected. That's why I tried again with a slightly different style.

This tool (PTT) inserts trace points into the NPTL to help you to analyze multithreaded applications behaviour. He's not designed for beginners, but for people facing complex multithreaded issues. I also agree with some of you: you can use Java or some others high level languages for programming. But some applications require performance and have to be written in C. That's why PTT can be useful for some developers.

PTT has been presented at the Ottawa Linux Symposium last summer. You can find the paper here (NPTL Stabilization Project, page 111).

Regards...

Re:Explanations...

[GuidoJ]

The problem with these kind of tools is that people tend to rely on them. Concurrent programming is not so much about tools or technology, but about proper design. In fact, _all_ programming is about proper design and much less about tools or technology.

Re:Explanations...

[BillAtHRST]

Welcome to slashdot!

Anyway, thanks for the contribution. I can think of cases where something like this would be VERY useful. Keep up the good work, and good luck.

P.S. You might want to also post a link at http://discuss.joelonsoftware.com/?design. The people there are just a bit less rambunctious than the slashdot crowd. Who knows, you might even get some useful feedback.

Re:Explanations...

[gduranceau]

Thank you for the pointer (and for your kindness)!

Tailor a concurrency model for your application

[try_anything]

A debugger won't help you if you're trying to ensure correctness at too low a level of abstraction. Most languages give you a couple of low-level building blocks equivalent to the pthreads basics: threads, mutexes, and condition variables. These should not be used directly except in the simplest of circumstances. Rather, they should be used to create a set of higher-level tools that can be applied in a simple and straightforward way to your task.

The most popular way is to create a workflow model with task queues, worker threads, and job dependencies, plus a few application-specific rules to ensure that resource limitations don't cause deadlock.

The high-level model can typically be lifted right out of your proof of deadlock avoidance. Don't have one of those? It's a good idea. The proof gives you a minimal solution and confidence to implement it. Without the proof, you're going to overkill the problem out of nervousness, and you still might miss something crucial.

Concurrent programming, a good skill

[mthreat]

Read this book: Concurrent Programming in Java: Design Principles and Patterns by Doug Lea. It's a bit dry, but well worth the read. Even if you're not programming in Java, the concepts, problems, and solutions are similar. Java just offers some abstraction.

Understand the primitives, wait(), notify(), synchronized. Then learn Java 1.5's java.util.concurrent package, so you won't have to use wait/notify yourself in most cases.

Most programmers don't understand the issues that come up with concurrent programming, and if you can learn them, it's yet another way to set yourself apart. They used to teach this in operating systems class, but these days, who knows.

Re:Concurrent programming, a good skill

[Anonymous Coward]

Only that book looks like it teaches you the bad habit of programming in Java.

Re:Concurrent programming, a good skill

[joebowbeer]

I would also suggest ordering Java Concurrency in Practice, by Brian Goetz with Tim Peierls, Josh Bloch, Joseph Bowbeer, David Holmes and Doug Lea. All of the authors were members of the expert group that created java.util.concurrent.

Java Concurrency in Practice
http://www.amazon.com/gp/product/0321349601/
http://www.campusi.com/isbn_0321349601.htm/

Btw, the real cover has shiny white bullet trains on it -- much sweeter than the one currently shown (even though I do love bees).

Re:Concurrent programming, a good skill

[Super Dave Osbourne]

REad the old book, Programming in Mach. That one is what enlightened me to mutex use and messaging some 16 years ago. I believe it is still valid to this day.

Re:Ada

[Doctor Memory]

it seems to me that Java doesn't give us a whole lot more than Ada had

How about a runtime you can use on a cell phone?

Re:Ada

[lbrandy]

It's not difficult to crosscompile an Ada compiler for embedded chips like ARMs and Xscale. This generally lacks certain featuers (ie, real time and threading)... but this is pretty trivial to get most of GNAT up and running on a major processor.

The real problem comes in when there's some cutsom hardware with a co-DSP or something like that.. since these compilers are generally customized heavily for a specific language (ie, C).

notifyAll()

[Latent Heat]

Yes, I wish I could understand the fine points of notify() and notifyAll().

Java's implementation of Monitor does not have wait conditions -- there is only a generic wait() and a generic notify(), and then you have to set and test variables inside synchronized blocks to figure out what you are notifying for and waiting on.

notify() only wakes up a random thread, so if you have multiple threads waiting, each waiting thread should notify() upon coming out of a wait() so that other threads get served, or you need to use notifyAll(). notifyAll() is like I made an unclear question on an exam, and I have to announce during the exam a change or correction, and 100 heads bob up at once in response.

You see, I can't direct a notify() to a particular wait() -- I have to notify() one at random or notifyAll() and have each wakened thread check condition variables to see if they were the target of the notify. I am not even sure if notify() works correctly in an app with only one wait() in it because there may be other threads in the GUI or wherever that are doing a wait().

And those libraries don't help because they are built on top of notify(), notifyAll() and wait().

Re:notifyAll()

[Anonymous Coward]

And those libraries don't help because they are built on top of notify(), notifyAll() and wait().

Uhm... any source, or is this an assumption? Quoting from documentation stuff:

...The atomic variable implementations in java.util.concurrent.atomic offer higher performance than would be available by using synchronization (on most platforms)...

...While locking is built into the Java language via the synchronized keyword, there are a number of inconvenient limitations to built-in monitor locks. The java.util.concurrent.locks package provides a high-performance lock implementation with the same memory semantics as synchronization, but which also supports specifying a timeout when attempting to acquire a lock, multiple condition variables per lock, non-lexically scoped locks, and support for interrupting threads which are waiting to acquire a lock....

The implications I'm seeing are that no, certain classes in the concurrency library are not just fancy wrappers around synchronized/notify/wait.

Or this quote:

Additionally, these packages provide low-level primitives for advanced concurrent programming which take advantage of concurrency support provided by the processor, enabling programmers to implement high-performance, highly scalable concurrent algorithms in the Java language to a degree not previously possible without resorting to native code.

So... yeah... are you sure?

Re:notifyAll()

[julesh]

If you have a hundred threads waiting on an object, but need to be able to notify a specific one, you have a design error. Have the threads waiting on different objects depending on which condition should wake them, then just use notify() if any one thread can procede (e.g. you've added an item to a queue to be processed by a worker thread) or notifyAll() if all can (e.g. a result that they are waiting for has been calculated).

The only downside to this is that you can't wait on multiple objects, but the need to do that is usually indicative of a design flaw, too.

Re:notifyAll()

[tricorn]

In fact, it is probably (though not necessarily) a design error unless every single waiting thread is in exactly the same piece of code in exactly the same state, so it doesn't matter which one is woken up. If you have different threads waiting on different conditions, they should be using different objects to do the waiting. If you have a bunch of threads and always want to just wake up one specific one, then have an object per thread. Depending on the program logic, you may even be able to just use a simple mutex ("synchronized") rather than condition variables (which require a bit more careful attention to exception handling, which is taken care of for you automatically with synchronized methods and blocks).

If your wait() loop is properly written, you can ALWAYS use a notifyAll(), notify() is just an optimization that suggests that it would be redundant to wake more than one thread. In fact, most implementations of condition variables indicate that notify() (or the equivalent) MAY wake more than one thread, though it only guarantees to wake one.

But did you stop to consider...

[Anonymous Coward]

Your mom is a mutex.

The effort it saves leads to poor design!

[thaig]

Thus spake the Assembler programmers of the first C compilers . . .
. . . and the C programmers of the C++ compilers . .
. . . and the C++ programmers of Java . . .

The late Ole Johan Dahl's simple method

[Anonymous Coward]

The late Ole Johan Dahl's very simple and "almost mathematical" method to demonstrate (almost prove) you've got no deadlocks in your system follows below. Here is an even more simplified version on how to find all your potential deadlocks in one hour using pen and paper.

Key to the understanding is that the only way deadlocks occur is when threads try to aquire locks in the opposite order: One thread holds lock A and tries to aquire lock B, while another thread is holding lock B and waits to aquire lock A. If both threads had tried to aquire lock A before B, deadlock would be impossible. Moving second thread's locking so it too aquires lock A before before B will solve the deadlock. Aquiring the lock earlier will perhaps slow down the program, but not as much as a deadlock.

Anyway, here's the "proof" method. It is based on having to rounds of desciption and "analysis", both amazingly simple.

First round description phase:

Name all your locks and mutextes A, B, C etc. For each execution thread in you system, write down on a strip of paper a capital 'A' each time the thread aquires lock A, 'B' for lock B etc, and lowercase letters 'a', 'b' when the locks are released. Use normal regular expression syntax (parantheses, ?, +, *) to express how ifs and loops in the code affect the sequence of locking and releases. Now you have an regular text expression for each thread describing the set of locks it holds. It can help to draw a line from each 'A' to the matching 'a' etc.

Analysis phase:
Move each strip of paper relative to each other and see if you can find a situation where two threads mutually tries to aquire locks that the other thread is holding. These are your deadlock situations. Now you must inspect your code to see if the thread "overlapping" (one thread being here while the other thred executing there) actually can occur, or if there are undescribed issues like waiting for I/O that cause this to be impossible. (Waiting for I/O can be considered a 'lock' that is held by the user and temporarily 'released' as he types something, but modelling it that way is not always beneficial).

Second round: try to do the same for again, swapping roles for locks and threads. Label each thread A, B, C etc. For eack lock, on a strip of paper write the capital letter A each time thread A can aquire it and a lowercase when it is released. Since the execution interleaving of threads is rather random this can be quite messy, but if you have done the first round properly, you should be able to find the remaining deadlocks during the description phase of this round.

Removing the deadlocks:
Make sure all threads aquire locks in the same order. Hold a lock a little longer than necessary may slow your system dowsn by up to one percent, but deadlocking will slow your system down, eh, many more percents.

Jesus christ, how did this make frist pots?

[aybiss]

Jesus christ, how did this make frist pots? Are you SERIOUSLY going to waste our time explaining this? Like there is a language left on the face of the planet without multi-threaded support. And umm - yeah, locking is locking. Thanks for that. By the way, locks should be brought upwards and managed intelligently, or avoided with smart procedures and data structures, not pushed deep into the code where it can be called from many places very often. And don't post first on multithreading ever again.

Parent post is simply WRONG

[joel.neely]

Take a look at java.util.concurrent (as another response has suggested). Specifically, look at:

"Concurrent Programming with J2SE 5.0"
http://java.sun.com/developer/technicalArticles/J2 SE/concurrency/index.html

and

"Concurrency Utilities Overview"
http://java.sun.com/j2se/1.5.0/docs/guide/concurre ncy/overview.html

There's much more to concurrency in Java (especially Java 5) than simple target-object synchronization. (For example, you can set up queues to pass safely from one thread to another.)

You might also want to look at some other frameworks that have been created in Java, such as CSP, covered in a series of DeveloperWorks articles beginning with:

"CSP for Java programmers, Part 1"
http://www-128.ibm.com/developerworks/java/library /j-csp1.html

There's a lot out there to let you think in much higher-level concepts than simple locks (although you can do that to, for the learning exercise ;-).

Re:Ada

[booch]

The reason Java runs on a cell phone is not that Java has a small footprint. It's because the computers inside cell phones are a lot beefier than they used to be. I used Ada on a 32-bit VAX system that was running at less than 100 MHz and had (I think) 32 MB of RAM. Today's cell phones are around that same magnitude of processing power.

A threaded application in C?

[Viol8]

What , you mean like a Java compiler and JVM for example?
Or did you think they were written in Java (which in turn
was written in java etc, turtles all the way down)?

I guess this is the issue with threads

[Latent Heat]

Going back to the Java docs, I realize that notify(), notifyAll(), and wait() are specific to the object having the monitor (any Java object on which synchronized gets invoked), and the monitor object doesn't even need to be a thread object (object implementing the Runnable interface).

Thanks for the input, I learned a lot from the discussion. I was under the impression that wait() was this big party-line affair where you couldn't notify a particular wait. Since notify() and wait() are object-monitor specific, that solves the problem I thought I had.

But in online discussions of notifyAll(), there is a lot of talk of how notifyAll() is so very necessary yet inefficient when you have lots of threads -- I haven't seen any discussion of using a separate synchronized object for every wait that you want to do, allowing use of straight notify().

Re:I guess this is the issue with threads

[tricorn]

There are uses for notifyAll(), just as there are uses for notify(). notifyAll() would typically be used in cases where there is a status change that multiple threads might be waiting for, for example a multiplexed communications channel where the underlying transport layer has been unavailable. notify() would typically be used where one or more threads are waiting for a request (and you've just made one), or where one or more threads are waiting for a resource (and you've just released one). Doesn't make sense to wake up more than one thread when only one of them is going to be able to continue. If you release two, you do two notify() calls, etc. If requests are variable sized and you released something that could satisfy more than one request, you need to do notifyAll() (e.g. a memory pool with variable sized blocks). Remember, when you do notifyAll(), all of the threads waiting on that object except one immediately switch from doing the wait() to trying to acquire the mutex again (the other one is the one that actually GETS the mutex), and then those each wake up in turn as the previous one releases the mutex.

Note that if more than one thread wants multiple resources, and those resources are limited, you could have deadlock problems (and they won't be detected even if you have deadlock detection turned on for the mutex). You'll have to do deadlock avoidance yourself.

Basically, design as if notifyAll() is your only option, but then use notify() when you know that only one thread is going to be able to proceed as a result of what you've just changed. Don't think of it as waking up a specific thread, think of it as signalling a condition, and whatever needs to happen in response to that condition will happen. In fact, when you signal, there might not be ANY threads waiting at that moment, but it doesn't matter - the next thread that WOULD wait will check, find that you've already set the condition so it doesn't need to wait, and continue from there EXACTLY as if it had waited and then you did the notify(). Since it's all protected by the mutex of the object you're waiting/notifying on, everything works out.

Multi-threaded Code

[oldCoder]

I wrote a lot of multi-threaded code on a uniprocessor for embedded systems development. It turns out that a few things really simplify multi-thread code:

1. The only reason to multi-thread is performance
2. Almost all useful multi-thread apps that need a performance boost are accepting a stream of data and/or emitting a stream of data
3. Producer-Consumer relationships therefore solve most of what you need.
4. You can use a thread like a mutex. That is, you can have the thread accept events that order it to modify the data store and send back events that the data store has been modified. This is little different from what a monitor has to do internally anyway but is more powerful and often much easier.
5. Data streams are physical, usually coming to or from actual devices, not necessarily from logical sources like users. An OS will use a heavyweight process to separate users as a security tool, but a thread is a different creature.
6. It is still true that the structure of the software is often a simple reflection of the social structure of the team that built it. Beware of a situation where each programmer has to create his or her own thread to feel "Real". And go ballistic if you find programmers who need to raise their thread's priority to feel important.

Re:Multi-threaded Code

[rbarreira]

The only reason to multi-thread is performance

Not true. Often, it's easier to program certain things with two threads than with just one.

Re:Use the right tool. Forget ADA!

[LoztInSpace]

I too remember Transputers and they were way too expensive and didn't keep up with performance. Eventually I found that serial processing on a 25 MHZ 386 could take the load of around 5-8 of them. After that a bit of funky coding using networked files blew them away for a fraction of the cost.

rule 1

[petermgreen]

if you can so so then its a good idea to develop on a dual CPU box. That way you will catch bugs much much earlier.