Friday, January 21, 2011

Cooperative multitasking using the Eventually workflow

In cooperative multitasking at most one task executes at any time. In order for another task to execute, the task currently in control must explicitly pause itself. The scheduler keeps track of which task is executing, which tasks are ready to be executed and which are blocked or sleeping.

This form of multitasking lacks concurrency, which makes it easy for multiple tasks to synchronize and communicate. On the downside, it is not suitable for improving performance of cpu-bound computations.

I have implemented a cooperative-multitasking "operating system" consisting of a scheduler and a couple "system calls" which I believe will make it easier for me to develop the menu systems of my future games. In this article I describe the design and API of this light-weight operating system.

The scheduler

The scheduler is implemented in class Scheduler in CoopMultiTasking.fs, where these methods are available:
  • AddTask: A task is an Eventually<unit> computation expression, and can be added to the scheduler using this method. The task won't execute until method RunFor is called. A task is removed from the scheduler after it completes.
  • HasLiveTasks indicates if the scheduler has at least one task which hasn't completed.
  • RunFor executes all ready tasks for a specified amount of time. Typically, this should be 1/60 for a game running at 60 frames per second, but any value will do. It is for instance possible to "fast-forward" execution by passing durations that exceed the amount of real time that has passed. See "Simulated time vs real time" below for details.

The system calls

Class Environment makes it possible for tasks to interact with the scheduler to control their execution and spawn sub-tasks.
  • Spawn allows a task to add a sub-task to the scheduler. The scheduler returns an instance of TaskController which can be used to instruct the sub-task to complete early and to wait for the sub-task to complete early. Spawn does not actually take a task, but a function which takes a reference to a Boolean and returns a task. The Boolean indicates when the task should kill itself. See "Killing sub-tasks" below form more information.
  • SpawnRepeat is a variant of Spawn which executes a sub-task in a loop. It returns a TaskController which can be used to interrupt the loop. Unlike Spawn, this method expects a task. The sub-task should be very short, as an iteration of the loop cannot be interrupted.
  • Wait causes the task to wait a specific duration. Note that this duration does not correspond to real time, but to durations as passed to RunFor.
  • Yield causes the task to stop executing, but remain ready for execution. If another task is ready, the scheduler executes it, otherwise the task continues executing.
  • WaitNextFrame causes the task to stop executing until the next time the scheduler's RunFor is called.
  • WaitUntil takes a function with signature unit -> bool. The task is paused until the function returns true. The function is first evaluated in the current frame without waiting, then once per call to RunFor. Note that the first evaluation of the function is preceded by an implicit call to Yield.

Simulated time vs real time

The time inside this environment, which I call simulated time, does not correspond to real time. Simulated time passes every time RunFor is called by the amount of time specified to RunFor.

Even if you always pass to RunFor the amount of real time that has passed, the amount of time tasks wait is not coupled to real time. This is due to RunFor never sleeping, even when all tasks are waiting. Instead, it directly advances the simulated time.

Tasks which are waiting for durations exceeding the frame time wake up during the correct frame. Within a frame, tasks wake up in the correct order, in accordance to their amount of time left before waking up.

Killing sub-tasks

It is not possible to forcibly kill a sub-task. Instead, a notification mechanism using a reference to a Boolean cell is used. It is the responsibility of the sub-task to test this cell often enough that excessively long delays after requesting termination do not occur. I realize this may not be a popular design decision, as this forces one to sprinkle the code of tasks with checks for termination requests. The rationale behind this decision is that uncontrolled termination can leave an application in an incorrect state. I don't feel strongly about that point, though.


rei said...

Regarding killing subtasks, how about if all of the wait/yield functions took a value indicating whether or not the task is in a state safe for termination, and recorded them in the Eventually union?

For instance, something like:

task {
// some work that causes invalid state
do! env.Yield false // "false" tells the scheduler that it's not safe to terminate the thread even if someone asked for it to be terminated
// some work that puts the task's data back into a valid state
do! env.Yield true // "true" tells the scheduler that if someone is requesting that this task be terminated, it should be

Joh. said...

@rei: The problem is that the responsibility of declaring whether it's safe to interrupt the thread falls on the deepest subtask, but it lacks the information to make that decision: The caller and every other level in the stack trace may be in an non-interruptible state.

rei said...

Ahh right. Back to the drawing board.

Joh. said...

@rei: In the end, this is how I solved that problem:

Use an exception and "try...finally" or "use" and IDisposable for all clean-up code.

Joh. said...

In other words: tasks must always be interruptible when they yield. It's a bit harsh on the programmer that implements tasks, but for the kind of stuff that I'm using the modified Eventually workflow (UI, screens...), that's not a problem.