Previous | Next --- Slide 44 of 64
Back to Lecture Thumbnails

What is the "efficient lock-free dequeue implementation"? If it implies that thread 0 work queue (for example) could be lock-free, why don't we need a lock to ensure that two different threads don't steal the same continuation from a thread? Am I understanding the term "lock-free" correctly?


@patrickbot. Good question. However, if you don't mind, I'd like to defer answering this question until the lecture on... you guessed it... Lock-free data structures.


Why remote threads steal from the "head" of the queue and local threads steal form the "tail" of the queue? What is the benefit of doing this?


@1pct See Kayvon's comment on the previous slide

Local threads take the most recent item from the queue because the data is the data that is most recently touched -- might be able to get cache locality benefits. Remote threads take the last item in the queue because it the largest piece of work -- the cost of stealing is amortized out by the large amount of work.


@thomasts It is not necessarily the largest piece of work.

@1pct See slide 46.