MTH 4355 Semaphores

semaphore

a synchronization primitive that acts as both a lock and condition variable

semaphore code

sem_init(pointer to semaphore object, shared between threads, condition variable)

sem_wait(semaphore s)

decrements the condition variable

if negative, puts thread to sleep

sem_signal(semaphore s)

increments the condition variable by 1

and wakes up a thread if any waiting

Reader/Writer Locks

single writer, multiple readers

Assume first thread is writer

Can only write when no readers in critical section

(lock for updating reader count, and lock for writing)

Dining philosipher

to avoid circle wait, have one thread grab a lock in a different order than the rest

atomicity violation

two threads access a shared variable at the same time

atomicity violation solution

add a lock

order violation

T2 assume T1 has created something T2 requires, but T1 did not create yet

order violation solution

add condition variables

encapsulation

why deadlock occurs most often

mutual exclusion, hold-and-wait, no preemption, circular wait

4 conditions required for a dead lock

prevent circular wait

give a total ordering for grabbing locks

prevent hold-and-wait

add more locks and make sure you obtain all locks at once

prevent no preemption

trylock

livelock

awkward moment when you trylock but its released after they tried, so another thread grabs lock

can add random delay to fix

prevent mutual exclusion

use hardware no lock method

deadlock prevention via scheduling

include meta data about locks, and schedule in a way that no deadlock can occur

deadlock prevention with detector

detect a deadlock, reboot OR break lock cycles(but loose some data in process)

no preemption

resources cannot be forcibly removed from threads holding them

hold-and-wait

thread holds onto resources while waiting for additional resources