6 3ULQFLSOHV RI 2SHUDWLQJ 6 VWHPV DOO Lecture 7 Semaphores and Monitors Geoffrey M Voelker LJKHU HYHO 6 QFKURQL DWLRQ We looked at using locks to provide mutual exclusion Locks work but they have some drawbacks when critical sections are long Instead we want synchronization mechanisms that Block waiters Leave interrupts enabled inside the critical section Look at two common high level mechanisms Spinlocks inefficient Disabling interrupts can miss or delay important events Semaphores binary mutex and counting Monitors mutexes and condition variables Use them to solve common synchronization problems October 12 2000 CSE 120 Lecture 7 Semaphores and Monitors 2 1 6HPDSKRUHV Semaphores are another data structures that provides mutual exclusion to critical sections Block waiters interrupts enabled within CS Described by Dijkstra in THE system in 1968 Semaphores can also be used as atomic counters more later Semaphores support two operations wait semaphore decrement block until semaphore is open Also P after the Dutch word for test or down signal semaphore increment allow another thread to enter Also V after the Dutch word for increment or up October 12 2000 CSE 120 Lecture 7 Semaphores and Monitors 3 ORFNLQJ LQ 6HPDSKRUHV Associated with each semaphore is a queue of waiting processes When wait is called by a thread If semaphore is open thread continues If semaphore is closed thread blocks on queue signal opens the semaphore If a thread is waiting on the queue the thread is unblocked If no threads are waiting on the queue the signal is remembered for the next thread In other words signal has history This history is a counter October 12 2000 CSE 120 Lecture 7 Semaphores and Monitors 4 2 6HPDSKRUH 7 SHV Semaphores come in two types Mutex semaphore Represents single access to an resource Guarantees mutual exclusion to a critical section Counting semaphore Represents a resource with many units available or a resource that allows certain kinds of unsynchronized concurrent access e g reading Multiple threads can pass the semaphore Number of threads determine by the semaphore count mutex has count 1 counting has count N October 12 2000 CSE 120 Lecture 7 Semaphores and Monitors 5 8VLQJ 6HPDSKRUHV Use is similar to our locks but semantics are different struct Semaphore int value Queue q S withdraw account amount wait S balance get balance account balance balance amount put balance account balance signal S return balance wait S balance get balance account balance balance amount Threads block It is undefined which thread runs after a signal October 12 2000 wait S wait S put balance account balance signal S signal S signal S CSE 120 Lecture 7 Semaphores and Monitors 6 3 6HPDSKRUHV LQ 1DFKRV wait S Disable interrupts while S value 0 enqueue S q current thread thread sleep current thread S value S value 1 Enable interrupts thread sleep assumes interrupts are disabled signal S Disable interrupts thread dequeue S q thread start thread S value S value 1 Enable interrupts Note that interrupts are disabled only to enter leave critical section Need to be able to reference current thread October 12 2000 CSE 120 Lecture 7 Semaphores and Monitors 7 8VLQJ 6HPDSKRUHV We ve looked at a simple example for using synchronization Mutual exclusion while accessing a bank account Now we re going to use semaphores to look at more interesting examples Readers Writers Bounded Buffers October 12 2000 CSE 120 Lecture 7 Semaphores and Monitors 8 4 5HDGHUV ULWHUV 3UREOHP Readers Writers Problem An object is shared among several threads Some threads only read the object others only write it We can allow multiple readers But only one writer How can we use semaphores to control access to the object to implement this protocol Use three variables int readcount number of threads reading object Semaphore mutex control access to readcount Semaphore w or r exclusive writing or reading October 12 2000 CSE 120 Lecture 7 Semaphores and Monitors 9 5HDGHUV ULWHUV number of readers int readcount 0 mutual exclusion to readcount Semaphore mutex 1 exclusive writer or reading Semaphore w or r 1 writer wait w or r lock out readers Write signal w or r up for grabs October 12 2000 reader wait mutex lock readcount readcount 1 one more reader if readcount 1 wait w or r synch w writers signal mutex unlock readcount Read wait mutex lock readcount readcount 1 one less reader if readcount 0 signal w or r up for grabs signal mutex unlock readcount CSE 120 Lecture 7 Semaphores and Monitors 10 5 5HDGHUV ULWHUV 1RWHV If there is a writer Once a writer exits all readers can fall through If no writer then readers can continue If readers and writers are waiting on w or r and a writer exits who goes first Which reader gets to go first The last reader to exit signals a waiting writer First reader blocks on w or r All other readers block on mutex Again depends on scheduler Why doesn t a writer need to use mutex October 12 2000 CSE 120 Lecture 7 Semaphores and Monitors 11 RXQGHG XIIHU Problem There is a set of resource buffers shared by producer and consumer threads Producer inserts resources into the buffer set Consumer removes resources from the buffer set Output disk blocks memory pages processes etc Whatever is generated by the producer Producer and consumer execute at different rates No serialization of one behind the other Tasks are independent easier to think about The buffer set allows each to run without explicit handoff October 12 2000 CSE 120 Lecture 7 Semaphores and Monitors 12 6 RXQGHG XIIHU Use three semaphores Mutex mutual exclusion to shared set of buffers Binary semaphore Empty count of empty buffers Full count of full buffers Counting semaphore Counting semaphore October 12 2000 CSE 120 Lecture 7 Semaphores and Monitors 13 RXQGHG XIIHU Semaphore mutex 1 mutual exclusion to shared set of buffers Semaphore empty N count of empty buffers all empty to start Semaphore full 0 count of full buffers none full to start producer while 1 Produce new resource wait empty wait for empty buffer wait mutex lock buffer list Add resource to an empty buffer signal mutex unlock buffer list signal full note a full buffer October 12 2000 consumer while 1 wait full wait for a full buffer wait mutex lock buffer list Remove resource from a full buffer signal mutex unlock buffer list signal empty note an empty buffer Consume resource CSE 120 Lecture 7 Semaphores and Monitors 14 7 6HPDSKRUH 6XPPDU Semaphores can be used to solve any of the traditional synchronization
View Full Document
Unlocking...