[Question] Fiber yield behavior

[Guillaume227]

I am looking for a way to 'yield' from the currently executing fiber in the sense that the fiber would be sent to the back of the worker Work::fibers queue (as opposed to Work::waiting) and would otherwise resume once its turn comes, without requiring any notification, event signaling or timeout. I have been looking at the Scheduler::Fiber API and the various wait() overloads and cannot see a way to achieve that. So my questions are:

• is there a way to achieve that that I overlooked?
• if there isn't a way, is there a fundamental/strong reason why the API doesn't include that, i.e. could it be added as a contribution?

[Guillaume227]

I have just thought of a workaround: calling .wait(std::chrono::system_clock::now()); would achieve something similar to what I want, using 'now time' to force a reschedule without actually waiting. However it's still not semantically very clean and might be inefficient, so I am open to better suggestions.

[ben-clayton]

Hi @Guillaume227,

Marl doesn't really make any guarantees about order of execution - scheduled tasks that are unblocked can execute in any order. Pushing an unblocked task back on the work queue could immediately resume that task, without invoking any others, in which case you've made no forward progress with other tasks.

I'm lacking context to give advice here. Is there a reason why you can't suspend the task and use a signal to resume the task later?

Cheers, Ben

[Guillaume227]

I came upon marl as I was looking for a way to simulate some single-core embedded thread scheduling. The embedded implementation uses round robin scheduling (with some optional priority specification) for threads. My initial attempt using std::thread and std::condition_variable failed because the OS just doesn't give you enough control over when threads are going to yield/run. I then looked into coroutines (I am using c++20) but was also defeated due to the inability to co_await from nested functions.

So my scenario is specifically looking at the single thread / single worker case. In simulation mode, I swap every embedded thread instance for a marl Fiber. Those threads can be either signal-based or they run in an infinite loop with a sleep statement at the end of every iteration. Signal and sleep statements map nicely to marl's signal and wait API. I.e. I am happy for those threads to run without interruption until the next sleep/wait_signal statement (In the simulation code, I inject a call to suspend() in every sleep call from the embedded side).

On top of that I have a special control fiber that gets called once all other fibers are blocked. It is responsible for advancing the simulation clock (I swapped std::chrono::system_clock for a custom clock that give me control of the time), and for breaking out of the simulation after some time. That's the fiber that I wanted to just yield from once it has advanced the clock, without a definite wait time.

Regarding order of execution, my understanding was that I could rely on some FIFO behavior in the fibers queue. Some initial testing with just two simulated fibers (in addition to the control fiber) seemed to work, but as you say there is no guarantee so that might just be luck.

I think I am getting close to something that fits my use case, I might have to maintain some overlay in my fork for the custom clock bit and a way to specify Fiber priorities (i.e. an integer such that the Fiber with the highest prio will be picked at every suspend step out of all the fibers ready to be resumed). Maybe adding some optional sorting func that suspend would call on fibers to pick the next one to run. For the clock I am not sure how to customize the Scheduler class cleanly without making it a template which is a mess because of the logic in the .cpp file.

template<typename ClockType>
class Scheduler { ... /*yuck, everything has to go in the h file now*/ };

Thanks for the reply @ben-clayton. I am having a good time looking at your work, it's quite neat, well thought-out, elegant!

[ben-clayton]

Hi @Guillaume227 ,

Thank you for the additional context.

If you need explicit FIFO behaviours, I wonder if marl::Ticket might be helpful.

Assuming you have a way to access a shared marl::Ticket::Queue, you could have each of the fiber tasks synchronize themselves with a queue to 'round-robin' with something like:

#include "marl/defer.h"
#include "marl/scheduler.h"
#include "marl/ticket.h"

int main() {
  // Scheduler with no threads, just fibers
  marl::Scheduler scheduler(marl::Scheduler::Config{});
  scheduler.bind();
  defer(scheduler.unbind());  // unbind before destructing the scheduler.

  // Queue used to FIFO order fiber execution
  auto queue = std::make_shared<marl::Ticket::Queue>();

  // Schedule a bunch of tasks. Each task holds a loop that'll spin until the
  // work is done.
  for (int fiber_id = 0; fiber_id < 5; fiber_id++) {
    // Grab a ticket outside of marl::schedule, so that initial orders are
    // deterministic.
    marl::Ticket initial_ticket = queue->take();
    // schedule a task for the fiber of execution
    marl::schedule([=] {
      marl::Ticket ticket = initial_ticket;
      for (int i = 0; i < 3; i++) {  // Or loop until some other signal is set.
        ticket.wait();               // wait until this fiber is called
        printf("Fiber %d's turn!\n", fiber_id);
        // before we call the next ticket, grab another one at the end of the
        // queue.
        marl::Ticket next_ticket = queue->take();
        // signal we're done. The next queued fiber will now be unblocked.
        ticket.done();
        // next loop around, we'll want to block on the new ticket.
        ticket = next_ticket;
      }
    });
  }

  // All done.
  return 0;
}

Running this should give you the deterministic output:

Fiber 0's turn!
Fiber 1's turn!
Fiber 2's turn!
Fiber 3's turn!
Fiber 4's turn!
Fiber 0's turn!
Fiber 1's turn!
Fiber 2's turn!
Fiber 3's turn!
Fiber 4's turn!
Fiber 0's turn!
Fiber 1's turn!
Fiber 2's turn!
Fiber 3's turn!
Fiber 4's turn!

I'm not too sure how well this would fit with your existing changes, or the control fiber, but might give you some more ideas on how you could tackle this with the existing marl primitives.

For the clock I am not sure how to customize the Scheduler class cleanly without making it a template which is a mess because of the logic in the .cpp file.

Understood. The std clocks are not friendly for swapping, without heavy use of templates. Sorry, I don't have any suggestions here.

Thanks for the reply @ben-clayton. I am having a good time looking at your work, it's quite neat, well thought-out, elegant!

Very kind of you. Thank you!