Transcript Tutorial Notes # 5

Tutorial 5
Even More Synchronization!
presented by:
Antonio Maiorano
Paul Di Marco
Quick Recap
• When multiple threads share resources,
we need a way to synchronize access
to these resources
• Recall the coffee example with pourer
and drinker
• Solution: Use semaphores!
Alternatives to Semaphores
• Semaphores are great, but they can be
difficult to use when solving certain
problems
• We will look at alternatives to
semaphores
• Note: These alternatives are more
convenient, though semaphores can still
be used to solve these problems
Problem 1
• 2 drummers (threads) each with his/her
own drum set
• Only 2 drumsticks: drumStick1 and
drumStick2 (shared resources)
• Both drummers want to play, and to
play, a drummer needs two drumsticks
One solution…
Semaphore drumStick1 = new Semaphore(1);
Semaphore drumStick2 = new Semaphore(2);
Drummer 1:
Drummer 2:
drumStick1.Wait();
drumStick2.Wait();
drumStick1.Wait();
drumStick2.Wait();
PlayDrums();
PlayDrums();
drumStick2.Signal();
drumStick1.Signal();
drumStick2.Signal();
drumStick1.Signal();
This works, but…
But what if…
Drummer 1:
Drummer 2:
drumStick1.Wait();
drumStick2.Wait();
drumStick2.Wait();
drumStick1.Wait();
PlayDrums();
PlayDrums();
drumStick2.Signal();
drumStick1.Signal();
drumStick1.Signal();
drumStick2.Signal();
• Potential deadlock!
• Problem: can’t rely on programmers to
obtain semaphores in the same order
Alternative: AND Synchronization
• Two functions:
– WaitMulti(S1, S2, …,Sn) : Blocks calling
thread until all semaphores are available
– SignalMulti(S1, S2, …, Sn) : Releases all
semaphores
• Easy to implement
• See Java code: MultiSemTest.java
Drummers… one more time!
Semaphore drumStick1 = new Semaphore(1);
Semaphore drumStick2 = new Semaphore(2);
MultiSemaphore drumSticks;
drumSticks = new MultiSemaphore(drumStick1, drumStick2);
Drummer 1:
Drummer 2:
drumSticks.WaitMulti();
PlayDrums();
drumSticks.SignalMulti();
drumSticks.WaitMulti();
PlayDrums();
drumSticks.SignalMulti();
Problem solved!
Problem 2
• Global keyboard state object : Know
when keys are pressed
• Threads: ask keyboard state object
when a key has been pressed
• Threads may start at any time
One solution…
Semaphore keyA = new Semaphore(0); // Initially not pressed
Operating System thread:
...
User thread:
...
if (keyPressed = ‘A’)
keyA.Signal();
// Wait for ‘A’ key to be
// pressed before continuing
keyA.Wait();
...
...
This works sometimes…
What’s the problem?
• Only one thread will react upon key
press
• If a thread starts after the key has been
pressed, the Wait() call will return
immediately
• The semaphore is passive: it does not
take timing into account
• We need an active semaphore…
Alternative: Events
• Events are active semaphores with its
functions defined as:
– Wait() : Block until event occurs; calling
thread is added to the event’s waiting
queue.
– Signal() : Unblock all threads on event’s
waiting queue; remove them from the
queue.
• See Java code: EventTest.java
Only diff!
One more time…
Event keyA = new Semaphore(0); // Initially not pressed
Operating System thread:
...
User thread:
...
if (keyPressed = ‘A’)
keyA.Signal();
// Wait for ‘A’ key to be
// pressed before continuing
keyA.Wait();
...
...
Monitors
• A monitor is an Abstract Data Type – like a
class
• The key importance of a monitor is that
only one function can be accessed at a
time
• An important property of ADTs for use with
monitors is separation of interface and
implementation
Interface / Implementation
Have a public interface to the class while
maintaining the implementation private:
• Prevents use of internal structures
• Allows the implementation to change while
keeping the same interface
• Allows for control of how the object is used
• Enforced interface allows for proving
properties about its behaviour
Monitor Analogy
• A monitor can be thought of as a class
where each function is a critical section
• The monitor thus would have a mutex
as a private data member, and
• Each function would thus call
mutex.Wait() before executing, and
mutex.Signal() before exiting.
In Java…
• A monitor can be implemented as we
just described, or
• As a class where all of the methods are
“synchronized”, where Java does the
work for you
Simple Monitor
monitor SharedBalance {
private int balance;
public SharedBalance(int amt)
{balance = amt;}
public credit(int amt) {balance += amt;}
public debit(int amt) {balance –= amt;}
}
Readers – Writers Problem
• We have many readers and many
writers
– Readers want to read a resource
– Writers want to write to a resource
• Rules:
– Multiple readers are allowed
– One writer can write at a time
– No readers can read when a writer is
writing
Building Our Solution
• Before the reader or writer reads from
the resource, it calls the its “start”
method
• The “start” methods ensure that the
“coast is clear”; that it is fine to continue
to read from/write to the resource
• The “finish” methods allow the next
thread to read or write
Our Monitor
• We want to solve the problem with a
monitor, so it will need to keep track of:
– int numReaders = 0: number of readers
currently reading
– int numWriters = 0: number of writers
currently writing / waiting to write
– boolean busy = false: is a writer busy?
The Readers and Writers
reader() {
writer() {
while (true){
// …
mon.startRead();
// read the resource
mon.finishRead();
// …
}
}
while (true) {
// …
mon.startWrite();
// write the resource
mon.finishWrite();
// …
}
}
Our Solution
// reader methods
startRead() {
// writer methods
startWrite() {
while (numWriters != 0);
++numReaders;
++numWriters;
while (busy || numReaders > 0);
busy = true;
}
}
finishWrite() {
--numWriters;
busy = false;
finishRead() {
--numReaders;
}
}
The Problem With Our Solution
• While a reader/writer is executing it’s
“start” in the monitor, no other processes
are allowed in!!!
• We have to look further for our solution…
• Condition variables are used when:
– a thread running in a monitor
– encounters a condition that is not satisfied,
– which can only be satisfied by another thread
Condition Variables
This is exactly what we need!
• Condition Variables are an extension of
Events to the concept of monitors
– It temporarily blocks current thread,
– Handing over “ownership” of the monitor to
another thread – to do some work that will
make the condition true
– The original thread regains “ownership” of
monitor later on…
Regaining the Monitor
What happens on a call to signal() depends
on the semantics used
• Hoare’s semantics:
– Signaling thread (S) is immediately
interrupted and monitor is given back to a
blocked thread (B)
– Thread S resumes (in the monitor) when B
finishes using the monitor
And Another Way…
• Hansen’s sematics are not immediate:
– Signal is “saved”
– A blocked thread will wake up only when the
signaling thread finishes with the monitor
* The blocked thread must always verify the
condition again upon waking up, since some
time has elapsed since the signal() was called
– This results in less context switches,
increasing system performance
How Do We Use Them?
• Condition variables have three methods:
– wait(): block on a variable, give up monitor
– signal(): wake up a thread blocked on this
– queue(): ask if are there any threads blocked
on this variable - to be used as part of the
condition
• In Java, they correspond to the usage,
within “synchronized” objects, of wait()
and signal() – although there is no queue()
Return to Readers – Writers
• Now that we know about condition
variables, we can solve this problem easily
• We now have the following variables:
– int numReaders = 0 (same as before)
– boolean busy = false (same as before)
– Condition Variables okToRd, okToWr
• Solution will use Hoare’s semantics
The Final Solution
// reader methods
startRead() {
// writer methods
startWrite() {
while (busy || okToWr.queue())
okToRead.wait();
++numReaders;
++numWriters;
while (numReaders != 0 || busy)
okToWr.wait();
busy = true;
}
finishRead() {
}
finishWrite() {
--numReaders;
if (numReaders == 0)
okToWr.signal()
busy = false;
if (okToWr.queue())
okToWr.signal();
else okToRead.signal();
}
}