程序代写代做代考 Java concurrency Book Chapter 2

Book Chapter 2

Concurrency: processes & threads 1
©Magee/Kramer 2nd Edition

Chapter 2

Processes & Threads

Concurrency: processes & threads 2
©Magee/Kramer 2nd Edition

concurrent processes

We structure complex systems as
sets of simpler activities, each
represented as a sequential process.
Processes can overlap or be
concurrent, so as to reflect the
concurrency inherent in the physical
world, or to offload time-consuming
tasks, or to manage communications or
other devices.

Designing concurrent software can be
complex and error prone. A rigorous
engineering approach is essential.

Concept of a process as
a sequence of actions.

Model processes as
finite state machines.

Program processes as
threads in Java.

Concurrency: processes & threads 3
©Magee/Kramer 2nd Edition

processes and threads

Concepts: processes – units of sequential execution.

Models: finite state processes (FSP)
to model processes as sequences of actions.
labelled transition systems (LTS)
to analyse, display and animate behavior.

Practice: Java threads

Concurrency: processes & threads 4
©Magee/Kramer 2nd Edition

2.1 Modeling Processes

Models are described using state machines,
known as Labelled Transition Systems LTS.
These are described textually as finite state
processes (FSP) and displayed and analysed by
the LTSA analysis tool.

♦ LTS – graphical form
♦ FSP – algebraic form

Concurrency: processes & threads 5
©Magee/Kramer 2nd Edition

modeling processes

A process is the execution of a sequential program. It is
modeled as a finite state machine which transits from
state to state by executing a sequence of atomic actions.

off

0 1
a light switch

LTS

a sequence of
actions or traceon off on off on off ……….

Can finite state models produce infinite traces?

Concurrency: processes & threads 6
©Magee/Kramer 2nd Edition

FSP – action prefix

If x is an action and P a process then (x-> P)
describes a process that initially engages in the action
x and then behaves exactly as described by P.

ONESHOT = (once -> STOP). ONESHOT state
machine

(terminating process)

once

0 1

Convention: actions begin with lowercase letters
PROCESSES begin with uppercase letters

Concurrency: processes & threads 7
©Magee/Kramer 2nd Edition

FSP – action prefix & recursion

SWITCH = OFF,
OFF = (on -> ON),
ON = (off-> OFF).

Repetitive behaviour uses recursion:

Substituting to get a more succinct definition:

off

0 1

SWITCH = OFF,
OFF = (on ->(off->OFF)).

And again:

SWITCH = (on->off->SWITCH).

Concurrency: processes & threads 8
©Magee/Kramer 2nd Edition

animation using LTSA

The LTSA animator can be
used to produce a trace.

Ticked actions are eligible
for selection.

In the LTS, the last action is
highlighted in red.

off

0 1

Concurrency: processes & threads 9
©Magee/Kramer 2nd Edition

FSP – action prefix

FSP model of a traffic light :
TRAFFICLIGHT = (red->orange->green->orange

-> TRAFFICLIGHT).

LTS generated using LTSA:
red orange green

orange

0 1 2 3

Trace:
red orange green orange red orange green …

Concurrency: processes & threads 10
©Magee/Kramer 2nd Edition

FSP – choice

If x and y are actions then (x-> P | y-> Q)
describes a process which initially engages in either of
the actions x or y. After the first action has
occurred, the subsequent behavior is described by P if
the first action was x and Q if the first action was y.

Who or what makes the choice?
Is there a difference between input and
output actions?

Concurrency: processes & threads 11
©Magee/Kramer 2nd Edition

FSP – choice

FSP model of a drinks machine :
DRINKS = (red->coffee->DRINKS

|blue->tea->DRINKS
).

LTS generated using LTSA:

Possible traces?

red

blue

coffee

tea

0 1 2

Concurrency: processes & threads 12
©Magee/Kramer 2nd Edition

Non-deterministic choice

Process (x-> P | x -> Q) describes a process which
engages in x and then behaves as either P or Q.

COIN = (toss->HEADS|toss->TAILS),
HEADS= (heads->COIN),
TAILS= (tails->COIN).

Tossing a
coin.

toss

heads

tails

0 1 2

Possible traces?

Concurrency: processes & threads 13
©Magee/Kramer 2nd Edition

Modeling failure

How do we model an unreliable communication channel
which accepts in actions and if a failure occurs produces
no output, otherwise performs an out action?

Use non-determinism…

CHAN = (in->CHAN
|in->out->CHAN
).

out

0 1

Concurrency: processes & threads 14
©Magee/Kramer 2nd Edition

FSP – indexed processes and actions

Single slot buffer that inputs a value in the range 0 to 3
and then outputs that value:

BUFF = (in[i:0..3]->out[i]-> BUFF).
equivalent to

or using a process parameter with default value:

BUFF = (in[0]->out[0]->BUFF
|in[1]->out[1]->BUFF
|in[2]->out[2]->BUFF
|in[3]->out[3]->BUFF
).

indexed actions
generate labels of
the form
action.index

BUFF(N=3) = (in[i:0..N]->out[i]-> BUFF).

Concurrency: processes & threads 15
©Magee/Kramer 2nd Edition

FSP – indexed processes and actions

const N = 1
range T = 0..N
range R = 0..2*N

SUM = (in[a:T][b:T]->TOTAL[a+b]),
TOTAL[s:R] = (out[s]->SUM).

index expressions to
model calculation:

in.0.0

in.0.1
in.1.0

in.1.1

out.0

out.1

out.2

0 1 2 3

Local indexed process
definitions are equivalent
to process definitions
for each index value

Concurrency: processes & threads 16
©Magee/Kramer 2nd Edition

FSP – guarded actions

The choice (when B x -> P | y -> Q) means that
when the guard B is true then the actions x and y are
both eligible to be chosen, otherwise if B is false then
the action x cannot be chosen.

COUNT (N=3) = COUNT[0],
COUNT[i:0..N] = (when(iCOUNT[i+1]

|when(i>0) dec->COUNT[i-1]
).

inc inc

dec

inc

dec dec

0 1 2 3

Concurrency: processes & threads 17
©Magee/Kramer 2nd Edition

FSP – guarded actions

A countdown timer which beeps after N ticks, or can be
stopped.
COUNTDOWN (N=3) = (start->COUNTDOWN[N]),
COUNTDOWN[i:0..N] =

(when(i>0) tick->COUNTDOWN[i-1]
|when(i==0)beep->STOP
|stop->STOP
).

start

stop

tick

stop

tick

stop

tick beep
stop

0 1 2 3 4 5

Concurrency: processes & threads 18
©Magee/Kramer 2nd Edition

FSP – guarded actions

What is the following FSP process equivalent to?

const False = 0
P = (when (False) doanything->P).

Answer:

STOP

Concurrency: processes & threads 19
©Magee/Kramer 2nd Edition

FSP – process alphabets

The alphabet of a process is the set of actions in
which it can engage.

Process alphabets are
implicitly defined by the
actions in the process
definition.

The alphabet of a process
can be displayed using the
LTSA alphabet window.

Process:
COUNTDOWN

Alphabet:
{ beep,
start,
stop,
tick

}

Concurrency: processes & threads 20
©Magee/Kramer 2nd Edition

FSP – process alphabet extension

Alphabet extension can be used to extend the implicit
alphabet of a process:

Alphabet of WRITER is the set {write[0..3]}
(we make use of alphabet extensions in later chapters)

WRITER = (write[1]->write[3]->WRITER)
+{write[0..3]}.

Concurrency: processes & threads 21
©Magee/Kramer 2nd Edition

Revision & Wake-up Exercise

In FSP, model a process FILTER, that exhibits the
following repetitive behavior:

inputs a value v between 0 and 5, but only outputs it if
v <= 2, otherwise it discards it. FILTER = (in[v:0..5] -> DECIDE[v]),

DECIDE[v:0..5] = ( ? ).

Concurrency: processes & threads 22
©Magee/Kramer 2nd Edition

2.2 Implementing processes

Modeling processes as
finite state machines
using FSP/LTS.

Implementing threads
in Java.

Note: to avoid confusion, we use the term process when referring to
the models, and thread when referring to the implementation in Java.

Concurrency: processes & threads 23
©Magee/Kramer 2nd Edition

Implementing processes – the OS view

A (heavyweight) process in an operating system is represented by its code,
data and the state of the machine registers, given in a descriptor. In order to
support multiple (lightweight) threads of control, it has multiple stacks, one
for each thread.

D ata Code

OS Process

D escriptor

Thread 1 Thread 2 Thread n

Stack Stack Stack

D escriptor D escriptor

D escriptor

Concurrency: processes & threads 24
©Magee/Kramer 2nd Edition

threads in Java

A Thread class manages a single sequential thread of control.
Threads may be created and deleted dynamically.

The Thread class executes instructions from its method
run(). The actual code executed depends on the
implementation provided for run() in a derived class.

Thread

run()

MyThread

run()

class MyThread extends Thread {
public void run() {

//……
}

}

Creating a thread object:
Thread a = new MyThread();

Concurrency: processes & threads 25
©Magee/Kramer 2nd Edition

threads in Java

Since Java does not permit multiple inheritance, we often
implement the run() method in a class not derived from Thread but
from the interface Runnable.

Runnable

run()

MyRun

run()

public interface Runnable {
public abstract void run();

}

class MyRun implements Runnable{
public void run() {

//…..
}

}

Thread
target

Creating a thread object:
Thread b = new Thread(new MyRun());

Concurrency: processes & threads 26
©Magee/Kramer 2nd Edition

thread life-cycle in Java

An overview of the life-cycle of a thread as state transitions:

Created Alive

Terminated

new Thread()

start()

stop(), or
run() returnsstop()

The predicate isAlive() can be
used to test if a thread has been started but
not terminated. Once terminated, it cannot
be restarted (cf. mortals).

start() causes the thread to call its
run() method.

Concurrency: processes & threads 27
©Magee/Kramer 2nd Edition

thread alive states in Java

Once started, an alive thread has a number of substates :

Runnable Non-Runnable
suspend()

resume()

yield()

Running

dispatch

suspend()

start()

stop(), or
run() returnsAlso, wait() makes a Thread Non-Runnable,

and notify() makes it Runnable
(used in later chapters).

sleep()

Alive

Java thread lifecycle – an FSP specification

THREAD = CREATED,
CREATED = (start ->RUNNABLE

|stop ->TERMINATED),
RUNNING = ({suspend,sleep}->NON_RUNNABLE

|yield ->RUNNABLE
|{stop,end} ->TERMINATED
|run ->RUNNING),

RUNNABLE = (suspend ->NON_RUNNABLE
|dispatch ->RUNNING
|stop ->TERMINATED),

NON_RUNNABLE = (resume ->RUNNABLE
|stop ->TERMINATED),

TERMINATED = STOP.

Java thread lifecycle – an FSP specification

end, run,
dispatch are
not methods of
class Thread.

States 0 to 4 correspond to CREATED, TERMINATED, RUNNABLE,
RUNNING, and NON-RUNNABLE respectively.

start

stop

suspend

dispatch

stop

suspend
sleep

yield

end

run

stop

resume

0 1 2 3 4

CountDown timer example

COUNTDOWN (N=3) = (start->COUNTDOWN[N]),
COUNTDOWN[i:0..N] =

(when(i>0) tick->COUNTDOWN[i-1]
|when(i==0)beep->STOP
|stop->STOP
).

Implementation in Java?

CountDown timer – class diagram

Applet

init()
start()
stop()
run()
tick()
beep()

Runnable

CountDown

NumberCanvas

setvalue()

Threadcounter

display

target

The class NumberCanvas
provides the display canvas.

The class CountDown derives from Applet and contains the
implementation of the run() method which is required by Thread.

CountDown class

public class CountDown extends Applet
implements Runnable {

Thread counter; int i;
final static int N = 10;
AudioClip beepSound, tickSound;
NumberCanvas display;

public void init() {…}
public void start() {…}
public void stop() {…}
public void run() {…}
private void tick() {…}
private void beep() {…}

}

CountDown class – start(), stop() and run()

COUNTDOWN Model
public void start() {

counter = new Thread(this);
i = N; counter.start();

}

public void stop() {
counter = null;

}

public void run() {
while(true) {

if (counter == null) return;
if (i>0) { tick(); –i; }
if (i==0) { beep(); return;}

}
}

start ->

stop ->

COUNTDOWN[i] process
recursion as a while loop

STOP
when(i>0) tick -> CD[i-1]
when(i==0)beep -> STOP

STOP when run() returns

CountDown

counter thread

start()

new Thread(this)

target.run()

createdcounter.start()

alive

terminated

init()

tick()

beep()

CountDown execution

CountDown

counter thread

stop()

new Thread(this)

target.run()

createdcounter.start()

counter=null

alive

terminated

tick()
tick()

CountDown execution

start()
init()

Summary

Concepts
process – unit of concurrency, execution of a program

Models
LTS to model processes as state machines – sequences of
atomic actions

FSP to specify processes using prefix “->”, choice ” | ”
and recursion.

Practice
Java threads to implement processes.

Thread lifecycle – created, running, runnable, non-
runnable, terminated.

Related Posts