Synchronization Examples

Synchronization Examples

• This chapter covers classic problems of synchronization, synchronization within the kernel, and POSIX and Java synchronization
• Alternative approaches to synchronization are also discussed

Classical Problems of Synchronization

• Classical problems serve as tests for newly proposed synchronization schemes
• These include the Bounded-Buffer Problem, Readers and Writers Problem, and Dining-Philosophers Problem

Bounded-Buffer Problem

• Involves n buffers, each holding one item
• A semaphore named mutex is initialized to 1
• A semaphore named full is initialized to 0
• A semaphore named empty is initialized to n

Producer Process Structure for Bounded-Buffer Problem

• The producer process waits until there's an empty buffer (empty > 0), then decrements ‘empty’.
• It acquires a lock (mutex), adds the produced item to the buffer, releases the lock, and increments ‘full’.
• This repeats continuously

Consumer Process Structure for Bounded-Buffer Problem

• The consumer process waits until there's a full buffer (full > 0), then decrements ‘full’.
• It acquires a lock (mutex), removes an item from the buffer and releases the lock. It then increments ‘empty’.
• This repeats continuously

Readers-Writers Problem

• A data set is shared among concurrent processes, with readers only reading and writers both reading and writing
• There's a need to allow multiple readers or only one single writer to access the shared data at a time

Readers-Writers Problem Details

• Several variations exist regarding how readers and writers are handled, involving priorities
• Shared data includes a data set, semaphore rw_mutex(initialized to 1), semaphore mutex(initialized to 1), and integer read_count(initialized to 0)

Writer Structure for Readers-Writers Problem

• A writer process waits on rw_mutex, performs writing, and then signals rw_mutex

Reader Structure for Readers-Writers Problem

• A reader process waits on mutex, increments read_count, and if it's the first reader, waits on rw_mutex
• It signals mutex, performs reading, waits on mutex again, decrements read_count, and if it's the last reader, signals rw_mutex, and signals mutex again

Readers-Writers Problem Variations

• The first variation ensures no reader waits unless a writer has permission to use the shared object
• In the second variation, once a writer is ready, it writes ASAP
• Both variations may lead to starvation and further variations
• Reader-writer locks are used by the kernel to solve this problem on some systems

Dining-Philosophers Problem

• Philosophers alternate between thinking and eating, needing two chopsticks to eat
• They cannot interact with their neighbors and must release chopsticks after eating
• The shared data consist of a bowl of rice (data set) and a semaphore chopstick[5], initialized to 1

Dining-Philosophers Problem Algorithm

• Philosopher i waits for chopstick[i] and chopstick[(i + 1) % 5], eats, then signals both chopsticks

Dining-Philosophers Problem Remedies

• This algorithm causes all five philosophers can become hungry simultaneously creating a deadlock
• To avoid this, allow at most four philosophers at the table, allow a philosopher to pick up only if both chopsticks are available, or use an asymmetric solution where odd philosophers pick up left then right and even philosophers pick up right then left

Monitor Solution to Dining Philosophers

• A monitor is used which allows one philosopher to eat at a time
• Deadlock is not possible, however, starvation is possible

Synchronization Examples: Common Systems

• Solaris, Windows, and Linux are operating systems that require synchronization
• Pthreads is an API that also manages synchronization

Solaris Synchronization

• Employs various locks for multitasking, multithreading (including real-time threads) & multiprocessing
• Uses adaptive mutexes for efficiency in protecting data from short code segments. Starts as a standard semaphore spin-lock.
• Uses condition variables and reader-writer locks for longer code sections needing data access
• Uses turnstiles to arrange threads waiting to get either an adaptive mutex or reader-writer lock; turnstiles are per-lock-holding-thread, not per-object, and priority-inheritance per-turnstile provides the running thread the top priority of the threads in its turnstile

Windows Synchronization

• Uses interrupt masks to shield the access to global resources on uniprocessor systems
• Uses spinlocks on multiprocessor systems (spin locking thread will never be preempted)
• Provides dispatcher objects for user-level; these act as mutexes, semaphores, events, and timers
• Events effectively similar to condition variables, timers notify when time expires and dispatcher objects are either signaled-state (object available) or non-signaled state (thread will block)

Linux Synchronization

• Prior to kernel Version 2.6, disables interrupts to implement short critical sections (Version 2.6 and later is fully preemptive)
• Linux provides semaphores, atomic integers, spinlocks and reader-writer versions of both
• On single-CPU systems, spinlocks are replaced by enabling and disabling kernel preemption

Pthreads Synchronization

• Pthreads API is OS-independent and provides mutex locks, condition variables, read-write locks, and spinlocks

Alternative Approaches: Transactional Memory

• A memory transaction is a sequence of read-write operations to memory that are atomically performed

Alternative Approaches: OpenMP

• OpenMP: set of compiler directives and API that support parallel programming where code inside #pragma omp critical is treated as critical section and performed atomically

Alternative Approaches: Functional Programming Languages

• Functional programming offer a different paradigm compared to procedural languages in that they do not maintain state
• Variables are treated as immutable, so they cannot change state once assigned a value
• Functional languages like Erlang and Scala are of increasing interest for handling data races