Concurrency, Mutual Exclusion and Synchronization

Concurrency and Mutual Exclusion

• Focuses on concurrency, mutual exclusion, and synchronization
• Includes mutual exclusion requirements and hardware approaches to support mutual exclusion

Topics

• Semaphores
• Monitors
• Message passing
• Classical concurrency problems, specifically the producer/consumer problem

Process Awareness and Potential Issues

• Processes unaware of each other face competition, leading to potential mutual exclusion, deadlock (renewable resource), and starvation issues
• Indirectly aware processes (sharing) involve cooperation, potentially leading to mutual exclusion, deadlock (renewable resource), starvation, and data coherence issues
• Directly aware processes (communication) use cooperation with a risk of deadlock (consumable resource) and starvation

Resource Competition

• Concurrent processes conflict when competing for the same resource, like I/O devices, memory, processor time, or clock signals
• Competing processes have 3 control problems to face,
• The need for mutual exclusion
• Deadlock
• Starvation

Mutual Exclusion Requirements

• A process that halts must not interfere with other processes
• Processes requiring access to a critical section must not be indefinitely delayed, avoiding deadlock or starvation
• Any process requesting entry to its critical section when no process is in a critical section must be permitted without delay
• Should not make assumptions about relative process speeds or number of processes
• Processes remain inside its critical section for a finite time

Mutual Exclusion Hardware Support

• In a uniprocessor system, concurrent processes can only be interleaved, not overlapped
• Mutual exclusion is guaranteed if processes are prevented from being interrupted

Interrupt Disabling

• Prevents interruption of a process to assure mutual exclusion
• Primitives are defined by the OS kernel for interrupt disabling and enabling
• Execution efficiency degrades because the processor's ability to interleave processes becomes limited
• It will not work in a multiprocessor architecture

Compare and Exchange Instruction

• Also called "compare and swap instruction"
• An atomic operation (not subject to interruption) is carried out atomically.
• If the values are the same, a swap occurs between a memory value and a test value

Special Machine Instruction Advantages

• Works for any number of processes whether on a single or multiple processors sharing memory
• It has simple verification
• Supports multiple critical sections, defined by their own variable

Special Machine Instruction Disadvantages

• Busy-waiting consumes processor time while waiting critical section access
• Starvation becomes possible with arbitrary waiting process selection
• Possibility of deadlock

Common Concurrency Mechanisms

• Semaphore: An integer value for signaling among processes with initialize, decrement, and increment operations
• Binary Semaphore: Takes on values 0 and 1
• Mutex: Locks the mutex (sets the value to zero) and unlocks it
• Condition Variable: Blocks a process or thread until a condition is true
• Monitor: A programming language construct that encapsulates variables, access procedures, and initialization code within an abstract data type
• Event Flags: Involves a memory word used for synchronization where application code associates each bit in a flag with a different event
• Mailboxes/Messages: Enables two processes to exchange information
• Spinlocks: Involves mutual exclusion where a process loops infinitely awaiting a lock variable to indicate availability

Semaphores

• There is no way to inspect or manipulate semaphores other than the three defined operations
• A semaphore may be initialized to a nonnegative integer value
• The semWait operation decrements the semaphore value
• The semSignal operation increments the semaphore value

Semaphore Consequences

• It is not possible to know before a process decrements a semaphore whether it will block or not
• It is not possible to know which process will continue immediately on a uniprocessor system when two processes are running concurrently
• Knowledge of whether another process is waiting is absent, so unblocked processes may be zero or one

Semaphore Types

• Queue holds processes waiting on the semaphore
• The one that has been blocked is released from the queue first by Strong Semaphores
• Weak Semaphores does not specify its process removal order

Mutual exclusion of a critical section achieved using semaphores

Producer/Consumer Problem

• Producers generate data and place it in a buffer
• One consumer takes items out of the buffer at a time
• Only one producer or consumer may access the buffer at any one time
• Producer must not add data if full, and consumer must not remove data when empty

Semaphore Implementation

• semWait and semSignal operations must be atomic primitives
• Implemented in hardware or firmware
• Alternate software schemes like Dekker's or Peterson's algorithms exist

Monitors

• A programming language construct with equivalent functionality to semaphores, but easier to control
• Implemented in programming languages and as a program library

Monitor Characteristics

• Local data variables are accessible only by the monitor's procedures
• Processes enter the monitor by invoking one of its procedures
• Only one process may be executing in the monitor at a time

Synchronization

• Uses condition variables within, and are accessible only by, the monitor
• Includes:
  • cwait(c): suspends execution of the calling process on condition c
  • csignal(c): resumes execution of some process blocked after a cwait on the same condition

Message Passing

• Interaction entails synchronization and communication
• Sender and receiver must be blocked (requires more synchronization)

Message Passing Primitives

• send (destination, message)
• receive (source, message)
• A process sends information in the form of a message to another process designated by a destination
• A process receives information by executing the receive primitive, indicating the source and the message

Message System Design Characteristics

• Synchronization: This refers to the essential process of managing and coordinating communication between various processes within a concurrent system, which may execute simultaneously.
  • Blocked send and receive operations are fundamental mechanisms that cause the execution to pause until the communication process is fully completed, ensuring data integrity and order.
  • Non-blocking operations support asynchronous interactions, enabling processes to continue executing without waiting for the communication to finalize.
  • Furthermore, implementing arrival testing functions is critical to ensure timely and efficient handling of responses, allowing systems to react dynamically to incoming data and events.
• Addressing: Direct (send/receive explicit or implicit), Indirect (static, dynamic, ownership)
• Queueing: FIFO or priority

Addressing Methods in Message Passing

• Direct Addressing: send specifies the destination
• Receive Explicit: requires explicit process designation as a sender
  • Receive Implicit: source has value returned after the operation
• Indirect Addressing: messages sent to a queue structure ("mailboxes")
  • Provides great flexibility of use

General Message Format

• General Message Format contains:
  • Header: type, ID (destination, source), message length, control information
  • Body: message contents

Queueing Discipline

• Simplest is first-in-first-out
• Alternatives are:
  • Specifying message priority by type/sender
  • Allowing the receiver to inspect and select the next message

Readers/Writers Problem

• A shared date with a single writer process while others are reading
• Conditions:
  • May have any number of simultaneous readers
  • Only one writer at a time
    • if a writer is writing, no reader may be reading

Explore concurrency, mutual exclusion, and synchronization, including requirements and hardware approaches. Learn about semaphores, monitors, message passing, and classical concurrency problems like the producer/consumer problem. Understand process awareness and potential issues such as mutual exclusion, deadlock, starvation, and data coherence.