atomic - Computer Science & Engineering
Contents
1. no interleaved execution No fancy hardware code restrictions deadlock or unfair scheduling e g disabling interrupts 15 February 2005 Dan Grossman 21 6 5 ways atomic is better 1 Atomic makes deadlock less common e Deadlock with parallel untransfer Sun JDK had this for buffer append e Trivial deadlock if locks not re entrant e 1 lock ata time race with total funds available 15 February 2005 Dan Grossman 22 6 5 ways atomic is better 2 Atomic allows modular code evolution Race avoidance global object lock mapping Deadlock avoidance global lock partial order e Want to write foo to be race and deadlock free What locks should acquire Are y and z immutable In what order 15 February 2005 Dan Grossman 23 6 5 ways atomic is better 3 Atomic localizes errors Bad code messes up only the thread executing it e Unsynchronized actions by other threads are invisible to atomic e Atomic blocks that are too long may get starved but won t starve others Can give longer time slices 15 February 2005 Dan Grossman 24 6 5 ways atomic is better 4 Atomic makes abstractions thread safe without committing to serialization To wrap this with synchronization Grab the same lock before any call But Unnecessary no operations run in parallel even if member and size could Insufficient implementation may have races 15 February 20052. Research that needs doing and needs eager dedicated clever people 15 February 2005 Dan Grossman Cyclone in brief A safe convenient and modern language at the C level of abstraction e Safe memory safety abstract types no core dumps e C level user controlled data representation and resource management easy interoperability e Convenient may need more type annotations but work hard to avoid it e Modern add features to capture common idioms new code for legacy or inherently low level systems 15 February 2005 Dan Grossman Status Cyclone really exists except memory safe threads e gt 150K lines of Cyclone code including the compiler Compiles itself in 30 seconds e Targets gcc Linux Cygwin OSX OpenBSD Mindstorm Gameboy e User s manual mailing lists e Still a research vehicle 15 February 2005 Dan Grossman 6 Example projects e Open Kernel Environment Bos Samwel OPENARCH 02 e MediaNet Hicks et al OPENARCH 03 e RBClick Patel Lepreau OPENARCH 03 e STP Patel et al SOSP 03 e FPGA synthesis Teifel Manohar ISACS 04 e Maryland undergrad O S course geekOS 2004 e Windows device driver 6K lines e Always looking for systems projects that would benefit from Cyclone www research att com projects cyclone 15 February 2005 Dan Grossman T Not null pointers pointer to a t value or NULL pointer to a t value e Subtyping t lt t but tea t lt b
3. is better than mutual exclusion locks And why it belongs in a language e How to implement atomic on a uniprocessor e How to implement atomic on a multiprocessor 15 February 2005 Dan Grossman 29 Interleaved execution The uniprocessor assumption Threads communicating via shared memory don t execute in true parallel Actually more general than uniprocessor threads on different processors can pass messages An important special case e Many language implementations make this assumption e Many concurrent apps don t need a multiprocessor e g a document editor e f uniprocessors are dead where s the funeral 15 February 2005 Dan Grossman 30 Implementing atomic Key pieces e Execution of an atomic block logs writes e If scheduler pre empts a thread in an atomic block rollback the thread e Duplicate code so non atomic code is not slowed down by logging rollback e In an atomic block buffer output and log input Necessary for rollback but may be inconvenient 15 February 2005 Dan Grossman 31 Logging example e Executing atomic block in h builds a LIFO log of old values Rollback on pre emption e Pop log doing assignments e Set program counter and stack to beginning of atomic On exit from atomic drop log 15 February 2005 Dan Grossman 32 Logging efficiency x 0 Keeping the log small e Don t log reads key uniprocessor optimization e Don t log memory allo
4. Dan Grossman 25 6 5 ways atomic is better 5 Atomic is usually what programmers want Flanagan Qadeer Freund e Vast majority of Java methods marked synchronized are actually atomic e Of those that aren t vast majority of races are application level bugs synchronized Is an implementation detail does not belong in interfaces atomic does interface I synchronized int m class A synchronized int m an I lt lt call code with races gt gt re class B int m return 3 not an I 15 February 2005 Dan Grossman 26 6 5 ways atomic is better 6 Atomic can efficiently implement locks ee ee e Cute O S homework oo oe a problem void acquire while true while b spin n practice atomic implement locks like if b continue you always have b true return e Atomic and locks peacefully co exist void release Use both if you b false want 15 February 2005 Dan Grossman 27 6 5 ways atomic is better 6 5 Concurrent programs have the granularity problem e Too little synchronization non determinism races bugs e Too much synchronization poor performance sequentialization Example Should a chaining hashtable have one lock one lock per bucket or one lock per entry atomic doesn t solve the problem but makes it easier to mix coarse grained and fine grained operations 15 February 2005 Dan Grossman 28 Atomicity overview e Why atomic
5. OCaml bytecode compiler e Advantages of mostly functional language Fewer writes don t log object initialization To the front end atomic is just a function e Key next step port applications that use locks Planet active network from UPenn MetaPRL logical framework from CalTech 15 February 2005 Dan Grossman Atomicity overview e Why atomic is better than mutual exclusion locks And why it belongs in a language e How to implement atomic on a uniprocessor e How to implement atomic on a multiprocessor 15 February 2005 Dan Grossman A multiprocessor approach e Give up on zero cost reads e Give up on safe unsynchronized accesses All shared memory access must be within atomic conceptually compiler can insert them e But Try to minimize inter thread communication Strategy Use locks to implement atomic e Each shared object guarded by a readers writer lock Key many objects can share a lock e Logging and rollback to prevent deadlock 15 February 2005 Dan Grossman 39 Example redux e Atomic code acquires lock s forx andy 1 or 2 locks e Release locks on rollback or completion e Avoid deadlock automatically Possibilities Rollback on lock unavailable Scheduler detects deadlock initiates rollback e Only 1 problem 15 February 2005 Dan Grossman 40 What locks what There is little chance any compiler in my lifetime will infer a decent object to lock map
6. progress e Atomicity via shadow memory amp versioning Harris et al e Checking for atomicity Qadeer et al e Transactional memory in SW Herlihy et al or HW tcc PLDIO3 OOPSLA03 PODC03 ASPLOS04 15 February 2005 Dan Grossman 45 Beyond low level type safety 0 Brief Cyclone overview Synergy of types static analysis dynamic checks The need for more 1 Better concurrency primitives Brief plug for 2 A C level module system CLAMP 3 Better error messages SEMINAL Research that needs doing and needs eager dedicated clever people 15 February 2005 Dan Grossman 46 Clamp Clamp is a C like Language for Abstraction Modularity and Portability it holds things together Go beyond Cyclone by using a module system to encapsulate low level assumptions e g e Module X assumes big endian 32 bit words e Module Y uses module X e Do need to change Y when port Similar ideas in Modula 3 and Knit but no direct support for the data rep levels of C code Clamp doesn t exist yet there are many interesting questions 15 February 2005 Dan Grossman 47 Error Messages What happens 1 Aresearcher implements an elegant new analysis in a compiler that is great for correct programs 2 But the error messages are inscrutable so the compiler gets hacked up e Pass around more state e Sprinkle special cases and strings everywhere e Slow down the compiler e Introduce compiler bugs Recentl
7. Type Safety Concurrency and Beyond Programming Language Technology for Reliable Software Dan Grossman University of Washington 15 February 2005 PL for Better Software e Software is part of society s critical infrastructure Where we learn of security lapses bboards tech news business page front page e PL is uniquely positioned to help We own The build process and run time Intellectual tools to prove program properties e But solid science engineering is key The UMPLFAP solution is a non starter Crisp problems and solutions Use My Perfect Language For All Programming 15 February 2005 Dan Grossman 2 Better low level code My focus for the last n years bring type safety to low level languages e For some applications C remains the best choice Explicit data representation Explicit memory management Tons of legacy code e But C without the dangerous stuff is too impoverished No arrays threads null pointers varargs e Cyclone a safe modern language at the C level A necessary but insufficient puzzle piece 15 February 2005 Dan Grossman 3 Beyond low level type safety 0 Brief Cyclone overview Synergy of types static analysis dynamic checks example not NULL pointers The need for more example data races 1 Better concurrency primitives AtomCAML Brief plug for 2 A C level module system CLAMP 3 Better error messages SEMINAL
8. cated after atomic was entered in particular local variables like z e No need to log an address after the first time To keep logging fast only occasionally trim e Tell programmers non local writes cost more Keeping logging fast Simple resizing or chunked array 15 February 2005 Dan Grossman 33 Duplicating code Duplicate code so callees know to log or not e For each function f compile f atomic and f normal e Atomic blocks and atomic functions call atomic functions e Function pointers e g vtables compile to pair of code pointers Cute detail compiler erases any atomic block in _atomic 15 February 2005 Dan Grossman 34 Qualitative evaluation e Non atomic code executes unchanged e Writes in atomic block are logged 2 extra writes e Worst case code bloat of 2x e Thread scheduler and code generator must conspire e Still have to deal with I O Atomic blocks probably shouldn t do much 15 February 2005 Dan Grossman 35 Handling I O Buffering sends output is easy and necessary Logging receives input is easy and necessary And may as well rollback if the thread blocks But may miss subtle non determinism void f write file foo flushed read file fo0o0 void g atomic read won t see write read may see write Alternative receive after send in atomic throws exception 15 February 2005 Dan Grossman 36 Prototype e AtomCAML modified
9. e objects synchronized Solve the problem for high level PLs first 2 Amillion line system needs more modularity than no buffer overflows 3 Fancy types mean weird error messages and or buggy compiler Good news 3 new research projects 15 February 2005 Dan Grossman 18 Atomicity overview e Why atomic is better than mutual exclusion locks And why it belongs in a language e How to implement atomic on a uniprocessor e How to implement atomic on a multiprocessor Preliminary ideas that use locks cleverly Foreshadowing hard part is efficient implementation key is cheap logging and rollback 15 February 2005 Dan Grossman 19 Threads tn PL e Positive shift Threads are a C library and a Java language feature e But Locks are an error prone low level mechanism that is a poor match for much programming Java programs libraries full of races and deadlocks Java 1 5 just provides more low level mechanisms e Target domain Apps that use threads to mask I O latency and provide responsiveness e g GUIs Not high performance scientific computing 15 February 2005 Dan Grossman 20 Atomic An easier to use and harder to implement primitive void deposit int x void deposit int x synchronized this atomic int tmp balance tmp x balance tmp semantics semantics lock acquire release behave as if int tmp balance tmp x balance tmp
10. motivating us e For updates and other projects www cs washington edu research progsys wasp 15 February 2005 Dan Grossman 51
11. ping More locks more communication Fewer locks less parallelism 15 February 2005 Dan Grossman 41 What locks what There is little chance any compiler in my lifetime will infer a decent object to lock mapping More locks more communication Fewer locks less parallelism Programmers cant do it well either though we make them try 15 February 2005 Dan Grossman 42 What locks what There is little chance any compiler in my lifetime will infer a decent object to lock mapping When stuck in computer science use 1 of the following a 22905 Divide and conquer Locality Level of indirection Encode computation as data An abstract data type 15 February 2005 Dan Grossman 43 Locality Hunch Objects accessed in the same atomic block will likely be accessed in the same atomic block again e So while holding their locks change the object to lock mapping to share locks Conversely detect false contention and break sharing e If hunch is right future atomic block acquires fewer locks Less inter thread communication And many papers on heuristics and policies 15 February 2005 Dan Grossman 44 Related Work on Atomic Old ideas e Transactions in databases and distributed systems Different trade offs and flexibilities e Rollback for various recoverability needs e Atomic sequences to implement locks Bershad et al e Atomicity via restricted sharing ARGUS Rapid new
12. ses Can know by e Types precondition checked at call site e Flow new objects start unaliased e Else user should use a temporary the safe thing 15 February 2005 Dan Grossman Data race example struct SafeArr int len int arr pi 3 TT ip2t 5 4 if pl gt len gt 4 pl gt arr 4 42 pl p2 15 February 2005 Dan Grossman 14 Data race example struct SafeArr int len int arr pi 3 TT ip2t 5 4 III if pl gt len gt 4 kpl p2 pl gt arr 4 42 change p1 gt 1len to 5 change p1 gt arr 15 February 2005 Dan Grossman 15 Data race example struct SafeArr int len int arr pi 3 TT e NE a if pl gt len gt 4 kpl p2 pl gt arr 4 42 check p1 gt len gt 4 change p1 gt 1len to 5 write p1 gt arr 4 XXX change p1 gt arr 15 February 2005 Dan Grossman Lock types Type system ensures For each shared data object there exists a lock that a thread must hold to access the object e Basic approach for Java found many bugs Flanagan et al Boyapati et al e Adaptation to Cyclone works out See my last colloquium talk March 2003 But locks are the wrong thing for reliable concurrency 15 February 2005 Dan Grossman 17 Cyclone summary Achieving memory safety a key first step but 1 Locks for memory safety is really weak applications always need to keep multipl
13. ut eo ea Bae Eee od e Downcast via run time check often avoided via flow analysis 15 February 2005 Dan Grossman Example FILE fopen const char const char int fgetc FILE int fclose FILE void g FILE f fopen foo r int C while c fgetc f EOF fclose f e Gives warning and inserts one null check e Encourages a hoisted check 15 February 2005 Dan Grossman A classic moral e Richer types make interface stricter e Stricter interface make implementation easier faster e Exposing checks to user lets them optimize e Can t check everything statically e g close once 15 February 2005 Dan Grossman 10 Key Design Principles in Action e Types to express invariants Preconditions for arguments Properties of values in memory e Flow analysis where helpful Lets users control explicit checks Soundness aliasing limits usefulness e Users control data representation Pointers are addresses unless user allows otherwise e Often can interoperate with C safely just via types 15 February 2005 Dan Grossman 11 It s always aliasing But can avoid checks when compiler knows all aliases Can know by e Types precondition checked at call site e Flow new objects start unaliased e Else user should use a temporary the safe thing 15 February 2005 Dan Grossman It s always aliasing But can avoid checks when compiler knows all alia
14. y fixed a dangerous bug in Cyclone resulting from not type checking e gt f as e f 15 February 2005 Dan Grossman 48 A new approach e One solution 2 checkers trust the fast one use the other for messages Hard to keep in sync slow one no easier to write e SEMINAL use fast one as a subroutine for search Human speed 1 2 seconds Find a similar term with holes that type checks e Easier to read than types e Offer multiple ranked choices e Example e1 e2 e3 doesn t type check but f el e3 does and f el e2 gt f00 e3 does e Help PL compilers Al HCI Searching for Error Messages in Advanced Languages 15 February 2005 Dan Grossman 49 Summary e We must make it easier to build large reliable software Current concurrency technology doesn t Current modules for low level code doesn t Type systems are hitting the error message wall e Programming languages research is fun Ultimate blend of theory and practice Unique place in tool chain control Core computer science with much work remaining 15 February 2005 Dan Grossman 50 Acknowledgments e Cyclone is joint work with Greg Morrisett Harvard Trevor Jim AT amp T Research Michael Hicks Maryland Thanks Ben Hindman for compiler hacking e Atomicity is joint work with Michael Ringenburg Thanks Cynthia Webber for some benchmarks Thanks Manuel Fahndrich and Shaz Qadeer MSR for
Download Pdf Manuals
Related Search