CS162 Operating Systems and Systems Programming Midterm Review March 7 2011 Ion Stoica http inst eecs berkeley edu cs162 Synchronization Critical section 3 7 Ion Stoica CS162 UCB Spring 2011 Midterm Review 2 Definitions Synchronization using atomic operations to ensure cooperation between threads Mutual Exclusion ensuring that only one thread does a particular thing at a time One thread excludes the other while doing its task Critical Section piece of code that only one thread can execute at once Critical section is the result of mutual exclusion Critical section and mutual exclusion are two ways of describing the same thing 3 7 Ion Stoica CS162 UCB Spring 2011 Midterm Review 3 Locks using interrupts Key idea maintain a lock variable and impose mutual exclusion only during operations on that variable int value FREE Acquire Release disable interrupts disable interrupts if value BUSY if anyone on wait queue take thread off wait queue put thread on wait queue Place on ready queue Go to sleep else Enable interrupts value FREE else value BUSY enable interrupts enable interrupts 3 7 Ion Stoica CS162 UCB Spring 2011 Midterm Review 4 Better locks using test set test set address most architectures result M address M address 1 return result int guard 0 int value FREE Acquire Release Short busy wait time Short busy wait time while test set guard while test set guard if anyone on wait queue if value BUSY take thread off wait queue put thread on wait queue Place on ready queue go to sleep guard 0 else else value FREE value BUSY guard 0 guard 0 3 7 Ion Stoica CS162 UCB Spring 2011 Midterm Review 5 Semaphores Semaphores are a kind of generalized lock First defined by Dijkstra in late 60s Main synchronization primitive used in original UNIX Definition a Semaphore has a non negative integer value and supports the following two operations P an atomic operation that waits for semaphore to become positive then decrements it by 1 Think of this as the wait operation V an atomic operation that increments the semaphore by 1 waking up a waiting P if any This of this as the signal operation Note that P stands for proberen to test and V stands for verhogen to increment in Dutch 3 7 Ion Stoica CS162 UCB Spring 2011 Midterm Review 6 Semaphores Like Integers Except Semaphores are like integers except No negative values Only operations allowed are P and V can t read or write value except to set it initially Operations must be atomic Two P s together can t decrement value below zero Similarly thread going to sleep in P won t miss wakeup from V even if they both happen at same time Semaphore from railway analogy Here is a semaphore initialized to 2 for resource control Value 2 Value 0 Value 1 3 7 Ion Stoica CS162 UCB Spring 2011 Midterm Review 7 Condition Variables Condition Variable a queue of threads waiting for something inside a critical section Key idea allow sleeping inside critical section by atomically releasing lock at time we go to sleep Contrast to semaphores Can t wait inside critical section Operations Wait lock Atomically release lock and go to sleep Reacquire lock later before returning Signal Wake up one waiter if any Broadcast Wake up all waiters Rule Must hold lock when doing condition variable ops 3 7 Ion Stoica CS162 UCB Spring 2011 Midterm Review 8 Complete Monitor Example with condition variable Here is an infinite synchronized queue Lock lock Condition dataready Queue queue AddToQueue item lock Acquire queue enqueue item dataready signal lock Release 3 7 Get Lock Add item Signal any waiters Release Lock RemoveFromQueue lock Acquire Get Lock while queue isEmpty dataready wait lock If nothing sleep item queue dequeue Get next item lock Release Release Lock return item Ion Stoica CS162 UCB Spring 2011 Midterm Review 9 Mesa vs Hoare monitors Need to be careful about precise definition of signal and wait Consider a piece of our dequeue code while queue isEmpty dataready wait lock If nothing sleep item queue dequeue Get next item Why didn t we do this if queue isEmpty dataready wait lock If nothing sleep item queue dequeue Get next item Answer depends on the type of scheduling Hoare style most textbooks Signaler gives lock CPU to waiter waiter runs immediately Waiter gives up lock processor back to signaler when it exits critical section or if it waits again Mesa style most real operating systems 3 7 Signaler keeps lock and processor Waiter placed on ready queue with no special priority to check Practically need Ion Stoica CS162 condition UCB Spring again 2011 after wait Midterm Review 10 Read Writer Revisited Writer Reader check into system check into system lock Acquire lock Acquire AW AR 0 while AW WW 0 while WW WR okToWrite wait lock okToRead wait lock WW WR AW lock release AR lock release read write access What if we AccessDbase ReadWrite read only remove access this AccessDbase ReadOnly check out of system line lock Acquire AW check out of system if WW 0 lock Acquire okToWrite signal else if WR 0 AR okToRead broadcast if AR 0 WW 0 okToWrite signal lock Release lock Release 3 7 Ion Stoica CS162 UCB Spring 2011 Midterm Review 11 Read Writer Revisited Writer Reader check into system check into system lock Acquire lock Acquire AW AR 0 while AW WW 0 while WW WR okToWrite wait lock okToRead wait lock WW WR AW lock release AR lock release read write access AccessDbase ReadWrite read only What access if we AccessDbase ReadOnly check out of system turn signal to lock Acquire AW check out broadcast of system if WW 0 lock Acquire okToWrite signal else if WR 0 AR okToRead broadcast if AR 0 WW 0 okToWrite broadcast lock Release lock Release 3 7 Ion Stoica CS162 UCB Spring 2011 Midterm Review 12 Read Writer Revisited Writer Reader check into system check into system lock Acquire lock Acquire AW AR 0 while AW WW 0 while WW WR okContinue wait lock okContinue wait lock WW WR AW lock release AR lock release read write access AccessDbase ReadWrite read only access AccessDbase ReadOnly check out of system lock Acquire AW check out of system if WW 0 lock Acquire okToWrite signal else if WR 0 AR okContinue broadcast if AR 0 WW 0 okContinue signal lock Release lock Release 3 7 What if we turn okToWrite and okToRead into okContinue Ion Stoica CS162 UCB Spring 2011 Midterm Review 13 Read Writer Revisited Writer Reader check into system check into system lock Acquire lock Acquire AW AR 0 while AW WW 0 while WW WR okContinue wait lock okContinue wait lock WW WR AW lock release AR lock release read write access
View Full Document
Unlocking...