This short article is about thread synchronization. It will examine the matter under the following headings: Race Condition, Mutex Locks, Critical Section Problem, Solutions to Critical Section Problem, and Deadlock & Starvation.

Race Condition

“A thread is a flow of execution through the process code, with its program counter..., system registers which hold its current working variables, and a stack which contains the execution history[1]”.

A race condition can be defined as the behavior of an electronic, software or another system, in which the output depends on the sequence or timing of uncontrollable events.This term refers to the idea of two signals competing to influence the output first. When events do not occur in the order intended by the programmer, it becomes a bug.

A critical section is where shared variable scan be accessed. A race condition may occur inside a critical section. In a critical section of code, multiple threads execute the code concurrently, and the sequence in which each thread executes the code can make a significant difference to the result[2].

Semaphore is a signalling mechanism of an integer variable that is shared between threads and used to solve the critical section problem and to accomplish process synchronization in the multiprocessing environment.Semaphore enables multiple processes to be managed with simple integer values.Semaphore uses two atomic operations: wait() and signal() for process synchronization.

Mutex Locks

Mutex lock is a simplified version of semaphore. It is a shared variable that can be in one of two states: unlocked or locked.If a process or thread needs access to the critical region, it calls mutex lock.

If the mutex is unlocked the call succeeds and the calling thread is free to enter the critical region.If the mutex is locked, the calling thread is blocked until the thread in the critical region is finished and calls mutex unlock. When multiple threads are blocked on the mutex, one of them is selected randomly and allowed to acquire the lock[3].

There is some vagueness between binary semaphore and mutex. The use cases of mutex and semaphore are different. Because of their implementation similarity, mutex would be referred to as a binary semaphore.

Mutex is a locking mechanism created to synchronize access to a resource. Only one task can obtain the mutex which means that only that process can release the lock (mutex).

Semaphore is a signalling mechanism; an interrupt is activated upon which an interrupt service routine (ISR) signals the call processing task to wake up[4].

Critical Section Problem

A critical section is a part of the code where shared data can be manipulated and a possible race condition may occur. The critical section problem is to create a procedure where processes can synchronize their activities to jointly share data.

Following conditions are required to deal with critical section problem:

• Mutual exclusion–only one process is active inside the critical section.
• Progress–programs will jointly decide which process will get inside a critical section.
• Bounded waiting–how long a program must wait before it can get inside critical section[5].

Race Condition, mutex lock and critical section problem which were discussed in above paragraphs are demonstrated and explained below.

This program will show what is happening when mutex lock is not used.

As per Figure 2.2,we can see that race condition starts when both threads t1 and t2 race towards the shared variable “x”. Both threads entering now the critical section of the code at line 15.
Without the lock,both treads can write in the accumulated register at the same time which will affect the result.

This behavior is noticeable in Figure 2.3 below.

Figure above shows that not a single result is this same and is far from the expected outcome of 2000000. The result depends on which thread gets to the shared variable first (line 7, Figure 2.2) and then which is going to be executed first.
Highlighted in yellow is the moment when two threads entered the critical section at the same time.

Solutions to Critical Section Problem

There are two types of solutions to the critical section problem:

• Hardware solutions
• Software solutions

Hardware solutions are using memory barriers, compare-and-swap operations, and atomic variables[5].

A memory barrier is a type of instruction that makes a central processing unit (CPU) or compiler enforce an ordering constraint on memory operations issued before and after the barrier instruction[6].

“Compare and swap operation compares the value of a variable with an expected value, and if the values are equal then swaps the value of the variable for a new value[7].”

The atomic operation takes place when two operations running in parallel, a processor reads and writes a location during the same data transmission, and until this operation is completed, another input/output process cannot perform memory reading or writing tasks[8].

Software solutions are using mutex locks, semaphores, monitors, and condition variables.The code below demonstrates the use of mutex locks to address the critical section problem.

The code in Figure 2.4is almost the same as in Figure 2.2 with one significant difference – mutex lock.
Mutex lock() was introduced just before threads can enter the critical section (line 15 of the code) and then mutex unlock() was added at the end of the critical section.

This means that threads t1 and t2 still racing for that shared variable (line 11) but then whichever thread gets first into the critical section then it locks it and no other thread can be executed until that first one unlocks the critical section.

Figure 2.5 below show the considerable impact of the mutex locks.

Figure 2.5 shows that all results are the same and with the expected outcome of 2000000. Thread synchronization took place by the use of mutex.

Deadlock & Starvation

Deadlock and starvation are conditions where processes demanding a resource have been deferred for a long time but there are differences between these conditions.

Deadlock takes place when several processes hold a resource and wait to acquire a resource that is held by some other processes.
Figure 2.6 illustrates the deadlock situation.

Four conditions are required for the deadlock to take place:

• Mutual exclusion–one process at a time can use a resource,and if another process needs to access the same resource, then it must wait until the other process releases it.
• Hold and Wait–a process must hold a resource and wait to obtain another resource that is held by another process.
• No Preemption–a process that holds the resources must release them voluntarily when it has completed its task.
• Circular wait–a process must circularly wait for resources as per Figure 2.6.

Starvation happens when processes with high priorities constantly use resources, which prevents low priority processes from obtaining them or when a process is never given the resources it requires for execution because of faulty resource allocation judgments[9].

I hope that you have enjoyed this post, please let me know what you think about it in the comments section below.

If you wish to study thread synchronization in depth then here are the sources I used to create this post:

[1] Tutorialspoint.com. n.d. Operating System - Multi-Threading. [online] Available at:https://www.tutorialspoint.com/operating_system/os_multi_threading.htm [Accessed 3 December 2021].
[2] Barnes, R., 2018. Race Condition, Critical Section and Semaphore. [online]Tutorialspoint.com. Available at: section-and-semaphore> [Accessed 15 November 2021].
[3] Tanenbaum, A.S. and Bos, H., 2015. Modern operating systems. 4th ed. Pearson, pp.135,pp850.
[4] GeeksforGeeks. 2021. Mutex vs Semaphore - GeeksforGeeks. [online] Available at:https://www.geeksforgeeks.org/mutex-vs-semaphore/ [Accessed 6 December 2021].
[5] Silberschatz, A., Galvin, P. and Gagne, G., 2018. Operating system concepts. 10th ed.
Hoboken, N.J.: Wiley, pp.55, pp.106-110, pp.287.
[6] En.wikipedia.org. n.d. Memory barrier - Wikipedia. [online] Available at: lso%20known,and%20after%20the%20barrier%20instruction.> [Accessed 20 November 2021].
[7] Jenkov, J., 2021. [online] Tutorials.jenkov.com. Available at:http://tutorials.jenkov.com/java-concurrency/compare-and-swap.html [Accessed 20 November 2021].
[8] Techopedia.com. 2011. What is an Atomic Operation? - Definition from Techopedia.[online] Available at: https://www.techopedia.com/definition/3466/atomic-operation[Accessed 20 November 2021].
[9] www.javatpoint.com. n.d. Difference between Deadlock and Starvation - javatpoint.[online] Available at: https://www.javatpoint.com/deadlock-vs-starvation [Accessed 21 November 2021].

Header picture thanks to the https://pixabay.com/images/id-4854847/