Transcript memory

Concurrent Languages – Part 1
COMP 640
Programming Languages
1
Topics


Brief review of Concurrent Computing
Two language approaches to dealing
with concurrent programming


Java
Occam – next week
COMP 640 – CWB
2
Concurrent Computing





Concurrent program: 2 or more execution
contexts
Parallel program: concurrent with
simultaneous execution
Distributed program: on separate processors
Multiprocessing: in separate processes
(separate memory)
Multi-threaded: same process (common
memory)
COMP 640 – CWB
3
States of a Thread
Figure 11.1
Source: T&N, Figure 11.1
Deadlock
COMP 640 – CWB
5
Dijkstra's Semaphores



P(s): if(s>0) s--; else block();
V(s): if(isBlocked) wakeup(); else s++;
Uses:

Cooperative synchronization


E.g., producer/consumer
Critical section locking
COMP 640 – CWB
6
Monitors


Protect critical sections
Condition variable represents a lock



List of waiting threads
wait action: thread blocks until signaled
signal action: running thread holding lock releases
a blocked thread to run


Hoare monitor: signaling thread loses the lock and
released thread run immediately (no other thread can
intervene)
Mesa monitor: signaling thread keeps the lock; signaled
thread runs sometime after lock is released (another
thread could potentially run instead)
COMP 640 – CWB
7
Concurrency in Java


Threads
Monitors
COMP 640 – CWB
8
"Syntax" of Java Threads
new Thread(){
public void run() {
doSomeWork();
//thread is now terminating
}
}.start();
No language features
COMP 640 – CWB
9
Semantics of Java
Threads


May be implemented on multiple processors
and/or by time-slicing
Threads are created by a side effect of the
creation of a Thread object



Become runnable when the start() method is called
Running commences in the run() method
Thread terminates when run() completes
COMP 640 – CWB
10
Semantics of Java
Threads and Variables
a = b;

main memory
use
load
Working
Memory
assign
store
Main
Memory
read
write
All threads share
Thread
Execution
Engine

A thread on a
separate processor
may have its own
working memory
COMP 640 – CWB
11
Semantics of Java Threads –
Ordering Rules for Working
Memory Actions

use

load
Working
Memory
assign
store
Main
Memory
Thread

Execution
Engine

read

write

use and assign occur in order
implied by program
A store must intervene between
= b;
assign and load on aavariable
An assign must intervene between
a load/store and a subsequent
store on a variable
Start of thread: an assign/load
must precede a use/store
Creation of variable: an
assign/load must precede a
use/store
Otherwise, load or store may
occur at any time
COMP 640 – CWB
12
Semantics of Java Threads –
Ordering Rules for Main
Memory Actions

use

load
Working
Memory
assign
store
Main
Memory
read
write
Thread

Execution
Engine

Every load must be
preceded by a read
Every store must be
a = b;
followed by a write
The reads for 2 loads
occur in the same order as
the loads
The writes for 2 stores
occur in the same order as
the stores
COMP 640 – CWB
13
Example from Java Spec.
class Sample {
int a = 1, b = 2;
void hither() { a = b; }
void yon() { b = a; }
}
precedes
Three orderings:
1. write a  read a, read b  write b
ah =2, hb=2, ma=2, mb=2, ya=2, yb=2
2. read a  write a, write b  read
ha=1, hb=1, ma=1, mb=1, ya=1, yb=1
3. read a  write a, read b  write b
ha=2, hb=2, ma=2, mb=1, ya=1, yb=1
COMP 640 – CWB
14
Amusing Statement
From the Java language spec:
"In the absence of explicit
synchronization, an implementation is
free to update the main memory in an
order that may be surprising. Therefore
the programmer who prefers to avoid
surprises should use explicit
synchronization. "
COMP 640 – CWB
15
Java Monitors: Syntax of
Synchronized Blocks
SynchronizedStatement:
synchronized ( Expression ) Block
The type of Expression must be a reference type,
or a compile-time error occurs.
Source: Java Language Spec,
Sect. 14.18
COMP 640 – CWB
16
Java Monitors: Syntax of
Synchronized Methods
MethodModifier: one of public protected
private abstract static final synchronized
native strictfp
Source: Java Language Spec,
Sect. 8.4.3
COMP 640 – CWB
17
Java Monitors: Semantics
of Synchronized Methods
"A synchronized method acquires a lock (§17.1)
before it executes. For a class (static) method,
the lock associated with the Class object for the
method's class is used. For an instance method,
the lock associated with this (the object for which
the method was invoked) is used."
Source: Java Language Spec,
Sect. 8.4.3.6
COMP 640 – CWB
18
Java Synchronized Blocks
- Semantics
1.
2.
3.
4.
5.
Evaluate expression  V
If V is null, throw nullPointerException
Lock the lock associated with V: may block
while another thread holds the lock
Execute block
When block completes (normally or
abnormally), unlock lock assoc. with V
Paraphrased from: Java Language Spec,
Sect. 14.18
COMP 640 – CWB
19
Semantics of Java Threads –
Ordering Rules for Locks
use
Working
Memory
load
assign
store
read
write
Main
Memory

lock
unlock
Thread

Execution
Engine


A lock may occur only if the
numbers of locks and unlocks by
another thread are equal.
An unlock may occur only if the
number of unlocks by the same
thread is less than the number
of locks
A store (and its corresponding
write) must intervene between
an assign and an unlock.
An assign/load must intervene
between a lock and a use/store.
(I.e., a lock invalidates the
working memory.)
COMP 640 – CWB
20
Example from Java Spec.
with Locks
class SyncSample {
int a = 1, b = 2;
synchronized void hither()
{ a = b; }
synchronized void yon()
{ b = a; }
}
Three orderings? Two orderings:
1. write a  read a, read b  write b
ah =2, hb=2, ma=2, mb=2, ya=2, yb=2
2. read a  write a, write b  read
ha=1, hb=1, ma=1, mb=1, ya=1, yb=1
3. read a  write a, read b  write b
ha=2, hb=2, ma=2, mb=1, ya=1, yb=1
COMP 640 – CWB
21
Semantics of Java Threads –
Ordering Rules for Volatile
Variables

use
Working
Memory
load

assign
store
read
Thread
Execution
A use must be immediately
preceded by a load.
An assign must be
immediately followed by a
store.
Engine
write
Main
Memory
lock
In effect, the working memory
cache does not exist.
unlock
COMP 640 – CWB
22
Java's wait() & notify()
Thread must hold lock on v before calling v.wait() or
v.notify()
 v.wait()




v.notify()


Mesa-style
monitor
add thread to the wait set of v
release lock (i.e., if thread has done N more locks than
unlocks, do N unlocks)
put thread in blocked state



remove a thread, T, from wait set of v
make T runnable
T then locks the lock associated with v (which might block)
T then performs N-1 additional locks
T then returns from the wait() method call
COMP 640 – CWB
23
Reference
The official description in the Java spec:
http://java.sun.com/docs/books/jls/second_edition/html/memory.doc.html#30206
COMP 640 – CWB
24
Next Week

Finish up concurrent languages

The Occam language

Read Sections 1, 2, 6, and 7 of
http://www.wotug.org/occam/documentation/oc3refman.pdf

Event-driven languages

Read Chapter 9 of T&N
COMP 640 – CWB
25