(5) Synchronization

Question 1

What are ‘Critical sections’?

Answer 1

Sequences of instructions that may get incorrect results if executed simultaneously

Question 2

When do Critical Sections arise?

Answer 2

Read-modify-write pattern. Two threads trying to access a global/heap allocated variable (not local/stack).

Question 3

What is a race condition?

Answer 3

If the result of the program executing depends on the timing, i.e it is non-deterministic.

Question 4

What are the requirements for a correct critical section?

Answer 4

Mutual exclusion
(at most one thread in the critical section)

Progress
(If T outside critical section then T can’t prevent S from entering it)

Bounded Waiting
(If T is waiting for critical section it will eventually enter it)

Performance
(The overhead of entering and exiting is small)

Question 5

How do we implement Mutual Exclusion?

Answer 5

Via hardware - special machine instructions
Via OS support - primitives via syscall
Via Software - entirely by user code

Question 6

Give Peterson’s Algorithm

Answer 6

(Let ˆı mean 1-i)
flag[i] = true;
turn = ˆı;
while ( flag[ˆı] && turn == ˆı ){}
/* critical section */
flag[i] = false;

Question 7

What are the different mechanisms for building critical sections?

Answer 7

Spinlocks
Semaphores
Monitors
Messages

Question 8

What is a lock?

Answer 8

A memory object with two operations:
Acquire(): obtain right to enter CritSec
Release(): Give up right to be in CritSec

Acquire() prevents progress of thread until lock can be acquired.

Question 9

How do we implement spinlocks?

Answer 9

‘Busy wait’ / spin in the acquire method until the lock is released. When a thread loops waiting for a mutex it is called a Spinlock. Acquire/release must be ATOMIC (executes as though it could not be interrupted)