Synchronization and Deadlock

Process Synchronization #

Processes and threads use shared memory/resources as they operate. Therefore, synchronization issues must be addressed. When multiple processes/threads access shared resources simultaneously (a race condition), problems can arise. Special rules to prevent this are called process (thread) synchronization.

Race Condition: A problem where the outcome varies depending on the order in which multiple processes/threads access shared resources simultaneously.
User-Mode Synchronization: Advantages in performance, limitations in functionality
- Critical Section (CS)
Kernel-Mode Synchronization: Advantages in functionality, limitations in speed
- Mutex-based, Semaphore-based

Reader-Writer Problem: Multiple readers can access simultaneously, but only one writer can.

If readers keep coming, writers might wait indefinitely.

Dining Philosophers Problem: Philosophers sit at a round table and must pick up both chopsticks on either side to eat.
1. If all philosophers pick up their left chopstick first and then try to pick up their right chopstick, no chopsticks remain, leading to indefinite waiting for everyone (a deadlock state).

Critical Section #

A code region that restricts access to a shared resource to only one process/thread at a time when multiple processes/threads attempt to access it simultaneously.

Critical Section in the Reader-Writer Problem: Book - Shared DB
Critical Section in the Dining Philosophers Problem: Chopsticks
Conditions for Solving the Critical Section Problem
- Mutual Exclusion: If someone enters the critical section, no one else can access it.
- Progress: A process/thread that has finished its work in the critical section is appropriately selected.
- Bounded Waiting: To prevent starvation, there's a limit on how long a process/thread can wait to enter the critical section after requesting access.
Software-Based Synchronization
- Peterson's Algorithm / Dekker's Algorithm: Usable only for two processes, can lead to busy-wait issues.
- Lamport's Bakery Algorithm: Usable for two or more processes.
Hardware-Based Synchronization
- Using Locks: A process must acquire a lock to enter, and releases the lock upon exiting the critical section.
  - Lock-based methods struggle with interrupt disabling in multi-processor environments due to efficiency concerns, thus performance cannot be guaranteed.

Semaphore #

A software tool for synchronization that manages the number of resources that can be accessed simultaneously. It's a variable concept stored in the kernel, with two atomic operations: P and V. P means test, functioning as acquire(), and V means increment, functioning as release().

When a process enters the critical section, the semaphore's value decreases via a P operation.
After completing its work and exiting the critical section, the semaphore's value increases via a V operation.

Busy-Wait Method: Checks for access availability by executing a loop.
Block-WakeUp Method: Upon request, the resource count is first decremented. If the resource count is 0 or less, the process is inserted into a waiting queue. Even if the work is completed and the count is incremented upon release, if the variable is still 0 or less, it means waiting processes exist, so one is popped from the left and woken up.
If the critical section is long, the Block-WakeUp method is advantageous; if short, Busy-Wait is better.
Counting Semaphore: Increments a count when processes/threads enter the critical section to maintain a certain number.
Binary Semaphore: A semaphore consisting only of 0 and 1, allowing only one process to enter the critical section. Also known as a mutex.
- Mutex: A shortened, easier-to-read English term. It's a locking mechanism based on the concept of acquisition/release.
Semaphore vs. Mutex Difference: A mutex is used for a single synchronization target, while a semaphore is used for one or more.
Deadlock can also occur with semaphores.

Monitor #

Only one process operates within a monitor at a time. It's a higher-level concept than a mutex, simplifying synchronization compared to semaphores because programmers don't need to explicitly code synchronization constraints like locking processes.

Deadlock #

In an OS, deadlock (a state of impasse) refers to a situation where requests for system resources are entangled. It's a scenario where a set of processes are blocked, waiting indefinitely for resources held by other processes.

Deadlock Conditions #

Mutual Exclusion: Only one process can use a resource at a time. Other processes must wait until the requested resource is released.
- If a philosopher holds one chopstick, no one else can use that chopstick.
Hold and Wait: A process holding resources does not release them while waiting for other resources.
- A philosopher waiting for the other chopstick does not release the one they are holding.
No Preemption: Resources cannot be forcibly taken away from a process while it is using them; they must be released voluntarily.
1. A chopstick picked up by a philosopher cannot be taken away by another philosopher.

Even if the above four conditions are met, it occurs rarely.
- Deadlock only has a probability of occurring when all four conditions are established.
It is critical in computer environments, and resolving errors caused by deadlock is difficult.

Deadlock Prevention #

If even one of the four deadlock conditions does not occur, deadlock will not happen. Therefore, prevention involves negating each condition to block the possibility of occurrence.

Solving Mutual Exclusion: Releasing a non-shareable state can lead to synchronization issues, making it practically impossible.
Solving Hold and Wait: A method where a process holding resources does not wait for others. If multiple resources are needed, the process requests resources only when it can acquire all of them, releasing any partially acquired resources. This can lead to reduced resource utilization, degraded performance, and starvation.
Solving No Preemption: If preemption is possible, it's not an issue for CPUs, but switching resources like printers can be problematic. It's only feasible for resources that allow Save&Restore.
Solving Circular Wait: There is more room for application compared to the previous three. Resources are numbered, and requests are made in ascending order, or resources are requested only in one direction. This also has the problem of reduced resource utilization.

Negating even one of the four conditions incurs costs. Therefore, it is best used in fields where the cost of system degradation is less than the cost of deadlock, such as military, medical, and aerospace sectors.

> Deadlock Avoidance Deadlock avoidance is based on the premise that deadlocks arise from incorrect granting of resource requests.

Safe State: A state where all resources requested by processes can be allocated to everyone sequentially without deadlock.
Safe Sequence: An order of resource allocation, execution, and termination that prevents deadlock.
- This implies the absence of cycles.
- Disadvantage: Implementation requires prior information, such as allocation capabilities, the number of available resources, and the number of resources requested by processes.
Circular-wait must be avoided through safe allocation. Incomplete allocation carries the risk of deadlock.
Banker's Algorithm: Applied when there are multiple types of resources. When a process requests resources, it checks in advance if allocating them would leave the system in a safe state, thereby avoiding deadlock.
- Disadvantage: Requires a fixed set of allocable resources and knowledge of maximum resource demands. Since it must always avoid unsafe states, resource utilization is low.

Deadlock Detection and Recovery #

The OS periodically checks for deadlock occurrences.
Shorter periods increase overhead, longer periods decrease recovery chances.
Detection Algorithms
- For Single Instance, use Resource-Allocation Graph.
- For Multiple Instances, use Banker's Algorithm.
Recovery Techniques
- Process Termination: Terminate all processes at once or one by one.
  - Terminate all deadlocked processes at once: All processes, even those in operation, are suspended, and intermediate results are discarded.
  - Terminate one by one, detecting/recovering from deadlock with a detection algorithm: Overhead issue.
- Resource Preemption: Select a victim process with the minimum preemption cost and take away its resources.

Ignoring Deadlock #

Based on the observation that deadlock is a rare phenomenon even when all four necessary conditions are met.
It is deemed inefficient to incur costs to handle rare deadlocks, so no action is taken against them.
If a deadlock occurs in the system, programmers respond by manually killing the processes.