Understanding Atomicity Violation in Concurrent Programs

 
Atomicity Violation Detection
 
Prof. Moonzoo Kim
 
CS492B Analysis of Concurrent Programs
Data Race Free, Yet Race Bug (1/2)
Atomicity Violation Detection, Prof. Moonzoo Kim
2
public class 
Vector 
implements
 Collection
 {
 int 
elementCount
 ;
 Object 
[]
 
elementData
 ;
 public
 Vector(Collection c){
  elementCount = c.size() ;
  elementData = 
new
 Object[elementCount] ;
  c.toArray(elementData) ; }
 public
 
synchronized
 
int
 size(){
  
return
 elementCount ; }
 
public
 
synchronized
 Object[] toArray(Object a[]){
  ...
  System.arraycopy(elementData, 0, a, 0, elementCount) ;
  ... }
 
public
 
synchronized
 
boolean
 add(Object o) {
   ...
  elementCount++; ...} }
 
Thread 1
Vector v2=new Vector(v1);
 
Thread 2
 v1.add(obj);
 
Data race free 
(protected by 
this
)
 
Should
be
executed
atomically
Data Race Free, Yet Race Bug (2/2)
Atomicity Violation Detection, Prof. Moonzoo Kim
3
Thread 1
Thread2
 
//v1.size()
lock(v1)
t=v1.elementCount// 10
unlock(v1)
v2.elementCount=t
v2.elementData=new Object[10]
 
 
 
 
 
 
//v1.toArray()
lock(v1)
System.arraycopy(v1.elementData
 ,0,v2.elementData,0,
 v1.elementCount)
 
//v1.add()
lock(v1)
v1.elementCount++ // 11
unlock(v1)
 
Array out of bound error
 
Time-Of-Check to Time-Of-Use (TOCTOU) Attack
 
An attacker can exploit the race condition between the access and
open to trick the victim into reading/overwriting an entry in the
system password database.
http://en.wikipedia.org/wiki/Time_of_check_to_time_of_use
http://cecs.wright.edu/~pmateti/InternetSecurity/Lectures/RaceConditions/index.html
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
4
//a program installed setuid root
if (access(“/home/attacker/file”,“w”) != 0)
  exit(1) ;
 
 
 
fd = fopen(“/home/attacker/file”, “w+”);
// Do something about fd
 
Victim
//after the access check
symlink(“/etc/passwd”,
                “/home/attacker/file”);
 
Attacker
 
Atomicity
 
A code block is 
atomic
 if for every interleaved execution,
there is an equivalent execution with the same result
where the code block is executed serially 
(i.e., not
interleaved with other threads)
.
 
Programmers often assume the atomicity of a code
block to reason its behavior as if it is a sequential code.
c.f. atomic block: code block defined as atomic by
programmers
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
5
 
Atomicity Violation
 
An atomicity violation (atomicity bug) is a race bug that
violates the atomicity of an atomic block defined by
programmers
 
Atomicity violation detection techniques check 
if an
observed execution is equivalent to any serial execution
(i.e., serializable)
Reduction based technique
Access pattern based technique
Happens-before relation based techniques
 
 
 
 
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
6
 
Lipton’s Reduction (1/2)
 
An interleaved execution 
σ
 can be 
reduced
 to an equivalent
interleaved execution 
σ
 by swapping 
commuting
 operations.
Two operations 
a
 and 
b
 in 
σ
 
are 
commuting
 
if
a
 and 
b 
are executed by different threads, and
a 
is immediately followed by 
b, and
their execution orders 
do 
not
 change the resulting state
 in an
execution.
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
7
 
s
0
 
s
0
 
s
2
 
s
2
 
t1:
lock(m)
 
t2:
tmp=0
 
t1:
lock(m)
 
t2:
tmp=0
 
s
1
 
s
1
 
σ
:
 
σ
 
:
 
Lipton’s Reduction (2/2)
 
An operation 
p
 is 
right-mover
 if 
p
 commutes with the operation
that immediately follows 
p
 and executed by another thread
 
 
An operation 
p
 is 
left-mover
 if 
p
 is commutes with the operation
immediately followed by 
p
 , executed by another thread
 
 
An operation 
p
 is 
both-mover
 
if 
p
 is right-mover and left-mover at
the same time
non-mover
 
if p is neither right-mover nor left-mover.
 
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
8
 
Atomizer 
[Flanagan, POPL 04]
 
Atomizer checks 
if an observed execution 
σ 
can be reduced
to an equivalent serial execution 
σ
Atomizer
 
assumes that every public methods are atomic blocks
Note that, in a serial execution, executions of atomic blocks do not
overlap with each other.
 
Reduction rule
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
9
Serializable Execution Example
Atomicity Violation Detection, Prof. Moonzoo Kim
10
lock(X)
write(A)
read(A)
read(C)
write(B)
unlock(X)
lock(Y)
write(C)
read(B)
unlock(Y)
write(tmp)
Thread 1
Thread 2
lock(X)
write(A)
read(A)
read(C)
write(B)
unlock(X)
lock(Y)
write(C)
read(B)
unlock(Y)
write(tmp)
 
Thread 1
 
Thread 2
lock(X)
write(A)
read(A)
read(C)
write(B)
unlock(X)
lock(Y)
write(C)
read(B)
unlock(Y)
write(tmp)
 
Thread 1
 
Thread 2
Variable A and B are consistently guarded by lock X and Y, respectively
Variable C is not consistently guarded by any lock
 
Equivalent to
 a serial execution
Left
Right
Non-serializable Execution Example
Atomicity Violation Detection, Prof. Moonzoo Kim
11
lock(X)
unlock(X)
read(A)
read(C)
lock(X)
unlock(X)
lock(Y)
write(C)
read(B)
write(A)
write(tmp)
Thread 1
Thread 2
Variables A and B are consistently guarded by lock X and Y, respectively
Variable C is not consistently guarded by any lock
unlock(Y)
lock(X)
unlock(X)
read(A)
read(C)
lock(X)
unlock(X)
lock(Y)
write(C)
read(B)
write(A)
write(tmp)
 
Thread 1
 
Thread 2
unlock(Y)
unlock(X)
lock(X)
 
Not equivalent to any serial execution
Left
Right
lock(X)
unlock(X)
read(A)
read(C)
lock(X)
unlock(X)
lock(Y)
write(C)
read(B)
write(A)
write(tmp)
 
Thread 1
 
Thread 2
unlock(Y)
 
Atomicity Checking
 
Atomizer’s serializability checking with the reduction is the same
as checking if every transaction is in the following pattern:
 
[
Right-mover
]*  [
Non-mover
]
? 
[
Left-mover
]
*
 
 
e.g: Two-phase locking
 
lock(X)
 
  lock(Y)
       lock(Z)
       /* data accesses */
       unlock(Z)
     unlock(Y)
   unlock(X)
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
12
 
Expanding phase
 
Shrinking phase
 
L. Wang and S. D. Stoller: Runtime Analysis of Atomicity for Multithreaded Programs, IEEE TSE, 32(2), 2006
False Positive of Atomizer
 class 
Vector {
   Object [] elementData;
   int
 elementCount ;
   int
 size(){
 1: 
synchronized
(
this
){
 2:  
return
 elementCount;
 3: }
   }
   boolean
 contains(Object x){
    //atomic block begins
 4: 
int
 i=0;
 5: 
while(i < size()){
 6:  
synchronized
(
this
){
 7:   
if
(elementData[i].equals(x))
 8:    
return
 
true
;
 9:  }
10:  i++;
11: }
12: 
return
 
false
;
    //atomic block ends
   }
 }
Atomicity Violation Detection, Prof. Moonzoo Kim
13
1:lock(this)
2:read(elementCount)
3:unlock(this)
 
t1: 
contains(o1)
 
t2: 
contains(o2)
1:lock(this)
2:read(elementCount)
3:unlock(this)
1:lock(this)
2:read(elementCount)
3:unlock(this)
 
Detected as atomicity violation,
but “semantically” serializable
Unserializable pattern#4
Unserializable pattern#2
Unserializable pattern#3
Access Pattern Based Detection
Detect interleaved accesses on a shared variable that
match to 
non-serializable patterns 
as atomicity violations
Select 4 among total 8 patterns as buggy based on experiences in real-bugs
Atomicity Violation Detection, Prof. Moonzoo Kim
14
read(x)
read(x)
write(x)
write(x)
read(x)
write(x)
write(x)
write(x)
read(x)
read(x)
write(x)
write(x)
Unserializable pattern#1
S. Lu et al.: AVIO: Detecting Atomicity Violations via Access Interleaving Invariants, ASPLOS 2006
Unlike serial executions, first and
second read operations may see
different values
Intended data-flow from first
write to read operations may be
interfered by the second write
Read operation may see the data
before the update is completed
check-and-set in the left thread
may be interfered by right thread
False Negative of Access Patterns
Thread1(){
 //atomic block begins
 
synchronized
(X){
  a = 0 ; }
 
synchronized
(Y){
  b = 0 ; }
 //atomic block ends
}
Thread2(){
 //atomic block begins
 
synchronized
(X){
  a = 1 ; }
 
synchronized
(Y){
  b = 1 ; }
 //atomic block ends
}
Atomicity Violation Detection, Prof. Moonzoo Kim
15
lock(X)
write(
a,0
)
unlock(X)
t1: 
Thread1()
t2: 
Thread2()
lock(X)
write(
a,1
)
unlock(X)
lock(X)
write(
b,0
)
unlock(X)
lock(X)
write(
b,1
)
unlock(X)
 
a:1
, 
b:0
 
Velodrome 
[Flanagan, PLDI 08]
 
Velodrome defines happens-
before relation over atomic
block executions
 
Veldorome detects an
inconsistency in the happens-
before relation (i.e. cycle)
as an atomicity violation
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
16
 
Happens-Before in Transactions (1/3)
 
An 
execution
 is a sequence of operations
 
A 
transaction
 in an execution is the sequence of
operations in a thread, that correspond to an execution
of an atomic block
Users can specify where an atomic block starts/ends in code
 
An execution is 
serial
 if each transaction’s operation
execute contiguously, without interleaving
 
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
17
 
Happens-Before in Transactions (2/3)
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
18
 
Happens-Before in Transactions (3/3)
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
19
 
*  P. A. Bernstein et al., 
Concurrency Control and Recovery in Database Systems
,  Addison-Wesley, 1987
Example
Atomicity Violation Detection, Prof. Moonzoo Kim
20
lock(X)
write(
a
)
unlock(X)
t1: 
Thread1()
t2: 
Thread2()
lock(Y)
write(
b
)
unlock(Y)
lock(Z)
read(
c
)
unlock(Z)
lock(X)
read(
a
)
unlock(X)
t3: 
Thread2()
lock(Y)
read(
b
)
write(
c
)
unlock(Y)
Tr#1
Tr#2
Tr#3
lock(Z)
unlock(Z)
False Positive of Velodrome
Execution order of write operations on a variable without read
operations do not change result states, except for the last one
Atomicity Violation Detection, Prof. Moonzoo Kim
21
write(
a, 1
)
t1: 
Thread1()
t2: 
Thread2()
write(
a, 11
)
write(
a, 2
)
write(
a, 12
)
Tr#1
Tr#2
lock(X)
unlock(X)
lock(X)
unlock(X)
lock(X)
lock(X)
Thread1(){
 //atomic block begins
 
synchronized
(X){
  a = 1}
 
synchronized
(X){
  a = 2 ; }
 //atomic block ends
}
Thread2(){
 //atomic block begins
 
synchronized
(X){
  a = 11 ;
  a = 12 ; }
 //atomic block ends
}
 
View-Serializability (1/2)
 
Conflict-serializability 
(used by Velodrome)
An execution is conflict-serializable if there exists a serial execution s.t.
 (1) two executions have the same operations, and
 (2) for every pair of conflicting operations, the two operations have
       the same order in both executions
 
View-serializability
*
An execution is view-serializable if there exists a serial execution s. t.
(1) two executions have the same operations, and
(2) each read operation has the same write predecessor in both executions, and
         - The write-predecessor of a read operation is the last write operation
           on the variable that the read operation reads in an execution
(3) each variable has the same final write operation in both executions
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
22
 
*
L. Wang et al.: Accurate and Efficient Runtime Detection of Atomicity Errors in Concurrent Programs, PPoPP 2006
 
View-Serializability (2/2)
 
We can implement the view-serializability checking by modifying
the conflict definition
Two operations 
p
 and 
q
 in an execution 
conflict
 if
these access the same variable where
p
 is writing, and 
q
 is reading, or
q
 is the final write operation on the variable in the
execution
these operate on the same lock, or
these are executed in the same thread
 
 
 
Atomicity Violation Detection, Prof. Moonzoo Kim
 
23
Slide Note
Embed
Share

Explore the concept of atomicity violation in concurrent programs along with detection techniques to ensure the integrity of critical code blocks. Learn from examples and insights shared by Prof. Moonzoo Kim.


Uploaded on Jul 17, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. CS492B Analysis of Concurrent Programs Atomicity Violation Detection Prof. Moonzoo Kim

  2. Data Race Free, Yet Race Bug (1/2) public class Vector implements Collection { int elementCount ; Object [] elementData ; Data race free (protected by this) public Vector(Collection c){ elementCount = c.size() ; elementData = new Object[elementCount] ; c.toArray(elementData) ; } Should be executed atomically public synchronized int size(){ return elementCount ; } public synchronized Object[] toArray(Object a[]){ ... System.arraycopy(elementData, 0, a, 0, elementCount) ; ... } public synchronized boolean add(Object o) { ... elementCount++; ...} } Thread 1 Thread 2 Vector v2=new Vector(v1); v1.add(obj); 2 Atomicity Violation Detection, Prof. Moonzoo Kim

  3. Data Race Free, Yet Race Bug (2/2) Thread 1 Thread2 //v1.size() lock(v1) t=v1.elementCount// 10 unlock(v1) v2.elementCount=t v2.elementData=new Object[10] //v1.add() lock(v1) v1.elementCount++ // 11 unlock(v1) //v1.toArray() lock(v1) System.arraycopy(v1.elementData ,0,v2.elementData,0, v1.elementCount) Array out of bound error 3 Atomicity Violation Detection, Prof. Moonzoo Kim

  4. Time-Of-Check to Time-Of-Use (TOCTOU) Attack Attacker Victim //a program installed setuid root if (access( /home/attacker/file , w ) != 0) exit(1) ; //after the access check symlink( /etc/passwd , /home/attacker/file ); fd = fopen( /home/attacker/file , w+ ); // Do something about fd An attacker can exploit the race condition between the access and open to trick the victim into reading/overwriting an entry in the system password database. http://en.wikipedia.org/wiki/Time_of_check_to_time_of_use http://cecs.wright.edu/~pmateti/InternetSecurity/Lectures/RaceConditions/index.html 4 Atomicity Violation Detection, Prof. Moonzoo Kim

  5. Atomicity A code block is atomic if for every interleaved execution, there is an equivalent execution with the same result where the code block is executed serially (i.e., not interleaved with other threads). Programmers often assume the atomicity of a code block to reason its behavior as if it is a sequential code. c.f. atomic block: code block defined as atomic by programmers 5 Atomicity Violation Detection, Prof. Moonzoo Kim

  6. Atomicity Violation An atomicity violation (atomicity bug) is a race bug that violates the atomicity of an atomic block defined by programmers Atomicity violation detection techniques check if an observed execution is equivalent to any serial execution (i.e., serializable) Reduction based technique Access pattern based technique Happens-before relation based techniques 6 Atomicity Violation Detection, Prof. Moonzoo Kim

  7. Liptons Reduction (1/2) An interleaved execution can be reduced to an equivalent interleaved execution by swapping commuting operations. Two operations a and b in are commuting if a and b are executed by different threads, and a is immediately followed by b, and their execution orders do not change the resulting state in an execution. s0 t1:lock(m) s1 : s2 t2:tmp=0 s1 s2 s0 : t2:tmp=0 t1:lock(m) 7 Atomicity Violation Detection, Prof. Moonzoo Kim

  8. Liptons Reduction (2/2) An operation p is right-mover if p commutes with the operation that immediately follows p and executed by another thread An operation p is left-mover if p is commutes with the operation immediately followed by p , executed by another thread An operation p is both-mover if p is right-mover and left-mover at the same time non-mover if p is neither right-mover nor left-mover. 8 Atomicity Violation Detection, Prof. Moonzoo Kim

  9. Atomizer [Flanagan, POPL 04] Atomizer checks if an observed execution can be reduced to an equivalent serial execution Atomizer assumes that every public methods are atomic blocks Note that, in a serial execution, executions of atomic blocks do not overlap with each other. Reduction rule Operation type Right-mover and/or left-mover lock(m) (i.e., lock m is held by a thread) right-mover unlock(m) left-mover read(v) or write(v) where v is thread-local both-mover read(v) or write(v) where v is shared, and consistently guarded by a lock read(v) or write(v) where v is shared, and not consistently guarded by a lock both-mover non-mover 9 Atomicity Violation Detection, Prof. Moonzoo Kim

  10. Serializable Execution Example Variable A and B are consistently guarded by lock X and Y, respectively Variable C is not consistently guarded by any lock Left Thread 1 Thread 2 Thread 1 Thread 2 Thread 1 Thread 2 lock(X) lock(Y) lock(Y) read(A) read(B) read(B) lock(Y) write(C) write(C) read(B) lock(X) write(B) read(A) write(tmp) write(C) unlock(Y) write(tmp) lock(X) read(C) read(C) read(A) write(tmp) write(A) write(A) write(B) write(B) read(C) unlock(Y) unlock(Y) write(A) unlock(X) Equivalent to a serial execution unlock(X) unlock(X) Right 10 Atomicity Violation Detection, Prof. Moonzoo Kim

  11. Non-serializable Execution Example Variables A and B are consistently guarded by lock X and Y, respectively Variable C is not consistently guarded by any lock Left Thread 1 Thread 2 Thread 1 Thread 2 Thread 1 Thread 2 lock(Y) read(B) lock(X) read(A) write(tmp) lock(X) read(A) write(C) unlock(Y) lock(Y) read(B) lock(Y) read(B) lock(X) read(A) write(tmp) write(C) write(C) unlock(Y) write(tmp) read(C) read(C) read(C) unlock(X) unlock(Y) unlock(X) unlock(X) unlock(X) lock(X) lock(X) lock(X) lock(X) write(A) write(A) write(A) unlock(X) unlock(X) unlock(X) Atomicity Violation Detection, Prof. Moonzoo Kim Not equivalent to any serial execution Right 11

  12. Atomicity Checking Atomizer s serializability checking with the reduction is the same as checking if every transaction is in the following pattern: [Right-mover]* [Non-mover]? [Left-mover]* e.g: Two-phase locking lock(X) lock(Y) lock(Z) /* data accesses */ unlock(Z) unlock(Y) unlock(X) Expanding phase Shrinking phase L. Wang and S. D. Stoller: Runtime Analysis of Atomicity for Multithreaded Programs, IEEE TSE, 32(2), 2006 12 Atomicity Violation Detection, Prof. Moonzoo Kim

  13. False Positive of Atomizer class Vector { Object [] elementData; int elementCount ; t1: contains(o1) t2: contains(o2) 1:lock(this) int size(){ 1: synchronized(this){ 2: return elementCount; 3: } } 2:read(elementCount) 3:unlock(this) boolean contains(Object x){ //atomic block begins 4: int i=0; 5: while(i < size()){ 6: synchronized(this){ 7: if(elementData[i].equals(x)) 8: return true; 9: } 10: i++; 11: } 12: return false; //atomic block ends } } 1:lock(this) 2:read(elementCount) 3:unlock(this) 1:lock(this) 2:read(elementCount) 3:unlock(this) Detected as atomicity violation, but semantically serializable 13 Atomicity Violation Detection, Prof. Moonzoo Kim

  14. Access Pattern Based Detection Detect interleaved accesses on a shared variable that match to non-serializable patterns as atomicity violations Select 4 among total 8 patterns as buggy based on experiences in real-bugs read(x) write(x) Unlike serial executions, first and second read operations may see different values write(x) write(x) Intended data-flow from first write to read operations may be interfered by the second write read(x) read(x) Unserializable pattern#1 Unserializable pattern#2 Read operation may see the data before the update is completed read(x) write(x) check-and-set in the left thread may be interfered by right thread write(x) read(x) write(x) write(x) Unserializable pattern#3 Unserializable pattern#4 S. Lu et al.: AVIO: Detecting Atomicity Violations via Access Interleaving Invariants, ASPLOS 2006 14 Atomicity Violation Detection, Prof. Moonzoo Kim

  15. False Negative of Access Patterns t1: Thread1() t2: Thread2() Thread1(){ //atomic block begins synchronized(X){ a = 0 ; } lock(X) write(a,0) unlock(X) synchronized(Y){ b = 0 ; } //atomic block ends lock(X) write(a,1) unlock(X) } Thread2(){ //atomic block begins synchronized(X){ a = 1 ; } lock(X) write(b,1) unlock(X) synchronized(Y){ b = 1 ; } //atomic block ends lock(X) write(b,0) unlock(X) } a:1, b:0 15 Atomicity Violation Detection, Prof. Moonzoo Kim

  16. Velodrome [Flanagan, PLDI 08] Velodrome defines happens- before relation over atomic block executions Veldorome detects an inconsistency in the happens- before relation (i.e. cycle) as an atomicity violation 16 Atomicity Violation Detection, Prof. Moonzoo Kim

  17. Happens-Before in Transactions (1/3) An execution is a sequence of operations A transaction in an execution is the sequence of operations in a thread, that correspond to an execution of an atomic block Users can specify where an atomic block starts/ends in code An execution is serial if each transaction s operation execute contiguously, without interleaving 17 Atomicity Violation Detection, Prof. Moonzoo Kim

  18. Happens-Before in Transactions (2/3) Two operations in an execution conflict if these access the same variable, and at least one is writing, or these operate on the same lock, or these are executed in the same thread If two operations do not conflict, they commute The happens-before relation over operations ( ) in an execution satisfies the following properties: a b if a occurs before b in the execution, and a conflicts with b a b if a occurs before b, and a and b are in the same transaction a c if a b and b c 18 Atomicity Violation Detection, Prof. Moonzoo Kim

  19. Happens-Before in Transactions (3/3) A transaction ? happens-before a transaction ? in an execution (? ?) if ? ?, and ? ?, ? ?: ? ? An execution is serializable if and only if the transactional happens-before relation ( ) is acyclic* A blame assignment is a set of happens-before relation over operations that construct a cycle in the transactional happens-before relation * P. A. Bernstein et al., Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987 19 Atomicity Violation Detection, Prof. Moonzoo Kim

  20. Example t2: Thread2() t1: Thread1() Tr#1 t3: Thread2() Tr#2 lock(X) write(a) unlock(X) lock(Y) write(b) unlock(Y) Tr#3 Tr#2 Tr#3 Tr#1 Tr#2 Tr#3 Tr#1 Not serializable lock(Z) lock(Y) read(b) write(c) unlock(Y) unlock(Z) lock(X) read(a) unlock(X) lock(Z) read(c) unlock(Z) 20 Atomicity Violation Detection, Prof. Moonzoo Kim

  21. False Positive of Velodrome t1: Thread1() Tr#1 lock(X) t2: Thread2() Thread1(){ //atomic block begins synchronized(X){ a = 1} write(a, 1) unlock(X) Tr#2 synchronized(X){ a = 2 ; } //atomic block ends lock(X) write(a, 11) write(a, 12) } Thread2(){ //atomic block begins synchronized(X){ a = 11 ; a = 12 ; } //atomic block ends } unlock(X) lock(X) write(a, 2) lock(X) Execution order of write operations on a variable without read operations do not change result states, except for the last one 21 Atomicity Violation Detection, Prof. Moonzoo Kim

  22. View-Serializability (1/2) Conflict-serializability (used by Velodrome) An execution is conflict-serializable if there exists a serial execution s.t. (1) two executions have the same operations, and (2) for every pair of conflicting operations, the two operations have the same order in both executions View-serializability* An execution is view-serializable if there exists a serial execution s. t. (1) two executions have the same operations, and (2) each read operation has the same write predecessor in both executions, and - The write-predecessor of a read operation is the last write operation on the variable that the read operation reads in an execution (3) each variable has the same final write operation in both executions *L. Wang et al.: Accurate and Efficient Runtime Detection of Atomicity Errors in Concurrent Programs, PPoPP 2006 22 Atomicity Violation Detection, Prof. Moonzoo Kim

  23. View-Serializability (2/2) We can implement the view-serializability checking by modifying the conflict definition Two operations p and q in an execution conflict if these access the same variable where p is writing, and q is reading, or q is the final write operation on the variable in the execution these operate on the same lock, or these are executed in the same thread 23 Atomicity Violation Detection, Prof. Moonzoo Kim

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#