PROCESSES AND THREADS
2.4.6 Thread Scheduling
When several processes each have multiple threads, we have two levels of par-
allelism present: processes and threads. Scheduling in such systems differs sub-
stantially depending on whether user-level threads or kernel-level threads (or both)
Let us consider user-level threads first. Since the kernel is not aware of the ex-
istence of threads, it operates as it always does, picking a process, say,
, and giv-
control for its quantum. The thread scheduler inside
decides which thread
to run, say
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 select another process to run.
When the process
finally runs again, thread
will resume running.
continue to consume all of
’s time until it is finished. However, its antisocial be-
havior will not affect other processes.
They will get whatever the scheduler con-
siders their appropriate share, no matter what is going on inside process
Now consider the case that
’s threads have relatively little work to do per
CPU burst, for example, 5 msec of work within a 50-msec quantum. Consequently,
each one runs for a little while, then yields the CPU back to the thread scheduler.
This might lead to the sequence
, before the
kernel switches to process
This situation is illustrated in Fig. 2-44(a).
1. Kernel picks a process
1. Kernel picks a thread
A1, A2, A3, A1, A2, A3
A1, B1, A2, B2, A3, B3
A1, A2, A3, A1, A2, A3
A1, B1, A2, B2, A3, B3
Order in which
(a) Possible scheduling of user-level threads with a 50-msec proc-
ess quantum and threads that run 5 msec per CPU burst. (b) Possible scheduling
of kernel-level threads with the same characteristics as (a).
The scheduling algorithm used by the run-time system can be any of the ones
In practice, 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.
Since threads cooperate, this is usually not an issue.
Now consider the situation with kernel-level threads. Here the kernel picks a
particular 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 for-
cibly 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
, something not possible with these parameters and user-level
threads. This situation is partially depicted in Fig. 2-44(b).
A major difference between user-level threads and kernel-level threads is the
performance. Doing a thread switch with user-level threads takes a handful of ma-
chine instructions. With kernel-level threads it requires a full context switch,
changing the memory map and invalidating the cache, which is several orders of
On the other hand, with kernel-level threads, having a thread
block on I/O does not suspend the entire process as it does with user-level threads.
Since the kernel knows that switching from a thread in process
to a thread in
is more expensive than running a second thread in process
(due to hav-
ing to change the memory map and having the memory cache spoiled), it can take
this information into account when making a decision. For example, 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 factor is that user-level threads can employ an applica-
tion-specific thread scheduler. Consider, for example, the Web server of Fig. 2-8.
Suppose 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 strategy maximizes the amount of parallelism in
an environment where workers frequently block on disk I/O.
threads, the kernel would never know what each thread did (although they could be
assigned different priorities).
In general, however, application-specific thread
schedulers can tune an application better than the kernel can.
2.5 CLASSICAL IPC PROBLEMS
The operating systems literature is full of interesting problems that have been
widely discussed and analyzed using a variety of synchronization methods.
following sections we will examine three of the better-known problems.
2.5.1 The Dining Philosophers Problem
In 1965, Dijkstra posed and then solved a synchronization problem he called
dining philosophers problem
Since that time, everyone inventing yet another
synchronization primitive has felt obligated to demonstrate how wonderful the new