Definition
Concept
Critical section: code segment accessing shared resources. Concurrent processes: may execute critical sections simultaneously. Objective: prevent data inconsistency, ensure data integrity.
Scope
Scope: portion of program with potential conflicting access. Shared resources: variables, files, hardware devices. Protection needed to avoid interference.
Example
Example: incrementing shared counter. Without control: race condition leads to incorrect count. With critical section: controlled access preserves correctness.
Importance in Operating Systems
Concurrency Control
Operating systems: manage multiple processes/threads. Concurrency: simultaneous execution. Critical section: prevents conflicts in concurrent environments.
Resource Sharing
Shared resources: memory, I/O devices. Coordination essential to prevent corruption. Critical section ensures exclusive access.
System Stability
Failure to protect critical sections: causes race conditions, deadlocks, data corruption. System stability depends on effective synchronization.
Necessary Conditions for Critical Section
Mutual Exclusion
Only one process allowed in critical section at any time. Prevents concurrent conflicting operations.
Progress
Processes outside critical section cannot block others indefinitely. Ensures system makes progress.
Bounded Waiting
Limits waiting time for processes to enter critical section. Prevents starvation.
Race Condition
Definition
Race condition: multiple processes access shared data concurrently without synchronization. Result: unpredictable outcomes.
Causes
Causes: improper synchronization, missing mutual exclusion, timing-dependent errors.
Consequences
Consequences: data corruption, incorrect program behavior, system crashes.
Mutual Exclusion
Principle
Mutual exclusion: restricts simultaneous critical section access. Guarantees exclusive access to shared resources.
Implementation Goals
Goals: correctness, efficiency, fairness. Minimize overhead, avoid deadlock and starvation.
Techniques
Techniques: hardware support, software algorithms, operating system primitives.
Synchronization Mechanisms
Locks
Locks: basic synchronization tool. Acquire lock before critical section, release after. Ensures mutual exclusion.
Semaphores
Semaphores: integer counters with wait/signal operations. Binary semaphores enforce mutual exclusion.
Monitors
Monitors: high-level synchronization construct. Encapsulates shared variables, procedures, and synchronization.
Software Solutions
Peterson's Algorithm
Two-process mutual exclusion algorithm. Uses turn and flag variables. Guarantees mutual exclusion, progress, bounded waiting.
Lamport's Bakery Algorithm
Generalizes to n processes. Assigns numbers to processes; lowest number enters critical section. Ensures fairness.
Drawbacks
Software algorithms: rely on atomicity of read/write. Vulnerable to hardware interrupts, inefficiency in multiprocessors.
flag[0] = true;turn = 1;while (flag[1] && turn == 1) { /* busy wait */}/* critical section */flag[0] = false;Hardware Solutions
Test-and-Set Instruction
Atomic instruction: tests memory bit and sets it. Used to implement spinlocks.
Compare-and-Swap
Atomically compares memory with expected value, swaps if equal. Enables lock-free synchronization.
Disabling Interrupts
Prevents context switch during critical section by disabling interrupts. Effective but affects system responsiveness.
boolean test_and_set(boolean *target) { boolean rv = *target; *target = true; return rv;}Classical Algorithms
Bakery Algorithm
Ensures first-come, first-served access. Uses numbering system analogous to bakery tickets.
Dekker’s Algorithm
First solution for two-process mutual exclusion. Uses flags and turn variable to avoid deadlock/starvation.
Peterson’s Algorithm
Improved two-process algorithm. Simpler and more efficient than Dekker’s method.
| Algorithm | Processes Supported | Key Feature |
|---|---|---|
| Dekker's Algorithm | 2 | Flag and turn for mutual exclusion |
| Peterson’s Algorithm | 2 | Simplified flag/turn mechanism |
| Bakery Algorithm | n | Number assignment for fairness |
Deadlock and Starvation
Deadlock
Deadlock: processes wait indefinitely for resource. Causes system halt. Critical section design must avoid circular waits.
Starvation
Starvation: some processes never enter critical section. Caused by unfair scheduling or priority inversion.
Prevention Strategies
Strategies: enforce bounded waiting, use fair locks, priority inheritance protocols.
Critical Section in Practice
Operating System Primitives
OS provides mutexes, semaphores, condition variables. APIs: pthread_mutex_lock, WaitForSingleObject, etc.
Multithreading Libraries
Libraries implement critical sections with locks, atomic operations. Examples: POSIX threads, Java synchronized blocks.
Performance Considerations
Synchronization overhead impacts performance. Techniques: lock-free programming, fine-grained locking.
Summary
Core Concept
Critical section: essential for safe concurrent access to shared resources.
Implementation
Multiple solutions: software algorithms, hardware instructions, OS primitives.
Challenges
Deadlock, starvation, race conditions must be addressed for robust systems.
References
- E. W. Dijkstra, “Cooperating Sequential Processes,” Programming Languages, vol. 1, 1968, pp. 43-112.
- A. S. Tanenbaum, Modern Operating Systems, 4th ed., Prentice Hall, 2014, pp. 295-320.
- M. Herlihy and N. Shavit, The Art of Multiprocessor Programming, Morgan Kaufmann, 2012, pp. 75-110.