Module 3: Interprocess Communications

Synchronization Criteria

Safety

• Data and process states must stay consistent as processes access data

• Failure → Invalid application states or corrupted data

Liveness

• All processes will eventually complete

• Failure → deadlock or starvation (at least 1 process waits forever)

• Deadlock: all processes block, with each process waiting on the next

Synchronized Code Patterns

Example: multiple squares → image formation

General Model:

• Initialization - create threads needed for task (pre-init & post-init)

• Update - threads execute tasks that share resources (general_update & post_update)

• Shutdown - terminate threads post job (pre_shutdown & post_shutdown procedures)

Approaches to synchronization

• Busy Waiting

• Shadow Copies

• Barrier Synchronization

• Monitors

• Message Passing

• Mutexes & Semaphores

Shadow Copies (Copy-On-Write)

• Necessary when one process is writing to a shared structure and other processes are reading

• Ex) Writing process preempted before finishing

• While writer is writing, other processes read OLD version

• After finished → new reads read new data, old reads finish reading old data

Shadow Copy Steps

1) Make OG data read only w/ read-only lock

2) Make copy of OG data

3) Update copy with new info

4) Change pointer to new copy

5) Delete/release old data once all readers are done

Barriers

• Require all processes to reach a specified point before continuing

• ALL must reach barrier before moving on

• Implemented using flags and control structures that pause processes when others are not ready

• Embedded in programming languages sometimes

NOT FREQUENTLY USED

Monitors

• require language support

• not based on shared memory to lock

• use conditional variables provided by programming language

• Yield the CPU: if process tries to acquire monitor lock and fails, it leaves CPU and blocks

VERY COMMON

Python Implementation (explicit): conditional var must define a critical region with cv.wait() and cv.notify(), anything in between can only be accessed by single process/thread at a time

• cv.wait(): process indicating lock

• cv.notify(): return lock and notify others it is free

Java Implementation (implicit): can only set entire procedures as critical regions, use “synchronized” in the function definition, Java ensures only one process/thread enters at a time

Monitors Continued…

• Language Construct that use conditional variables

• CVs handle blocking/unblocking critical regions

• At most 1 process/thread in a CR at a time

Mutexes (Mutual Exclusion Variables) and Semaphores

• Shared-memory variables

• Provided by OS, implement blocking-based locking mechanism: a process that tries to acquire the lock but can’t will block itself

Mutexes (Single Lock: 0 or 1)

• Mutex is binary in nature: lock/unlock operations only

• Once locked, only locking thread can unlock mutex

• Intended for single-process-at-a-time critical regions

• Single lock protects a single resource

Semaphore (Array of Locks, Counter)

• Creation: initialized with the # of locks available

• Acquiring Lock → down

• Releasing Lock → up

• A binary semaphore is similar to mutex but can be unlocked/locked by any thread/process with access to the semaphore

Semaphores: How Do They Work?

Creation

• Have a starting count = number of locks there are = number of resources accessed concurrently by different processes