\"\" \"\" \"\"
Go up to Implementation
Go forward to Garbage Collection
RISC-Linz logo

Thread Scheduling

By default, new threads are declared in a lazy state and pushed on a global stack. Initially, there is only one active thread, the program's main thread. A lazy thread in the global stack is executed on the following occasions only:  
Idling
An idle process finds no activated thread ready for execution. In this case, it takes a lazy thread from the global stack, allocates a thread space and switches control to the newly activated thread.
Waiting
An active thread needs the result of a thread which is still in lazy state. In this case, the active threads executes the code of the lazy thread itself.
Terminating
A thread is going to terminate but finds a lazy thread in the global stack. In this case, the thread continues execution with the code of the lazy thread.
Control is switched from one active thread to another only, if the time slice of a thread has ended or if the thread needs the result of another thread which has been already activated (by another process) but not yet terminated.

As an example, let us take a look at a program where the initial thread t0 creates two threads and waits for their results in turn. Each new thread creates two other threads resulting in the tree of threads of depth 4 depicted in the following figure:

 

Assume that there are three processes executing the program. A possible execution schedule is then described by the following table:

Time P0 P1 P2 Task Stack
0 t0 t2,t1
1 t1 t2 t6,t4,t5,t3
2 t6 t3 t5 t14,t12,t8,t13,t11,t7,t4
3 t13 t7 t11 t14,t12,t8,t4
4 t14 t8 t12 t4
5 t4 t10,t9
6 t10 t9
At time 0, process P0 executes thread t0 which creates threads t1 and t2. t1 is immediately taken by P1 for execution as well as t2 by P2 such that P0 becomes idle at time 1. However, t1 and t2 push t3,t5,t4,t6 on the thread stack such that at time 2 process P0 starts execution of t6. In the following time steps, all processes now create the corresponding thread subtrees and, by waiting for the respective results, execute the corresponding code. At time 5, process P0 is the quickest to grab t4 and is the only one to continue execution while the other processes idle. In the end P1 and P2 take the newly created t10 and t9.

All in all, the 15 lazy threads of the tree are executed by only six real threads of which only four threads are active at the same time (including the one thread which is blocked waiting for the result). Above figure illustrates this fact by a "bubble" for each active thread (with the different shadings representing the different processes).


Author: Wolfgang Schreiner
Last Modification: April 12, 1997