Operating Systems Chapter 6: Synchronization Tools

Chapter 6: Synchronization Tools

• Synchronization tools are used to coordinate processes, ensuring proper execution
• Many modern systems provide hardware support for implementing the critical sections
• Uniprocessors can disable interrupts, but this isn't effective for multitasking systems
• The chapter focuses on different hardware tools like mutex locks, semaphores, monitors, and condition variables, as well as atomic variables, to handle critical sections.
• The critical-section problem describes how multiple processes can access shared resources concurrently without causing race conditions or data inconsistencies.

Outline

• Background
• The Critical-Section Problem
• Peterson's Solution
• Hardware Support for Synchronization
• Mutex Locks
• Semaphores
• Monitors
• Liveness
• Evaluation

Objectives

• Describe critical-section problem and illustrate race conditions
• Illustrate hardware solutions using memory barriers, compare-and-swap, and atomic operations.
• Demonstrate how mutex locks, semaphores, monitors, and condition variables handle critical section issues.
• Evaluate the efficiency of synchronization tools (low-, moderate-, high-contention scenarios).

Memory Barrier

• Memory models define how memory modifications are propagated across processors.
• Strong ordering memory modifications are immediately visible to all other processors which affects performance.
• Weak ordering memory modifications may not be immediately visible which can lead to performance and issues with race conditions but can also enhance performance as it's more flexible.
• A memory barrier is an instruction that ensures that all prior memory operations are completed before subsequent ones.

Memory Barrier Instructions

• When a memory barrier instruction is executed, all previous load and store operations are completed.
• This ensures reordering of instructions does not affect the order of memory access, improving consistency between processors if needed.

Memory Barrier Example

• Using memory barriers, ensure that one thread's output (e.g., a value) is visible before another thread accesses that data, protecting data integrity.

Synchronization Hardware

• Many modern systems use hardware instructions for synchronization.
• Uniprocessors can disable interrupts, halting other processes temporarily to prevent race conditions, but is inefficient in multiprocessor systems.
• Efficiency on multiprocessor systems is improved by hardware support for atomic operations.
• Two forms of hardware support are hardware instructions (e.g., test-and-set, compare-and-swap) and atomic variables.

Hardware Instructions

• Special hardware instructions (test-and-set, compare-and-swap) allow testing and modifying a memory location or swapping two memory locations atomically (without interruption)

Test-and-Set Instruction

• Executed atomically
• Returns the original value of the passed parameter
• Sets the new value of the passed parameter to true

Solution Using Test-and-Set

• Shared boolean variable "lock" is initialized to false
• The while loop ensures exclusive access to the critical section

The Compare-and-Swap Instruction

• Executed atomically
• Returns the original value of the passed parameter
• Sets the variable's value to the new value only if the original value matches the expected value.

Solution Using Compare-and-Swap

• Shared integer variable "lock" is initialized to 0
• The while loop ensures exclusive access to the critical section

Atomic Variables

• Atomic variables enable uninterruptible updates to basic data types (integers and booleans)
• Atomic operations guarantee data integrity even when multiple processes access shared memory.

Mutex Locks

• Mutex locks are software tools for managing concurrent access to shared resources.
• A Boolean variable indicates whether a lock is available (true) or not (false).
• Acquire() and release() operations on the lock must be executed atomically (uninterruptably)

Solution to Critical Section Problem Using Mutex Locks

• Use a mutex lock to ensure that only one process can access a critical section at any given moment; acquire() lock before critical section, release() after critical section.

Semaphore

• Semaphores provide more sophisticated synchronization than mutex locks.
• Semaphores are integer variables that can be accessed only through the wait() and signal() (or P() and V()) operations, guaranteeing atomicity.

Semaphore (Cont.)

• Counting semaphores: integer values can range over an unrestricted domain.
• Binary semaphores: integer values can only range between 0 and 1; functionally same as mutex locks.

Semaphore Usage Example

• Using semaphores to control the order of execution of critical sections across multiple processes.

Semaphore Implementation

• Guaranteeing atomicity of wait() and signal() operations is crucial.
• Inside a critical section, busy waiting could be a problem (loops that continually check a condition).

Problems with Semaphores

• Incorrect use of semaphore operations (e.g., signal before wait) or missing critical section checks can produce problems.