Thread scheduling

CM Modula-3 has a flexible scheduling algorithm. Here is a rough explanation of its behaviour.

All threads are kept in a circular list. This list is modified only when new threads are created or when they exit; that is, the relative order of threads in this list is never modified.

When the scheduler comes into action, the list of threads is scanned starting with the thread following the one currently running, until a thread that can execute is found:

• if it was preempted by the scheduler or called Scheduler.Yield, it can execute
• if it is waiting for a condition or a mutex that is now free, it can execute
• if it has blocked because of a call to Thread.Pause (or a similar procedure), it can execute iff the timeout has expired
• if it has blocked because of a call to SchedulerPosix.IOWait, (or a similar procedure), it can execute iff the timeout is now expired or a polling select(2) returns a non-zero value.

If such a thread is found, it becomes active.

If no thread can execute, and there are no threads blocked in a Thread.Pause or a SchedulerPosix.IOWait, a deadlock situation is detected and reported. Otherwise, a combination of the file descriptors sets (OR of all the file descriptors sets) and timeouts (MIN of all the timeouts) is formed, select(2) is called with those arguments and the whole process of searching for an executable thread is redone. This ensures that the Unix process does not consume CPU resources while waiting.

The scheduler is activated when the running thread tries to acquire a mutex which is locked, waits for a condition, calls Thread.Pause (or a similar procedure) with a future time, calls SchedulerPosix.IOWait, (or a similar procedure) with a non-zero valued timeout and no files are ready at the time of the call, or the time allocated to the thread has expired (preemption).

Preemption is implemented using the Unix virtual interval timer. CM Modula-3 does not use the real time interval timer nor the profiling interval timer for thread scheduling; these are available to the program.

Because of the preemption implementation, Unix kernel calls will block the process (i.e. the Unix process sleeps even though some threads could run). However, Thread.Pause and SchedulerPosix.IOWait provide functional equivalents of sigpause(2) and select(2) that do not cause the process to block.