Re: [boost] Cooperative Multi-Tasking

Subject: Re: [boost] Cooperative Multi-Tasking
From: Daniel Larimer (dlarimer_at_[hidden])
Date: 2010-03-04 14:04:11

On Mar 4, 2010, at 9:38 AM, Ian Emmons wrote:

> On Mar 3, 2010, at 3:37 PM, Daniel Larimer wrote:
>> I am curious whether anyone here has experience with any cross-platform cooperative multi-tasking libraries?  I am familiar with the Boost.Coroutine library, but it only provides the "primitives" or "threads".   What I am looking for is something much higher level that hides all of the coroutine details behind a asynchronous function call / future API.  Something along the line of ASIO for coroutines.  
>> 
>> I am guessing that Boost.Asio would benefit from such a library.  It seems obvious to me now that coroutines / cooperative multi-tasking is the superior approach to solving problems with a large number of actors and "locks" where heavy weight preemptive scheduling would bog down the system. 
>> 
>> Considering that cooperative multitasking is a very old concept, are there any reasons why there are no obvious libraries / scheduling systems in place?   Does everyone "roll their own" or do they avoid it for some other reason?
>> 
>> Dan
> 
> My own experience (quite old now) with cooperative multitasking comes from Windows and Macintosh GUI programming back around 1990, before Windows and Macintosh had the modern concepts of process or thread.  Your app consisted of a loop that fetched the next message/event and then acted on it.  In that model, there was a single thread running all the applications on the system.  It switched between applications by returning from the "get next message" system call in the message loop of whatever application it wanted to run next.
> 
> Is that what you mean by "cooperative multitasking" here?  If so, I would agree that it has some utility.  However, it singularly fails to utilize multiple cores/processors, which is an important thing in today's world of static CPU speed and rapidly increasing core density.  It also suffers from increased reliability problems, because it is harder in that model to isolate tasks from faults in other tasks._______________________________________________

Back when I was in middle school I was programming on Mac OS 7,8 and 9 and remember the constant reboots from infinite loops and my high school computer science class on Win 95/98 suffered the same fate!   

What I am trying to achieve is one real system thread per core and then distributing tasks (boost::function) among the cores.  Each core would then use a cooperative system for handing asynchronous calls among actors.  All of the ASIO stuff would happen in yet another real thread which would run the io_service.

Boost.Asio implements a concept of a strand for tasks that must happen in a particular order.  I was going to add to that the concept of a 'coop' (perhaps a better name???)  for tasks which don't require order, but do require that they are not actually run by two preemptive threads at the same time.   This would allow you to write actors that do not need to worry about locking.

The problem with implementing actors with Asio is that the default "future" that "blocks" or waits ties up an entire OS thread when it is really unnecessary.

Then I am going to implement the ability to bind futures to functions that are passed to the scheduler so that the method can automatically be invoked as soon as all of the parameters are ready.

The plan is to only allocate a new coroutine when ever all existing coroutines are blocked and then to keep recycling the coroutines by passing them new functions to run.

As it stands right now I have a working system that is almost entirely lock free (yet thread safe!) except when the task queue is empty and I need to wait for the next timer/event in which case I really want the process to sleep!  There is still a lot of work to be done though.

So in light of the above, I was hoping to get some insights into possible pitfalls and lessons learned.  

Talking with my employer, I am gaining support for eventually open sourcing a lot of this!   As far as I have been able to google, I have not found any system that does what I describe above.