Concurrent Object-Oriented Programming Concurrent Programming in Java

Java Concurrency (VRH 8.6)

Objects, Active Objects (VRH 7.2,7.8) • Java is multi-threaded.
• Two ways to create new threads:
– Extend [Link]
Carlos Varela • Overwrite “run()” method.
RPI – Implement Runnable interface
• Include a “run()” method in your class.
• Starting a thread
Adapted with permission from: – new MyThread().start();
Seif Haridi – new Thread(runnable).start();
KTH
Peter Van Roy
UCL

October 30, 2006

C. Varela; Adapted from S. Haridi and P. Van Roy 1 C. Varela; Adapted from S. Haridi and P. Van Roy 2

The synchronized Statement synchronized as a modifier

• To ensure only one thread can run a block of code, use
synchronized: • You can also declare a method as synchronized:

synchronized int blah(String x) {

synchronized ( object ) { // blah blah blah
// critical code here }

}
equivalent to:

• Every object contains an internal lock for synchronization. int blah(String x) {

synchronized (this) {
// blah blah blah
}
}

C. Varela; Adapted from S. Haridi and P. Van Roy 3 C. Varela; Adapted from S. Haridi and P. Van Roy 4

Object-Oriented Programming in Attributes of Classes

Oz
The class Counter has the syntactic form The class Counter has the syntactic form
class Counter class Counter val is an attribute:
attr val attr val a modifiable cell
meth display meth display that is accessed by the
{Browse @val} {Browse @val}
end end atom val
meth inc(Value) meth inc(Value)
val := @val + Value val := @val + Value
end end
meth init(Value) meth init(Value)
val := Value val := Value
end end
end end
C. Varela; Adapted from S. Haridi and P. Van Roy 5 C. Varela; Adapted from S. Haridi and P. Van Roy 6

1
 Attributes of classes Attributes of classes
The class Counter has the syntactic form The class Counter has the syntactic form
class Counter class Counter
attr val attr val
meth display meth display
{Browse @val} the attribute val {Browse @val} the attribute val
end is accessed by the end is assigned by the
meth inc(Value) meth inc(Value)
operator @val operator :=
val := @val + Value val := @val + Value
end end as val := ...
meth init(Value) meth init(Value)
val := Value val := Value
end end
end end
C. Varela; Adapted from S. Haridi and P. Van Roy 7 C. Varela; Adapted from S. Haridi and P. Van Roy 8

Methods of classes Concurrency and state

are tough when used together
The class Counter has the syntactic form • Execution consists of multiple threads, all executing
class Counter methods independently and all using shared memory
attr val are statements • Because of interleaving semantics, execution happens as if
meth display method head is a there was one global order of operations
{Browse @val} record (tuple) pattern • Assume two threads and each thread does k operations.
end
Then the total number of possible interleavings is 2k
meth inc(Value)
val := @val + Value This is exponential in k. k ( )
end • One can program by reasoning on all possible
meth init(Value) interleavings, but this is extremely hard. What do we do?
val := Value
end
end
C. Varela; Adapted from S. Haridi and P. Van Roy 9 C. Varela; Adapted from S. Haridi and P. Van Roy 10

Concurrent stateful model Why not use a simpler model?

〈s〉 ::= skip empty statement
• The concurrent declarative model is much simpler
| 〈x〉 = 〈y〉 variable-variable binding
| 〈x〉 = 〈v〉 variable-value binding – Programs give the same results as if they were sequential, but they give the results
incrementally
| 〈s1〉 〈s2 〉 sequential composition
| local 〈x〉 in 〈s1 〉 end declaration • Why is this model so easy?
| proc { 〈x〉 〈y1 〉 … 〈yn 〉 } 〈s1〉 end procedure creation – Because dataflow variables can be bound to only one value. A thread that shares a
| if 〈x〉 then 〈s1 〉 else 〈s2〉 end conditional variable with another thread does not have to worry that the other thread will change
| { 〈x〉 〈y1〉 … 〈yn〉 } procedure application the binding.
| case 〈x〉 of 〈pattern〉 then 〈s1〉 else 〈s2〉 end pattern matching • So why not stick with this model?
| {NewName 〈x〉 } name creation – In many cases, we can stick with this model
| thread 〈s〉 end thread creation – But not always. For example, two clients that communicate with one server cannot
| {ByNeed 〈x〉 〈y〉 } trigger creation be programmed in this model. Why not? Because there is an observable
| try 〈s1〉 catch 〈x〉 then 〈s2〉 end exception context nondeterminism.
| raise 〈x〉 end raise exception • The concurrent declarative model is deterministic. If the program we write has
| {NewCell 〈x〉 〈y〉 } cell creation an observable nondeterminism, then we cannot use the model.
| {Exchange 〈x〉 〈y〉 〈z〉 } cell exchange

C. Varela; Adapted from S. Haridi and P. Van Roy 11 C. Varela; Adapted from S. Haridi and P. Van Roy 12

2
 Programming with
When to use each approach
concurrency and state
• Programming with concurrency and state is largely a
matter of reducing the number of interleavings, so that we • Message passing: useful for multi-agent applications, i.e.,
can reason about programs in a simpler way. There are programs that consist of autonomous entities (« agents »,
two basic approaches: message passing and atomic actions. « actors » or « active objects ») that communicate with
• Message passing with active objects: Programs consist of each other.
threads that send asynchronous messages to each other.
• Atomic actions: useful for data-centered applications, i.e.,
Each thread only receives a message when it is ready,
which reduces the number of interleavings. programs that consist of a large repository of data
(« database » or « shared state ») that is accessed and
• Atomic actions on shared state: Programs consist of
passive objects that are called by threads. We build large updated concurrently.
atomic actions (e.g., with locks, monitors, or transactions) • Both approaches can be used together in the same
to reduce the number of interleavings. application, for different parts

C. Varela; Adapted from S. Haridi and P. Van Roy 13 C. Varela; Adapted from S. Haridi and P. Van Roy 14

Overview of
Ports and cells
concurrent programming
• We have seen cells, the basic unit of encapsulated state, as a primitive concept
• There are four basic approaches: underlying stateful and object-oriented programming. Cells are like variables
in imperative languages.
– Sequential programming (no concurrency)
• Cells are the natural concept for programming with shared state
– Declarative concurrency (streams in a functional language)
• There is another way to add state to a language, which we call a port. A port is
– Message passing with active objects (Erlang, SALSA) an asynchronous FIFO communications channel.
– Atomic actions on shared state (Java) • Ports are a natural concept for programming with active objects
• The atomic action approach is the most difficult, yet it is • Cells and ports are duals of each other
– Each can be implemented with the other, so they are equal in expressiveness
the one you will probably be most exposed to!
– Each is more natural in some circumstances
• But, if you have the choice, which approach to use? – They are equivalent because each allows many-to-one communication (cell shared
– Use the simplest approach that does the job: sequential if that is by threads, port shared by threads)

ok, else declarative concurrency if there is no observable

nondeterminism, else message passing if you can get away with it.

C. Varela; Adapted from S. Haridi and P. Van Roy 15 C. Varela; Adapted from S. Haridi and P. Van Roy 16

Ports Building locks with cells

• A port is an ADT with two operations: • The basic way to program with shared state is by using locks
• A lock is a region of the program that can only be occupied by one thread at a
– {NewPort S P}: create a new port P with a new stream S. The
time. If a second thread attempts to enter, it will suspend until the first thread
stream is a list with unbound tail, used to model the FIFO nature of exits.
the communications channel.
• More sophisticated versions of locks are monitors and transactions:
– {Send P X}: send message X on port P. The message is appended – Monitors: locks with a gating mechanism (e.g., wait/notify in Java) to control which
to the stream S and can be read by threads reading S. threads enter and exit and when. Monitors are the standard primitive for concurrent
programming in Java.
• Example: – Transactions: locks that have two exits, a normal and abnormal exit. Upon
declare P S in abnormal exit (called « abort »), all operations performed in the lock are undone, as
{NewPort S P} if they were never done. Normal exit is called « commit » .
{Browse S} • Locks can be built with cells. The idea is simple: the cell contains a token. A
thread{Send P 1}end thread attempting to enter the lock takes the token. A thread that finds no
token will wait until the token is put back.
thread{Send P 2}end

C. Varela; Adapted from S. Haridi and P. Van Roy 17 C. Varela; Adapted from S. Haridi and P. Van Roy 18

3
 Building active objects with ports Defining ports with cells
• Here is a simple active object: • A port is an unbundled stateful ADT:

proc {NewPort S P}
declare P in C={NewCell S} Anyone can do a send because
in anyone can do an exchange
local Xs in
P={Wrap C}
{NewPort Xs P} end
thread {ForAll Xs proc {$ X} {Browse X} end} end
end proc {Send P X}
C={Unwrap P}
Old
{Send P foo(1)} in
thread {Send P bar(2)} end {Exchange C X|Old Old}
end

C. Varela; Adapted from S. Haridi and P. Van Roy 19 C. Varela; Adapted from S. Haridi and P. Van Roy 20

Creating active objects

Active objects with classes
with NewActive
• An active object’s behavior can be defined by a class
• The class is used to create a (passive) object, which is invoked by one thread that reads • We can create a function NewActive that behaves like New except that it
from a port’s stream creates an active object:
• Anyone can send a message to the object asynchronously, and the object will execute fun {NewActive Class Init}
them one after the other, in sequential fashion: Obj Xs P
in
declare ActObj in Obj={New Class Init}
local Obj Xs P in {NewPort Xs P}
Obj={New Class init} thread {ForAll Xs proc {$ M} {Obj M} end} end
{NewPort Xs P} proc {$ M} {Send P M} end
thread {ForAll Xs proc {$ M} {Obj M} end} end end
proc {ActObj M} {Send P M} end
ActObj = {NewActive Class init}
end
{ActObj msg(1)}

• Note that {Obj M} is synchronous and {ActObj M} is asynchronous!

C. Varela; Adapted from S. Haridi and P. Van Roy 21 C. Varela; Adapted from S. Haridi and P. Van Roy 22

Making active objects

Playing catch
synchronous
ball
• We can make an active object synchronous by using a dataflow variable to class Bounce B1 B2
store a result, and waiting for the result before continuing attr other count:0
meth init(Other) ball
fun {NewSynchronousActive Class Init}
other:=Other
Obj Xs P
in end declare B1 B2 in
Obj={New Class Init} meth ball
B1={NewActive Bounce init(B2)}
{NewPort Xs P} count:=@count+1
{@other ball} B2={NewActive Bounce init(B1)}
thread {ForAll Xs proc {$ msg(M X)} {Obj M} X=unit end} end
proc {$ M} X in {Send P msg(M X)} {Wait X} end end
end meth get(X) % Get the ball bouncing
X=@count {B1 ball}
• This can be modified to handle when the active object raises an exception, to end
pass the exception back to the caller end % Follow the bounces
{Browse {B1 get($)}}

C. Varela; Adapted from S. Haridi and P. Van Roy 23 C. Varela; Adapted from S. Haridi and P. Van Roy 24

4
 An area server Event manager with active objects
• An event manager contains a set of event handlers
• Each handler is a triple Id#F#S where Id identifies it, F is the state update
class AreaServer declare S in function, and S is the state
meth init skip end S={NewActive AreaServer init}
• Reception of an event causes all triples to be replaced by Id#F#{F E S}
meth square(X A) (transition from F to {F E S})
A=X*X % Query the server
• The manager EM is an active object with four methods:
end declare A in – {EM init} initializes the event manager
meth circle(R A) {S square(10 A)} – {EM event(E)} posts event E at the manager
A=3.14*R*R {Browse A} – {EM add(F S Id)} adds new handler with F, S, and returns Id
end – {EM delete(Id S)} removed handler Id, returns state
end declare A in • This example taken from real use in Erlang
{S circle(20 A)}
{Browse A}

C. Varela; Adapted from S. Haridi and P. Van Roy 25 C. Varela; Adapted from S. Haridi and P. Van Roy 26

Defining the event manager Using the event manager

• Mix of functional and object-oriented style • Simple memory-based handler keeps list of events

class EventManager declare EM MemH Id in

attr handlers State transition done using EM={NewActive EventManager init}
meth init handlers:=nil end
functional programming
meth event(E)
handlers:= MemH=fun {$ E Buf} E|Buf end
{Map @handlers fun {$ Id#F#S} Id#F#{F E S} end} {EM add(MemH nil Id)}
end
meth add(F S Id) {EM event(a1)}
Id={NewName} {EM event(a2)}
handlers:=Id#F#S|@handlers ...
end
meth delete(DId DS)
• An event handler is purely functional, yet when put in the event manager, the
handlers:={[Link]
latter is a concurrent imperative program. This is an example of separation of
@handlers fun {$ Id#F#S} DId==Id end [_#_#DS]}
concerns by using multiple paradigms.
end
end
C. Varela; Adapted from S. Haridi and P. Van Roy 27 C. Varela; Adapted from S. Haridi and P. Van Roy 28

Exercises

60. Do Java and C++ provide linguistic abstractions for active

objects? If so, which? If not, how would you implement
this abstraction?
61. Exercise VRH 7.9.1 (pg 567)
62. *Exercise VRH 7.9.6(a) (pg 568)

C. Varela; Adapted from S. Haridi and P. Van Roy 29