CMPS 405: OPERATING SYSTEMS
Synchronization
This material is based on the operating system books by Silberschatz and Stallings
and other Linux and system programming books.
Operating Systems, CSE Dept., Qatar University
Objectives
Motivations
Concurrent Programming
Producer/Consumer Problem
Synchronization Terminology
Cooperative Processes Interaction Structure
Java Synchronization
Java Object locking (Synchronized Access)
Using yield,
Using wait/notify and wait/notifyAll methods pairs
Synchronization with Semaphores
The Concept of a Semaphore
Operating Systems, CSE Dept., Qatar University
Objectives
Java API Support for Concurrency
java.util.concurrent
Semaphores in java.util.concurrent.Semaphore
Reentrant Locks in java.util.concurrent.locks.ReentrantLock
Classical Synchronization Problems
Producer/Consumer Problem
Readers/Writers Problem
Operating Systems, CSE Dept., Qatar University
Concurrent Programming
In sequential programming: all computational tasks are executed in
sequence, one after the other.
In concurrent programming: multiple computational tasks are executed
simultaneously, at the same time.
Implementation of concurrent tasks:
as separate programs
as a set of processes or threads created by a single program
Execution of concurrent tasks:
on a single processor
Multithreaded programming
on several processors in close proximity
Parallel computing
on several processors distributed across a network
Distributed computing
Operating Systems, CSE Dept., Qatar University
Producer/Consumer Problem
Paradigm for cooperating
processes, producer process Producer
produces information that is
consumed by a consumer insert(item)
process.
unbounded-buffer places no Buffer
practical limit on the size of
the buffer.
remove()
bounded-buffer assumes that
there is a fixed buffer size. Consumer
Operating Systems, CSE Dept., Qatar University
Modeling The Shared Buffer
Buffer<interface>
void insert(Object)
Object remove()
BoundedBuffer<class> UnBoundedBuffer<class>
Operating Systems, CSE Dept., Qatar University
Bounded Buffer Implementation
public class BoundedBuffer implements Buffer {
count
private static final int BUFFER_SIZE = 5;
private int count; out in 3
private int in;
private int out; X X X
private Object[] buffer;
public BoundedBuffer(){ }
public void insert(Object item){ } public BoundedBuffer() {
public Object remove(){ } count = 0; in = 0; out = 0;
} buffer = new Object[BUFFER_SIZE];
}
public void insert(Object item) { public Object remove() {
while (count == BUFFER_SIZE); Object item;
++count; while (count == 0);
buffer[in] = item; --count;
in = (in + 1) % BUFFER_SIZE; item = buffer[out];
} out = (out + 1) % BUFFER_SIZE;
return item;
}
Operating Systems, CSE Dept., Qatar University
The Producer
import java.util.*;
public class Producer implements Runnable {
private Buffer buffer;
public Producer(Buffer b) {
buffer = b;
}
public void run() {
Date message;
while (true) {
int sleeptime = (int) (5000 * Math.random());
System.out.println("Producer napping "+sleeptime+" milliseconds");
try {Thread.sleep(sleeptime); }
catch (InterruptedException e){ }
message = new Date();
System.out.println("Producer is a wake and produced " + message);
buffer.insert(message);
}
}
}
Operating Systems, CSE Dept., Qatar University
The Consumer
import java.util.*;
public class Consumer implements Runnable {
private Buffer buffer;
public Consumer(Buffer b) {
buffer = b;
}
public void run() {
Date message;
while (true) {
int sleeptime = (int) (5000 * Math.random());
System.out.println("Consumer napping "+sleeptime+" milliseconds");
try {sleep(sleeptime);}
catch (InterruptedException e){}
System.out.println("Consumer is awake and wants to consume.");
message = (Date) buffer.remove();
System.out.println(“Consumer is a wake and consumed " + message);
}
}
}
Operating Systems, CSE Dept., Qatar University
The Factory Class
public class Factory{
public Factory(){
Buffer buffer = new BoundedBuffer();
Thread producerThread = new Thread(new Producer(buffer));
Thread consumerThread = new Thread(new Consumer(buffer));
producerThread.start();
consumerThread.start();
}
public static void main(String args[]) {
new Factory();
}
Operating Systems, CSE Dept., Qatar University
The Problem
Concurrent access to shared data may result in data
inconsistency
Maintaining data consistency requires mechanisms
to ensure the orderly execution of cooperating
processes
We can do so by having an integer count that keeps
track of the number of full buffers. Initially, count is
set to 0. It is incremented by the producer after it
produces a new buffer and is decremented by the
consumer after it consumes a buffer.
Operating Systems, CSE Dept., Qatar University
Threads accessing shared data
Body of the insert method
invoked by the Producer
Body of the remove
method invoked
by the Consumer
Operating Systems, CSE Dept., Qatar University
Synchronization Terminology
Concurrent accesses to same shared variable, where at least one access is
a write, would result in:
Incorrect results following order of accesses
Irregular errors, very hard to debug
Definition of Race Condition: the situation when there is concurrent
access to shared data and the final outcome depends upon order of
execution.
Definition of Critical Section: Section of code where shared data is
accessed.
Definition of Synchronization: Mechanism that allows the programmer to
control the relative order in which operations occur in different threads or
processes. (Coordinate Access of shared data)
Definition of Mutual Exclusion - If process Pi is executing in its critical
section, then no other processes can be executing in their critical sections.
Operating Systems, CSE Dept., Qatar University
Cooperative Processes Interaction Structure
....
Process/thread 1 ....... Process/thread n
Entry Section - Code that requests permission to enter its critical section.
Exit Section - Code that runs after exiting the critical section
Operating Systems, CSE Dept., Qatar University
Java Synchronization
Java provides synchronization at the language-level.
Each Java object has an associated lock.
This lock is acquired by invoking a synchronized method.
This lock is released when exiting the synchronized method.
Threads waiting to acquire the object lock are placed in the entry set for the
object lock.
Each object has an associated entry set.
Operating Systems, CSE Dept., Qatar University
Synchronized Objects in Java
Apply synchronized keyword to object
Mutual exclusion for code in synchronization block
Example:
Object x = new Object();
synchronized(x) { // acquire lock on x on entry
... // hold lock on x in block
} // release lock on x on exit
Operating Systems, CSE Dept., Qatar University
Synchronized Methods in Java
Java methods also provide locks:
Apply synchronized keyword to method
Mutual exclusion for entire body of method
Synchronizes on object invoking method
Example:
synchronized foo() { …code… }
shorthand notation for
foo() {
synchronized (this) { …code… }
}
Operating Systems, CSE Dept., Qatar University
Synchronized Methods in Java
Public synchronized void insert(Object item){
…… // body of the method goes here
Short hand notation for
Public void insert(Object item){
synchronized(this){
…… // body of the method goes here
}
}
Operating Systems, CSE Dept., Qatar University
Locks in Java
Properties:
No other thread can get lock on x while in block
Locked block of code critical section
Lock is released when block terminates:
End of block reached
Exit block due to return, continue, break
Exception thrown
Operating Systems, CSE Dept., Qatar University
Java Synchronization: Remarks
Use same lock to provide mutual exclusion
Ensure atomic transactions:
Sequence of actions must be performed as single
Ensure lock is held for duration of transaction
atomic transaction to avoid data race ONLY.
Avoiding deadlock
Potential problem:
Threads holding lock may be unable to obtain lock held by other
thread, and vice versa
Thread holding lock may be waiting for action performed by
other thread waiting for lock
Program is unable to continue execution (deadlock)
Operating Systems, CSE Dept., Qatar University
Example: Producer/Consumer Problem
Synchronized insert() and remove() methods
Operating Systems, CSE Dept., Qatar University
Java Synchronization wait/notify()
When a thread invokes wait():
1. The thread releases the object lock;
2. The state of the thread is set to Blocked;
3. The thread is placed in the wait set for the object.
When a thread invokes notify():
1. An arbitrary thread T from the wait set is selected;
2. T is moved from the wait to the entry set;
3. The state of T is set to Runnable.
When a thread invokes notifyAll():
selects all threads in the wait set and moves them to the entry set.
Entry and wait sets
Operating Systems, CSE Dept., Qatar University
Java Synchronization wait/notify()
Synchronization rules in Java:
A thread that owns the lock for an object can enter another synchronized
method (or block) for the same block. This is known recursive lock.
A thread can nest synchronized method invocations for different objects.
Thus, a thread can simultaneously own the lock of several different
objects.
If a method is not declared synchronized, then it can be invoked
regardless of lock ownership, even when another synchronized method
for the same object is executing.
If the wait set of an object is empty, then the call for notify() or
notifyall() has no effect.
wait(), notify(), and notifyall() may only be invoked from synchronized
methods or blocks; otherwise, an IllegalMonitorStateException is
thrown.
Operating Systems, CSE Dept., Qatar University
Java Thread States
Operating Systems, CSE Dept., Qatar University
Producer/Consumer Problem
Operating Systems, CSE Dept., Qatar University
Readers/Writers Problem
A data set S is shared among a number of
concurrent processes
Readers – only read the data set; they do not perform any
updates
Writers – can both read and write.
In other words:
o Any number of readers can access S at the same time.
o No writer can access S at the same time as a reader or another
writer.
OS examples: file locks
Operating Systems, CSE Dept., Qatar University
Readers-Writers Problem
Interface for read-write locks
Operating Systems, CSE Dept., Qatar University
Java Synchronization - Readers-Writers
Operating Systems, CSE Dept., Qatar University
Java Synchronization - Readers-Writers
Methods called by readers
Operating Systems, CSE Dept., Qatar University
Java Synchronization - Readers-Writers
Methods called by writers
Operating Systems, CSE Dept., Qatar University
The Concept of a Semaphore
A Semaphore is a synchronization tool that does not require busy waiting
Semaphore S – integer variable
Two standard operations modify S: In Dutch proberen
acquire() and release() (test)
Originally called P() and V() In Dutch verhogen
Less complicated (increment)
Can only be accessed via two indivisible (atomic) operations
Operating Systems, CSE Dept., Qatar University
Semaphore as General Synchronization Tool
Counting semaphore – integer value can range over an
unrestricted domain
Binary semaphore – integer value can range only between 0
and 1; can be simpler to implement
Also known as mutex locks
Usage of Semaphores
Operating Systems, CSE Dept., Qatar University
Semaphore Implementation
Busy wait: while a process is in its
critical section, any other process
trying to enter its critical section
must loop continuously in the entry
code.
Spin Lock: is a semaphore with
busy wait, process spins while
Waiting for the lock.
In a single CPU multiprogramming System where locks are expected to be held
for long time – critical section is long -, busy wait wastes CPU cycles that some
other process might be able to use productively.
In a multiprocessor System where locks are expected to be held for short time –
critical section is short -, busy wait is useful requiring no context switching.
But in most applications, locks are expected to be held for long time – critical
section is long – So, this implementation is not good.
Operating Systems, CSE Dept., Qatar University
Semaphore Implementation with no Busy waiting
With each semaphore there is an associated waiting queue.
Each entry in a waiting queue has two data items:
value (of type integer)
pointer to next record in the list
Two operations:
block – place the process invoking the operation on the
appropriate waiting queue.
wakeup – remove one of processes in the waiting queue
and place it in the ready queue.
Operating Systems, CSE Dept., Qatar University
Semaphore Implementation with no Busy waiting (Cont.)
Number of available resources, value ≥ 0
meaning (Value) =
| value | is the number of waiting processes, value ≤ 0
Operating Systems by Mohammad Saleh, CSE Dept., Qatar University
Deadlock and Starvation
Deadlock – two or more processes are waiting indefinitely for an event that
can be caused by only one of the waiting processes
Let S and Q be two semaphores initialized to 1.
P0 P1
Waits for Waits for
S.acquire(); Q.acquire(); P0 to
P1 to
release Q. Q.acquire(); S.acquire(); release S.
. .
. .
. .
S.release(); Q.release();
Q.release(); S.release();
Starvation – indefinite blocking. A process may never be removed from the
semaphore queue in which it is suspended.
Operating Systems, CSE Dept., Qatar University
The Producer/Consumer Problem
•Semaphore mutex
initialized to the value 1
•Semaphore full
initialized to the value 0.
•Semaphore empty
initialized to the value N.
Operating Systems, CSE Dept., Qatar University
The Producer/Consumer Problem
Operating Systems, CSE Dept., Qatar University
The Producer/Consumer Problem
Operating Systems, CSE Dept., Qatar University
The Producer/Consumer Problem
Operating Systems, CSE Dept., Qatar University
The Producer/Consumer Problem
Operating Systems, CSE Dept., Qatar University
The Readers/Writers Problem
Shared Data
Data set
Semaphore mutex initialized to 1.
Semaphore db initialized to 1.
Integer readerCount initialized to 0.
Operating Systems, CSE Dept., Qatar University
The Readers/Writers Problem
public class Database implements RWLock {
// the number of active readers
private int readerCount;
Semaphore mutex; // controls access to readerCount
Semaphore db; // controls access to the database
public Database() {
readerCount = 0;
mutex = new Semaphore(1);
db = new Semaphore(1);
}
Operating Systems, CSE Dept., Qatar University
The Readers/Writers Problem
Methods called by readers
public void acquireReadLock(int readerNum) {
mutex.acquire();
++readerCount;
// if I am the first reader tell all others
// that the database is being read
if (readerCount == 1)
db.acquire();
System.out.println("Reader " + readerNum
+ " is reading. Reader count = " + readerCount);
mutex.release();
}
public void releaseReadLock(int readerNum) {
mutex.acquire();
--readerCount;
// if I am the last reader tell all others
// that the database is no longer being read
if (readerCount == 0)
db.release();
System.out.println("Reader " + readerNum
+ " is done reading. Reader count = " + readerCount);
mutex.release();
}
Operating Systems, CSE Dept., Qatar University
The Readers/Writers Problem
Methods called by writers
public void acquireWriteLock(int writerNum) {
db.acquire();
System.out.println("writer " + writerNum + " is
writing.");
public void releaseWriteLock(int writerNum) {
System.out.println("writer " + writerNum + " is done
writing.");
db.release();
}
} //ends class DataBase
Operating Systems, CSE Dept., Qatar University
The Readers/Writers Problem
Operating Systems, CSE Dept., Qatar University
The Readers/Writers Problem
Operating Systems, CSE Dept., Qatar University
Java Concurrency: Semaphore
Java has a package specifically to support concurrency
programming.
The package is java.util.concurrent
It has supported solutions for Semaphore synchronization
Semaphores in java.util.concurrent.Semaphore
Operating Systems, CSE Dept., Qatar University
Java Semaphores
To create a semaphore call the constructor
Semaphore(int value)
To acquire a permit from this semaphore, blocking until one is available, or
the thread is interrupted
void acquire()
To acquire the given number of permits from this semaphore, blocking
until all are available, or the thread is interrupted
void acquire(int permits)
To return the current number of permits available in this semaphore
int availablePermits()
To release a permit, returning it to the semaphore
void release()
To release the given number of permits, returning them to the semaphore
void release(int permits)
Operating Systems, CSE Dept., Qatar University
Java Semaphores
How to?
import java.util.concurrent.Semaphore;
Usage:
Semaphore sem = new Semaphore(1);
//……….
try{
sem.acquire();
//critical section
}
finally{
sem.release();
}
Operating Systems, CSE Dept., Qatar University
Java Reentrant Locks
Java API ReentrantLock is owned by a single thread and is used to provide
a mutually exclusive access to a shared resource.
One additional feature of ReentrantLock is setting fairness parameter,
which favors granting the lock to the longest-waiting thread.
How to?
import java.util.concurrent.locks.ReentrantLock;
Usage:
lock key = new ReentrantLock();
key.lock();
try{
//critical section
}
finally{
key.unlock();
}
Operating Systems, CSE Dept., Qatar University
