Critical Section and Locks with C

Though theoretically taught well in operating systems courses, and used pretty often in multithreaded programs, I have found many people to struggle with these concepts, so I thought of assembling up a page.

I will write a short code e.g. describing what a critical section is, what can go wrong exactly unless we protect it and will use c mutex locks to resolve the problem. It is the part in italics that I find most people messed up with.

Every program when loads into memory become a process. Each process has various places to store data depending upon their type. Let us take the example of global variables which are stored in data segment. We create multiple threads from this process. Thread is simply a new sequence of executing instructions. With each thread certain sections of memory are newly created for e.g. each thread has a separate calling stack. However, data segment remains the same.

Now suppose I have a function inside which I am accessing a global variable

 int x = 5;  // This is global and declared outside of any function at file scope


void thread_function(void)

{

    if (x < 6)    // instruction 1 – for reference latter in text

      x++;         // instruction 2

    else

      printf(“x is out of range\n”);

}

Say we have a main which calls above function. Also we create a thread which starts with above function. Both will complete their execution. Can you guess the output?

The first one to enter the thread will increment x by one (now it is 6) and the second will print “out of range” right?

Wrong – It MAY turn out that way, but there is no guarantee and you cannot count upon this behavior.

The correct answer would be that it is unpredictable. Why? Because you would never know the order of scheduling of main and the other thread. Let me elaborate.

To OS, each thread has its own small time slice called quantum to share CPU for execution. So main and the other thread each will have its turn. It is possible that main has executed its part until instruction 1 and its quantum expired. OS transferred the control to other thread which executed, found x to be 5, incremented it and went on.

So when main comes back again i.e. is scheduled again to continue from where it left (after instruction 1), it is not going to check if x<6 since that was done previously and found true. It will only proceed to increment x which is already 6 as incremented by other thread. This would result into new value of x which is 7.

Please note that above will not always happen. But it can and it probably would happen any time so we cannot write code which has a chance of running into this situation.

Some points to be clear about:
- x is a shared (global) variable i.e. a single copy accessible by both threads.
- What problem did occur? The code was written with the intention that x would never exceed 6. But we just saw that it can in fact attain any value i.e. if there are 10 threads which expired after instruction 1, x would reach 6+10 = 16.
- The above code was accessing and modifying x. Had we be just printing or using x, there can never be such a problem.

For the reasons described above the code segment

 if(x < 6)

   x++;

is called a critical section. The precise definition would be “any consecutive instructions which should always be executed without switching context (transferring control to another thread) is a critical section”.

If we look at the root of this problem, it is because the if statement and the increment statement are not a single unit or atomic for OS. An atomic instruction is one which is guaranteed by the OS to be executed without any context switch.

For this purpose we protect the critical section with some kind of a lock. Mutex is a common usage and it’s header file and syntax in C pthread library is as follows:

 #include <pthread.h>


pthread_mutex_t var=PTHREAD_MUTEX_INITIALIZER;


pthread_mutex_lock(&var);  // lock the critical section


if(x < 6)

   x++;

pthread_mutex_unlock(&var); // unlock once you are done

We create a mutex variable, acquire the lock before entering critical section and once done, release the lock. Obviously we cannot prevent the Operating system from transferring control to another thread. So if we are in critical section and have acquired the lock, no other thread would be able to get it unless it is free. This means that if main acquired lock and its quantum expired, the other thread came along, tried to acquire lock and got hanged in there until the lock is released by main. So other thread will waste its quantum, main’s turn will come back which finishes its execution and releases lock. Other thread will only be able to acquire lock then which pro grammatically means it will only return from the pthread_mutex_lock function then.

This is a waste of cycles but it only happens when a threads quantum expires in the middle of a critical section. So still the loss might not be much. Better yet, there are api’s such as

 pthread_mutex_trylock(&var)

which does not attempt to acquire lock but rather checks if the lock is free. So we can try lock first and if it fails, we do some other useful work and come back later. If it succeeds we call the actual lock function and proceed ahead.

For a detailed code sample take a look at
Common threads: POSIX threads explained, Part 2

That's true. Thank you for adding to that. The init API sure gives a lot of control and choice compared to static macro which only initializes to defaults.

Moreover, there is one scenario in which the macro is essential

Quote

Static initializers are usually more efficient than pthread_mutex_init, and they are guaranteed to be performed exactly once before any thread begins execution.

Quoted from Unix Systems Programming - Communication, Concurrency and Threads by Robins and Robins. Example 13.2.

So basically if we have multiple threads creating the mutex, the macro is guaranteed to be executed exactly once and no more, pretty much similar to initialization of static variables i.e. static int j = 4; initializes only once and ignores subsequent calls.

Edited by fayyazlodhi, 02 May 2011 - 10:47 AM.
grammatical mistake