Synchronization & Deadlocks

The Critical Section Problem

The Critical Section is the portion of the code in the program where shared variables are accessed and/or updated.

• Race around Condition – The final output of the code depends on the order in which the variables are accessed.
• Mutual Exclusion – If a process Pi is executing in its critical section, then no other process is allowed to enter into the critical section.
• Progress – If no process is executing in the critical section, then the decision of a process to enter a critical section cannot be made by any other process that is executing in its remainder section.
• Bounded Waiting – There exists a bound on the number of times other processes can enter into the critical section after a process has made a request to access the critical section and before the request is granted.

Synchronization Tools

Tools used to manage concurrent access to shared data:

• Semaphore : A protected variable or abstract data type used to lock the resource being used. Binary semaphores take only 0 and 1. Counting semaphores can range over an unrestricted domain.
• Mutex : Provides mutual exclusion. Either producer or consumer can have the key (mutex) and proceed with their work. Only one thread can work with the entire buffer at any point of time.

Deadlock Handling

There are three ways to handle deadlock:

• Deadlock prevention or avoidance: The idea is to not let the system into a deadlock state. Banker’s algorithm is used for deadlock avoidance.
• Deadlock detection and recovery: Let deadlock occur, then do preemption to handle it once occurred.
• Ignore the problem all together: If deadlock is very rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take.

Banker’s Algorithm

Banker’s algorithm is a deadlock avoidance algorithm. It is named so because this algorithm is used in banking systems to determine whether a loan can be granted or not. When a new process is created, it must specify the maximum instances of each resource type that it may need.