Module 3_Process Synchronization and Deadlocks

Process Synchronization and Deadlocks

1. Overview

Synchronization is essential in concurrent programming to manage the access of multiple processes to shared resources effectively.
Deadlocks occur when two or more processes cannot proceed because each is waiting for the other to release resources.

2. Concurrency

2.1 Principles of Concurrency

Concurrency pertains to the execution of multiple processes simultaneously.
Requires effective communication and synchronization between processes to avoid conflicts.

2.2 Inter-Process Communication (IPC)

IPC mechanisms are needed to manage communication between concurrent processes effectively.
Common methods include message passing and shared memory.

3. Mutual Exclusion

3.1 Definition

Mutual exclusion ensures that only one process can access a shared resource at a time, preventing data inconsistencies.

3.2 Challenges

Managing mutual exclusion can be difficult, especially in concurrent environments, where processes may attempt to access the same resource simultaneously.

4. Critical Section Problem

4.1 Definition

A critical section is a segment of code in which a process accesses shared resources.
The challenge is to design a protocol ensuring that when one process is in its critical section, no other processes can enter.

4.2 Structure of a Process

Structure typically involves an entry section, critical section, exit section, and remainder section.

do {
    entry section;
    critical section;
    exit section;
    remainder section;
} while (true);

5. Algorithms for Mutual Exclusion

5.1 Basic Algorithm

A simple algorithm involves checking for a turn variable, where each process waits for its turn to enter the critical section.

5.2 Test-and-Set Instruction

A test-and-set instruction is an atomic operation that sets a variable and returns its old value, which is used to manage locks in critical sections.
```
boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = TRUE;
    return rv;
}
```

5.3 Compare-and-Swap Instruction

This operation atomically checks if a variable is equal to a specified value and swaps it if so.

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected) *value = new_value;
    return temp;
}

6. Semaphores

6.1 Definition

A semaphore is a synchronization tool that helps manage process access to shared resources.
It is characterized by atomic operations: wait() and signal().

6.2 Implementation

A semaphore implementation consists of maintaining a value associated with resource availability, and processes will wait or signal accordingly.

7. Deadlocks

7.1 Definition and Characteristics

A deadlock is a situation where processes are stuck waiting indefinitely for resources that are held by each other.
Deadlocks can occur under specific conditions: mutual exclusion, hold-and-wait, no preemption, and circular wait.

7.2 Resource Allocation Graphs

Used to visually represent the state of resources and processes, where edges indicate requests and allocations between processes and resources.

7.3 Deadlock Prevention and Avoidance

Prevention involves ensuring at least one of the necessary conditions for a deadlock cannot hold.
Avoidance uses information about maximum resource needs to ensure the system is always in a safe state.

7.4 Deadlock Detection

Deadlock detection algorithms periodically check for cycles in resource allocation graphs to identify deadlocks and facilitate recovery.

7.5 Recovery from Deadlocks

Recovery methods include aborting processes or preempting resources from certain processes to break the deadlock cycle.

7.6 Example of Deadlock Situations

Thread examples show how circular waits can lead to deadlocks, emphasizing the importance of resource management strategies.

8. Classical Synchronization Problems

8.1 Bounded Buffer Problem

This problem involves managing a fixed-size buffer between producer and consumer processes, ensuring synchronization using semaphores.

8.2 Readers-Writers Problem

Addresses the challenge of allowing concurrent reading while preventing simultaneous writing, usually implemented with semaphores.

8.3 Dining-Philosophers Problem

An example in which philosophers must share chopsticks (resources) without falling into deadlock, requiring careful resource allocation strategies.