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

Book Chapter 3

Concurrency: concurrent execution 1
©Magee/Kramer 2nd Edition

Chapter 3

Concurrent Execution

Concurrency: concurrent execution 2
©Magee/Kramer 2nd Edition

Concurrent execution

Concepts: processes – concurrent execution
and interleaving.

process interaction.

Models: parallel composition of asynchronous processes
– interleaving

interaction – shared actions
process labeling, and action relabeling and hiding
structure diagrams

Practice: Multithreaded Java programs

Concurrency: concurrent execution 3
©Magee/Kramer 2nd Edition

Definitions

Concurrency
Logically simultaneous processing.

Does not imply multiple processing
elements (PEs). Requires
interleaved execution on a single PE.
Parallelism

Physically simultaneous processing.
Involves multiple PEs and/or
independent device operations.

A

Time

B

C

Both concurrency and parallelism require controlled access to
shared resources . We use the terms parallel and concurrent
interchangeably and generally do not distinguish between real and
pseudo-concurrent execution.

Concurrency: concurrent execution 4
©Magee/Kramer 2nd Edition

3.1 Modeling Concurrency

How should we model process execution speed?
arbitrary speed

(we abstract away time)

How do we model concurrency?
arbitrary relative order of actions from different processes

(interleaving but preservation of each process order )

What is the result?
provides a general model independent of scheduling

(asynchronous model of execution)

Concurrency: concurrent execution 5
©Magee/Kramer 2nd Edition

parallel composition – action interleaving

If P and Q are processes then (P||Q) represents the
concurrent execution of P and Q. The operator || is
the parallel composition operator.

ITCH = (scratch->STOP).
CONVERSE = (think->talk->STOP).

||CONVERSE_ITCH = (ITCH || CONVERSE).
Disjoint

alphabets

think talk scratch
think scratch talk
scratch think talk

Possible traces as
a result of action
interleaving.

Concurrency: concurrent execution 6
©Magee/Kramer 2nd Edition

parallel composition – action interleaving

(0,0) (0,1) (0,2) (1,2) (1,1) (1,0)

from CONVERSEfrom ITCH

2 states 3 states

ITCH

scratch

0 1
CONVERSE

think talk

0 1 2

CONVERSE_ITCH

scratch

think

scratch

talk scratch

talk think

0 1 2 3 4 5

2 x 3 states

Concurrency: concurrent execution 7
©Magee/Kramer 2nd Edition

parallel composition – algebraic laws

Commutative: (P||Q) = (Q||P)
Associative: (P||(Q||R)) = ((P||Q)||R)

= (P||Q||R).

Clock radio example:
CLOCK = (tick->CLOCK).
RADIO = (on->off->RADIO).

||CLOCK_RADIO = (CLOCK || RADIO).

LTS? Traces? Number of states?

Concurrency: concurrent execution 8
©Magee/Kramer 2nd Edition

modeling interaction – shared actions

If processes in a composition have actions in common,
these actions are said to be shared. Shared actions are
the way that process interaction is modeled. While
unshared actions may be arbitrarily interleaved, a
shared action must be executed at the same time by all
processes that participate in the shared action.

MAKER
synchronizes
with USER
when ready.

MAKER = (make->ready->MAKER).
USER = (ready->use->USER).

||MAKER_USER = (MAKER || USER).

Non-disjoint
alphabets

LTS? Traces? Number of states?

Concurrency: concurrent execution 9
©Magee/Kramer 2nd Edition

modeling interaction – handshake

A handshake is an action acknowledged by another:

MAKERv2 = (make->ready->used->MAKERv2).
USERv2 = (ready->use->used ->USERv2).

||MAKER_USERv2 = (MAKERv2 || USERv2).

3 states
3 states

3 x 3
states?

make ready use

used

0 1 2 3
4 states
Interaction
constrains
the overall
behaviour.

Concurrency: concurrent execution 10
©Magee/Kramer 2nd Edition

modeling interaction – multiple processes

MAKE_A = (makeA->ready->used->MAKE_A).
MAKE_B = (makeB->ready->used->MAKE_B).
ASSEMBLE = (ready->assemble->used->ASSEMBLE).

||FACTORY = (MAKE_A || MAKE_B || ASSEMBLE).

Multi-party synchronization:

makeA

makeB makeA ready assemble

used
makeB

0 1 2 3 4 5

Concurrency: concurrent execution 11
©Magee/Kramer 2nd Edition

composite processes

A composite process is a parallel composition of primitive
processes. These composite processes can be used in the
definition of further compositions.

||MAKERS = (MAKE_A || MAKE_B).

||FACTORY = (MAKERS || ASSEMBLE).

Substituting the definition for MAKERS in FACTORY and applying the
commutative and associative laws for parallel composition results in
the original definition for FACTORY in terms of primitive processes.

||FACTORY = (MAKE_A || MAKE_B || ASSEMBLE).

Concurrency: concurrent execution 12
©Magee/Kramer 2nd Edition

process instances and labeling

a:P prefixes each action label in the alphabet of P with a.

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

||TWO_SWITCH = (a:SWITCH || b:SWITCH).

Two instances of a switch process:

a:SWITCH
a.on

a.off

0 1
b:SWITCH

b.on

b.off

0 1

||SWITCHES(N=3) = (forall[i:1..N] s[i]:SWITCH).
||SWITCHES(N=3) = (s[i:1..N]:SWITCH).

An array of instances of the switch process:

Concurrency: concurrent execution 13
©Magee/Kramer 2nd Edition

process labeling by a set of prefix labels

{a1,..,ax}::P replaces every action label n in the
alphabet of P with the labels a1.n,…,ax.n. Further,
every transition (n->X) in the definition of P is
replaced with the transitions ({a1.n,…,ax.n} ->X).

Process prefixing is useful for modeling shared resources:
RESOURCE = (acquire->release->RESOURCE).
USER = (acquire->use->release->USER).

||RESOURCE_SHARE = (a:USER || b:USER
|| {a,b}::RESOURCE).

Concurrency: concurrent execution 14
©Magee/Kramer 2nd Edition

process prefix labels for shared resources

How does the model ensure
that the user that acquires
the resource is the one to
release it?

a:USER
a.acquire a.use

a.release

0 1 2
b:USER

b.acquire b.use

b.release

0 1 2

{a,b}::RESOURCE
a.acquire
b.acquire

a.release
b.release

0 1

RESOURCE_SHARE

a.acquire

b.acquire b.use

b.release

a.use

a.release

0 1 2 3 4

Concurrency: concurrent execution 15
©Magee/Kramer 2nd Edition

action relabeling

Relabeling functions are applied to processes to change
the names of action labels. The general form of the
relabeling function is:

/{newlabel_1/oldlabel_1,… newlabel_n/oldlabel_n}.

Relabeling to ensure that composed
processes synchronize on particular actions.

CLIENT = (call->wait->continue->CLIENT).
SERVER = (request->service->reply->SERVER).

Note that both newlabel and oldlabel can be sets of labels.

Concurrency: concurrent execution 16
©Magee/Kramer 2nd Edition

action relabeling

||CLIENT_SERVER = (CLIENT || SERVER)
/{call/request, reply/wait}.

CLIENT
call reply

continue

0 1 2
SERVER

call service

reply

0 1 2

CLIENT_SERVER call service reply

continue

0 1 2 3

Concurrency: concurrent execution 17
©Magee/Kramer 2nd Edition

action relabeling – prefix labels

An alternative formulation of the client server system is
described below using qualified or prefixed labels:

SERVERv2 = (accept.request
->service->accept.reply->SERVERv2).

CLIENTv2 = (call.request
->call.reply->continue->CLIENTv2).

||CLIENT_SERVERv2 = (CLIENTv2 || SERVERv2)
/{call/accept}.

Concurrency: concurrent execution 18
©Magee/Kramer 2nd Edition

action hiding – abstraction to reduce complexity

When applied to a process P, the hiding operator \{a1..ax}
removes the action names a1..ax from the alphabet of P
and makes these concealed actions “silent”. These silent
actions are labeled tau. Silent actions in different
processes are not shared.

Sometimes it is more convenient to specify the set of
labels to be exposed….

When applied to a process P, the interface
operator @{a1..ax} hides all actions in the
alphabet of P not labeled in the set a1..ax.

Concurrency: concurrent execution 19
©Magee/Kramer 2nd Edition

action hiding

USER = (acquire->use->release->USER)
\{use}.

USER = (acquire->use->release->USER)
@{acquire,release}.

The following definitions are equivalent:

acquire tau

release

0 1 2

Minimization removes hidden
tau actions to produce an
LTS with equivalent
observable behavior.

acquire

release

0 1

Concurrency: concurrent execution 20
©Magee/Kramer 2nd Edition

structure diagrams – systems as interacting processes

P a
b

Process P with
alphabet {a,b}.

P a b Qm Parallel Composition
(P||Q) / {m/a,m/b,c/d}

P Qa

c dc

x xx

S
yx

Composite process
||S = (P||Q) @ {x,y}

Concurrency: concurrent execution 21
©Magee/Kramer 2nd Edition

structure diagrams

We use structure diagrams to capture the structure
of a model expressed by the static combinators:
parallel composition, relabeling and hiding.

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

||TWOBUF = ?

a:BUFF b:BUFF
a.out

TWOBUFF

outin
inoutin out

Concurrency: concurrent execution 22
©Magee/Kramer 2nd Edition

structure diagrams

Structure diagram for CLIENT_SERVER ?

CLIENT call request SERVERcall

replywait reply servicecontinue

Structure diagram for CLIENT_SERVERv2 ?

CLIENTv2 call accept SERVERv2call

servicecontinue

Concurrency: concurrent execution 23
©Magee/Kramer 2nd Edition

structure diagrams – resource sharing

a:USER
printer

b:USER
printer

printer:
RESOURCE

acquire
release

PRINTER_SHARE

RESOURCE = (acquire->release->RESOURCE).
USER = (printer.acquire->use

->printer.release->USER)\{use}.

||PRINTER_SHARE
= (a:USER||b:USER||{a,b}::printer:RESOURCE).

Concurrency: concurrent execution 24
©Magee/Kramer 2nd Edition

3.2 Multi-threaded Programs in Java

Concurrency in Java occurs when more than one thread is alive.
ThreadDemo has two threads which rotate displays.

Concurrency: concurrent execution 25
©Magee/Kramer 2nd Edition

ThreadDemo model

ROTATOR = PAUSED,
PAUSED = (run->RUN | pause->PAUSED

|interrupt->STOP),
RUN = (pause->PAUSED |{run,rotate}->RUN

|interrupt->STOP).

||THREAD_DEMO = (a:ROTATOR || b:ROTATOR)

/{stop/{a,b}.interrupt}.

b:ROTATOR

a.run

a.pause

a.rotate

b.run

b.pause

b.rotate

THREAD_DEMO

a:ROTATOR
stop

Interpret
run,
pause,
interrupt
as inputs,
rotate as
an output.

Concurrency: concurrent execution 26
©Magee/Kramer 2nd Edition

ThreadDemo implementation in Java – class diagram
ThreadDemo creates two ThreadPanel displays when initialized.
ThreadPanel manages the display and control buttons, and delegates calls to
rotate() to DisplayThread. Rotator implements the runnable interface.

Applet

ThreadDemo ThreadPanel

rotate()
start()
stop()

A,B

init()
start()
stop()

Runnable

Rotator

run()

GraphicCanvas
Panel

Thread

DisplayThread

display

thread

target

rotate()

Concurrency: concurrent execution 27
©Magee/Kramer 2nd Edition

Rotator class

class Rotator implements Runnable {

public void run() {
try {

while(true) ThreadPanel.rotate();
} catch(InterruptedException e) {}

}
}

Rotator implements the runnable interface, calling
ThreadPanel.rotate() to move the display.

run()finishes if an exception is raised by Thread.interrupt().

Concurrency: concurrent execution 28
©Magee/Kramer 2nd Edition

ThreadPanel class

public class ThreadPanel extends Panel {

// construct display with title and segment color c
public ThreadPanel(String title, Color c) {…}

// rotate display of currently running thread 6 degrees
// return value not used in this example
public static boolean rotate()

throws InterruptedException {…}

// create a new thread with target r and start it running
public void start(Runnable r) {

thread = new DisplayThread(canvas,r,…);
thread.start();

}

// stop the thread using Thread.interrupt()
public void stop() {thread.interrupt();}

}

ThreadPanel
manages the display
and control buttons for
a thread.

Calls to rotate()
are delegated to
DisplayThread.

Threads are created by
the start() method,
and terminated by the
stop() method.

Concurrency: concurrent execution 29
©Magee/Kramer 2nd Edition

ThreadDemo class

public class ThreadDemo extends Applet {
ThreadPanel A; ThreadPanel B;

public void init() {
A = new ThreadPanel(“Thread A”,Color.blue);
B = new ThreadPanel(“Thread B”,Color.blue);
add(A); add(B);

}

public void start() {
A.start(new Rotator());
B.start(new Rotator());

}

public void stop() {
A.stop();
B.stop();

}
}

ThreadDemo creates two
ThreadPanel displays
when initialized and two
threads when started.

ThreadPanel is used
extensively in later
demonstration programs.

Concurrency: concurrent execution 30
©Magee/Kramer 2nd Edition

Summary

Concepts
concurrent processes and process interaction

Models
Asynchronous (arbitrary speed) & interleaving (arbitrary order).

Parallel composition as a finite state process with action
interleaving.

Process interaction by shared actions.

Process labeling and action relabeling and hiding.

Structure diagrams

Practice
Multiple threads in Java.