Class Note for CMPSCI 377 at UMass(55)
Class Note for CMPSCI 377 at UMass(55)
Popular in Course
Popular in Department
This 7 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 16 views.
Reviews for Class Note for CMPSCI 377 at UMass(55)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 377 Operating Systems Fall 2007 Lecture 9 October 18 Lecturer Emery Berger Scribe Andrew Huang 91 Synchronization 911 Consistency Threads must ensure consistency Otherwise threads may result in a race condition leading to a non deterministic result A race is when the result is dependent the order in which the threads nish For example Thread A says X l and if X 2 then print What7 Thread B says X 2 What is X Threads require synchronization operations for this to be answered 92 The too much milk problem The too much milk problem time You Your roommate 300 Arrive Home 305 Look in fridge no milk 310 Leave for grocery 315 Arrive home 320 Arrive at grocery Look in fridge no milk 325 Buy milk Leave for grocery 330 Arrive home put milk in fridge 335 Arrive at grocery 340 Buy milk 345 Arrive home put milk in fridge 350 Uh oh This is why we need to synchronize activities Terminology De nition 91 Mutual exclusion mutem prevents multiple threads from entering The critical sec tion is code that only one thread can execute at a time A lock is a mechanism for mutual exclusion 91 92 0 Lock on entering critical section accessing shared data 0 Unlock when complete 0 Wait if locked 921 Solving the Too Much Milk Problem Correctness properties 0 Only one person buys milk 7 Safety nothing bad happens 0 Someone buys milk if you need to 7 Progress something good eventually happens First use atomic loads stores as building blocks 0 Leave a note lock 0 Remove a note unlock o Don7t buy milk if there s a note wait 922 Too Much Milk Attempt 1 thread A thread B ifno milk ampamp no note leave note buy milk remove note if no milk ampamp no note leave note buy note remove note l If both threads switch after reading the if statement7 then both Will buy milk 923 Too Much Milk Attempt 2 Idea use labeled notes thread A thread B leave note B if no note A if no milk buy milk remove note B leave note A if no note B if no milk buy milk remove note A Lecture 9 October 18 Lecture 9 October 18 93 l If both threads switch after leaving a note neither will buy milk 924 Too Much Milk Attempt 3 Idea wait for the right note thread A thread B leave note A leave note B while note B if no note A do nothing if no milk if no milk buy milk buy milk remove note B remove note A Possibility 1 thread A runs rst then thread B thread A will buy milk thread B will see there is milk and therefore not buy any more milk Possibility 2 thread B runs rst then thread A thread B will buy milk thread A will see there is milk and therefore not buy any more milk Possibility 3 Interleaved A waits buys thread A and thread B can leave a note but thread A will wait for thread B to nish before moving on thread B will not buy milk because note A exists and nish the thread thread A will continue and buy milk Possibility 4 Interleaved A waits B buys thread B will leave a note and see there is no note A A can start and see there is a note B and wait for B to nish B will continue to buy milk if there no milk and then nish before thread A will continue thread A will not buy milk because thread B just bought milk So attempt 3 is a correct solution because it preserves the desired properties 0 Safety we only buy milk once 0 Progress we always buy milk but 925 Problems With this solution Complicated o Dif cult to convince outselves that it works 94 Lecture 9 October 18 Asymmetrical 0 Threads A amp B are different 0 Adding more threads different code for each thread Poor utilization 0 Busy waiting consumes CPU7 no useful work 7 time could be better spent on other work Possibly nonportable o Relies on atomicity of loads amp stores 7 atomicity is 77 all of nothing77 93 Language Support Synchronization making an area of code atomic is complicated Better way provide languagelevel support 0 Higherlevel approach 0 Hide gory details in runtime system lncreasingly highlevel approaches pthread supplies all these 0 Locks7 Atomic Operations 0 Semaphores generalized locks o Monitors tie shared data to synchronization 94 Locks Provide mutual exclusion to shared data Via two atomic routines o acquire wait for lock then take it 0 release unlock wake up waiters Rules 0 Acquire lock before accessing shared data 0 Release lock afterwards 0 Lock initially released Lecture 9 October 18 95 941 Pthreads Syntax POSIX standard for CC Mutual exclusion locks o Ensures only one thread in critical section pthreadmut exJnit l pthreadmut exlockl update data cn39tz39cal section pthreadmutexunlockl 942 Pthreads API Routine Pre x Functional Group pthread Threads themselves and miscellaneous subroutines pthreadattr Threads attributes objects pthreadmutex Mutexes 943 Too Much Milk Locks thread A thread B pmJockl pJnJockl if no milk if no milk buy milk buy milk pmJockl pJnJockl The code in both threads is exactly the same Clean7 symmetric but how do we implement it Hardware support prevents both locks from happening at the same time Dekker s algorithm allows mutual exlusion 944 Implementing Locks Requires hardware support in general Can build on atomic operations 0 Load Store 0 Disable interrupts 7 Uniprocessors only7 this does not work on multiprocessors 7 Says to OS7 77Shut up7 don7t switch me out or interrupt me77 0 Test amp Set7 Compare amp Swap 96 Lecture 9 October 18 945 Disabling Interrupts 77I want a noti cation When some time elapses7 a hardware signal called an interrupt7 and time is up77 Disabling interrupts prevent scheduler from switching threads in middle of critical sections 0 lgnores quantum expiration timer interrupt o No handling lO operations 7 Don7t make lO calls in critical section In cooperative multithreading7 a thread can call yield and say it is ok to switch out Class private int value private Queue q Lock value 0 q empty public void acquire disable interrupts if value BUSY add this thread to q enable interrupts sleepO else value BUSY enable interrupts public void release disable interrupts if q not empty thread t qlpop put t on ready queue value FREE enable interrupts Lecture 9 October 18 946 Time 947 X1 Y2 ZX Could run ZX7 and then X17 because reads can come rst but Locks via Disabling Interrupts Thread A Thread B disable interrupts Sl p sleep return enable disable switch Sleep sleep return enable B arrier Barrier prevents misordering BARRIER don7t execute until above is done X1 Y2 ZX 95 Summary Communication between threadszvia shared variables Critical sections regions of code that modify or access shared variables Must be protected by synchronization primitives that ensure mutual exclusion o Loads 85 stores tricky7 error prone 0 Solution high level primitives eg7 locks
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'