WallOS v0.5.0 - Scheduler

This week I have released the WallOS scheduler.

The scheduler design itself has been in the works for a long time. I've just now been motivated enough to actually finish the design and implement it.

Design

The WallOS scheduler, named the WallOS "Fair Enough" Scheduler (WFES), is basically a very complicated version of a round robin scheduler. It has different priority levels that determine how much of a timeslice a task gets, plus a few extra rules on top for the cases that I felt plain round robin handles badly.

I didn't want an overly complex scheduler, and didn't feel the need to make some completely fair system for it. I designed my scheduler around being simple to understand, wouldn't need a ton of coordination between CPUs, and would behave relatively predictably.

The "Fair Enough" was my whole philosophy when writing it. The scheduler tries to "approximate" fairness, rather than guarantee it. Starvation is mitigated (a long queue can run a few tasks back to back to try to balance it out), but nothing gets hard latency or throughput guarantees.

Cross Communication

Every CPU is on it's own. There is very little need for cross CPU communication. Each CPU owns it's own queues and makes it's own scheduling decisions. There are a few certain spots they are forced to communicate of course (creating a task, balancing), but overall very little cross communication is going on. This greatly simplifies having to worry about deadlocks.

Priority

There are ten levels of priority, and each one gets half the runtime of the one above it. Priority 5 is the default and gets a 16 ms quantum, so priority 2 gets 128 ms and priority 9 gets 1 ms. Priorities 0 and 1 are special, they are interleaved between every other task so latency-sensitive work gets in quickly, and their time is capped so they can't swallow the CPU:

P0 -> P1 -> P2 -> P0 -> P1 -> P3 -> P0 -> P1 -> P4 -> ...

Affinity

A task can be pinned to a CPU in two ways, either soft or hard. Soft affinity is almost always respected, only being moved in very certain circumstances (mostly to do with the system having very little work to do in general). Hard affinity is "absolute" (more on that later), and a task that uses it has the potential to never run (the kernel can freely take over a CPU as it needs).

Balancing

Balancing is lazy. An idle CPU steals work from its neighbors and backs off exponentially if there's nothing to steal, and every few seconds each CPU does a quick check to see whether it's badly out of balance. Each CPU runs it's own balancing pass, and will balance against the first other CPU it finds that is unbalanced in comparison. This avoids having to have all CPUs communicate for balancing.

Blocking

Blocking isn't really managed by the scheduler. The scheduler keeps note that the task is blocked, but doesn't know what it's blocked on. Blocking subsystems are required to wake the task when they can be unblocked, and remove references to the task in case they are destroyed while blocked. The CPU will simply not schedule tasks that it sees are blocked, and will tell the subsystem to remove references if it's been destroyed.

Kernel Tasks

The kernel can preempt anything. Normal tasks run until their quantum is up. Kernel tasks can cut in immediately, take over a CPU, or run without being time-sliced. Nothing else is allowed to end a task's quantum early.

There is a special category of tasks that can do basically anything they want, kernel tasks. They can preempt tasks mid quanta, take over a CPU (forcing all tasks to be put on other CPUs), or run to completion. These are are meant to be high priority tasks that need to be dealt with immediately. These being "kernel" tasks does not mean that all tasks in the kernel are special, regular tasks can still be run in ring 0.

Code Split

I designed the code have a split between "core" and architecture dependent scheduling. I wont go into too much detail here (there's a doc that better describes this), but I designed it with the hopes that it would be relatively easy to port to other architectures without changing the core functionality of the scheduler.

What's next

Everything below is in order of importance.

Exit Status and Wait-For-Child

I designed the scheduler initially without considering the possibility that I would want task exit status (I know, it's kinda and important thing, just overlooked when first writing it). The scheduler needs a way for parent tasks to wait on children to return, meaning we need a ZOMBIE state for the tasks to live in, and a way to deliver the exit statuses to the parent. This in theory shouldn't require a huge rewrite, but does need some more careful planning.

User Mode

Currently there is no way to create a user mode task. All tasks are in ring 0. This requires some more work on my side, in particular in the x86_64 port, in order to support swapgs. I also need to update the GDT, add on to the VMM, SYSCALL/SYSRET, and rewrite a lot of the IDT to actually support swapping from user to kernel and back, and handling faults differently depending on the mode they came from.

User mode isn't a huge daunting task, most of the underlying work is ready, mostly just a lot of small changes in a lot of different spots.

Hard Affinity Tasks

Hard affinity tasks currently have no way to get information back from the kernel in the event of a takeover. I actually don't know if I will have them get a signal (as I wrote in the spec), and actually have a new proposal:

Each hard affinity task, upon creation, gets to decide how it wants to be handled in the event of a takeover. It would have an option to stay on the cpu (how it is currently, no signal), be destroyed, "demoted" to a soft affinity task (and moved), or moved (as a hard affinity) to a new CPU. In the latter two, it would receive a signal from the new CPU to be alerted that it's been moved.

This would allow for hard affinity tasks and takeovers to be simplified. This is likely what I will implement, as before, we'd need a way to send a signal and then give the task a small time to run to figure out what to do. This takes away a lot of the complexity.