2012-12-26

On parallel computing

C is a certain kind of devil that can turn around in the blink of an eye. If you're not careful for an instant, it's gonna bite you in the ass. Hard. But parallel computing is another kind of devil that does the same thing. When you combine the two, you get the most intricate problem humankind has to face. But I'll only discuss the parallel part in this post.
In my experience using threads, I've created completely crazy code (as pointed out by my colleagues, Paul Țiței and Sebi Orțan). I'd like to come clean, and help you avoid making the same mistakes.

First, here's the classic tried-and-true formula guaranteed to occasionally spawn a deadlock:

void *a() {
    lock_resource(X);
    lock_resource(Y);
    do_work();
    unlock(X);
    unlock(Y);
}

void *b() {
    lock_resource(Y);
    lock_resource(X);
    do_work();
    unlock(X);
    unlock(Y);
}

Suppose a() and b() are called in a quick succession. Say that a() locks X, then immediately after, b() locks Y. a() is now waiting for Y, and b() for X. Deadlock.
This can be easily prevented by ensuring that a() and b() lock the resources in the same order. Use pencil and paper, or whatever you like, but you MUST guarantee this. It's the only way to ensure correctness.

Our teacher, Rareș Boian, told us at the course that, once you run into a deadlock and are able to fix it, your lab project should be OK. Well, I fixed my deadlock, but I created a more subtle problem (very, very wrong, according to my colleagues, and me, eventually) - which was not noticed by our lab examiner, luckily (or not) for me:

void *thread(){
    lock_mutex();
    do_things_that_dont_need_mutex();
    do_things_that_need_mutex();
    do_other_things_that_dont_need_mutex();
    unlock_mutex();
}

Of course, when I put it this way, you're gonna notice it. My program has no concurrency, defeating the purpose of threads! Since each thread locks the mutex for its whole run, what are other threads doing in the mean time? Perhaps they're just being handled by the thread/function calling mechanism, but that takes a trivial amount of processing power, compared to the instructions that don't need the mutex. They don't call it critical section for nothing! Don't include uncritical things in it, like I did!
Maybe this wasn't mentioned enough at the course, or maybe it was just me (skipping some and being really stupid), but I felt the need of pointing this out to the rest of the world.
While our overworked teachers may have missed this important philosophical point, I am leveraging the power of the Internet (free content distribution) to point it out to you. Be kind and share this to your fellow prospective programmers!