Concurrency: Mutual Exclusion and Synchronization

Problems with concurrent execution

An example

The critical section problem

The critical section problem

Framework for analysis of solutions

Requirements for a valid solution to the critical section problem

Requirements for a valid solution to the critical section problem

Types of solutions

Software solutions

Algorithm 1

Algorithm 2

Algorithm 3 (Peterson’s algorithm)

Algorithm 3: proof of correctness

Algorithm 3: proof of correctness (cont.)

n-process solution: bakery algorithm

The bakery algorithm (cont.)

The bakery algorithm (cont.)

Drawbacks of software solutions

Hardware solutions: interrupt disabling

Hardware solutions: special machine instructions

The test-and-set instruction

The test-and-set instruction (cont.)

Using xchg for mutual exclusion

Semaphores

Semaphores

Semaphore’s operations (atomic)

Semaphores: observations

Semaphores: observations

Using semaphores for solving critical section problems

Using semaphores to synchronize processes

The producer/consumer problem

P/C: unbounded buffer

P/C: unbounded buffer

P/C: unbounded buffer

Solution of P/C: unbounded buffer

P/C: unbounded buffer

P/C: finite circular buffer of size k

P/C: finite circular buffer of size k

Solution of P/C: finite circular buffer of size k

The Dining Philosophers Problem

The Dining Philosophers Problem

The Dining Philosophers Problem

Problems with Semaphores

Monitors

Monitor

Monitor

Condition Variables

Monitor

Producer/Consumer problem

Monitor for the bounded P/C problem

Monitor for the bounded P/C problem

Message Passing

Synchronization in message passing

Synchronization in message passing

Addressing in message passing

Mailboxes and Ports

Ownership of ports and mailboxes

Enforcing mutual exclusion with message passing

The bounded-buffer P/C problem with message passing

The bounded-buffer P/C problem with message passing