Concurrency Issues - Virginia Tech

Concurrency Issues - Virginia Tech

Concurrency Issues Motivation, Problems, Directions Dennis Kafura - CS 5204 - Operating Systems 1 Concurrency Issues Reasons for Concurrency coordination multitasking parallelism performance Dennis Kafura - CS 5204 - Operating Systems

2 Concurrency Issues Moores Law Transistor density on integrated circuits doubles about every two years. Gordon E. Moore, Co-founder, Intel Corporation. Dennis Kafura - CS 5204 - Operating Systems 3 Concurrency Issues Hitting the wall

Dennis Kafura - CS 5204 - Operating Systems 4 Concurrency Issues Thermal Density 2005 (cooler alone) 1993 (CPU and cooler) Dennis Kafura - CS 5204 - Operating Systems 5 Concurrency Issues Rise of Multi-/Many- Core Technologies Intel: Quad Core

Sun: 8 core chip Dennis Kafura - CS 5204 - Operating Systems Intel: 80 core experimental system 6 Concurrency Issues Context concurrent parallel Support for concurrent and parallel programming conform to application semantics

functionality respect priorities of applications no unnecessary blocking fast context switch high processor utilization performance relative importance Dennis Kafura - CS 5204 - Operating Systems 7 Concurrency Issues Heavyweight Process Model ...

user kernel simple, uni-threaded model security provided by address space boundaries high cost for context switch coarse granularity limits degree of concurrency Dennis Kafura - CS 5204 - Operating Systems 8 Concurrency Issues Lightweight (User-level) Threads ... user kernel thread semantics defined by application

fast context switch time (within an order of magnitude of procedure call time) system scheduler unaware of user thread priorities unnecessary blocking (I/O, page faults, etc.) processor under-utilization Dennis Kafura - CS 5204 - Operating Systems 9 Concurrency Issues Kernel-level Threads ... user kernel thread semantics defined by system overhead incurred due to overly general implementation and cost of kernel traps for thread operations

context switch time better than process switch time by an order of magnitude, but an order of magnitude worse than user-level threads system scheduler unaware of user thread state (e.g, in a critical region) leading to blocking and lower processor utilization Dennis Kafura - CS 5204 - Operating Systems 10 Concurrency Issues Threads are Bad Difficult to program Synchronizing access to shared state Deadlock Hard to debug (race conditions, repeatability)

Break abstractions Modules must be designed thread safe Difficult to achieve good performance simple locking lowers concurrency context switching costs OS support inconsistent

semantics and tools vary across platforms/systems May not be right model Window events do not map to threads but to events Dennis Kafura - CS 5204 - Operating Systems 11 Concurrency Issues Lees Crticisms of Threads Threads are not composable

Difficult to reason about threads Everything can change between steps Threads are wildly nondeterministic Inteference via shared resources Requires careful pruning by programmer In practice, difficult to program correctly

Experience and examples Dennis Kafura - CS 5204 - Operating Systems 12 Concurrency Issues Ousterhouts conclusions Dennis Kafura - CS 5204 - Operating Systems 13 Concurrency Issues Resilience of Threads

Widely supported in mainstream operating systems Direct kernel/hardware support even if semantics differ via kernel threads and multi-core shared address spaces Ability to pass complex data structures efficiently via pointers in shared memory

Programmability standard interfaces defined (e.g., POSIX) construct in some languages (e.g., Java) widely delolyed/understood (even if misused) Dennis Kafura - CS 5204 - Operating Systems 14 Concurrency Issues Concurrency Errors in Practice Characterization study

Four large, mature, open-source systems 105 randomly selected currency errors Examined bug report, code, corrections Classified bug patterns, manifestation, fix strategy Dennis Kafura - CS 5204 - Operating Systems 15 Concurrency Issues Concurrency Error Patterns Finding (1): Most (72 out of 74) of the examined non-deadlock concurrency bugs are covered by two simple patters: atomicity-violation and order-violation. A B

atomicity-violation: interference with a sequence of steps intended to be performed as a unit order-violation: failure to perform steps in the intended order Dennis Kafura - CS 5204 - Operating Systems 16 Concurrency Issues Concurrency Bug Manifestations Finding (3): The manifestation of most (101 out of 105) examined concurrency bugs involves no more than two threads. Other findings: most (66%) non-deadlock concurrency bugs involved only one variable and most (97%) of deadlock concurrency bugs involves at most two

resources.. Dennis Kafura - CS 5204 - Operating Systems 17 Concurrency Issues Concurrency Bug Fix Strategies Finding (9): Adding or changing locks is not the major fix strategy. COND: Condition check Design: algorithm change Switch: Code switch Lock: add or change lock Another finding: transactional memory (TM) can help avoid many (41 or 105) concurrency bugs. Dennis Kafura - CS 5204 - Operating Systems

18 Concurrency Issues Solutions to thread problems New models of concurrent computation MapReduce Large-scale data Highly distributed, massively parallel environment Concurrent Collections (CnC)

General concurrent programming vehicle Multicore architectures Thread-per-process models Communicating Sequential Processes Grace Sammati Dennis Kafura - CS 5204 - Operating Systems 19

Recently Viewed Presentations

  • Abject (adj) - SharpSchool

    Abject (adj) - SharpSchool

    Complicity (n) Involvement in wrongdoing; the state of being an accomplice. Syn: collusion, connivance. Ant: noninvolvement, innocence *** being an
  • Introducere În Compatibilitate Electromagnetică

    Introducere În Compatibilitate Electromagnetică

    Un detaliu de asigurare a ecranării la îmbinarea uşii şi antena pentru generarea /măsurarea câmpului electromagnetic sunt arătate în figura : Firme consacrate O firmă consacrată este Laplace Instruments din Anglia care realizează o gamă largă de echipamente pentru EMC:...
  • Jacek Zurada, IEEE Life FellowCandidate for 2018 IEEE ...

    Jacek Zurada, IEEE Life FellowCandidate for 2018 IEEE ...

    Jacek Zurada, IEEE Life FellowCandidate for 2018 IEEE President-ElectR10, Sydney, August 11, [email protected] www.jacekzurada.org IEEE Universe Regions, Sections ,
  • Geochemical and Chronostratigraphic Record of Cenomanian ...

    Geochemical and Chronostratigraphic Record of Cenomanian ...

    Fingerprint Volcanic Rock Type. TAS diagrams susceptible to alteration and mobility of elements. Zr/TiO2 - Nb/Y diagram (Winchester & Floyd, 1977) utilizes immobile elements to categorize rock type. Intermediate to evolved (Andestie - Rhyolite), typical volcanic arc lavas.
  • Slovensko hľadá SuperStar 2 - Základná škola na ...

    Slovensko hľadá SuperStar 2 - Základná škola na ...

    Hrá na husliach, klavíri a na gitare. Zje všetko, ale najradšej má buchty na pare. Je optimista. Bratislava 24.marca 2006 - Peter Bažík v kole LEGENDY verzus LEGENDY nepostúpil a skončil na 4.mieste Ivan Štroffek Narodil sa 26.5. 1984 v...
  • FDP Expanded Clearinghouse Lynette Arias, University of Washington

    FDP Expanded Clearinghouse Lynette Arias, University of Washington

    McLean Hospital. Purdue University. Syracuse University. Tufts University. ... New York University School of Medicine. North Carolina State University. ... Gloria Greene/ Steve Parker. University of Alabama. Jennifer Rodis. University of Wisconsin-Madison. Sara Clough.
  • Case Study Follicular Lymphoma - haematologynursesireland.ie

    Case Study Follicular Lymphoma - haematologynursesireland.ie

    GCS 15/15, PEARL, no apparent injury. CTB - clear. Wanted to leave hospital to attend the hearing of his step-fathers court case. Treatment. 5/7/16 - 1st CHOP with Rasburicase (no GCSF-splenomegaly) ... Case Study Follicular Lymphoma Last modified by:
  • enviroprosecutionlaw.files.wordpress.com

    enviroprosecutionlaw.files.wordpress.com

    Ronaldo Guirgola now calls Australia his home. The operation of the Convention, and how it will affect architectural services amongst other cultural goods and services traded internationally, as they incorporated into international trade agreements, like the TPP (Trans-Pacific Partnership ...