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 pi wants to get in critical section and no process is in critical section
then pi 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: pi 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:
0 comments:
Post a Comment