http://lass.cs.umass.edu/~shenoy/courses/fall08/schedule.html
Too much Milk What are the correctness properties for this problem? – Only one person buys milk at a time. – Someone buys milk if you need it
Solution 1: Lock->Accquire() if (noMilk) { buy milk } Lock->Release()
Solution 2: // if Semaphore is free (non-zero), it continue executing. // if Semaphore is not free, the OS puts the process on the wait queue // for the Semaphore. Semaphore_S->Wait() if (noMilk) { buy milk } // unblock one process on semaphore S's wait queue. Semaphore_S->Signal()
Condition Variable: is queue of threads waiting for something inside a critical section. C.Wait(Lock) //atomic release lock, go to sleep, when the process wakes up it re-aquires lock. C.Singal() //wait up waiting thread if one exists; otherwise do nothing. C.Broadcast(): wake up all waiting threads Rule: thread must hold the lock when doing condition var operations.
Readers/Writers
Write() write_mutex->wait() writers++; if (writers ==1) read_block->wait() write_mutex->signal()
write_block->wait() perform write write_block->signal()
write_mutex->wait() write -= 1 //done write if (writers == 0) read_block->signal() write_mutex->signal()
Read() write_pending->wait() read_block->wait()
read_mutext->wait() readers+=1 if (readers == 1) write_block->wait() read_mutext->singal()
read_block->singal() write_pending->signal()
perform read
read_mutex->wait() reader -= 1; //reader done if (readers == 0) { write_block->singal() read_mutex->singal()
Dining Philosophers Semaphore chopstick[8]; do { wait(chopstick[i]); wait(chopstick[(i+1)&7]) //eat signal(chopstick[i]); signal(chopstick[(i+1)%5]) //think } white(TRUE);