Designing Parallel Algorithms (Synchronization)
What we already know..
Synchronization
Accessing a shared Data
The Critical Section Problem
Solving The CS Problem
Critical Sections & Locks
Observations
Locking Mechanisms
Critical Sections Using Spin Locks
Implementing Spin Locks
Implementing a spin Locks
Implementing a spin Locks
Drawback of the Simple Test-and-Set Lock
Test&Set Lock with Backoff
Test-Test&Set Lock
Performance of Test-and-Set Locks
Queuing Locks versus Spin Locks
The Ticket Algorithm
Critical Sections Using the TicketAlgorithm
Implementing the Ticket Lock
The Bakery Algorithm
Implementation of The Bakery Algorithm

Queuing Locks versus Spin Locks
Spin locks are efficient (low latency and memory demand)
When a lock becomes free, spinning processes rush to grab the lock in an arbitrary order; one succeeds, others fail and spin again.
The same process can grab the lock again.
Queuing locks provide fair solution to the CS problem
Waiting processes are queued on the lock;
Released lock is passed to the proc in the head of the queue;
Examples : ticket, bakery algorithms.