COMP2310 - Week 5 - Distributed Synchronisation

Synchronisation Methods

• Semaphores -> C, POSIX
• Conditional critical regions -> Edison
  • Synchronisation based on values of various conditions (booleans)
• Monitors -> Modula-1, Mesa
• Mutexes & conditional variables -> POXIX
  • Locks
• Synchronised methods -> Java
• Protected objects -> Ada
• Atomic blocks -> Chapel, X10

Message-based Synchronisation

• Asynchronous -> Message is simply sent, sender had reached a particular point
• Synchronous -> Neither sender or reciever can proceed until both have been "synchronised" together
• Remote procedure calls -> Called object

Side Effects

Operations make no changes, calling it repeatedly/multiple times will return the same result -> No side effects

Side effecting operations allow for changing the outside world

• Locally

  • Visible to the task/process

• Outside

  • Access to updated variables (requires synchronisation)

• Examples

  • Handling 64-bit integer on 8 or 16-bit controller
  • Schedulers may interrupt threads irrespective of shared data

Condition Synchronisation by Flags

Assume word-access atomicity

A set of processes agree on a (word-size) atomic variable as a flag to indicate synchronisation conditional

• Each process is sequential, A happens before B

Semaphores

• Atomic operation $P$ on $S$ - passeren (Dutch for 'pass')

P(S): [when S > 0 then S := S - 1] --blocking operation

Also known as 'wait', 'suspend_until_true','sem_wait'

• Atomic operation $V$ on $S$ - vrijgeven (Dutch for 'to release')

V(S): [S := S + 1]

Also known as 'signal','set_true','sem_post'

Drawbacks

• Not bound to any resource or method or region

  • Compiler has no idea what is supposed to be protected by a semaphore

• Semaphores could be scattered all over

• Inadequate for non-trivial systems

Conditional Critical Regions

• Set of associated code sections in different processes

  • Guaranteed execution under mutual exclusion
    • Processes prevented from entering if another process is active
    • Shared data structures group in named regions

• Condition synchronisation not provided by guards

• No access order can be assumed -> potential livelock

Benefits and Drawbacks

• Association between data nad synchronisation primitives is visible to compiler and runtime
• All guards must be re-evaluated when exiting any CCR
  • No order in re-evaluation phase
• CCRs can also be distrubuted throughout code -> Spaghetti code