How is the locking implemented for a double-ended queue like this? I'd imagine that if the queue were really long, you could have threads steal from the top, have the current thread take work from the bottom, and you could do this without a lock (only until there's one element left) - but how would something like that be implemented? Does Cilk use queues that have a locking mechanism in this way?

^ That is a fascinating question.

My understanding is that we should always get the task from the work queue even for the current thread? You can search for "deque" for a double ended queue, but I'm not sure if it is needed here

@12345 I think the point of the dequeue here is that the worker thread will always pop from the bottom of its work queue (relative to the picture), but whenever we want to steal from another worker's work queue, we want to steal from the top of the work queue (relative to the picture), so we want something that allows us to pop from both ends.

I am also interested in the answer to @juliob's question. It makes sense that there should be a locking mechanism to avoid a race condition. Specifically, there could be a lock at the 'top' of the structure since that's the only place multiple threads try to access. In the case of 1 element being left, I guess this could be solved by having the current thread also grab the lock whenever it gets something from the bottom. In the case of large pieces of work being stolen, this overhead/scheduling work should be infrequent.