Hey guys, this is a fairly simple and fast question.. I wanted to ask what method you tend to use for notifying when a task is finished. Do you use a simple atomic counter , the job would be considered finished when Counter==0, or do you use system primitives like the "Event" structure on windows.
TaskSystem
Atomic updates are fine if you know your hardware platform exceptionally well, and your kernel to boot. Languages like C++11 and later that provide atomicity models make this a much more appealing option today than a few years ago.
That said, I (personally) would strongly recommend sticking with synchronization tools provided by your OS/libraries/language/etc. unless you're profoundly adept at dealing with atomic operations. Atomics are notoriously easy to screw up in very subtle and hard-to-reproduce ways.
That said, I (personally) would strongly recommend sticking with synchronization tools provided by your OS/libraries/language/etc. unless you're profoundly adept at dealing with atomic operations. Atomics are notoriously easy to screw up in very subtle and hard-to-reproduce ways.
Author
Thank you for your response ApochPiQ .. I am quite interested in the manners in which an atomic approach would fail. Would you possibly have an example? In a counter based approach, I would have an atomic for the preqrequisites of the task, and a counter for the current value(begins at 1). When the "execute" function is called on the task, the task decrements it's internal value to zero... and decrements the "prerequisite" counter of all of it's post jobs.
It can fail if doing it yourself by not enforcing correct memory ordering. The std library atomics provide sequential consistency by default though, IIRC.
If it's likely that a thread is going to need to sleep until the job is done, then an OS event is good.
If everything is structured so that most of the time no waiting/sleeping will actually occur (but code to wait still needs to be present for correctness) then atomics can be a valid optimization.
Note that with atomics, you'll basically be building your own busy-wait/spin-lock type mechanism, which is definitely frowned upon and will cause everyone yo ask you why you're doing such a thing.
You'll definitely want to have enough tasksin flight that when a thread decides to wait for one task, it can perform some other tasks whilr waiting instead of just busy-waiting.
If it's likely that a thread is going to need to sleep until the job is done, then an OS event is good.
If everything is structured so that most of the time no waiting/sleeping will actually occur (but code to wait still needs to be present for correctness) then atomics can be a valid optimization.
Note that with atomics, you'll basically be building your own busy-wait/spin-lock type mechanism, which is definitely frowned upon and will cause everyone yo ask you why you're doing such a thing.
You'll definitely want to have enough tasksin flight that when a thread decides to wait for one task, it can perform some other tasks whilr waiting instead of just busy-waiting.
Author
Thank you for your response hodgeman. As of right now, when a thread asks to "Wait" for a job, the job manager checks if the counter==0 , and if it does.. it returns immediately.. if the counter is not equal to zero.. the thread goes into a "wait" phase, in which it keeps processing tasks until the wait counter ==0. Would this approach not be more efficient than an OS Event approach? In the OS Event approach, the thread will sleep until the event is signaled, and because of that.. tasks that could of been run have to now wait on the task to complete. I guess you would be able to do a "TryWait" with the OS Event approach, so it may work out to be similar. Another fear I may have is allocating a new event primitive for each job. As far as I know, this approach would have a higher overhead than simply using an atomic integer. Would you advice a pooling approach if I took this approach?
If the overhead involved in task dispatching is significant, likely your tasks are too small.
Edit: Before doing complicated things, first implement a simple approach, and see how it behaves. If it does the job, you're done, move on to other problems.
Author
Thank you both for your responses!.. Yeah, I sometimes have a problem with preoptimizations, and this may be another instance of it.
Naively attempting to use atomics to wake up/suspend threads has one massive problem: you will be fighting with the OS the entire way for control over the thread's execution time, and the OS knows better than you.
Do some research on phenomena like race conditions, deadlocks, livelocks, task queue starvation, task queue saturation, and so on. There's way more material out there than I could hope to summarize in a forum post.
Since C++11 it's way easier to get atomics right, since the language itself understands the guarantees you need, and the standard library offers a way to implement atomic operations.
To get a feel for how subtle this stuff is, search for the "ABA problem" from lockless threading literature.
Do some research on phenomena like race conditions, deadlocks, livelocks, task queue starvation, task queue saturation, and so on. There's way more material out there than I could hope to summarize in a forum post.
Since C++11 it's way easier to get atomics right, since the language itself understands the guarantees you need, and the standard library offers a way to implement atomic operations.
To get a feel for how subtle this stuff is, search for the "ABA problem" from lockless threading literature.
As of right now, when a thread asks to "Wait" for a job, the job manager checks if the counter==0 , and if it does.. it returns immediately.. if the counter is not equal to zero.. the thread goes into a "wait" phase, in which it keeps processing tasks until the wait counter ==0. Would this approach not be more efficient than an OS Event approach?
Yes, but only in the case where you actually can keep processing tasks.
What do you do if your task queue is empty? In that case, you've got no work to do while waiting, so all you can do is either busy-wait, or let the OS scheduler kick in.
Busy waiting is a very bad thing to do (there will be other threads on the system that could be using this CPU time!) so you should give your timeslice back to the OS in this case.
Another fear I may have is allocating a new event primitive for each job. As far as I know, this approach would have a higher overhead than simply using an atomic integer. Would you advice a pooling approach if I took this approach?
Yeah constantly reallocating OS events seems like a lot of work so you'd certainly try to use pooling/etc to reduce that cost.
Another approach is to make your task objects long-lived and reusable, so they allocate a waitable event once upon creation, and then reuse it frame after frame after frame.
In my current task system, I actually just have a single semaphore that's shared by the entire thread pool. Whenever a task is pushed into the queue or a "waitable" task completes, it signals the semaphore. If a thread must busy wait (waiting on a task to complete but the task queue is also empty), then it can wait on the semaphore, and it will wake up as soon as its dependency task is completed, or when new work is in the queue, or earlier. It will never over-sleep.
Before doing complicated things, first implement a simple approach, and see how it behaves. If it does the job, you're done, move on to other problems.
That too :)
The more time you spend on this, the less time you're spending on your game.
Author
Thank you hodgman.. I've decided to stick with event pools and to do let the OS kick in when the queues are empty.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
