Mutual Exclusion and Example Java
Solutions
F29OC
ss002.00_2020_01_09_Threads_intro
Recall Basic Race Problem
Multiple Threads
(or processes)
i++
Time
i++
Apr 21, 2024 2
BUT, what is shared in Java?
Multiple Threads
(or processes)
i++
i++
Apr 21, 2024 3
Java Memory Model
Apr 21, 2024 4
Passed by value:
Apr 21, 2024 9
Passed by reference:
Apr 21, 2024 10
Shared State?
• Pass by value to thread • Passed by reference to
= thread =
• not part of shared state • Part of shared state
Reference = Jenkov - Java Memory model
http://tutorials.jenkov.com/java-concurrency/ja
va-memory-model.html
And see GitLab value-or-reference example
Apr 21, 2024 11
How do we protect
shared state from Race
conditions?
Apr 21, 2024 12
Extrinsic Monitor Solution
• Make methods critical regions
Share state
lock
unlock
lock
unlock
lock
unlock
Apr 21, 2024 13
Other Solutions
• Busy Waiting
– Java Atomic variables
• Blocking solutions (thread scheduled out)
– Semaphores
– Monitors
• Intrinsic
• Extrinsic (already covered)
Apr 21, 2024 14
Example: Java AtomicBoolean
Provides set of Atomic methods, e.g.:
• get() //returns current value
• set(arg) //set current value to arg
Provide MX access to single
(atomic) variable
From <https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/atomic/AtomicBoolean.html#compareAndSet(boolean,%20boolean)>
Apr 21, 2024 15
Example: Java AtomicBoolean
More sophisticate Atomic methods:
Can provide critical region
• getAndSet(arg) mechanism
• compareAndSet()
Easier programming of
providing Critical Regions
From <https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/atomic/AtomicBoolean.html#compareAndSet(boolean,%20boolean)>
Apr 21, 2024 16
compareAndSet method
boolean compareAndSet( expected, update)
Atomically sets the value to update
if the current value == expected
Returns: true if value updated,
false otherwise
Apr 21, 2024 17
Use in Busy Wait
AtomicBoolean atomicBoolean = AtomicBoolean(false);
void criticalRegion() {
while (!atomicBoolean.compareAndSet(false, true) {
}
// Now have access (no one else has)
// CR code here
atomicBoolean.set(false); // release control
}
From <
https://stackoverflow.com/questions/25038919/is-this-use-of-atomicboolean-a-valid-replacemen
Apr 21,t-for-synchronized-blocks
2024 18
Use in Busy Wait
!atomicBoolean.compareAndSet(false, true)
Occupied
Apr 21, 2024 19
Thread States in Busy Wait
• Always Runnable – in either ReadyToRun or
Running (on a CPU)
Runnable
Ready to
Run
Running
• Can use lots of processor cycles and make
system unresponsive!
Apr 21, 2024 20
For safety can add sleep into loop
• Prevents processor hogging but increases
average latency
Runnable
Ready to
Run
Running
Thread.sleep
Timed_ (duration)
waiting
Apr 21, 2024 21
getAndSet method
v.getAndSet(arg)
• sets variable v to arg
• returns the value of v before update
Apr 21, 2024 22
Summary
• Can use lots CPU cycles
is it free?
• Low level is it free?
is it free?
• Programming Error prone is it free?
is it free?
• But Fast
(as no OS overhead)
Apr 21, 2024 24
Solutions
• Blocking solutions
– Semaphores
– Monitors
• Intrinsic
• Extrinsic
Apr 21, 2024 25
Semaphores
• Many different names & notations
• Java • Tanenbaum
.acquire( ) = down(&semaphore)
.release( ) = up(&semaphore)
<Read Oracle API> <Read Tanenbaum 2.3.6 Mutexes>
Apr 21, 2024 26
Java’s ‘Permit’ View
Conceptually, a semaphore maintains a set of permits.
Each acquire() blocks until a permit is available, and
then takes it.
Each release() adds a permit, potentially releasing a
blocking acquirer.
However, no actual permit objects are used;
the Semaphore just keeps a count of the number
available and acts accordingly.
<See https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Semaphore.html>
Apr 21, 2024 27
Using Semaphores for MX
Apr 21, 2024 30
Acquire Method
Apr 21, 2024 31
Acquire Method
Apr 21, 2024 32
Acquire Method: if No Permits Left
Apr 21, 2024 33
Release Method: with Blocked Thread
Apr 21, 2024 34
Release Method: No one blocked
Permit is “transferred”
back to Semaphore
Apr 21, 2024 35
Threads ‘blocked’ on a Semaphore are in
state “Waiting”
Runnable
Ready to
Run
Running
sem.acquire() on
semaphore with no
permits blocks
calling thread on the
Waiting Waiting Q
Apr 21, 2024 36
Made Runnable when they aquire Permit
Runnable
Ready to
Run
Running
sem.release()
Waiting
Implementation for multiple semaphores likely to
use multiple Wait Queues
Runnable
TCB TCB
Ready to
Run
registers registers
head
Runnable Q
. .
tail .
.
.
.
Running
TCB TCB
registers registers
head . .
Waiting Q . .
sem.release() tail . .
TCB
registers
head .
Waiting Q tail
.
.
Waiting TCB
TCB TCB
registers
registers registers
.
.
head . .
Waiting Q tail
.
.
.
.
.
Apr 21, 2024 38
Semaphore: Example Code
Apr 21, 2024 39
Use for Mutual Exclusion
//Declare semaphore and initialise to one permit
//(As only want one Thread instance in CR at a time
Semaphore sem = new Semaphore(1);
//In Thread
sem.acquire();
//Acquired MX control so do stuff
sem.release(); //Release permit
Apr 21, 2024 40
Semaphores - Summary
• Must initialise to correct number of permits!
• .acquire ( ) and .release ( ) methods can easily
be missed out!
• Confusingly can also be used for signal/wait
synchronisation
Apr 21, 2024 41
Solutions
• Blocking solutions
– Semaphores
– Monitors
• Intrinsic
• Extrinsic
• Note that Intrinsic Monitors comprise an implicit lock
mechanism + one implicit condition variable(s). Here
we will just consider the lock mechanism & syntax.
Apr 21, 2024 42
Intrinsic MonitorsEach instance of a
public class SynchronizedCounter { ‘synchronized’ class
private int c = 0; has its own ‘monitor;’
public synchronized void increment() {
c++;
}
public synchronized void decrement() {
c--;
}
}
• Only one Thread instance is allowed to ‘own’ an object’s monitor at a time.
• A thread can only execute a synchronised method if it owns the objects monitor.
• If another thread already owns the object’s monitor then the new caller will ne blocked from
proceeding.
Read: https://docs.oracle.com/javase/tutorial/essential/concurrency/syncmeth.html
Apr 21, 2024 43
Intrinsic Monitors
Thread tries to acquire control
(ownership) of monitor
(Thread will be blocked
from proceeding if another
thread already has control)
Release control (ownership) of monitor
Apr 21, 2024 48
Intrinsic Monitors
You can have multiple synchronised
methods within a class
Apr 21, 2024 49
Intrinsic Monitors
But each object only has one monitor
(lock mechanism)
Apr 21, 2024 50
Intrinsic monitors
• Mut Ex mechanism clear
• No separate .acquire/.release methods
• No initialisation
• But only one monitor per object
Apr 21, 2024 51
Summary
• 4 Different MX mechanisms
– Busy Waiting
• Java Atomic variables enhanced versions of TSL
– Blocking solutions
• Semaphores
• Monitors
– Intrinsic
– Extrinsic
Apr 21, 2024 52
End of this slide set
Apr 21, 2024 53
