happily chew up every CPU cycle they could get. For example, consider two developers working
on different projects on the same machine. Time slicing is necessary for both of them to get a fair
share of the machine.
The other situation (the dependent case) occurs when the two processes depend directly upon each
other. One process needs another to perform some task before it can continue--a text editor
cannot do anything until the file system has delivered files to it to work on, and the file system has
nothing to do until the text editor requests some services from it. In such a case, time slicing is of
no use at all.
In Figure 5-1 we show two independent threads being time sliced and two dependent threads that
require some resource. In the second case, T1 is allowed to run as long as it wants to. It could run
forever if only it didn't need to exchange that resource with T2. A real machine is typically faced
with both situations all the time, along with the judgments of users and system administrators as to
the relative importance of the various processes.
We will not attempt to solve these problems here. Suffice it to say that the use of these techniques
results in less than perfect scheduling algorithms, but we have done fairly well with them over the
past 3040 years nonetheless.
We will now go into some of the gory details of how scheduling is done. The major point we
make is that most threaded programs are of the dependent case above, and scheduling is
accomplished mainly by dependence upon the program's need for synchronization.
Process Contention Scope
PCS scheduling is done by the threads library. The library chooses which unbound thread will be
put on which LWP. The scheduling of the LWP is (of course) still global and independent of the
local scheduling. Although this does mean that unbound threads are subject to a funny, two-tiered
scheduling architecture, in practice you can ignore the scheduling of the LWP and deal solely with
the local scheduling algorithm.
There are four ways to cause an active thread (say, T1) to context switch. Three of them require
that the programmer has written code. These methods are largely identical across all the libraries.
1. Synchronization. By far the most common means of being context switched (a wild
generalization) is for T1 to request a mutex lock and not get it. If the lock is already being
held by T2, then T1 will be placed on the sleep queue, awaiting the lock, thus allowing a
different thread to run.
2. Preemption. A running thread (T6) does something that causes a higher-priority thread
(T2) to become runnable. In that case, the lowest-priority active thread (T1) will be pre-
empted, and T2 will take its place on the LWP. The ways of causing this to happen
include releasing a lock, and changing the priority level of T2 upward or of T1 downward.
3. Yielding. If the programmer puts an explicit call to the yield call [Thread.yield()
sched_yield()] in the code that T1 is running, the scheduler will look to see if there is
another runnable thread (T2). If there is one, that thread will be scheduled.[6] If there isn't
one, T1 will continue to run.
[6]
There are no guarantees about the behavior of yield(). It is legal for it to do nothing!
4. Time slicing. If the vendor's PCS allows time slicing (like Digital UNIX, unlike Solaris),
T1 might simply have its time slice run out and T2 (at the same priority level) would then
receive a time slice.
Search WWH :
