//pseudocode
for job in jobsWaitingInList
//If no thread 'owns' this job, assign it to this thread
if(InterlockedCompareExchange(&job.threadOwner, thisThreadId, 0) == thisThreadID) {
//This thread got the job first, so remove it from the waiting list
jobsWaitingInList.Remove(job)
//Process the job
job.process()
} //else
// A context switch happened between getting the job from the list and trying to run
// it. In this case, continue onto the next job in the list
Lock-free multithreading: dissemination of tasks?
Author
Hey all
I'm creating a multithreaded program that uses a task-independent way of getting jobs done. The concept is as follows:
- There are a variable of worker threads
- Each thread has access to a list of waiting tasks ('jobs') that need to be done.
- Each thread looks at the list of jobs, takes one off the stack and processes it. Repeat ad. infinitum
These jobs can be anything, from processing a frame during video encoding to creating collision islands to accessing a database. Each job is designed to be as atomic as possible. For example, one job could be to resolve the collision islands between objects in a scene. Once these collision islands are determined, it would create a job for each collision island and put it onto the list. The whole goal of this is to try to move away from the each-thread-has-a-specific-task idea of multithreading and towards a data-oriented multithreading approach.
Since I'm designing this program from the ground up, I opted to try and impose as many good-multithreading practices as possible. At the moment, I'm trying to wrap my head around lock-free multithreading and its application to my design. I've looked into the InterlockedCompareExchange and came up with something like this that would be executed in each worker thread:
However, this lockless approach isn't thread-safe. The modification of the job list in one thread can cause a null pointer exception if two threads happen to grab a hold of the same job, but one of them completes the CAS and removes the job before the other thread can even call the CAS function. A quick fix for this would require locking the jobList when iterating over it and removing the job, but that would go against the whole idea of lockless programming.
Is there a correct/elegant way to use lockless in my approach? Any suggestions/critiques on the approach in general are quite welcome as well :)
google: lockless queue
Here's the first couple, I found them pretty useful.
http://www.ddj.com/cpp/193004231
http://mooproductions.blogspot.com/2006/12/lockless-queue-revision.html
This one's a gamedev thread
http://www.gamedev.net/community/forums/topic.asp?topic_id=463697
Here's the first couple, I found them pretty useful.
http://www.ddj.com/cpp/193004231
http://mooproductions.blogspot.com/2006/12/lockless-queue-revision.html
This one's a gamedev thread
http://www.gamedev.net/community/forums/topic.asp?topic_id=463697
You can't make a thread safe lockless queue if there are more than 1 reader and 1 writer. Since you want arbitrary number of readers and arbitrary number of writers, that means you have to use locks.
The data-oriented approach is interesting, but creates overhead as opposed to giving each thread a specific task. It's the sort of thing that could be good for large scale distributed computing, but not for regular desktop applications.
The data-oriented approach is interesting, but creates overhead as opposed to giving each thread a specific task. It's the sort of thing that could be good for large scale distributed computing, but not for regular desktop applications.
Quote:You can't make a thread safe lockless queue if there are more than 1 reader and 1 writer. Since you want arbitrary number of readers and arbitrary number of writers, that means you have to use locks.
Sure, but each worker thread can maintain its own queue. The main thread then is responsible for supplying the jobs, using whatever algorithm is most appropriate (it could try to keep the size of the different threads' queues approximately equal for instance). It still allows a way for the supplier to drop off tasks without stalling, and for the workers to consume at their own pace.
I'm working on a resource manager at the moment and I have it set up so that any component of the system can register itself as an event recipient. The recipient defines its own messages and the rest of the application has only to send the event and its parameters. The events then go directly to the recipient. In this system, there is no central event processor. Each recipient has their own event list. A similar design might get you past the access collision on your job list.
yahastu is just wrong about the need for locks when there is more than one writer. You do not need locks. The whole point of the lock-free queue idea is that you can have any number of threads queueing and dequeing tasks without locks.
The problem is that you're not thinking in terms of lock-free queues. The "for each job in waitinglist" type of logic is causing the trouble. Make the jobs list a lock-free queue, and do not iterate over it. Dequeue jobs and enqueue jobs. These are the only ways that the worker threads ever need to access the job queue.
The compare and exchange is used to implement the lock-free queue. It is not used by the client code that is using the lock-free queue. Correctly implementing the queue can be a little tricky. A correct implementation allows any number of threads to queue and dequeue elements without locks and without deadlocks (although if there are several threads attempting to modify the queue simultaneously, it is possible for threads to spend time spinning around while other threads beat them to the queue. The most important thing is that the thread that got to the queue first will always be able to get its work done, so it is never the case that all the threads are spending all their time fighting over the queue).
If you're using a modern version of windows, there is an interlocked singly linked list available that does most of the work of implementing a lock-free queue. All that's left is to wrap it up to make it user more user friendly, if you want. It does the tricky synchronization part for you.
The problem is that you're not thinking in terms of lock-free queues. The "for each job in waitinglist" type of logic is causing the trouble. Make the jobs list a lock-free queue, and do not iterate over it. Dequeue jobs and enqueue jobs. These are the only ways that the worker threads ever need to access the job queue.
The compare and exchange is used to implement the lock-free queue. It is not used by the client code that is using the lock-free queue. Correctly implementing the queue can be a little tricky. A correct implementation allows any number of threads to queue and dequeue elements without locks and without deadlocks (although if there are several threads attempting to modify the queue simultaneously, it is possible for threads to spend time spinning around while other threads beat them to the queue. The most important thing is that the thread that got to the queue first will always be able to get its work done, so it is never the case that all the threads are spending all their time fighting over the queue).
If you're using a modern version of windows, there is an interlocked singly linked list available that does most of the work of implementing a lock-free queue. All that's left is to wrap it up to make it user more user friendly, if you want. It does the tricky synchronization part for you.
This is the exact problem that I was just about to approach. I would love to hear others' opinions/experiences as well.
Just a side note - accessing lock-free queue isn't a cheap operation. So make sure your operations aren't af too fine granularity, or you'll be facing a lot of overhead.
Lock-less approach makes sure you're always doing useful work rather than waiting, but you should still try to maximize the work you do for every entry.
Only with naive implementation. General robust queue implementation can handle any combination.
General lock-free remove operation looks something like this:
As is obvious from the above, you could be spinning for a while.
This also doesn't solve the ABA problem, or any other tricky details, such as memory allocation for holders.
What you really want is reactor or pro-actor pattern. Look into boost::asio for robust general-purpose implementation. It's an IO library, but the async framework is usable without that. It also takes care of all the threading issues.
Lock-less approach makes sure you're always doing useful work rather than waiting, but you should still try to maximize the work you do for every entry.
Quote:You can't make a thread safe lockless queue if there are more than 1 reader and 1 writer. Since you want arbitrary number of readers and arbitrary number of writers, that means you have to use locks.
Only with naive implementation. General robust queue implementation can handle any combination.
General lock-free remove operation looks something like this:
while (true) { // get first element Object * ptr = queue.first; // atomic swap, replace queue.first with ptr.next // at the time of swap, queue.first must equal ptr if (ICEX(&queue.first, ptr.next, ptr) == ptr) { // it does, we have removed the element return ptr; } // it does not, someone beat us to it, try again};As is obvious from the above, you could be spinning for a while.
This also doesn't solve the ABA problem, or any other tricky details, such as memory allocation for holders.
What you really want is reactor or pro-actor pattern. Look into boost::asio for robust general-purpose implementation. It's an IO library, but the async framework is usable without that. It also takes care of all the threading issues.
Author
Thanks for the info. I'll be implementing a lockless queue tonight. Does anyone have any whitepapers/further reading on lockless concepts they can point me to?
yahastu: in the future, task-specific multithreading appears to be a dead end. What happens when desktops have 4 cores and 4 tasks? Everything is cheery. What happens when you have 16 cores and 4 tasks? That means 12 cores are sitting empty.
Check out AndyTX and andi's post over at IGDA:
http://www.igda.org/Forums/showthread.php?threadid=25826
yahastu: in the future, task-specific multithreading appears to be a dead end. What happens when desktops have 4 cores and 4 tasks? Everything is cheery. What happens when you have 16 cores and 4 tasks? That means 12 cores are sitting empty.
Check out AndyTX and andi's post over at IGDA:
http://www.igda.org/Forums/showthread.php?threadid=25826
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
