address spaces, but they do not have to (often they merely overlap). It is impor-
tant to remember that only one thread may be executing on a CPU at any given
time, which is basically the reason kernels have CPU schedulers. An example of
multiple threads within a process can be found in most web browsers. Usually
at least one thread exists to handle user interface events (like stopping a page
load), one thread exists to handle network transactions, and one thread exists
to render web pages.
3.3 Scheduling
Multitasking kernels (like Linux) allow more than one process to exist at any
given time, and furthermore each process is allowed to run as if it were the
only process on the system. Processes do not need to be aware of any other
processes unless they are explicitly designed to be. This makes programs easier
to develop, maintain, and port [1]. Though each CPU in a system can execute
only one thread within a process at a time, many threads from many processes
appear to be executing at the same time. This is because threads are scheduled
to run for very short periods of time and then other threads are given a chance
to run. A kernel’s scheduler enforces a thread scheduling policy, including when,
for how long, and in some cases where (on Symmetric Multiprocessing (SMP)
systems) threads can execute. Normally the scheduler runs in its own thread,
which is woken up by a timer interrupt. Otherwise it is invoked via a system
call or another kernel thread that wishes to yield the CPU. A thread will be
allowed to execute for a certain amount of time, then a context switch to the
scheduler thread will occur, followed by another context switch to a thread of
the scheduler’s choice. This cycle continues, and in this way a certain policy for
CPU usage is carried out.
3.4 CPU and I/O-bound Threads
Threads of execution tend to be either CPU-bound or I/O-bound (Input/Output
b ound). That is, some threads spend a lot of time using the CPU to do compu-
tations, and others spend a lot of time waiting for relatively slow I/O operations
to complete. For example - a thread that is sequencing DNA will b e CPU bound.
A thread taking input for a word processing program will be I/O-bound as it
sp ends most of its time waiting for a human to type. It is not always clear
whether a thread should be considered CPU or I/O bound. The best a sched-
uler can do is guess, if it cares at all. Many schedulers do care about whether
or not a thread should be considered CPU or I/O bound, and thus techniques
for classifying threads as one or the other are important parts of schedulers.
Schedulers tend to give I/O-bound threads priority access to CPUs. Pro-
grams that accept human input tend to be I/O-bound - even the fastest typist
has a considerable amount of time between each keystroke during which the
program he or she is interacting with is simply waiting. It is important to give
programs that interact with humans priority since a lack of speed and respon-
siveness is more likely to be perceived when a human is expecting an immediate
8