Cheap Threads: Internals of the Scheduler

Internals of the Scheduler

The central issue of any scheduling algorithm is: who goes next?

The simplest approach is a round robin, scheduling successive threads in a fixed cycle. Every thread runs as often as every other thread. Cheap Threads can implement a round robin, but this simple scheme may not be good enough. Some threads may need to run frequently, while others may run only occasionally.

Like most other scheduling schemes, Cheap Threads addresses this problem by letting you assign different priorities to different threads. High priority threads run more frequently than low priority threads.

Priorities are represented by integers ranging from zero (the highest priority) to CT_PRIORITY_MAX (the lowest priority, defined as 15 in ct.h). This convention is confusing to discuss because the higher numbers represent lower priorities, and vice versa. There is, however, a reason for this convention. If you ever change the number of priority levels, the highest priority will still be represented by zero. Code written for the earlier version will still work as intended, or very nearly so.

In the following discussion, the term "priority level" refers specifically to the number representing a priority. The term "priority", without the word "level", retains its ordinary meaning.

Run Queues

The priority of a thread is defined when the thread is created, via the ct_create_thread() function. There is no function to permanently change the priority level of an existing thread. If the need arises, however, it would be easy to implement such a function.

For each priority level, the scheduler maintains a series of queues of runnable threads, one queue for each priority level (it stores sleeping threads separately). When it needs to pick a thread to run, the scheduler looks for a non-empty queue, starting with level zero. If it finds one, it removes the thread from the head of that queue and runs it. If all the queues are empty, the scheduler terminates.

When the thread returns control, the scheduler usually appends it to the tail of the queue for that thread's priority level. There are several exceptions:

The thread has called ct_wait(), and its message queue is empty. The scheduler adds the thread to a list of sleeping threads rather than to a run queue.

The thread has called ct_exit() to signal that it should expire. The scheduler destroys the thread.

The thread's input queue is not empty, and the thread has not called ct_exit(), nor reported an error. The scheduler re-enqueues it for execution at the highest priority.

The thread has called ct_penalize(), volunteering to be given a lower priority temporarily. The scheduler appends it to the tail of a queue at a higher priority level than the queue where it would normally belong. This reassignment of priority only occurs once. After the next run of that thread, its normal priority level will be in effect, unless the thread calls ct_penalize() again.

Risk of Starvation

As described above, the schedule always picks one of the highest-priority threads to run next. The question naturally arises: how does a low-priority thread ever run?

Every priority-based scheduler faces the same problem. Without some kind of precaution, a low-priority task faces the possibility of starvation. It may never get any CPU time because higher-priority tasks keep jumping in front of it.

The general solution is to adjust the priorities dynamically. If a task waits long enough, you increase its priority a bit. Even a low-priority task can eventually attain a high enough priority that it can claim some CPU time.

Scrunching the Queues

Periodically, the scheduler effectively raises the priority of every thread in the run queues -- except of course for the threads in queue zero, which already have the highest possible priority.

It does so by moving the threads to different queues. First it transfers queue 1 to the end of queue zero. Then it transfers queue 2 to queue1, queue 3 to queue 2, and so forth, leaving the last queue empty. This procedure is called "scrunching".

At the end of this operation, the threads which had already been in queue zero are still there. All other threads are now at priority levels one less than what they were before.

This rearrangement changes the dynamic priorities, but not the static priorities. That is, a thread defined with a priority level of 4 may now be sitting in queue 3, but after its next run it will go back to queue 4.

Avoiding Starvation

By periodically scrunching the queues, we ensure that no thread will ever starve. The logic goes like this:

If a runnable thread goes for very long without running, it will eventually move to the next higher priority level.

If it still doesn't run, it will eventually move to the queue for priority level zero.

Threads are added only to the end of any queue. No thread ever jumps ahead of another thread within the same queue.

As long as the scheduler keeps running threads, a thread in queue zero will eventually reach the head of the queue, and the scheduler will run it.

Conclusion: as long as the scheduler keeps running threads, a runnable thread absolutely will run eventually, no matter how low its priority. The only exception is if the scheduler stops running threads, because some thread calls ct_halt(), reports an error, or gets caught in an endless loop.

How Often to Scrunch

By default, the scheduler scrunches the queues every time it runs eight threads. This number is defined in ct.h as CT_DEFAULT_COUNTDOWN.

This particular choice of frequency is completely arbitrary, and may not be appropriate for your application. You can change it by calling the ct_set_countdown() function to tell the scheduler how many threads to run before scrunching the queues.

If you pass it a large number, then low priority threads will almost never run. If you pass it a very small number, then the effect of priorities will be weaker, and the scheduler will behave more like a round robin.

At the default setting, the queue-scrunching consumes about a sixth of the overhead incurred by the scheduler. Scrunching more or less frequently will increase or decrease the overhead accordingly.

Recommendations

For a strict round robin, assign a zero priority level to all threads. Don't put threads to sleep, because awakening them will put them back into the cycle in a different position. Use ct_set_countdown() to reduce the frequency of scrunching, thereby reducing the overhead.

For a modified round robin, assign each thread the same priority, preferably zero or one, and let your threads sleep and awaken as appropriate. The result will be a round robin for the runnable threads, with occasional rearrangements as threads sleep and awaken.

If you do use multiple priority levels, you probably won't need to use more than three or four of them. Typically they should all be relatively high priorities (i.e. low level numbers). Don't assign a low priority unless you want that thread to run extremely infrequently.

Home