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

Subject: Re: [boost] [fiber] on schedulers and wakeups
From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2015-09-08 18:19:11

On Tue, Sep 8, 2015 at 7:21 PM, Oliver Kowalke <oliver.kowalke_at_[hidden]> wrote:
> 2015-09-08 13:34 GMT+02:00 Giovanni Deretta <gpderetta_at_[hidden]>:
>
>> 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<context*> 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