Race condition, Critical section & Atomocity

Describe the terms race condition, critical section & atomocity with examples

Race condition
      A situation where two or more processes are reading or writing some shared data and the final result depends on the exact ordering of events. 

Critical Section
     It is the part of the program where the shared memory is accessed or a critical section is group of instructions/statements or region of code that need to be executed atomically, such as accessing a resource (file, input or output port, global data, etc.).
In concurrent programming, if one thread tries to change the value of shared data at the same time as another thread tries to read the value (i.e. data race across threads), the result is unpredictable.The access to such shared variable (shared memory, shared files, shared port, etc…) to be synchronized. Few programming languages have built in support for synchronization.
It is critical to understand the importance of race condition while writing kernel mode programming (a device driver, kernel thread, etc.). since the programmer can directly access and modifying kernel data structures.

A simple solution to critical section can be thought as shown below,

acquireLock();
Process Critical Section
releaseLock();

A thread must acquire a lock prior to executing critical section. The lock can be acquired by only one thread. There are various ways to implement locks in the above pseudo code.
The three requirements for solving the critical section problem:

• Mutual Exclusion:  one process at a time gets in critical section.
  http://en.wikipedia.org/wiki/Mutex
• Progress:  if p_i wants to get in critical section and no process is in critical section
                  then p_i should be able to progress.

Progress is defined as the following: if no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in making the decision as to which process will enter its critical section next. This selection cannot be postponed indefinitely.A process cannot immediately re-enter the critical section if the other process has set its flag to say that it would like to enter its critical section.

• Bound wait:  p_i should be able to get critical section with some upper waiting time.

Example:
The Producer-Consumer Problem:
Producer:

while(true)
{
    Produce(nextp);
    while(counter == n);   //if buffer is full, wait
    buffer[in] = nextp;
    in = (in + 1) % n;     //mode by n
    counter = counter + 1;
}

Consumer:

while(true)
{
    while(counter == 0);  //if buffer is empty, wait
    nextc = buffer[out];
    out = (out + 1) % n;
    counter = counter - 1;
    Consume(nextc);
}

The problem occurred at sharing the same memory space, counter.
If both read and write counter at same time,  it will cause inconsistent.
e.g. Both got counter = 3
then producer update it into 4 then consumer writes it into 2.

Useful Links:
http://en.wikipedia.org/wiki/Critical_section

Atomicity:

In simple terms, atomicity is unbreakability, i.e. an uninterrupted operation. If two users issue a print command, each print should go in single attempt. If the printer driver is sending parts of data from two users, the printout will not be as expected. Hence, the printer driver must send the print command as unbreakable operation from one application at a time (in other words synchronize the access to printer).
Note that the data base terminology on atomicity would be different, yet the concept is same.
With an example we can understand the atomicity in programming well. Consider in a multi-threaded application, a function is incrementing a global/static variable,
count++; // count has permanent storage in RAM
The above statement can be decomposed into, atleast three operations.

1. Fetching count value
2. Incrementing count value
3. Storing the updated value

If a thread executing the function containing the above statement is fetching its value (say 2). It is possible that at this point of execution, the thread can be preempted and another thread may invoke the same function. Consequently, the value of count will be incremented to 3 by that thread. When the former thread is resumed, it still retains the previous value (2), instead of latest value (3), and ends up in writing back 3 again. Infact, the value of count should be 4 due to affect of both the threads.
Such kind of bugs are quite difficult to recreate and locate.
An example of atomic operation is instruction execution, usually an instruction feed to the execution unit can’t be stopped in the middle. Yet, a statement in high level language results in multiple instructions. It is the root cause of non-atomic operations.
 
Useful Links:
http://en.wikipedia.org/wiki/Atomic_action