DOC PREVIEW
Berkeley COMPSCI 162 - Synchronization, Atomic operations, Locks, Semaphores"

This preview shows page 1-2-3 out of 10 pages.

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

Unformatted text preview:

Page 1 CS162!Operating Systems and!Systems Programming!Lecture 4!Synchronization, Atomic operations, Locks, Semaphores"January 31, 2011!Ion Stoica!http://inst.eecs.berkeley.edu/~cs162!Lec 4.2!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!Space Shuttle Example"• Original Space Shuttle launch aborted 20 minutes before scheduled launch!• Shuttle has five computers:!– Four run the “Primary Avionics #Software System” (PASS)!» Asynchronous and real-time!» Runs all of the control systems!» Results synchronized and compared every 3 to 4 ms!– The Fifth computer is the “Backup Flight System” (BFS)!» stays synchronized in case it is needed!» Written by completely different team than PASS!• Countdown aborted because BFS disagreed with PASS!– A 1/67 chance that PASS was out of sync one cycle!– Bug due to modifications in initialization code of PASS!» A delayed init request placed into timer queue!» As a result, timer queue not empty at expected time to force use of hardware clock!– Bug not found during extensive simulation!PASS BFS Lec 4.3!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!Another 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 counter!! ! !Thread A ! !Thread B!! !i = 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? !• 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 4.4!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!Goals for Today"• Synchronization!• Hardware Support for Synchronization!• Higher-level Synchronization Abstractions!– Semaphores, monitors, and condition variables!• Programming paradigms for concurrent programs!Note: Some slides and/or pictures in the following are"adapted from slides ©2005 Silberschatz, Galvin, and Gagne "Note: Some slides and/or pictures in the following are"adapted from slides ©2005 Silberschatz, Galvin, and Gagne. Many slides generated by Kubiatowicz."Page 2 Lec 4.5!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!Motivation: “Too much milk”"• Great thing about OSʼs – analogy between problems in OS and problems in real life!– Help you understand real life problems better!– But, computers are much stupider than people!• Example: People need to coordinate:!Arrive home, put milk away"3:30"Buy milk"3:25"Arrive at store"Arrive home, put milk away"3:20"Leave for store"Buy milk"3:15"Leave for store"3:05"Look in Fridge. Out of milk"3:00"Look in Fridge. Out of milk"Arrive at store"3:10"Person B"Person A"Time"Lec 4.6!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!Definitions"• Synchronization: using atomic operations to ensure cooperation between threads!– For now, only loads and stores are atomic!– Weʼll show its hard to build anything useful with only reads and writes!• 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.!Lec 4.7!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!More Definitions"• 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!• For example: fix the milk problem by putting a key on the refrigerator!– Lock it and take key if you are going to go buy milk!– Fixes too much: roommate angry if only wants orange juice!– Of Course – We donʼt know how to make a lock yet!#$@%@#$@ Lec 4.8!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!Too Much Milk: Correctness Properties"• Need to be careful about correctness of concurrent programs, since non-deterministic!– Always write down behavior first!– Impulse is to start coding first, then when it doesnʼt work, pull hair out!– Instead, think first, then code!• What are the correctness properties for the “Too much milk” problem?!– Never more than one person buys!– Someone buys if needed!• Restrict ourselves to use only atomic load and store operations as building blocks!Page 3 Lec 4.9!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!Too Much Milk: Solution #1"• Use a note to avoid buying too much milk:!– Leave a note before buying (kind of “lock”)!– Remove note after buying (kind of “unlock”)!– Donʼt buy if note (wait)!• Suppose a computer tries this (remember, only memory read/write are atomic):! if (noMilk) { if (noNote) { leave Note; buy milk; remove note; } } • Result? !Lec 4.10!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!Too Much Milk: Solution #1" • Still too much milk but only occasionally!! Thread A Thread B if (noMilk) if (noNote) { if (noMilk) if (noNote) { leave Note; buy milk; remove note; } }! leave Note; buy milk; … • Thread can get context switched after checking milk and note but before buying milk!!• Solution makes problem worse since fails intermittently!– Makes it really hard to debug…!– Must work despite what the thread dispatcher does!!Lec 4.11!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!Too Much Milk: Solution #1½ "• Clearly the Note is not quite blocking enough!– Letʼs try to fix this by placing note first!• Another try at previous solution:! leave Note; if (noMilk) { if (noNote) { buy milk; } } remove note; • What happens here?!– Well, with human, probably nothing bad!– With computer: no one ever buys milk!Lec 4.12!31/1/11! Ion Stoica CS162 ©UCB Spring 2011!Too


View Full Document

Berkeley COMPSCI 162 - Synchronization, Atomic operations, Locks, Semaphores"

Documents in this Course
Lecture 1

Lecture 1

12 pages

Nachos

Nachos

41 pages

Security

Security

39 pages

Load more
Download Synchronization, Atomic operations, Locks, Semaphores"
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 Synchronization, Atomic operations, Locks, Semaphores" 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 Synchronization, Atomic operations, Locks, Semaphores" 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?