How to implement a practical fiber scheduler?

Question

I know the very basics about using coroutines as a base and implementing a toy scheduler. But I assume it's oversimplified view about asynchronous schedulers in whole. There are whole set of holes missing in my thoughts.

How to keep the cpu from running a scheduler that's running idle/waiting? Some fibers just sleep, others wait for input from operating system.

Ludewig

Answer 1

You'd need to multiplex io operations into an event based interface(select/poll), so you can leverage the OS to do the waiting, while still being able to schedule other fibers. select/poll have a timeout argument - for fibers that want to sleep, you can create a priority queue that uses that option of select/poll to emulate a sleep call.

Trying to serve fibers that does blocking operations (call read/write/sleep etc). directly won't work unless you schedule each fiber in a native thread - which kind of beats the purpose.

See http://swtch.com/libtask/ for a working implementation.

Maddy

libtask looks nice but it does not seem to allow for explicit user scheduling of the task (i could not find an API to give cpu to a particular task). I think boost::context looks more general, and there is a layer on top called boost::fiber that implements the locks between different tasks – Instar

Answer 2

You should probably take a look at the setcontext family of functions (http://en.wikipedia.org/wiki/Setcontext). This will mean that within your application you will need to re-implement all functions that may block (read, write, sleep etc) into asynchronous forms and return to the scheduler.

Only the "scheduler fibre" will get to wait on completion events using select(), poll() or epoll(). This means when the scheduler is idle, the process will be sleeping in the select/poll/epoll call, and would not be taking up CPU.

Edmonds

How does setcontext compare on implementing it all without relying to machine stack at all? I could put coroutines wait until an another coroutine stops to imitate simple call. – Ludewig

Answer 3

Though it's a little bit late to answer, I'd like to mention that I have a practical implementation of a fiber library in C, called libevfibers.

Despite of being a young project, it is used in production. It provides a solution not only to classical asynchronous operations like reading/writing a socket, but also addresses the filesystem IO in a non-blocking manner. The project leverages 3 great libraries --- libcoro, libev and libeio.

Tetchy

Answer 4

You can control controlflow also via the use of coroutines. A library that supports the creation of those is BOOST.ASIO.

A good example is available here: Boost Stackful Coroutines

Manvell

Answer 5

From an implementation point of view, you can start with an asynchronous event loop implementation. Then you can just implement the fiber scheduling on top of that by using the asynchronous event handlers to switch to the corresponding fiber.

A sleeping/waiting fiber just means that it isn't scheduled at the moment - it just switches to the event loop instead.

BTW, if you are looking for some actual code, have a look at http://svn.cmeerw.net/src/nginetd/trunk/ which is still work in progress, but tries to implement a fiber scheduler on top of a multi-threaded event loop (with Win32 I/O completion ports or Linux's edge-triggered epoll).

Diba