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