Re: [boost] [fiber] on schedulers and wakeups

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