Progress of Concurrent Obiects with Partial methods Hongjin Liang and xinyu feng Nanjing University UStC
Progress of Concurrent Objects with Partial Methods Hongjin Liang and Xinyu Feng Nanjing University & USTC
acquire t What are good locks? as objects with partial methods? lock released Safety Functionality linearizability Progress Wait-freedom(wFy Lock-freedo LF) Starvation-freedom(SF) None applies! Deadhock-freedom(DF)
What are good locks? lock_acquire() { … } lock_release() { … } as objects with partial methods? None applies! Safety & Functionality: linearizability Progress: Wait-freedom (WF) Lock-freedom (LF) Starvation-freedom (SF) Deadlock-freedom (DF)
Not all locks are equally good
Not all locks are equally good!
Example: Test-and-Set (TAs)locks TAS locks acq i Tickets local succ. succ: false while(! succ i succ: =cas(L, 0, 1): re Unfair!
Example: Test-and-Set (TAS) locks acq() { local succ; succ := false; while( ! succ ) { succ := cas(L, 0, 1); } } rel() { L := 0; } TAS locks Tickets Unfair!
Example: Ticket locks acqot local i i: =getAndInc( next ) Fair! Whle(i!= serving)旮; relot serving: =serving+ 1;] Ticket locks serving next De 2 0 Queue management in banks
Example: Ticket locks Ticket locks Queue management in banks acq() { local i; i := getAndInc( next ); while( i != serving ) {} ; } rel() { serving := serving + 1; } next serving i Fair!