2
$\begingroup$

I am currently reading this paper by Chales-Lev. This paper explain an implementation of work-stealing dequeue. The part where I don't understand is in the implementation of steal operation.

public Object steal() {
11 long t = this.top;
12 long b = this.bottom;
13 CircularArray a = this.activeArray;
14 long size = b - t;
15 if (size <= 0) return Empty;
16 Object o = a.get(t);
17 if (! casTop(t, t+1))
18 return Abort;
19 return o;
}

I am confused by this sentence on page 3 regarding this implementation:

Note that because top is read before bottom, it is guaranteed that the values read represent a consistent view of the memory. Specifically, it implies that bottom and top indeed had their observed values when bottom was read at Line 12.

I actually have find an example where loading bottom before top is problematic. Say for example where one thread do steal operation and in between the load bottom and load top operation there is another threads that keep doing pop operation until the queue is empty. Then after that we load top variable. Because we load the bottom variable first, we don't know that the queue is already empty and at that point of time, top variable is up to date so the casTop() will be successful. But if we load the top variable first. There is no way to make the queue empty without modifying the top variable, so the casTop() will fail when there is another thread that try to make the dequeue empty.

But I still don't understand the sentence above. What does it mean by consistent view of memory? Even though I already find the reason why I must load top first before bottom, I afraid there is a concept that I don't understand here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.