CODEWITHSUNDEEP
.netparallel-processingtask-parallel-library
Farah_online
Farah_online

Reputation: 589

Duplicating queue in TPL

I am studying task parallel library for .NET (TPL) , I am trying to understand how it works , I understand the idea of work stealing , but I can't understand why we use duplicating queue and How it works ?

when new task is created , whom specify which thread should take it and put it in its task queue ?

can you help me ?

Upvotes: 3

Views: 278

Answers (1)

svick
svick

Reputation: 244948

Imagine you were implementing the TPL yourself and used ordinary non-duplicating work-stealing queues. So, for each queue, you have one thread that pushes to and pops from the tail of the queue and multiple threads that can take from the head of the queue (called thieves in the paper). Because you want to make sure that every task that is added to the queue is removed exactly once (either by popping or by taking) you have to use locking in each of the three operations.

In a way, it seems quite wasteful to lock on push and pop, when you know only one thread is going to use those operations. But there's nothing you can do about it, if you want to be sure the queue behaves correctly.

Your library works, but you realize what often happens is that you are waiting for a task, which was not even started yet. So, what about running it synchronously in the current thread? You could do that, but the problem is that the task is in some queue and you can't safely and quickly remove it from there. What you can do though is to add a flag to the task, indicating its state, and accessing the flag in a thread-safe manner.

This way, if you dequeue the task eventually, you won't run it, because you know it is already running or even finished. What about the queue? We said we wanted to make sure we remove the task from the queue exactly once. But this is no longer required: if we remove some task twice, it doesn't matter, because the task is going to take care of it itself and will actually start only once.

But this means we can remove the locks from pop and push, resulting in a duplicating queue, which is faster than normal work-stealing queue, because it has weaker requirements: we can be sure that every task is removed from it at least once.

EDIT: reactions to the questions:

remove task by taking is OK, but remove task by pushing task in the queue!

Sorry, that was a mistake, now fixed. It is popping or taking.

case 3 in fib example in page 6, is it?

Yes.

why? I can't understand this problem.

The problem is, this task could be in a queue for any thread or it could be currently executing on any thread. So you would have to at the very least search through tasks that are running on each thread, using a lock for every thread. And every thread would have to use lock whenever it changed its running task. If the task isn't currently running, you have to at least lock the queue you are removing from. Which also makes the analysis of the behavior of the queue more complicated: now things can vanish from the middle of the queue.

what is the logical link between remove locks from pop and push, and duplicating queue?

When you remove the locks, you can't be completely sure that a task is removed exactly once. What could happen is that there is only one task in the queue and two different threads call take and pop at the same time. Because pop doesn't use locks, the same task is removed twice.

Upvotes: 4

Related Questions