DOC PREVIEW
CORNELL CS 3410 - Atomic Instructions

This preview shows page 1-2-16-17-18-33-34 out of 34 pages.

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

Unformatted text preview:

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

CORNELL CS 3410 - Atomic Instructions

Documents in this Course
Marra

Marra

43 pages

Caches

Caches

34 pages

ALUs

ALUs

5 pages

Caches!

Caches!

54 pages

Memory

Memory

41 pages

Caches

Caches

32 pages

Caches

Caches

54 pages

Caches

Caches

34 pages

Caches

Caches

54 pages

Load more
Download Atomic Instructions
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 Atomic Instructions 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 Atomic Instructions 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?