Report on Threadpool Scheduling Techniques -- Need Feedback
-
Concurrency is one of those things that gets me all worked up and interested, and part of the reason for this is because I find it great fun to be creating some sort of framework that others might be able to use, in order to increase their scalability, where all they have to do is figure out which parts are scalable, and leave the gory details of handling concurrency to the framework. Anyway, I'm looking to do some research and experimentation (and write a short document on my findings) on something concurrency related on Windows. I've read some articles in the past on how to properly/efficiently use threadpools (by Herb Sutter, other concurrency gurus, and such), and one of the problems mentioned was a thread in a threadpool waiting on another thread in the threadpool, since you've effectively reduced your concurrency. I'd like to attempt to solve this problem in C++ by attempting a couple of techniques: - Using fibers to emulate explicit wait API calls (WaitForSingleObject, etc.) so that waits essentially cause a switch to a different threadpool task, until the wait is ready. The idea behind this is that we can preserve the number of threads in a threadpool, and have them switch between fibers while one is waiting on another thread, and then have them switch back to the original fiber when it's ready to run. This is because a thread can have multiple fibers. For those that don't know, a fiber can be sort of seen as a lightweight thread with its own stack space that is attached to an actual thread. Of course, feel free to correct me if I'm wrong, since I'm fairly new to this. - Optimizing a threadpool by using more threads than can be efficiently used concurrently. The idea behind this is that in a 4-core system, 4 active tasks can be performed at a time, but if one of these tasks waits on another task, then only 3 active tasks are working, so we optimize the threadpool by having for instance 6 tasks in all (4 running, 2 blocked), and when necessary to preserve maximum concurrency, we unblock the blocked tasks, and block them again where possible (I've seen allusions to the fact that we can do this, but this will require some more research). I've already crafted (in previous attempts at research and testing), my own somewhat generic C++ threadpool framework, and my idea is to add the above concepts to what I currently have, to answer a few questions at least: - Are my ideas feasible and not overly complicated? - Is it possible to generalize what I'm trying to do in a framework?
-
Concurrency is one of those things that gets me all worked up and interested, and part of the reason for this is because I find it great fun to be creating some sort of framework that others might be able to use, in order to increase their scalability, where all they have to do is figure out which parts are scalable, and leave the gory details of handling concurrency to the framework. Anyway, I'm looking to do some research and experimentation (and write a short document on my findings) on something concurrency related on Windows. I've read some articles in the past on how to properly/efficiently use threadpools (by Herb Sutter, other concurrency gurus, and such), and one of the problems mentioned was a thread in a threadpool waiting on another thread in the threadpool, since you've effectively reduced your concurrency. I'd like to attempt to solve this problem in C++ by attempting a couple of techniques: - Using fibers to emulate explicit wait API calls (WaitForSingleObject, etc.) so that waits essentially cause a switch to a different threadpool task, until the wait is ready. The idea behind this is that we can preserve the number of threads in a threadpool, and have them switch between fibers while one is waiting on another thread, and then have them switch back to the original fiber when it's ready to run. This is because a thread can have multiple fibers. For those that don't know, a fiber can be sort of seen as a lightweight thread with its own stack space that is attached to an actual thread. Of course, feel free to correct me if I'm wrong, since I'm fairly new to this. - Optimizing a threadpool by using more threads than can be efficiently used concurrently. The idea behind this is that in a 4-core system, 4 active tasks can be performed at a time, but if one of these tasks waits on another task, then only 3 active tasks are working, so we optimize the threadpool by having for instance 6 tasks in all (4 running, 2 blocked), and when necessary to preserve maximum concurrency, we unblock the blocked tasks, and block them again where possible (I've seen allusions to the fact that we can do this, but this will require some more research). I've already crafted (in previous attempts at research and testing), my own somewhat generic C++ threadpool framework, and my idea is to add the above concepts to what I currently have, to answer a few questions at least: - Are my ideas feasible and not overly complicated? - Is it possible to generalize what I'm trying to do in a framework?
Cyrilix wrote:
- Using fibers to emulate explicit wait API calls (WaitForSingleObject, etc.) so that waits essentially cause a switch to a different threadpool task, until the wait is ready.
Requires you to emulate kernel waits (presuming you have more than one fiber per thread in the threadpool), or do you effectively poll the kernel objects on fiber context switches (oh, and you'll need to schedule them yourself somehow).
Cyrilix wrote:
- Optimizing a threadpool by using more threads than can be efficiently used concurrently.
That sounds a lot simpler - maybe you can detect thread state and automatically add new threads to the pool as other threads enter wait states? And then reduce the number of active threads appropriately when the waits terminate? Personally, my feelings about concurrency have been significantly influenced by the concurrency approaches of other programming[^] langauges[^]. Both those languages are functional, which avoids the problems of sharing data between threads. Erlang uses an actor model[^] of concurrency, while Haskell has several concurrency models. I think utilising the best approaches of those different models could offer significant improvements in achieving concurrency capable of making best use of multiple processing cores. One other thought - for something a bit simpler, emulating the tasking model of Ada with C++ and threads might be an interesting challenge. Ada tasking has been knocking around since the early 1980s and is still (IMO and in many other people's opinions) a significantly better model of concurrent programming than basic threads. Anyway - that may be of use, maybe not - I hope there's something coherent in there!
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
-
Cyrilix wrote:
- Using fibers to emulate explicit wait API calls (WaitForSingleObject, etc.) so that waits essentially cause a switch to a different threadpool task, until the wait is ready.
Requires you to emulate kernel waits (presuming you have more than one fiber per thread in the threadpool), or do you effectively poll the kernel objects on fiber context switches (oh, and you'll need to schedule them yourself somehow).
Cyrilix wrote:
- Optimizing a threadpool by using more threads than can be efficiently used concurrently.
That sounds a lot simpler - maybe you can detect thread state and automatically add new threads to the pool as other threads enter wait states? And then reduce the number of active threads appropriately when the waits terminate? Personally, my feelings about concurrency have been significantly influenced by the concurrency approaches of other programming[^] langauges[^]. Both those languages are functional, which avoids the problems of sharing data between threads. Erlang uses an actor model[^] of concurrency, while Haskell has several concurrency models. I think utilising the best approaches of those different models could offer significant improvements in achieving concurrency capable of making best use of multiple processing cores. One other thought - for something a bit simpler, emulating the tasking model of Ada with C++ and threads might be an interesting challenge. Ada tasking has been knocking around since the early 1980s and is still (IMO and in many other people's opinions) a significantly better model of concurrent programming than basic threads. Anyway - that may be of use, maybe not - I hope there's something coherent in there!
Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
I don't exactly have a game plan for how I will handle fibers and waits so part of the task would be for me to see if the Windows API has any kind of built-in support for this. If I can somehow accomplish that, then I don't think the scheduling would be a problem because I can use a simple algorithm as proof-of-concept. As for the second idea, something like what you suggest will definitely be in the works. I'm actually a bit skeptical as to whether or not I'll see any major improvements here, but sometimes I surprise myself. In terms of other languages and their concurrency approaches, that's probably something I'll want to look at if I have time, so I'll keep it in mind. Thanks. Edit: I gave some thought to what you said about the Ada task model vs. C++ and threads, and it seems to me like different concurrency models must still be implemented at the base with C++ or assembly. I guess the question then becomes, how do you use lower-level languages to implement a higher-level concurrency model. I think what I'm essentially trying to do here is to refine a higher-level task-based model by using something like threads.
modified on Sunday, July 12, 2009 8:23 PM
-
Concurrency is one of those things that gets me all worked up and interested, and part of the reason for this is because I find it great fun to be creating some sort of framework that others might be able to use, in order to increase their scalability, where all they have to do is figure out which parts are scalable, and leave the gory details of handling concurrency to the framework. Anyway, I'm looking to do some research and experimentation (and write a short document on my findings) on something concurrency related on Windows. I've read some articles in the past on how to properly/efficiently use threadpools (by Herb Sutter, other concurrency gurus, and such), and one of the problems mentioned was a thread in a threadpool waiting on another thread in the threadpool, since you've effectively reduced your concurrency. I'd like to attempt to solve this problem in C++ by attempting a couple of techniques: - Using fibers to emulate explicit wait API calls (WaitForSingleObject, etc.) so that waits essentially cause a switch to a different threadpool task, until the wait is ready. The idea behind this is that we can preserve the number of threads in a threadpool, and have them switch between fibers while one is waiting on another thread, and then have them switch back to the original fiber when it's ready to run. This is because a thread can have multiple fibers. For those that don't know, a fiber can be sort of seen as a lightweight thread with its own stack space that is attached to an actual thread. Of course, feel free to correct me if I'm wrong, since I'm fairly new to this. - Optimizing a threadpool by using more threads than can be efficiently used concurrently. The idea behind this is that in a 4-core system, 4 active tasks can be performed at a time, but if one of these tasks waits on another task, then only 3 active tasks are working, so we optimize the threadpool by having for instance 6 tasks in all (4 running, 2 blocked), and when necessary to preserve maximum concurrency, we unblock the blocked tasks, and block them again where possible (I've seen allusions to the fact that we can do this, but this will require some more research). I've already crafted (in previous attempts at research and testing), my own somewhat generic C++ threadpool framework, and my idea is to add the above concepts to what I currently have, to answer a few questions at least: - Are my ideas feasible and not overly complicated? - Is it possible to generalize what I'm trying to do in a framework?
just wondering but does windows give u that type of control without writing a kernel mode driver type app? regarding fibre management etc. because i'm sure that windows has a system that deals with this so your going to be overriding it to a certain level. or am i thinking about the wrong tangent?
-
just wondering but does windows give u that type of control without writing a kernel mode driver type app? regarding fibre management etc. because i'm sure that windows has a system that deals with this so your going to be overriding it to a certain level. or am i thinking about the wrong tangent?
I've never worked with fibers so I don't actually know. I see that they have a neat little API for some of the stuff that I might want to do, but that may not be sufficient. With respect to working with fibers, I'm starting from ground zero here. :) I've also read a lot of articles warning very heavily against their usage, bugs, limitations, and etc. It's not too encouraging but still tempting, which is why I ask for some feedback.
-
I've never worked with fibers so I don't actually know. I see that they have a neat little API for some of the stuff that I might want to do, but that may not be sufficient. With respect to working with fibers, I'm starting from ground zero here. :) I've also read a lot of articles warning very heavily against their usage, bugs, limitations, and etc. It's not too encouraging but still tempting, which is why I ask for some feedback.
ahh a fellow explorer not afraid of the dark or the unknown excellent, may i suggest running these apps on a spare PC... i am having flash backs to when i started COM programming, my GUID registry entries would have won an award for coding horrors, and windows took about 35mins to boot up hahah the good ol days