Module No 2: Processes
Processes.
A process can be thought of as a program in execution. A process will need
certain resources—such as CPU time, memory, files, and I/O devices — to
accomplish its task. These resources are allocated to the process either when
it is created or while it is executing. A process is the unit of work in most
systems. Systems consist of a collection of processes: operating-system
processes execute system code, and user processes execute user code. All
these processes may execute concurrently.
Process Concept .
A process is more than the program code, which is sometimes known as the
text section. It also includes the current activity, as represented by the value
of the program counter and the contents of the processor’s registers. A
process generally also includes the process stack, which contains temporary
data (such as function parameters, return addresses, and local variables),
and a data section, which contains global variables. A process may also
include a heap, which is memory that is dynamically allocated during
process run time. The structure of a process in memory is shown in Figure
3.1.
Process State .
As a process executes, it changes state. The state of a process is defined in
part by the current activity of that process. A process may be in one of the
following states:
• New. The process is being created.
• Running. Instructions are being executed.
• Waiting. The process is waiting for some event to occur (such as an I/O
completion or reception of a signal).
• Ready. The process is waiting to be assigned to a processor.
• Terminated. The process has finished execution.
Process Control Block.
Each process is represented in the operating system by a process control
block (PCB)—also called a task control block. A PCB is shown in Figure 3.3.
It contains many pieces of information associated with a specific process,
including these:
•Process state. The state may be new, ready, running, waiting, halted, and
so on.
• Program counter. The counter indicates the address of the next instruction
to be executed for this process.
• CPU registers. The registers vary in number and type, depending on the
computer architecture. They include accumulators, index registers, stack
pointers, and general-purpose registers, plus any condition-code
information. Along with the program counter, this state information must
be saved when an interrupt occurs, to allow the process to be continued
correctly afterward (Figure 3.4).
• CPU-scheduling information. This information includes a process priority,
pointers to scheduling queues, and any other scheduling parameters.
• Memory-management information. This information may include such
items as the value of the base and limit registers and the page tables, or the
segment tables, depending on the memory system used by the operating
system.
• Accounting information. This information includes the amount of CPU
and real time used, time limits, account numbers, job or process numbers,
and so on.
• I/O status information. This information includes the list of I/O devices
allocated to the process, a list of open files, and so on.
Context Switch.
Interrupts cause the operating system to change a CPU from its current task
and to run a kernel routine. Such operations happen frequently on general-
purpose systems. When an interrupt occurs, the system needs to save the
current context of the process running on the CPU so that it can restore that
context when its processing is done, essentially suspending the process and
then resuming it. The context is represented in the PCB of the process. It
includes the value of the CPU registers, the process state ,and memory-
management information. Generically, we perform a state save of the
current state of the CPU, be it in kernel or user mode, and then a state
restores to resume operations.
Switching the CPU to another process requires performing a state save of the
current process and a state restore of a different process. This task is known
as a context switch. When a context switch occurs, the kernel saves the
context of the old process in its PCB and loads the saved context of the new
process scheduled to run. Context-switch time is pure overhead, because the
system does no useful work while switching. Switching speed varies from
machine to machine, depending on the memory speed, the number of
registers that must be copied, and the existence of special instructions (such
as a single instruction to load or store all registers). A typical speed is a few
milliseconds. Context-switch times are highly dependent on hardware
support. For instance, some processors (such as the Sun UltraSPARC)
provide multiple sets of registers. A context switch here simply requires
changing the pointer to the current register set. Of course, if there are more
active processes than there are register sets, the system resorts to copying
register data to and from memory, as before. Also, the more complex the
operating system, the greater the amount of work that must be done during
a context switch.
Module No 2: Threads
Thread.
A thread is a basic unit of CPU utilization; it comprises a thread ID, a
program counter, a register set, and a stack. It shares with other threads
belonging to the same process its code section, data section, and other
operating-system resources, such as open files and signals. A traditional (or
heavyweight) process has a single thread of control. If a process has multiple
threads of control, it can perform more than one task at a time. Figure 4.1
illustrates the difference between a traditional single-threaded process and
a multithreaded process.
Most software applications that run on modern computers are
multithreaded. An application typically is implemented as a separate
process with several threads of control. A web browser might have one
thread display images or text while another thread retrieves data from the
network, for example. A word processor may have a thread for displaying
graphics, another thread for responding to keystrokes from the user, and a
third thread for performing spelling and grammar checking in the
background. Applications can also be designed to leverage processing
capabilities on multicore systems. Such applications can perform several
CPU-intensive tasks in parallel across the multiple computing cores.
In certain situations, a single application may be required to perform several
similar tasks. For example, a web server accepts client requests for web
pages, images, sound, and so forth. A busy web server may have several
(perhaps thousands of) clients concurrently accessing it. If the web server
ran as a traditional single-threaded process, it would be able to service only
one client at a time, and a client might have to wait a very long time for its
request to be serviced.
One solution is to have the server run as a single process that accepts
requests. When the server receives a request, it creates a separate process to
service that request. In fact, this process-creation method was in common
use before threads became popular. Process creation is time consuming and
resource intensive, however. If the new process will perform the same tasks
as the existing process, why incur all that overhead? It is generally more
efficient to use one process that contains multiple threads. If the web-server
process is multithreaded, the server will create a separate thread that listens
for client requests. When a request is made, rather than creating another
process, the server creates a new thread to service the request and resume
listening for additional requests. This is illustrated in Figure 4.2
Benefits.
The benefits of multithreaded programming can be broken down into four
major categories:
1. Responsiveness. Multithreading an interactive application may allow a
program to continue running even if part of it is blocked or is performing a
lengthy operation, thereby increasing responsiveness to the user. This
quality is especially useful in designing user interfaces. For instance,
consider what happens when a user clicks a button that results in the
performance of a time-consuming operation. A single-threaded application
would be unresponsive to the user until the operation had completed. In
contrast, if the time-consuming operation is performed in a separate thread,
the application remains responsive to the user.
2. Resource sharing. Processes can only share resources through techniques
such as shared memory and message passing. Such techniques must be
explicitly arranged by the programmer. However, threads share the memory
and the resources of the process to which they belong by default. The benefit
of sharing code and data is that it allows an application to have several
different threads of activity within the same address space.
3. Economy. Allocating memory and resources for process creation is costly.
Because threads share the resources of the process to which they belong, it
is more economical to create and context-switch threads. Empirically
gauging the difference in overhead can be difficult, but in general it is
significantly more time consuming to create and manage processes than
threads. In Solaris, for example, creating a process is about thirty times
slower than is creating a thread, and context switching is about five times
slower.
4. Scalability. The benefits of multithreading can be even greater in a
multiprocessor architecture, where threads may be running in parallel on
different processing cores. A single-threaded process can run on only one
processor, regardless how many are available.
Multicore Programming.
Earlier in the history of computer design, in response to the need for more
computing performance, single-CPU systems evolved into multi-CPU
systems. A more recent, similar trend in system design is to place multiple
computing cores on a single chip. Each core appears as a separate processor
to the operating system. Whether the cores appear across CPU chips or
within CPU chips, we call these systems multicore or multiprocessor
systems. Multithreaded programming provides a mechanism for more
efficient use of these multiple computing cores and improved concurrency.
Consider an application with four threads. On a system with a single
computing core, concurrency merely means that the execution of the threads
will be interleaved over time (Figure 4.3), because the processing core is
capable of executing only one thread at a time. On a system with multiple
cores, however, concurrency means that the threads can run in parallel,
because the system can assign a separate thread to each core (Figure 4.4).
A system is parallel if it can perform more than one task simultaneously. In
contrast, a concurrent system supports more than one task by allowing all
the tasks to make progress. Thus, it is possible to have concurrency without
parallelism. Before the advent of SMP and multicore architectures, most
computer systems had only a single processor. CPU schedulers were
designed to provide the illusion of parallelism by rapidly switching between
processes in the system, thereby allowing each process to make progress.
Such processes were running concurrently, but not in parallel. As systems
have grown from tens of threads to thousands of threads, CPU designers
have improved system performance by adding hardware to improve thread
performance.
Programming Challenges.
In general, five areas present challenges in programming for multicore
systems:
1. Identifying tasks. This involves examining applications to find areas that
can be divided into separate, concurrent tasks. Ideally, tasks are independent
of one another and thus can run in parallel on individual cores.
2. Balance. While identifying tasks that can run in parallel, programmers
must also ensure that the tasks perform equal work of equal value. In some
instances, a certain task may not contribute as much value to the overall
process as other tasks. Using a separate execution core to run that task may
not be worth the cost.
3. Data splitting. Just as applications are divided into separate tasks, the data
accessed and manipulated by the tasks must be divided to run on separate
cores.
4. Data dependency. The data accessed by the tasks must be examined for
dependencies between two or more tasks. When one task depends on data
from another, programmers must ensure that the execution of the tasks is
synchronized to accommodate the data dependency.
5. Testing and debugging. When a program is running in parallel on
multiple cores, many different execution paths are possible. Testing and
debugging such concurrent programs are inherently more difficult than
testing and debugging single-threaded applications.
Types of Parallelism.
Data parallelism focuses on distributing subsets of the same data across
multiple computing cores and performing the same operation on each core.
Consider, for example, summing the contents of an array of size N. On a
single-core system, one thread would simply sum the elements [0] . . . [N −
1]. On a dual-core system, however, thread A, running on core 0, could sum
the elements [0] . . . [N/2 − 1] while thread B, running on core 1, could sum
the elements [N/2] . . . [N − 1]. The two threads would be running in parallel
on separate computing cores.
Task parallelism involves distributing not data but tasks (threads) across
multiple computing cores. Each thread is performing a unique operation.
Different threads may be operating on the same data, or they may be
operating on different data. An example of task parallelism might involve
two threads, each performing a unique statistical operation on the array of
elements. The threads again are operating in parallel on separate computing
cores, but each is performing a unique operation.
Multithreading Model.
A relationship must exist between user threads and kernel threads. We look
at three common ways of establishing such a relationship: the many-to-one
model, the one-to-one model, and the many-to-many model.
Many-to-One Model
The many-to-one model (Figure 4.5) maps many user-level threads to one
kernel thread. Thread management is done by the thread library in user
space, so it is efficient. However, the entire process will block if a thread
makes a blocking system call. Also, because only one thread can access the
kernel at a time, multiple threads are unable to run in parallel on multicore
systems. Green threads—a thread library available for Solaris systems and
adopted in early versions of Java—used the many-to-one model. However,
very few systems continue to use the model because of its inability to take
advantage of multiple processing cores.
One-to-One Model
The one-to-one model (Figure 4.6) maps each user thread to a kernel thread.
It provides more concurrency than the many-to-one model by allowing
another thread to run when a thread makes a blocking system call. It also
allows multiple threads to run in parallel on multiprocessors. The only
drawback to this model is that creating a user thread requires creating the
corresponding kernel thread. Because the overhead of creating kernel
threads can burden the performance of an application, most
implementations of this model restrict the number of threads supported by
the system. Linux, along with the family of Windows operating systems,
implement the one-to-one model.
Many-to-Many Model
The many-to-many model (Figure 4.7) multiplexes many user-level threads
to a smaller or equal number of kernel threads. The number of kernel threads
may be specific to either a particular application or a particular machine (an
application may be allocated more kernel threads on a multiprocessor than
on a single processor).
Let’s consider the effect of this design on concurrency. Whereas the many-
to-one model allows the developer to create as many user threads as she
wishes, it does not result in true concurrency, because the kernel can
schedule only one thread at a time. The one-to-one model allows greater
concurrency, but the developer has to be careful not to create too many
threads within an application (and in some instances may be limited in the
number of threads she can create). The many-to-many model suffers from
neither of these shortcomings: developers can create as many user threads
as necessary, and the corresponding kernel threads can run in parallel on a
multiprocessor. Also, when a thread performs a blocking system call, the
kernel can schedule another thread for execution.
One variation on the many-to-many model still multiplexes many user-level
threads to a smaller or equal number of kernel threads but also allows a user-
level thread to be bound to a kernel thread. This variation is sometimes
referred to as the two-level model (Figure 4.8).