程序代写代做代考 compiler data structure c# Java assembler algorithm C Erlang concurrency c++ cache graph clock ada distributed system Systems, Networks & Concurrency 2019

Systems, Networks & Concurrency 2019
Communication & Sync3hronization Uwe R. Zimmer – The Australian National University

[Ben-Ari06]
[AdaRM2012]
M. Ben-Ari
Ada Reference Manual – Lan- guage and Standard Libraries; ISO/IEC 8652:201x (E)
Principles of Concurrent and Dis- tributed Programming
2006, second edition, Prentice- Hall, ISBN 0-13-711821-X
[Chapel 1.11.0 Language Specification Version 0.97]
[Barnes2006]
see course pages or http://chapel.cray.com/ spec/spec-0.97.pdf released on 2. April 2015
Barnes, John
Programming in Ada 2005
[Saraswat2010]
Communication & Synchronization
Addison-Wesley, Pearson education, ISBN- 13 978-0-321-34078-8, Harlow, England, 2006
Saraswat, Vijay
[Gosling2005]
Report on the Programming Language X10 Version 2.01
Draft — January 13, 2010
Gosling, James, Joy, B, Steele,
Guy & Bracha, Gilad
The JavaTM Language Specification – third edition
2005
© 2019 Uwe R. Zimmer, The Australian National University
page 254 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
References for this chapter

• Semaphores
• Conditional critical regions
• Monitors
• Mutexes & conditional variables
• Synchronized methods
• Protected objects
• Atomic blocks
C, POSIX — Dijkstra
Edison (experimental)
Modula-1, Mesa — Dijkstra, Hoare, … POSIX
Java, C#, …
Ada
Chapel, X10
Message based synchronization
Communication & Synchronization
• Asynchronous messages
• Synchronous messages
• Remote invocation, remote procedure call
e.g. POSIX, …
e.g. Ada, CHILL, Occam2, … e.g. Ada, …
© 2019 Uwe R. Zimmer, The Australian National University
page 255 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Overview
Synchronization methods
Shared memory based synchronization

Communication & Synchronization
Operations have side effects which are visible …
Motivation
Side effects
either
… locally only
(and protected by runtime-, os-, or hardware-mechanisms)
or
… outside the current process
If side effects transcend the local process then all forms of access need to be synchronized.
© 2019 Uwe R. Zimmer, The Australian National University page 256 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
int i; {declare globally to multiple threads}
i++; if i > n {i=0;}
Sanity check
Do we need to? – really?
{in one thread} {in another thread}
What’s the worst that can happen?
© 2019 Uwe R. Zimmer, The Australian National University page 257 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Sanity check
Do we need to? – really?
int i; {declare globally to multiple threads}
i++; if i > n {i=0;}
{in one thread} {in another thread}
Handling a 64-bit integer on a 8- or 16-bit controller will not be atomic
… yet perhaps it is an 8-bit integer.
Unaligned manipulations on the main memory will usually not be atomic
… yet perhaps it is a aligned.
Broken down to a load-operate-store cycle, the operations will usually not be atomic
… yet perhaps the processor supplies atomic operations for the actual case.
Many schedulers interrupt threads irrespective of shared data operations
… yet perhaps this scheduler is aware of the shared data.
Local caches might not be coherent
© 2019 Uwe R. Zimmer, The Australian National University page 258 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
… yet perhaps they are.

Even if all assumptions hold: How to expand this code?
Communication & Synchronization
Sanity check
Do we need to? – really?
int i; {declare globally to multiple threads}
i++; if i > n {i=0;}
{in one thread} {in another thread}
Handling a 64-bit integer on a 8- or 16-bit controller will not be atomic
… yet perhaps it is an 8-bit integer.
Unaligned manipulations on the main memory will usually not be atomic
… yet perhaps it is a aligned.
Broken down to a load-operate-store cycle, the operations will usually not be atomic
… yet perhaps the processor supplies atomic operations for the actual case.
Many schedulers interrupt threads irrespective of shared data operations
… yet perhaps this scheduler is aware of the shared data.
Local caches might not be coherent
© 2019 Uwe R. Zimmer, The Australian National University page 259 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
… yet perhaps they are.

Communication & Synchronization
Sanity check
Do we need to? – really?
int i; {declare globally to multiple threads}
i++; if i > n {i=0;}
{in one thread} {in another thread}
The chances that such programming errors turn out are usually small and some im- plicit by chance synchronization in the rest of the system might prevent them at all.
(Many effects stemming from asynchronous memory accesses are interpreted as (hardware) ‘glitches’, since they are usually rare, yet often disastrous.)
On assembler level on very simple CPU architectures: synchronization by employing knowledge about the atomicity of CPU-operations and inter- rupt structures is nevertheless possible and utilized in practice.
In anything higher than assembler level on single core, predictable μ-controllers:
Measures for synchronization are required!
© 2019 Uwe R. Zimmer, The Australian National University page 260 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Assumption: word-access atomicity:
i.e. assigning two values (not wider than the size of a ‘word’) to an aligned memory cell concurrently:
Towards synchronization
Condition synchronization by flags
x := 0 | x := 500
will result in either x = 0 or x = 500 – and no other value is ever observable
© 2019 Uwe R. Zimmer, The Australian National University page 261 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Towards synchronization
Condition synchronization by flags
Assuming further that there is a shared memory area between two processes:
• A set of processes agree on a (word-size) atomic variable operating as a flag to indicate synchronization conditions:
© 2019 Uwe R. Zimmer, The Australian National University page 262 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

process P1;
statement X;
var Flag : boolean := false; process P2;
repeat until Flag; statement Y;
Flag := true;
end P1;
statement B; end P2;
Communication & Synchronization
Towards synchronization
Condition synchronization by flags
Sequence of operations: A < B; 6X ; A@ < Y; 6X,Y ; B@ © 2019 Uwe R. Zimmer, The Australian National University page 263 of 757 (chapter 3: “Communication & Synchronization” up to page 368) statement A; Communication & Synchronization Towards synchronization Condition synchronization by flags Assuming further that there is a shared memory area between two processes: • A set of processes agree on a (word-size) atomic variable operating as a flag to indicate synchronization conditions: Memory flag method is ok for simple condition synchronization, but ... ... is not suitable for general mutual exclusion in critical sections! ... busy-waiting is required to poll the synchronization condition! More powerful synchronization operations are required for critical sections © 2019 Uwe R. Zimmer, The Australian National University page 264 of 757 (chapter 3: “Communication & Synchronization” up to page 368) Communication & Synchronization • a set of processes agree on a variable S operating as a flag to indicate synchronization conditions Basic synchronization by Semaphores Basic definition (Dijkstra 1968) Assuming the following three conditions on a shared memory cell between processes: • an atomic operation P on S — for ‘passeren’ (Dutch for ‘pass’): P(S): [as soon as S > 0 then S := S – 1] this is a potentially delaying operation
aka: ‘Wait’, ‘Suspend_Until_True’, ‘sem_wait’, …
• an atomic operation V on S — for ‘vrygeven’ (Dutch for ‘to release’):
V(S):[S := S + 1]
aka ‘Signal’, ‘Set-True’, ‘sem_post’, …
then the variable S is called a Semaphore.
© 2019 Uwe R. Zimmer, The Australian National University page 265 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

process P1;
statement X;
var sync : semaphore := 0; process P2;
wait (sync)
signal (sync);
statement Y; end P1;
statement B; end P2;
Communication & Synchronization
Towards synchronization
Condition synchronization by semaphores
Sequence of operations: A < B; 6X ; A@ < Y; 6X,Y ; B@ © 2019 Uwe R. Zimmer, The Australian National University page 266 of 757 (chapter 3: “Communication & Synchronization” up to page 368) statement A; process P1; statement X; var mutex : semaphore := 1; process P2; wait (mutex); wait (mutex); statement Y; statement B; signal (mutex); signal (mutex); statement Z; end P1; statement C; end P2; Communication & Synchronization Towards synchronization Mutual exclusion by semaphores Sequence of operations: A < B < C; X < Y < Z; 6X,Z ; A,B,C@; 6A,C ; X,Y,Z@; J6B ; Y@ © 2019 Uwe R. Zimmer, The Australian National University page 267 of 757 (chapter 3: “Communication & Synchronization” up to page 368) statement A; This is "queueless" and can translate into a single machine instruction. Communication & Synchronization package Ada.Synchronous_Task_Control is type Suspension_Object is limited private; Towards synchronization Semaphores in Ada (S : in out Suspension_Object); (S : in out Suspension_Object); (S : Suspension_Object) return Boolean; procedure Set_True procedure Set_False function Current_State procedure Suspend_Until_True (S : in out Suspension_Object); private ... ------ not specified by the language end Ada.Synchronous_Task_Control; only one task can be blocked at Suspend_Until_True! (Program_Error will be raised with a second task trying to suspend itself) no queues! minimal run-time overhead © 2019 Uwe R. Zimmer, The Australian National University page 268 of 757 (chapter 3: “Communication & Synchronization” up to page 368) for special cases only ... otherwise: Communication & Synchronization package Ada.Synchronous_Task_Control is type Suspension_Object is limited private; Towards synchronization Semaphores in Ada (S : in out Suspension_Object); (S : in out Suspension_Object); (S : Suspension_Object) return Boolean; procedure Set_True procedure Set_False function Current_State procedure Suspend_Until_True (S : in out Suspension_Object); private ... ------ not specified by the language end Ada.Synchronous_Task_Control; only one task can be blocked at Suspend_Until_True! (Program_Error will be raised with a second task trying to suspend itself) no queues! minimal run-time overhead © 2019 Uwe R. Zimmer, The Australian National University page 269 of 757 (chapter 3: “Communication & Synchronization” up to page 368) task B; task body B is begin task A; task body A is begin Communication & Synchronization Towards synchronization Malicious use of "queueless semaphores" with Ada.Synchronous_Task_Control; use Ada.Synchronous_Task_Control; X : Suspension_Object; ...... Suspend_Until_True (X); Suspend_Until_True (X); ...... ...... end B; end A; Could raise a Program_Error as multiple tasks potentially suspend on the same semaphore (occurs only with high efficiency semaphores which do not provide process queues) © 2019 Uwe R. Zimmer, The Australian National University page 270 of 757 (chapter 3: “Communication & Synchronization” up to page 368) task B; task body B is begin task A; task body A is begin Communication & Synchronization Towards synchronization Malicious use of "queueless semaphores" with Ada.Synchronous_Task_Control; use Ada.Synchronous_Task_Control; X, Y : Suspension_Object; ...... Suspend_Until_True (Y); Suspend_Until_True (X); Set_True (X); Set_True (Y); ...... end B; end A; Will result in a deadlock (assuming no other Set_True calls) © 2019 Uwe R. Zimmer, The Australian National University page 271 of 757 (chapter 3: “Communication & Synchronization” up to page 368) task B; task body B is begin task A; task body A is begin Communication & Synchronization Towards synchronization Malicious use of "queueless semaphores" with Ada.Synchronous_Task_Control; use Ada.Synchronous_Task_Control; X, Y : Suspension_Object; ...... Suspend_Until_True (Y); Suspend_Until_True (X); Suspend_Until_True (X); Suspend_Until_True (Y); ...... end B; end A; Will potentially result in a deadlock (with general semaphores) or a Program_Error in Ada. © 2019 Uwe R. Zimmer, The Australian National University page 272 of 757 (chapter 3: “Communication & Synchronization” up to page 368) pshared is actually a Boolean indicating whether the semaphore is to be shared between processes *value indicates the number of waiting processes as a negative integer in case the semaphore value is zero int sem_init int sem_destroy (sem_t *sem_location, int pshared, unsigned int value); (sem_t *sem_location); Communication & Synchronization Towards synchronization Semaphores in POSIX int sem_wait int sem_trywait int sem_timedwait (sem_t *sem_location, const struct timespec *abstime); (sem_t *sem_location); (sem_t *sem_location); int sem_post (sem_t *sem_location); int sem_getvalue (sem_t *sem_location, int *value); © 2019 Uwe R. Zimmer, The Australian National University page 273 of 757 (chapter 3: “Communication & Synchronization” up to page 368) Deadlock? Livelock? Mutual exclusion? sem_t mutex, cond[2]; typedef emun {low, high} priority_t; int waiting; int busy; void deallocate (priority_t P) { void allocate (priority_t P) { sem_wait (&mutex); busy = 0; sem_getvalue (&cond[high], &waiting); if (waiting < 0) { sem_wait (&mutex); if (busy) { sem_post (&cond[high]); } sem_post (&mutex); else { sem_getvalue (&cond[low], &waiting); if (waiting < 0) { sem_wait (&cond[P]); } sem_post (&cond[low]); } busy = 1; sem_post (&mutex); } else { sem_post (&mutex); © 2019 Uwe R. Zimmer, The Australian National University page 274 of 757 (chapter 3: “Communication & Synchronization” up to page 368) Communication & Synchronization Towards synchronization Semaphores in POSIX }} } wait check and manipulate signal administration Semaphore (int permits, boolean fair) protected void int availablePermits reducePermits drainPermits (int reduction) () Communication & Synchronization boolean tryAcquire } () } boolean int tryAcquire () (int permits, long timeout, TimeUnit unit) void void release release () (int permits) } protected Collection getQueuedThreads () int getQueueLength () boolean hasQueuedThreads () boolean isFair () String toString ()
© 2019 Uwe R. Zimmer, The Australian National University
}
page 275 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Towards synchronization
Semaphores in Java (since 2004)
void acquire ()
void acquire (int permits)
void acquireUninterruptibly (int permits)

Communication & Synchronization
Towards synchronization
Review of semaphores
• Semaphores are not bound to any resource or method or region
Compiler has no idea what is supposed to be protected by a semaphore.
• Semaphores are scattered all over the code
Hard to read and highly error-prone.
Adding or deleting a single semaphore operation usually stalls a whole system.
Semaphores are generally considered
inadequate for non-trivial systems.
(all concurrent languages and environments offer efficient and higher-abstraction synchronization methods)
Special (usually close-to-hardware) applications exist.
© 2019 Uwe R. Zimmer, The Australian National University page 276 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Distributed synchronization
Conditional Critical Regions
Basic idea:
• Critical regions are a set of associated code sections in different processes,
which are guaranteed to be executed in mutual exclusion: • Shared data structures are grouped in named regions
and are tagged as being private resources.
• Processes are prohibited from entering a critical region,
when another process is active in any associated critical region. • Condition synchronisation is provided by guards:
• When a process wishes to enter a critical region it evaluates the guard (under mu- tual exclusion). If the guard evaluates to false, the process is suspended / delayed.
• Generally, no access order can be assumed potential livelocks
© 2019 Uwe R. Zimmer, The Australian National University page 277 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

loop
loop
region critial_buffer_region when buffer.size < N do region critial_buffer_region when buffer.size > 0 do
Communication & Synchronization
buffer : buffer_t;
resource critial_buffer_region : buffer;
process producer;
process consumer;
—— place in buffer etc. end region;
—— take from buffer etc.
end loop; end producer;
end region; end loop;
© 2019 Uwe R. Zimmer, The Australian National University
page 278 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Distributed synchronization
Conditional Critical Regions
end consumer;

Communication & Synchronization
Distributed synchronization
Review of Conditional Critical Regions
• Well formed synchronization blocks and synchronization conditions.
• Code, data and synchronization primitives are associated (known to compiler and runtime).
• All guards need to be re-evaluated, when any conditional critical region is left: all involved processes are activated to test their guards
there is no order in the re-evaluation phase potential livelocks
• Condition synchronisation inside the critical code sections requires to leave and re-enter a critical region.
• As with semaphores the conditional critical regions are distributed all over the code. on a larger scale: same problems as with semaphores.
(The language Edison (Per Brinch Hansen, 1981) uses conditional critical regions for synchroniz- ation in a multiprocessor environment (each process is associated with exactly one processor).) © 2019 Uwe R. Zimmer, The Australian National University page 279 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Basic idea:
Communication & Synchronization
Centralized synchronization
Monitors
(Modula-1, Mesa — Dijkstra, Hoare)
• Collect all operations and data-structures shared in critical regions in one place, the monitor.
• Formulate all operations as procedures or functions.
• Prohibit access to data-structures, other than by the monitor-procedures and functions.
• Assure mutual exclusion of all monitor-procedures and functions.
© 2019 Uwe R. Zimmer, The Australian National University page 280 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

How to realize conditional synchronization?
monitor buffer;
export append, take;
var (* declare protected vars *) procedure append (I : integer);
begin
…
procedure take (var I : integer); …
(* initialisation *) end;
© 2019 Uwe R. Zimmer, The Australian National University
page 281 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Centralized synchronization
Monitors

Hoare-monitors:
Communication & Synchronization
Centralized synchronization
Monitors with condition synchronization
• Condition variables are implemented by semaphores (Wait and Signal).
• Queues for tasks suspended on condition variables are realized.
• A suspended task releases its lock on the monitor, enabling another task to enter.
(Hoare ‘74)
More efficient evaluation of the guards:
the task leaving the monitor can evaluate all guards and the right tasks can be activated.
Blocked tasks may be ordered and livelocks prevented.
© 2019 Uwe R. Zimmer, The Australian National University page 282 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
var BUF
top, base
NumberInBuffer
spaceavailable, itemavailable : condition;
procedure append (I : integer); begin
if NumberInBuffer = size then wait (spaceavailable);
end if;
BUF [top] := I;
NumberInBuffer := NumberInBuffer + 1; top := (top + 1) mod size;
signal (itemavailable)
end append; …
© 2019 Uwe R. Zimmer, The Australian National University
page 283 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Centralized synchronization
Monitors with condition synchronization
monitor buffer;
export append, take;
: array [ … ] of integer; : 0..size-1;
: integer;

The signalling and the waiting process are both active in the monitor!
if NumberInBuffer = 0 then wait (itemavailable);
Communication & Synchronization
end if;
I := BUF[base];
base := (base+1) mod size; NumberInBuffer := NumberInBuffer-1; signal (spaceavailable);
end take;
begin (* initialisation *)
NumberInBuffer := 0;
top := 0;
base := 0
end;
© 2019 Uwe R. Zimmer, The Australian National University
page 284 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Centralized synchronization
Monitors with condition synchronization
…
procedure take (var I : integer); begin

Communication & Synchronization
Centralized synchronization
Monitors with condition synchronization
Suggestions to overcome the multiple-tasks-in-monitor-problem:
• A signal is allowed only as the last action of a process before it leaves the monitor.
• A signal operation has the side-effect of executing a return statement.
• Hoare, Modula-1, POSIX:
a signal operation which unblocks another process has the side-effect of blocking the cur- rent process; this process will only execute again once the monitor is unlocked again.
• A signal operation which unblocks a process does not block the caller, but the unblocked process must re-gain access to the monitor.
© 2019 Uwe R. Zimmer, The Australian National University page 285 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Centralized synchronization
Monitors in Modula-1
• procedure wait (s, r):
delays the caller until condition variable s is true (r is the rank (or ‘priority’) of the caller).
• procedure send (s):
If a process is waiting for the condition variable s, then the process at the top of the queue of the highest filled rank is activated (and the caller suspended).
• function awaited (s) return integer: check for waiting processes on s.
© 2019 Uwe R. Zimmer, The Australian National University page 286 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

INTERFACE MODULE resource_control;
DEFINE allocate, deallocate;
VAR busy : BOOLEAN; free : SIGNAL;
PROCEDURE allocate;
BEGIN
IF busy THEN WAIT (free) END;
busy := TRUE;
END;
PROCEDURE deallocate;
BEGIN
busy := FALSE;
Communication & Synchronization
Centralized synchronization
Monitors in Modula-1
SEND (free); —— or: IF AWAITED (free) THEN SEND (free); END;
BEGIN
busy := false;
END.
© 2019 Uwe R. Zimmer, The Australian National University page 287 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Centralized synchronization
Monitors in POSIX (‘C’)
(types and creation) Synchronization between POSIX-threads:
typedef … pthread_mutex_t;
typedef … pthread_mutexattr_t;
typedef … pthread_cond_t;
typedef … pthread_condattr_t;
int pthread_mutex_init ( pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);
int pthread_mutex_destroy ( pthread_mutex_t *mutex);
int pthread_cond_init ( pthread_cond_t *cond, const pthread_condattr_t *attr); int pthread_cond_destroy ( pthread_cond_t *cond);
…
© 2019 Uwe R. Zimmer, The Australian National University page 288 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Attributes include:
• semantics for trying to lock a mutex which is locked already by the same thread
• sharing of mutexes and
condition variables between processes
• priorityceiling
• clock used for timeouts •…
int pthread_mutex_init (
pthread_mutex_t pthread_mutexattr_t pthread_mutex_t
*mutex, *attr); *mutex);
Communication & Synchronization
int pthread_mutex_destroy (
int pthread_cond_init ( pthread_cond_t
*cond, *attr); *cond);
int pthread_cond_destroy (
…
pthread_cond_t
© 2019 Uwe R. Zimmer, The Australian National University
page 289 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Centralized synchronization
Monitors in POSIX (‘C’)
(types and creation) Synchronization between POSIX-threads:
typedef … pthread_mutex_t;
typedef … pthread_mutexattr_t;
typedef … pthread_cond_t;
typedef … pthread_condattr_t;
const
const pthread_condattr_t

Undefined while locked
Undefined while threads are waiting
int pthread_mutex_init ( const
pthread_mutex_t pthread_mutexattr_t pthread_mutex_t
*mutex,
*attr);
*mutex);
int pthread_mutex_destroy ( int pthread_cond_init (
Communication & Synchronization
Centralized synchronization
Monitors in POSIX (‘C’)
(types and creation) Synchronization between POSIX-threads:
typedef … pthread_mutex_t; typedef … pthread_mutexattr_t; typedef … pthread_cond_t; typedef … pthread_condattr_t;
*cond, const pthread_condattr_t *attr); int pthread_cond_destroy ( pthread_cond_t *cond);
…
pthread_cond_t
© 2019 Uwe R. Zimmer, The Australian National University page 290 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

unblocks ‘at least one’ thread unblocks all threads
…
int pthread_mutex_lock (
int pthread_mutex_trylock (
int pthread_mutex_timedlock (
pthread_mutex_t *mutex);
pthread_mutex_t *mutex);
pthread_mutex_t *mutex,
int pthread_mutex_unlock
int pthread_cond_wait
( pthread_mutex_t *mutex);
int pthread_cond_timedwait
( pthread_cond_t *cond, pthread_mutex_t *mutex,
int pthread_cond_signal
int pthread_cond_broadcast
const struct timespec *abstime); ( pthread_cond_t *cond);
© 2019 Uwe R. Zimmer, The Australian National University
( pthread_cond_t *cond);
page 291 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Centralized synchronization
Monitors in POSIX (‘C’)
(operators)
const struct timespec *abstime);
( pthread_cond_t *cond, pthread_mutex_t *mutex);

undefined
if called ‘out of order’ i.e. mutex is not locked
…
int pthread_mutex_lock (
int pthread_mutex_trylock (
int pthread_mutex_timedlock (
pthread_mutex_t *mutex); pthread_mutex_t *mutex); pthread_mutex_t *mutex, struct timespec *abstime);
int pthread_mutex_unlock
int pthread_cond_wait
( (
pthread_mutex_t *mutex);
int pthread_cond_timedwait
(
pthread_cond_t *cond, pthread_mutex_t *mutex); pthread_cond_t *cond, pthread_mutex_t *mutex,
int pthread_cond_signal
int pthread_cond_broadcast (
© 2019 Uwe R. Zimmer, The Australian National University
page 292 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Centralized synchronization
Monitors in POSIX (‘C’)
(
pthread_cond_t *cond);
pthread_cond_t *cond);
const
(operators)
const struct timespec *abstime);

can be called • anytime
• anywhere
• multipletimes
…
int pthread_mutex_lock ( int pthread_mutex_trylock ( int pthread_mutex_timedlock (
pthread_mutex_t *mutex); pthread_mutex_t *mutex); pthread_mutex_t *mutex, struct timespec *abstime);
int pthread_mutex_unlock
int pthread_cond_wait
const (
pthread_mutex_t *mutex);
int pthread_cond_timedwait
( (
pthread_cond_t *cond, pthread_mutex_t *mutex); pthread_cond_t *cond, pthread_mutex_t *mutex,
int pthread_cond_signal ( int pthread_cond_broadcast (
pthread_cond_t *cond); pthread_cond_t *cond);
© 2019 Uwe R. Zimmer, The Australian National University
page 293 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Centralized synchronization
Monitors in POSIX (‘C’)
(operators)
const struct timespec *abstime);

Communication & Synchronization
#define BUFF_SIZE 10
typedef struct { pthread_mutex_t mutex;
PTHREAD_COND_WAIT (
&B->buffer_not_full,
PTHREAD_COND_WAIT (
&B->buffer_not_empty,
&B->mutex); }}
&B->mutex);
PTHREAD_MUTEX_UNLOCK (&B->mutex);
PTHREAD_COND_SIGNAL (
PTHREAD_MUTEX_UNLOCK (&B->mutex);
PTHREAD_COND_SIGNAL (
return 0;
return 0;
page 294 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Centralized synchronization
pthread_cond_t buffer_not_full;
pthread_cond_t buffer_not_empty;
int count, first, last;
int buf [BUFF_SIZE];
} buffer;
int append (int item, buffer *B) { PTHREAD_MUTEX_LOCK (&B->mutex); while (B->count == BUFF_SIZE) {
int take (int *item, buffer *B) { PTHREAD_MUTEX_LOCK (&B->mutex); while (B->count == 0) {
&B->buffer_not_empty);
&B->buffer_not_full);
}}
© 2019 Uwe R. Zimmer, The Australian National University

need to be called with a locked mutex
better to be called
after unlocking all mutexes (as it is itself potentially blocking)
Communication & Synchronization
#define BUFF_SIZE 10
typedef struct { pthread_mutex_t mutex;
PTHREAD_COND_WAIT ( &B->buffer_not_full,
PTHREAD_COND_WAIT ( &B->buffer_not_empty,
}
PTHREAD_MUTEX_UNLOCK (&B->mutex); PTHREAD_COND_SIGNAL (
}
PTHREAD_MUTEX_UNLOCK (&B->mutex); PTHREAD_COND_SIGNAL (
return 0;
return 0;
page 295 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
&B->mutex);
&B->mutex);
Centralized synchronization
pthread_cond_t buffer_not_full; pthread_cond_t buffer_not_empty; int count, first, last;
int buf [BUFF_SIZE];
} buffer;
int append (int item, buffer *B) { PTHREAD_MUTEX_LOCK (&B->mutex); while (B->count == BUFF_SIZE) {
int take (int *item, buffer *B) { PTHREAD_MUTEX_LOCK (&B->mutex); while (B->count == 0) {
&B->buffer_not_empty);
&B->buffer_not_full);
}}
© 2019 Uwe R. Zimmer, The Australian National University

using System;
using System.Threading;
static long data_to_protect = 0;
static void Reader()
static void Writer()
Communication & Synchronization
{ try {
Monitor.Enter (data_to_protect); Monitor.Wait (data_to_protect); … read out protected data
{ try {
Monitor.Enter (data_to_protect); … write protected data Monitor.Pulse (data_to_protect);
Centralized synchronization
Monitors in C#
}}
finally { finally {
Monitor.Exit (data_to_protect); }}
Monitor.Exit (data_to_protect);
}}
© 2019 Uwe R. Zimmer, The Australian National University page 296 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

using namespace System;
using namespace System::Threading
private: integer data_to_protect; void Reader()
void Writer() { try {
Communication & Synchronization
{ try {
Monitor::Enter (data_to_protect); Monitor::Wait (data_to_protect); … read out protected data
Monitor::Enter (data_to_protect); … write protected data Monitor::Pulse (data_to_protect);
};
};
}
finally {
}
finally {
Monitor::Exit (data_to_protect); }
Monitor.Exit (data_to_protect); }
© 2019 Uwe R. Zimmer, The Australian National University
page 297 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Centralized synchronization
Monitors in Visual C++

Imports System
Imports System.Threading
Public Sub Reader
Public Sub Writer Try
Communication & Synchronization
Private Dim data_to_protect As Integer = 0
Try
Monitor.Enter (data_to_protect) Monitor.Wait (data_to_protect) … read out protected data
Monitor.Enter (data_to_protect) … write protected data Monitor.Pulse (data_to_protect)
Finally
Monitor.Exit (data_to_protect)
Finally
Monitor.Exit (data_to_protect)
End Try End Sub
End Try End Sub
© 2019 Uwe R. Zimmer, The Australian National University
page 298 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Centralized synchronization
Monitors in Visual Basic

… the Java library monitor connects data or condition variables to the monitor by convention only!
public void reader
throws InterruptedException {
public void writer
throws InterruptedException {
}
}
mon.enter(); Condvar.await();
… read out protected data mon.leave();
mon.enter();
… write protected data Condvar.signal(); mon.leave();
© 2019 Uwe R. Zimmer, The Australian National University
page 299 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Monitor mon = new Monitor();
Monitor.Condition Condvar = mon.new Condition();
Centralized synchronization
Monitors in Java

Communication & Synchronization
Centralized synchronization
Monitors in Java
(by means of language primitives)
Java provides two mechanisms to construct a monitors-like structure:
• Synchronized methods and code blocks:
all methods and code blocks which are using the synchronized tag are mutually exclusive with respect to the addressed class.
• Notification methods:
wait, notify, and notifyAll can be used only in synchronized regions and are waking any or all threads, which are waiting in the same synchronized object.
© 2019 Uwe R. Zimmer, The Australian National University page 300 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Considerations:
Communication & Synchronization
Centralized synchronization
Monitors in Java
(by means of language primitives)
1. Synchronized methods and code blocks:
• In order to implement a monitor all methods in an object need to be synchronized.
any other standard method can break a Java monitor and enter at any time. • Methods outside the monitor-object can synchronize at this object.
it is impossible to analyse a Java monitor locally, since lock ac- cesses can exist all over the system.
• Static data is shared between all objects of a class.
access to static data need to be synchronized with all objects of a class.
Synchronize either in static synchronized blocks: synchronized (this.getClass()) {…} or in static methods: public synchronized static {…}
© 2019 Uwe R. Zimmer, The Australian National University page 301 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Considerations:
Communication & Synchronization
Centralized synchronization
Monitors in Java
(by means of language primitives)
2. Notification methods: wait, notify, and notifyAll • wait suspends the thread and releases the local lock only
nested wait-calls will keep all enclosing locks. • notify and notifyAll do not release the lock!
methods, which are activated via notification need to wait for lock-access.
• Java does not require any specific release order (like a queue) for wait-suspended threads
livelocks are not prevented at this level (in opposition to RT-Java).
• There are no explicit conditional variables associated with the monitor or data.
notified threads need to wait for the lock to be released and to re-evaluate its entry condition.
© 2019 Uwe R. Zimmer, The Australian National University page 302 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
public class ConditionVariable {
public boolean wantToSleep = false;
}
Centralized synchronization
(by means of language primitives) Standard monitor solution:
• introduce synchronization-scopes in monitor-methods:
synchronize on the adequate conditional variables first and synchronize on the adequate monitor-object second.
Monitors in Java
• declare the monitored data-structures private to the monitor object (non-static).
• introduce a class ConditionVariable:
• make sure that all methods in the monitor are implementing the correct synchronizations.
• make sure that no other method in the whole system is
synchronizing on or interfering with this monitor-object in any way by convention.
© 2019 Uwe R. Zimmer, The Australian National University page 303 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
private int
private int
private int
private boolean writing = false;
Centralized synchronization
readers = 0;
waitingReaders = 0;
waitingWriters = 0;
Monitors in Java
(multiple-readers-one-writer-example: usage of external conditional variables)
public class ReadersWriters {
ConditionVariable OkToRead = new ConditionVariable ();
ConditionVariable OkToWrite = new ConditionVariable (); …
© 2019 Uwe R. Zimmer, The Australian National University page 304 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

}…
} }
Communication & Synchronization
Centralized synchronization
if (writing | readers > 0) { waitingWriters++; OkToWrite.wantToSleep = true;
} else {
writing = true; OkToWrite.wantToSleep = false;
Monitors in Java
(multiple-readers-one-writer-example: usage of external conditional variables)
… public void StartWrite () throws InterruptedException { synchronized (OkToWrite) {
synchronized (this) {
if (OkToWrite.wantToSleep) OkToWrite.wait (); }
© 2019 Uwe R. Zimmer, The Australian National University page 305 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
synchronized (OkToWrite) { synchronized (this) {
} }}}} …
Centralized synchronization
Monitors in Java
(multiple-readers-one-writer-example: usage of external conditional variables)
… public void StopWrite () { synchronized (OkToRead) {
if (waitingWriters > 0) {
waitingWriters–;
OkToWrite.notify (); // wakeup one writer
} else {
writing = false;
OkToRead.notifyAll (); // wakeup all readers readers = waitingReaders;
waitingReaders = 0;
© 2019 Uwe R. Zimmer, The Australian National University page 306 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

}…
}
Communication & Synchronization
Centralized synchronization
Monitors in Java
(multiple-readers-one-writer-example: usage of external conditional variables)
… public void StartRead () throws InterruptedException { synchronized (OkToRead) {
synchronized (this) {
if (writing | waitingWriters > 0) { waitingReaders++; OkToRead.wantToSleep = true;
} else { readers++;
OkToRead.wantToSleep = false;
}
if (OkToRead.wantToSleep) OkToRead.wait (); }
© 2019 Uwe R. Zimmer, The Australian National University page 307 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

} }
} }
Communication & Synchronization
Centralized synchronization
Monitors in Java
(multiple-readers-one-writer-example: usage of external conditional variables)
… public void StopRead () { synchronized (OkToWrite) {
synchronized (this) {
readers–;
if (readers == 0 & waitingWriters > 0) {
© 2019 Uwe R. Zimmer, The Australian National University
page 308 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
waitingWriters–;
OkToWrite.notify ();
}

Communication & Synchronization
Per Brinch Hansen (1938-2007) in 1999:
Centralized synchronization
Monitors in Java
Java’s most serious mistake was the decision to use the sequential part of the language to implement the run-time support for its paral- lel features. It strikes me as absurd to write a compiler for the sequen- tial language concepts only and then attempt to skip the much more difficult task of implementing a secure parallel notation. This wish- ful thinking is part of Java’s unfortunate inheritance of the insecure
C language and its primitive, error-prone library of threads methods.
“Per Brinch Hansen is one of a handful of computer pioneers who was responsible for advan- cing both operating systems development and concurrent programming from ad hoc tech- niques to systematic engineering disciplines.” (from his IEEE 2002 Computer Pioneer Award)
© 2019 Uwe R. Zimmer, The Australian National University page 309 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Centralized synchronization
Object-orientation and synchronization
Since mutual exclusion, notification, and condition synchronization schemes need to be de- signed and analyzed considering the implementation of all involved methods and guards:
New methods cannot be added without re-evaluating the class! Re-usage concepts of object-oriented programming do not translate to
synchronized classes (e.g. monitors) and thus need to be considered carefully.
The parent class might need to be adapted
in order to suit the global synchronization scheme.
Inheritance anomaly (Matsuoka & Yonezawa ‘93)
Methods to design and analyse expandible synchronized systems exist, yet they
are complex and not offered in any concurrent programming language. Alternatively, inheritance can be banned in the context of synchronization (e.g. Ada).
© 2019 Uwe R. Zimmer, The Australian National University page 310 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Centralized synchronization
Monitors in POSIX, Visual C++, C#, Visual Basic & Java
All provide lower-level primitives for the construction of monitors.
All rely on convention rather than compiler checks.
Visual C++, C+ & Visual Basic offer data-encapsulation and connection to the monitor.
Java offers data-encapsulation (yet not with respect to a monitor).
POSIX (being a collection of library calls)
does not provide any data-encapsulation by itself.
Extreme care must be taken when employing object-oriented programming and synchronization (incl. monitors)
© 2019 Uwe R. Zimmer, The Australian National University page 311 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Centralized synchronization
Nested monitor calls
Assuming a thread in a monitor is calling an operation in
another monitor and is suspended at a conditional variable there:
the called monitor is aware of the suspension and allows other threads to enter.
the calling monitor is possibly not aware of the suspension and keeps its lock!
the unjustified locked calling monitor reduces the system performance and leads to potential deadlocks.
Suggestions to solve this situation:
• Maintain the lock anyway: e.g. POSIX, Java
• Prohibit nested monitor calls: e.g. Modula-1
• Provide constructs which specify the release of a monitor lock for remote calls, e.g. Ada
© 2019 Uwe R. Zimmer, The Australian National University page 312 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Centralized synchronization
Criticism of monitors
• Mutual exclusion is solved elegantly and safely.
• Conditional synchronization is on the level of semaphores still
all criticism about semaphores applies inside the monitors
Mixture of low-level and high-level synchronization constructs.
© 2019 Uwe R. Zimmer, The Australian National University page 313 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Combine with
to:
the encapsulation feature of monitors
the coordinated entries of conditional critical regions
Communication & Synchronization
Centralized synchronization
Synchronization by protected objects
Protected objects
• All controlled data and operations are encapsulated.
• Operations are mutual exclusive (with exceptions for read-only operations).
• Guards (predicates) are syntactically attached to entries.
• No protected data is accessible (other than by the defined operations).
• Fairness inside operations is guaranteed by queuing (according to their priorities).
• Fairness across all operations is guaranteed by the “internal progress first” rule.
• Re-blocking provided by re-queuing to entries (no internal condition variables).
© 2019 Uwe R. Zimmer, The Australian National University page 314 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

•
protected functions can have ‘in’ parameters only
and are not allowed to alter the private data (enforced by the compiler).
Communication & Synchronization
protected type Shared_Data (Initial : Data_Item) is function Read return Data_Item;
procedure Write (New_Value : Data_Item);
private
The_Data : Data_Item := Initial; end Shared_Data_Item;
Centralized synchronization
Synchronization by protected objects
Some read-only operations do not need to be mutually exclusive:
(Simultaneous read-access)
protected functions allow simultaneous access (but mutual exclusive with other operations). … there is no defined priority between functions and other protected operations in Ada.
© 2019 Uwe R. Zimmer, The Australian National University page 315 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
type Index is mod Buffer_Size;
subtype Count is Natural range 0 .. Buffer_Size; type Buffer_T is array (Index) of Data_Item;
protected type Bounded_Buffer is entry Get (Item : out Data_Item);
entry Put (Item : Data_Item);
private
First : Index := Index’First;
Last : Index := Index’Last;
Num : Count := 0;
Buffer : Buffer_T;
end Bounded_Buffer;
© 2019 Uwe R. Zimmer, The Australian National University
page 316 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Centralized synchronization
Synchronization by protected objects
(Condition synchronization: entries & barriers) Condition synchronization is realized in the form of protected procedures
combined with boolean predicates (barriers): called entries in Ada: Buffer_Size : constant Integer := 10;

Communication & Synchronization
Item := Buffer (First);
First := First + 1;
Num := Num – 1;
Centralized synchronization
Synchronization by protected objects
(Condition synchronization: entries & barriers)
protected body Bounded_Buffer is
entry Get (Item : out Data_Item) when Num > 0 is
begin
end Get;
entry Put (Item : Data_Item) when Num < Buffer_Size is begin Last := Last + 1; Buffer (Last) := Item; Num := Num + 1; end Put; end Bounded_Buffer; © 2019 Uwe R. Zimmer, The Australian National University page 317 of 757 (chapter 3: “Communication & Synchronization” up to page 368) Buffer : Bounded_Buffer; select Buffer.Put (Some_Data); or delay 10.0; -- do something after 10 s. end select; select Buffer.Get (Some_Data); else -- do something else end select; © 2019 Uwe R. Zimmer, The Australian National University page 318 of 757 (chapter 3: “Communication & Synchronization” up to page 368) Communication & Synchronization Centralized synchronization Synchronization by protected objects (Withdrawing entry calls) Buffer : Bounded_Buffer; select select Buffer.Put (Some_Data); or Buffer.Get (Some_Data); then abort delay 10.0; -- do something after 10 s. -- meanwhile try something else end select; end select; select select Buffer.Get (Some_Data); else then abort -- do something else Buffer.Put (Some_Data); -- try to enter for 10 s. end select; © 2019 Uwe R. Zimmer, The Australian National University end select; page 319 of 757 (chapter 3: “Communication & Synchronization” up to page 368) Communication & Synchronization Centralized synchronization Synchronization by protected objects (Withdrawing entry calls) delay 10.0; Communication & Synchronization • on leaving a protected procedure or entry, all potentially altered barriers are re-evaluated. Centralized synchronization Synchronization by protected objects (Barrier evaluation) Barrier in protected objects need to be evaluated only on two occasions: • on creating a protected object, all barrier are evaluated according to the initial values of the internal, protected data. Alternatively an implementation may choose to evaluate barriers on those two occasions: • on calling a protected entry, the one associated barrier is evaluated. • on leaving a protected procedure or entry, all potentially altered barriers with tasks queued up on them are re-evaluated. Barriers are not evaluated while inside a protected object or on leaving a protected function. © 2019 Uwe R. Zimmer, The Australian National University page 320 of 757 (chapter 3: “Communication & Synchronization” up to page 368) private entry Proceed when Proceed’count > 5
Release : Boolean := False; end Block_Five;
or Release is
© 2019 Uwe R. Zimmer, The Australian National University
page 321 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Centralized synchronization
Synchronization by protected objects
(Operations on entry queues)
The count attribute indicates the number of tasks waiting at a specific queue:
protected Block_Five is entry Proceed;
protected body Block_Five is
begin
Release := Proceed’count > 0; end Proceed;
end Block_Five;

private
begin
New_Message : Message;
Arrived
M := New_Message
end Broadcast;
Arrived := Receive’count > 0; end Proceed;
© 2019 Uwe R. Zimmer, The Australian National University
end Broadcast;
page 322 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Centralized synchronization
Synchronization by protected objects
(Operations on entry queues)
The count attribute indicates the number of tasks waiting at a specific queue:
protected type Broadcast is
entry Receive (M: out Message);
protected body Broadcast is
entry Receive (M: out Message)
procedure Send (M:
Message);
: Boolean := False;
when Arrived is
procedure Send (M: Message) is
begin
New_Message := M;
Arrived := Receive’count > 0; end Send;

Communication & Synchronization
Centralized synchronization
Synchronization by protected objects
(Entry families, requeue & private entries) Additional, essential primitives for concurrent control flows:
• Entry families:
A protected entry declaration can contain
a discrete subtype selector, which can be evaluated by the barrier (other parameters cannot be evaluated by barriers) and implements an array of protected entries.
• Requeue facility:
Protected operations can use ‘requeue’ to redirect tasks to other internal, external, or private entries. The current protected operation is finished and the lock on the object is released.
‘Internal progress first’-rule: external tasks are only considered for queuing on barriers once no internally requeued task can be progressed any further!
• Private entries:
Protected entries which are not accessible from outside the protected object, but can be employed as destinations for requeue operations.
© 2019 Uwe R. Zimmer, The Australian National University page 323 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

package Modes is
package body Modes is
type Mode_T is
(Takeoff, Ascent, Cruising,
protected body Mode_Gate is procedure Set_Mode
Descent, Landing);
(Mode: Mode_T) is
Communication & Synchronization
protected Mode_Gate is
procedure Set_Mode (Mode: Mode_T); entry Wait_For_Mode (Mode_T);
begin
private
entry Wait_For_Mode
(for Mode in Mode_T)
when Current_Mode = Mode is
Current_Mode : Mode_Type := Takeoff; end Mode_Gate;
end Modes;
begin null;
end Wait_For_Mode;
© 2019 Uwe R. Zimmer, The Australian National University
end Modes;
page 324 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Centralized synchronization
Synchronization by protected objects
(Entry families)
Current_Mode := Mode; end Set_Mode;
end Mode_Gate;

Communication & Synchronization
type Urgency is (urgent, not_so_urgent); type Server_Farm is (primary, secondary);
protected Pre_Filter is
entry Reception (U : Urgency);
private
entry Server (Server_Farm) (U : Urgency);
end Pre_Filter;
Centralized synchronization
Synchronization by protected objects
(Entry families, requeue & private entries) How to moderate the flow of incoming calls to a busy server farm?
© 2019 Uwe R. Zimmer, The Australian National University page 325 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
protected body Pre_Filter is entry Reception (U : Urgency)
Centralized synchronization
Synchronization by protected objects
(Entry families, requeue & private entries)
when Server (primary)’count = 0 or else Server (secondary)’count = 0 is begin
If U = urgent and then Server (primary)’count = 0 then requeue Server (primary);
else
requeue Server (secondary); end if;
end Reception;
entry Server (for S in Server_Farm) (U : Urgency) when True is
begin null; — might try something even more useful end Server;
end Pre_Filter;
© 2019 Uwe R. Zimmer, The Australian National University page 326 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Thus the following operations are prohibited:
Centralized synchronization
Synchronization by protected objects
(Restrictions for protected operations)
All code inside a protected procedure, function or entry is bound to non-blocking operations.
• entry call statements
• delay statements
• task creations or activations
• select statements
• accept statements
• … as well as calls to sub-programs which contain any of the above
The requeue facility allows for a potentially blocking operation,
and releases the current lock!
© 2019 Uwe R. Zimmer, The Australian National University page 327 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

General • Levels of abstraction
Monitors
Conditional critical regions
Criteria:
• Centralized versus distributed
Data structure encapsulation
Guards (barriers)
• Support for automated (compiler based) consistency and correctness validation
Synchronized methods (mutual exclusion)
Conditional variables
• Error sensitivity
• Predictability
• Efficiency
Semaphores (atomic P, V ops)
© 2019 Uwe R. Zimmer, The Australian National University
page 328 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Shared memory based synchronization
Protected objects
Flags (atomic word access)

POSIX
• All low level constructs available
Monitors
Conditional critical regions
• Connection with the actual data-struc- tures by means of convention only
Data structure encapsulation
Guards (barriers)
• Extremely error-prone
• Degree of non-determinism intro-
Synchronized methods (mutual exclusion)
Conditional variables
duced by the ‘release some’ semantic
• ‘C’ based
• Portable
Semaphores (atomic P, V ops)
© 2019 Uwe R. Zimmer, The Australian National University
page 329 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Shared memory based synchronization
Protected objects
Flags (atomic word access)

Java
• Mutual exclusion available.
Monitors
Conditional critical regions
• General notification feature (not connected to other locks, hence not a conditional variable)
Data structure encapsulation
Guards (barriers)
• Universal object orientation makes local analysis hard or even impossible
Synchronized methods (mutual exclusion)
Conditional variables
• Mixture of
high-level object oriented features and low level concurrency primitives
Semaphores (atomic P, V ops)
© 2019 Uwe R. Zimmer, The Australian National University
page 330 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Shared memory based synchronization
Protected objects
Flags (atomic word access)

• Data is associated with the locks to protect it
Guards (barriers)
• Condition variables related to the data protection locks
Synchronized methods (mutual exclusion)
Conditional variables
• Mixture of
high-level object oriented features and low level concurrency primitives
Semaphores (atomic P, V ops)
© 2019 Uwe R. Zimmer, The Australian National University
page 331 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Shared memory based synchronization
C#, Visual C++, Visual Basic
Monitors
Conditional critical regions
• Mutual exclusion via library calls (convention)
Data structure encapsulation
Protected objects
Flags (atomic word access)

C++14
• Mutual exclusion in scopes
Data structure encapsulation
• Data is not strictly associated with the locks to protect it
Guards (barriers)
• Condition variables related to the mutual exclusion locks
Synchronized methods (mutual exclusion)
Conditional variables
Communication & Synchronization
Shared memory based synchronization
• Set of essential primitives without combin- ing them in a syntactically strict form (yet?)
© 2019 Uwe R. Zimmer, The Australian National University
page 332 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Monitors
Conditional critical regions
Protected objects
Semaphores (atomic P, V ops)
Flags (atomic word access)

Rust
• Mutual exclusion in scopes
Monitors
Conditional critical regions
• Data is strictly associated with locks to protect it
Data structure encapsulation
Guards (barriers)
• Condition variables related to the mutual exclusion locks
Synchronized methods (mutual exclusion)
• Combined with the message passing semantics already a power set of tools.
Conditional variables
• Concurrency features migrated to a standard library.
Semaphores (atomic P, V ops)
© 2019 Uwe R. Zimmer, The Australian National University
page 333 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Shared memory based synchronization
Protected objects
Flags (atomic word access)

• Full implementation of the Dijkstra / Hoare monitor concept
Data structure encapsulation
Guards (barriers)
Communication & Synchronization
Shared memory based synchronization
Modula-1, Chill, Parallel Pascal, …
The term monitor appears in many other concurrent languages, yet it is usually not associated with an actual language primitive.
Synchronized methods (mutual exclusion)
Conditional variables
© 2019 Uwe R. Zimmer, The Australian National University
page 334 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Monitors
Conditional critical regions
Protected objects
Semaphores (atomic P, V ops)
Flags (atomic word access)

• High-level synchronization support which scales to large size projects.
• Full compiler support
incl. potential deadlock analysis
Data structure encapsulation
Guards (barriers)
Communication & Synchronization
Shared memory based synchronization
Ada
Monitors
Conditional critical regions
• Low-Level semaphores for very special cases
Synchronized methods (mutual exclusion)
Ada has still
no mainstream competitor
in the field of explicit concurrency. (2018)
Conditional variables
© 2019 Uwe R. Zimmer, The Australian National University
page 335 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Protected objects
Semaphores (atomic P, V ops)
Flags (atomic word access)

Communication & Synchronization
High Performance Computing
Synchronization in large scale concurrency
High Performance Computing (HPC) emphasizes on keeping as many CPU nodes busy as possible:
Avoid contention on sparse resources.
Data is assigned to individual processes rather than processes synchronizing on data.
Data integrity is achieved by keeping the CPU nodes in approximate “lock-step”, yet there is still a need to re-sync concurrent entities.
Traditionally this has been implemented using the
Message Passing Interface (MPI) while implementing separate address spaces.
Current approaches employ partitioned address spaces,
i.e. memory spaces can overlap and be re-assigned. Chapel, Fortress, X10.
Not all algorithms break down into independent computation slices and so there is a need for memory integrity mechanisms in shared/partitioned address spaces.
© 2019 Uwe R. Zimmer, The Australian National University page 336 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Current developments
Atomic operations in X10
X10 offers only atomic blocks in unconditional and conditional form.
• Unconditional atomic blocks are guaranteed to be non-blocking,
which means that they cannot be nested and need to be implemented using roll-backs.
• Conditional atomic blocks can also be used as a pure notification system (similar to the Java notify method).
• Parallel statements (incl. parallel, i.e. unrolled ‘loops’).
• Shared variables (and their access mechanisms) are not defined.
• The programmer does not specify the scope of the locks (atomic blocks) but they are managed by the compiler/runtime environment.
Code analysis algorithms are required in order to provide efficiently,
otherwise the runtime environment needs to associate every atomic block with a global lock.
© 2019 Uwe R. Zimmer, The Australian National University page 337 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Chapel offers a variety of concurrent primitives:
Current developments
Synchronization in Chapel
• Parallel operations on data (e.g. concurrent array operations)
• Parallel statements (incl. parallel, i.e. unrolled ‘loops’)
• Parallelism can also be explicitly limited by serializing statements
• Atomic blocks for the purpose to construct atomic transactions
• Memory integrity needs to be programmed by means of synchronization statements (waiting for one or multiple control flows to complete)
and/or atomic blocks
Further Chapel semantics are still forthcoming … so there is still hope for a stronger shared memory synchronization / memory integrity construct.
© 2019 Uwe R. Zimmer, The Australian National University page 338 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Synchronization model
Message structure
• Asynchronous
• Synchronous
• Remote invocation
• arbitrary
• restricted to ‘basic’ types
• restricted to un-typed communications
Addressing (name space)
• directcommunication
• mail-boxcommunication
© 2019 Uwe R. Zimmer, The Australian National University
page 339 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Synchronization
Message-based synchronization

Delay the sender process until
send
• Receiver becomes available
• Receiver acknowledges reception
© 2019 Uwe R. Zimmer, The Australian National University
page 340 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Synchronous message (sender waiting)
Message-based synchronization
Message protocols
time
asyncronous
syncronous time
receive

Delay the receiver process until
• Sender becomes available
• Sender concludes transmission
© 2019 Uwe R. Zimmer, The Australian National University
page 341 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Synchronous message (receiver waiting)
receive
Message-based synchronization
Message protocols
send
time
asyncronous
syncronous time

Communication & Synchronization
Asynchronous message
Neither the sender nor the receiver is blocked:
receive
• Message is not transferred directly
• A buffer is required to store the messages
• Policy required for buffer sizes and buffer overflow situations
© 2019 Uwe R. Zimmer, The Australian National University
page 342 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Message-based synchronization
Message protocols
send
time
asyncronous
syncronous time

Introducing an intermediate process:
• Intermediate needs to be ac- cepting messages at all times.
• Intermediate also needs to send out messages on request.
Communication & Synchronization
Asynchronous message (simulated by synchronous messages)
send
receive send
While processes are blocked in the sense of synchronous message passing, they are not ac- tually delayed as the intermediate is always ready.
time
time time
© 2019 Uwe R. Zimmer, The Australian National University
page 343 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Message-based synchronization
Message protocols
receive

Introducing two asynchronous messages:
receive
receive send
Communication & Synchronization
• Both processes voluntarily suspend them- selves until the transaction is complete.
• As no immediate communication takes place, the processes are never actually synchronized.
• The sender (but not the receiver) process knows that the transaction is complete.
time
asyncronous syncronous
time
© 2019 Uwe R. Zimmer, The Australian National University
page 344 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Message-based synchronization
Message protocols
Synchronous message
(simulated by asynchronous messages) send

• Passparameters
remote invocation
• Keep sender blocked while
receiver executes the local procedure
results
Communication & Synchronization
Remote invocation
• Delay sender or receiver
until the first rendezvous point
invocation
• Passresults
• Release both processes out of the rendezvous
asyncronous
syncronous time
© 2019 Uwe R. Zimmer, The Australian National University
page 345 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Message-based synchronization
Message protocols
time

• •
Simulate two synchronous messages Processes are never actually synchronized
receive
receive send
© 2019 Uwe R. Zimmer, The Australian National University
page 346 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Message-based synchronization
Message protocols
Remote invocation
(simulated by asynchronous messages) send
receive send
send receive
time
asyncronous
syncronous time

Communication & Synchronization
Remote invocation (no results)
Shorter form of remote invocation which does not wait for results to be passed back.
remote invocation
invocation
• Still both processes are actually synchronized at the time of the invocation.
© 2019 Uwe R. Zimmer, The Australian National University
page 347 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Message-based synchronization
Message protocols
time
asyncronous
syncronous time

• •
Simulate one synchronous message Processes are never actually synchronized
receive
receive send
Communication & Synchronization
Message-based synchronization
Message protocols
Remote invocation (no results)
(simulated by asynchronous messages) send
© 2019 Uwe R. Zimmer, The Australian National University
page 348 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
time
asyncronous syncronous
time

Communication & Synchronization
Message-based synchronization
Synchronous vs. asynchronous communications Purpose ‘synchronization’: synchronous messages / remote invocations
Purpose ‘last message(s) only’: asynchronous messages
Synchronous message passing in distributed systems requires hardware support.
Asynchronous message passing requires the usage of buffers and overflow policies. Can both communication modes emulate each other?
• Synchronous communications are emulated by a combination of asynchronous messages in some systems (not identical with hardware supported synchronous communication).
• Asynchronous communications can be emulated in
synchronized message passing systems by introducing a ‘buffer-task’ (de-coupling sender and receiver as well as allowing for broadcasts).
© 2019 Uwe R. Zimmer, The Australian National University page 350 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Direct versus indirect:
Communication & Synchronization
send to wait for from send to
wait for from
Asymmetrical addressing:
send to …
wait for
Client-server paradigm
© 2019 Uwe R. Zimmer, The Australian National University
page 351 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Message-based synchronization
Addressing (name space)

Communication medium:
© 2019 Uwe R. Zimmer, The Australian National University
page 352 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Message-based synchronization
Addressing (name space)
Connections one-to-one
Functionality
buffer, queue, synchronization
one-to-many one-to-all many-to-one all-to-one many-to-many
multicast
broadcast
local server, synchronization general server, synchronization general network- or bus-system

Communication & Synchronization
Message-based synchronization
Message structure
• Machine dependent representations need to be taken care of in a distributed environment.
• Communication system is often outside the typed language environment.
Most communication systems are handling streams (packets) of a basic element type only.
Conversion routines for data-structures other then the basic element type are supplied …
… manually (POSIX, C)
… semi-automatic (CORBA)
… automatic (compiler-generated) and typed-persistent (Ada, CHILL, Occam2)
© 2019 Uwe R. Zimmer, The Australian National University page 353 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Message-based synchronization
Message structure (Ada)
package Ada.Streams is
pragma Pure (Streams);
type Root_Stream_Type is abstract tagged limited private; type Stream_Element is mod implementation-defined;
type Stream_Element_Offset is range implementation-defined;
subtype Stream_Element_Count is
Stream_Element_Offset range 0..Stream_Element_Offset’Last;
type Stream_Element_Array is
array (Stream_Element_Offset range <>) of Stream_Element;
procedure Read (…) is abstract; procedure Write (…) is abstract;
private
… — not specified by the language end Ada.Streams;
© 2019 Uwe R. Zimmer, The Australian National University
page 354 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
Message-based synchronization
Message structure (Ada)
Reading and writing values of any subtype S of a specific type T to a Stream: procedure S’Write (Stream : access Ada.Streams.Root_Stream_Type’Class;
Item :inT);
procedure S’Class’Write (Stream : access Ada.Streams.Root_Stream_Type’Class;
Item : in T’Class);
procedure S’Read (Stream : access Ada.Streams.Root_Stream_Type’Class;
Item : out T);
procedure S’Class’Read (Stream : access Ada.Streams.Root_Stream_Type’Class;
Item : out T’Class) Reading and writing values, bounds and discriminants
of any subtype S of a specific type T to a Stream:
procedure S’Output (Stream : access Ada.Streams.Root_Stream_Type’Class;
Item : in T);
function S’Input (Stream : access Ada.Streams.Root_Stream_Type’Class) return T;
© 2019 Uwe R. Zimmer, The Australian National University page 355 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

POSIX: MPI: CHILL: Occam2:
“message queues”:
ordered indirect [asymmetrical | symmetrical] asynchronous
byte-level many-to-many message passing
“message passing”:
ordered [direct | indirect] [asymmetrical | symmetrical] asynchronous memory-block- level [one-to-one | one-to-many | many-to-one | many-to-many] message passing “buffers”, ”signals”:
ordered indirect [asymmetrical | symmetrical] [synchronous | asynchronous]
typed [many-to-many | many-to-one] message passing
“channels”:
ordered indirect symmetrical synchronous fully-typed one-to-one message passing “(extended) rendezvous”:
ordered direct asymmetrical [synchronous | asynchronous]
fully-typed many-to-one remote invocation
Ada:
Java:
Communication & Synchronization
Message-based synchronization
Message-passing systems examples:
no message passing system defined
© 2019 Uwe R. Zimmer, The Australian National University page 356 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

ordered symmetrical asymmetrical synchronous asynchronous direct indirect
one-to-one many-to-one many-to-many
POSIX: MPI: CHILL: Occam2:

memory-blocks
message queues message passing message passing message passing remote invocation channels
Ada: Go:

Erlang:

message passing
Communication & Synchronization
Message-based synchronization
Message-passing systems examples:
contents
byte-stream
method

basic types fully typed fully typed fully typed fully typed

Java:
© 2019 Uwe R. Zimmer, The Australian National University page 357 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
no message passing system defined

concurrent entities are synchronized at these points
INT reading:
SEQ i = 0 FOR 1000
Communication & Synchronization
SEQ
— generate reading SensorChannel ! reading
INT data:
SEQ i = 0 FOR 1000
SEQ
SensorChannel ? data
— employ data
© 2019 Uwe R. Zimmer, The Australian National University
page 358 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Message-based synchronization
Message-based synchronization in Occam2
Communication is ensured by means of a ‘channel’, which:
• •
can be used by one writer and one reader process only
and is synchronous:
CHAN OF INT SensorChannel:
PAR

Essential Occam2 keywords
ALT PAR SEQ PRI
ANY CHAN OF
DATA TYPE RECORD OFFSETOF PACKED
BOOL BYTE INT REAL
CASE IF ELSE FOR FROM WHILE
FUNCTION RESULT PROC IS
PROCESSOR PROTOCOL TIMER
SKIP STOP VALOF
Concurrent, distributed, real-time programming language!
INT reading:
SEQ i = 0 FOR 1000
Communication & Synchronization
SEQ
— generate reading
SensorChannel ! reading
INT data:
SEQ i = 0 FOR 1000
SEQ
SensorChannel ? data
— employ data
© 2019 Uwe R. Zimmer, The Australian National University
page 359 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Message-based synchronization
Message-based synchronization in Occam2
Communication is ensured by means of a ‘channel’, which:
• •
can be used by one writer and one reader process only
and is synchronous:
CHAN OF INT SensorChannel:
PAR

dcl SensorBuffer buffer (32) int;
Communication & Synchronization
Message-based synchronization
Message-based synchronization in CHILL
CHILL is the ‘CCITT High Level Language’,
where CCITT is the Comité Consultatif International Télégraphique et Téléphonique.
The CHILL language development was started in 1973 and standardized in 1979.
strong support for concurrency, synchronization, and communica- tion (monitors, buffered message passing, synchronous channels)
… receive case
send SensorBuffer (reading); (SensorBuffer in data) : …
signal SensorChannel = (int) to consumertype;
…
send SensorChannel (reading)
to consumer
receive case
(SensorChannel in data): …
© 2019 Uwe R. Zimmer, The Australian National University
page 360 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
esac;
esac;

dcl SensorBuffer buffer (32) int;
Communication & Synchronization
Message-based synchronization
Message-based synchronization in CHILL
CHILL is the ‘CCITT High Level Language’,
where CCITT is the Comité Consultatif International Télégraphique et Téléphonique.
The CHILL language development was started in 1973 and standardized in 1979.
strong support for concurrency, synchronization, and communica- tion (monitors, buffered message passing, synchronous channels)
… receive case
send SensorBuffer (reading);asynchronous (SensorBuffer in data) : …
signal SensorChannel = (int) to consumertype;
…
send SensorChannel (reading)
to consumer
synchronous
receive case
(SensorChannel in data): …
© 2019 Uwe R. Zimmer, The Australian National University
page 361 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
esac;
esac;

• entry points in tasks
• full set of parameter profiles supported
Communication & Synchronization
Message-based synchronization
Message-based synchronization in Ada
Ada supports remote invocations ((extended) rendezvous) in form of:
If the local and the remote task are on different architectures, or if an intermediate communication system is employed then:
parameters incl. bounds and discriminants are ‘tunnelled’ through byte-stream-formats. Synchronization:
• Both tasks are synchronized at the beginning of the remote invocation ( ‘rendezvous’)
• The calling task if blocked until the remote routine is completed ( ‘extended rendezvous’)
© 2019 Uwe R. Zimmer, The Australian National University page 362 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

[(index)] —— waiting for synchronization —— waiting for synchronization —— waiting for synchronization —— waiting for synchronization —— synchronized
accept [(index)] ;
time
time
© 2019 Uwe R. Zimmer, The Australian National University
page 363 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Message-based synchronization
Message-based synchronization in Ada
(Rendezvous)

—— —— —— —— ——
blocked blocked blocked blocked
synchronized
time
time
© 2019 Uwe R. Zimmer, The Australian National University
page 364 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Message-based synchronization
Message-based synchronization in Ada
[(index)] —— waiting for synchronization —— waiting for synchronization —— waiting for synchronization —— waiting for synchronization ——
accept [(index)] do
return results
end ;
(Extended rendezvous)
—— remote invocation
—— remote invocation
—— remote invocation

[(index)] synchronized
time
time
© 2019 Uwe R. Zimmer, The Australian National University
page 365 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Message-based synchronization
Message-based synchronization in Ada
(Rendezvous)
accept [(index)] ;
—— waiting for synchronization
—— waiting for synchronization
—— waiting for synchronization

[(index)] synchronized
—— —— —— —— ——
blocked
blocked
blocked
blocked
—— remote invocation —— remote invocation —— remote invocation —— remote invocation
time
time
© 2019 Uwe R. Zimmer, The Australian National University
page 366 of 757 (chapter 3: “Communication & Synchronization” up to page 368)
Communication & Synchronization
Message-based synchronization
Message-based synchronization in Ada
return results
end ;
(Extended rendezvous)
accept [(index)] ;
—— waiting for synchronization
—— waiting for synchronization
—— waiting for synchronization

Communication & Synchronization
Message-based synchronization
Message-based synchronization in Ada
Some things to consider for task-entries:
• In contrast to protected-object-entries, task-entry bodies can call other blocking operations.
• Accept statements can be nested (but need to be different).
helpful e.g. to synchronize more than two tasks.
• Accept statements can have a dedicated exception handler (like any other code-block).
Exceptions, which are not handled during the rendezvous phase are propagated to all involved tasks.
• Parameters cannot be direct ‘access’ parameters, but can be access-types.
• ‘count on task-entries is defined,
but is only accessible from inside the tasks which owns the entry.
• Entry families (arrays of entries) are supported.
• Private entries (accessible for internal tasks) are supported.
© 2019 Uwe R. Zimmer, The Australian National University page 367 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Communication & Synchronization
• Guard evaluation times, nested monitor calls, deadlocks, simultaneous reading, queue management.
Summary
Communication & Synchronization
• Shared memory based synchronization • Flags, condition variables, semaphores,
conditional critical regions, monitors, protected objects.
• Synchronization and object orientation, blocking operations and re-queuing.
• Message based synchronization
• Synchronizationmodels • Addressingmodes
• Messagestructures
• Examples
© 2019 Uwe R. Zimmer, The Australian National University
page 368 of 757 (chapter 3: “Communication & Synchronization” up to page 368)

Related Posts