# 68KOS scheduler

The 68KOS scheduler uses a multilevel queue system. Each priority level is
represented by a FIFO. Each task has a minimum and maximum priority, and each
event source (on which tasks can block) has a starting priority.

When a task is created, it is spawned at the default priority level. (For a
real-time task, it can be spawned at a higher priority with its minimum
priority bounding it there.) It also has a counter to track how much time it
has spent at this priority level.

When the scheduler needs to decide which task is to run next, it scans the
priority queues in decreasing order of priority and finds the first ready task.
It decrements the counter, and begins executing the task.

When a task is preempted, if its counter has reached zero, it is moved down one
level into the next priority queue down (as far down as its minimum priority
will permit), and reloads the counter to that priority's starting count.

When a task moves from Blocked to Ready, it is placed into the starting priority
of the event source on which it was waiting, with the counter initialized to
that priority's starting count.

This has the effect of bumping tasks to foreground when they become ready,
then downgrading them more and more as they consume more CPU time. It also
permits real-time tasks that always run ahead of others, by bounding their
priority at a minimum level.

Nominally, there are 16 priority levels, with the system default priority being
7, and priorities 8-15 reserved for real-time tasks.

## TCB (Task Control Block)

```c
struct tcb {
	cpu_state_t cpu_state;

	unsigned max_prio;
	unsigned min_prio;
	unsigned time_counter;

	// Pointer to what we're blocking on. If NULL, we're ready.
	// If the thread wants to block on multiple things, just create a
	// "tee blocker" that sinks events from multiple sources.
	struct event_source * blocker;

	// Next thread in the priority queue or blocker list
	struct tcb * next_in_queue;

	// Next thread in the process
	struct tcb * next_in_process;

	// Parent process
	struct pcb * process;
};
```

## PCB (Process Control Block)

```c
struct pcb {
	// bitfield is just pseudocode. The selected and prio_accum fields
	// at least will be implemented in the same integer to allow an
	// overflow optimization.
	enum mode {
		MODE_SUPERVISOR, // Do not exit supervisor mode when running
		MODE_LOADER,     // User mode; allow extra loader features
		                 //   (export symbol, change page permission,
		                 //   move mode from loader to user)
		MODE_TASK,       // User mode
	} : 2;

	// Linked list of threads
	struct tcb * threads;

	// Linked list of all owned resources that can be freed on exit,
	// including RAM, excluding files.
	struct resource * resources;

	// Array of open file descriptors - use doubling reallocation to grow
	// this each time new space is needed, do not free it until the process
	// exits
	struct file_descriptor * file_descriptors;

	// Next process in the list
	struct pcb * next;
};
```

## Event sources

Event sources all live in kernel space, and store a list of all the tasks
blocking on them. When they produce an event, they move all tasks in their list
to their starting priority.