DOC PREVIEW
Berkeley COMPSCI 162 - Midterm Review

This preview shows page 1-2-3-23-24-25-26-46-47-48 out of 48 pages.

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

Unformatted text preview:

CS162 Operating Systems and Systems Programming Midterm ReviewSynchronization, Critical sectionDefinitionsLocks: using interruptsBetter locks: using test&setSemaphoresSemaphores Like Integers ExceptCondition VariablesComplete Monitor Example (with condition variable)Mesa vs. Hoare monitorsRead/Writer RevisitedSlide 12Slide 13Slide 14Slide 15DeadlockFour requirements for DeadlockResource Allocation Graph ExamplesDeadlock Detection AlgorithmBanker’s Algorithm for Preventing DeadlockMemory Multiplexing, Address TranslationImportant Aspects of Memory MultiplexingWhy Address Translation?Addr. Translation: Segmentation vs. PagingReview: Address SegmentationSlide 26Slide 27Review: PagingSlide 29Slide 30Review: Two-Level PagingSlide 32Review: Inverted TableAddress Translation ComparisonCaches, TLBsReview: Sources of Cache MissesDirect Mapped CacheSet Associative CacheFully Associative CacheWhere does a Block Get Placed in a Cache?Review: Caching Applied to Address TranslationTLB organizationReducing translation time furtherOverlapping TLB & Cache AccessPutting Everything TogetherPaging & Address TranslationTranslation Look-aside BufferCachingCS162Operating Systems andSystems ProgrammingMidterm ReviewMarch 7, 2011Ion Stoicahttp://inst.eecs.berkeley.edu/~cs162Midterm Review.23/7 Ion Stoica CS162 ©UCB Spring 2011Synchronization, Critical sectionMidterm Review.33/7 Ion Stoica CS162 ©UCB Spring 2011Definitions•Synchronization: using atomic operations to ensure cooperation between threads•Mutual Exclusion: ensuring that only one thread does a particular thing at a time–One thread excludes the other while doing its task•Critical Section: piece of code that only one thread can execute at once–Critical section is the result of mutual exclusion–Critical section and mutual exclusion are two ways of describing the same thing.Midterm Review.43/7 Ion Stoica CS162 ©UCB Spring 2011Locks: using 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 (anyone on wait queue) {take thread off wait queuePlace on ready queue;} else {value = FREE;}enable interrupts;}Midterm Review.53/7 Ion Stoica CS162 ©UCB Spring 2011Better locks: using test&set•test&set (&address) { /* most architectures */result = M[address];M[address] = 1;return result;}Release() {// Short busy-wait timewhile (test&set(guard));if anyone on wait queue {take thread off wait queuePlace on ready queue;} else {value = FREE;}guard = 0;int guard = 0;int value = FREE;Acquire() {// Short busy-wait timewhile (test&set(guard));if (value == BUSY) {put thread on wait queue;go to sleep() & guard = 0;} else {value = BUSY;guard = 0;}}Midterm Review.63/7 Ion Stoica CS162 ©UCB Spring 2011Semaphores•Semaphores are a kind of generalized lock–First defined by Dijkstra in late 60s–Main synchronization primitive used in original UNIX•Definition: a Semaphore has a non-negative integer value and supports the following two operations:–P(): an atomic operation that waits for semaphore to become positive, then decrements it by 1 »Think of this as the wait() operation–V(): an atomic operation that increments the semaphore by 1, waking up a waiting P, if any»This of this as the signal() operation–Note that P() stands for “proberen” (to test) and V() stands for “verhogen” (to increment) in DutchMidterm Review.73/7 Ion Stoica CS162 ©UCB Spring 2011Value=2Value=1Value=0Semaphores Like Integers Except•Semaphores are like integers, except–No negative values–Only operations allowed are P and V – can’t read or write value, except to set it initially–Operations must be atomic»Two P’s together can’t decrement value below zero»Similarly, thread going to sleep in P won’t miss wakeup from V – even if they both happen at same time•Semaphore from railway analogy–Here is a semaphore initialized to 2 for resource control:Value=1Value=0Value=2Midterm Review.83/7 Ion Stoica CS162 ©UCB Spring 2011Condition Variables•Condition Variable: a queue of threads waiting for something inside a critical section–Key idea: allow sleeping inside critical section by atomically releasing lock at time we go to sleep–Contrast to semaphores: Can’t wait inside critical section•Operations:–Wait(&lock): Atomically release lock and go to sleep. Re-acquire lock later, before returning. –Signal(): Wake up one waiter, if any–Broadcast(): Wake up all waiters•Rule: Must hold lock when doing condition variable ops!Midterm Review.93/7 Ion Stoica CS162 ©UCB Spring 2011Complete Monitor Example (with condition variable)•Here is an (infinite) synchronized queueLock lock;Condition dataready;Queue queue;AddToQueue(item) {lock.Acquire(); // Get Lockqueue.enqueue(item); // Add itemdataready.signal(); // Signal any waiterslock.Release(); // Release Lock}RemoveFromQueue() {lock.Acquire(); // Get Lockwhile (queue.isEmpty()) {dataready.wait(&lock); // If nothing, sleep}item = queue.dequeue(); // Get next itemlock.Release(); // Release Lockreturn(item);}Midterm Review.103/7 Ion Stoica CS162 ©UCB Spring 2011Mesa vs. Hoare monitors•Need to be careful about precise definition of signal and wait. Consider a piece of our dequeue code:while (queue.isEmpty()) {dataready.wait(&lock); // If nothing, sleep}item = queue.dequeue(); // Get next item–Why didn’t we do this?if (queue.isEmpty()) {dataready.wait(&lock); // If nothing, sleep}item = queue.dequeue(); // Get next item•Answer: depends on the type of scheduling–Hoare-style (most textbooks):»Signaler gives lock, CPU to waiter; waiter runs immediately»Waiter gives up lock, processor back to signaler when it exits critical section or if it waits again–Mesa-style (most real operating systems):»Signaler keeps lock and processor»Waiter placed on ready queue with no special priority»Practically, need to check condition again after waitMidterm Review.113/7 Ion Stoica CS162 ©UCB Spring 2011Read/Writer RevisitedReader() {// check into systemlock.Acquire();while ((AW + WW) > 0) {WR++;okToRead.wait(&lock);WR--;}AR++;lock.release();// read-only accessAccessDbase(ReadOnly);// check out of systemlock.Acquire();AR--;if (AR == 0 && WW > 0)okToWrite.signal();lock.Release();}Writer() {// check into systemlock.Acquire();while ((AW + AR)


View Full Document

Berkeley COMPSCI 162 - Midterm Review

Documents in this Course
Lecture 1

Lecture 1

12 pages

Nachos

Nachos

41 pages

Security

Security

39 pages

Load more
Download Midterm Review
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 Midterm Review 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 Midterm Review 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?