Test 1

Question 1

operating system

Answer 1

is software that manages a computer’s hardware. It
also provides a basis for application programs and acts as an intermediary
between the computer user and the computer hardware.

Question 2

hardware

Answer 2

the central processing unit (CPU), the memory, and the
input/output (I/O) devices—provides the basic computing resources for the
system.

Question 3

application programs

Answer 3

such as word processors, spreadsheets,
compilers, and web browsers—define the ways in which these resources are
used to solve users’ computing problems. The operating system controls the
hardware and coordinates its use among the various application programs for
the various users.

Question 4

a resource allocator

Answer 4

From the computer’s point of view, the operating system is the program most
intimately involved with the hardware. In this context, we can view an operating
system as a resource allocator. A computer system has many resources
that may be required to solve a problem: CPU time, memory space, storage
space, I/O devices, and so on. The operating system acts as the manager of these
resources. Facing numerous and possibly conflicting requests for resources, the
operating system must decide how to allocate them to specific programs and
users so that it can operate the computer system efficiently and fairly.

Question 5

A control program

Answer 5

A control program manages the execution of user programs
to prevent errors and improper use of the computer. It is especially concerned
with the operation and control of I/O devices.

Question 6

Moore’s Law

Answer 6

In the 1960s, Moore’s Law predicted
that the number of transistors on an integrated circuit would double every 18
months, and that prediction has held true. Computers gained in functionality
and shrank in size, leading to a vast number of uses and a vast number and
variety of operating systems. (See Appendix A for more details on the history
of operating systems.)

Question 7

kernel

Answer 7

The kernel is a computer program at the core of a computer’s operating system and generally has complete control over everything in the system. It is the portion of the operating system code that is always resident in memory and facilitates interactions between hardware and software components.

Question 8

system
programs

Answer 8

are associated with the operating system but are not necessarily
part of the kernel

Question 9

application programs

Answer 9

which include all programs
not associated with the operation of the system.

Question 10

middleware

Answer 10

Mobile operating systems often include not only a core kernel
but also middleware—a set of software frameworks that provide additional
services to application developers.

Question 11

the operating system includes

Answer 11

the always running
kernel, middleware frameworks that ease application development
and provide features, and system programs that aid in managing the system
while it is running.

Question 12

device driver

Answer 12

Typically, operating systems have a device driver for each device controller.
This device driver understands the device controller and provides the
rest of the operating system with a uniform interface to the device. The CPU and
the device controllers can execute in parallel, competing for memory cycles. To
ensure orderly access to the shared memory, a memory controller synchronizes
access to the memory.

Question 13

interrupt

Answer 13

Hardware may trigger an interrupt at any time by sending a signal to the
CPU, usually by way of the system bus. (There may be many buses within
a computer system, but the system bus is the main communications path
between the major components.) Interrupts are used for many other purposes
as well and are a key part of how operating systems and hardware interact.
When the CPU is interrupted, it stops what it is doing and immediately
transfers execution to a fixed location. The fixed location usually contains
the starting address where the service routine for the interrupt is located.
The interrupt service routine executes; on completion, the CPU resumes the
interrupted computation. A Interrupts are an important part of a computer architecture. Each computer
design has its own interrupt mechanism, but several functions are common.
The interrupt must transfer control to the appropriate interrupt service routine.
The straightforward method for managing this transfer would be to invoke
a generic routine to examine the interrupt information.

Question 14

The interrupt routine
is

Answer 14

called indirectly through the table, with no intermediate routine needed.
Generally, the table of pointers is stored in low memory (the first hundred or so
locations). These locations hold the addresses of the interrupt service routines
for the various devices. This array, or interrupt vector, of addresses is then
indexed by a unique number, given with the interrupt request, to provide the
address of the interrupt service routine for the interrupting device. Operating
systems as different asWindows and UNIX dispatch interrupts in this manner

Question 15

interrupt vector

Answer 15

These locations hold the addresses of the interrupt service routines
for the various devices. This array, or interrupt vector, of addresses is then
indexed by a unique number, given with the interrupt request, to provide the
address of the interrupt service routine

Question 16

The interrupt architecture must also save

Answer 16

the state information ofwhatever
was interrupted, so that it can restore this information after servicing the
interrupt. If the interrupt routine needs to modify the processor state—for
instance, by modifying register values—it must explicitly save the current state
and then restore that state before returning. After the interrupt is serviced, the
saved return address is loaded into the program counter, and the interrupted
computation resumes as though the interrupt had not occurred.

Question 17

interrupt process

Answer 17

We
say that the device controller raises an interrupt by asserting a signal on the
interrupt request line, the CPU catches the interrupt and dispatches it to the
interrupt handler, and the handler clears the interrupt by servicing the device.
Figure 1.4 summarizes the interrupt-driven I/O cycle.

Question 18

The basic interrupt mechanism just described enables the CPU to respond to
an asynchronous event, as when a device controller becomes ready for service.
In a modern operating system, however, we need more sophisticated interrupthandling features.

Answer 18

1. We need the ability to defer interrupt handling during critical processing.
2. We need an efficient way to dispatch to the proper interrupt handler for
   a device.
3. We need multilevel interrupts, so that the operating system can distinguish between high- and low-priority interrupts and can respond with
   the appropriate degree of urgency

Question 19

Most CPUs have two interrupt request lines

Answer 19

One is the nonmaskable
interrupt, which is reserved for events such as unrecoverable memory errors.
The second interrupt line is maskable: it can be turned off by the CPU before
the execution of critical instruction sequences that must not be interrupted. The
maskable interrupt is used by device controllers to request service.

Question 20

interrupt
chaining,

Answer 20

in which each element in the interrupt vector points to the head of
a list of interrupt handlers. When an interrupt is raised, the handlers on the
corresponding list are called one by one, until one is found that can service
the request. This structure is a compromise between the overhead of a huge
interrupt table and the inefficiency of dispatching to a single interrupt handler

Question 21

interrupt priority
levels

Answer 21

These levels enable the CPU to defer the handling of low-priority inter

Question 22

Main memory commonly is implemented in
a semiconductor technology called dynamic random-access memory (DRAM).

Answer 22

DRAM

Question 23

volatile

Answer 23

—loses its content when power
is turned off or otherwise lost—we cannot trust it to hold the bootstrap program. Instead, for this and some other purposes, the computer uses electrically erasable programmable read-only memory (EEPROM) and other forms of
firmwar —storage that is infrequently written to and is nonvolatile.

Question 24

STORAGE DEFINITIONS AND NOTATION

Answer 24

The basic unit of computer storage is the bit. A bit can contain one of two
values, 0 and 1. All other storage in a computer is based on collections of bits.
Given enough bits, it is amazing how many things a computer can represent:
numbers, letters, images, movies, sounds, documents, and programs, to name
a few. A byte is 8 bits, and on most computers it is the smallest convenient
chunk of storage. For example, most computers don’t have an instruction to
move a bit but do have one to move a byte. A less common term is word,
which is a given computer architecture’s native unit of data. A word is made
up of one or more bytes. For example, a computer that has 64-bit registers and
64-bit memory addressing typically has 64-bit (8-byte) words. A computer
executes many operations in its native word size rather than a byte at a time.
Computer storage, along with most computer throughput, is generally
measured and manipulated in bytes and collections of bytes. A kilobyte, or
KB, is 1,024 bytes; a megabyte, or MB, is 1,0242 bytes; a gigabyte, or GB, is
1,0243 bytes; a terabyte, or TB, is 1,0244 bytes; and a petabyte, or PB, is 1,0245
bytes. Computer manufacturers often round off these numbers and say that
a megabyte is 1 million bytes and a gigabyte is 1 billion bytes. Networking
measurements are an exception to this general rule; they are given in bits
(because networks move data a bit at a time).

Question 25

A typical instruction–execution cycle,

Answer 25

first fetches an instruction from memory and stores
that instruction in the instruction register. The instruction is then decoded
and may cause operands to be fetched from memory and stored in some
internal register. After the instruction on the operands has been executed, the
result may be stored back in memory. Notice that the memory unit sees only
a stream of memory addresses. It does not know how they are generated (by
the instruction counter, indexing, indirection, literal addresses, or some other
means) or what they are for (instructions or data). Accordingly, we can ignore
how a memory address is generated by a program. We are interested only in
the sequence of memory addresses generated by the running program.

Question 26

Ideally, we want the programs and data to reside in main memory permanently. This arrangement usually is not possible on most systems for two
reasons:

Answer 26

1. Main memory is usually too small to store all needed programs and data
   permanently.
2. Main memory, as mentioned, is volatile—it loses its contents when power
   is turned off or otherwise lost.

Question 27

The most common secondary-storage devices are

Answer 27

hard-disk drives (HDDs)
and nonvolatile memory (NVM) devices, which provide storage for both
programs and data. Most programs (system and application) are stored in
secondary storage until they are loaded into memory. Many programs then use
secondary storage as both the source and the destination of their processing.
Secondary storage is also much slower than main memory

Question 28

semiconductor memory

Answer 28

The top four levels of memory in the figure are constructed using semiconductor memory, which consists of semiconductor-based electronic circuits.
NVM devices, at the fourth level, have several variants but in general are faster
than hard disks. The most common form of NVM device is flash memory, which
is popular in mobile devices such as smartphones and tablets. Increasingly,
flash memory is being used for long-term storage on laptops, desktops, and
servers as well.

Question 29

volotile vs non volotile memory

Answer 29

Volatile storage will be referred to simply as memory. If we need to emphasize a particular type of storage device (for example, a register),we will do
so explicitly.
* Nonvolatile storage retains its contents when power is lost. It will be
referred to as NVS. The vast majority of the time we spend on NVS will
be on secondary storage. This type of storage can be classified into two
distinct types:
◦ Mechanical. A few examples of such storage systems are HDDs, optical
disks, holographic storage, and magnetic tape. If we need to emphasize
a particular type of mechanical storage device (for example, magnetic
tape), we will do so explicitly.
◦ Electrical. A few examples of such storage systems are flash memory,
FRAM, NRAM, and SSD. Electrical storage will be referred to as NVM. If
we need to emphasize a particular type of electrical storage device (for
example, SSD), we will do so explicitly.
Mechanical storage is generally larger and less expensive per byte than
electrical storage. Conversely, electrical storage is typically costly, smaller,
and faster than mechanical storage.

Question 30

when DMA is used

Answer 30

The form of interrupt-driven I/O described in Section 1.2.1 is fine for
moving small amounts of data but can produce high overhead when used for
bulk data movement such as NVS I/O. To solve this problem, direct memory
access (DMA) is used. After setting up buffers, pointers, and counters for the
I/O device, the device controller transfers an entire block of data directly to
or from the device and main memory, with no intervention by the CPU. Only
one interrupt is generated per block, to tell the device driver that the operation
has completed, rather than the one interrupt per byte generated for low-speed
devices. While the device controller is performing these operations, the CPU is
available to accomplish other work.
Some high-end systems use switch rather than bus architecture. On these
systems, multiple components can talk to other components concurrently,
rather than competing for cycles on a shared bus. In this case, DMA is even
more effective. Figure 1.7 shows the interplay of all components of a computer
system.

Question 31

The core

Answer 31

is the component that executes instructions and registers for storing data locally. The one main CPU with
its core is capable of executing a general-purpose instruction set, including
instructions from processes. These systems have other special-purpose processors as well. They may come in the form of device-specific processors, such as
disk, keyboard, and graphics controllers.

Question 32

Multiprocessor Systems

Answer 32

On modern computers, from mobile devices to servers, multiprocessor systems now dominate the landscape of computing. Traditionally, such systems
have two (or more) processors, each with a single-core CPU. The processors share the computer bus and sometimes the clock, memory, and peripheral devices. The primary advantage of multiprocessor systems is increased
throughput. That is, by increasing the number of processors, we expect to get
more work done in less time. The speed-up ratio with N processors is not N,
however; it is less than N. When multiple processors cooperate on a task, a certain amount of overhead is incurred in keeping all the parts working correctly.
This overhead, plus contention for shared resources, lowers the expected gain
from additional processors.

Question 33

symmetric multiprocessing (SMP)

Answer 33

in which each peer CPU processor performs all tasks, including
operating-system functions and user processes. Figure 1.8 illustrates a typical
SMP architecture with two processors, each with its own CPU. Notice that each
CPU processor has its own set of registers, as well as a private—or local—
cache. However, all processors share physical memory over the system bus.
The benefit of this model is that many processes can run simultaneously
—N processes can run if there are N CPUs—without causing performance
to deteriorate significantly. However, since the CPUs are separate, one may
be sitting idle while another is overloaded, resulting in inefficiencies. These
inefficiencies can be avoided if the processors share certain data structures. A
multiprocessor system of this form will allow processes and resources—such
as memory— to be shared dynamically among the various processors and can
lower the workload variance among the processors. S

Question 34

multicore systems

Answer 34

in which multiple computing cores reside on a single chip.
Multicore systems can be more efficient than multiple chips with single cores
because on-chip communication is faster than between-chip communication.

Question 35

DEFINITIONS OF COMPUTER SYSTEM COMPONENTS

Answer 35

• CPU—The hardware that executes instructions.
• Processor—A physical chip that contains one or more CPUs.
• Core—The basic computation unit of the CPU.
• Multicore— Including multiple computing cores on the same CPU.
• Multiprocessor— Including multiple processors.
  Although virtually all systems are now multicore, we use the general term
  CPU when referring to a single computational unit of a computer system and
  core as well as multicore when specifically referring to one or more cores on
  a CPU.

Question 36

Adding additional CPUs to a multiprocessor system

Answer 36

will increase computing power; however, as suggested earlier, the concept does not scale very well,
and once we add too many CPUs, contention for the system bus becomes a
bottleneck and performance begins to degrade. An alternative approach is
instead to provide each CPU (or group of CPUs) with its own local memory
that is accessed via a small, fast local bus. The CPUs are connected by a shared
system interconnect, so that all CPUs share one physical address space. This
approach—known as non-uniform memory access, or NUMA—is illustrated
in Figure 1.10. The advantage is that, when a CPU accesses its local memory,
not only is it fast, but there is also no contention over the system interconnect.
Thus, NUMA systems can scale more effectively as more processors are added.

Question 37

The CPUs are connected by a shared
system interconnect,

Answer 37

so that all CPUs share one physical address space. This
approach—known as non-uniform memory access, or NUMA—is illustrated
in Figure 1.10. The advantage is that, when a CPU accesses its local memory,
not only is it fast, but there is also no contention over the system interconnect.
Thus, NUMA systems can scale more effectively as more processors are added.
A potential drawback with a NUMA system is increased latency when a CPU
must access remote memory across the system interconnect, creating a possible
performance penalty. In other words, for example, CPU0 cannot access the local
memory of CPU3 as quickly as it can access its own local memory, slowing down
performance. Operating systems can minimize this NUMA penalty through
careful CPU scheduling and memory management, as discussed in Section 5.5.2
and Section 10.5.4. Because NUMA systems can scale to accommodate a large
number of processors, they are becoming increasingly popular on servers as
well as high-performance computing systems.

Question 38

blade servers

Answer 38

are systems in which multiple processor boards, I/O
boards, and networking boards are placed in the same chassis. The difference between these and traditional multiprocessor systems is that each bladeprocessor board boots independently and runs its own operating system. Some
blade-server boards are multiprocessor as well, which blurs the lines between types of computers. In essence, these servers consist of multiple independent
multiprocessor systems.

Question 39

clustered system

Answer 39

Another type of multiprocessor system is a clustered system, which gathers together multiple CPUs. Clustered systems differ from the multiprocessor
systems described in Section 1.3.2 in that they are composed of two or more
individual systems—or nodes—joined together; each node is typically a multicore system. Such systems are considered loosely coupled. We should note
that the definition of clustered is not concrete; many commercial and opensource packages wrestle to define what a clustered system is and why one
form is better than another. The generally accepted definition is that clustered
computers share storage and are closely linked via a local-area network LAN
(as described in Chapter 19) or a faster interconnect, such as InfiniBand.

Question 40

Clustering is usually used to provide high-availability service—

Answer 40

that is,
service that will continue even if one or more systems in the cluster fail.
Generally, we obtain high availability by adding a level of redundancy in the
system. A layer of cluster software runs on the cluster nodes. Each node can
monitor one or more of the others (over the network). If the monitored machine
fails, the monitoring machine can take ownership of its storage and restart the
applications that were running on the failed machine. The users and clients of
the applications see only a brief interruption of service.
High availability provides increased reliability, which is crucial in many
applications. The ability to continue providing service proportional to the level
of surviving hardware is called graceful degradation. Some systems go beyond
graceful degradation and are called fault tolerant, because they can suffer a
failure of any single component and still continue operation. Fault tolerance
requires a mechanism to allow the failure to be detected, diagnosed, and, if
possible, corrected.

Question 41

Clustering can be structured asymmetrically or symmetrically

Answer 41

In asymmetric clustering, one machine is in hot-standby mode while the other is running the applications. The hot-standby host machine does nothing but monitor
the active server. If that server fails, the hot-standby host becomes the active server. In symmetric clustering, two or more hosts are running applications
and are monitoring each other. This structure is obviously more efficient, as it
uses all of the available hardware. However, it does require that more than one
application be available to run.

Question 42

Multiprogramming and Multitasking

Answer 42

One of the most important aspects of operating systems is the ability to run
multiple programs, as a single program cannot, in general, keep either the CPU
or the I/O devices busy at all times. Furthermore, users typically want to run
more than one program at a time as well. Multiprogramming increases CPU
utilization, as well as keeping users satisfied, by organizing programs so that
the CPU always has one to execute. In a multiprogrammed system, a program
in execution is termed a process.
The idea is as follows: The operating system keeps several processes in
memory simultaneously (Figure 1.12). The operating system picks and begins
to execute one of these processes. Eventually, the process may have to wait for
some task, such as an I/O operation, to complete. In a non-multiprogrammed
system, the CPU would sit idle. In a multiprogrammed system, the operating
system simply switches to, and executes, another process. When that process
needs to wait, the CPU switches to another process, and so on. Eventually, the
first process finishes waiting and gets the CPU back. As long as at least one
process needs to execute, the CPU is never idle.
This idea is common in other life situations. A lawyer does not work for
only one client at a time, for example. While one case is waiting to go to trial
or have papers typed, the lawyer can work on another case. If she has enough
clients, the lawyer will never be idle for lack of work. (Idle lawyers tend to
become politicians, so there is a certain social value in keeping lawyers busy.)
Multitasking is a logical extension of multiprogramming. In multitasking
systems, the CPU executes multiple processes by switching among them, but
the switches occur frequently, providing the user with a fast response time.
Consider that when a process executes, it typically executes for only a short
time before it either finishes or needs to perform I/O. I/O may be interactive;
that is, output goes to a display for the user, and input comes from a user
keyboard, mouse, or touch screen. Since interactive I/O typically runs at “people speeds,” it may take a long time to complete. I

Question 43

At the very least, we need two separate modes of operation: user mode
and kernel mode (also called supervisor mode, system mode, or privileged
mode).

Answer 43

A bit, called the mode bit, is added to the hardware of the computer
to indicate the current mode: kernel (0) or user (1). With the mode bit, we can
distinguish between a task that is executed on behalf of the operating system
and one that is executed on behalf of the user. When the computer system is
executing on behalf of a user application, the system is in user mode. However,
when a user application requests a service from the operating system (via a
system call), the system must transition from user to kernel mode to fulfill the request. This is shown in Figure 1.13. As we shall see, this architectural
enhancement is useful for many other aspects of system operation as well.

Question 44

Timer

Answer 44

We must ensure that the operating system maintains control over the CPU.
We cannot allow a user program to get stuck in an infinite loop or to fail
to call system services and never return control to the operating system. To
accomplish this goal, we can use a timer. A timer can be set to interrupt
the computer after a specified period. The period may be fixed (for example,
1/60 second) or variable (for example, from 1 millisecond to 1 second). A
variable timer is generally implemented by a fixed-rate clock and a counter.
The operating system sets the counter. Every time the clock ticks, the counter
is decremented. When the counter reaches 0, an interrupt occurs. For instance,
a 10-bit counter with a 1-millisecond clock allows interrupts at intervals from
1 millisecond to 1,024 milliseconds, in steps of 1 millisecond.

Question 45

The operating system is responsible for the following activities in connection with file management:

Answer 45

Creating and deleting files
* Creating and deleting directories to organize files
* Supporting primitives for manipulating files and directories
* Mapping files onto mass storage
* Backing up files on stable (nonvolatile) storage media

Question 46

Caching

Answer 46

is an important principle of computer systems. Here’s how it works.
Information is normally kept in some storage system (such as main memory).
As it is used, it is copied into a faster storage system— the cache—on a temporary basis. When we need a particular piece of information, we first check
whether it is in the cache. If it is, we use the information directly from the cache.

Question 47

The I/O subsystem consists of several components:

Answer 47

A memory-management component that includes buffering, caching, and
spooling
* A general device-driver interface
* Drivers for specific hardware devices

Question 48

Protection

Answer 48

then, is any mechanism for controlling the access of processes
or users to the resources defined by a computer system. This mechanism must
provide means to specify the controls to be imposed and to enforce the controls.
Protection can improve reliability by detecting latent errors at the interfaces
between component subsystems. Early detection of interface errors can often
prevent contamination of a healthy subsystem by another subsystem that is
malfunctioning. Furthermore, an unprotected resource cannot defend against
use (or misuse) by an unauthorized or incompetent user.

Question 49

Protection and security require the system to be able to distinguish among
all its users.

Answer 49

Most operating systems maintain a list of user names and associated user identifier (user IDs). In Windows parlance, this is a security ID
(SID). These numerical IDs are unique, one per user. When a user logs in to
the system, the authentication stage determines the appropriate user ID for the
user. That user ID is associated with all of the user’s processes and threads.
When an ID needs to be readable by a user, it is translated back to the user
name via the user name list.
In some circumstances, we wish to distinguish among sets of users rather
than individual users. For example, the owner of a file on a UNIX system may be
allowed to issue all operations on that file, whereas a selected set of users may
be allowed only to read the file. To accomplish this, we need to define a group
name and the set of users belonging to that group. Group functionality can
be implemented as a system-wide list of group names and group identifier .

Question 50

Distributed Systems

Answer 50

A distributed system is a collection of physically separate, possibly heterogeneous computer systems that are networked to provide users with access to
the various resources that the system maintains. Access to a shared resource
increases computation speed, functionality, data availability, and reliability.
Some operating systems generalize network access as a form of file access, with
the details of networking contained in the network interface’s device driver.

Question 51

A network,

Answer 51

in the simplest terms, is a communication path between two or
more systems. Distributed systems depend on networking for their functionality. Networks vary by the protocols used, the distances between nodes, and the
transport media. TCP/IP is the most common network protocol, and it provides
the fundamental architecture of the Internet. Most operating systems support
TCP/IP, including all general-purpose ones. Some systems support proprietary
protocols to suit their needs. For an operating system, it is necessary only that
a network protocol have an interface device—a network adapter, for example
—with a device driver to manage it, as well as software to handle data. These
concepts are discussed throughout this book.
Networks are characterized based on the distances between their nodes.
A local-area network (LAN) connects computers within a room, a building,
or a campus. A wide-area network (WAN) usually links buildings, cities, or
countries. A global company may have a WAN to connect its offices worldwide,
for example. These networks may run one protocol or several protocols. The
continuing advent of new technologies brings about new forms of networks.
For example, a metropolitan-area network (MAN) could link buildings within
a city. BlueTooth and 802.11 devices use wireless technology to communicate
over a distance of several feet, in essence creating a personal-area network
(PAN) between a phone and a headset or a smartphone and a desktop computer.
The media to carry networks are equally varied. They include copper wires,
fiber strands, and wireless transmissions between satellites, microwave dishes,
and radios. When computing devices are connected to cellular phones, they
create a network. Even very short-range infrared communication can be used
for networking. At a rudimentary level, whenever computers communicate,
they use or create a network. These networks also vary in their performance
and reliability.
Some operating systems have taken the concept of networks and distributed systems further than the notion of providing network connectivity.
A network operating system is an operating system that provides features
such as file sharing across the network, along with a communication scheme
that allows different processes on different computers to exchange messages

Question 52

Lists, Stacks, and Queues

Answer 52

An array is a simple data structure in which each element can be accessed
directly. For example, main memory is constructed as an array. If the data item
being stored is larger than one byte, then multiple bytes can be allocated to the
item, and the item is addressed as “item number × item size.” But what about
storing an item whose size may vary? And what about removing an item if the
relative positions of the remaining items must be preserved? In such situations,
arrays give way to other data structures.
After arrays, lists are perhaps the most fundamental data structures in computer science. Whereas each item in an array can be accessed directly, the items
in a list must be accessed in a particular order. That is, a list represents a collection of data values as a sequence. The most common method for implementing
this structure is a linked list, in which items are linked to one another. Linked
lists are of several types:
* In a singly linked list, each item points to its successor, as illustrated in
Figure 1.17.
* In a doubly linked list, a given item can refer either to its predecessor or to
its successor, as illustrated in Figure 1.18.
* In a circularly linked list, the last element in the list refers to the first
element, rather than to null, as illustrated in Figure 1.19.
Linked lists accommodate items of varying sizes and allow easy insertion
and deletion of items. One potential disadvantage of using a list is that performance for retrieving a specified item in a list of size n is linear—O(n), as it
requires potentially traversing all n elements in the worst case. Lists are sometimes used directly by kernel algorithms. Frequently, though, they are used for
constructing more powerful data structures, such as stacks and queues.
A stack is a sequentially ordered data structure that uses the last in, first
out (LIFO) principle for adding and removing items, meaning that the last item
placed onto a stack is the first item removed. The operations for inserting and
removing items from a stack are known as push and pop, respectively. An
operating system often uses a stack when invoking function calls. Parameters,
local variables, and the return address are pushed onto the stack when a
function is called; returning from the function call pops those items off the
stack.
A queue, in contrast, is a sequentially ordered data structure that uses the
first in, first out (FIFO) principle: items are removed from a queue in the order
in which they were inserted. There are many everyday examples of queues,
including shoppers waiting in a checkout line at a store and cars waiting in line
at a traffic signal. Queues are also quite common in operating systems—jobs
that are sent to a printer are typically printed in the order in which they were
submitted, for example. As we shall see in Chapter 5, tasks that are waiting to
be run on an available CPU are often organized in queues.

Question 53

Trees

Answer 53

A tree is a data structure that can be used to represent data hierarchically. Data
values in a tree structure are linked through parent–child relationships. In a
general tree, a parent may have an unlimited number of children. In a binary
tree, a parent may have at most two children, which we term the left child
and the right child. A binary search tree additionally requires an ordering
between the parent’s two children in which left child <= right child. Figure 1.20
provides an example of a binary search tree. When we search for an item in a
binary search tree, the worst-case performance is O(n) (consider how this can
occur). To remedy this situation, we can use an algorithm to create a balanced
binary search tree. Here, a tree containing n items has at most lg n levels, thus
ensuring worst-case performance of O(lg n). We shall see in Section 5.7.1 that
Linux uses a balanced binary search tree (known as a red-black tree) as part
its CPU-scheduling algorithm.

Question 54

Hash Functions and Maps

Answer 54

A hash function takes data as its input, performs a numeric operation on the
data, and returns a numeric value. This numeric value can then be used as
an index into a table (typically an array) to quickly retrieve the data. Whereas
searching for a data item through a list of size n can require up to O(n) comparisons, using a hash function for retrieving data from a table can be as good as
O(1), depending on implementation details. Because of this performance, hash
functions are used extensively in operating systems.

Question 55

A bitmap

Answer 55

is a string of n binary digits that can be used to represent the status of
n items. For example, suppose we have several resources, and the availability
of each resource is indicated by the value of a binary digit: 0 means that the
resource is available, while 1 indicates that it is unavailable (or vice versa).

Question 56

Mobile computing

Answer 56

refers to computing on handheld smartphones and tablet
computers. These devices share the distinguishing physical features of being
portable and lightweight. Historically, compared with desktop and laptop
computers, mobile systems gave up screen size, memory capacity, and overall
functionality in return for handheld mobile access to services such as e-mail
and web browsing. Over the past few years, however, features on mobile
devices have become so rich that the distinction in functionality between, say,
a consumer laptop and a tablet computer may be difficult to discern. In fact,
we might argue that the features of a contemporary mobile device allow it to
provide functionality that is either unavailable or impractical on a desktop or
laptop computer.

Question 57

Client –Server Computing

Answer 57

Contemporary network architecture features arrangements in which server
systems satisfy requests generated by client systems. This form of specialized
distributed system, called a client–server system, has the general structure
depicted in Figure 1.22.
Server systems can be broadly categorized as compute servers and file
servers:
* The compute-server system provides an interface to which a client can
send a request to perform an action (for example, read data). In response,
the server executes the action and sends the results to the client. A server
running a database that responds to client requests for data is an example
of such a system.
* The file-serve system provides a file-system interface where clients can
create, update, read, and delete files. An example of such a system is a
web server that delivers files to clients running web browsers. The actual
contents of the files can vary greatly, ranging from traditional web pages
to rich multimedia content such as high-definition video.

Question 58

Cloud computing

Answer 58

is a type of computing that delivers computing, storage,
and even applications as a service across a network. In some ways, it’s a
logical extension of virtualization, because it uses virtualization as a base for
its functionality. For example, the Amazon Elastic Compute Cloud (ec2) facility
has thousands of servers, millions of virtual machines, and petabytes of storage
available for use by anyone on the Internet. Users pay per month based on
how much of those resources they use. There are actually many types of cloud
computing, including the following:
* Public cloud—a cloud available via the Internet to anyone willing to pay
for the services
* Private cloud—a cloud run by a company for that company’s own use
* Hybrid cloud—a cloud that includes both public and private cloud components
* Software as a service (SaaS)—one or more applications (such as word
processors or spreadsheets) available via the Internet
* Platform as a service (PaaS)—a software stack ready for application use
via the Internet (for example, a database server)
* Infrastructure as a service (IaaS)—servers or storage available over the
Internet (for example, storage available for making backup copies of production data)

Question 59

User interface

Answer 59

Almost all operating systems have a user interface (UI).
This interface can take several forms. Most commonly, a graphical user
interface (GUI) is used. Here, the interface is a window system with a
mouse that serves as a pointing device to direct I/O, choose from menus,
and make selections and a keyboard to enter text. Mobile systems such
as phones and tablets provide a touch-screen interface, enabling users to
slide their fingers across the screen or press buttons on the screen to select
choices. Another option is a command-line interface (CLI), which uses text
commands and a method for entering them (say, a keyboard for typing
in commands in a specific format with specific options). Some systems
provide two or all three of these variations.

Question 60

Program execution

Answer 60

The system must be able to load a program into memory
and to run that program. The program must be able to end its execution,
either normally or abnormally (indicating error).

Question 61

I/O operations

Answer 61

A running program may require I/O, which may involve a
file or an I/O device. For specific devices, special functions may be desired
(such as reading from a network interface or writing to a file system). For
efficiency and protection, users usually cannot control I/O devices directly.
Therefore, the operating system must provide a means to do I/O.

Question 62

File-system manipulation

Answer 62

The file system is of particular interest. Obviously,
programs need to read andwrite files and directories. They also need
to create and delete themby name, search for a given file, and list file information.
Finally, some operating systems include permissions management
to allow or deny access to files or directories based on file ownership. Many
operating systems provide a variety of file systems, sometimes to allow personal choice and sometimes to provide specific features or performance
characteristics.

Question 63

Communications

Answer 63

There are many circumstances in which one process
needs to exchange information with another process. Such communication
may occur between processes that are executing on the same computer
or between processes that are executing on different computer systems
tied together by a network. Communications may be implemented via
shared memory, inwhich two ormore processes read and write to a shared
section of memory, or message passing, inwhich packets of information in
predefined formats are moved between processes by the operating system.

Question 64

Error detection

Answer 64

The operating system needs to be detecting and correcting
errors constantly. Errors may occur in the CPU and memory hardware (such
as a memory error or a power failure), in I/O devices (such as a parity error
on disk, a connection failure on a network, or lack of paper in the printer),
and in the user program (such as an arithmetic overflow or an attempt to
access an illegal memory location). For each type of error, the operating
system should take the appropriate action to ensure correct and consistent
computing. Sometimes, it has no choice but to halt the system. At other
times, it might terminate an error-causing process or return an error code
to a process for the process to detect and possibly correct.

Question 65

Resource allocation

Answer 65

When there are multiple processes running at the
same time, resources must be allocated to each of them. The operating
system manages many different types of resources. Some (such as CPU
cycles, main memory, and file storage) may have special allocation code,
whereas others (such as I/O devices) may havemuchmore general request
and release code. For instance, in determining how best to use the CPU,
operating systems have CPU-scheduling routines that take into account
the speed of the CPU, the process that must be executed, the number of
processing cores on the CPU, and other factors. There may also be routines
to allocate printers, USB storage drives, and other peripheral devices.

Question 66

Logging

Answer 66

We want to keep track of which programs use how much and
what kinds of computer resources. This record keeping may be used for
accounting (so that users can be billed) or simply for accumulating usage
statistics. Usage statistics may be a valuable tool for system administrators
who wish to reconfigure the system to improve computing services.

Question 67

Protection and security

Answer 67

The owners of information stored in a multiuser
or networked computer system may want to control use of that information.
When several separate processes execute concurrently, it should not
be possible for one process to interfere with the others or with the operating
system itself. Protection involves ensuring that all access to system
resources is controlled. Security of the system from outsiders is also important.
Such security starts with requiring each user to authenticate himself or herself to the system, usually by means of a password, to gain access
to system resources. It extends to defending external I/O devices, including
network adapters, from invalid access attempts and recording all such
connections for detection of break-ins. If a system is to be protected and
secure, precautions must be instituted throughout it. A chain is only as
strong as its weakest link.

Question 68

Command Interpreters

Answer 68

Most operating systems, including Linux, UNIX, and Windows, treat the command
interpreter as a special program that is running when a process is initiated
or when a user first logs on (on interactive systems). On systems with
multiple command interpreters to choose from, the interpreters are known as
shells. For example, on UNIX and Linux systems, a user may choose among several
different shells, including the C shell, Bourne-Again shell, Korn shell, and
others. Third-party shells and free user-written shells are also available. Most
shells provide similar functionality, and a user’s choice of which shell to use
is generally based on personal preference. Figure 2.2 shows the Bourne-Again
(or bash) shell command interpreter being used on macOS.
The main function of the command interpreter is to get and execute the next
user-specified command. Many of the commands given at this level manipulate
files: create, delete, list, print, copy, execute, and so on. The various shells
available on UNIX systems operate in this way. These commands can be implemented
in two general ways.

Question 69

Graphical User Interface

Answer 69

A second strategy for interfacing with the operating system is through a user friendly
graphical user interface, or GUI. Here, rather than entering commands
directly via a command-line interface, users employ a mouse-based window and-
menu system characterized by a desktop metaphor. The user moves the
mouse to position its pointer on images, or icons, on the screen (the desktop)
that represent programs, files, directories, and system functions. Depending
on the mouse pointer’s location, clicking a button on the mouse can invoke a
program, select a file or directory—known as a folder—or pull down amenu
that contains commands.

Question 70

Touch-Screen Interface

Answer 70

Because a either a command-line interface or a mouse-and-keyboard system is
impractical for most mobile systems, smartphones and handheld tablet computers
typically use a touch-screen interface. Here, users interact by making
gestures on the touch screen—for example, pressing and swiping fingers
across the screen. Although earlier smartphones included a physical keyboard,
most smartphones and tablets now simulate a keyboard on the touch screen.
Figure 2.3 illustrates the touch screen of the Apple iPhone. Both the iPad and
the iPhone use the Springboard touch-screen interface.

Question 71

Choice of Interface

Answer 71

The choice of whether to use a command-line or GUI interface is mostly
one of personal preference. System administrators who manage computers
and power users who have deep knowledge of a system frequently use the command-line interface. For them, it ismore efficient, giving them faster access
to the activities they need to perform. Indeed, on some systems, only a subset
of system functions is available via the GUI, leaving the less common tasks
to those who are command-line knowledgeable. Further, command-line interfaces
usually make repetitive tasks easier, in part because they have their own
programmability. For example, if a frequent task requires a set of commandline
steps, those steps can be recorded into a file, and that file can be run
just like a program. The program is not compiled into executable code but
rather is interpreted by the command-line interface. These shell scripts are
very common on systems that are command-line oriented, such as UNIX and
Linux.
In contrast, most Windows users are happy to use the Windows GUI environment
and almost never use the shell interface. Recent versions of the Windows
operating system provide both a standard GUI for desktop and traditional
laptops and a touch screen for tablets. The various changes undergone
by the Macintosh operating systems also provide a nice study in contrast. Historically,
Mac OS has not provided a command-line interface, always requiring
its users to interfacewith the operating system using its GUI.However,with the
release of macOS (which is in part implemented using a UNIX kernel), the operating
system now provides both an Aqua GUI and a command-line interface.
Figure 2.4 is a screenshot of the macOS GUI.
Although there are apps that provide a command-line interface for iOS
and Android mobile systems, they are rarely used. Instead, almost all users
of mobile systems interact with their devices using the touch-screen interface.

Question 72

System calls

Answer 72

provide an interface to the services made available by an operating
system. These calls are generally available as functions written in C and
C++, although certain low-level tasks (for example, tasks where hardware
must be accessed directly) may have to be written using assembly-language
instructions.

Question 73

Application Programming Interface

Answer 73

As you can see, even simple programs may make heavy use of the operating
system. Frequently, systems execute thousands of system calls per second.
Most programmers never see this level of detail, however. Typically, application
developers design programs according to an application programming
interface (API). The API specifies a set of functions that are available to an application
programmer, including the parameters that are passed to each function
and the return values the programmer can expect. Three of the most common
APIs available to application programmers are the Windows API for Windows
systems, the POSIX API for POSIX-based systems (which include virtually all
versions of UNIX, Linux, and macOS), and the Java API for programs that run
on the Java virtual machine.Aprogrammer accesses an API via a library of code
provided by the operating system. In the case of UNIX and Linux for programs
written in the C language, the library is called libc. Note that—unless specified
—the system-call names used throughout this text are generic examples. Each
operating system has its own name for each system call.
Behind the scenes, the functions that make up an API typically invoke the
actual system calls on behalf of the application programmer. For example, the
Windows function CreateProcess() (which, unsurprisingly, is used to create a new process) actually invokes the NTCreateProcess() system call in the
Windows kernel.

Question 74

run-time environment
(RTE)

Answer 74

the full suite of software needed to execute applications written
in a given programming language, including its compilers or interpreters
as well as other software, such as libraries and loaders. The RTE provides a system-call interface that serves as the link to system calls made available
by the operating system. The system-call interface intercepts function calls in
the API and invokes the necessary system calls within the operating system.
Typically, a number is associated with each system call, and the system-call
interface maintains a table indexed according to these numbers. The system call
interface then invokes the intended system call in the operating-system
kernel and returns the status of the system call.

Question 75

used. If there are more than five parameters, the block method is
used.

Answer 75

Parameters also can be placed, or pushed, onto a stack by the program
and popped off the stack by the operating system. Some operating systems
prefer the block or stack method because those approaches do not limit the
number or length of parameters being passed.

Question 76

System calls can be grouped roughly into six major categories: process control,
fill management, device management, information maintenance, communications,
and protection.

Answer 76

Below,we briefly discuss the types of system calls that
may be provided by an operating system. Most of these system calls support,
or are supported by, concepts and functions that are discussed in later chapters.
Figure 2.8 summarizes the types of system calls normally provided by an
operating system. As mentioned, in this text, we normally refer to the system
calls by generic names. Throughout the text, however, we provide examples
of the actual counterparts to the system calls for UNIX, Linux, and Windows
systems.

Question 77

Process Control

Answer 77

A running program needs to be able to halt its execution either normally
(end()) or abnormally (abort()). If a system call is made to terminate the
currently running program abnormally, or if the program runs into a problem
and causes an error trap, a dump of memory is sometimes taken and an
error message generated. The dump is written to a special log file on disk
and may be examined by a debugger—a system program designed to aid
the programmer in finding and correcting errors, or bugs—to determine the
cause of the problem. Under either normal or abnormal circumstances, the
operating system must transfer control to the invoking command interpreter.
The command interpreter then reads the next command. In an interactive
system, the command interpreter simply continues with the next command;
it is assumed that the user will issue an appropriate command to respond to any error. In a GUI system, a pop-up window might alert the user to the error
and ask for guidance. Some systems may allow for special recovery actions in
case an error occurs. If the program discovers an error in its input and wants
to terminate abnormally, it may also want to define an error level.More severe
errors can be indicated by a higher-level error parameter. It is then possible to
combine normal and abnormal termination by defining a normal termination
as an error at level 0. The command interpreter or a following program can use
this error level to determine the next action automatically.
A process executing one program may want to load() and execute()
another program. This feature allows the command interpreter to execute a
program as directed by, for example, a user command or the click of a mouse.
An interesting question is where to return control when the loaded program
terminates. This question is related to whether the existing program is lost,
saved, or allowed to continue execution concurrently with the new program.

Question 78

boot loader

Answer 78

The standard Arduino platform does not provide an operating system; instead,
a small piece of software known as a boot loader loads the sketch into a specific
region in the Arduino’s memory (Figure 2.9). Once the sketch has been loaded,
it begins running, waiting for the events that it is programmed to respond to.
For example, if the Arduino’s temperature sensor detects that the temperature
has exceeded a certain threshold, the sketch may have the Arduino start the
motor for a fan. An Arduino is considered a single-tasking system, as only
one sketch can be present in memory at a time; if another sketch is loaded,
it replaces the existing sketch. Furthermore, the Arduino provides no user
interface beyond hardware input sensors.

Question 79

Information Maintenance

Answer 79

Many system calls exist simply for the purpose of transferring information
between the user program and the operating system. For example, most systems
have a system call to return the current time() and date().Other system
calls may return information about the system, such as the version number of
the operating system, the amount of free memory or disk space, and so on.
Another set of system calls is helpful in debugging a program. Many
systems provide system calls to dump() memory. This provision is useful for
debugging. The program strace, which is available on Linux systems, lists
each system call as it is executed. Even microprocessors provide a CPU mode,
known as single step, in which a trap is executed by the CPU after every
instruction. The trap is usually caught by a debugger.
Many operating systems provide a time profile of a program to indicate
the amount of time that the program executes at a particular location or set
of locations. A time profile requires either a tracing facility or regular timer
interrupts.At every occurrence of the timer interrupt, the value of the program
counter is recorded. With sufficiently frequent timer interrupts, a statistical
picture of the time spent on various parts of the program can be obtained.
In addition, the operating system keeps information about all its processes,
and system calls are used to access this information. Generally, calls are also
used to get and set the process information (get process attributes() and
set process attributes()). In Section 3.1.3, we discuss what information is
normally kept.

Question 80

There are two common models of interprocess communication: the messagepassing
model and the shared-memory model

Answer 80

In the message-passing model,
the communicating processes exchange messages with one another to transfer information. Messages can be exchanged between the processes either
directly or indirectly through a common mailbox. Before communication can
take place, a connection must be opened. The name of the other communicator
must be known, be it another process on the same system or a process on
another computer connected by a communications network. Each computer in
a network has a host name by which it is commonly known. Ahost also has a
network identifier, such as an IP address. Similarly, each process has a process
name, and this name is translated into an identifier by which the operating
system can refer to the process. The get hostid() and get processid()
system calls do this translation. The identifiers are then passed to the generalpurpose
open() and close() calls provided by the file system or to specific
open connection() and close connection() system calls, depending on
the system’s model of communication. The recipient process usually must give
its permission for communication to take placewith an accept connection()
call. Most processes thatwill be receiving connections are special-purpose daemons,
which are system programs provided for that purpose. They execute a
wait for connection() call and are awakened when a connection is made.
The source of the communication, known as the client, and the receiving daemon,
known as a server, then exchange messages by using read message()
and write message() system calls. The close connection() call terminates
the communication.
In the shared-memory model, processes use shared memory create()
and shared memory attach() system calls to create and gain access to regions
of memory owned by other processes. 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 is determined by the processes and
is not under the operating system’s control. The processes are also responsible
for ensuring that they are notwriting to the same location simultaneously. Such
mechanisms are discussed in Chapter 6. In Chapter 4, we look at a variation of
the process scheme—threads—in which some memory is shared by default.
Both of the models just discussed are common in operating systems,
and most systems implement both. Message passing is useful for exchanging
smaller amounts of data, because no conflicts need be avoided. It is also easier
to implement than is shared memory for inter computer communication.
Shared memory allows maximum speed and convenience of communication,
since it can be done at memory transfer speeds when it takes place within a
computer. Problems exist, however, in the areas of protection and synchronization
between the processes sharing memory.

Question 81

File management

Answer 81

These programs create, delete, copy, rename, print, list,
and generally access and manipulate files and directories.

Question 82

Status information.

Answer 82

Some programs simply ask the system for the date,
time, amount of available memory or disk space, number of users, or
similar status information. Others are more complex, providing detailed
performance, logging, and debugging information. Typically, these programs
format and print the output to the terminal or other output devices
or files or display it in a window of the GUI. Some systems also support a
registry, which is used to store and retrieve configuration information.

Question 83

File modificatio

Answer 83

Several text editors may be available to create and modify
the content of files stored on disk or other storage devices. There may
also be special commands to search contents of files or perform transformations
of the text.

Question 84

Programming-language support.

Answer 84

Compilers, assemblers, debuggers, and
interpreters for common programming languages (such as C, C++, Java,
and Python) are often provided with the operating system or available as
a separate download.

Question 85

Program loading and execution.

Answer 85

Once a program is assembled or compiled,
it must be loaded into memory to be executed. The system may
provide absolute loaders, relocatable loaders, linkage editors, and overlay
loaders. Debugging systems for either higher-level languages or machine
language are needed as well.

Question 86

Communications.

Answer 86

These programs provide the mechanism for creating
virtual connections among processes, users, and computer systems. They
allow users to send messages to one another’s screens, to browse web
pages, to send e-mail messages, to log in remotely, or to transfer files from
one machine to another.

Question 87

Background services.

Answer 87

All general-purpose systems have methods for
launching certain system-program processes at boot time. Some of these
processes terminate after completing their tasks, while others continue to run until the system is halted. Constantly running system-program processes
are known as services, subsystems, or daemons. One example is
the network daemon discussed in Section 2.3.3.5. In that example, a system
needed a service to listen for network connections in order to connect
those requests to the correct processes. Other examples include process
schedulers that start processes according to a specified schedule, system
error monitoring services, and print servers. Typical systems have dozens
of daemons. In addition, operating systems that run important activities in
user context rather than in kernel context may use daemons to run these
activities.

Question 88

linker

Answer 88

Source files are compiled into object files that are designed to be loaded
into any physical memory location, a format known as an relocatable object
fil . Next, the linker combines these relocatable object files into a single binary
executable file. During the linking phase, other object files or libraries may be
included as well, such as the standard C or math library (specifiedwith the flag
-lm).

Question 89

loader

Answer 89

Aloader is used to load the binary executable file into memory, where it is
eligible to run on a CPU core. An activity associated with linking and loading
is relocation, which assigns final addresses to the program parts and adjusts
code and data in the program to match those addresses so that, for example, the
code can call library functions and access its variables as it executes. In Figure
2.11,we see that to run the loader, all that is necessary is to enter the name of the
executable file on the command line. When a program name is entered on the command line on UNIX systems—for example, ./main—the shell first creates
a new process to run the program using the fork() system call. The shell then
invokes the loader with the exec() system call, passing exec() the name of
the executable file. The loader then loads the specified program into memory
using the address space of the newly created process. (When a GUI interface is
used, double-clicking on the icon associated with the executable file invokes
the loader using a similar mechanism.)
The process described thus far assumes that all libraries are linked into
the executable file and loaded into memory. In reality, most systems allow
a program to dynamically link libraries as the program is loaded. Windows,
for instance, supports dynamically linked libraries (DLLs). The benefit of this
approach is that it avoids linking and loading libraries that may end up not
being used into an executable file. Instead, the library is conditionally linked
and is loaded if it is required during program run time. For example, in Figure
2.11, the math library is not linked into the executable file main. Rather, the
linker inserts relocation information that allows it to be dynamically linked
and loaded as the program is loaded. We shall see in Chapter 9 that it is
possible for multiple processes to share dynamically linked libraries, resulting
in a significant savings in memory use.

Question 90

ELF FORMAT

Answer 90

Linux provides various commands to identify and evaluate ELF files. For
example, the file command determines a file type. If main.o is an object
file, and main is an executable file, the command
file main.o
will report that main.o is an ELF relocatable file, while the command
file main
will report that main is an ELF executable. ELF files are divided into a number
of sections and can be evaluated using the readelf command.

Question 91

An application can be made available to run on multiple operating systems
in one of three ways:

Answer 91

1. The application can be written in an interpreted language (such as Python
   or Ruby) that has an interpreter available for multiple operating systems.
   The interpreter reads each line of the source program, executes equivalent
   instructions on the native instruction set, and calls native operating system
   calls. Performance suffers relative to that for native applications, and
   the interpreter provides only a subset of each operating system’s features,
   possibly limiting the feature sets of the associated applications.
2. The application can be written in a language that includes a virtual
   machine containing the running application. The virtual machine is part
   of the language’s full RTE.One example of this method is Java. Java has an
   RTE that includes a loader, byte-code verifier, and other components that
   load the Java application into the Java virtual machine. This RTE has been ported, or developed, for many operating systems, from mainframes to
   smartphones, and in theory any Java app can runwithin the RTEwherever
   it is available. Systems of this kind have disadvantages similar to those
   of interpreters, discussed above.
3. The application developer can use a standard language or API in which
   the compiler generates binaries in a machine- and operating-system specific
   language. The application must be ported to each operating system
   on which it will run. This porting can be quite time consuming and
   must be done for each new version of the application, with subsequent
   testing and debugging. Perhaps the best-known example is the POSIX
   API and its set of standards for maintaining source-code compatibility
   between different variants of UNIX-like operating systems.

Question 92

At the
application level, the libraries provided with the operating system contain APIs
to provide features like GUI interfaces, and an application designed to call one
set of APIs (say, those available from iOS on the Apple iPhone) will not work on
an operating system that does not provide those APIs (such as Android). Other
challenges exist at lower levels in the system, including the following.

Answer 92

Each operating system has a binary format for applications that dictates
the layout of the header, instructions, and variables. Those components
need to be at certain locations in specified structures within an executable
file so the operating system can open the file and load the application for
proper execution.
* CPUs have varying instruction sets, and only applications containing the
appropriate instructions can execute correctly.
* Operating systems provide system calls that allow applications to request
various activities, such as creating files and opening network connections.
Those system calls vary among operating systems in many respects,
including the specific operands and operand ordering used, how an application
invokes the system calls, their numbering and number, their meanings,
and their return of results.

Question 93

issues of same apps on different systems

Answer 93

• Each operating system has a binary format for applications that dictates
  the layout of the header, instructions, and variables. Those components
  need to be at certain locations in specified structures within an executable
  file so the operating system can open the file and load the application for
  proper execution.
• CPUs have varying instruction sets, and only applications containing the
  appropriate instructions can execute correctly.
• Operating systems provide system calls that allow applications to request
  various activities, such as creating files and opening network connections.
  Those system calls vary among operating systems in many respects,
  including the specific operands and operand ordering used, how an application
  invokes the system calls, their numbering and number, their meanings,
  and their return of results.

Question 94

application binary interface (ABI)

Answer 94

is used to define
how different components of binary code can interface for a given operating
system on a given architecture. An ABI specifies low-level details, including
addresswidth, methods of passing parameters to system calls, the organization of the run-time stack, the binary format of system libraries, and the size of data
types, just to name a few. Typically, an ABI is specified for a given architecture
(for example, there is an ABI for the ARMv8 processor). Thus, an ABI is the
architecture-level equivalent of an API. If a binary executable file has been
compiled and linked according to a particular ABI, it should be able to run on
different systems that support that ABI. However, because a particular ABI is
defined for a certain operating system running on a given architecture, ABIs do
little to provide cross-platform compatibility.

Question 95

Design Goals

Answer 95

The first problem in designing a system is to define goals and specifications. At
the highest level, the design of the system will be affected by the choice of hardware
and the type of system: traditional desktop/laptop, mobile, distributed,
or real time.
Beyond this highest design level, the requirements may be much harder to
specify. The requirements can, however, be divided into two basic groups: user
goals and system goals.

Question 96

Mechanisms and Policies

Answer 96

One important principle is the separation of policy from mechanism. Mechanisms
determine how to do something; policies determine what will be done.
For example, the timer construct (see Section 1.4.3) is a mechanism for ensuring
CPU protection, but deciding how long the timer is to be set for a particular user
is a policy decision.
The separation of policy and mechanism is important for flexibility. Policies
are likely to change across places or over time. In the worst case, each change
in policy would require a change in the underlying mechanism. A general
mechanism flexible enough to work across a range of policies is preferable.
A change in policy would then require redefinition of only certain parameters
of the system. For instance, consider a mechanism for giving priority to certain
types of programs over others. If the mechanism is properly separated from
policy, it can be used either to support a policy decision that I/O-intensive
programs should have priority over CPU-intensive ones or to support the
opposite policy.

Question 97

Implementation

Answer 97

Once an operating system is designed, it must be implemented. Because operating
systems are collections of many programs, written by many people over
a long period of time, it is difficult to make general statements about how they
are implemented.
Early operating systems were written in assembly language. Now, most
are written in higher-level languages such as C or C++, with small amounts of the system written in assembly language. In fact, more than one higherlevel
language is often used. The lowest levels of the kernel might be written
in assembly language and C. Higher-level routines might be written in C and
C++, and system libraries might be written in C++ or even higher-level languages.
Android provides a nice example: its kernel is writtenmostly in C with
some assembly language. Most Android system libraries are written in C or
C++, and its application frameworks—which provide the developer interface
to the system—are written mostly in Java.We cover Android’s architecture in
more detail in Section 2.8.5.2.
The advantages of using a higher-level language, or at least a systemsimplementation
language, for implementing operating systems are the same
as those gained when the language is used for application programs: the code
can be written faster, is more compact, and is easier to understand and debug.
In addition, improvements in compiler technology will improve the generated
code for the entire operating system by simple recompilation. Finally,
an operating system is far easier to port to other hardware if it is written in
a higher-level language. This is particularly important for operating systems
that are intended to run on several different hardware systems, such as small
embedded devices, Intel x86 systems, and ARM chips running on phones and
tablets.
The only possible disadvantages of implementing an operating system in a
higher-level language are reduced speed and increased storage requirements.
This, however, is not a major issue in today’s systems. Although an expert
assembly-language programmer can produce efficient small routines, for large
programs a modern compiler can perform complex analysis and apply sophisticated
optimizations that produce excellent code. Modern processors have
deep pipelining and multiple functional units that can handle the details of
complex dependencies much more easily than can the human mind.

Question 98

Monolithic Structure

Answer 98

The simplest structure for organizing an operating system is no structure at all.
That is, place all of the functionality of the kernel into a single, static binary file
that runs in a single address space. This approach—known as a monolithic
structure—is a common technique for designing operating systems.
An example of such limited structuring is the original UNIX operating
system, which consists of two separable parts: the kernel and the system
programs. The kernel is further separated into a series of interfaces and device
drivers, which have been added and expanded over the years as UNIX has
evolved. We can view the traditional UNIX operating system as being layered
to some extent, as shown in Figure 2.12. Everything below the system-call
interface and above the physical hardware is the kernel. The kernel provides
the file system, CPU scheduling, memory management, and other operatingsystem
functions through system calls. Taken in sum, that is an enormous
amount of functionality to be combined into one single address space.

Question 99

Layered Approach

Answer 99

The monolithic approach is often known as a tightly coupled system because
changes to one part of the system can have wide-ranging effects on other parts.
Alternatively, we could design a loosely coupled system. Such a system is
divided into separate, smaller components that have specific and limited functionality.
All these components together comprise the kernel. The advantage
of this modular approach is that changes in one component affect only that
component, and no others, allowing system implementers more freedom in
creating and changing the inner workings of the system.
Asystem can be made modular in many ways. One method is the layered
approach, in which the operating system is broken into a number of layers
(levels). The bottom layer (layer 0) is the hardware; the highest (layer N) is the
user interface. This layering structure is depicted in Figure 2.14.
An operating-system layer is an implementation of an abstract object made
up of data and the operations that can manipulate those data. A typical
operating-system layer—say, layer M—consists of data structures and a set
of functions that can be invoked by higher-level layers. Layer M, in turn, can
invoke operations on lower-level layers.
The main advantage of the layered approach is simplicity of construction
and debugging. The layers are selected so that each uses functions (operations) Nevertheless, relatively few operating systems
use a pure layered approach. One reason involves the challenges of
appropriately defining the functionality of each layer. In addition, the overall
performance of such systems is poor due to the overhead of requiring a user
program to traverse through multiple layers to obtain an operating-system service.
Some layering is common in contemporary operating systems, however.
Generally, these systems have fewer layers with more functionality, providing
most of the advantages of modularized code while avoiding the problems of
layer definition and interaction.

Question 100

Microkernels

Answer 100

In the mid-1980s, researchers at Carnegie Mellon University developed an
operating system called Mach that modularized the kernel using the microkernel
approach. This method structures the operating system by removing all nonessential components from the kernel and implementing them as userlevel
programs that reside in separate address spaces. The result is a smaller
kernel. There is little consensus regarding which services should remain in the
kernel and which should be implemented in user space. Typically, however,
microkernels provide minimal process and memory management, in addition
to a communication facility. Figure 2.15 illustrates the architecture of a typical
microkernel.
The main function of the microkernel is to provide communication
between the client program and the various services that are also running in
user space. Communication is provided through message passing, which was
described in Section 2.3.3.5. For example, if the client programwishes to access
a file, itmust interact with the file server. The client program and service never
interact directly. Rather, they communicate indirectly by exchanging messages
with the microkernel.
One benefit of the microkernel approach is that it makes extending the
operating system easier. All new services are added to user space and consequently
do not require modification of the kernel. When the kernel does have to
be modified, the changes tend to be fewer, because the microkernel is a smaller
kernel. The resulting operating system is easier to port from one hardware
design to another. The microkernel also provides more security and reliability,
since most services are running as user—rather than kernel—processes. If a
service fails, the rest of the operating system remains untouched.

Question 101

Modules

Answer 101

Perhaps the best current methodology for operating-system design involves
using loadable kernel modules (LKMs). Here, the kernel has a set of core
components and can link in additional services via modules, either at boot time
or during run time. This type of design is common in modern implementations
of UNIX, such as Linux, macOS, and Solaris, as well as Windows.
The idea of the design is for the kernel to provide core services, while
other services are implemented dynamically, as the kernel is running. Linking
services dynamically is preferable to adding newfeatures directly to the kernel,
which would require recompiling the kernel every time a change was made.
Thus, for example, we might build CPU scheduling and memory management
algorithms directly into the kernel and then add support for different file
systems by way of loadable modules.
The overall result resembles a layered system in that each kernel section
has defined, protected interfaces; but it is more flexible than a layered system,
because any module can call any other module. The approach is also similar to
the microkernel approach in that the primary module has only core functions
and knowledge of how to load and communicate with other modules; but it
is more efficient, because modules do not need to invoke message passing in
order to communicate.

Question 102

Hybrid Systems

Answer 102

In practice, very few operating systems adopt a single, strictly defined structure.
Instead, they combine different structures, resulting in hybrid systems
that address performance, security, and usability issues. For example, Linux
is monolithic, because having the operating system in a single address space
provides very efficient performance. However, it also modular, so that new
functionality can be dynamically added to the kernel. Windows is largely monolithic as well (again primarily for performance reasons), but it retains
some behavior typical of microkernel systems, including providing support
for separate subsystems (known as operating-system personalities) that run as
user-mode processes.Windows systems also provide support for dynamically
loadable kernel modules. We provide case studies of Linux and Windows 10
in Chapter 20 and Chapter 21, respectively. In the remainder of this section,
we explore the structure of three hybrid systems: the Apple macOS operating
system and the two most prominent mobile operating systems—iOS and
Android.

Question 103

macOS and iOS

Answer 103

User experience layer. This layer defines the software interface that allows
users to interact with the computing devices. macOS uses the Aqua user
interface, which is designed for a mouse or trackpad, whereas iOS uses the
Springboard user interface, which is designed for touch devices.
* Application frameworks layer. This layer includes the Cocoa and Cocoa
Touch frameworks, which provide an API for the Objective-C and Swift
programming languages. The primary difference between Cocoa and
Cocoa Touch is that the former is used for developing macOS applications,
and the latter by iOS to provide support for hardware features unique to
mobile devices, such as touch screens.
* Core frameworks. This layer defines frameworks that support graphics
and media including, Quicktime and OpenGL.
Kernel environment. This environment, also known as Darwin, includes
the Mach microkernel and the BSD UNIX kernel. We will elaborate on
Darwin shortly.

Question 104

Some significant distinctions between macOS and iOS include the following:

Answer 104

Because macOS is intended for desktop and laptop computer systems, it is
compiled to run on Intel architectures. iOS is designed for mobile devices
and thus is compiled for ARM-based architectures. Similarly, the iOS kernel
has been modified somewhat to address specific features and needs
of mobile systems, such as power management and aggressive memory
management. Additionally, iOS has more stringent security settings than
macOS.
* The iOS operating system is generally much more restricted to developers
than macOS and may even be closed to developers. For example, iOS
restricts access to POSIX and BSD APIs on iOS, whereas they are openly
available to developers on macOS.

Question 105

Operating-System Debugging

Answer 105

We have mentioned debugging from time to time in this chapter. Here,we take
a closer look. Broadly, debugging is the activity of finding and fixing errors
in a system, both in hardware and in software. Performance problems are
considered bugs, so debugging can also include performance tuning, which
seeks to improve performance by removing processing bottlenecks. In this
section, we explore debugging process and kernel errors and performance
problems. Hardware debugging is outside the scope of this text.

Question 106

Failure Analysis

Answer 106

If a process fails, most operating systems write the error information to a log
fil to alert system administrators or users that the problem occurred. The
operating system can also take a core dump—a capture of the memory of the
process—and store it in a file for later analysis. (Memorywas referred to as the “core” in the early days of computing.) Running programs and core dumps can
be probed by a debugger, which allows a programmer to explore the code and
memory of a process at the time of failure.
Debugging user-level process code is a challenge. Operating-system kernel
debugging is even more complex because of the size and complexity of the
kernel, its control of the hardware, and the lack of user-level debugging tools.
Afailure in the kernel is called a crash.When a crash occurs, error information
is saved to a log file, and the memory state is saved to a crash dump.
Operating-system debugging and process debugging frequently use different
tools and techniques due to the very different nature of these two tasks.
Consider that a kernel failure in the file-system code would make it risky for
the kernel to try to save its state to a file on the file system before rebooting.

Question 107

Counters

Answer 107

Operating systems keep track of system activity through a series of counters,
such as the number of system calls made or the number of operations
performed to a network device or disk. The following are examples of Linux
tools that use counters:
Per-Process
* ps—reports information for a single process or selection of processes
* top—reports real-time statistics for current processes
System-Wide
* vmstat—reports memory-usage statistics
* netstat—reports statistics for network interfaces
* iostat—reports I/O usage for disks

Question 108

Tracing

Answer 108

Whereas counter-based tools simply inquire on the current value of certain
statistics that are maintained by the kernel, tracing tools collect data for a
specific event—such as the steps involved in a system-call invocation.
The following are examples of Linux tools that trace events:
Per-Process
* strace—traces system calls invoked by a process
* gdb—a source-level debugger
System-Wide
* perf—a collection of Linux performance tools
* tcpdump—collects network packets Making operating systems easier to understand, debug, and tune as they
run is an active area of research and practice. A new generation of kernelenabled
performance analysis tools has made significant improvements in how
this goal can be achieved. Next, we discuss BCC, a toolkit for dynamic kernel
tracing in Linux.

Question 109

BCC

Answer 109

is a rich toolkit that provides tracing features
for Linux systems. BCC is a front-end interface to the eBPF (extended
Berkeley Packet Filter) tool. The BPF technology was developed in the early
1990s for filtering traffic across a computer network. The “extended” BPF (eBPF)
added various features to BPF. eBPF programs are written in a subset of C and
are compiled into eBPF instructions, which can be dynamically inserted into a
running Linux system. The eBPF instructions can be used to capture specific
events (such as a certain system call being invoked) or to monitor system performance
(such as the time required to perform disk I/O). To ensure that eBPF
instructions are well behaved, they are passed through a verifie before being
inserted into the running Linux kernel. The verifier checks to make sure that
the instructions do not affect system performance or security.
Although eBPF provides a rich set of features for tracing within the Linux
kernel, it traditionally has been very difficult to develop programs using its
C interface. BCC was developed to make it easier to write tools using eBPF by
providing a front-end interface in Python. ABCC tool is written in Python and
it embeds C code that interfaces with the eBPF instrumentation, which in turn
interfaces with the kernel. The BCC tool also compiles the C program into eBPF
instructions and inserts it into the kernel using either probes or tracepoints,
two techniques that allow tracing events in the Linux kernel.

Question 110

What makes BCC especially powerful

Answer 110

is that its tools can be used on
live production systems that are running critical applications without causing
harm to the system. This is particularly useful for system administrators who
must monitor system performance to identify possible bottlenecks or security
exploits. Figure 2.20 illustrates the wide range of tools currently provided by
BCC and eBPF and their ability to trace essentially any area of the Linux operating
system. BCC is a rapidly changing technology with new features constantly
being added.
2.11 Summary