Critical Sections and Protection

Before we dive into the topic, let us try to set the context for Critical Sections. In an Operating System,

1. There are, often, a number of processes that are ready to be executed at a particular instant of time.
2. These processes require various resources for their execution.
3. Some of these resources may be shared between multiple processes. These resources may be variables, memory sections, peripherals, etc.
4. Such shared resources are called critical resources and the code sections making use of such resources are called critical sections.

One thing to keep in mind with these shared resources is that they should not be used simultaneously by multiple processes. Why? Let us understand with some examples

Critical Sections Example 1:

Let us consider an example scenario to understand it:Consider two C programs, Task_A and Task_B, in a round-robin system.–  Task_B outputs the message “I am task_B” and Task_A outputs the message “I am Task_A.”– In the midst of printing, Task_B is interrupted by Task_A, which begins printing.– The result is the incorrect output: I am I am Task_ATask_B– The above issue arises when the display terminal is shared by the two resources.The display terminal is a critical resource and the code to print the statements are thus critical section.

Critical Sections Example 2:

Consider another example. An example of a water tank.

• We design a system to read the time and the corresponding water level in the tank.
• The system also has a button which the user can press.
• This button switches ON the display and prints on the display the time and the level.

Now, say we have a task to read the level that periodically reads the levels and stores is:

void level_task()
{
    time = clockUpdate();
    level = sensorRead();
    ...
}

And the button task is as follows:

void button_task()
{
    print(time);
    print(level);
}

 Since the user can push the button at any time, the button task will have a higher priority.Assume the situation where the CPU is executing the level_task() and is currently executing time = clockUpdate();Just before the completion of execution of this line, the user presses the button. The control will jump to the button_task(). Now, in the variable ‘time‘ we have the current time but in the variable ‘level‘ we have the old level 

Time	Level
6	500
7	600
8	700
9	800
10	900

 If the time read was 8, the level would still be pointing to 600 which is wrong. So, what the user sees is:Time = 8Level = 600,When in reality, it should beTime = 8Level = 700In this example,

time = clockUpdate();
level = sensorRead();

inside the level_task() is the critical section. Such sections need to be protected with proper mechanisms to avoid any issues.

One Final Example:

Now, think of a situation where we have two processes and these processes are using the same variable “a”. They are reading the variable and then updating the value to the variable and finally writing the data in the memory.

SomeProcess()
{
    ...
    read(a) //instruction 1
    a = a + 5//instruction 2
    write(a) //instruction 3...       
}

In the above, you can see that a process after doing some operations will have to read the value of “a”, then increment the value of “a” by 5 and at last write the value of “a” in the memory. Now, we have two processes P1 and P2 that needs to be executed. Let’s take the following two cases and also assume that the value of “a” is 10 initially

1. In this case, process P1 will be executed fully (i.e. all the three instructions) and after that, the process P2 will be executed. So, the process P1 will first read the value of “a” to be 10 and then increment the value by 5 and make it to 15. Lastly, this value will be updated in the memory. So, the current value of “a” is 15. Now, the process P2 will read the value i.e. 15, increment with 5(15+5 = 20) and finally write it to the memory i.e. the new value of “a” is 20. Here, in this case, the final value of “a” is 20.
2. In this case, let’s assume that the process P1 starts executing. So, it reads the value of “a” from the memory and that value is 10(initial value of “a” is taken to be 10). Now, at this time, context switching happens between process P1 and P2. Now, P2 will be in the running state and P1 will be in the waiting state and the context of the P1 process will be saved. As the process P1 didn’t change the value of “a”, so, P2 will also read the value of “a” to be 10. It will then increment the value of “a” by 5 and make it to 15 and then save it to the memory. After the execution of the process P2, the process P1 will be resumed and the context of the P1 will be read. So, the process P1 is having the value of “a” as 10(because P1 has already executed the instruction 1). It will then increment the value of “a” by 5 and write the final value of “a” in the memory i.e. a = 15. Here, the final value of “a” is 15.

In the above two cases, after the execution of the two processes P1 and P2, the final value of “a” is different i.e. in 1st case it is 20 and in 2nd case, it is 15. What’s the reason behind this?The processes are using the same resource here i.e. the variable “a”. In the first approach, the process P1 executes first and then the process P2 starts executing. But in the second case, the process P1 was stopped after executing one instruction and after that the process P2 starts executing. And here both the processes are dealing on the same resource i.e. variable “a” at the same time. This is the critical section of the process. So, there must be some synchronization between the processes when they are using shared resources.The shared resources can be used by all the processes but the processes should make sure that at a particular time, only one process should be using that shared resource. This is called process synchronization. Now that we understand what critical sections are, how do we apply process synchronization and protect them? Well, there are two very popular ways:

1. Mutex
2. Semaphores

Mutex for protecting Critical Sections:

The first way to protect Critical sections is to use Mutex.Mutex is short for Mutual ExclusionThe mutex behaves like a token (key) and it restricts access to a resource. If a task wants to access the protected resource, it must first acquire the token. If it is already taken, the task could wait for it to become available. Once obtained, the token is owned by the task and is released once the task is finished using the protected resource.A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects.

Real-life mutex analogy

Imagine a company office that has three employees and one company car. The shared resource, in this case, is the car and the key to the car is the mutex. If an employee wants to use the car, he has to obtain the key (mutex). If an employee has already taken the key and is using the car, all other employees have to wait for the key to be returned to the office.The car here is a critical resource and at any given time only one employee may use it. The protecting mechanism to ensure only one person uses the car is the key, or Mutex in case of programs.The mutex behaves like a token (key) and it restricts access to a resource. If a task wants to access the protected resource it must first acquire the token. If it is already taken, the task could wait for it to become available. Once obtained, the token is owned by the task and is released once the task is finished using the protected resource.A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects.Consider another example of a bathroom key owned by an urban coffee shop. At the coffee shop, there is one bathroom and one bathroom key. If you ask to use the bathroom when the key is not available, you are asked to wait in a queue for the key. By a very similar protocol, 

a mutex helps multiple tasks serialize their accesses to shared global resources and gives waiting tasks a place to wait for their turn.

To summarize with an example, here’s how to use a mutex:

/* Task 1 */
   mutexWait(mutex_mens_room);
      // Safely use shared resource
   mutexRelease(mutex_mens_room);

/* Task 2 */
   mutexWait(mutex_mens_room);
      // Safely use shared resource
   mutexRelease(mutex_mens_room);

For our water level example, using mutex can be as follows:

mutex_t print_mutex; //create a mutex named print_mutex

void level_task()
{
    mutex_lock(&print_mutex);  //lock the mutex
    time = clockUpdate();
    level = sensorRead();
    mutex_unlock(&print_mutex);  //unlock the mutex
    ...
}

void button_task()
{
    mutex_lock(&print_mutex);  //lock the mutex
    print(time);
    print(level);
    mutex_unlock(&print_mutex);  //unlock the mutex
}

void main()
{
    mutex_init(&print_mutex);
    ...
}

Ofcourse, this is just an example. Different Operating Syntaxes will have different API calls and prototypes for creating, initializing, locking and unlocking a mutex.

Semaphores for protecting Critical Sections:

Another way to protect Critical Sections is through the use of Semaphores.A semaphore is a signaling mechanism. It is available in all real-time operating systems with some subtle differences in its implementation. Semaphores are used for synchronization (between tasks or between tasks and interrupts) and managing allocation and access to shared resources.The correct use of a semaphore is for signaling from one task to another.  Tasks that use semaphores either signal or wait—not both. For example, Task 1 may contain code to post (i.e., signal or increment) a particular semaphore when the “power” button is pressed and Task 2, which wakes the display, pends on that same semaphore. In this scenario, one task is the producer of the event signal; the other the consumer.A semaphore usually gives access or restricts access to a resource depending on how it is set up.There are two atomic operations in particular that are used for modifying the value of a semaphore and they are wait() and signal(). Mostly they are used for signaling one task to another.In the water level example, we can make use of semaphores as well as shown below:

semaphore print_sem; //create a mutex named print_mutex
void level_task()
{
    semaphore_wait(&print_sem);  //lock the mutex
    time = clockUpdate();
    level = sensorRead();
    semaphore_signal(&print_sem);  //unlock the mutex
    ...
}
void button_task()
{
    semaphore_wait(&print_sem);  //lock the mutex
    print(time);
    print(level);
    semaphore_signal(&print_sem);  //unlock the mutex
}
void main()
{
    semaphore_init(&print_sem);
    ...
}

Conclusion:

This post introduced to Critical Sections and the issues related to it. We also looked at the solutions using mutex and semaphores. In the next post, we will discuss mutexes and semaphores in more details.

📖 Related: Mutual Exclusion in RTOS: Mutexes, Critical Sections, and Atomics