Jump to content




Recent Status Updates

View All Updates

Binpress - Cut your development time and costs in half
Photo
- - - - -

Critical Section and Locks with C

context switch

  • Please log in to reply
4 replies to this topic

#1 fkl

fkl

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 415 posts

Posted 01 May 2011 - 02:53 PM

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
  • 0

#2 Alexander

Alexander

    I do have 9 lives, you know.

  • Moderator
  • 3,856 posts
  • Location:Vancouver, Eh! Cleverness: 200
  • Programming Language:C, C++, PHP, Assembly

Posted 02 May 2011 - 03:00 AM

Ah yes - very informative written tutorial.

One thing I think I should mention, is that the default mutex initialisation can be replaced with a function to accept attributes (pthread_mutex_init(3)), which could provide the type of mutex (recursive checking, error detection, deadlocking...), process sharing boundaries, protocols for priority in the circumstance a thread with higher priority were to request a mutex to name a few.

  • 0
Be sure to check out the new site additions - brought to you by your friendly CODECALL staff-person.
If a suggested code/method fails, informing us is less important than telling us why or what errors had occurred.

#3 fkl

fkl

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 415 posts

Posted 02 May 2011 - 10:45 AM

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

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

  • 0

#4 fkl

fkl

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 415 posts

Posted 14 July 2011 - 10:35 AM

A good follow up to writing a basic mutex lock using in line assembly

http://forum.codecal...c-assembly.html
  • 0
Today is the first day of the rest of my life

#5 zooro

zooro

    CC Lurker

  • New Member
  • Pip
  • 3 posts
  • Location:UAE
  • Programming Language:C, Java, C#, (Visual) Basic
  • Learning:Java, C#

Posted 02 May 2012 - 02:43 AM

I really like this Post .. it is really informative with good code example ....

I know this post had posted one a year back ....

But if you could please explain how we can use Test and Set method to solve the crtical section problem in the same code example u posted above ..will be very helpful!! :)

Thank you ,,,
  • 0





Powered by binpress