Atomic Instructions!Hakim&Weatherspoon&CS&3410,&Spring&2011&Computer)Science)Cornell)University)P&H)Chapter)2.11)2)Announcements!PA4)due)next,)Friday,)May)13th)• Work)in)pairs)• Will$not$be$able$to$use$slip$days$• Need)to)schedule)Eme)for)presentaEon)May)16,)17,)or)18)• Signup)today)a*er)class)(in)front))))3)Announcements!Prelim2)results)• Mean)56.4)±)16.3)(median)57.8),)Max)95.5)• Pickup)in)Homework)pass)back)room)(Upson)360)))!"#"$"%"&"'!"'#"'$"'%"'&"'(" #!" #(" )!" )(" $!" $(" (!" ((" %!" %(" *!" *(" &!" &(" +!" +(" '!!"!"#$%&'()*+"#,(4)Goals for Today!Finish)SynchronizaEon)• Threads)and)processes)• CriEcal)secEons,)race)condiEons,)and)mutexes)• Atomic)InstrucEons)• HW)support)for)synchronizaEon)• Using)sync)primiEves)to)build)concurrencyWsafe)data)structures)• Cache)coherency)causes)problems)• Locks)+)barriers)• Language)level)synchronizaEon)))))5)Mutexes!Q:)How)to)implement)criEcal)secEon)in)code?)A:)Lots)of)approaches….)Mutual)Exclusion)Lock)(mutex))lock(m):)wait)Ell)it)becomes)free,)then)lock)it)unlock(m):)unlock)it))safe_increment().{..pthread_mutex_lock(m);..hits.=.hits.+.1;..pthread_mutex_unlock(m).}.6)Synchronization!SynchronizaEon)techniques)clever)code))• must)work)despite)adversarial)scheduler/interrupts)• used)by:)hackers)• also:)noobs)disable)interrupts)• used)by:)excepEon)handler,)scheduler,)device)drivers,)…)disable)preempEon)• dangerous)for)user)code,)but)okay)for)some)kernel)code)mutual)exclusion)locks)(mutex))• general)purpose,)except)for)some)interruptWrelated)cases)7)Hardware)Support)for)SynchronizaEon)8)Atomic Test and Set!Mutex)implementaEon)• Suppose)hardware)has)atomic)testWandWset))Hardware)atomic)equivalent)of…)int.test_and_set(int.*m).{..old.=.*m;..*m.=.1;..return.old;.}.9)Using test-and-set for mutual exclusion!Use)testWandWset)to)implement)mutex)/)spinlock)/)crit.)sec.).int.m.=.0;......while.(test_and_set(&m)).{./*.skip.*/.};...m.=.0;.10)Spin waiting!Also)called:)spinlock,)busy)waiEng,)spin)waiEng,)…)• Efficient)if)wait)is)short)• Wasteful)if)wait)is)long))Possible)h eu risEc:)• spin)for)Eme)proporEonal)to)expected)wait)Eme)• If)Eme)runs)out,)contextWswitch)to)some)other)thread)11)Alternative Atomic Instructions!Other)atomic)hardware)primiEves))W)test)and)set)(x86)))W)atomic)increment)(x86)))W)bus)lock)prefix)(x86)))12)Alternative Atomic Instructions!Other)atomic)hardware)primiEves))W)test)and)set)(x86)))W)atomic)increment)(x86)))W)bus)lock)prefix)(x86)))W)compare)and)exchange)(x86,)ARM)deprecated)))W)linked)load)/)store)condiEonal))(MIPS,)ARM,)PowerPC,)DEC)Alpha,)…))13)mutex from LL and SC!Linked)load)/)Store)CondiEonal))mutex_lock(int.*m).{.again:..LL.t0,.0(a0)..BNE.t0,.zero,.again..ADDI.t0,.t0,.1..SC.t0,.0(a0)..BEQ.t0,.zero,.again.}.14)Using)synchronizaEon)primiEves)to)build)concurrencyWsafe)datastructures)15)Broken invariants!Access)to)shared)data)must)be)synchronized)• goal:)enforce)datastructure)invariants))//.invariant:..//.data.is.in.A[h.….tT1].char.A[100];.int.h.=.0,.t.=.0;..//.writer:.add.to.list.tail.void.put(char.c).{..A[t].=.c;..t++;.}.//.reader:.take.from.list.head.char.get().{..while.(h.==.t).{.};..char.c.=.A[h];..h++;..return.c;.}.16)Protecting an invariant!Rule)of)thumb:)all)updates)that)can)affect))invariant)become)criEcal)secEons)//.invariant:.(protected.by.m).//.data.is.in.A[h.….tT1].pthread_mutex_t.*m.=.pthread_mutex_create();.char.A[100];.int.h.=.0,.t.=.0;..//.writer:.add.to.list.tail.void.put(char.c).{..pthread_mutex_lock(m);..A[t].=.c;..t++;..pthread_mutex_unlock(m);.}.//.reader:.take.from.list.head.char.get().{..pthread_mutex_lock(m);..char.c.=.A[h];..h++;..pthread_mutex_unlock(m);..return.c;.}.17)Guidelines for successful mutexing!Insufficient)locking)can)cause)races)• Skimping)on)mutexes?)Just)say)no!)Poorly)designed)locking)can)cause)deadlock))• know)why)you)are)using)mutexes!)• acquire)locks)in)a)consistent)order)to)avoid)cycles)• use)lock/unlock)like)braces)(match)them)lexically))– lock(&m);)…;)unlock(&m))– watch)out)for)return,)goto,)and)funcEon)calls!)– watch)out)for)excepEon/error)condiEons!)P1:.lock(m1);..lock(m2);.P2:.lock(m2);..lock(m1);.18)Cache)Coherency)causes)yet)more)trouble)19)Remember: Cache Coherence!Recall:)Cache)coherence)defined...)Informal:)Reads)return)most)recently)wriken)value)Formal:)For)concurrent)processes)P1)and)P2)• P)writes)X)before)P)reads)X)(with)no)intervening)writes))⇒)read)returns)wriken)value)• P1)writes)X)before)P2)reads)X))⇒)read)returns)wriken)value)• P1)writes)X)and)P2)writes)X)⇒)all)processors)see)writes)in)the)same)order)– all)see)the)same)final)value)for)X)20)Relaxed consistency implications!Ideal)case:)sequenEal)consistency)• Globally:)writes)appear)in)interleaved)order)• Locally:)other)core’s)writes)show)up)in)program)order)In)pracEce:)not)so)much…)• writeWback)caches))sequenEal)consistency)is)tricky)• writes)appear)in)semiWrandom)order)• locks)alone)don’t)help))))*)MIPS)has)sequenEal)consistency;)Intel)does)not)21)Acquire/release!Memory)Barriers)and)Release)Consistency))• Less)strict)than)sequenEal)consistency;)easier)to)build)One)protocol:)• Acquire:)lock,)and)force)subsequent)accesses)aqer)• Release:)unlock,)and)force)previous)accesses)before))P1:......acquire(m);..A[t].=.c;..t++;..release(m);.P2:......acquire(m);..A[t].=.c;..t++;..unlock(m);.Moral:)can’t)rely)on)sequenEal)consistency)(so)use)synchronizaEon)libraries))22)Are)Locks)+)Barriers)enough?)23)Beyond mutexes!Writers)must)check)for)full)buffer)&)Readers)must)check)if)for)empty)buffer)• ideal:)don’t)busy)wait…)go)to)sleep)instead)char.get().{..acquire(L);..char.c.=.A[h];..h++;..release(L);..return.c;.}.24)Beyond mutexes!Writers)must)check)for)full)buffer)&)Readers)must)check)if)for)empty)buffer)• ideal:)don’t)busy)wait…)go)to)sleep)instead)char.get().{..acquire(L);..char.c.=.A[h];..h++;..release(L);..return.c;.}.char.get().{..acquire(L);..while.(h.==.f).{.};..char.c.=.A[h];..h++;..release(L);..return.c;.}.char.get().{..while.(h.==.t).{.};..acquire(L);..char.c.=.A[h];..h++;..release(L);..return.c;.}.25)Beyond mutexes!Writers)must)check)for)full)buffer)&)Readers)must)check)if)for)empty)buffer)•
View Full Document