Synchronization and !Prelim 2 Review"Hakim&Weatherspoon&CS&3410,&Spring&2011&Computer)Science)Cornell)University)2)Announcements"FarmVille)pizza)Party)was)fun!)• Winner:)Team)HakimPeterSpoon))Joseph)Mongeluzzi)and)Jason)Zhao))1st Round Sweet 16 Elite Eight Final Four Championship Final Four Elite Eight Sweet 16 1st Round1 hakimPeterSpoon gaxlr 2hakimPeterSpoon gaxlr32 bossbot ams_jhj_test 31hakimPeterSpoon gaxlr16 seeder Sparkles 15seeder eli_whitney17 ryanbot eli_whitney 18hakimPeterSpoon gaxlr9 tsapanzerhalis vanessaKensington 10tsapanzerhalis vanessaKensington24 superfarmer our_farmer 23tsapanzerhalis vanessaKensington8 drunkbot cheese 7drunkbot cheese25tenThousandFlippingVegetablesjhl_ncn_farmer 26hakimPeterSpoon hakimPeterSpoon gaxlr4 WALLE phantom 3WALLE phantom29better_than_peters_botstestExploit12 30WALLE phantom13 petey9 dcv_prd_farmer 14enb_lw_farmer dcv_prd_farmer20 enb_lw_farmer fastfiller 19QihoTheShark better_greedy12 aen_dpm_farmer better_greedy 11aen_dpm_farmer better_greedy21 exploit chomp 22QihoTheShark better_greedy5 QihoTheShark frl_hd_farmer 6QihoTheShark frl_hd_farmer28 fertile_cresent mjbebe 273)Announcements"HW4)due)today,)Tuesday,)April)26th)• Work)alone))Next)two)weeks)• Prelim2)will)in#class(this)Thursday,)April)28th))– 90)minutes)in)class:)1:25pm)–)2:55pm)– Topics:)Caching,)Virtual)Memory,)Paging,)TLBs,)I/O,)Traps,)ExcepZons,)mulZcore,)and)synchronizaZon)• PA4)will)be)final)project)(no)final)exam))– Available)this)Friday,)April)29th)and)due)Friday,)May)13th))– Need)to)schedule)Zme)for)presentaZon)May)16,)17,)or)18.)– Will(not(be(able(to(use(slip(days()4)Goals for Today"Finish)SynchronizaZon)• Threads)and)processes)• CriZcal)secZons,)race)condiZons,)and)mutexes))Prelim)2)review)• Caching,)• Virtual)Memory,)Paging,)TLBs)• I/O)and)DMA))• OperaZng)System,)Traps,)ExcepZons,)• MulZcore)and)synchronizaZon))))5)MulZccore)is)a)reality…))…)but)how)do)we)write)mulZccore)safe)code?)6)Processes)and))Threads)7)Processes are heavyweight"Parallel)programming)with)processes:)• They)share)almost)everything))code,)shared)mem,)open)files,)filesystem)privileges,)…)• Pagetables)will)be)almost)idenZcal)• Differences:)PC,)registers,)stack)Recall:)process)=)execuZon)context)+)address)space)8)Processes and Threads"Process)OS)abstracZon)of)a)running)computaZon)• The)unit)of)execuZon)• The)unit)of)scheduling)• ExecuZon)state)+)address)space)From)process)perspecZve)• a)virtual)CPU)• some)virtual)memory)• a)virtual)keyboard,)screen,)…)Thread)OS)abstracZon)of)a)single)thread)of)control)• The)unit)of)scheduling)• Lives)in)one)single)process)From)thread)perspecZve)• one)virtual)CPU)core)on)a)virtual)mulZccore)machine)9)Multithreaded Processes"10)Threads"#include)<pthread.h>))int)counter)=)0;))void)PrintHello(int)arg)){))printf(“I’m)thread)%d,)counter)is)%d\n”,)arg,)counter++);))...)do)some)work)...))pthread_exit(NULL);))}))int)main)()){)))for)(t)=)0;)t)<)4;)t++)){))))) )printf(“in)main:)creating)thread)%d\n",)t);)))))) )pthread_create(NULL,)NULL,)PrintHello,)t);))))})))))pthread_exit(NULL);))}))11)Threads versus Fork"in)main:)creating)thread)0)I’m)thread)0,)counter)is)0)in)main:)creating)thread)1)I’m)thread)1,)counter)is)1)in)main:)creating)thread)2)in)main:)creating)thread)3)I’m)thread)3,)counter)is)2)I’m)thread)2,)counter)is)3))If)processes?)12)Example Multi-Threaded Program"Example:)Apache)web)server)void)main()){)setup();))while)(c)=)accept_connection())){)))req)=)read_request(c);)) )hits[req]++;))send_response(c,)req);))))}))cleanup();)})13)Race Conditions"Example:)Apache)web)server)Each)client)request)handled)by)a)separate)thread)(in)parallel))• Some)shared)state:)hit)counter,)...))))(look)familiar?))Timingcdependent)failure)⇒)race)condiZon)• )hard)to)reproduce)⇒)hard)to)debug)Thread'52'...'hits'='hits'+'1;'...'Thread'205'...'hits'='hits'+'1;'...'Thread'52'read'hits'addi'write'hits'Thread'205'read'hits'addi'write'hits'14)Programming with threads"Within)a)thread:)execuZon)is)sequenZal)Between)threads?)• No)ordering)or)Zming)guarantees)• Might)even)run)on)different)cores)at)the)same)Zme)Problem:)hard)to)program,)hard)to)reason)about)• Behavior)can)depend)on)subtle)Zming)differences)• Bugs)may)be)impossible)to)reproduce)Cache)coherency)isn’t)sufficient…)Need)explicit)synchronizaZon)to))make)sense)of)concurrency!)15)Managing)Concurrency)Races,)CriZcal)SecZons,)and)Mutexes)16)Goals"Concurrency)Goals)Liveness)• Make)forward)progress)Efficiency)• Make)good)use)of)resources)Fairness)• Fair)allocaZon)of)resources)between)threads)Correctness)• Threads)are)isolated)(except)when)they)aren’t))17)Race conditions"Race)CondiZon)Timingcdependent)error)when))accessing))shared)state))• Depends)on)scheduling)happenstance)…)e.g.)who)wins)“race”)to)the)store)instrucZon?)Concurrent)Program)Correctness)=)all)possible)schedules)are)safe)))• Must)consider)every.possib le.permutaZon)• In)other)words…)) )…)the)scheduler)is)your)adversary)18)Critical sections"What)if)we)can)designate)parts)of)the)execuZon)as)criZcal)secZons)• Rule:)only)one)thread)can)be)“inside”)Thread'52'''read'hits'addi'write'hits''''Thread'205'''read'hits'addi'write'hits''''19)Interrupt Disable"Q:)How)to)implement)criZcal)secZon)in)code?)A:)Lots)of)approaches….)Disable)interrupts?)CSEnter())=)disable)interrupts)(including)clock))CSExit())=)recenable)interrupts)))))))Works)for)some)kernel)datacstructures)Very)bad)idea)for)user)code)read)hits)addi)write)hits)20)Preemption Disable"Q:)How)to)implement)criZcal)secZon)in)code?)A:)Lots)of)approaches….)Modify)OS)scheduler?)CSEnter())=)syscall)to)disable)context)switches)CSExit())=)syscall)to)recenable)context)switches)))))))Doesn’t)work)if)interrupts)are)part)of)the)problem)Usually)a)bad)idea)anyway)read)hits)addi)write)hits)21)Mutexes"Q:)How)to)implement)criZcal)secZon)in)code?)A:)Lots)of)approaches….)Mutual)Exclusion)Lock)(mutex))acquire(m):)wait)Zll)it)becomes)free,)then)lock)it)release(m):)unlock)it))apache_got_hit()){))pthread_mutex_lock(m);))hits)=)hits)+)1;))pthread_mutex_unlock(m))})22)Q:)How)to)implement)mutexes?)Prelim 2 Review"24)Caches)Memory pyramid Disk (Many GB) Memory (128MB – few GB) L2 Cache (½-32MB) L1 Cache (several KB) Reg 100s bytes Cache Design 101"1 cycle access (early in pipeline) 1-3 cycle
View Full Document
Unlocking...