DOC PREVIEW
UCSD CSE 120 - Semaphores and Monitors

This preview shows page 1-2-17-18-19-35-36 out of 36 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSE 120 Principles of Operating Systems Spring 2009Higher-Level SynchronizationSemaphoresBlocking in SemaphoresSemaphore TypesUsing SemaphoresSemaphores in NachosUsing SemaphoresReaders/Writers ProblemReaders/WritersReaders/Writers NotesBounded BufferBounded Buffer (2)Bounded Buffer (3)Bounded Buffer (4)Semaphore QuestionsSemaphore SummaryMonitorsMonitor SemanticsAccount ExampleMonitors, Monitor Invariants and Condition VariablesCondition VariablesMonitor Bounded BufferMonitor QueuesCondition Vars != SemaphoresSignal SemanticsHoare vs. Mesa MonitorsMonitor Readers and WritersMonitor Readers and WritersMonitor Readers and WritersMonitor Readers and WritersCondition Vars & LocksUsing Cond Vars & LocksMonitors and JavaSummaryNext time…Slide Number 37AnnouncementsElection monitorElection monitorCounting Semaphores with Mutex SemaphoresHow not to do itCSE 120Principles of Operating SystemsSpring 2009Lecture 6: Semaphores and MonitorsGeoffrey M. VoelkerApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 2Higher-Level Synchronization 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 problemsApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 3Semaphores Semaphores are an abstract data type that provide 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 are integers that 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() That's it! No other operations – not even just reading its value – exist Semaphore safety property: the semaphore value is always greater than or equal to 0April 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 4Blocking in Semaphores 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 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 counterApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 5Semaphore Types Semaphores come in two types Mutex semaphore (or binary semaphore) Represents single access to a resource Guarantees mutual exclusion to a critical section Counting semaphore (or general 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 = NApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 6Using Semaphores 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 signalcritical section thread_sleep() assumes interrupts are disabled Note that interrupts are disabled only to enter/leave critical section How can it sleep with interrupts disabled? Need to be able to reference current thread What happens if “while (value !=0)” is an “if (value != 0)”?April 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 7Semaphores in Nachoswait (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;}April 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 8Using Semaphores 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 BuffersApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 9Readers/Writers Problem 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» Let #r be the number of readers, #w be the number of writers» Safety: (#r ≥ 0) ∧ (0 ≤ #w ≤ 1) ∧ ((#r > 0) ⇒ (#w = 0)) 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 readingApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 10// number of readersint readcount = 0;// mutual exclusion to readcountSemaphore mutex = 1;// exclusive writer or readerSemaphore w_or_r = 1;writer {wait(w_or_r); // lock out readersWrite;signal(w_or_r); // up for grabs}Readers/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}} w_or_r provides mutex between readers and writers writer wait/signal, reader wait/signal when readcount goes from 0 to 1 or from 1


View Full Document

UCSD CSE 120 - Semaphores and Monitors

Documents in this Course
Threads

Threads

14 pages

Deadlocks

Deadlocks

19 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Processes

Processes

18 pages

Threads

Threads

29 pages

Security

Security

16 pages

Paging

Paging

13 pages

Processes

Processes

32 pages

Lecture 2

Lecture 2

13 pages

Paging

Paging

8 pages

Threads

Threads

14 pages

Paging

Paging

13 pages

Paging

Paging

26 pages

Paging

Paging

13 pages

Lecture

Lecture

13 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Security

Security

17 pages

Threads

Threads

15 pages

Processes

Processes

34 pages

Structure

Structure

10 pages

Lecture 3

Lecture 3

13 pages

Lecture 1

Lecture 1

28 pages

Threads

Threads

15 pages

Paging

Paging

30 pages

Load more
Download Semaphores and Monitors
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Semaphores and Monitors and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Semaphores and Monitors 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?