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.