Chapter 7: Synchronization
Example
Operating System Concepts – 10th Edition
Synchronization Examples
Classic Problems of Synchronization
Bounded-Buffer Problem
Readers and Writers Problem
Window Synchronization
POSIX Synchronization
Operating System Concepts – 10th Edition 7.2
Bounded-Buffer Problem
n buffers, each can hold one item
Semaphore mutex initialized to the value 1
Semaphore full initialized to the value 0
Semaphore empty initialized to the value n
Operating System Concepts – 10th Edition 7.3
Bounded Buffer Problem (Cont.)
The structure of the producer process
do {
...
/* produce an item in next_produced */
...
wait(empty);
wait(mutex);
...
/* add next produced to the buffer */
...
signal(mutex);
signal(full);
} while (true);
Operating System Concepts – 10th Edition 7.4
Bounded Buffer Problem (Cont.)
The structure of the consumer process
do {
wait(full);
wait(mutex);
...
/* remove an item from buffer to next_consumed */
...
signal(mutex);
signal(empty);
...
/* consume the item in next consumed */
...
} while (true);
Operating System Concepts – 10th Edition 7.5
Readers-Writers Problem
A data set is shared among a number of concurrent processes
Readers – only read the data; they do not perform any updates
Writers – can both read and write
Problem – allow multiple readers to read the data set at the same time, but at most only
one single writer can access shared data at a time
Several variations of how readers and writers are treated – involve different priorities.
The simplest solution, referred to as the first readers-writers problem, requires that no
reader be kept waiting unless a writer has already gained access to the shared data
Shared data update (by writers) can be delayed
This gives readers priority in accessing shared data
Shared Data
Data set
Semaphore rw_mutex initialized to 1
Semaphore mutex initialized to 1
Integer read_count initialized to 0
Operating System Concepts – 10th Edition 7.6
Readers-Writers Problem (Cont.)
The structure of a writer process
do {
wait(rw_mutex);
...
/* writing is performed */
...
signal(rw_mutex);
} while (true);
Operating System Concepts – 10th Edition 7.7
Readers-Writers Problem (Cont.)
The structure of a reader process Note:
do {
wait(mutex); rw_mutex controls the access to shared
read_count++; data (critical section) for writers, and the
first reader. The last reader leaving the
if (read_count == 1) critical section also has to release this lock
wait(rw_mutex);
signal(mutex) mutex controls the access of readers to
... the shared variable count
/* reading is performed */
... Writers wait on rw_mutex, first reader
yet gain access to the critical section also
wait(mutex); waits on rw_mutex. All subsequent
read_count--; readers yet gain access wait on mutex
if (read_count == 0)
signal(rw_mutex);
signal(mutex);
} while (true);
Operating System Concepts – 10th Edition 7.8
Readers-Writers Problem Variations
First variation – no reader kept waiting unless a writer has gained access to use shared
object. This gives a higher priority to readers. This is simple, but can result in starvation for
writers, thus can potentially significantly delay the update of the object.
Second variation – once a writer is ready, it needs to perform update asap. In this case, if a
writer is wait to access the object (this implies that there could be either readers or a writer
inside), no new readers may start reading, i.e., they must wait (outside) after the waiting writer
updates the object
A solution to either problem may result in starvation
The problem can be dealt by the kernel in providing reader-writer locks, in which multiple
processes are permitted to concurrently acquire a reader-writer lock in read mode, but only one
process can acquire the reader-writer lock for writing （exclusive access). Acquiring a reader–
writer lock thus requires specifying the mode of the lock: either read or write access
Operating System Concepts – 10th Edition 7.9
Synchronization Examples
Solaris
Windows XP
Linux
Pthreads
Operating System Concepts – 10th Edition 7.10
Solaris Synchronization
Implements a variety of locks to support multitasking, multithreading (including real-time
threads), and multiprocessing
Uses adaptive mutex for efficiency when protecting data from short code segments,
usually less than a few hundred （machine-level) instructions
Starts as a standard semaphore implemented as a spinlock in a multiprocessor system
If lock held, and by a thread running on another CPU, spins to wait for the lock to become
available
If lock held by a non-run-state thread, block and sleep waiting for signal of lock being released
Uses condition variables
Uses readers-writers locks when longer sections of code need access to data. These are
used to protect data that are frequently accessed, but usually in a read-only manner. The
readers-writer locks are relatively expensive to implement.
Operating System Concepts – 10th Edition 7.11
Windows Synchronization
The kernel uses interrupt masks to protect access to global resources in uniprocessor
systems
The kernel uses spinlocks in multiprocessor systems to protect short code segments
For efficiency, the kernel ensures that a thread will never be preempted while holding a spinlock
For thread synchronization outside the kernel, i.e., in user mode, Windows provides
dispatcher objects, threads synchronize according to several different mechanisms, including
mutex locks, semaphores, events, and timers
Events are similar to condition variables; they may notify a waiting thread when a desired
condition occurs
Timers are used to notify one or more thread that a specified amount of time has expired
Dispatcher objects either signaled-state (object available) or non-signaled state (this means that
another thread is holding the object, therefore the thread will block)
Operating System Concepts – 10th Edition 7.12
Linux Synchronization
Linux:
Prior to kernel Version 2.6, disables interrupts to implement short critical sections
Version 2.6 and later, fully preemptive kernel
Linux provides:
semaphores
Spinlocks – for multiprocessor systems
atomic integer, and all math operations using atomic integers performed without
interruption
reader-writer locks
On single-CPU system, spinlocks replaced by enabling and disabling kernel preemption
Operating System Concepts – 10th Edition 7.13
Atomic Variables
Atomic variables - atomic_t is the type for atomic integer
Consider the variables
atomic_t counter;
int value;
Operating System Concepts – 10th Edition 7.14
POSIX Synchronization
POSIX API provides
mutex locks
semaphores
condition variables
Widely used on UNIX, Linux, and MacOS
Operating System Concepts – 10th Edition 7.15
POSIX Mutex Locks
Creating and initializing the lock
Acquiring and releasing the lock
Operating System Concepts – 10th Edition 7.16
POSIX Condition Variables
POSIX condition variables are associated with a POSIX mutex lock to provide
mutual exclusion: Creating and initializing the condition variable:
Operating System Concepts – 10th Edition 7.17
POSIX Condition Variables
Thread waiting for the condition a == b to become true:
pthread_cond_wait() &mutex as the second parameter - in addition to
putting the calling thread to sleep, releases the lock when putting said caller to
sleep. If not， no other thread can acquire the lock and signal it to wake up
Operating System Concepts – 10th Edition 7.18
POSIX Condition Variables
Thread signaling another thread waiting on the condition variable:
When signaling (as well as when modifying the condition variable), make sure to
have the lock held. This ensures that no race condition is accidentally introduced
Before returning after being waked up, the pthread cond wait() re-
acquires the lock, thus ensuring that any time the waiting thread is running
between the lock acquire at the beginning of the wait sequence, and the lock
release at the end, it holds the lock.
Operating System Concepts – 10th Edition 7.19
End of Chapter 7
Operating System Concepts – 10th Edition