DOC PREVIEW
Berkeley COMPSCI 162 - Mutual Exclusion, Semaphores, Monitors, and Condition Variables

This preview shows page 1-2-15-16-31-32 out of 32 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 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 32 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 32 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 32 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 32 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 32 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS162 Operating Systems and Systems Programming Lecture 7 Mutual Exclusion, Semaphores, Monitors, and Condition VariablesReview: A Concurrent Program ExampleReview: Hand Simulating Multiprocessor ExampleReview: Too Much Milk Solution #3Goals for TodayHigh-Level PictureWhere are we going with synchronization?How to implement Locks?Naïve use of Interrupt Enable/DisableBetter Implementation of Locks by Disabling InterruptsNew Lock Implementation: DiscussionInterrupt re-enable in going to sleepAdministriviaHow to Re-enable After Sleep()?Interrupt disable and enable across context switchesAtomic Read-Modify-Write instructionsExamples of Read-Modify-WriteImplementing Locks with test&setProblem: Busy-Waiting for LockBetter Locks using test&setHigher-level Primitives than LocksSemaphoresSemaphores Like Integers ExceptTwo Uses of SemaphoresProducer-consumer with a bounded bufferCorrectness constraints for solutionFull Solution to Bounded BufferDiscussion about SolutionMotivation for Monitors and Condition VariablesMonitor with Condition VariablesSimple Monitor ExampleSummaryCS162Operating Systems andSystems ProgrammingLecture 7Mutual Exclusion, Semaphores, Monitors, and Condition VariablesSeptember 21, 2005Prof. John Kubiatowiczhttp://inst.eecs.berkeley.edu/~cs162Lec 7.29/21/05 Kubiatowicz CS162 ©UCB Fall 2005Review: A Concurrent Program Example•Two threads, A and B, compete with each other–One tries to increment a shared counter–The other tries to decrement the counterThread A Thread Bi = 0; i = 0;while (i < 10)while (i > -10) i = i + 1; i = i – 1;printf(“A wins!”); printf(“B wins!”);•Assume that memory loads and stores are atomic, but incrementing and decrementing are not atomic •Who wins? Could be either•Is it guaranteed that someone wins? Why or why not?•What it both threads have their own CPU running at same speed? Is it guaranteed that it goes on forever?Lec 7.39/21/05 Kubiatowicz CS162 ©UCB Fall 2005Review: Hand Simulating Multiprocessor Example•Inner loop looks like this:Thread AThread Br1=0 load r1, M[i]r1=0 load r1, M[i]r1=1 add r1, r1, 1r1=-1 sub r1, r1, 1M[i]=1 store r1, M[i]M[i]=-1 store r1, M[i]•Hand Simulation:–And we’re off. A gets off to an early start–B says “hmph, better go fast” and tries really hard–A goes ahead and writes “1”–B goes and writes “-1”–A says “HUH??? I could have sworn I put a 1 there”•Could this happen on a uniprocessor?–Yes! Unlikely, but if you depending on it not happening, it will and your system will break…Lec 7.49/21/05 Kubiatowicz CS162 ©UCB Fall 2005Review: Too Much Milk Solution #3•Here is a possible two-note solution:Thread A Thread Bleave note A; leave note B;while (note B) { if (noNote A) { do nothing; if (noMilk) {} buy milk;if (noMilk) { } buy milk; }} remove note B;remove note A;•Does this work? Yes. Both can guarantee that: –It is safe to buy, or–Other will buy, ok to quit•At A: –if no note B, safe for A to buy, –otherwise wait to find out what will happen•At B: –if no note A, safe for B to buy–Otherwise, A is either buying or waiting for B to quitLec 7.59/21/05 Kubiatowicz CS162 ©UCB Fall 2005Goals for Today•Hardware Support for Synchronization•Higher-level Synchronization Abstractions–Semaphores, monitors, and condition variables•Programming paradigms for concurrent programsNote: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and GagneLec 7.69/21/05 Kubiatowicz CS162 ©UCB Fall 2005High-Level Picture•The abstraction of threads is good:–Maintains sequential execution model –Allows simple parallelism to overlap I/O and computation•Unfortunately, still too complicated to access state shared between threads –Consider “too much milk” example–Implementing a concurrent program with only loads and stores would be tricky and error-prone•Today, we’ll implement higher-level operations on top of atomic operations provided by hardware–Develop a “synchronization toolbox”–Explore some common programming paradigmsLec 7.79/21/05 Kubiatowicz CS162 ©UCB Fall 2005Where are we going with synchronization?•We are going to implement various higher-level synchronization primitives using atomic operations–Everything is pretty painful if only atomic primitives are load and store–Need to provide primitives useful at user-levelLoad/Store Disable Ints Test&Set Comp&SwapLocks Semaphores Monitors Send/ReceiveShared ProgramsHardwareHigher-level APIProgramsLec 7.89/21/05 Kubiatowicz CS162 ©UCB Fall 2005How to implement Locks?•Lock: prevents someone from doing something–Lock before entering critical section and before accessing shared data–Unlock when leaving, after accessing shared data–Wait if locked»Important idea: all synchronization involves waiting•Atomic Load/Store: get solution like Milk #3–Looked at this last lecture–Pretty complex and error prone•Hardware Lock instruction–Is this a good idea?–Complexity?»Done in the Intel 432. »Each feature makes hardware more complex and slow–What about putting task to sleep?»How do you handle the interface between the hardware and scheduler?Lec 7.99/21/05 Kubiatowicz CS162 ©UCB Fall 2005•How can we build multi-instruction atomic operations?–Recall: dispatcher gets control in two ways. »Internal: Thread does something to relinquish the CPU»External: Interrupts cause dispatcher to take CPU–On a uniprocessor, can avoid context-switching by:»Avoiding internal events (although virtual memory tricky)»Preventing external events by disabling interrupts•Consequently, naïve Implementation of locks:LockAcquire { disable Ints; }LockRelease { enable Ints; }•Problems with this approach:–Can’t let user do this! Consider following:LockAcquire();While(TRUE) {;}–Real-Time system—no guarantees on timing! »Critical Sections might be arbitrarily long–What happens with I/O or other important events?»“Reactor about to meltdown. Help?”Naïve use of Interrupt Enable/DisableLec 7.109/21/05 Kubiatowicz CS162 ©UCB Fall 2005Better Implementation of Locks by Disabling Interrupts•Key idea: maintain a lock variable and impose mutual exclusion only during operations on that variableint value = FREE;Acquire() {disable interrupts;if (value == BUSY) {put thread on wait queue;Go to sleep();// Enable interrupts?} else {value = BUSY;}enable interrupts;}Release() {disable interrupts;if


View Full Document

Berkeley COMPSCI 162 - Mutual Exclusion, Semaphores, Monitors, and Condition Variables

Documents in this Course
Lecture 1

Lecture 1

12 pages

Nachos

Nachos

41 pages

Security

Security

39 pages

Load more
Download Mutual Exclusion, Semaphores, Monitors, and Condition Variables
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 Mutual Exclusion, Semaphores, Monitors, and Condition Variables 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 Mutual Exclusion, Semaphores, Monitors, and Condition Variables 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?