Thread Scheduling

GPL includes a multi-threaded preemptive priority-driven real-time operating system. User program threads can be swapped out or preempted by system threads any time the system clock ticks or whenever an I/O device interrupt occurs. Clock tick interrupts occur every 125 µsec (8KHz) and cause the system to swap out the current thread and begin execution of servo control threads and other high priority system threads. After the system threads complete, eligible user threads are executed during the remainder of the time before the next clock tick.

The standard thread scheduling algorithm for normal user threads is a round-robin scheme. In this approach, each user thread is permitted to execute for up to one millisecond before the next user thread that is ready to run is swapped in. Since the clock ticks at 8KHz, a user thread runs for up to eight 125 µsec ticks. If a user thread is active when the clock ticks, the thread's "remaining tick count" is decremented by 1, even if it did not run for the entire previous tick. When this count hits 0, the thread is moved to the end of the round-robin list. After all other user threads and system threads have had a chance to run, the original thread will move to the start of the round-robin list and will resume execution.

When a thread goes to sleep, is blocked, or is preempted, its remaining tick count is not decremented, so when it resumes execution, it gets the remainder of the 8 ticks that are left. When a thread is blocked or uses the Thread.Sleep method, all other threads continue to execute, using whatever time is available. When a user thread is unblocked or wakes from a sleep, it goes to the end of the round-robin list with whatever time it had left in its 1 msec interval. When a thread is preempted by a higher priority thread and resumed, it continues executing for whatever time it has left. It is not put at the end of the round-robin list.

If many user threads and system threads are busy, a given user thread may only get to run for 1 out of n milliseconds, where n is the number of busy threads. Nonetheless, the standard round-robin scheduling provides a good balance for most applications. For some time-critical user threads, this scheduling method may be undesirable.

An alternate scheduling algorithm, enabled by the Thread.Schedule method, allows critical user threads to run in a timely manner ahead of all other standard-priority threads. This algorithm is based on the POSIX sporadic scheduling policy. The algorithm schedules specified threads as follows:

At a fixed repetition rate, any specified high priority user thread has its priority raised above the standard thread priority.
After the high priority thread has run for a specified period of time, the thread's priority is returned to the standard level, and it is placed at the end of the round-robin queue of standard-level threads.
The high priority thread may run at standard priority if it gets to the front of the round-robin queue before the start of its next high priority period.

For more information on the specifics of the alternative scheduling algorithm, please see the dictionary page on the Thread.Schedule method.