Thread Scheduling

Thread Scheduling

When many processes each have multiple threads, we have two levels of parallelism present: processes and threads. Scheduling in such systems differs considerably depending on whether user-level threads or kernel-level threads (or both) are supported.

Let us examine user-level threads first. Since the kernel is not aware of the existence of threads, it functions as it always does, picking a process, say, A, and giving A control for its quantum. The thread scheduler inside A determines which thread to run, say A1. Since there are no clock interrupts to multiprogram threads, this thread may continue running as long as it wants to. If it uses up the process entire quantum, the kernel will choose another process to run.

When the process A finally runs again, thread A1 will resume running. It will continue to consume all of A's time until it comes to an end. On the other hand its antisocial behavior will not affect other processes. They will get whatever the scheduler considers their appropriate share, no matter what is going on inside process A.

Now look at the case that A's threads have comparatively little work to do per CPU burst, for instance, 5 msec of work within a 50-msec  quantum. Therefore, each one runs for a little while, then yields the CPU back to the thread scheduler. This might lead to the sequence  A1, A2, A3, A1, A2, A3, A1, A2, A3, A1, before the kernel switches to process B. This situation is demonstrated in Figure 1-(a).

The scheduling algorithm used by the run-time system can be any of the ones explained above. In reality, round-robin scheduling and priority scheduling are most common. The only constraint is the absence of a clock to interrupt a thread that has run too long.

Now look at the situation with kernel-level threads. Here the kernel picks a specific thread to run. It does not have to take into account which process the thread belongs to, but it can if it wants to. The thread is given a quantum and is forceably suspended if it exceeds the quantum. With a 50-msec quantum but threads that block after 5 msec, the thread order for some period of 30 msec might be A1, B1, A2, B2, A3, B3, something not possible with these parameters and user-level threads. This situation is partially shown in Figure 1-(b).

A main difference between user-level threads and kernel-level threads is the performance. Doing a thread switch with user-level threads takes a handful of machine instructions. With kernel-level threads it requires a full context switch, changing the memory map and invalidating the cache, which is several orders of magnitude slower. However, with kernel-level threads, having a thread block on I/O does not suspend the complete process as it does with user-level threads.

Possible scheduling of user-level threads

Since the kernel knows that switching from a thread in process A to a thread in process B is more expensive than running a second thread in process A (due to having to change the memory map and having the memory cache spoiled), it can consider this information when making a decision. For instance, given two threads that are otherwise equally important, with one of them belonging to the same process as a thread that just blocked and one belonging to a different process, preference could be given to the former.

Another important thing is that user-level threads can employ an application-specific thread scheduler. Look at, for instance, the Web server of "THREADS" Figure 2. Assume that a worker thread has just blocked and the dispatcher thread and two worker threads are ready. Who should run next? The run-time system, knowing what all the threads do, can easily pick the dispatcher to run next, so that it can start another worker running. This approach maximizes the amount of parallelism in an environment where workers often block on disk I/O. With kernel-level threads, the kernel would never know what each thread did (although they could be allocated different priorities). Generally, however, application-specific thread schedulers can tune an application better than the kernel can.


thread scheduler, scheduling algorithm, memory map, kernel, process