Chapter 6 OS - Synchronization

Race condition

Situation where several processes access and manipulate the same data concurrently. Outcome depends on particular order in which access takes place

Critical section

Segment of code where a process may be accessing and updating data that is shared with at least one other process

Three requirements for a solution to the critical section problem

1. Mutual exclusion - Only one process can execute in its critical section at a time

2. Progress - If no progress is in its critical section, processes not in remainder sections can decide who enters next

3. Bounded waiting - There is a limit on how many times other processes can enter their critical sections after a process request entry

Peterson’s Solution

Simple algorithm for two processes. Uses two shared variables to coordinate.

Two shared data items in Peterson’s solution

Int turn - indicates whose turn it is to enter critical section

boolean flag[2] - indicates if process is ready to enter its critical section

Peterson’s solutions does not work on modern architectures due to…

Modern processors and compilers reorder read and write operations that have no dependencies. 

Memory barrier(Memory fence)

Instruction that forces all loads and stores to be completed before any subsequent load or store operations are performed, ensuring memory modifications are visible to other processors

Test_and_set

Automatically sets boolean variable to true and returns original value, all as one uninterruptible operation

compare_and_swap

Automatically compare a value to expected value, if they match, updates it to a new value. It always returns original value.

Atomic variable

A variable that provides atomic operations on basic data types (integers,booleans) typically implemented using compare_and_swap operations

Mutex

Mutual exclusion

Two main operations of mutex lock

acquire() and release()

acquire() in mutex

Acquires the lock before entering critical section

Release() in mutex

Releases the lock when exiting critical section

What is a spinlock

A mutex lock where process “spins” or busy waits while waiting for the lock to become available, without needing a context switch

When are spin locks preferable to regular locks

On multi core systems when a lock will be held for a short duration( less than two context switches), they avoid the overhead of context switching

Lock contention

Lock contention is when a thread is blocked when trying to acquire it.

Semaphore

An integer variable accessed only through two atomic operations

Two atomic operations

1. Wait()

2. Signal()

Two types of semaphores

Binary and counting

Binary semaphores

Value ranges between 0 and 1 

Counting semaphores

Value ranges over an unrestricted domain

Wait() operation on a semaphore

Waits while S less then or = to 0( busy wait) then decrements S 

Signal() operation on semaphore

Increments the semaphore value S

Semaphores avoid busy waiting

Suspends processes that wait and places them in waiting queue, then using wakeup() to resume them when signal() is called

Monitors

An abstract data type that includes programmer defined operations with mutual exclusion within the monitor, encapsulating shared data and operations