Operating System Concepts: Critical Sections

Key Concepts in Critical Section Management

• Progress: If no process is in the critical section and there are processes waiting to enter, selection for entry cannot be indefinitely postponed.
• Bounded Waiting: There must be a limit on how many times other processes can enter their critical sections after an entry request is made.
  • Each process operates at non-zero speed, without assuming relative speeds among processes.

Critical-Section Handling Approaches

• Preemptive Kernel: Allows the current process to be preempted if it's in kernel mode.
• Non-Preemptive Kernel: Runs until the process exits kernel mode, blocks, or yields the CPU, effectively preventing race conditions in kernel mode.

Peterson’s Solution

• Algorithm designed for two processes sharing two variables: int turn and Boolean flag.
  • turn indicates whose turn it is to enter the critical section.
  • flag[i] indicates if process Pi is ready to enter its critical section (flag[i] = true).

Process Algorithm

• Each process sets its flag to true and indicates the turn of the other process.
• Continues in a loop until it enters the critical section, then resets its flag to false after exiting.

Requirements Validation

• Mutual Exclusion: Process Pi can enter the critical section only if either flag[j] = false or turn = i.
• Progress Requirement: Only processes in the entry section can participate in selecting the next process.
• Bounded Waiting: Each process cannot re-enter the critical section while another is waiting.

Synchronization Hardware

• Critical section code implementation is often supported by hardware.
• Locking critical regions prevents preemption; however, disabling interrupts is inefficient in multiprocessor systems.

Solutions with Locks

• Critical sections can be protected using locks:
  • A lock acquisition function ensures that a process can enter its critical section only when it successfully acquires the lock.

Atomic Instructions

• test_and_set instruction:

  • Atomically sets a variable to true and returns its original value, allowing for mutual exclusion.

• compare_and_swap instruction:

  • Atomically swaps values under a certain condition, ensuring controlled access to shared resources.

Bounded-Waiting with test_and_set

• Uses a waiting array to allow processes to communicate their readiness, ensuring mutual exclusion while only permitting bounded entry.

Mutex Locks

• A mutex lock provides a simpler way to manage critical sections:
  • A Boolean variable indicates if the lock is available.
  • Calls to acquire and release locks must be atomic, though this leads to busy waiting (spinlock).

Semaphore as Synchronization Tool

• Provides more sophisticated synchronization than mutex locks.
• Uses process and resource sets to manage requests and allocations, facilitating resource management and access control.

Resource Allocation Graph

• Visual representation helps analyze resource allocation and deadlock avoidance:
  • If the graph has no cycles, there is no deadlock.
  • If there's a cycle, the deadlock is possible, particularly if resources are singular per type.

Deadlock Handling Methods

• Deadlock Prevention: Ensures the system never enters a deadlock state.
• Deadlock Avoidance: Employs strategies to prevent situations leading to deadlocks.
• Deadlock Recovery: Allows entering a deadlock state but includes strategies for recovery.
• Many systems, including UNIX, choose to ignore deadlocks and assume they do not occur.