!Previous: isolated processes– modularize system– share resources– speed!Now: safe non-isolated processes– Processes share state (computer, files, memory).– Concurrent access = bugs.» Example: single lane road, two approaching cars!Readings: – Silbershatz/Galvin: 7th Ed – ch. 6; 6th Ed - ch. 7gccPast and PresenthardwareOSwwwlsviMultiple processes, one world: safe?!No. Bugs if one process writes state that could be simultaneously read/written by another. – emacs writes out file while gcc compiling it. – Result? Hard to predict, except that its probably not going to be correct (or repeatable: have fun). – Always dangerous? (No. More later.) But often enough that you better think carefully.!When safe? Isolated processes– “isolated” = shares no state with any other process– doesn’t really exist: share file system, memory, …newoldemacsgccIsolated vs non-isolated processes!isolated: no shared data between processes– If P produces result x, then running any other set of independent processes P’, P’’, … wouldn’t change it.– Scheduling independence: any order = same result– Consider: internet, lots of independent machines. If don’t share state, doesn’t matter what other people do.!Non-isolated: share state– Result can be influenced by what other processes running– Scheduling can alter results– Big problem: non-deterministic. Same inputs != same result. Makes debugging very very hard.newoldemacsgccnewemacsgccWhy share? Two core reasons!Cost: buy m, amortize cost by letting n share (n > m)– One computer, many jobs; one road, many cars; this classroom, many other classes.!Information: need results from other processes– Gives speed: parallel threads working on same state– Gives modularity(?!): ability to share state lets us split tasks into isolated processes (gcc, emacs) and communicate just what is necessary– Sharing information hugely important. Consider impact of new ways to share information (print, telephone, internet, www, human voice)emacsgccc.cExample: two threads, one counter!Assume a popular web server. Uses multiple threads (on multiple processors) to speed things up. !Simple shared state error: each thread increments a shared counter to track the number of hits today:!What happens when two threads execute this code concurrently?hits = hits + 1;Fun with shared counters!One possible result: lost update! !One other possible result: everything works.– Bugs in parallel code are frequently intermittent. Makes debugging hard. !Called a “race condition”hits = 0 + 1read hits (0)hits = 0 + 1read hits (0)T1T2hits = 1hits = 0timeCS140 - Summer 2008 - Handout #3Race conditions!Race condition: timing dependent error involving shared state. – Whether it happens depends on how threads scheduled!*Hard* because:– Must make sure all possible schedules are safe. Number of possible schedules permutations is huge.– Some bad schedules? Some that will work sometimes?– They are intermittent. Timing dependent = small changes (printf’s, different machine) can hide bug.if (n == stack_size) /* A */ return full; /* B */stack[n] = v; /* C */n = n + 1; /* D */– Who wins?– Guaranteed that someone wins?– What if both threads run on own identical speed CPU executing in parallel? (Guaranteed to go on forever?)– What to do???More race condition funThread b:i = 0;while(i > -10) i = i – 1;print ‘B won!’;Thread a:i = 0;while(i < 10) i = i +1;print ‘A won!’;Dealing with race conditions!Nothing. Can be a fine response– if “hits” a perf. counter, lost updates may not matter.– Pros: simple, fast. Cons: usually doesn’t help.!Don’t share: duplicate state, or partition: – Do this whenever possible! One counter per process, two lane highways instead of single, …– Pros: simple again. Cons: never enough to go around or may have to share (gcc eventually needs to compile file)– (ee/architecture note: cache interference)!Is there a general solution? Yes! – What was our problem? Bad interleavings. So prevent!hits[1] = hits[1] + 1; hits[2] = hits[2] + 1; T2T1Atomicity: controlling race conditions !atomic unit = instruction sequence guaranteed to execute indivisibly (also, a “critical section”).– If two threads execute the same atomic unit at the same time, one thread will execute the whole sequence before the other begins.– How to make multiple inst’s seem like one atomic one??hits = hits + 1T1T2hits = 2hits = 0timehits = hits + 1Making atomicity: Uniprocessor!Only req’: thread not preempted in critical section. – Have scheduler check thread’s program counter: – Pro: fast atomicity. Con: need compiler support.!OS Traditional: threads disable/enable interrupts:– Pro: works. Con: infinite loop = stop the world./* pintos */old = intr_disable();hits = hits + 1;intr_set_level(old);while(1) { /* naïve dispatcher loop */! interrupt thread;! if pc != critical section! ! save old thread state! ! pick thread! ! load new thread state! jump to thread/* openbsd */int s = splhigh(); hits = hits + 1;splx(s);save_flags(flags); /* linux */cli()hits = hits + 1;restore_flags(flags);Making atomicity: Multiprocessor!Must prevent any other thread from executing critical section!Hardware support: could wire in atomic increment– pro: works. Con: not a general approach– instead, we do a variant: provide a hardware building block that can construct atomic primitives!General solution: locks (just like on door)– when thread enters critical section, locks it so no other thread can enter. when it leaves, thread unlocks it.– Pro: general. Con: manual, low level (better later…)unlocklockLocks: making code atomic.!Lock: shared variable, two operations: – “acquire” (lock): acquire exclusive access to lock, wait if lock already acquired.– “release” (unlock): release exclusive access to lock.!How to use? Bracket critical section in lock/unlock:– Result: only one thread updating counter at a time.– Access is “mutually exclusive”: locks in this way called “mutexes”– What have we done? Bootstrap big atomic units from smaller ones (locks)lock hit_lock;...lock(hit_lock); hit = hit + 1; unlock(hit_lock);Lock rules for easy concurrency!Every shared variable protected by a lock– shared = touched by more than one thread!Must hold lock for a shared variable before you touch– essential property: two threads can’t hold same
View Full Document
Unlocking...