1CSE 120CSE 120Principles of Operating Principles of Operating SystemsSystemsFall 2004Fall 2004Lecture 7: Semaphores and MonitorsLecture 7: Semaphores and MonitorsGeoffrey M. VoelkerGeoffrey M. VoelkerOctober 12, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 2© 2004 Geoffrey M. VoelkerAnnouncementsAnnouncementsz UCSD CSE Programming Contest Saturday 10/16 Why should you go? To be like John Rapp:http://www.cse.ucsd.edu/users/calder/UCSDProgramContest/2October 12, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 3© 2004 Geoffrey M. VoelkerAnnouncementsAnnouncementsz Homework #2 outz Next week I’ll be in Beijing No class on Tuesday 10/19 – work on project! Prof. Keith Marzullo will give the lecture on 10/21z Email question Why not have an idle thread in Nachos? [hint: a purely pragmatic reason]z Any questions on the project?October 12, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 4© 2004 Geoffrey M. VoelkerHigherHigher--Level SynchronizationLevel Synchronizationz We looked at using locks to provide mutual exclusionz Locks work, but they have some drawbacks when critical sections are long Spinlocks – inefficient Disabling interrupts – can miss or delay important eventsz Instead, we want synchronization mechanisms that Block waiters Leave interrupts enabled inside the critical sectionz Look at two common high-level mechanisms Semaphores: binary (mutex) and counting Monitors: mutexes and condition variablesz Use them to solve common synchronization problems3October 12, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 5© 2004 Geoffrey M. VoelkerSemaphoresSemaphoresz Semaphores are another data structure that provides mutual exclusion to critical sections Block waiters, interrupts enabled within CS Described by Dijkstra in THE system in 1968z Semaphores can also be used as atomic counters More laterz 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, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 6© 2004 Geoffrey M. VoelkerBlocking in SemaphoresBlocking in Semaphoresz Associated with each semaphore is a queue of waiting processesz When wait() is called by a thread: If semaphore is open, thread continues If semaphore is closed, thread blocks on queuez Then 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” (c.f. condition vars later)» This “history” is a counter4October 12, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 7© 2004 Geoffrey M. VoelkerSemaphore TypesSemaphore Typesz Semaphores come in two typesz Mutex semaphore Represents single access to a resource Guarantees mutual exclusion to a critical sectionz 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 determined by the semaphore “count”» mutex has count = 1, counting has count = NOctober 12, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 8© 2004 Geoffrey M. VoelkerUsing SemaphoresUsing Semaphoresz 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 signal5October 12, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 9© 2004 Geoffrey M. VoelkerSemaphores in NachosSemaphores in Nachosz thread_sleep() assumes interrupts are disabled Note that interrupts are disabled only to enter/leave critical section How can it sleep with interrupts disabled?z 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, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 10© 2004 Geoffrey M. VoelkerUsing SemaphoresUsing Semaphoresz We’ve looked at a simple example for using synchronization Mutual exclusion while accessing a bank accountz Now we’re going to use semaphores to look at more interesting examples Readers/Writers Bounded Buffers6October 12, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 11© 2004 Geoffrey M. VoelkerReaders/Writers ProblemReaders/Writers Problemz 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 writerz How can we use semaphores to control access to the object to implement this protocol?z 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, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 12© 2004 Geoffrey M. Voelker// 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}Readers/WritersReaders/Writersreader {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}}7October 12, 2004 CSE 120 – Lecture 7 – Semaphores and Monitors 13© 2004 Geoffrey M. VoelkerReaders/Writers NotesReaders/Writers Notesz If there is a writer First reader blocks on w_or_r All other readers block on mutexz Once a writer exits, all readers can fall
View Full Document
Unlocking...