Slide 1AnnouncementsAnnouncementsGoals for TodaySlide 5Slide 6Processes are heavyweightProcesses and ThreadsMultithreaded ProcessesThreadsThreads versus ForkExample Multi-Threaded ProgramRace ConditionsProgramming with threadsSlide 15GoalsRace conditionsCritical sectionsInterrupt DisablePreemption DisableMutexesSlide 22Slide 23Slide 24Cache Design 101Cache MissesDirect Mapped CacheFully Associative Cache2-Way Set-Associative CacheEvictionCache WritesTags and OffsetsCache PerformanceCache Hit/Miss RateCache Hit/Miss RateCache Conscious ProgrammingCache Conscious ProgrammingCan answer the question…..Slide 39Processor & MemoryPhysical Addressing ProblemsAddress SpaceVirtual Memory AdvantagesHow to make it work?Two Programs Sharing Physical MemoryPage Table for TranslationVirtual Addressing with a CacheA TLB in the Memory HierarchyVirtual vs. Physical CachesAddress TranslationHardware/Software BoundaryHardware/Software BoundarySlide 53PagingSlide 55Slide 56ExceptionsTerminologySlide 59Memory-Mapped I/ODMA: Direct Memory AccessSlide 62Why Multicore?Slide 64Power TrendsUniprocessor PerformanceWhy Multicore?Intel’s argumentSlide 69Amdahl’s LawAmdahl’s LawMultithreaded ProcessesShared countersRace conditionsCritical SectionsMutexesProtecting an invariantSlide 78Synchronization and Prelim 2 ReviewHakim WeatherspoonCS 3410, Spring 2011Computer ScienceCornell University2AnnouncementsFarmVille pizza Party was fun!•Winner: Team HakimPeterSpoonJoseph Mongeluzzi and Jason Zhao1st 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 273AnnouncementsHW4 due today, Tuesday, April 26th•Work aloneNext 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, Exceptions, multicore, and synchronization•PA4 will be final project (no final exam)–Available this Friday, April 29th and due Friday, May 13th –Need to schedule time for presentation May 16, 17, or 18.–Will not be able to use slip days4Goals for TodayFinish Synchronization•Threads and processes•Critical sections, race conditions, and mutexesPrelim 2 review•Caching,•Virtual Memory, Paging, TLBs•I/O and DMA •Operating System, Traps, Exceptions,•Multicore and synchronization5Multi-core is a reality…… but how do we write multi-core safe code?6Processes and Threads7Processes are heavyweightParallel programming with processes:•They share almost everything code, shared mem, open files, filesystem privileges, …•Pagetables will be almost identical•Differences: PC, registers, stackRecall: process = execution context + address space8Processes and ThreadsProcessOS abstraction of a running computation•The unit of execution•The unit of scheduling•Execution state+ address spaceFrom process perspective•a virtual CPU•some virtual memory•a virtual keyboard, screen, …ThreadOS abstraction of a single thread of control•The unit of scheduling•Lives in one single processFrom thread perspective•one virtual CPU core on a virtual multi-core machine9Multithreaded Processes10Threads#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); }11Threads versus Forkin main: creating thread 0I’m thread 0, counter is 0in main: creating thread 1I’m thread 1, counter is 1in main: creating thread 2in main: creating thread 3I’m thread 3, counter is 2I’m thread 2, counter is 3If processes?12Example Multi-Threaded ProgramExample: Apache web servervoid main() {setup();while (c = accept_connection()) {req = read_request(c);hits[req]++;send_response(c, req);}cleanup();}13Race ConditionsExample: Apache web serverEach client request handled by a separate thread (in parallel)•Some shared state: hit counter, ...(look familiar?)Timing-dependent failure race condition• hard to reproduce hard to debugThread 52...hits = hits + 1;...Thread 205...hits = hits + 1;...Thread 52read hitsaddiwrite hitsThread 205read hitsaddiwrite hits14Programming with threadsWithin a thread: execution is sequentialBetween threads?•No ordering or timing guarantees•Might even run on different cores at the same timeProblem: hard to program, hard to reason about•Behavior can depend on subtle timing differences•Bugs may be impossible to reproduceCache coherency isn’t sufficient…Need explicit synchronization to make sense of concurrency!15Managing ConcurrencyRaces, Critical Sections, and Mutexes16GoalsConcurrency GoalsLiveness•Make forward progressEfficiency•Make good use of resourcesFairness•Fair allocation of resources between threadsCorrectness•Threads are isolated (except when they aren’t)17Race conditionsRace ConditionTiming-dependent error when accessing shared state •Depends on scheduling happenstance… e.g. who wins “race” to the store instruction?Concurrent Program Correctness =all possible schedules are safe •Must consider every possible permutation•In other words…… the scheduler is your adversary18Critical sectionsWhat if we can designate parts of the execution as critical sections•Rule: only one thread can be “inside”Thread 52read hitsaddiwrite hitsThread 205read hitsaddiwrite hits19Interrupt DisableQ: How to implement critical section in code?A: Lots of approaches….Disable interrupts?CSEnter() = disable interrupts (including clock)CSExit() = re-enable interruptsWorks for some kernel
View Full Document
Unlocking...