Popular in Course
verified elite notetaker
Popular in Computer Information Technology
verified elite notetaker
This 75 page Class Notes was uploaded by Kathleen Cartwright on Monday September 28, 2015. The Class Notes belongs to CIS700 at University of Pennsylvania taught by Staff in Fall. Since its upload, it has received 21 views. For similar materials see /class/215375/cis700-university-of-pennsylvania in Computer Information Technology at University of Pennsylvania.
Reviews for CIS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/28/15
Goal SDIMS A Scalable Distributed Information Management System Vm39un Singlml I A Distributed Operating System Backbone gt Informatlon collectlon and mana emen I Core functionality of large distributed systems gt Monitor query and react to changes in the system gt Examples syst administration and management Flle location service 5ervlce placement and location Multlcast tree construction sensor monitoring and control Naman and request routing Dlst rlbuted DenlaIaf rvice attack detection I Benefits gt Ease development ot new services gt Facilitate deployment gt Avold repetition ot same task by ditterent services gt Optlmlze system performance Contributions SDIMS Outline I Provides an important basic building block gt Informatlon collectlon and management I Satisfies key requiremen s gt scalability Wlth bath nodes and at l rlbutes Leverage bistributed Hash Tables DHT gt Flexlblll l y Enable applications to control the aggregation Pravlde flexlble API install update and probe r Autonomy Enable admlnls lratars to control flow of lnfarmatlan Build Autonomous DHTS gt Robustness Handle fallures gracefully Perform reaggregation upon fallures Lamby derouln ond ondeniond optional I SDIMS a distributed operating system backbone I Aggregation abstraction I Our approach eslgn gt Proto gt simulation and experimental results I Conclusions Outline Aggregation Abstraction Astrolabe VanRenesse et aI TOCS 03 a fcd A 2 Attributes WCJHA gt Information at machines I Aggregation true V A gt Physlcal nodes are leaves 2quot quot a 1 2 gt Each virtual node represents a logical group ot nodes Admlnlst ratlve domains groups wl l rlln domains etc I Aggregation function f for attribute A c tes the aggregated value A tor levell subtree AL locally stored mlue at the physical node or mu 39 Z A H AH for vlrtual node wlth k chlldren gt Each vlrtual node ls slmulated by one or more mach Ines I Example Total users logged in the system gt Attrlbute numUsers gt Aggregation Function Summation I SDIMS a distributed operating system backbone I Aggregation abstraction I Our approach gt Deslgn gt Proto gt simulation and experimental results I Conclusions Scalability with nodes and attributes Building aggregation trees Exploit DHTs I To be a basic building block SDIMS should support Tran S gt Appllcatlons wlth a large number of attrlbutes Example Flle locatlon system Each le is an ol lribule or 2 number of ol lribules L Challenges build aggregation trees in a scalable way gt Bulld multlple trees 5lngle free for all n rlbutes land Imbalance gt Ensure small number of chlldren per node n the tree educes mnxlmum node stress DHT can be vlewed as multlple aggregatlon trees olstrlbuted Hash Tables DHTs gt Each ed an ID from large space 160bp gt For each pre x k each node has a Ilnk to another node alahing k bits l matching on the m bit Paslrv TopeslrvC1NCHURD SkipNe r ele ness ere A DHT can be vlewed as a mesh of trees gt Routes from all nodes to a parttcular key form a tree gt leferent trees for dlfferent keys DHT trees as aggregation trees DHT trees as aggregation trees Key 111 000 100 010 110 001 101 011 111 I Keys 111 and 000 000 111 00x 11x Oxx lxx 000 100 010 110 001 101 011 111 API Design Goals Design of Flexible API I Expose scalable aggregation trees from DHT b Flexi ility Expose several aggregation mechanisms gt Attrlbu les Wl lh dlfferen l realismwrite ratlos quotL PU land chnn as often Aggregale on every arile v loo much quotNumL FUsquot changes rarely a Aggregale on re d gt Spatlal and temporal heterogenelty Nonunlfom and chan lng readtowmte rates acrog tree Example a multtcast sesslan wtth changlng nembershlp Support sparse attributes of same functionality efficientl gt Examples flle Ioca llon multlcast etc gt Not all nodes are Interested In all attrlbu les attribute gt Attrlbute attrlbute type attrlbute name gt Example type flleloca llonquot me lleFooquot Install an aggregation function for a t gt Amortlze lnstallatlon cost across attrlbutes of same type gt Arguments up and dawn control aggregatlon on update I Up ate the value of a particular attribute gt Aggregatlon performed accordlng to u and d wn gt Aggregatlon along tree Wlth keyshashmttrlbute I Probe for an aggregated value at some level gt If regulred aggregatlon done to produce thls result gt Two modes oneshot and contlnuous I New abstraction separate attribute type from name Scalability and Flex y Scalability and Flex y I Insta time aggregation and propagation strategy gt Applications can specify up and down Examples UpdateLocal 0 ime 14 i UpdateAll ALL WALL ime I Spatial and temporal hetero eneity gt Applications can exploit continuous mode in probe API with ex I time to ropagate for a fixed time gt Also implies scalability With sparse attributes I Insta time aggregation and propagation strategy gt Applications can specify up and down Examples UpdateLocal 11 aux0 I Spatial and temporal heterogeneity gt Applications can exploit continuous mode in probe API o propagate agg egate mlues to only interested nodes i e to ropagate for a fixed time gt Also implies scalability With sparse attributes Scalability and Flex y Scalability and Flex y I Install time aggregation and propagation strategy gt Applications can specify up and down gt Examp es Update acal we dew0 UpdateAll upAll dawmALl U dateU T39 pqul lf ime h I Spatial and temporal heterogeneity gt Applications can exploit continuous mode in probe API with ex i time to propagate for a fixed time gt Also implies scalability With sparse attributes I Install time aggregation and propagation strategy gt Applications can specify up and down gt Examples UpdateLocal 0 d 0 To propagate aggregate m u with expi time to propagate for a fixed time gt Also implies scalability With sparse attributes Scalability and FlexIb ty Autonomy I Insta time aggregation and propagation strategy gt Applications can specify up and down gt Examp es UpdateLocal d WALL ime I Spatial and temporal heterogeneity gt Applications can exploit continuous mode in probe API To propagate agg egate values to only interested nodes me to ropa with x ivy ti p gate for a finite time gt Also implies scalability With sparse attributes I Systems spanning multiple administrative domains gt Allow a domain administrator control information flow Prevent external observer from observing the information in the domain Prevent external failwes from affecting the operations in the domain gt Support for efficient domain Wise aggregation I DHT trues might not con orm I Autonomous DHT Outline Prototype and Evaluation I SDIMS a distributed operating system backbone I Aggregation abstraction I Cor approac gt Leverage Distributed Hash Tables gt Separate attribute type from name gt Flexible API gt Prototype and evaluation I Conclusions I SDIMS prototype gt Bull l on top or Freepagtry Druschel et al Rlce up gt Two layers Bottom AutonomoustT Top Aggregation Management Layer I Methodology gt Prototype Mlcr abenchmwks an PMI networks PlonMLob c5 bepmmenl Simulation Results Scala ty Simulation Results Flexib39 ity Methodology a Sparse omoales malnemsessaons am 3de size membership r Node stress AM at incoming and ongoing into Two paln ls gt Max Node Stress on order or mognmde less man Asnoiooe gt Max Node Stress deereoses osthe namoer otnodes increases 1907 Astrolabe 65536 Astrolabe 4056 Astrolabe 256 39 sDIMs 256 1906 100000 Node Stress 10000100 100 1000 Number of sessions I Simulation with 4096 nodes I Attributes with different up and down strategies 1m g Update UpdateLocal 3 1m Up5 1m downo g Upa 1 quotdown5 E UpdateUp g M nm1 am 1 1m 1m momma Prototype Results Conclusions I CS department 180 machines 283 SDIMS nodes I PlanetLab 7O machines Depaltment Netwulk Manet Law 39 I l E Latency ins E E a Updae m Updae up Update meg Update m I SDIMS basic building block for largerscale distributed service gt Provldes lnforma llon collection and management Our Approac gt scalability and Flexlblll l y through Leveraging s separating attribute type from attribute mme Providing flexlble API install update and probe Default lazy reaggregation Optional ondemand reaggregation Game Theoretic Learning Regret Minimization vs Utility Maximization Amy Greenwald with David Gondek Amir Jafari and Casey Marks Brown University University of Pennsylvania November 17 2004 Background No external regret learning converges to the set of minimax equilibria in zero sum games eg Freund and Schapire 1996 No internal regret learning converges to the set of correlated equilibria in generalsum games eg Foster and Vohra 1997 Foreground 1 Definitions 0 A continuum of no regret properties called no CD regret o A continuum of game theoretic equilibria called lt1gt equilibria 2 Existence Theorem 0 Constructive proof No CDregret learning algorithms exist VCID 3 Convergence Theorem 0 No lt1gt regret learning converges to the set of lt1gt equilibria VCD 4 Surprising Result 0 No internal regret is the strongest form of no lt1gt regret learning 0 Therefore no no CD regret algorithm learns Nash equilibria Outline 0 Game Theory 0 Single Agent Learning Model 0 Multiagent Learning amp Game Theoretic Equilibria Game Theory A Crash Course 1 General Sum Games 0 Nash Equilibrium o Correlated Equilibrium 2 Zero Sum Games 0 Minimax Equilibrium An Example Prisoners Dilemma C D 0 44 05 D 50 11 C Cooperate D Defect One Shot Games A one shot game is a 3 tuple I I Ahm ej where o I is a set of players 0 for all players 2 E I a set of pure actions AZ with ai E A a reward function n A gt R where A H Ai with a e A 23961 One Shot Games A one shot game is a 3 tuple I IAzmi 1 where o I is a set of players 0 for all players 2 E I a set of pure actions AZ with ai E A a reward function n A gt R where A 2 HM Az with a e A The players can employ randomized or mixed actions 0 for all players 2 E I a set of mixed actions Q Qi E RAil Z qij 1 amp qzj 2 OVj With qi E an expected reward function n Q gt R where Q Hie Q with q E Q St riq ZaeAqaria Nash Equilibrium Notation Write CL 1304 E A for Li E 14139 and CL E A4 HEM Aj Write q QuQ D E Q for 1239 E Qi and Q z39 E Q z Hj7 iQi Definition A Nash equilibrium is a mixed action profile q st mq 2 r q qii for all players 1 and for all mixed actions qi E Qi Theorem Nash 51 Every finite strategic form game has a mixed strategy Nash equilibrium Correlated Equilibrium Chicken L R T 66 27 B 72 00 CE L R T 12 14 B 14 0 max 127139TL 97TTR 97139BL OWBR subject to WT 7TTR 7TBL 7TBR 1 7TTL77TTR77TBL77TBRZ 0 67TLT 27TRT 77TLB 07TRB 67TTL 27TBL 77TTR 0WBR 77TLT 07TRT 67TLB 27TRB 77TTL 0WBL 67TTR 27TBR Correlated Equilibrium Chicken L R T 66 27 B 72 00 CE L R T 12 14 B 14 0 max 127139TL 97TTR 97139BL OWBR subject to WT 7TTR 7TBL 7TBR 1 7TTL77TTR77TBL77TBRZ 0 67 TL 27 TR 77 BL OWBR 67 TL 27 BL 77 TR O7TBR 77 TL 07 TR 67 BL 27TBR 77 TL 07 BL 67 TR 27TBR 10 Correlated Equilibrium Definition A mixed action profile q e Q is a correlated equilibrium iff for all bure actions jk 6 Ai 2 1070 0 Mia i ha 239 Z 0 1 017161471 Observe Every Nash equilibrium is a correlated equilibrium gt Every finite normal form game has a correlated equilibrium 11 Zero Sum Games Matching Pennies H T H 11 17 1 T 1 1 11 Rock Paper Scissors Ziejl a O for all a e A Emma c for all a E A for some 0 e R 12 Minimax Equilibrium Example L R T 1 2 B 4 3 Definition A mixed action profile 143 6 Q is a minimax equilibrium in a two player zero sum game iff O 01qu r10 13 W E A1 0 S l2Q7k E A2 13 Single Agent Learning Model 0 set of actions N 1n o for all times t mixed action vector qt 6 Q q e 1R Ziqi 1 amp qi 2 OVz pure action vector at 6139 for some pure action 2 reward vector rt 2 r1 rn 6 01 A learning algorithm A is a sequence of functions qt Historyt1 gt Q where a History is a sequence of action reward pairs a1r1 a2r2 14 Transformations Mixed Transformations CDLINEAR 1Q gt Q the set of all linear transformations the set of all row stochastic matrices cpSWAP Q gt Q g1 deterministic C CDLINEAR Pure Transformations fSWAp F I N gtN the set of all pure transformations 15 Isomorphism The operation of elements of J quotSWAP on N g the operation of elements of CDSWAP on Q ij 6Fz j 2 V ka eFk 3 Example Ifn4 and F1l gt22l gt33l gt44l gt 1 then l OOO CDCDCDI OOl O Ol OO v for 8 ltq17q2q3q4gt E Q 16 ThUS Q1Q2Q3Q4gt Q4Q1Q2Q3 External Regret Matrices fEXT Fj E FSWAPlj E N1Where F70 2 7 CIDEXT W E CDSWAPlj E N Where 616 ej Example If n 4 then GOO GOO 2 OOOO I I I H C C ThUS Q1Q2Q3Q4gt 0100gt for 3 Q1Q2Q3Q4gt E Q 17 Internal Regret Matrices 71NT Fij E fSWAPW E N Where FijW j if k 2i k otherwise H e39 if 1 Ii 2 w w 9 cpINT gb E CDSWAPIU E N Where 6W ek otherwise Example If n 4 then 1 O O O 23 O O l 0 lt1 O O 1 O O O O l ThUS lt917Q27Q37Q4gt 291707Q2Q3aq4gt1f0r 3 lt917Q27Q37Q4gt E Q 18 Regret Vector p 6 Rd Observed Regret Vector ra r aqb r a Expected Regret Vector rq Ep r a a N q p r7Ea a N q r 41 r q No Observed Regret limsuptgo zi q wiw g 0 for all qb 6 CD as No Expected CD Regret lim SUIth 21 r7q7 g 0 for all qb 6 CD 19 Approachability U g V is said to be approachable iff there exists learning algorithm A q1q2 st for any sequence of rewards r1r2 lim dU t lim inf dupt 0 t gtoltgt t gtoou U as where t denotes the average value of p through time t A ltlgt no regret learning algorithm is one whose observed regret approaches the negative orthant RE 20 Blackwell39s Theorem The negative orthant R is approachable iff there exists a learning algorithm A q1q2 st for any sequence of rewards r1r2 prt17qt1 39 33 S 0 4 for all times t where x maxx0 Moreover this procedure can be used to approach the negative orthant RE 0 if t 6 Rf play arbitrarily o if t 6 VRigt play according to A 21 Regret Matching Algorithm Given CID Given Y E R3 If Z Y 0 play arbitrarily If Z Y gt 0 define stochastic matrix Z dgt 53 A E AltIgtY ltb dgt Yltb 5 play mixed strategy q qA Regret Matching Theorem Regret matching satisfies the generalized Blackwell condition p7a7Q Z O 22 Proof p01 1 Y Zp nqY 6 gtEdgt ZTq TqY 7 gtEdgt 7quot gm m 8 gtEdgt TltqZ Y qZY gt 9 gtE gtEdgt Z gte Y gt 2 Kb 739quot ltq q 10 Z gt Z gtE Y ZY TqA q 11 ZY Tltq q lt12 13 H m 9 23 Generic Regret Matching Algorithm CDg fort1 1 2 3 4 7T play mixed strategy qt realize pure action 239 observe rewards rt for all d E Cb compute instantaneous regret observed p E p rt7 61 rt aid rt ei expected pal E p rt7 qt 2 rt qt rt qt update cumulative regret vector X X 1 p compute Y gXt 2429b Y compute A Y dzedgt solve for the fixed point qH39l qH lA 24 Special Cases of Regret Matching Foster and Vohra 97 CDINT Hart and Mas Colell OO CIDEXT Choose GX zkX2 so that gkX X Freund and Schapire 95 CDEXT Cesa Bianchi and Lugosi O3 CDINT Choose GX In 2k enXk so that gkX enXk 2k enXk 25 Multiagent Model 0 a set of players I z e I o for all players 2 a set of pure actions AZ with ai e A a set of mixed actions Q with qi E Q a reward function m A gt 01 where A HiAi with a e A an expected reward function n Q gt 01 where Q HiQi With q E Q S t r q ZaeA qar a a set an qbi 6 Chi 26 ClD Equilibrium An mixed action profile q e Q is a ClD eduilibrium iff ri q g mq for all players 139 and for all or 6 Chi Examples Correlated Equilibrium Chi CDINT for all players 139 Generalized Minimax Equilibrium Chi CDEXT for all players 139 27 Convergence Theorem If all playersi play via some no clgtZgt regret algorithm then thejoint empirical distribution of play converges to the set of CID equilibria almost surely Proof For all players 139 for all gbi 6 Chi limsupriwmtn Mzt 14 t gtoo 1 t 1 t nmsup Z r aa Z Ma aii lt15 t gtOO t 721 t 721 g o 16 almost surely 28 Zero Sum Games Matching Pennies H T H 11 1 1 T 1 1 11 Rock Paper Scissors 29 Matching Pennies Weights Frequencnes NER exponential n 0037233 Matching Pennies NER exponential n 0037233 Matching Pennies 1 i i i i 1 i i i i 7 Player 1 H 7 Player 1 T 7 Player 2 H 5 7 Player 2 T c 07 D 3 O39 2 u E e 395 E uJ Player 1 H Player 1 T Player 2 H Player 2 T 0 200 400 600 800 1000 0 200 400 600 800 1000 Time Time 3O Rock Paper Scissors Weights Frequencies 1 NER polynomial p 2 Rock Paper Scissors 1 NER polynomial p 2 Rock Paper Scissors U f i 0399 7 mayerlzg 7 ayer i i W firm o 7 ayer 07 i i J 0397 7 Player 2 P 7 Player 2 8 06 1 i i i 80 ii iii ii 04 if M 0 i D 03 i I Hi i E0 i i i i L 02 i i i 02 01 i i i 01 i i ii iii O0 2000 4000 T I 6000 8000 10000 4000 T 6000 8000 10000 me me 31 General Sum Games Shapley Game Correlated Equilibrium 32 Shapley Game No Internal Regret Learning Empirical Frequency Frequencies NIR polynomial p 2 Shapley Game Player 1 Player 1 Player 1 Player 2 Player 2 Player 2 marw a 4000 6000 Time sdoo 1 0000 NIR exponential n 0014823 Shapley Game 7 Player1T 7 Player 1 M 7 Player1 B 39 Player 2 L 7 Player 2 C 7 Player 2 R 0 oo Empirical Frequency 00 2000 4000 6000 8000 1 0000 Time 33 Shapley Game No Internal Regret Learning Joint Frequencies NIR polynomial p 2 Shapley Game NIR exponential n 0014823 Shapley Game 0 oo 0 0 Empirical Frequency 2 9 Empirical Frequency 0 2000 4000 6000 Time 34 Shapley Game No External Regret Learning Empirical Frequency Frequencies NER polynomial p 2 Shapley Game Player 1 T Player 1 M Player 1 B Player 2 L Player 2 C Player 2 R 9 2000 4000 6000 Time sdoo 1 0000 NER exponential n 0014823 Shapley Game 7 Player 1 T 7 Player 1 M gt 08 7 Player 1 B 39 g 7 Player 2 L g 7 Player 2 C Equot 06 7 Player 2 R u E 2 5 E u 00 2000 4000 6000 8000 1 0000 Time 35 Summary 0 No external and no internal regret can be defined along one continuum no CD regret o No CD regret learning algorithms exist VCID o No lt1gt regret learning converges to the set of lt1gt eduilibria VCD 0 No internal regret learning is the strongest form of no CD regret learning Therefore Nash equilibrium cannot be learned via no CD regret learning 36 A little rationality goes a long wayquot Hart 03 Regret Minimization vs Utility Maximization 0 RM is easy to implement 0 RM justifies randomness in actions 0 Can RM be used to explain human behavior 37 Runtime Atomicity Analysis of Multithreaded Programs Focus is on the paper Atomizer A Dynamic Atomicity Checker for Multithreaded Programs by C Flanagan and S Freund presented by Sebastian Burckhardt University of Pennsylvania C18 700 Runtime Verification Seminar Wednesday October 20 2004 Outline of talk Verification of multithreaded programs in general Atomizer the core concepts Dynamic analysis Reduction Lock set algorithm Atomizer the improvements Atomizer evaluation 3 Correctness of Multithreaded Programs Multithreaded means concurrent communication by shared memory Reasoning quite challenging even for experts Typically programmers use fairly lowlevel synchronization primitives Mutex Locks Semaphores Monitors repopularized by Java To make it worse performance matters othenNise why bother with multiple threads Nondynamic verification We won t talk about these today Restrict design space type systems specialpurpose languages Design paradigms Static analysis Lexical Control flow Data flow Checking concurrent executions Problem number of possible concurrent executions very large Approach Check them all means model check the concurrent model not practical without heavy abstraction Approach ll Checkjust one this is the regular testing method Approach Hi Check one and extrapolate look for bad things that could happen g What are the bad things we can look for Deadlock Races Definition of race Two threads are allowed to access same variable at the same time and at least one access is a write View inconsistency intuitive description grouping of variables inconsistent among threads Lack of atomicitv What are we looking for Deadlock look for inconsistent order of lock acquisition Races look for variables that aren t consistentlv protected by some lock by tracking locks held during each access eg Eraser Lockset alg View inconsistency track variable sets associated which each lock eg in JPaX JNuke Atomicity Reductionbased eq Atomizer Block based eg WangStoller s tool Atomicity Checking Advantages Can find bugs that are resistant to regular testing and race detection Good correspondence with programming methodology easy to understand the idea can verify interfaces encouraging code reuse programmer can gain confidence in code by validating atomicity assumptions Scalable has been applied to gt100k lines of Java code 9 Example javaangStringBuffer public final class StringBuffer public synchronized StringBuffer appendStringBuffer sb int len sblength sbgetCharsO len value count public synchronized int length public synchronized void getChars mQ Example javaangStringBuffer public final class StringBuffer public synchronized StringBuffer appendStringBuffer sb int len sblength another thread can modify sb here gt len is no longer the correct length of len but there is no race sbgetCharsO len value count public synchronized int length public synchronized void getChars Definition A block of code is atomic if for every legal execution of the program there is an equivalent legal execution within which the entire block executes without preemption Executions are equivalent iff the dynamic instruction stream per thread is iden cal the same read reads the value of the same write umgm How does it work 1 Identify blocks that are supposed to be atomic use heuristics exported methods synchronized methods synchronized blocks allow user annotations can turn off the checking if there are false bugs can do additional checks by declaring atomic atomic void getChars a gm How does it work 2 Perform instrumentation on the source code level could also be done at the bytecode level lnstrumented source code produces event stream during execution Analyze event stream online Atomizer or off line For each block that is supposed to be atomic check whether there is an equivalent execution in which it is scheduled contiguously Erma How does it work 3 We can t possibly check all possible executions to find an equivalent atomic one Idea Find a large class of instruction sequences for which we can always guarantee that it can be shuffled into an uninterrupted sequence by local painNise swaps Then warn user if supposedly atomic block does not belong to this class gt Lipton s theory of reduction 1975 umgm Semantic model Dynamic instruction stream of each thread consists of 4 types of instructions rdxv wrxv aCQm relm read value v from shared var x write value v to shared var x acquire lock m release lock m mg Leftmovers Can always swap an relm with an interleaved instruction j1 of another thread to its left Call this a leftmover i0 relm i2 i0 relm i2 1011 12 dgt 10 km 12 Reason can always release lock earlier readwrite matching not affected by move Rightmovers Can always swap an acqm with an interleaved instruction j1 of another thread to its right Call this a rightmover i0 jO aCClm j1 i2 Reason lock is still available j1 can not be acqm readwrite matching not affected by move qgt i0 acqm i2 jO j1 Neither rdxv nor wrxv can in general be swapped with an adjacent interleaved instruction of another thread Call them Nonmovers nonmovers rd xv wrxv wrxv rd xv wrxv rd xv wrxv wrxv Bothmovers If an access rdxvwrxv goes to a variable protected by a lock which is held by this thread it is a bothmover acqm rdxvj1 relm Reason j1 can not be an access to x Suppose for now we know which locks can protect a variable Emu Lipton s Reduction Let s denote the instructions as follows L for leftmover R for rightmover N for nonmover B for bothmover Then any execution sequence matching the following regular expression is equivalent to an atomic one R B N 8 L B Examples RL RBL NLLLB RNL BBB But not NN LR zi Example Say the method COPSV public class A private int x y public synchronized void copy Y X more methods produces the dynamic instruction stream acqm rdx4 wry4 rem is it atomic For now assume all methods of class A are synchronized 22 Example acqm rdx4 b1 b2 wry4 rem b3 acqm rd x4 wry4 b1 b2 rem b3 acqm rdx4 wry4 rem b1 b2 b3 Emu Implementation Can efficiently check if blocks match R B N a L B by using an online automaton Problem to classify variable accesses correctly we need to know which locks protect which 24i Which locks with which field fields may not be protected by this object s lock public class A2 private int Xy public synchronized swap int 2 y y X X 2 public int getX return X public int getY return y field may be protected by a different object s lock public class A2 private int Xy Integer mylock new lntegerO public copy SYnchronizedmylock y X public int getX synchronizedmylock return X public int getY synchronizedmylock return X 25 Basic Eraser lockset algorithm Argue If a variable is consistently protected by some lock this lock must be held during all accesses to that variable Dynamically we can look at the set of locks helds during each access so far and keep track of their intersection If the intersection is empty there seems to be no consistent locking discipline classify access as a nonmover OthenNise there seems to be a consistent locking discipline classify access as a bothmover What about reclassifying accesses if changes occur during runtime can t be done online but could be done offline 25 Improve Classification 1 Avoid flagging some classic safe usages threadlocal variables need no lock to protect them initialization one thread initializes my thread W data then passes it to another thread threadlocal from rst thread rw second thread rw second thread rl other thread wrrte other thread read any thread read there on any thread write Write once read many times Track state for each field use lock set for classification only if in state Shared Modified Emu Improve Classification 2 Reentrant locks reentrant acquires and releases are bothmovers Redundant locks if a lock is only accessed by one thread it is redundant threadlocal locks if lock B is always held while accessing lock A lock A is redundant protected locks redundant acquires and releases are bothmovers can classify locks using the same lockset and threadaccess algorithms as for fields 28 Improve Classification 3 Benign readwrite races public class A2 private int X public int read return X synchronized void inc X x l read and inc are atomic more or less track separate lockset containing locks held during all writes superset of locks held during all accesses classify read as bothmover if current thread holds a write lock even if accessprotecting lockset is empty Emu It s not that easy Unsynchronized reads and writes are not atomic if more than 32 bit quantity more rules exists eg volatile vs nonvolatile are not guaranteed to proceed in order only synchronization events are sequentially consistent memory model relative to hardware is specified memory model of hardware is not specified does anybody know does Atomizer need adjustments for non sequentially consistent machines Evaluation Nam Nun Max Nam Base Atomizer Atornicity Benchmark Lines Threads Locks 1601511616 LockSetPairs Time s Slowdown Warnings Errors elevator 529 5 8 1 17 1114 2 0 11660 29948 26 385 3 728 836 4 1 tsp 706 10 2 1 5 094 482 7 0 sor 17690 4 1 1 2 070 73 0 0 rnoidyn 1291 5 1 1 2 362 118 0 0 rnonterario 3557 5 1 1 2 794 22 1 0 raytracer 1859 5 5 1 7 596 366 1 1 mtrt 11315 6 7 2 7 233 464 6 0 jigsaw 90100 53 706 31 4531 1349 47 34 1 specJBB 30490 10 262000 6 340088 1801 112 4 0 webi 22284 5 402445 3 452685 6035 19 0 libjava 75305 39 816617 6 986855 965 19 4 Warnings Effect of improvements 140 I I I I elevator I hedc x 120 x sor quotHE moldyn I 100 montecarlo e x raytracer 0 mtrt 439 80 jigsaw a specJBB v i webl libjava o 60 A 40 h 39 20 quotu 3939 39nq I 0 A T Basic reentrant thread local threadlocal protected Writeprotected locks locks locks 2I locks data 32 Atomizer paper contributions Concise review of concepts Formal semantics for multithreaded programs Reduction idea Lockset alqorithm Description of the algorithm and some improvements Formal description of the algorithm formulation of theorem describing its correctness in provable detail Mentions optimizations handle reentrant locks threadlocal locks protected Locks writeprotected data Experimental evaluation of the tool performance scale usabilitv 33 lll E E Bibliography C Artho K Hayelund and A Biere High level data races In The First International Workshop on Veri cation and Validation of Enterprise Infor mation Systems VVEIS OS April 2003 Cormac Flanagan and Stephen N Freund Atomizer a dynamic atomic ity checker for multithreaded programs In Proceedings of the gist ACM SIGPLAN SIGACT symposium on Principles of programming languages pages 2567267 ACM Press7 2004 Richard J Lipton Reduction a method of proving properties of parallel programs Commun ACM 181271777217 1975 Stefan Savage Michael Burrows Greg Nelson Patrick Sobalvarro and Thomas Anderson Eraser a dynamic data race detector for multithreaded programs ACM Trans Compnt Syst7 154917411 1997 Liqiang Wang and Scott D Stoller Run time analysis for atomicity In Proceedings of the Third Workshop on Runtime Veri cation RV volume 892 of Electronic Notes in Theoretical Computer Science Elsevier 2003 Liqiang Wang and Scott D Stoller Runtime analysis of atomicity for multi threaded programs Technical Report DAR 04 27 State University of New York at Stony Brook July 2004 httpwwwcssunysbedu 1iqiang atomicityhtm1