Why does this multi-threaded program work (and not crash)?

Question

From my understanding, if two or more threads attempt to access the same memory block at the same time, it should "complain," to say the least.

I'm writing a program for a class that computes palindromes (words that appear backwards and forwards in the list also count). In my multithreaded solution, I spawn 26 threads to handle each letter of the alphabet

int error = pthread_create(&threads[i], NULL, computePalindromes, args);

compute palindrome simply runs through the sublist of words:

void * computePalindromes(void * arguments) {
    struct arg_struct *args = (struct arg_struct *)arguments;
    int i;

    for (i = args->start; i < args->end; i++) {
        if (quickFind(getReverse(array[i]), 0, size - 1)) {
            printf("%s\n", array[i]);
        }
    }

    return NULL;
}

now, the segment that SHOULD cause the program to stop. I modified quickSelect to find the reverse word in the list.

int quickFind(char * string, int lower_bound, int upper_bound) {
    int index = ((upper_bound + lower_bound) / 2);
    //sem_wait(&semaphores[index]);
    if (upper_bound <= lower_bound) return (strcmp(string, array[index]) == 0);

    if (strcmp(string, array[index]) > 0) {
        //sem_post(&semaphores[index]);
        return quickFind(string, (index + 1), upper_bound);
    } else if (strcmp(string, array[index]) < 0) {
        //sem_post(&semaphores[index]);
        return quickFind(string, lower_bound, (index - 1)); 
    } else return 1;
}

you can see that I commented out a bunch of sem_post/waits.

Answer 1

There's nothing wrong with two threads accessing the same memory at the same time as long as they're only reading the memory and not writing it. None of the operations that you're performing on the data actually modify it, so it's perfectly safe for the threads to perform all these operations in parallel.

Hope this helps!

Answer 2

Just to add to the existing excellent answers and comments, lets visualise what happens in a single core CPU.

Now obviously in a single core CPU there can be only one thread/process running at a time. The operating system scheduler, which is just another thread really (a very special one...), chooses what gets run for the next 15ms or so. But at any one point whatever is running has sole access to memory. So whilst it might feel like there's a lot running all at once in practise there isn't. It's just a lot of threads being run one at a time for very brief periods of time.

However we all have multi core CPUs now. What's happening there is that the cores are all able to address memory (one way or another - things like Netburst, QPI and Hypertransport make things complicated). However, deep down in the electronics it is impossible to have two or more cores simultaneously accessing the same memory chip. Doing so would start breaking things, so a lot of care is taken to make sure that only one core at a time can access any one piece of physical memory. So memory access is, in a very fundamental way, serialised at the electronics level.

"Aha" I hear you say, "that would make everything really slow!". And you'd be right, so the hardware guys solve that with caches to help improve things.

So the result is that if two threads on separate cores try to write to the same address, the memory hardware forces them to take their turn. It's just pure luck as to which one goes first if the accesses are truly simultaneous. What you don't know in software is how this arbitration is done, so you can't rely on it. On one computer with a 32bit bus width you may get away with an int32 assignment being completed in one, uninterrupted operation, but probably not an int64 assignment. But on a 64bit bus width you may find the int64 assignment is completed uninterrupted.

So if you have a statement in one thread like a = b + c, and a = 10 in another thread and they run at exactly the same time (within less than 0.3 nanosecond of each other, corresponding loosely to a 3GHz clock rate), you don't know whether a will be 10, b+c, or some horrible blend of the two (because you don't know how the hardware is going handle both cores' writes, and you don't know how many hardware memory transactions are actually involved in "a =" anyway, and you don't know if a thread has been pre-empted by the scheduler part way through!). Regardless of what's happened the electronics will not complain at all (why should it? All it cares about is not catching fire and blowing up, and it's not the hardware's job to second guess what the software wants to do), so the OS and your program are oblivious to the fact that Things Have Gone Wrong.

That's why you need semaphores to serialise access to 'a' so that it ends up being at least either b+c or 10, and you'd use other program flow controls to ensure that the correct one of those is what ends up in a.

Without the semaphore you're taking a chance (0.3 nanosecond is very short), and on one computer you may never see a problem, but on another you might see it every time. You can't tell in advance what's going to happen. So for reliability you have to code it right.

Testing

Testing a program sharing data with semaphore controlled access is fraught and difficult. In fact you cannot prove that such a program is 'flawless' through testing alone. All you can do is assess the program design for correctness, and review whether the source code correctly implements the design. That's a hell of a lot of work, and it is difficult to get it right. It takes rigid discipline on the part of the programmer(s) to get it right.

There are other programming paradigms designed to alleviate this problem. Communicating Sequential Processes is one that I keep banging on about. It needs a complete mind shift to get into it, but the payback is that testing a program is far more likely to reveal latent problems in the source code. From a programmer's point of view it's a delight - you can relax into writing multi-threaded software and enjoy it, rather than sweating and fretting to ensure that all your shared data is accessed properly behind semaphores. It also scales very nicely :)

Links:

CSP on Wikipedia - a theoretical explanation of CSP

Java CSP on Wikipedia - has a good explanation of CSP at the programmer's level

In C you're a bit on your own. You'll end up writing your own library using pipe() and pselect() or similar. But well worth it I say.