Скачать или смотреть PAR: Critical Section

DEFINITION : A critical section protects access to shared data by allowing only one thread to execute the code within it at any point in time.

Why do we need critical section :

Running multiple threads of a single process simultaneously does not cause problems by itself. The problem arises when these threads are required to share memory in the form of variables or arrays or objects.

Concurrent accesses to these shared memory locations without synchronisation will lead to erroneous execution. Keeping this in mind, all accesses to these locations are protected. These protected regions in the code are called critical sections.

How are they protected?

Critical sections are characterised by atomic execution. Atomic execution means that only one thread can be executing its critical section. If any other process also wants to execute its critical section, it must wait until the first one finishes.

How to implement

Implementations of Critical Sections need to satisfy these three conditions :

Mutual Exclusion: Mutual exclusion implies that out of all threads only one can be in its critical section at any point of time. This can be implemented using various locking techniques.

Progress: When the critical section is not being executed by any thread, the next thread (if any) should be allowed to access its critical section.

Bounded Waiting: Once a thread requests critical section access, there is a limit on the number of threads that access their critical sections before this thread’s request is granted. After the limit is reached, this thread is allowed to execute its critical section code. This implies that there is no deadlock condition in which one thread holds the access to the critical section for infinite time.


Structure of critical sections :
Entry Point - responsible for locking all the access to these shared memory

{

Critical Section code

}

Exit - releases the lock to shared memory and
Remainder code


Example :

for( ii = 0; ii < 6 ; ii++)

A[ii+1] = a[ii] + 1 ---- 1

A[ii] = a[ii-1] + 1 ------ 2

Let us assume the ith iteration of the loop is delegated to the thread t_(i-1).

This implies that a[5] is being simultaneously written by threads t4 and t5 and also being read by t5 and t6. Hence we require CS
This would mean that a[5] is written by threads t4 and t5.


Let us have the two threads T1 and T2 which execute 1 and 2

T1 T2

A[ii+1] = a[ii] + 1 --- 1 A[ii] = a[ii-1] + 1 ----- 2

Here we cannot have T1 reading and T2 writing into a[ii] at the same time because we cannot guarantee which value will be read. In such cases, we make the access into shared memory a[ii] as a critical section.


Implementation :

The simplest implementation of critical sections is done using semaphores. For entrance, a thread should acquire a semaphore which it releases upon exit. Other threads are kept waiting until the semaphore is released but can gain control of the CPU and execute other code including the critical sections guarded by different semaphores.


Critical Sections in real life :

In the popular streaming service Netflix , with a basic subscription, only one person can stream videos at one point of time. The others should wait until the service is vacant.