, Lecture Con.02
Semester 1, 2022
©The University of Melbourne
SWEN90004 (2022) Java threads; mutual exclusion 1 / 28
Copyright By PowCoder代写 加微信 powcoder
Modelling Complex Software Systems
Java threads; mutual exclusion
Safety and liveness properties Mutual exclusion
Threads in Java (possibly)
Announcements:
Tutorials begin next week (Tuesday, Wednesday or Friday) Assignment 1 released!
We will cover relevant material next week!
SWEN90004 (2022) Java threads; mutual exclusion
Safety and liveness properties
We distinguish between safety and liveness properties of concurrent systems.
Roughly, safety means that “nothing bad will ever happen” and liveness means that “something good eventually happens”.
Interference (or rather its absence) is an archetypal safety property. Deadlock (or rather its absence) is an archetypal liveness property.
SWEN90004 (2022) Java threads; mutual exclusion
Deadlock is a situation where a set of processes are unable to make any further progress, because of mutually incompatible demands they make of shared resources.
Concurrent languages provide means for mutual exclusion and for processes to wait for required resources. They also use a principle of no preemption, that is, a process has to give up resources voluntarily.
We will return to these conditions later.
SWEN90004 (2022) Java threads; mutual exclusion 4 / 28
Potential deadlock (two processes)
P wants s held held by
by r wants Q actually
requires s requires r
Java threads; mutual exclusion
deadlock inevitable
infeasible zone
deadlock happens
The mutual exclusion (Mutex) problem
N processes (here, N = 2) are executing infinite loops, each alternating between a critical and a non-critical section. A process may halt in its non-critical section, but not in its critical section.
class P extends Thread {
while (true) { non_critical_P(); pre_protocol_P(); critical_P(); post_protocol_P();
class Q extends Thread {
while (true) { non_critical_Q(); pre_protocol_Q(); critical_Q(); post_protocol_Q();
Shared variables are only written to in the critical section, so in order to avoid race conditions, only one thread can be in its critical section at any time.
SWEN90004 (2022) Java threads; mutual exclusion 6 / 28
Desirable properties of a Mutex solution
There are a number of ways to solve this problem, but a solution should have the following properties:
Mutual exclusion: only one process may be active in its critical section at a time.
No deadlock: if one or more processes are trying to enter their critical section, one must eventually succeed.
No starvation: if a process is trying to enter its critical section, it must eventually succeed.
Also desirable:
Handles lack of contention: if only one process is trying to enter its critical section, it must succeed with minimal overhead.
SWEN90004 (2022) Java threads; mutual exclusion 7 / 28
Rules of the game
No variable used in a protocol is also used in critical/non-critical sections, and vice versa.
Load, store, and test of common memory variables are atomic operations.
There must be progress through critical sections: once a process reaches its critical section, it must eventually reach the end of the section.
We cannot assume progress through non-critical sections: while in such a section, a process might terminate or enter an infinite loop.
SWEN90004 (2022) Java threads; mutual exclusion
First attempt
static int turn = 1;
class P extends Thread { public void run() {
while (true) {
p1: non_critical_P();
p2: while (turn != 1); p3: critical_P();
class Q extends Thread { public void run() {
while (true) {
q1: non_critical_Q();
q2: while (turn != 2); q3: critical_Q();
Note that while (! property); is just a way of implementing an await(property) statement.
SWEN90004 (2022) Java threads; mutual exclusion 9 / 28
Properties of first attempt
Mutual exclusion?:
No deadlock?:
No starvation?:
Handles lack of contention?:
SWEN90004 (2022) Java threads; mutual exclusion 10 / 28
Second attempt
static int p = 0; static int q = 0;
class P extends Thread { public void run() {
while (true) {
class Q extends Thread { public void run() {
while (true) {
p1: p2: p3: p4: p5:
non_critical_P(); while (q != 0); p=1; critical_P(); p=0;
q1: q2: q3: q4: q5:
non_critical_Q(); while (p != 0); q=1; critical_Q(); q=0;
Variable p is set to 1 when thread P wants to enter its critical
section, and then set to 0 when it is done (same for q and Q).
SWEN90004 (2022) Java threads; mutual exclusion 11 / 28
Properties of second attempt
Mutual exclusion?:
No deadlock?:
No starvation?:
Handles lack of contention?:
SWEN90004 (2022) Java threads; mutual exclusion 12 / 28
Third attempt
static int p = 0; static int q = 0;
class P extends Thread { public void run() {
while (true) {
p1: non_critical_P();
p3: while (q != 0);
p4: critical_P();
class Q extends Thread { public void run() {
while (true) {
q1: non_critical_Q();
q3: while (p != 0);
q4: critical_Q();
Each process now sets its want flag before waiting.
SWEN90004 (2022) Java threads; mutual exclusion 13 / 28
Properties of third attempt
Mutual exclusion?:
No deadlock?:
No starvation?:
Handles lack of contention?:
SWEN90004 (2022) Java threads; mutual exclusion 14 / 28
Fourth attempt
static int p = 0; static int q = 0;
class P extends Thread { public void run() {
while (true) {
class Q extends Thread { public void run() {
while (true) {
p1: p2: p3: p4: p5:
non_critical_P(); p=1;
while (q != 0) {
p = 0; p = 1;
q1: q2: q3: q4: q5:
non_critical_Q(); q=1;
while (p != 0) {
q = 0; q = 1;
p6: critical_P(); p7: p=0;
q6: critical_Q(); q7: q=0;
SWEN90004 (2022) Java threads; mutual exclusion 15 / 28
Properties of fourth attempt
Mutual exclusion?:
No deadlock?:
No starvation?:
Handles lack of contention?:
SWEN90004 (2022) Java threads; mutual exclusion 16 / 28
Fifth attempt: Dekker’s algorithm
static int turn = 1; static int p = 0; static int q = 0;
while (true) {
while (true) {
p0: p1: p2: p3: p4: p5: p6:
p7: p8: p9: }
non_critical_P(); p = 1;
while (q != 0) {
if (turn == 2) { p = 0;
while (turn == 2); p = 1;
critical_P(); turn = 2;
q0: q1: q2: q3: q4: q5: q6:
q7: q8: q9: }
non_critical_Q(); q = 1;
while (p != 0) {
if (turn == 1) { q = 0;
while (turn == 1); q = 1;
critical_Q(); turn = 1;
SWEN90004 (2022) Java threads; mutual exclusion 17 / 28
Properties of Dekker’s algorithm
Mutual exclusion?:
No deadlock?:
No starvation?:
Handles lack of contention?:
SWEN90004 (2022) Java threads; mutual exclusion 18 / 28
Threads in Java
Java calls a process a “thread”.
There are two ways to create threads in Java. The first is to extend
the java.lang.Thread class:
class MyThread extends Thread { public void run() {
//insert process code here
System.out.println(“SWEN90004 thread”); for (int i = 0; i < 10; i++) {
System.out.println("\t thread " + i); }
SWEN90004 (2022) Java threads; mutual exclusion 19 / 28
Threads in Java
Then, create an instance of this class:
public class UseMyThread {
public static void main(String [] args) {
Thread myThread = new MyThread();
myThread.start(); }
The first statement creates the thread.
The call to start() causes the new thread to call its run() method
and execute it independently of the caller.
SWEN90004 (2022) Java threads; mutual exclusion 20 / 28
Threads in Java, second way
As Java does not support multiple inheritance, you may not always be able to extend class Thread.
The alternative (and usually recommended!) way to create a thread is to implement the Runnable interface:
class MyRunnable implements Runnable { //we must implement the "run()" method public void run() {
System.out.println("SWEN90004 runnable"); for (int i = 0; i < 10; i++) {
System.out.println("\t runnable " + i); }
SWEN90004 (2022) Java threads; mutual exclusion 21 / 28
Threads in Java, second way
Then, create an instance of this using Thread:
public class UseMyRunnable {
public static void main(String [] args) {
Thread myRunnable =
new Thread(new MyRunnable());
myRunnable.start(); }
SWEN90004 (2022) Java threads; mutual exclusion 22 / 28
Thread states
Runnable Running
Non-runnable Dead A thread that is alive is always in one of three states:
running: it is currently executing;
runnable: it is currently not executing but is ready to execute; or
non-runnable: it is not running and is not ready to run—may be waiting on some input or shared data to become unlocked.
SWEN90004 (2022) Java threads; mutual exclusion 23 / 28
Java thread primitives
Calling start() causes the Java virtual machine to execute the run() method in a dedicated thread, concurrent with the calling code.
A thread stops executing when run() finishes.
(A thread can also be stopped using stop(), but this method is
deprecated and it’s use is discouraged.)
A thread can be suspended for a specified amount of time using the sleep(long milliseconds) method.
(A thread can also be suspended indefinitely using suspend(), and awoken using resume(), but these methods are deprecated, and their use is discouraged.)
SWEN90004 (2022) Java threads; mutual exclusion 24 / 28
Java thread primitives
We can test whether a thread is running using the isAlive() method.
The method yield() causes the current thread to pause, going from “running” status to “runnable”.
When it goes from “runnable” to “running” (ie, executes run() again) is a matter for a runtime system’s scheduler to decide.
Calling t.join() suspends the caller until thread t has completed. (In this sense the two join together.)
SWEN90004 (2022) Java threads; mutual exclusion 25 / 28
Additional suspension states
To account for Java’s concurrency primitives fully, we need to consider additional states that a thread can be in:
Having called sleep(); having called join();
waiting for a lock to be released (having called wait() – we will talk about this more next week).
A thread can be interrupted through Thread.interrupt().
If interrupted in one of the three states above, it will return to “runnable” state, and sleep(), join(), or wait() will throw an InterruptedException.
SWEN90004 (2022) Java threads; mutual exclusion
Interference example in Java
class Count extends Thread { static volatile int n = 0;
public void run() {
for (int i = 0; i < 10; i++) {
n = temp + 1; }
public static void main(String[] args) { Count p = new Count();
Count q = new Count();
p.start();
q.start();
try { p.join(); q.join(); }
catch (InterruptedException e) { } System.out.println("The final value of n is " + n);
SWEN90004 (2022) Java threads; mutual exclusion
Exercise and recommended reading
One of the tutorial problems for next week is to apply each of these attempted solutions to Count.java – note that many of them will ‘appear’ to work reliably!
More formal analysis of mutex solution attempts is covered in M. Ben-Ari, Principles of Concurrent and Distributed
Programming, , 2nd edition, 2006.
SWEN90004 (2022) Java threads; mutual exclusion
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com