07 CSC520 06 Bahan Pengajaran Chapter 06 Process Synchronization

Focuses on synchronization issues in operating systems, specifically how processes access shared resources without conflicts.

Define the critical-section problem and illustrate a race condition.
Understand hardware solutions to the critical-section problem including memory barriers, atomic variables, and compare-and-swap operations.
Learn to implement mutex locks, semaphores, monitors, and condition variables for synchronized access to shared data.
Assess synchronization tools under varying contention scenarios.

Concurrent Execution: Processes can run simultaneously and may be interrupted at any moment.
Data inconsistency: Issues arise when multiple processes access shared data concurrently, requiring mechanisms for orderly execution (Example: the Bounded Buffer problem).
Necessity of synchronization to maintain data integrity in cooperating processes.

Race Condition Example: Two processes (P0 and P1) use the fork() call and may lead to conflict over the kernel variable next_available_pid, potentially assigning the same PID to two different processes.

Definition: A critical section is part of a process that accesses shared resources and must not be executed by more than one process at the same time.
Requirements:
1. Mutual Exclusion: Only one process in its critical section at a time.
2. Progress: No indefinite postponement in selecting the next process for the critical section.
3. Bounded Waiting: Limit the number of times other processes can enter critical sections after a request is made.

Mechanism: Disable interrupts during entry into the critical section and enable them upon exit.
Limitations: Can lead to starvation and issues in multi-CPU environments.

Two-process solution: Utilizes a shared variable turn to manage access.
Algorithm for Process Pi: Loops until it can access the critical section based on the turn.
Correctness: Ensures mutual exclusion and potentially satisfies progress and bounded-waiting requirements.

Description: Uses two variables (turn and flag) to indicate which process is ready to enter the critical section.
Algorithm: Includes setting flags and waiting based on the state of those flags.
Correctness Verification: Mutual exclusion, progress, and bounded waiting are satisfied under this model but with limitations on modern architecture due to instruction reordering.

Define how memory models ensure consistency in concurrent actions.
Strongly Ordered vs. Weakly Ordered: Describes how memory operations visibility differs across processors.
Usage of Memory Barriers: Ensures that necessary memory updates become visible to other processes before proceeding.

Operations like Test-and-Set and Compare-and-Swap for managing resource access atomically.
Test-and-Set: Boolean check that sets lock variable.
Compare-and-Swap: Swap two values atomically only if current value matches expected.

Simplifies the control of critical sections by offering a lock that must be acquired before entering.
Implemented with atomic instructions, often causing busy waiting while waiting for the lock.

Definition: An integer-based synchronization tool allowing access through atomic operations (wait() and signal()).
Types: Counting semaphores for general resource management and binary semaphores mirroring mutex behavior.
Semaphore Implementation: Managing a queue of processes waiting for access based on semaphore value to avoid busy waiting.

Definition: High-level synchronization constructs allowing only one active process contextual access at a time.
Uses condition variables for process waiting and signaling, ensuring mutual exclusion is maintained during function execution.

Operations: Include wait() to suspend a process and signal() to resume it based on certain conditions.
Applicable in ensuring that operations that must occur sequentially are effectively synchronized.

Definition: The set of properties ensuring system progress without indefinite waiting.
Deadlock: Describes processes stuck in a waiting state, unable to proceed due to mutual blocking.
Starvation: A process may never be able to access a resource if it consistently gets pre-empted by others.

Implementing synchronization tools is critical in concurrent programming to control access to shared resources and maintain data consistency, with various methodologies ranging from low-level atomic operations to high-level constructs like monitors.