Race Condition
6

This article has been co-authored by Aakriti

Dealing with race conditions is an important aspect of Operating System Design. In this article, we attempt to introduce the problem of race condition to our readers.

So what is a Race Condition?

Take a look at the program below, better yet try to execute it. (It has been tested on a linux machine using gcc. You might need to change certain aspects of it depending upon the tools at your disposal).



    #include 
    #include 
     
    void *inc_x(void  *x_void_ptr)
    {
    int i,*x_ptr = (int *)x_void_ptr;
    for(i=0;i<50000;i++)
    {
            ++(*x_ptr);
    }

    printf("Thread Two finished!\n");
    
    return NULL;
    }

    int main()
    {

    int i,x = 0;
        /* show the initial values of x and y */
    printf("x: %d\n", x);

    /* this variable is our reference to the second thread */
    pthread_t inc_x_thread;

    if(pthread_create(&inc_x_thread, NULL, inc_x, &x)) {

    fprintf(stderr, "Error creating thread\n");
        return 1;
    }

    for(i=0;i<50000;i++)
    {
        x++;
    }

    printf("Thread One finished!\n");

    if(pthread_join(inc_x_thread, NULL)) 
    {
        fprintf(stderr, "Error joining thread\n");
        return 2;
    }

    printf("x: %d\n", x);

    return 0;
    }


It can be compiled in linux using gcc by the following command:


gcc pThreads.c -lpthread

The above program has two threads of execution. One is the main thread, another one is the thread created using pthread API. Both threads try to increment the value of a shared variable x.

It gives different output on each run! Below are the outputs for three independent runs :

x: 0 
Thread Two finished!
Thread One finished! 
x: 90476


x: 0
Thread One finished!
Thread Two finished!
x: 89713

x: 0
Thread Two finished!
Thread One finished!
x: 94006

This is a simple enough program, where we are trying to raise the value of 'x' to 100,000 using 2 threads in parallel. But the result is way off and different for subsequent runs!

What is the reason of this indeterministic behaviour?

This is an example of race condition.

Wikipedia defines Race Condition as

"A race condition or race hazard is the behaviour of an electronic or software system where the output is dependent on the sequence or timing of other uncontrollable events. The term originates with the idea of two signals racing each other to influence the output first".

In this case variable 'x' is shared by the two threads, and they race each other to increment its value first.

Even then, one might ask, since both the threads are just adding 1 to the value of 'x', how does it matter which does it first? The answer anyway should be the same. It's still not clear why the result isn't 100,000 as expected.

To answer this, you must understand the notion of an atomic operation. It is an operation that happens indivisibly and cannot be interrupted leading to a partial completion. For example, there are a few assembly language instructions which are atomic like atomic-read, atomic-write, test-and-set, compare-and-swap, etc.

If incrementing 'x' in our case, was an atomic operation we would have always got the same result i.e. 100,000. But (un)fortunately, that is not the case here. This is because 'C' is an example of a high level language, and does not have one to one instruction mapping with the low level assembly language.

(Although this is highly architecture dependent, your code should be such that it has universal aplicability.)

The simple 'C' statement 'x++' in this case, is first broken down into assembly level instructions and the processor executes it at that level of granularity, instruction by instruction.

In this case, the C statement would roughly be translated to:

LD : load x into a register INC: increment register value by 1 STR: store register value into x

In my machine, x++ instruction in 'C' translates to:

    movl    20(%esp), %eax
    addl    $1, %eax
    movl    %eax, 20(%esp)

Here 20(%esp) is the location of 'x' and %eax is an x86 register. You can generate the assembly code using:


gcc pThreads.c -lpthread -S.

When two or more threads run in parallel on a single processor, what actually happens behind the scene is time sharing enabled by context switching. The processor executes instructions for one thread (or process) for some time, stops and saves intermediate results and then starts executing instructions for some other thread. Based on the scheduling algorithm followed, it can select the next thread (or process) to run.

So, when two threads simultaneously try to execute 'x++' instruction, what they are doing is issuing three assembly instructions each. The thread running these three instructions might get context switched out in between for the execution of instructions issued by the other thread.

Consider this particular scenario, say the current value of x is 380. Now both threads issue the instructions to increment 'x' at the same time. Processor juggles between the two processes as follows:

Possible execution sequence

At the end of this particular case, the final value of 'x' is 381 as opposed to 382. Thread two overwrites the update made by thread one. Hence, for the above 'C' program, different runs produces different results as the context switching between processes in indeterminate. Hence in this case, the resultant value of 'x' would always be less than or equal to 100,000. We leave it for the reader to verify that the value can not be greater!

In this article, we have learnt what is a race condition and what are its consequences. Following articles will deal with solutions of the problem posed here. Is it possible to solve this problem through software based solutions? Or do you need hardware support for this? What is the mathematics behind the solution?

Stay tuned!


The author of this article is Mohit Dhingra. Here is Mohit Dhingra's bio:

I am Masters by Research student at Indian Institute of Science, Bangalore. I am basically a computer systems guy and have also worked on applications of theoretical computer science. I have been teaching OS, Algorithms among other subjects to undergrad students on weekends.


  • 0.00
    vishnu Posted

    Good read.These type of thread implementations on a software must include mutexes or semaphores unless we don't want these race conditions.


  • 82.77
    Adit Posted

    Interesting article!!


Signup for free to share your opinion. Already have an account? Sign in to post opinion