On Tue, Sep 8, 2015 at 7:21 PM, Oliver Kowalke wrote:

2015-09-08 13:34 GMT+02:00 Giovanni Deretta :

...

My first concern is that scheduler is a global (per thread) property. This makes sense, but it limits its usability in libraries, unless the library completely owns a thread.

the scheduler is only entered if a function from boost.fiber is called. code outside of fiber code is ‎unaffected how does it limit the usability?

Two different libraries can't use boost.fiber if they require a custom scheduler or they need to run their own threads. Basically the scheduler is a scarce resource and limits composability. Of course code that doesn't know about fibers isn't affected.

It would be nice if schedulers where schedulable

...

entities themselves, so that they could be nested (more at the end).

in the current design each thread has one scheduler (the scheduler is hidden). a scheduleable entity is a fiber context (fiber's stack), that means that each boost::fibers::fiber is attached to one fiber context (detaching a fiber means decoupleing from the context).

how do you detach a fiber by a context? What does it mean? Did you mean detach a fiber+context from a scheduler?

the scheduler maintains several queues (waiting ,ready ,...) containing fiber context's depending on their state (waiting, ready ,...).

why are the wait queues part of the scheduler itself? Shouldn't they be a property of the waitable primitive?

the scheduler_algorithm (customizable) defines how ready context's are sorted (round-robin, priority-queue,...) for resumption. if a fiber context becomes ready the scheduler calls scheduler_algorithm::awakened() and passes the fiber context to the algorithm. in order to resume the next context, the scheduler calls sched_algorithm::pick_next().

ok, that matches my understanding.

if a scheduler would be schedulable, it would have been a context - a scheduler would then schedule itself. I'm uncertain how your schedulable schedulers would fit in this pattern (probably not very well).

One option is scheduling schedulable entities. Something like schedulable { schedulable * next, * previous; void (*run)(schedulable*self); // or use a virtual }; but there are of course advantages in knowing that each schedulable is a contex as you can swapcontext to it.

...

Also the description of the scheduler interface does not specify any thread safety requirements. I assume that at least awakened must be thread safe as the scheduling might be caused by a signal coming from another thread. Any requirements should be specified properly. This leads to two additional points.

in the context of migrating fibers between threads, yes. boost.fiber started in the review claiming that fiber-migration is not supported, thus the thread safety requirements are not mentioned.

yes, but a running fiber bound to thread 1 can still signal a waiting fiber bound to thread 2 (via a condition variable for example), so there must be some thread safe mechanism for for transitioning a waiting fiber to runnable, i.e. a way to add it to the ready queue. I thought that 'awakened' was supposed to do that. Ok, I went and looked at the code. I see that on wakeup, the context is simply marked as ready. The main scheduler loop, after each scheduling event goes through the wait list and moves ready contextes to the main thread. It sleeps for a specific interval if there are no runnable contextes. This has multiple issues. First of all the periodic sleeping is extremely bad. If 'run' can't do anything right now, it shouldn't sleep a fixed interval, it should instead block waiting for an external signal (on some applications, busy waiting could be an option). Second, scanning the wait list for ready contextes at every rescheduling doesn't really scale; for such a simple scheduler, scheduling should be strictly O(1). Timers have similar issues. This is how I would expect a scheduling algorithm to work: context { atomic next; scheduler* preferred_scheduler; }; context * this_context; // currently running scheduler* this_scheduler; // current scheduler scheduler { intrusive_slist<context> ready; intrusive_slist<context> ready_next; atomic_intrusive_slist<context> remote_ready; event_count ec; atomic<bool> done; // can be used to interrupt the scheduler // this is the idle task, itself a fiber. Should run in the original thread stack void idle() { while (true) { auto n = get_next(); while (n == 0) { int ticket = ec.prepare_wait() if ((n = get_next()) { ec.retire_wait(); break; } ec.wait(); } ready_next.push_back(this_context); switch_context(n, this_context); // the idle fiber should also pump the timer queue and react to external interrupt signals. // when running inside asio, it will also pump the io_service (or return to it). // in a work sharing setup would also answer external requests for work. } } void remote_add(context *w) { remote_ready.push_back(waiter); ec.signal(); } }; context * get_next() { if (auto n = ready.pop()) { return n; } if (auto n = remote_ready.pop_all()) { ready_next.splice_back(n); // whole list not just one element } swap(ready_next, ready); return ready_next.pop(); } void yield() { auto n = get_next(); assert(n); ready_next.push_back(this_context); switch_context(n, this_context); } // make a context ready void signal(context* waiter) { if(waiter->preferred_scheduler != this_scheduler) { // cross thread waiter->preferred_scheduler->remote_add(waiter); } else { // no preference or local this->scheduler.next_ready.push_back(waiter); // alternatively push this_context to back of queue and yield to waiter immediately } } // put this context to sleep on some queue (a mutex, condar, future, barrier, etc.) void wait(wait_queue* w) { auto n = this_scheduler->get_next(); assert(n); // these two should be done under the wait_queue spinlock or in reverse order to be safe from concurent remote wakeups w.push_back(this_context); } -- gpd

Oliver Kowalke writes:

2015-09-09 0:19 GMT+02:00 Giovanni Piero Deretta :

...

On Tue, Sep 8, 2015 at 7:21 PM, Oliver Kowalke wrote:

...

2015-09-08 13:34 GMT+02:00 Giovanni Deretta :

...

My first concern is that scheduler is a global (per thread) property. This makes sense, but it limits its usability in libraries, unless the library completely owns a thread.

the scheduler is only entered if a function from boost.fiber is called. code outside of fiber code is ‎unaffected how does it limit the usability?

Two different libraries can't use boost.fiber if they require a custom scheduler or they need to run their own threads. Basically the scheduler is a scarce resource and limits composability.

OK, good point! One of the design decisions for boost.fiber was that the scheduler itself is not visible (the user code does not instantiate it). the library should work similar to std::thread (os-scheduler not visible ...).

The point is that the scheduler is not completely invisible as it can be replaced. As the default scheduler is very basic, replacing it becomes pretty much a requirement.

of course if this decision is given up, the user creates (on stack or heap) a scheduler and if a new fiber is created the code must specify to which scheduler the fiber belongs to.

my_scheduler ms;

fiber f( ms, fn, arg1, arg2),

Specifying an explicit scheduler would be a nice addition, but if not specified, it should default to the current scheduler for the thread.

in the context of migrating fibers between threads:

- in the current design only single fibers are moved between schedulers running in different threads - you suggest that the scheduler itself is moved between threads?!

As I suggested elsethread, a child scheduler would appear to the parent scheduler as another fiber, so if that fiber is migrated, the whole scheduler is.

...

...

It would be nice if schedulers where schedulable

...

entities themselves, so that they could be nested (more at the end).

in the current design each thread has one scheduler (the scheduler is hidden). a scheduleable entity is a fiber context (fiber's stack), that means that each boost::fibers::fiber is attached to one fiber context (detaching a fiber means decoupleing from the context).

how do you detach a fiber by a context? What does it mean? Did you mean detach a fiber+context from a scheduler?

boost::fibers::fiber has a member pointer to boost::fibers::context boost::fibers::scheduler manages boost::fibers::context * detaching means boost::fibers:.fiber relases its pointer to boost::fibers::context.

the scheduler still manages (scheduling/lifetime) the detached context (boost::fibers::context is a control structure residing on the top of the fiber-stack)

Ok, I think I understand; I was thinking about fiber the abstract concept, while you of course meant the boost::fiber::fiber class, which can be detached like an std::thread. Although now I can't see how detaching is relevant to the nested scheduler discussion... -- gpd

Hartmut Kaiser writes:

Giovanni Piero Deretta :

...

Oliver Kowalke writes:

...

of course if this decision is given up, the user creates (on stack or

...

a scheduler and if a new fiber is created the code must specify to which scheduler

heap) the

...

fiber belongs to.

my_scheduler ms;

fiber f( ms, fn, arg1, arg2),

Specifying an explicit scheduler would be a nice addition, but if not specified, it should default to the current scheduler for the thread.

Hmmm, I would prefer if the scheduler and fiber interfaces were left orthogonal. A fiber is just a callable,

A fiber itself is not just a callable though, it is logically a sequence of callables (each callable is the next continuation at wait and yield points). At each reschedule point, the fiber needs to know which executor need to use for the next continuation. The same issue happen with plain 'executed' function object that need to execute another continuation, it either needs to know the executor explicitly or there must be a default (possibly thread specific one). There are obviously advantages to using n4406 executor interface as a scheduler, especially as something like that is likely to be standardized. On the other hand a specialized fiber scheduler has its advantages, for example it never not need memory allocation to schedule a continuation as it can always use intrusive hooks to concatenate context objects which are guaranteed to persist; also knowing that the task you are yielding to is a fiber has some advantages as you can directly swap-context to it. It should always be possible to adapt an n4406-like executor to work as a fiber scheduler. Boost.Fiber might provide a generic adapter. -- gpd

Hartmut Kaiser writes:

Giovanni Piero Deretta :

...

Hartmut Kaiser writes:

...

Giovanni Piero Deretta :

...

Oliver Kowalke writes:

...

of course if this decision is given up, the user creates (on stack

...

a scheduler and if a new fiber is created the code must specify to which scheduler

or heap) the

...

fiber belongs to.

my_scheduler ms;

fiber f( ms, fn, arg1, arg2),

Specifying an explicit scheduler would be a nice addition, but if not specified, it should default to the current scheduler for the thread.

Hmmm, I would prefer if the scheduler and fiber interfaces were left orthogonal. A fiber is just a callable,

A fiber itself is not just a callable though, it is logically a sequence of callables (each callable is the next continuation at wait and yield points). At each reschedule point, the fiber needs to know which executor need to use for the next continuation.

If a fiber is not a callable, then exposing it using a std::thread-compatible interface does not really makes sense.

I can't parse that. Certainly I wouldn't expect boost::fiber::fiber to be a callable; then again, neither is std::thread.

...

The same issue happen with plain 'executed' function object that need to execute another continuation, it either needs to know the executor explicitly or there must be a default (possibly thread specific one).

I don't see a reason not to expose the executor used to schedule the fiber. Something like

auto exec = this_fiber::get_executor()

oh, sure, I'm completely in favor of that; but I also think that there should be a notion of an optional preferred fiber executor[1] (or scheduler), which will be used in preference to the thread local executor for plain yields and wakeup (for example a fiber::condition_variable::signal need to know where to schedule the woken up fibers, and the thread local executor might not be the correct place). [1] currently in Boost.Fiber this exists, and it is not optional. -- gpd

2015-09-09 0:19 GMT+02:00 Giovanni Piero Deretta :

...

the scheduler maintains several queues (waiting ,ready ,...) containing fiber context's depending on their state (waiting, ready ,...).

why are the wait queues part of the scheduler itself? Shouldn't they be a property of the waitable primitive?

the scheduler has a wait queue as well as each waitable primitve has a wait queue. the wait queue inside the scheduler is especially required for detached fibers at termination (~scheduler())

...

if a scheduler would be schedulable, it would have been a context - a scheduler would then schedule itself. I'm uncertain how your schedulable schedulers would fit in this pattern (probably not very well).

One option is scheduling schedulable entities. Something like

schedulable { schedulable * next, * previous; void (*run)(schedulable*self); // or use a virtual };

but there are of course advantages in knowing that each schedulable is a contex as you can swapcontext to it.

the scheduler simply know which fiber can be resuemd next. if fiber f1 has to suspend (maybe joins another fiber) it calls the scheduler to select the next fiber f2 and transfer execution control to fiber f2 (context switch). the process of selecting the next fiber and calling the context switch are running inside fiber f1. that means that we have a call chain between fibers. I'm uncertain what schedulable::run() should execute if the schedulable is a scheduler and a context switch is called (what doesn't make sense to me).

Ok, I went and looked at the code. I see that on wakeup, the context is simply marked as ready. The main scheduler loop, after each scheduling event goes through the wait list and moves ready contextes to the main thread.

not main thread - it moves fibers, that have been signaled as ready, from the waiting queue to the ready queue (that is sched_algorithm::awakened() is used for). sched_algorithm::pick_next() selects a fiber from its internal ready-queue.

This is how I would expect a scheduling algorithm to work:

<snip> I've to think about your suggestion how it could applied to the current code

2015-09-09 0:19 GMT+02:00 Giovanni Piero Deretta :

context * this_context; // currently running scheduler* this_scheduler; // current scheduler

scheduler { intrusive_slist<context> ready; intrusive_slist<context> ready_next; atomic_intrusive_slist<context> remote_ready; event_count ec; atomic<bool> done; // can be used to interrupt the scheduler // this is the idle task, itself a fiber. Should run in the original thread stack void idle() { while (true) { auto n = get_next(); while (n == 0) { int ticket = ec.prepare_wait() if ((n = get_next()) { ec.retire_wait(); break; } ec.wait(); } ready_next.push_back(this_context); switch_context(n, this_context);

<snip> the scheduler with its idle() function would introduce extra context switches because idle() enqueues the scheduler to the ready_next-queue before it switches to the next fiber. seams that the scheduler (fiber) is resumed after each (worker)-fiber. boost.fiber tries to prevent this - it switches only between (worker)-fibers, the scheduler functions only like a store for the next fiebrs.

Oliver Kowalke writes: <snip>

the scheduler with its idle() function would introduce extra context switches because idle() enqueues the scheduler to the ready_next-queue before it switches to the next fiber. seams that the scheduler (fiber) is resumed after each (worker)-fiber. boost.fiber tries to prevent this - it switches only between (worker)-fibers, the scheduler functions only like a store for the next fiebrs.

The idea is that yield and friends would switch to the idle fiber only when they reach the end of the ready queue. To be clear: there are two ready queues: ready and next_ready. Yield pops from ready and pushes into next_ready. ready is never empty, as the last element in the list is always the idle fiber. When the idle fiber is run, it moves the content of next_ready into ready and pushes itself at the end of ready. So yes, if you have N ready tasks yielding, there are N+1 context switches (but not 2*N) per iteration. The cost of the additional idle task is amortized over N tasks. On the other hand, yield becomes simply a push+pop+switch. All corner cases (empty queue, handle off thread signals, pump the timer queue) are handled inside the idle task. Of course a completely equivalent setup is to have an idle function and call it at the end of the ready queue. I do not claim that the idle fiber solution is superior; although it find it elegant, it was not really the core of my criticism of the current scheduler. -- gpd

2015-09-11 11:02 GMT+02:00 Oliver Kowalke :

2015-09-11 10:48 GMT+02:00 Giovanni Deretta :

...

So yes, if you have N ready tasks yielding, there are N+1 context switches (but not 2*N) per iteration. The cost of the additional idle task is amortized over N tasks.but

the idle-fiber pushes itself to ready_next before switch_context() is called that would mean that idle-fiber is called every second time

OK - you are right, please ignore my posting

Oliver Kowalke writes:

2015-09-11 10:48 GMT+02:00 Giovanni Deretta :

...

The idea is that yield and friends would switch to the idle fiber only when they reach the end of the ready queue.

the idle-fiber executes only function idle() - why not simply execute idle() instead of switch_context(n, this_context); at the end of scheduler::yield()?

what are the reasons that idle() must run on an extra fiber-stack?

As I said elsewhere, there is no fundamental reason and, although I consider the idle fiber a better solution, I would be perfectly fine with a scheduler that doesn't have such a thing and simply called the idle function when appropriate. Note that unconditionally calling idle at the end of yield is not necessarily ideal though, as the idea is that it might execute more expensive operations that you want to do only at the end of an 'epoch' (i.e. when all ready fibers have executed once). Adding a conditional test on yield opens up the possibility of a misprediction. At that point the cost of an additional fiber switch is minimal. The fact is, often there is an existing idle fiber anyway; if you spawn a dedicated thread to run a scheduler, the thread has an implicit fiber which would go otherwise unused; if you are running on top of another scheduler (for example boost::asio::io_service or one of the proposed executors), the idle fiber is simply the context of the underlying scheduler callback; in this case after control reaches back the idle fiber, it is appropriate to return control to the underlying io_service and reschedule another callback (with asio::post for example); Nested scheduler support would fall of naturally and almost transparently on top of this model, together with the ability to temporary override the current thread local scheduler. A nested scheduler idle fiber would appear as just another fiber in the parent scheduler loop. To be clear, the major concerns I have with the current scheduler designs are: - lack of proper cross scheduler wakeup. - unconditional sleep when the scheduler is empty. - the handling of waiting tasks (including the clock wait queue). All three issues are tightly interwoven. Idle tasks, nested schedulers would all be nice to have for me, but not deal breakers. -- gpd

Oliver Kowalke writes:

2015-09-11 15:14 GMT+02:00 Giovanni Deretta :

...

- lack of proper cross scheduler wakeup. - unconditional sleep when the scheduler is empty. - the handling of waiting tasks (including the clock wait queue).

your concerns are already addressed in another branch

Is this the 'signal' on github branch? If possible, I would like to hold my final review until this work is, if not completed, at least in a state where the design forward is clear. -- gpd

// make a context ready void signal(context* waiter) { if(waiter->preferred_scheduler != this_scheduler) { // cross thread waiter->preferred_scheduler->remote_add(waiter); } else { // no preference or local this->scheduler.next_ready.push_back(waiter); // alternatively push this_context to back of queue and yield to waiter immediately } }

to push a ready fiber to the scheduler from a waitable (mutex, condtion-variable ...) might be a better solution than signaling via an atomic. I'll branch and test your suggestion. thx