Chapter 3

Question 1

The Process

Answer 1

Informally, as mentioned earlier, a process is a program in execution. The status
of the current activity of a process is represented by the value of the program
counter and the contents of the processor’s registers

Question 2

Activation record

Answer 2

Notice that the sizes of the text and data sections are fixed, as their sizes do
not change during program run time. However, the stack and heap sections can
shrink and grow dynamically during program execution. Each time a function
is called, an activation record containing function parameters, local variables,
and the return address is pushed onto the stack; when control is returned from
the function, the activation record is popped from the stack. Similarly, the heap
will grow as memory is dynamically allocated, and will shrink when memory
is returned to the system. Although the stack and heap sections grow toward
one another, the operating system must ensure they do not overlap one another.

Question 3

program vs process

Answer 3

We emphasize that a program by itself is not a process. A program is a
passive entity, such as a file containing a list of instructions stored on disk
(often called an executable fil ). In contrast, a process is an active entity,
with a program counter specifying the next instruction to execute and a set
of associated resources. A program becomes a process when an executable file
is loaded into memory. Two common techniques for loading executable files
are double-clicking an icon representing the executable file and entering the
name of the executable file on the command line (as in prog.exe or a.out).
Although two processes may be associated with the same program, they
are nevertheless considered two separate execution sequences. For instance,
several users may be running different copies of the mail program, or the same
user may invoke many copies of the web browser program. Each of these is a
separate process; and although the text sections are equivalent, the data, heap,
and stack sections vary. It is also common to have a process that spawns many
processes as it runs. We discuss such matters in Section 3.4.
Note that a process can itself be an execution environment for other code.
The Java programming environment provides a good example. In most circumstances, an executable Java program is executed within the Java virtual
machine (JVM). The JVM executes as a process that interprets the loaded Java
code and takes actions (via native machine instructions) on behalf of that code.
For example, to run the compiled Java program Program.class, we would
enter
java Program
The command java runs the JVM as an ordinary process, which in turns
executes the Java program Program in the virtual machine. The concept is the
same as simulation, except that the code, instead of being written for a different
instruction set, is written in the Java language.

Question 4

program vs process

Answer 4

We emphasize that a program by itself is not a process. A program is a
passive entity, such as a file containing a list of instructions stored on disk
(often called an executable fil ). In contrast, a process is an active entity,
with a program counter specifying the next instruction to execute and a set
of associated resources. A program becomes a process when an executable file
is loaded into memory. Two common techniques for loading executable files
are double-clicking an icon representing the executable file and entering the
name of the executable file on the command line (as in prog.exe or a.out).
Although two processes may be associated with the same program, they
are nevertheless considered two separate execution sequences. For instance,
several users may be running different copies of the mail program, or the same
user may invoke many copies of the web browser program. Each of these is a
separate process; and although the text sections are equivalent, the data, heap,
and stack sections vary. It is also common to have a process that spawns many
processes as it runs. We discuss such matters in Section 3.4.
Note that a process can itself be an execution environment for other code.
The Java programming environment provides a good example. In most circumstances, an executable Java program is executed within the Java virtual
machine (JVM). The JVM executes as a process that interprets the loaded Java
code and takes actions (via native machine instructions) on behalf of that code.
For example, to run the compiled Java program Program.class, we would
enter
java Program
The command java runs the JVM as an ordinary process, which in turns
executes the Java program Program in the virtual machine. The concept is the
same as simulation, except that the code, instead of being written for a different
instruction set, is written in the Java language.

Question 5

types of processes

Answer 5

*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.

Question 6

Process Control Block

Answer 6

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 when it is rescheduled to run.
* CPU-scheduling information. This information includes a process priority, pointers to scheduling queues, and any other scheduling parameters.
(Chapter 5 describes process scheduling.)
* 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 (Chapter 9).
* 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.
In brief, the PCB simply serves as the repository for all the data needed to start,
or restart, a process, along with some accounting data.

Question 7

Threads

Answer 7

The process model discussed so far has implied that a process is a program that
performs a single thread of execution. For example, when a process is running
a word-processor program, a single thread of instructions is being executed.
This single thread of control allows the process to perform only one task at a
time. Thus, the user cannot simultaneously type in characters and run the spell
checker. Most modern operating systems have extended the process concept
to allow a process to have multiple threads of execution and thus to perform
more than one task at a time. This feature is especially beneficial on multicore
systems, where multiple threads can run in parallel. A multithreaded word
processor could, for example, assign one thread to manage user input while
another thread runs the spell checker. On systems that support threads, the PCB
is expanded to include information for each thread. Other changes throughout
the system are also needed to support threads. Chapter 4 explores threads in
detail.

Question 8

objective of multiprogramming

Answer 8

The objective of multiprogramming is to have some process running at all times
so as to maximize CPU utilization. The objective of time sharing is to switch
a CPU core among processes so frequently that users can interact with each
program while it is running. To meet these objectives, the process scheduler
selects an available process (possibly from a set of several available processes)
for program execution on a core. Each CPU core can run one process at a time. For a system with a single CPU core, there will never be more than one process
running at a time, whereas a multicore system can run multiple processes at
one time. If there are more processes than cores, excess processes will have to wait until a core is free and can be rescheduled. The number of processes
currently in memory is known as the degree of multiprogramming.
Balancing the objectives of multiprogramming and time sharing also
requires taking the general behavior of a process into account. In general, most
processes can be described as either I/O bound or CPU bound. An I/O-bound
process is one that spends more of its time doing I/O than it spends doing
computations. A CPU-bound process, in contrast, generates I/O requests
infrequently, using more of its time doing computations.

Question 9

PROCESS REPRESENTATION IN LINUX

Answer 9

The process control block in the Linux operating system is represented by the C structure task struct, which is found in the
<include/linux/sched.h> include file in the kernel source-code
directory. This structure contains all the necessary information for
representing a process, including the state of the process, scheduling
and memory-management information, list of open files, and pointers to the
process’s parent and a list of its children and siblings. (A process’s parent
is the process that created it; its children are any processes that it creates.
Its siblings are children with the same parent process.) Some of these fields
include:
long state; /* state of the process /
struct sched entity se; / scheduling information */
struct task struct parent; / this process’s parent /
struct list head children; / this process’s children */
struct files struct files; / list of open files */
struct mm struct mm; / address space */
For example, the state of a process is represented by the field long state
in this structure. Within the Linux kernel, all active processes are represented
using a doubly linked list of task struct. The kernel maintains a pointer –
current– to the process currently executing on the system

Question 10

Scheduling Queues

Answer 10

As processes enter the system, they are put into a ready queue, where they are
ready and waiting to execute on a CPU’s core This queue is generally stored as
a linked list; a ready-queue header contains pointers to the first PCB in the list,
and each PCB includes a pointer field that points to the next PCB in the ready
queue.
The system also includes other queues. When a process is allocated a CPU
core, it executes for a while and eventually terminates, is interrupted, or waits
for the occurrence of a particular event, such as the completion of an I/O
request. Suppose the process makes an I/O request to a device such as a disk.
Since devices run significantly slower than processors, the process will have
to wait for the I/O to become available. Processes that are waiting for a certain
event to occur — such as completion of I/O — are placed in a wait queue
(Figure 3.4).
A common representation of process scheduling is a queueing diagram,
such as that in Figure 3.5. Two types of queues are present: the ready queue and
a set of wait queues. The circles represent the resources that serve the queues,
and the arrows indicate the flow of processes in the system.
A new process is initially put in the ready queue. It waits there until it is
selected for execution, or dispatched. Once the process is allocated a CPU core
and is executing, one of several events could occur:
* The process could issue an I/O request and then be placed in an I/O wait
queue.
* The process could create a new child process and then be placed in a wait
queue while it awaits the child’s termination.
* The process could be removed forcibly from the core, as a result of an
interrupt or having its time slice expire, and be put back in the ready queue.
In the first two cases, the process eventually switches from the waiting state
to the ready state and is then put back in the ready queue. A process continues
this cycle until it terminates, at which time it is removed from all queues and
has its PCB and resources deallocated

Question 11

CPU Scheduling

Answer 11

A process migrates among the ready queue and various wait queues throughout its lifetime. The role of the CPU scheduler is to select from among the
processes that are in the ready queue and allocate a CPU core to one of them. The
CPU scheduler must select a new process for the CPU frequently. An I/O-bound
process may execute for only a few milliseconds before waiting for an I/O
request. Although a CPU-bound process will require a CPU core for longer durations, the scheduler is unlikely to grant the core to a process for an extended
period. Instead, it is likely designed to forcibly remove the CPU from a process
and schedule another process to run. Therefore, the CPU scheduler executes at
least once every 100 milliseconds, although typically much more frequently.
Some operating systems have an intermediate form of scheduling, known
as swapping, whose key idea is that sometimes it can be advantageous to
remove a process from memory (and from active contention for the CPU)
and thus reduce the degree of multiprogramming. Later, the process can be
reintroduced into memory, and its execution can be continued where it left off.
This scheme is known as swapping because a process can be “swapped out” from memory to disk, where its current status is saved, and later “swapped in”
from disk back to memory, where its status is restored. Swapping is typically
only necessary when memory has been overcommitted and must be freed up

Question 12

Context Switch

Answer 12

As mentioned in Section 1.2.1, interrupts cause the operating system to change
a CPU core 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
core 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 (see Figure 3.2), and memory-management information. Generically, we
perform a state save of the current state of the CPU core, be it in kernel or user
mode, and then a state restore to resume operations.
Switching the CPU core 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 and is illustrated in Figure 3.6. 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 several microseconds.
Context-switch times are highly dependent on hardware support. For
instance, some processors 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. As we will see in Chapter 9, advanced memory-management
techniques may require that extra data be switched with each context. For
instance, the address space of the current process must be preserved as the
space of the next task is prepared for use. How the address space is preserved,
and what amount of work is needed to preserve it, depend on the memory management method of the operating system.

Question 13

MULTITASKING IN MOBILE SYSTEMS

Answer 13

Because of the constraints imposed on mobile devices, early versions of iOS
did not provide user-application multitasking; only one application ran in
the foreground while all other user applications were suspended. Operatingsystem tasks were multitasked because they were written by Apple and well
behaved. However, beginning with iOS 4, Apple provided a limited form of
multitasking for user applications, thus allowing a single foreground application to run concurrently with multiple background applications. (On a
mobile device, the foreground application is the application currently open
and appearing on the display. The background application remains in memory, but does not occupy the display screen.) The iOS 4 programming API
provided support for multitasking, thus allowing a process to run in the background without being suspended. However, it was limited and only available
for a few application types. As hardware for mobile devices began to offer
larger memory capacities, multiple processing cores, and greater battery life,
subsequent versions of iOS began to support richer functionality for multitasking with fewer restrictions. For example, the larger screen on iPad tablets
allowed running two foreground apps at the same time, a technique known
as split-screen.
Since its origins, Android has supported multitasking and does not place
constraints on the types of applications that can run in the background. If
an application requires processing while in the background, the application
must use a service, a separate application component that runs on behalf
of the background process. Consider a streaming audio application: if the
application moves to the background, the service continues to send audio
data to the audio device driver on behalf of the background application. In
fact, the service will continue to run even if the background application is
suspended. Services do not have a user interface and have a small memory
footprint, thus providing an efficient technique for multitasking in a mobile
environment.

Question 14

Process Creation

Answer 14

During the course of execution, a process may create several new processes. As
mentioned earlier, the creating process is called a parent process, and the new
processes are called the children of that process. Each of these new processes
may in turn create other processes, forming a tree of processes.
Most operating systems (including UNIX, Linux, and Windows) identify
processes according to a unique process identifie (or pid), which is typically
an integer number. The pid provides a unique value for each process in the
system, and it can be used as an index to access various attributes of a process
within the kernel.
Figure 3.7 illustrates a typical process tree for the Linux operating system,
showing the name of each process and its pid. (We use the term process rather
loosely in this situation, as Linux prefers the term task instead.) The systemd
process (which always has a pid of 1) serves as the root parent process for all
user processes, and is the first user process created when the system boots.
Once the system has booted, the systemd process creates processes which
provide additional services such as a web or print server, an ssh server, and
the like. In Figure 3.7, we see two children of systemd—logind and sshd.
The logind process is responsible for managing clients that directly log onto
the system. In this example, a client has logged on and is using the bash shell,
which has been assigned pid 8416. Using the bash command-line interface,
this user has created the process ps as well as the vim editor. The sshd process
is responsible for managing clients that connect to the system by using ssh
(which is short for secure shell). On UNIX and Linux systems, we can obtain a listing of processes by using
the ps command. For example, the command
ps -el
will list complete information for all processes currently active in the system.
A process tree similar to the one shown in Figure 3.7 can be constructed by
recursively tracing parent processes all the way to the systemd process. (In
addition, Linux systems provide the pstree command, which displays a tree
of all processes in the system.)
In general, when a process creates a child process, that child process will
need certain resources (CPU time, memory, files, I/O devices) to accomplish
its task. A child process may be able to obtain its resources directly from
the operating system, or it may be constrained to a subset of the resources
of the parent process. The parent may have to partition its resources among
its children, or it may be able to share some resources (such as memory or
files) among several of its children. Restricting a child process to a subset of
the parent’s resources prevents any process from overloading the system by
creating too many child processes.
In addition to supplying various physical and logical resources, the parent
process may pass along initialization data (input) to the child process. For
example, consider a process whose function is to display the contents of a file—
say, hw1.c—on the screen of a terminal. When the process is created, it will get,
as an input from its parent process, the name of the file hw1.c. Using that file
name, it will open the file and write the contents out. It may also get the name
of the output device. Alternatively, some operating systems pass resources to
child processes. On such a system, the new process may get two open files,
hw1.c and the terminal device, and may simply transfer the datum between
the two

Question 15

THE init AND systemd PROCESSES

Answer 15

Traditional UNIX systems identify the process init as the root of all child
processes. init (also known as System V init) is assigned a pid of 1, and is
the first process created when the system is booted. On a process tree similar
to what is shown in Figure 3.7, init is at the root.
Linux systems initially adopted the System V init approach, but recent
distributions have replaced it with systemd. As described in Section 3.3.1,
systemd serves as the system’s initial process, much the same as System V
init; however it is much more flexible, and can provide more services, than
init.

Question 16

When a process creates a new process, two possibilities for execution exist:

Answer 16

1. The parent continues to execute concurrently with its children.
2. The parent waits until some or all of its children have terminated.
   There are also two address-space possibilities for the new process:
3. The child process is a duplicate of the parent process (it has the same
   program and data as the parent).
4. The child process has a new program loaded into it.

Question 17

UNIX calls

Answer 17

include <sys/types.h>

#include <stdio.h>
#include <unistd.h>
int main()
{
pid t pid;
/* fork a child process */
pid = fork();
if (pid < 0) { /* error occurred */
fprintf(stderr, "Fork Failed");
return 1;
}
else if (pid == 0) { /* child process */
execlp("/bin/ls","ls",NULL);
}
else { /* parent process */
/* parent will wait for the child to complete */
wait(NULL);
printf("Child Complete");
}
return 0;
}</unistd.h></stdio.h>

To illustrate these differences, let’s first consider the UNIX operating system. In
UNIX, as we’ve seen, each process is identified by its process identifier, which
is a unique integer. A new process is created by the fork() system call. The
new process consists of a copy of the address space of the original process.
This mechanism allows the parent process to communicate easily with its child
process. Both processes (the parent and the child) continue execution at the
instruction after the fork(), with one difference: the return code for the fork()
is zero for the new (child) process, whereas the (nonzero) process identifier of
the child is returned to the parent.
After a fork() system call, one of the two processes typically uses the
exec() system call to replace the process’s memory space with a new program. The exec() system call loads a binary file into memory (destroying the
memory image of the program containing the exec() system call) and starts its execution. In this manner, the two processes are able to communicate and
then go their separate ways. The parent can then create more children; or, if it
has nothing else to do while the child runs, it can issue a wait() system call
to move itself off the ready queue until the termination of the child. Because
the call to exec() overlays the process’s address space with a new program,
exec() does not return control unless an error occurs.
The C program shown in Figure 3.8 illustrates the UNIX system calls previously described. We now have two different processes running copies of the
same program. The only difference is that the value of the variable pid for the
child process is zero, while that for the parent is an integer value greater than
zero (in fact, it is the actual pid of the child process). The child process inherits
privileges and scheduling attributes from the parent, as well certain resources,
such as open files. The child process then overlays its address space with the
UNIX command /bin/ls (used to get a directory listing) using the execlp()
system call (execlp() is a version of the exec() system call). The parent waits
for the child process to complete with the wait() system call. When the child
process completes (by either implicitly or explicitly invoking exit()), the parent process resumes from the call to wait(), where it completes using the
exit() system call. This is also illustrated in Figure 3.9.
Of course, there is nothing to prevent the child from not invoking exec()
and instead continuing to execute as a copy of the parent process. In this
scenario, the parent and child are concurrent processes running the same code
instructions. Because the child is a copy of the parent, each process has its own
copy of any data.
As an alternative example, we next consider process creation in Windows.
Processes are created in the Windows API using the CreateProcess() function, which is similar to fork() in that a parent creates a new child process.
However, whereas fork() has the child process inheriting the address space
of its parent, CreateProcess() requires loading a specified program into the
address space of the child process at process creation. Furthermore, whereas
fork() is passed no parameters, CreateProcess() expects no fewer than ten
parameters.
The C program shown in Figure 3.10 illustrates the CreateProcess()
function, which creates a child process that loads the application mspaint.exe.
We opt for many of the default values of the ten parameters passed to CreateProcess(). Readers interested in pursuing the details of process creation
and management in the Windows API are encouraged to consult the bibliographical notes at the end of this chapter.
The two parameters passed to the CreateProcess() function are
instances of the STARTUPINFO and PROCESS INFORMATION structures.
STARTUPINFO specifies many properties of the new process, such as window
#include <stdio.h>
#include <windows.h>
int main(VOID)
{
STARTUPINFO si;
PROCESS INFORMATION pi;
/* allocate memory */
ZeroMemory(&si, sizeof(si));
si.cb = sizeof(si);
ZeroMemory(&pi, sizeof(pi));
/* create child process */
if (!CreateProcess(NULL, /* use command line */
"C:∖∖WINDOWS∖∖system32∖∖mspaint.exe", /* command */
NULL, /* don’t inherit process handle */
NULL, /* don’t inherit thread handle */
FALSE, /* disable handle inheritance */
0, /* no creation flags */
NULL, /* use parent’s environment block */
NULL, /* use parent’s existing directory */
&si,
&pi))
{
fprintf(stderr, "Create Process Failed");
return -1;
}
/* parent will wait for the child to complete */
WaitForSingleObject(pi.hProcess, INFINITE);
printf("Child Complete");
/* close handles */
CloseHandle(pi.hProcess);
CloseHandle(pi.hThread);
}
size and appearance and handles to standard input and output files. The
PROCESS INFORMATION structure contains a handle and the identifiers to
the newly created process and its thread. We invoke the ZeroMemory()
function to allocate memory for each of these structures before proceeding
with CreateProcess().
The first two parameters passed to CreateProcess() are the application
name and command-line parameters. If the application name is NULL (as it
is in this case), the command-line parameter specifies the application to load. In this instance, we are loading the Microsoft Windows mspaint.exe application. Beyond these two initial parameters, we use the default parameters for
inheriting process and thread handles as well as specifying that there will be no
creation flags. We also use the parent’s existing environment block and starting
directory. Last, we provide two pointers to the STARTUPINFO and PROCESS -
INFORMATION structures created at the beginning of the program. In Figure
3.8, the parent process waits for the child to complete by invoking the wait()
system call. The equivalent of this in Windows is WaitForSingleObject(),
which is passed a handle of the child process—pi.hProcess—and waits for
this process to complete. Once the child process exits, control returns from the
WaitForSingleObject() function in the parent process.</windows.h></stdio.h>

Question 18

Process Termination

Answer 18

A process terminates when it finishes executing its final statement and asks
the operating system to delete it by using the exit() system call. At that
point, the process may return a status value (typically an integer) to its waiting
parent process (via the wait() system call). All the resources of the process
—including physical and virtual memory, open files, and I/O buffers—are
deallocated and reclaimed by the operating system.
Termination can occur in other circumstances as well. A process can cause
the termination of another process via an appropriate system call (for example,
TerminateProcess() in Windows). Usually, such a system call can be invoked
only by the parent of the process that is to be terminated. Otherwise, a user—
or a misbehaving application—could arbitrarily kill another user’s processes.
Note that a parent needs to know the identities of its children if it is to terminate
them. Thus, when one process creates a new process, the identity of the newly
created process is passed to the parent.
A parent may terminate the execution of one of its children for a variety of
reasons, such as these:
* The child has exceeded its usage of some of the resources that it has been
allocated. (To determine whether this has occurred, the parent must have
a mechanism to inspect the state of its children.)
* The task assigned to the child is no longer required.
* The parent is exiting, and the operating system does not allow a child to
continue if its parent terminates.
Some systems do not allow a child to exist if its parent has terminated.
In such systems, if a process terminates (either normally or abnormally), then
all its children must also be terminated. This phenomenon, referred to as
cascading termination, is normally initiated by the operating system.
To illustrate process execution and termination, consider that, in Linux and
UNIX systems, we can terminate a process by using the exit() system call,
providing an exit status as a parameter:
/* exit with status 1 */
exit(1);

In fact, under normal termination, exit() will be called either directly (as
shown above) or indirectly, as the C run-time library (which is added to UNIX
executable files) will include a call to exit() by default.
A parent process may wait for the termination of a child process by using
the wait() system call. The wait() system call is passed a parameter that
allows the parent to obtain the exit status of the child. This system call also
returns the process identifier of the terminated child so that the parent can tell
which of its children has terminated:
pid t pid;
int status;
pid = wait(&status);
When a process terminates, its resources are deallocated by the operating
system. However, its entry in the process table must remain there until the
parent calls wait(), because the process table contains the process’s exit status.
A process that has terminated, but whose parent has not yet called wait(), is
known as a zombie process. All processes transition to this state when they
terminate, but generally they exist as zombies only briefly. Once the parent
calls wait(), the process identifier of the zombie process and its entry in the
process table are released.
Now consider what would happen if a parent did not invoke wait() and
instead terminated, thereby leaving its child processes as orphans. Traditional
UNIX systems addressed this scenario by assigning the init process as the new
parent to orphan processes. (Recall from Section 3.3.1 that init serves as the
root of the process hierarchy in UNIX systems.) The init process periodically
invokes wait(), thereby allowing the exit status of any orphaned process to be
collected and releasing the orphan’s process identifier and process-table entry.
Although most Linux systems have replaced init with systemd, the latter
process can still serve the same role, although Linux also allows processes other
than systemd to inherit orphan processes and manage their termination.

Question 19

Android Process Hierarchy

Answer 19

Because of resource constraints such as limited memory, mobile operating
systems may have to terminate existing processes to reclaim limited system
resources. Rather than terminating an arbitrary process, Android has identified
an importance hierarchy of processes, and when the system must terminate
a process to make resources available for a new, or more important, process,
it terminates processes in order of increasing importance. From most to least
important, the hierarchy of process classifications is as follows:
* Foreground process—The current process visible on the screen, representing the application the user is currently interacting with
* Visible process—A process that is not directly visible on the foreground
but that is performing an activity that the foreground process is referring
to (that is, a process performing an activity whose status is displayed on
the foreground process)
* Service process—A process that is similar to a background process but
is performing an activity that is apparent to the user (such as streaming
music)
* Background process—A process that may be performing an activity but
is not apparent to the user.
* Empty process—A process that holds no active components associated
with any application
If system resources must be reclaimed, Android will first terminate empty
processes, followed by background processes, and so forth. Processes are
assigned an importance ranking, and Android attempts to assign a process as
high a ranking as possible. For example, if a process is providing a service and
is also visible, it will be assigned the more-important visible classification.
Furthermore, Android development practices suggest following the guidelines of the process life cycle. When these guidelines are followed, the state of
a process will be saved prior to termination and resumed at its saved state if
the user navigates back to the application.

Question 20

Interprocess Communication

Answer 20

Processes executing concurrently in the operating system may be either independent processes or cooperating processes. A process is independent if it does
not share data with any other processes executing in the system. A process
is cooperating if it can affect or be affected by the other processes executing
in the system. Clearly, any process that shares data with other processes is a
cooperating process.
There are several reasons for providing an environment that allows process
cooperation:
* Information sharing. Since several applications may be interested in the
same piece of information (for instance, copying and pasting), we must
provide an environment to allow concurrent access to such information.
* Computation speedup. If we want a particular task to run faster, we must
break it into subtasks, each of which will be executing in parallel with the
others. Notice that such a speedup can be achieved only if the computer
has multiple processing cores.
* Modularity. We may want to construct the system in a modular fashion,
dividing the system functions into separate processes or threads, as we
discussed in Chapter 2.
Cooperating processes require an interprocess communication (IPC)
mechanism that will allow them to exchange data— that is, send data to
and receive data from each other. There are two fundamental models of
interprocess communication: shared memory and message passing. In the
shared-memory model, a region of memory that is shared by the cooperating
processes is established. Processes can then exchange information by reading
and writing data to the shared region. In the message-passing model, communication takes place by means of messages exchanged between the
cooperating processes. The two communications models are contrasted in
Figure 3.11. Both of the models just mentioned are common in operating systems,
and many systems implement both. Message passing is useful for exchanging
smaller amounts of data, because no conflicts need be avoided. Message passing is also easier to implement in a distributed system than shared memory.
(Although there are systems that provide distributed shared memory, we do
not consider them in this text.) Shared memory can be faster than message passing, since message-passing systems are typically implemented using system
calls and thus require the more time-consuming task of kernel intervention.
In shared-memory systems, system calls are required only to establish shared memory regions. Once shared memory is established, all accesses are treated
as routine memory accesses, and no assistance from the kernel is required.
In Section 3.5 and Section 3.6 we explore shared-memory and message passing systems in more detail.

Question 21

MULTIPROCESS ARCHITECTURE—CHROME BROWSER

Answer 21

Many websites contain active content, such as JavaScript, Flash, and HTML5
to provide a rich and dynamic web-browsing experience. Unfortunately,
these web applications may also contain software bugs, which can result in
sluggish response times and can even cause the web browser to crash. This
isn’t a big problem in a web browser that displays content from only one website. But most contemporary web browsers provide tabbed browsing, which
allows a single instance of a web browser application to open several websites
at the same time, with each site in a separate tab. To switch between the different sites, a user need only click on the appropriate tab. This arrangement
is illustrated below:
Aproblem with this approach is that if a web application in any tab crashes,
the entire process—including all other tabs displaying additional websites—
crashes as well.
Google’s Chrome web browser was designed to address this issue by
using a multiprocess architecture. Chrome identifies three different types of
processes: browser, renderers, and plug-ins.
* The browser process is responsible for managing the user interface as
well as disk and network I/O. A new browser process is created when
Chrome is started. Only one browser process is created.
* Renderer processes contain logic for rendering web pages. Thus, they
contain the logic for handling HTML, Javascript, images, and so forth. As
a general rule, a new renderer process is created for each website opened
in a new tab, and so several renderer processes may be active at the same
time.
* A plug-in process is created for each type of plug-in (such as Flash or
QuickTime) in use. Plug-in processes contain the code for the plug-in as
well as additional code that enables the plug-in to communicate with
associated renderer processes and the browser process.
The advantage of the multiprocess approach is that websites run in isolation from one another. If one website crashes, only its renderer process is
affected; all other processes remain unharmed. Furthermore, renderer processes run in a sandbox, which means that access to disk and network I/O is
restricted, minimizing the effects of any security exploits.

Question 22

IPC in Shared-Memory Systems

Answer 22

Interprocess communication using shared memory requires communicating
processes to establish a region of shared memory. Typically, a shared-memory
region resides in the address space of the process creating the shared-memory
segment. Other processes that wish to communicate using this shared-memory
segment must attach it to their address space. Recall that, normally, the operating system tries to prevent one process from accessing another process’s
memory. Shared memory requires that two or more processes agree to remove
this restriction. They can then exchange information by reading and writing
data in the shared areas. The form of the data and the location are determined
by these processes and are not under the operating system’s control. The processes are also responsible for ensuring that they are not writing to the same
location simultaneously. To illustrate the concept of cooperating processes, let’s consider the producer–consumer problem, which is a common paradigm for cooperating processes. A producer process produces information that is consumed by a consumer process. For example, a compiler may produce assembly code that is
consumed by an assembler. The assembler, in turn, may produce object modules that are consumed by the loader. The producer–consumer problem also
provides a useful metaphor for the client–server paradigm. We generally think
of a server as a producer and a client as a consumer. For example, a web server
produces (that is, provides) web content such as HTML files and images, which
are consumed (that is, read) by the client web browser requesting the resource.
One solution to the producer–consumer problem uses shared memory. To
allow producer and consumer processes to run concurrently, we must have
available a buffer of items that can be filled by the producer and emptied by
the consumer. This buffer will reside in a region of memory that is shared by
the producer and consumer processes. A producer can produce one item while
the consumer is consuming another item. The producer and consumer must be
synchronized, so that the consumer does not try to consume an item that has
not yet been produced.
Two types of buffers can be used. The unbounded buffer places no practical limit on the size of the buffer. The consumer may have to wait for new
items, but the producer can always produce new items. The bounded buffer
assumes a fixed buffer size. In this case, the consumer must wait if the buffer
is empty, and the producer must wait if the buffer is full.
Let’s look more closely at how the bounded buffer illustrates interprocess
communication using shared memory. The following variables reside in a
region of memory shared by the producer and consumer processes:
#define BUFFER SIZE 10
typedef struct {
…
} item;
item buffer[BUFFER SIZE];
int in = 0;
int out = 0;
The shared buffer is implemented as a circular array with two logical pointers:
in and out. The variable in points to the next free position in the buffer; out
points to the first full position in the buffer. The buffer is empty when in ==
out; the buffer is full when ((in + 1) % BUFFER SIZE) == out.
The code for the producer process is shown in Figure 3.12, and the code for
the consumer process is shown in Figure 3.13. The producer process has a local
variable next produced in which the new item to be produced is stored. The
consumer process has a local variable next consumed in which the item to be
consumed is stored.
This scheme allows at most BUFFER SIZE − 1 items in the buffer at the
same time. We leave it as an exercise for you to provide a solution in which
BUFFER SIZE items can be in the buffer at the same time. In Section 3.7.1, we
illustrate the POSIX API for shared memory.

Question 23

IPC in Message-Passing Systems

Answer 23

In Section 3.5, we showed how cooperating processes can communicate in a
shared-memory environment. The scheme requires that these processes share a
region of memory and that the code for accessing and manipulating the shared
memory be written explicitly by the application programmer. Another way to
achieve the same effect is for the operating system to provide the means for
cooperating processes to communicate with each other via a message-passing
facility

item next consumed;
while (true) {
while (in == out)
; /* do nothing /
next consumed = buffer[out];
out = (out + 1) % BUFFER SIZE;
/ consume the item in next consumed */
}

Message passing provides a mechanism to allow processes to communicate
and to synchronize their actions without sharing the same address space. It
is particularly useful in a distributed environment, where the communicating
processes may reside on different computers connected by a network. For
example, an Internet chat program could be designed so that chat participants
communicate with one another by exchanging messages.
A message-passing facility provides at least two operations:
send(message)
and
receive(message)
Messages sent by a process can be either fixed or variable in size. If only
fixed-sized messages can be sent, the system-level implementation is straightforward. This restriction, however, makes the task of programming more difficult. Conversely, variable-sized messages require a more complex system-level
implementation, but the programming task becomes simpler. This is a common
kind of tradeoff seen throughout operating-system design.
If processes P and Q want to communicate, they must send messages to and
receive messages from each other: a communication link must exist between
them. This link can be implemented in a variety of ways. We are concerned here
not with the link’s physical implementation (such as shared memory, hardware
bus, or network, which are covered in Chapter 19) but rather with its logical
implementation. Here are several methods for logically implementing a link
and the send()/receive() operations:
* Direct or indirect communication
* Synchronous or asynchronous communication
* Automatic or explicit buffering
We look at issues related to each of these features next.

Question 24

Naming

Answer 24

Processes that want to communicate must have a way to refer to each other.
They can use either direct or indirect communication.
Under direct communication, each process that wants to communicate
must explicitly name the recipient or sender of the communication. In this
scheme, the send() and receive() primitives are defined as:
* send(P, message)—Send a message to process P.
* receive(Q, message)—Receive a message from process Q.
A communication link in this scheme has the following properties:
* A link is established automatically between every pair of processes that
want to communicate. The processes need to know only each other’s
identity to communicate.

• A link is associated with exactly two processes.
• Between each pair of processes, there exists exactly one link.
  This scheme exhibits symmetry in addressing; that is, both the sender process and the receiver process must name the other to communicate. A variant
  of this scheme employs asymmetry in addressing. Here, only the sender names
  the recipient; the recipient is not required to name the sender. In this scheme,
  the send() and receive() primitives are defined as follows:
• send(P, message)—Send a message to process P.
• receive(id, message)—Receive a message from any process. The variable id is set to the name of the process with which communication has
  taken place.
  The disadvantage in both of these schemes (symmetric and asymmetric)
  is the limited modularity of the resulting process definitions. Changing the
  identifier of a process may necessitate examining all other process definitions.
  All references to the old identifier must be found, so that they can be modified
  to the new identifier. In general, any such hard-coding techniques, where identifiers must be explicitly stated, are less desirable than techniques involving
  indirection, as described next.
  With indirect communication, the messages are sent to and received from
  mailboxes, or ports. A mailbox can be viewed abstractly as an object into
  which messages can be placed by processes and from which messages can
  be removed. Each mailbox has a unique identification. For example, POSIX
  message queues use an integer value to identify a mailbox. A process can communicate with another process via a number of different mailboxes, but two
  processes can communicate only if they have a shared mailbox. The send()
  and receive() primitives are defined as follows:
• send(A, message)—Send a message to mailbox A.
• receive(A, messsage)—Receive a message from mailbox A.
  In this scheme, a communication link has the following properties:
• A link is established between a pair of processes only if both members of
  the pair have a shared mailbox.
• A link may be associated with more than two processes.
• Between each pair of communicating processes, a number of different links
  may exist, with each link corresponding to one mailbox.
  Now suppose that processes P1
  , P2
  , and P3
  all share mailbox A. Process P1
  sends a message to A, while both P2
  and P3
  execute a receive() from A. Which
  process will receive the message sent by P1
  ? The answer depends on which of
  the following methods we choose:
• Allow a link to be associated with two processes at most.
• Allow at most one process at a time to execute a receive() operation.
• Allow the system to select arbitrarily which process will receive the message (that is, either P2 or P3
  , but not both, will receive the message). The
  system may define an algorithm for selecting which process will receive
  the message (for example, round robin, where processes take turns receiving messages). The system may identify the receiver to the sender.
  A mailbox may be owned either by a process or by the operating system.
  If the mailbox is owned by a process (that is, the mailbox is part of the address
  space of the process), then we distinguish between the owner (which can
  only receive messages through this mailbox) and the user (which can only
  send messages to the mailbox). Since each mailbox has a unique owner, there
  can be no confusion about which process should receive a message sent to
  this mailbox. When a process that owns a mailbox terminates, the mailbox
  disappears. Any process that subsequently sends a message to this mailbox
  must be notified that the mailbox no longer exists.
  In contrast, a mailbox that is owned by the operating system has an existence of its own. It is independent and is not attached to any particular process.
  The operating system then must provide a mechanism that allows a process to
  do the following:
• Create a new mailbox.
• Send and receive messages through the mailbox.
• Delete a mailbox.
  The process that creates a new mailbox is that mailbox’s owner by default.
  Initially, the owner is the only process that can receive messages through this
  mailbox. However, the ownership and receiving privilege may be passed to
  other processes through appropriate system calls. Of course, this provision
  could result in multiple receivers for each mailbox.

Question 25

Synchronization

Answer 25

Communication between processes takes place through calls to send() and
receive() primitives. There are different design options for implementing
each primitive. Message passing may be either blocking or nonblocking—
also known as synchronous and asynchronous. (Throughout this text, you will
encounter the concepts of synchronous and asynchronous behavior in relation
to various operating-system algorithms.)
* Blocking send. The sending process is blocked until the message is
received by the receiving process or by the mailbox.
* Nonblocking send. The sending process sends the message and resumes
operation.
* Blocking receive. The receiver blocks until a message is available.
* Nonblocking receive. The receiver retrieves either a valid message or a
null.
message next produced;
while (true) {
/* produce an item in next produced */
send(next produced);
}
Figure 3.14 The producer process using message passing.
Different combinations of send() and receive() are possible. When both
send() and receive() are blocking, we have a rendezvous between the
sender and the receiver. The solution to the producer–consumer problem
becomes trivial when we use blocking send() and receive() statements. The
producer merely invokes the blocking send() call and waits until the message
is delivered to either the receiver or the mailbox. Likewise, when the consumer
invokes receive(), it blocks until a message is available.

Question 26

Buffering

Answer 26

Whether communication is direct or indirect, messages exchanged by communicating processes reside in a temporary queue. Basically, such queues can be
implemented in three ways:
* Zero capacity. The queue has a maximum length of zero; thus, the link
cannot have any messages waiting in it. In this case, the sender must block
until the recipient receives the message.
* Bounded capacity. The queue has finite length n; thus, at most n messages
can reside in it. If the queue is not full when a new message is sent, the
message is placed in the queue (either the message is copied or a pointer
to the message is kept), and the sender can continue execution without waiting. The link’s capacity is finite, however. If the link is full, the sender
must block until space is available in the queue.
* Unbounded capacity. The queue’s length is potentially infinite; thus, any
number of messages can wait in it. The sender never blocks.
The zero-capacity case is sometimes referred to as a message system with no
buffering. The other cases are referred to as systems with automatic buffering.

Question 27

POSIX Shared Memory

Answer 27

Several IPC mechanisms are available for POSIX systems, including shared
memory and message passing. Here, we explore the POSIX API for shared
memory.
POSIX shared memory is organized using memory-mapped files, which
associate the region of shared memory with a file. A process must first create
a shared-memory object using the shm open() system call, as follows:
fd = shm open(name, O CREAT | O RDWR, 0666);
The first parameter specifies the name of the shared-memory object. Processes
that wish to access this shared memory must refer to the object by this name.
The subsequent parameters specify that the shared-memory object is to be created if it does not yet exist (O CREAT) and that the object is open for reading and
writing (O RDWR). The last parameter establishes the file-access permissions of
the shared-memory object. A successful call to shm open() returns an integer
file descriptor for the shared-memory object.
Once the object is established, the ftruncate() function is used to
configure the size of the object in bytes. The call
ftruncate(fd, 4096);
sets the size of the object to 4,096 bytes.
Finally, the mmap() function establishes a memory-mapped file containing
the shared-memory object. It also returns a pointer to the memory-mapped file
that is used for accessing the shared-memory object.
The programs shown in Figure 3.16 and Figure 3.17 use the producer–
consumer model in implementing shared memory. The producer establishes a
shared-memory object and writes to shared memory, and the consumer reads
from shared memory.

Question 28

Mach Message Passing

Answer 28

As an example of message passing, we next consider the Mach operating
system. Mach was especially designed for distributed systems, but was shown
to be suitable for desktop and mobile systems as well, as evidenced by its
inclusion in the macOS and iOS operating systems, as discussed in Chapter 2.
The Mach kernel supports the creation and destruction of multiple tasks,
which are similar to processes but have multiple threads of control and
fewer associated resources. Most communication in Mach—including all intertask communication—is carried out by messages. Messages are sent to, and
received from, mailboxes, which are called ports in Mach. Ports are finite in size
and unidirectional; for two-way communication, a message is sent to one port,
and a response is sent to a separate reply port. Each port may have multiple
senders, but only one receiver. Mach uses ports to represent resources such
as tasks, threads, memory, and processors, while message passing provides
an object-oriented approach for interacting with these system resources and
services. Message passing may occur between any two ports on the same host
or on separate hosts on a distributed system.
Associated with each port is a collection of port rights that identify
the capabilities necessary for a task to interact with the port. For example,
for a task to receive a message from a port, it must have the capability
MACH PORT RIGHT RECEIVE for that port. The task that creates a port is that
port’s owner, and the owner is the only task that is allowed to receive messages
from that port. A port’s owner may also manipulate the capabilities for a port.
This is most commonly done in establishing a reply port. For example, assume
that task T1 owns port P1, and it sends a message to port P2, which is owned
by task T2. If T1 expects to receive a reply from T2, it must grant T2 the
right MACH PORT RIGHT SEND for port P1. Ownership of port rights is at the
task level, which means that all threads belonging to the same task share the
same port rights. Thus, two threads belonging to the same task can easily
communicate by exchanging messages through the per-thread port associated
with each thread.
When a task is created, two special ports— the Task Self port and the
Notify port—are also created. The kernel has receive rights to the Task Self
port, which allows a task to send messages to the kernel. The kernel can send
notification of event occurrences to a task’s Notify port (to which, of course,
the task has receive rights).
The mach port allocate() function call creates a new port and allocates
space for its queue of messages. It also identifies the rights for the port. Each
port right represents a name for that port, and a port can only be accessed via a right. Port names are simple integer values and behave much like UNIX file
descriptors. The following example illustrates creating a port using this API:
mach port t port; // the name of the port right
mach port allocate(
mach task self(), // a task referring to itself
MACH PORT RIGHT RECEIVE, // the right for this port
&port); // the name of the port right
Each task also has access to a bootstrap port, which allows a task to register
a port it has created with a system-wide bootstrap server. Once a port has been
registered with the bootstrap server, other tasks can look up the port in this
registry and obtain rights for sending messages to the port.
The queue associated with each port is finite in size and is initially empty.
As messages are sent to the port, the messages are copied into the queue. All
messages are delivered reliably and have the same priority. Mach guarantees
that multiple messages from the same sender are queued in first-in, firstout (FIFO) order but does not guarantee an absolute ordering. For instance,
messages from two senders may be queued in any order.
Mach messages contain the following two fields:
* A fixed-size message header containing metadata about the message,
including the size of the message as well as source and destination ports.
Commonly, the sending thread expects a reply, so the port name of the
source is passed on to the receiving task, which can use it as a “return
address” in sending a reply.
* A variable-sized body containing data.
Messages may be either simple or complex. A simple message contains
ordinary, unstructured user data that are not interpreted by the kernel. A
complex message may contain pointers to memory locations containing data
(known as “out-of-line” data) or may also be used for transferring port rights
to another task. Out-of-line data pointers are especially useful when a message
must pass large chunks of data. A simple message would require copying and
packaging the data in the message; out-of-line data transmission requires only
a pointer that refers to the memory location where the data are stored.
The function mach msg() is the standard API for both sending and
receiving messages. The value of one of the function’s parameters—either
MACH SEND MSG or MACH RCV MSG—indicates if it is a send or receive operation.
We now illustrate how it is used when a client task sends a simple message to
a server task. Assume there are two ports—client and server—associated
with the client and server tasks, respectively. The code in Figure 3.18 shows
the client task constructing a header and sending a message to the server, as
well as the server task receiving the message sent from the client.
The mach msg() function call is invoked by user programs for performing
message passing. mach msg() then invokes the function mach msg trap(),
which is a system call to the Mach kernel. Within the kernel, mach msg trap()
next calls the function mach msg overwrite trap(), which then handles the
actual passing of the message. port’s queue is full, the sender has several options (specified via parameters
to mach msg():
1. Wait indefinitely until there is room in the queue.
2. Wait at most n milliseconds.
3. Do not wait at all but rather return immediately.
4. Temporarily cache a message. Here, a message is given to the operating
system to keep, even though the queue to which that message is being
sent is full. When the message can be put in the queue, a notification
message is sent back to the sender. Only one message to a full queue can
be pending at any time for a given sending thread.
The final option is meant for server tasks. After finishing a request, a server
task may need to send a one-time reply to the task that requested the service,
but it must also continue with other service requests, even if the reply port for
a client is full.
The major problem with message systems has generally been poor performance caused by copying of messages from the sender’s port to the receiver’s
port. The Mach message system attempts to avoid copy operations by using
virtual-memory-management techniques (Chapter 10). Essentially, Mach maps
the address space containing the sender’s message into the receiver’s address
space. Therefore, the message itself is never actually copied, as both the sender
and receiver access the same memory. This message-management technique
provides a large performance boost but works only for intrasystem messages.