1&6(&6(3ULQFLSOHVRI2SHUDWLQJ3ULQFLSOHVRI2SHUDWLQJ6\VWHPV6\VWHPV)DOO)DOOLecture 7: Semaphores and MonitorsLecture 7: Semaphores and MonitorsGeoffrey M. VoelkerGeoffrey M. VoelkerOctober 12, 2000 CSE 120 -- Lecture 7 – Semaphores and Monitors 2+LJKHU+LJKHU/HYHO6\QFKURQL]DWLRQ/HYHO6\QFKURQL]DWLRQ● We looked at using locks to provide mutual exclusion● Locks work, but they have some drawbacks when critical sections are long◆ Spinlocks – inefficient◆ Disabling interrupts – can miss or delay important events● Instead, we want synchronization mechanisms that◆ Block waiters◆ Leave interrupts enabled inside the critical section● Look at two common high-level mechanisms◆ Semaphores: binary (mutex) and counting◆ Monitors: mutexes and condition variables● Use them to solve common synchronization problems2October 12, 2000 CSE 120 -- Lecture 7 – Semaphores and Monitors 36HPDSKRUHV6HPDSKRUHV● 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 4%ORFNLQJLQ6HPDSKRUHV%ORFNLQJLQ6HPDSKRUHV● 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 counter3October 12, 2000 CSE 120 -- Lecture 7 – Semaphores and Monitors 56HPDSKRUH7\SHV6HPDSKRUH7\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 = NOctober 12, 2000 CSE 120 -- Lecture 7 – Semaphores and Monitors 68VLQJ6HPDSKRUHV8VLQJ6HPDSKRUHV● Use is similar to our locks, but semantics are differentstruct 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;wait(S);put_balance(account, balance);signal(S);wait(S);…signal(S);…signal(S);Threads blockIt is undefined which thread runs after a signal4October 12, 2000 CSE 120 -- Lecture 7 – Semaphores and Monitors 76HPDSKRUHVLQ1DFKRV6HPDSKRUHVLQ1DFKRV● thread_sleep() assumes interrupts are disabled◆ Note that interrupts are disabled only to enter/leave critical section● Need to be able to reference current threadwait (S) {Disable interrupts;while (S.value == 0) {enqueue(S.q, current_thread);thread_sleep(current_thread);}S.value = S.value – 1;Enable interrupts;}signal (S) {Disable interrupts;thread = dequeue(S.q);thread_start(thread);S.value = S.value + 1;Enable interrupts;}October 12, 2000 CSE 120 -- Lecture 7 – Semaphores and Monitors 88VLQJ6HPDSKRUHV8VLQJ6HPDSKRUHV● 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 Buffers5October 12, 2000 CSE 120 -- Lecture 7 – Semaphores and Monitors 95HDGHUV:ULWHUV3UREOHP5HDGHUV:ULWHUV3UREOHP● 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 readingOctober 12, 2000 CSE 120 -- Lecture 7 – Semaphores and Monitors 10// number of readersint readcount = 0;// mutual exclusion to readcountSemaphore mutex = 1;// exclusive writer or readingSemaphore w_or_r = 1;writer {wait(w_or_r); // lock out readersWrite;signal(w_or_r); // up for grabs}5HDGHUV:ULWHUV5HDGHUV:ULWHUVreader {wait(mutex); // lock readcountreadcount += 1; // one more readerif (readcount == 1)wait(w_or_r); // synch w/ writerssignal(mutex); // unlock readcountRead;wait(mutex); // lock readcountreadcount -= 1; // one less readerif (readcount == 0)signal(w_or_r); // up for grabssignal(mutex); // unlock readcount}}6October 12, 2000 CSE 120 -- Lecture 7 – Semaphores and Monitors 115HDGHUV:ULWHUV1RWHV5HDGHUV:ULWHUV1RWHV● If there is a writer◆ First reader blocks on w_or_r◆ All other readers block on mutex● Once a writer exits, all readers can fall through◆ Which reader gets to go first?● The last reader to exit signals a waiting writer◆ If no writer, then readers can continue● If readers and writers are waiting on w_or_r, and a writer exits, who goes first?◆ Again, depends on scheduler● Why doesn’t a writer need to use mutex?October 12, 2000 CSE 120 -- Lecture 7 – Semaphores and Monitors 12%RXQGHG%XIIHU%RXQGHG%XIIHU● Problem: There is a set of resource buffers shared by producer and consumer threads● Producer inserts resources into the buffer set◆ Output, disk blocks, memory pages, processes, etc.● Consumer removes resources from the buffer set◆ 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 handoff7October 12,
View Full Document
Unlocking...