www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Threads don't scale, processes do

reply Bartosz Milewski <bartosz relisoft.com> writes:
My new blog entry is about the scalability of the thread model for 
concurrency. I discuss some lessons from the Erlang approach.You can 
vote on it in reddit:

http://www.reddit.com/comments/6xt9h/threads_dont_scaleproceses_do/
Aug 24 2008
parent reply Oliver Dathe <o.dathe gmx.de> writes:
 Fibers (as well as Javaís green threads) are not an alternative to
 heavyweight threads. Fibers canít run in parallel, so they have no
 way to use multiple processors. They are more of a flow-of-control
 construct, often used interchangeably with coroutines.

Fibers can be passed between Threads as long as they are not currently executing. This may be implementationdepended but generally seems not to be the big issue. See tango's Fibers. I frequently thought about a model where you got an applicationdepended Scheduler/Proxy/Supervisor S which interchanges a set of Fibers between a set of Threads - controlled on each yield(). It is based on the following scenario: - Create Fibers for all kinds of independed tasks (Game scenario: Graphics, Sound, Logic, Network, Peripheral) - These Fibers don't call() each others but frequently yield() - These Fibers only get call()ed by S, and so only yield() to S - N Fibers run on M Threads that are known to S. Lets assume N>M. - S may interchange Fibers on each yield() call between the Threads according to a policy and may suspend Threads if there is too few work to be done. Some extended demands which could be well accomplished by this pattern: 1.) Let S try to keep up to C=(number of CPUs) Threads busy, s.th. these don't reach a non-blocking state from the OS's point of view (see 3 and 4). Fibers can get switched between Threads at a higher frequency than the OS's Scheduler. That is determined by the frequency of yield() usage. The OS sees noting of that internal switching. 2.) Tie priorities and timing constraints to Fibers. When distributed Fibers do yield() with an appropriate frequency, then S may handle the constraints according to the given policy. This may also incorporate Thread affinity to reduce the impacts of Thread/CPU switching. 3.) Fibers could announce blocking calls to S, so it may transfer them to a specific set of Threads which are created only for the purpose of getting blocked. This is to avoid impact on the fibers in 1.) and 2.) yieldAndAnnounceBlockingCall(); // S transfers the Fiber to some thread dedicated only for blocking // s.th. 1.) and 2.) already can be accomplished. blocking_call(); // OS suspends execution yieldAndAnnounceBlockingFinished(); // S may transfer the Fiber back to the set of Threads for 1.) // or may add the current thread to the set of Threads for 1.) 4.) Synchronization of internal ressources by S yieldAndLock( someSharedRessource ); // Scheduler handles this, possibly without OS support use( someSharedRessource ); yieldAndUnlock( someSharedRessource ); // s.th. another request can get served The latter could make locking a significantly less expensive operation, since it circumvents the necessity to get synchronized by the OS. If the Fibers respect the protocol, then S knows exactly when a ressource R is (un)used and when there are waiters. It as well does not have to fear asynchronous concurrency (Yes, S needs to be synchronized itself). Blocked waiting for R does not become a OS supported blocking call but rather manifests in the fact that S does not transfer the requesting Fiber to a Thread as long as it is in an internal blocking state (OS sees nothing of it). I created this model when thinking about a flexible architecture for games where very different kinds of competing constraints/QoS should be satisfied like network and peripheral IO (delay constraints) and graphics/physics (overall-amount-of-time constraints). The traditional way (making as much work as possible available to the OS's scheduler, using blocking calls, synchronizing through locks and hoping the OS will do an appropriate scheduling) did not seem satisfying to me. Letting an internal Scheduler/Proxy/Supervisor S interchange a set of Fibers between a set of Threads according to an applicationdepended policy and as well making the Fibers announce blocking calls to S and explicitely synchronizing through S indeed seemed very promising to me. If someone knows of similar attempts please let me know.
Aug 27 2008
next sibling parent reply Christopher Wright <dhasenan gmail.com> writes:
Oliver Dathe wrote:
  > Fibers (as well as Javaís green threads) are not an alternative to
  > heavyweight threads. Fibers canít run in parallel, so they have no
  > way to use multiple processors. They are more of a flow-of-control
  > construct, often used interchangeably with coroutines.
 
 Fibers can be passed between Threads as long as they are not currently 
 executing. This may be implementationdepended but generally seems not to 
 be the big issue. See tango's Fibers.
 
 I frequently thought about a model where you got an applicationdepended 
 Scheduler/Proxy/Supervisor S which interchanges a set of Fibers between 
 a set of Threads - controlled on each yield(). It is based on the 
 following scenario:

I find the concept of userland scheduling and green threads interesting and would work on this with you if you wish. Interpreted languages such as Erlang can pause their green threads / green processes easily; not so with natively compiled code. This may be one of the largest issues with scheduling native fibers. You might be able to get around it with enough hacks, though some would have to involve your OS's kernel, I have no doubt.
Aug 27 2008
parent reply Oliver Dathe <o.dathe gmx.de> writes:
 I find the concept of userland scheduling and green threads interesting 
 and would work on this with you if you wish.

I'd really like to follow up on this, in collaboration even better! Unfortunately I'm very busy until some time in October. However, feel free to do what you like and I'd enjoy dicussing. Have you had any similar plans before?
 Interpreted languages such as Erlang can pause their green threads / 
 green processes easily; not so with natively compiled code. This may be 
 one of the largest issues with scheduling native fibers. You might be 
 able to get around it with enough hacks, though some would have to 
 involve your OS's kernel, I have no doubt.

Yes, preemptive greenthreading would fit into this even better! But its no prerequisite, so I chose the collaborative way with Fibers for this. Not sure if the preemptive way could get accomplished with help of signal handling in a safe way. Since the proposal is for Fibers, the responsibility to yield is tied to the app developer. You're aiming for more genericity or even language support, right? A compiler could also place the yields based on heuristics or even supported by profiler runs and a chosen scheduling policy. But yes, preemption would be cooler. If blocking functions would be marked as such, then a compiler could also place the appropriate yields with the announcement that I proposed for that. What makes me a bit suspicious about the model is that it tries to manage ressources that are already managed for it. Review point 1 where it should try to keep up to C=(number of CPUs) Threads in a schedulable state from the OS's point of view. Thats just a stupid heuristic. So I see two main operation areas for this concept: greedy applications like games and applications with weak realtime demands. However it does not incur any restrictions on other types of applications and indeed they could profit from interactivity, reduced OS responsibility/activity/overhead and the multicore story. Some work that was previously only managable by the OS could be offloaded into the application. E.g. fiberspecific semaphores can get implemented with a Queue!(Fiber) for waiters plus the counter in collaboration with the userspace scheduler. That is what I was aiming for in point 4.
Aug 30 2008
parent Sean Kelly <sean invisibleduck.org> writes:
Oliver Dathe wrote:
 I find the concept of userland scheduling and green threads 
 interesting and would work on this with you if you wish.

I'd really like to follow up on this, in collaboration even better! Unfortunately I'm very busy until some time in October. However, feel free to do what you like and I'd enjoy dicussing. Have you had any similar plans before?
 Interpreted languages such as Erlang can pause their green threads / 
 green processes easily; not so with natively compiled code. This may 
 be one of the largest issues with scheduling native fibers. You might 
 be able to get around it with enough hacks, though some would have to 
 involve your OS's kernel, I have no doubt.

Yes, preemptive greenthreading would fit into this even better! But its no prerequisite, so I chose the collaborative way with Fibers for this. Not sure if the preemptive way could get accomplished with help of signal handling in a safe way.

Solaris does preemptive greenthreading automatically, so you get it for free if you use pthreads on that system. It's a pretty cool setup. Sean
Aug 30 2008
prev sibling next sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Wed, 27 Aug 2008 12:49:50 -0400, Oliver Dathe <o.dathe gmx.de> wrote:

 3.) Fibers could announce blocking calls to S, so it may transfer them  
 to a specific set of Threads which are created only for the purpose of  
 getting blocked. This is to avoid impact on the fibers in 1.) and 2.)

This sounds synergistic with thin-locks. Although locking code would have to be moved into the thread class to allow polymorphism on how the lock's aquired. i.e. Thead.getThis.lock(heavy_lock)
 If someone knows of similar attempts please let me know.

I'd recommend reading about JCSP (and it's C# and C++ brethren) and occam / occam-pi (see: http://www.cs.kent.ac.uk/projects/ofa/kroc/ ).
Aug 27 2008
parent reply Oliver Dathe <o.dathe gmx.de> writes:
 This sounds synergistic with thin-locks. Although locking code would 
 have to be moved into the thread class to allow polymorphism on how the 
 lock's aquired. i.e. Thead.getThis.lock(heavy_lock)

Polymorphism is already used for that. You could modify __monitor (or (cast(void*)this)[1]) in an object to show to a struct with an interface reference for lock() and unlock(). You can then synchronize(...) on that, so I don't think you have to touch Thread for that. That is what I've seen in tango.core.sync.Monitor.
 I'd recommend reading about JCSP (and it's C# and C++ brethren) and 
 occam / occam-pi (see: http://www.cs.kent.ac.uk/projects/ofa/kroc/ ).

Thanks, but CSP seems to have very little connection to this.
Aug 30 2008
parent Sean Kelly <sean invisibleduck.org> writes:
Oliver Dathe wrote:
 This sounds synergistic with thin-locks. Although locking code would 
 have to be moved into the thread class to allow polymorphism on how 
 the lock's aquired. i.e. Thead.getThis.lock(heavy_lock)

Polymorphism is already used for that. You could modify __monitor (or (cast(void*)this)[1]) in an object to show to a struct with an interface reference for lock() and unlock(). You can then synchronize(...) on that, so I don't think you have to touch Thread for that. That is what I've seen in tango.core.sync.Monitor.

Yup. I'd even be happy to add a setMonitor routine somewhere, but as it's one line of code anyway I didn't see the need. Sean
Aug 30 2008
prev sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Sat, 30 Aug 2008 10:35:10 -0400, Oliver Dathe <o.dathe gmx.de> wrote:

 This sounds synergistic with thin-locks. Although locking code would  
 have to be moved into the thread class to allow polymorphism on how the  
 lock's aquired. i.e. Thead.getThis.lock(heavy_lock)

Polymorphism is already used for that. You could modify __monitor (or (cast(void*)this)[1]) in an object to show to a struct with an interface reference for lock() and unlock(). You can then synchronize(...) on that, so I don't think you have to touch Thread for that. That is what I've seen in tango.core.sync.Monitor.

I think we're misunderstanding each other. Your post suggests to me that before using any shared object in a fiber, you first convert the monitor to the fiber lock-yield type and then later convert the object back when you return it to normal code. Polymorphism of the object should not be used as you don't know a prior whether an object is executing on a thread or a fiber or both, hence my suggestion of using thread polymorphism and moving the thick-lock code there. The synergy with thin-locks is that both threads and fibers should be able to take a thin-lock using the same code. Then again, since the thin-lock looks up the thread id anyways, maybe it's a moot point.
 I'd recommend reading about JCSP (and it's C# and C++ brethren) and  
 occam / occam-pi (see: http://www.cs.kent.ac.uk/projects/ofa/kroc/ ).

Thanks, but CSP seems to have very little connection to this.

I re-read your post and it looks like your really interested in scheduling and not the threading. I'd still recommend CSP simply for the implementations of user-land thread scheduling. (besides alternatives/selects are cool) I'll also mention stackthreads, if your looking for just a pure fiber library. And nanothreads got a 40% performance increase over windows fibers if I remember correctly, so it might be worth taking a look at. In D, there's also DCSP. Also, futures are very efficient implementation wise, and would be easy to extend to take scheduling parameters, like a due date and/or profiling data (i.e. generated from play testing data or on the fly to determine which routines are typically slow and which are fast and to schedule accordingly)
Aug 30 2008