Lockset-Based Data Race Detector Implementation
Hint for Assignment#4: Implementing
Lockset-Based Data Race Detector
Prof. Moonzoo Kim
Computer Science, KAIST
CS492B Analysis of Concurrent Programs
Java Data Structure
•
HashMap
–
“dictionary” in Java
–
map.put(key, value)
/
map.get(key)
•
LinkedList
–
can be used for stack or queue
–
Stack (LIFO):
•
push =
list.addFirst(x)
•
pop =
list.removeFirst()
–
Queue (FIFO):
•
enqueue =
list.addFirst(x)
•
dequeue=
list.removeLast()
•
HashSet
–
do not contain duplicated elements
–
s1.retainAll(s2)
: remove s1’s elements that are not in s2
2
Data Structure for Thread
•
HashMap<Integer, LinkedList<Integer>>
stacks
–
Key:
thread identifier
–
Value:
a sequence of iids on methodEnter executions
–
c.f. HashMap is “dictionary” in Java
•
HashMap<Integer, LinkedList<Integer>>
heldLocks
–
Key:
thread identifier
–
Value:
a sequence of lock identifiers currently held by
this thread
–
A list is used instead of a set to consider recursive locking
3
Memory Location State
•
Eraser maintains the state for each memory location
to check if it is in initialization, and if read-shared.
C
(
v
) = {*}C
(
v
) is not
updated
Initialization
Read-shared
candidates
state
firstThread
Data Structure for Memory Address (1/2)
•
HashMap<Long, HashSet<Integer>>
candidates
–
Key:
memory
–
Value:
a set of candidate locks
•
HashMap<Integer, MemoryState>
state
–
Key:
memory
–
Value:
the monitoring state of the memory
5
Data Structure for Memory Address (2/2)
•
HashMap<Long, Integer>
firstThread
–
Key:
memory
–
Value:
thread that first accesses memory
•
HashMap<Integer, Integer>
lastAccessLoc
–
Key:
memory
–
Value:
iid of an operation that access memory right before
the data race detection
•
javato.activetesting.analysis.Observer.getIidToLoc(iid) converts iid
to the corresponding code line information
6
Lockset Algorithm Example
class
Account {long
balance;
//must be non-negative
void
withdraw(
long
x){1
if
(balance >= x){2
synchronized
(
this
){3 balance=balance – x;
4 }
5 }
}
void
deposit(
long
x){11
synchronized
(
this
){12 balance=balance + x;
13 }
}
}
7
11:lock(this)
12:t=balance
12:balance=t+10
t1:
deposit(10)
Initially,
balance
: 10
13:unlock(this)
2:lock(this)
3:t=balance
t2:
withdraw(5)
4:unlock(this)
3:balance=t-5
1:if(balance>=5)
lastAccessLoc
(balance): 12
Learn how to implement a lockset-based data race detector in Java using concepts such as HashMap, LinkedList, stack, queue, and memory location states. Explore data structures for thread management, memory addresses, and memory monitoring for efficient detection of data races in concurrent programs.
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
CS492B Analysis of Concurrent Programs Hint for Assignment#4: Implementing Lockset-Based Data Race Detector Prof. Moonzoo Kim Computer Science, KAIST
Java Data Structure HashMap dictionary in Java map.put(key, value) / map.get(key) LinkedList can be used for stack or queue Stack (LIFO): push = list.addFirst(x) pop = list.removeFirst() Queue (FIFO): enqueue = list.addFirst(x) dequeue= list.removeLast() HashSet do not contain duplicated elements s1.retainAll(s2): remove s1 s elements that are not in s2 2
Data Structure for Thread HashMap<Integer, LinkedList<Integer>> stacks Key: thread identifier Value: a sequence of iids on methodEnter executions c.f. HashMap is dictionary in Java HashMap<Integer, LinkedList<Integer>> heldLocks Key: thread identifier Value: a sequence of lock identifiers currently held by this thread A list is used instead of a set to consider recursive locking 3
Memory Location State Eraser maintains the state for each memory location to check if it is in initialization, and if read-shared. state C(v) = {*} candidates firstThread Initialization C(v) is not updated C(v) = C(v) L(t), report if C(v)= C(v) = C(v) L(t) (no bug report) Read-shared
Data Structure for Memory Address (1/2) HashMap<Long, HashSet<Integer>> candidates Key: memory Value: a set of candidate locks HashMap<Integer, MemoryState> state Key: memory Value: the monitoring state of the memory 5
Data Structure for Memory Address (2/2) HashMap<Long, Integer> firstThread Key: memory Value: thread that first accesses memory HashMap<Integer, Integer> lastAccessLoc Key: memory Value: iid of an operation that access memory right before the data race detection javato.activetesting.analysis.Observer.getIidToLoc(iid) converts iid to the corresponding code line information 6
Lockset Algorithm Example Initially, balance: 10 class Account { long balance; //must be non-negative void withdraw(long x){ 1 if(balance >= x){ 2 synchronized(this){ 3 balance=balance x; 4 } 5 } } t1: deposit(10) t2: withdraw(5) 11:lock(this) 12:t=balance lastAccessLoc (balance): 12 12:balance=t+10 13:unlock(this) C(balance) = {*} L(t2) = 1:if(balance>=5) void deposit(long x){ 11 synchronized(this){ 12 balance=balance + x; 13 } } } 2:lock(this) 3:t=balance 3:balance=t-5 4:unlock(this) 7
