Refactoring the scheduler (& sleeping)

[niaow]

At the time of writing, the scheduler works as the following loop:

1. check the time
2. if the front of the timer queue has already passed, then push the goroutine to the back of the scheduler queue
3. take the next task on the runqueue
4. if it is nil, go to sleep and ask for a wakeup; if it is non-nil, run it

This model was built before interrupts were part of the scheduler, and so incorporating interrupts is difficult. At the bare minimum, the timing code needs to be able to return early in case of interrupt so that interrupts can be handled properly.

Our current scheduler also has a few other issues:

1. When handling large amounts of small events, we spam-check the timer. On some platforms this is very fast, while on others like embedded Linux it can become a bottleneck.
2. Timing is tightly coupled to the scheduler, which may make it more difficult to make modifications.

[niaow]

To reduce the number of checks we have to do, we could replace the queue with a stack. Things that are being immediately resumed (by e.g. channel recv operations), get pushed onto the resume stack. We then check for events and push them onto the resume stack. If the resume stack is still empty, we go into an idle mode to wait for an event. Otherwise we extract the head and reset the stack, and run the old stack. This retains most of the fairness properties as before - a goroutine will not be resumed a second time until all other enqueued goroutines have also been resumed first. The main advantages of this are that it reduces the complexity of the scheduler and reduces the frequency of polling for events.

[niaow]

The bigger change here involves making changes to timing code to remove the assumption that timers are the only async event source. As interrupts are added, this assumption breaks, and as a result we will have to change timer code on all platforms (or most). I would like to propose that we move the platform-dependent code over to a slightly different API:

func wait()
func ticks() timeUnit
func delay(timeUnit)

In the implementation of time.Sleep, rather than using a builtin mechanism, we would call delay. This would be an async function which would be defined differently on different platforms. On some system we may even want to use different timers for different durations. The mechanism this used would be mostly transparent to the scheduler.

The wait function would be called by the scheduler when no events are currently available. In order to do this upgrade incrementally, we could start by moving the old timing code into here. As we make interrupt-aware systems, we would replace the definition with a platform-specific version which supports interrupts. This way we can gradually roll out interrupt support rather than having a single PR take forever.

And ticks() would remain the same.

[aykevl]

To reduce the number of checks we have to do, we could replace the queue with a stack. Things that are being immediately resumed (by e.g. channel recv operations), get pushed onto the resume stack. We then check for events and push them onto the resume stack. If the resume stack is still empty, we go into an idle mode to wait for an event. Otherwise we extract the head and reset the stack, and run the old stack.

How is this resume stack different from the runqueue as it exists today?
You do have a good point that as long as there are entries in the runqueue, there is no point in checking the sleep queue. So the scheduler could be optimized slightly by basically running with a few nested loops (in pseudocode):

loop forever:
    while runqueue is not empty:
        pop a task from the runqueue, and run it
    now := current time
    while sleep queue has task that is runnable (meaning its time has expired):
        pop that task from the sleep queue, and add it to the runqueue
    if no entries in the runqueue:
        sleep until the first sleep queue entry is runnable (or sleep forever if no tasks are ready)

However, interrupts are still not present in this architecture. So what if we combine the two, interrupts and sleep? After all, sleep is implemented as an interrupt on most chips. For example, it could work a bit like this:

loop forever:
    while runqueue is not empty:
        pop a task from the runqueue, and run it
    sleep (to be woken up by an interrupt)

So to sleep a task, it is added to a separately managed sleep queue, with a timer set to expire when the first task is ready to run. Whenever a task is added to the front of this sleep timer, the timer is reconfigured to that time. In the interrupt handler of this timer, the timer will add all tasks to the runqueue that are ready to run, and configure itself to trigger on the next task (if there is any in the sleep queue). In this architecture, it is trivial to add tasks to the runqueue from interrupts as that needs to be supported anyway for sleeping.

This is what I come up quickly, I haven't yet given much thought to how this should be implemented in practice, and how a gradual rollout can be done.

[aykevl]

Can you also describe how the scheduler would look, with your proposed API?

[niaow]

You do have a good point that as long as there are entries in the runqueue, there is no point in checking the sleep queue.

This actually was not my point, and is actually not true. While this works when there isnt much going on, the behavior starts to diverge as the system gets close to 100% busy time under intense workloads. If we just kept checking the runqueue, there would almost always be something there and there would be a huge delay between the time being reached and the goroutine being resumed.

My idea was analogous to choosing the current end of the runqueue, and then running everything up to and including that. After that we would check for events, push those to the runqueue, and repeat. This would ensure that all events get processed reasonably close to when they arrived, even if the system is under an extreme amount of load. The disadvantage of this is that it has the same overhead when only processing one goroutine.

[niaow]

Can you also describe how the scheduler would look, with your proposed API?

In pseudocode:

loop forever:
    check for events and push them to runqueue
    if the runqueue is empty, wait and then restart the loop
    find the current end of the runqueue, and pop off tasks until previous end reached
        run each

I have not quite decided how to handle checking for events. In #606, I had a function:

func popInt() *task

which returned a chain of tasks. However this might be a little too dependent on interrupts. We could potentially just rename it something like pollEvents to generalize it. This would need to be implemented differently on different platforms:

• on linux/darwin: call poll/epoll/related without blocking
• on bare metal: do what popInt currently does (read from an interrupt-safe queue)
• on WASM: probably return nil unless some hosted platform has something analagous (this will get optimized away)

As for wait(), this would eventually just call the appropriate wait-for-interrupt instruction (or syscall). On WASM, we will probably just return instead, as we have done previously.

[niaow]

In order to roll this out incrementally, the current timer logic could initially be moved into a default implementation of pollEvents/wait. As we add proper support on each platform, we would remove the build tag and allow it to use its own implementation.

[niaow]

As for how to implement timers, we actually have some trade-offs that we need to investigate. The main difference comes in when we decide to actually configure the hardware timer interrupt. We could:

• configure it when calling delay - this would have the advantage that we never have to check the time in pollEvents, but may increase the number of times we have to reconfigure the timer interrupt
• configure it in pollEvents - this would have the advantage that we only configure the timer interrupt a maximum of once per scheduler cycle, and we also dont have to touch the timer every scheduler cycle if the timer queue has not been modified
• check the timer in pollEvents, set the interrupt in wait - this would mean that we check the time on every iteration, and only set an interrupt before going to sleep; this does not require checking the time after waking up from a non-timer event

Whenever a task is added to the front of this sleep timer, the timer is reconfigured to that time.

This is more or less the first option I have listed here.

[niaow]

In this architecture, it is trivial to add tasks to the runqueue from interrupts as that needs to be supported anyway for sleeping.

So in #606, I used a slightly different approach where I had a seperate, differently structured, run stack for interrupts. I had multiple stacks of tasks that I would switch between, and the interrupts would write into whichever one the scheduler was not currently looking at (I basically used double buffering). However, I used a stack instead of a queue simply because they are easier to implement for interrupt-safe behavior. That being said, we could easily just use the same code and have the things resumed by channel operations use the same code as interrupts (except on AVR because AVR is weird, but we dont do that on AVR yet).

At least for now, I think having a separate queue for incoming interrupts will be easier to manage.

[niaow]

An implementation is in progress in #1006.