L-3.4: Critical Section Problem | Mutual Exclusion, Progress and Bounded Waiting | Operating System
Understanding Critical Sections in Concurrent Programming
Definition and Importance of Critical Sections
- A critical section is a part of a program where shared resources are accessed by multiple processes, emphasizing the need for synchronization.
- Cooperative processes share common resources such as code, memory, or variables, which necessitates careful management to avoid conflicts.
Structure of Programs with Critical and Non-Critical Sections
- In programming (e.g., C), the code is divided into critical and non-critical sections to manage resource access effectively.
- Each program (P1 and P2) contains both sections; critical sections hold shared variables while non-critical sections contain independent code.
Managing Shared Resources
- Common variables between programs should be placed in the critical section to prevent race conditions during execution.
- Non-critical sections can operate independently without interference since they do not rely on shared resources.
Race Conditions and Synchronization
- Race conditions occur when multiple processes attempt to modify shared variables simultaneously, leading to unpredictable results.
- To prevent race conditions, synchronization mechanisms must be implemented so that only one process can access the critical section at a time.
Synchronization Mechanisms
- Various methods exist for synchronization, including semaphores, monitors, lock variables, and Test-and-set locks (TSL).
- Before entering the critical section, programs must execute an entry section that ensures no other process can enter simultaneously.
Entry and Exit Protocols
- The entry protocol acts like a lock on a house; it prevents unauthorized access until certain conditions are met.
Understanding Process Synchronization
The Importance of Following Rules in Critical Sections
- Processes must execute the entry section before entering the critical section to prevent race conditions. If this rule is not followed, incorrect data may be generated.
- Various solutions exist for process synchronization, and while many methods are provided by researchers, one can also design their own synchronization mechanisms.
Conditions for Effective Synchronization
- Any synchronization mechanism must fulfill four essential conditions:
- Mutual Exclusion
- Progress
- Bounded Wait
- No assumptions about hardware or speed.
These conditions ensure that the solution is robust and effective.
- Among these four rules, Mutual Exclusion and Progress are primary rules that must be adhered to strictly; failure to do so undermines the effectiveness of the solution.
Exploring Mutual Exclusion
- Mutual Exclusion ensures that if one process (P1) is executing in the critical section, another process (P2) cannot enter until P1 exits, similar to a locked washroom scenario where only one person can use it at a time. This prevents simultaneous access to shared resources and maintains data integrity.
- If both processes attempt to enter the critical section simultaneously without proper control mechanisms in place, it results in a violation of mutual exclusion, indicating an inadequate solution for synchronization.
Understanding Progress in Synchronization
- Progress refers to ensuring that once a process has executed its non-critical code and wishes to enter the critical section, it should be able to do so as long as no other processes are currently executing within that section.
Understanding Progress in Critical Sections
Definition of Progress
- Progress refers to the state where no process is currently using the critical section, allowing any interested process (P1 or P2) to enter without obstruction.
Blocking and Lack of Progress
- If P1 wants to enter the critical section but is blocked by P2, this indicates a lack of progress. The system fails when one process prevents another from entering.
Mutual Exclusion and Empty Critical Section
- When both processes are interested in accessing the critical section but neither can due to blocking, it signifies that progress is not being made. This situation mirrors societal issues where individuals hinder each other's advancement.
Importance of Allowing Access
- For progress to occur, if P1 wishes to enter, P2 should allow it without interference. This principle ensures that both processes can utilize the critical section effectively.
Bounded Waiting: Ensuring Fairness
Concept of Bounded Waiting
- Bounded waiting means that while one process (e.g., P1) may use the critical section multiple times, there must be a limit ensuring that other processes (like P2) also get their turn eventually.
Starvation Prevention
- It’s crucial that no single process monopolizes access indefinitely; otherwise, starvation occurs where one process repeatedly enters while others wait excessively long for their chance.
Acceptable Usage Ratios
- While it's permissible for one process to use the critical section more frequently than another (e.g., 10 times vs. once), there should be a balance preventing unbounded usage by any single process.
No Assumptions on Hardware and Speed
Independence from Hardware Constraints
Synchronization in Critical Sections: Key Rules
Importance of Hardware Independence
- The proposed solution for synchronization in critical sections is designed to run on a 32-bit system, but it should not be limited by hardware specifications or processor speed.
- A solution that requires a specific processor speed (e.g., 1GHz) is deemed inadequate; solutions must be agnostic to hardware capabilities to ensure portability across systems.
Universal Solution Requirements
- Solutions should be portable and capable of running seamlessly across different operating systems without restrictions, such as running on Linux but failing on Windows.
- The ideal solution must adhere to the principle of universality, allowing easy adaptation and flexibility when transitioning between different environments.
Fundamental Rules for Synchronization Solutions
- Four essential rules govern synchronization solutions: Mutual Exclusion, Progress, Bounded Wait, and No Assumptions. Among these:
- Primary rules: Mutual Exclusion and Progress
- Secondary rules: Bounded Wait and No Assumptions