If that makes any sense to you,
you have a big problem
Concurrent
Object
Oriented
Programming
Susmit Bagchi, NTNU
Free Your Mind
To understand concurrent programming it is useful to first examine
sequential programming and the (often hidden)assumptions behind it.
Languages such as Fortran,C/C ++,and Pascal are influenced by the
underlying system architecture,which is typically a uniprocessor machine
with a von Neumann architecture:
A single CPU connected to RAM and i/o devices via a bus;
Instructions and data are shared in RAM;
Processor activity consists of fetch-execute cycles;
One instruction is executed per cycle (ignoring such issues as pipelining and
superscalar architectures).
Susmit Bagchi, NTNU
Contd..
This means that code is,essentially,written in the order we
expect the machine to execute it. This defines a total
ordering on the set of instructions:
{p 1 ,p 2 ,...,p L ,q 1 ,q 2 ,...,q M ,r 1 ,r 2 ,...,r N}
If we choose any two instructions from this set,then we can
always rank them according to their execution order.
*Two characteristics of sequential programming*
1.The textual order of statements specifies their order of execution
2.Successive statements must be executed without any temporal overlap
Neither of these applies to concurrent programming.
Susmit Bagchi, NTNU
CONCURRENT PROGRAMMING
Definition:
Operations in the source text are concurrent if they could be, but need not
be, executed in parallel. Operations that occur one after the other, ordered
in time, are said to be sequential.
The fundamental concept of concurrent programming is
-the notion of a process, which corresponds to a sequential
computation, with its own thread of control.
-the thread of a sequential computation is the sequence of
program points that are reached as control flows through the
source text of the program.
Susmit Bagchi, NTNU
Concurrent programming languages
•Specific language designs
**Actors (Hewitt, Guha)
**ABCL (Tokoro, Yonezawa)
**POOL (America, et al.)
**Obliq (Cardelli)
•Semantic frameworks, e.g., actor semantics
•Extensions to C++, e.g., COOL
•Process calculus approaches (Pierce, etc.)
Susmit Bagchi, NTNU
INTERACTIONS BETWEEN PROCESSES
Communication: involves the exchange of data between processes, either by an
explicit message passing or through the values of shared
variables.
Communication types: SYNC. and ASYNC.
Communication model: Communication I/O through channels
Synchronization:: relates the thread of one process with that of another.
Interactions between processes can also be visualized in terms of
competition and cooperation between processes.
Synchronization constructs: Semaphore, Monitors.
Susmit Bagchi, NTNU
Concurrent programming model
In order to model concurrency we allow process composition, P1 |
P2.
Intuitively, this means that processes P1 and P2 execute concurrently. Such
concurrent processes can interact in a synchronous fashion when one process
wants to perform an input action and another process wants to per-form a
matching output action.
Formally:
P ||Q  e: (P Q ) and  (Q P ).
Thus we have a partial ordering : given any two instructions from P or
Q ,we may or may not be able to rank them according to their execution order.
HOW MANY PARTIAL ORDER SEQUENCES POSSIBLE?
ALL SEQUENCES ARE EXECUTABLE?
Susmit Bagchi, NTNU
Programming model contd..
Discussion on Concurrent programming constructs:
# Ordering : <{p},{q}, {r}> ; Poset C = {<p>, <q>, <r>}
# Combinatorial form (C)
# Alphabet X ={x, x, x’, x’’, ……..x’n}
# Terminal function, t:PT; T={S,F}
# Process state transition predicate [x x’ …. (x’n OR t(x))]
# Cyclic process
Susmit Bagchi, NTNU
Characteristics of concurrent programming
Two characteristics of concurrent programming:
If two operations are concurrent with one another then
1.The textual order of statements does not specify their order of
execution
2.The operations are permitted (but not obliged)to overlap in time
Susmit Bagchi, NTNU
Formal definition (alternate form)
As a very simple example, consider two processes A and B
plugged together in the following way. A performs input action a
and then wants to perform output action b, returning to state A.
Process B performs an input action b followed by an output
action c, returning to state B upon completion. Hence, they are
defined as,
A = a.bˆ.A<a,b>
B= b.cˆ.B<b,c>
We assume we start with A and B operating concurrently, that
is, in state A | B. Now we can have the following sequence of
transitions:
a(a.bˆ.A| b.cˆ.B)A|
cˆ.B A|B
Susmit Bagchi, NTNU
Concurrent process expression
A] Prefixes:
P,Q, R ::= 0
(inert process)
x(y).P
(input prefix)
xˆ.y.P
(output prefix)
P|Q
(parallel composition)
(νx)P
(restriction)
!P
(replication)
B] The (Abelian) monoid properties:
1) P|Q  Q|P ---Commutativity of parallel composition
2) (P|Q)|R  P|(Q|R) --- Associativity of parallel composition
3) P|0  P
Susmit Bagchi, NTNU
Concurrent process expression contd….
C] The scope extension property:
((νx)P)|Q  (νx)(P|Q) if x FV(P) ((νx) is non-distributive)
D] Replication/ Creation:
!P  (P|n)|!P
Susmit Bagchi, NTNU
Concurrent Object Oriented Programming
Languages
Preliminaries:
Objects are completely “encapsulated”.
Objects communicate via “message passing” (OR shared memory).
An object may enquire the “internal local state” of another object by
sending a “message” requesting to execute some “method”.
Advantage of “message passing” over “shared memory”:
“message passing” separates the two objects/processes completely, but
not the “shared memory” construct.
”shared memory” system needs to take care of shared variables by
synchronized data structure access---a bit complicated.
Susmit Bagchi, NTNU
Why do we need concurrent OO language?
Because,
 Real world is concurrent (and distributed).
 Performance gain in (due to concurrency)
 resource utilization
 execution time
 Fault tolerance by replicating
data
 method
Susmit Bagchi, NTNU
OBJECT ORIENTED CONCURRENCY ISSUES
 Interaction primitives
Synchronous and asynchronous model
 Object granularity
bias that language offers toward size of object
ACTOR offers fine-grain/ SmallTalk offers coarse grain
 Encapsulation
case SmallTalk: class variablemultiple instances 
concurrent update (mutex??)
Opportunity for “interference” in concurrent system
Class consistency (arises from object migration and potential for
independent redefinition/modification of class definitions)
Susmit Bagchi, NTNU
ACTOR model
Actors originated through Carl Hewitt work on the artificial intelligence system
Planner in the early 1970’s.
Actor approach was formulated around three main design objectives:
1.
Shared, mutable data. The actor model is designed to deal with shared resources
that may change state. An example is a bank account whose balance may change.
2.
Reconfigurability. New objects may be created and it is possible to communicate
with new objects after they are created.
3.
Inherent concurrency. It should be possible to understand the "inherent
concurrency" of a program by examining it.
** The phrase "inherent concurrency" refers to the number of activities that could be
carried out in parallel if there were an unbounded number of processes available.
Susmit Bagchi, NTNU
BASIC IDEAS IN THE ACTOR MODEL
DEFINITION: An actor is an object that carries out its actions in response to
communications it receives. Actors support large-scale concurrent symbolic
computation.
*There are three basic actions that an actor may perform*
•Send communication to itself or other actors
•Create new actors
•Specify a replacement behavior, which is essentially another actor that takes the
place of the actor that creates it, for the purpose of responding to certain
communications.
Susmit Bagchi, NTNU
*Important points to remember*
• Each actor receives a linearly ordered sequence of communications.
• There is no assignment to local variables in the basic actor model.
• One execution of an actor script is an atomic computation.
• An important part of the model is the mail system, which routes and buffers
communication between actors. Every communication must be sent to a mail
address and an actor may communicate with any actor if it knows its mail
address.
Susmit Bagchi, NTNU
General properties of ACTOR
•The Actor model is asynchronous, with no global clock.
•Communication is
explicit, through mail addresses, without shared variables,
 buffered and asynchronous.
 Weak fairness is assumed, in the following forms:
Every message that is sent is eventually delivered. (However the notion of
"deliver" is subtle, because an actor may or may not be prepared to process a message
at a given time. More discussion below.)
Every computation eventually progresses, i.e., each process is eventually scheduled
and allowed to perform part of its computation.
Susmit Bagchi, NTNU
ACTOR characterization
All actors are characterized by:
¶ identity (never changes once an actor created)
¶ current behaviour (indicates actor’s action on next message)
Immutable actor: Actor having same “action behaviour” throughout its life time.
Actor Classes:
 Primitive actor
-corresponds to atomic types such as characters
-primitive actor are sent directly in messages
 Non-primitive actor
-mail-address represents actor identity
-current behaviour is composed of a set of instance
variables or local state of the actor
Susmit Bagchi, NTNU
ACTOR anatomy
Some internal organs of an actor
(defBehaviour simple-check-acc [balance]
(script
[[:deposit amount customer]
(become check-acc[(send balance[+amount] ) ] )
(send customer [:deposited amount] ) ]
[[:withdraw amount customer]
(become check-acc[(send balance [-amount] ) ] )
(send customer [:withdraw amount] ) ]
[[:balance customer]
(send customer [: balance balance] ) ] ) )
**Anatomical decease: Actor model does not have any form of code sharing as part of model.
Susmit Bagchi, NTNU
ACTOR is too old; ABCL/1 is charming!
ABCL/1 childhood: ABCL/1 has evolved from Actor but,
more pragmatic; adopts more eclectic view toward object coexistence
Object in ABCL/1: The object and its behaviour is specified entirely
by its script, which is a collection of message patterns and associated
methods.
Message passing in ABCL/1: Asynchronous and point to point.
Message types in ABCL/1:
-past (send message and resume activity)
-now (send message and wait for response)
-future (send message, mention future action and resume
activity; something like “future-RPC”)
Susmit Bagchi, NTNU
ABCL/1 is attractive!!
Message priorities:
-no such message priority in ACTOR model----(a distinction!)
-two types of priorities in ABCL/1(express_message OR ordinary_message)
Action set:
-reception of express_message will preempt ordinary_message processing
-when express_message processing is over, resumes from preemption point
Message queues and Object states:
-two message queues per object (express_message_Q OR ordinary_message_Q)
-three object states:
*dormant (currently idle, will do something on message arrival)
*active (currently processing a message, executing a method)
*waiting (while processing a message is sent, waiting for reply)
Susmit Bagchi, NTNU
MATTERS TO THINK
Some major research issues:
$$ HOW CAN YOU EXTEND THE CONCEPT OF “INHERITANCE” TO
CURRENT SETTING?
$$ HOW ACTOR WILL ACHIEVE CODE SHARING?
$$ SmallTalk-80 TRIED TO ACHIEVE “INHERITANCE”, BUT HOW TO COPE
WITH RESULTING “INCOMPLETE ENCAPSULATION”?
Susmit Bagchi, NTNU
Descargar

Π Calculus