Chapter 1 Flashcards
1
Q
An operating system is
A
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.
2
Q
kernel
A
is a core component of an operating system and serves as the main interface between the computer’s physical hardware and the processes running on it. The kernel enables multiple applications to share hardware resources by providing access to CPU, memory, disk I/O, and networking.
3
Q
system
programs
A
are associated with the operating system but are not necessarily part of the kernel, and application programs, which include all programs
not associated with the operation of the system
4
Q
middleware
A
a set of software frameworks that provide additional
services to application developers.
5
Q
A modern general-purpose computer system consists of
A
consists of one or more CPUs and
a number of device controllers connected through a common bus that provides
access between components and shared memory (Figure 1.2). Each device
controller is in charge of a specific type of device (for example, a disk drive,
audio device, or graphics display). Depending on the controller, more than one
device may be attached. For instance, one system USB port can connect to a
USB hub, to which several devices can connect. A device controller maintains
some local buffer storage and a set of special-purpose registers. The device
controller is responsible for moving the data between the peripheral devices
that it controls and its local buffer storage.
6
Q
Typically, operating systems have a device driver
A
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.
7
Q
Interrupts
A
Consider a typical computer operation: a program performing I/O. To start an
I/O operation, the device driver loads the appropriate registers in the device
controller. The device controller, in turn, examines the contents of these registers to determine what action to take (such as “read a character from the
keyboard”). The controller starts the transfer of data from the device to its local
buffer. Once the transfer of data is complete, the device controller informs the
device driver that it has finished its operation. The device driver then gives
control to other parts of the operating system, possibly returning the data or a
pointer to the data if the operation was a read. For other operations, the device
driver returns status information such as “write completed successfully” or
“device busy”. But how does the controller inform the device driver that it has
finished its operation? This is accomplished via an interrupt.
8
Q
Hardware may trigger an interrupt at any time by
A
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.
9
Q
interrupts must be handled
quickly
A
as they occur very frequently. A table of pointers to interrupt routines
can be used instead to provide the necessary speed. The interrupt routine
is 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 as Windows and UNIX dispatch interrupts in this manner.
The interrupt architecture must also save the state information of whatever
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.
10
Q
interrupt-request line, interrupt implementation
A
The basic interrupt mechanism works as follows. The CPU hardware has a
wire called the interrupt-request line that the CPU senses after executing every
instruction. When the CPU detects that a controller has asserted a signal on
the interrupt-request line, it reads the interrupt number and jumps to the
interrupt-handler routine by using that interrupt number as an index into
the interrupt vector. It then starts execution at the address associated with
that index. The interrupt handler saves any state it will be changing during
its operation, determines the cause of the interrupt, performs the necessary
processing, performs a state restore, and executes a return from interrupt
instruction to return the CPU to the execution state prior to the interrupt. 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.
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.
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.
In modern computer hardware, these three features are provided by the CPU
and the interrupt-controller hardware.
11
Q
Most CPUs have two interrupt request lines
A
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.
Recall that the purpose of a vectored interrupt mechanism is to reduce the
need for a single interrupt handler to search all possible sources of interrupts
to determine which one needs service. In practice, however, computers have
more devices (and, hence, interrupt handlers) than they have address elements
in the interrupt vector. A common way to solve this problem is to use interrupt
chaining, 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.
Figure 1.5 illustrates the design of the interrupt vector for Intel processors.
The events from 0 to 31, which are nonmaskable, are used to signal various
error conditions. The events from 32 to 255, which are maskable, are used for
purposes such as device-generated interrupts.
12
Q
interrupt priority
levels
A
The interrupt mechanism also implements a system of interrupt priority
levels. These levels enable the CPU to defer the handling of low-priority interrupts without masking all interrupts and makes it possible for a high-priority
interrupt to preempt the execution of a low-priority interrupt.
In summary, interrupts are used throughout modern operating systems to
handle asynchronous events (and for other purposes we will discuss throughout the text). Device controllers and hardware faults raise interrupts. To enable
the most urgent work to be done first, modern computers use a system of
interrupt priorities. Because interrupts are used so heavily for time-sensitive
processing, efficient interrupt handling is required for good system performance.
13
Q
Main memory commonly is implemented in
a semiconductor technology called
A
dynamic random-access memory (DRAM).
14
Q
the first program to run on computer power-on is
A
s a bootstrap program, which then loads
the operating system. Since RAM is volatile—loses its content when power
is turned off or otherwise lost—we cannot trust it to hold the bootstrap program
15
Q
RAM is volatile
A
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.
16
Q
STORAGE DEFINITIONS AND NOTATION
A
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).
17
Q
All forms of memory provide
A
an array of bytes. Each byte has its own
address. Interaction is achieved through a sequence of load or store instructions to specific memory addresses. The load instruction moves a byte or word
from main memory to an internal register within the CPU, whereas the store
instruction moves the content of a register to main memory. Aside from explicit
loads and stores, the CPU automatically loads instructions from main memory
for execution from the location stored in the program counter.
18
Q
A typical instruction–execution cycle, as executed on a system with a von
Neumann architecture
A
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.
19
Q
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:
A
- Main memory is usually too small to store all needed programs and data
permanently. - Main memory, as mentioned, is volatile—it loses its contents when power
is turned off or otherwise lost
20
Q
most computer systems provide
A
secondary storage as an extension of
main memory. The main requirement for secondary storage is that it be able to
hold large quantities of data permanently.
21
Q
The most common secondary-storage devices are
A
the 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. Hence, the proper
management of secondary storage is of central importance to a computer system
22
Q
The top four levels of memory in the figure are constructed using semiconductor memory
A
, 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.
23
Q
The vast majority of the time we spend on non volatile storage will
be on secondary storage. This type of storage can be classified into two
distinct types:
A
◦ 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.
24
Q
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.
A
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.
25
multiprocessor systems
s 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.
26
The most common multiprocessor systems use
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.
27
The definition of multiprocessor has evolved over time and now includes
multicore systems
, 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.
In addition, one chip with multiple cores uses significantly less power than
multiple single-core chips, an important issue for mobile devices as well as
laptops.
In Figure 1.9, we show a dual-core design with two cores on the same processor chip. In this design, each core has its own register set, as well as its own
local cache, often known as a level 1, or L1, cache. Notice, too, that a level 2 (L2)
cache is local to the chip but is shared by the two processing cores. Most architectures adopt this approach, combining local and shared caches, where local,
lower-level caches are generally smaller and faster than higher-level shared caches.
28
DEFINITIONS OF COMPUTER SYSTEM COMPONENTS
* 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.
29
Adding additional CPUs to a multiprocessor system 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.
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.
30
blade servers
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 blade processor 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.
31
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.
32
Clustering is usually used to provide high-availability service—
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.
Clustering can be structured asymmetrically or symmetrically. 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
33
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.
Since a cluster consists of several computer systems connected via a network, clusters can also be used to provide high-performance computing environments. Such systems can supply significantly greater computational power
than single-processor or even SMP systems because they can run an application
concurrently on all computers in the cluster. The application must have been
written specifically to take advantage of the cluster, however. This involves a
technique known as parallelization, which divides a program into separate
components that run in parallel on individual cores in a computer or computers in a cluster. Typically, these applications are designed so that once each
computing node in the cluster has solved its portion of the problem, the results
from all the nodes are combined into a final solution.
34
HADOOP
Hadoop is an open-source software framework that is used for distributed
processing of large data sets (known as big data) in a clustered system containing simple, low-cost hardware components. Hadoop is designed to scale
from a single system to a cluster containing thousands of computing nodes.
Tasks are assigned to a node in the cluster, and Hadoop arranges communication between nodes to manage parallel computations to process and coalesce
results. Hadoop also detects and manages failures in nodes, providing an
efficient and highly reliable distributed computing service.
Hadoop is organized around the following three components:
1. A distributed file system that manages data and files across distributed computing nodes.
2. The YARN (“Yet Another Resource Negotiator”) framework, which manages
resources within the cluster as well as scheduling tasks on nodes in the
cluster.
3. The MapReduce system, which allows parallel processing of data across
nodes in the cluster.
Hadoop is designed to run on Linux systems, and Hadoop applications
can be written using several programming languages, including scripting
languages such as PHP, Perl, and Python. Java is a popular choice for
developing Hadoop applications, as Hadoop has several Java libraries that
support MapReduce.
35
Once the kernel is loaded and executing, it can start providing services to
the system and its users
. Some services are provided outside of the kernel by
system programs that are loaded into memory at boot time to become system
daemons, which run the entire time the kernel is running. On Linux, the first
system program is “systemd,” and it starts many other daemons. Once this
phase is complete, the system is fully booted, and the system waits for some
event to occur.
If there are no processes to execute, no I/O devices to service, and no users
to whom to respond, an operating system will sit quietly, waiting for something
to happen. Events are almost always signaled by the occurrence of an interrupt.
In Section 1.2.1 we described hardware interrupts. Another form of interrupt is
a trap (or an exception), which is a software-generated interrupt caused either
by an error (for example, division by zero or invalid memory access) or by
a specific request from a user program that an operating-system service be
performed by executing a special operation called a system call.
36
Multiprogramming
g 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. Input, for example, may be bounded by the user’s typing speed; seven characters per second is fast for
people but incredibly slow for computers. Rather than let the CPU sit idle as
this interactive input takes place, the operating system will rapidly switch the
CPU to another process.
37
In a multitasking system, the operating system must ensure reasonable
response time.
A common method for doing so is virtual memory, a technique that allows the execution of a process that is not completely in memory
(Chapter 10). The main advantage of this scheme is that it enables users to
run programs that are larger than actual physical memory. Further, it abstracts
main memory into a large, uniform array of storage, separating logical memory as viewed by the user from physical memory. This arrangement frees
programmers from concern over memory-storage limitations.
38
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).
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.
At system boot time, the hardware starts in kernel mode. The operating
system is then loaded and starts user applications in user mode. Whenever a
trap or interrupt occurs, the hardware switches from user mode to kernel mode
(that is, changes the state of the mode bit to 0). Thus, whenever the operating
system gains control of the computer, it is in kernel mode. The system always
switches to user mode (by setting the mode bit to 1) before passing control to
a user program.
39
System calls provide the means for a user program to ask the operating
system to perform tasks reserved for the operating system on the user program’s behalf.
A system call is invoked in a variety of ways, depending on
the functionality provided by the underlying processor. In all forms, it is the
method used by a process to request action by the operating system. A system
call usually takes the form of a trap to a specific location in the interrupt vector.
This trap can be executed by a generic trap instruction, although some systems
have a specific syscall instruction to invoke a system call.
When a system call is executed, it is typically treated by the hardware as
a software interrupt. Control passes through the interrupt vector to a service
routine in the operating system, and the mode bit is set to kernel mode. The
system-call service routine is a part of the operating system. The kernel examines the interrupting instruction to determine what system call has occurred;
a parameter indicates what type of service the user program is requesting.
Additional information needed for the request may be passed in registers, on
the stack, or in memory (with pointers to the memory locations passed in registers). The kernel verifies that the parameters are correct and legal, executes
the request, and returns control to the instruction following the system call.
40
Timer
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.
41
We emphasize that a program by itself is not a process.
A program is a
passive entity, like the contents of a file stored on disk, whereas a process is an
active entity
42
The operating system is responsible for the following activities in connection with process management:
* Creating and deleting both user and system processes
* Scheduling processes and threads on the CPUs
* Suspending and resuming processes
* Providing mechanisms for process synchronization
* Providing mechanisms for process communication
43
Caching
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.
44
cache size
Because caches have limited size, cache management is an important
design problem. Careful selection of the cache size and of a replacement policy
can result in greatly increased performance, as you can see by examining Figure
1.14. Replacement algorithms for software-controlled caches are discussed in
Chapter 10.
The movement of information between levels of a storage hierarchy may be
either explicit or implicit, depending on the hardware design and the controlling operating-system software. For instance, data transfer from cache to CPU
and registers is usually a hardware function, with no operating-system intervention. In contrast, transfer of data from disk to memory is usually controlled
by the operating system.
In a hierarchical storage structure, the same data may appear in different
levels of the storage system. For example, suppose that an integer A that is
to be incremented by 1 is located in file B, and file B resides on hard disk.
The increment operation proceeds by first issuing an I/O operation to copy the
disk block on which A resides to main memory. This operation is followed by
copying A to the cache and to an internal register. Thus, the copy of A appears
in several places: on the hard disk, in main memory, in the cache, and in an
internal register (see Figure 1.15). Once the increment takes place in the internal
register, the value of A differs in the various storage systems.
45
The I/O subsystem consists of several components:
* A memory-management component that includes buffering, caching, and
spooling
* A general device-driver interface
* Drivers for specific hardware devices
Only the device driver knows the peculiarities of the specific device to which
it is assigned.
46
Protection
, 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. A protection-oriented
system provides a means to distinguish between authorized and unauthorized
usage
47
Protection and security require the system to be able to distinguish among
all its users. Most operating systems maintain a list of
f 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 .
A user can be in one or more groups, depending on operating-system design
48
In the course of normal system use, the user ID and group ID for a user
are sufficient
However, a user sometimes needs to escalate privileges to gain
extra permissions for an activity. The user may need access to a device that is
restricted, for example. Operating systems provide various methods to allow
privilege escalation. On UNIX, for instance, the setuid attribute on a program
causes that program to run with the user ID of the owner of the file, rather than
the current user’s ID. The process runs with this effective UID until it turns off
the extra privileges or terminates.
49
Virtualization
is a technology that allows us to abstract the hardware of a single computer (the CPU, memory, disk drives, network interface cards, and so
forth) into several different execution environments, thereby creating the illusion that each separate environment is running on its own private computer.
These environments can be viewed as different individual operating systems
(for example, Windows and UNIX) that may be running at the same time and
may interact with each other
50
virtual machine
A user of a virtual machine can switch among
the various operating systems in the same way a user can switch among the
various processes running concurrently in a single operating system.
Virtualization allows operating systems to run as applications within other
operating systems. At first blush, there seems to be little reason for such functionality. But the virtualization industry is vast and growing, which is a testament to its utility and importance.
51
Emulation
involves simulating computer hardware in software, is typically used when the source CPU type is different from
the target CPU type. For example, when Apple switched from the IBM Power
CPU to the Intel x86 CPU for its desktop and laptop computers, it included an
emulation facility called “Rosetta,” which allowed applications compiled for
the IBM CPU to run on the Intel CPU. That same concept can be extended to allow
an entire operating system written for one platform to run on another. Emulation comes at a heavy price, however. Every machine-level instruction that runs
natively on the source system must be translated to the equivalent function
on the target system, frequently resulting in several target instructions. If the
source and target CPUs have similar performance levels, the emulated code
may run much more slowly than the native code.
With virtualization, in contrast, an operating system that is natively compiled for a particular CPU architecture runs within another operating system
also native to that CPU. Virtualization first came about on IBM mainframes as
a method for multiple users to run tasks concurrently. Running multiple virtual machines allowed (and still allows) many users to run tasks on a system
designed for a single user. Later, in response to problems with running multiple
Microsoft Windows applications on the Intel x86 CPU, VMware created a new
virtualization technology in the form of an application that ran on Windows.
That application ran one or more guest copies of Windows or other native
x86 operating systems, each running its own applications.
52
virtual machine manager (VMM)
Windows was the host operating system, and the VMware application was the
virtual machine manager (VMM). The VMM runs the guest operating systems,
manages their resource use, and protects each guest from the others.
Even though modern operating systems are fully capable of running multiple applications reliably, the use of virtualization continues to grow. On laptops
and desktops, a VMM allows the user to install multiple operating systems for
exploration or to run applications written for operating systems other than the
native host. For example, an Apple laptop running macOS on the x86 CPU can
run a Windows 10 guest to allow execution of Windows applications. Companies writing software for multiple operating systems can use virtualization
to run all of those operating systems on a single physical server for development, testing, and debugging. Within data centers, virtualization has become a
common method of executing and managing computing environments. VMMs
like VMware ESXand Citrix XenServer no longer run on host operating systems
but rather are the host operating systems, providing services and resource
management to virtual machine processes.
53
A distributed system is a
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.Others make users specifically invoke network functions. Generally, systems
contain a mix of the two modes— for example FTP and NFS. The protocols
that create a distributed system can greatly affect that system’s utility and
popularity
54
A network
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.
A computer running a network operating system acts autonomously from all
other computers on the network, although it is aware of the network and is
able to communicate with other networked computers. A distributed operating system provides a less autonomous environment.
55
Lists, Stacks, and Queues
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.
56
Trees
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
57
Hash Functions and Maps
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.
One potential difficulty with hash functions is that two unique inputs
can result in the same output value— that is, they can link to the same table location. We can accommodate this hash collision by having a linked list at the
table location that contains all of the items with the same hash value. Of course,
the more collisions there are, the less efficient the hash function is.
One use of a hash function is to implement a hash map, which associates
(or maps) [key:value] pairs using a hash function. Once the mapping is established, we can apply the hash function to the key to obtain the value from the
hash map (Figure 1.21). For example, suppose that a user name is mapped to
a password. Password authentication then proceeds as follows: a user enters
her user name and password. The hash function is applied to the user name,
which is then used to retrieve the password. The retrieved password is then
compared with the password entered by the user for authentication.
58
Bitmaps
Abitmap 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). The value of the i
th position in the bitmap is associated with the i
th resource. As an
example, consider the bitmap shown below:
001011101
Resources 2, 4, 5, 6, and 8 are unavailable; resources 0, 1, 3, and 7 are available.
The power of bitmaps becomes apparent when we consider their space
efficiency. If we were to use an eight-bit Boolean value instead of a single bit,
the resulting data structure would be eight times larger. Thus, bitmaps are
commonly used when there is a need to represent the availability of a large
number of resources. Disk drives provide a nice illustration. A medium-sized
disk drive might be divided into several thousand individual units, called disk
blocks. A bitmap can be used to indicate the availability of each disk block.
In summary, data structures are pervasive in operating system implementations. Thus, we will see the structures discussed here, along with others,
throughout this text as we explore kernel algorithms and their implementations.
59
Traditional Computing
As computing has matured, the lines separating many of the traditional computing environments have blurred. Consider the “typical office environment.”
Just a few years ago, this environment consisted of PCs connected to a network,
with servers providing file and print services. Remote access was awkward,
and portability was achieved by use of laptop computers.
Today, web technologies and increasing WAN bandwidth are stretching the
boundaries of traditional computing. Companies establish portals, which provide web accessibility to their internal servers. Network computers (or thin
clients)—which are essentially terminals that understand web-based computing—are used in place of traditional workstations where more security or
easier maintenance is desired. Mobile computers can synchronize with PCs
to allow very portable use of company information. Mobile devices can also connect to wireless networks and cellular data networks to use the company’s
web portal (as well as the myriad other web resources).
At home, most users once had a single computer with a slow modem connection to the office, the Internet, or both. Today, network-connection speeds
once available only at great cost are relatively inexpensive in many places,
giving home users more access to more data. These fast data connections are
allowing home computers to serve up web pages and to run networks that
include printers, client PCs, and servers. Many homes use firewall to protect their networks from security breaches. Firewalls limit the communications
between devices on a network.
In the latter half of the 20th century, computing resources were relatively
scarce. (Before that, they were nonexistent!) For a period of time, systems were
either batch or interactive. Batch systems processed jobs in bulk, with predetermined input from files or other data sources. Interactive systems waited for
input from users. To optimize the use of the computing resources, multiple
users shared time on these systems. These time-sharing systems used a timer
and scheduling algorithms to cycle processes rapidly through the CPU, giving
each user a share of the resources.
Traditional time-sharing systems are rare today. The same scheduling technique is still in use on desktop computers, laptops, servers, and even mobile
computers, but frequently all the processes are owned by the same user (or a
single user and the operating system). User processes, and system processes
that provide services to the user, are managed so that each frequently gets a
slice of computer time. Consider the windows created while a user is working
on a PC, for example, and the fact that they may be performing different tasks
at the same time. Even a web browser can be composed of multiple processes,
one for each website currently being visited, with time sharing applied to each
web browser process.
60
Mobile computing
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.
Today, mobile systems are used not only for e-mail and web browsing but
also for playing music and video, reading digital books, taking photos, and
recording and editing high-definition video. Accordingly, tremendous growth
continues in the wide range of applications that run on such devices. Many
developers are now designing applications that take advantage of the unique
features of mobile devices, such as global positioning system (GPS) chips,
accelerometers, and gyroscopes. An embedded GPS chip allows a mobile device
to use satellites to determine its precise location on Earth. That functionality is especially useful in designing applications that provide navigation— for example, telling users which way to walk or drive or perhaps directing them to
nearby services, such as restaurants. An accelerometer allows a mobile device
to detect its orientation with respect to the ground and to detect certain other
forces, such as tilting and shaking. In several computer games that employ
accelerometers, players interface with the system not by using a mouse or a
keyboard but rather by tilting, rotating, and shaking the mobile device! Perhaps
more a practical use of these features is found in augmented-reality applications, which overlay information on a display of the current environment.
It is difficult to imagine how equivalent applications could be developed on
traditional laptop or desktop computer systems.
To provide access to on-line services, mobile devices typically use either
IEEE standard 802.11 wireless or cellular data networks. The memory capacity
and processing speed of mobile devices, however, are more limited than those
of PCs. Whereas a smartphone or tablet may have 256 GB in storage, it is not
uncommon to find 8 TB in storage on a desktop computer. Similarly, because
power consumption is such a concern, mobile devices often use processors that
are smaller, are slower, and offer fewer processing cores than processors found
on traditional desktop and laptop computers.
Two operating systems currently dominate mobile computing: Apple iOS
and Google Android. iOS was designed to run on Apple iPhone and iPad
mobile devices. Android powers smartphones and tablet computers available
from many manufacturers. We examine these two mobile operating systems in
further detail in Chapter 2.
61
Client –Server Computing
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.
62
Peer-to-Peer Computing
Another structure for a distributed system is the peer-to-peer (P2P) system
model. In this model, clients and servers are not distinguished from one
another. Instead, all nodes within the system are considered peers, and each
may act as either a client or a server, depending on whether it is requesting or
providing a service. Peer-to-peer systems offer an advantage over traditional
client–server systems. In a client–server system, the server is a bottleneck; but
in a peer-to-peer system, services can be provided by several nodes distributed
throughout the network.
To participate in a peer-to-peer system, a node must first join the network
of peers. Once a node has joined the network, it can begin providing services
to—and requesting services from—other nodes in the network. Determining
what services are available is accomplished in one of two general ways:
* When a node joins a network, it registers its service with a centralized
lookup service on the network. Any node desiring a specific service first
contacts this centralized lookup service to determine which node provides
the service. The remainder of the communication takes place between the
client and the service provider.
* An alternative scheme uses no centralized lookup service. Instead, a peer
acting as a client must discover what node provides a desired service by
broadcasting a request for the service to all other nodes in the network.
The node (or nodes) providing that service responds to the peer making
the request. To support this approach, a discovery protocol must be provided that allows peers to discover services provided by other peers in the
network. Figure 1.23 illustrates such a scenario.
Peer-to-peer networks gained widespread popularity in the late 1990s with
several file-sharing services, such as Napster and Gnutella, that enabled peers
to exchange files with one another. The Napster system used an approach similar to the first type described above: a centralized server maintained an index of
all files stored on peer nodes in the Napster network, and the actual exchange
of files took place between the peer nodes. The Gnutella system used a technique similar to the second type: a client broadcast file requests to other nodes
in the system, and nodes that could service the request responded directly to
the client. Peer-to-peer networks can be used to exchange copyrighted materials (music, for example) anonymously, and there are laws governing the
distribution of copyrighted material. Notably, Napster ran into legal trouble
for copyright infringement, and its services were shut down in 2001. For this
reason, the future of exchanging files remains uncertain. Skype is another example of peer-to-peer computing. It allows clients to
make voice calls and video calls and to send text messages over the Internet
using a technology known as voice over IP (VoIP). Skype uses a hybrid peerto-peer approach. It includes a centralized login server, but it also incorporates
decentralized peers and allows two peers to communicate.
63
Cloud computing
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)
These cloud-computing types are not discrete, as a cloud computing environment may provide a combination of several types. For example, an organization may provide both SaaS and IaaS as publicly available services.
Certainly, there are traditional operating systems within many of the types
of cloud infrastructure. Beyond those are the VMMs that manage the virtual
machines in which the user processes run. At a higher level, the VMMs themselves are managed by cloud management tools, such as VMware vCloud
Director and the open-source Eucalyptus toolset. These tools manage the
resources within a given cloud and provide interfaces to the cloud components,
making a good argument for considering them a new type of operating system.
Figure 1.24 illustrates a public cloud providing IaaS. Notice that both the
cloud services and the cloud user interface are protected by a firewall.
64
Embedded systems almost always run
real-time operating systems. A realtime system is used when rigid time requirements have been placed on the
operation of a processor or the flow of data; thus, it is often used as a control
device in a dedicated application. Sensors bring data to the computer. The computer must analyze the data and possibly adjust controls to modify the sensor
inputs. Systems that control scientific experiments, medical imaging systems,
industrial control systems, and certain display systems are real-time systems.
Some automobile-engine fuel-injection systems, home-appliance controllers,
and weapon systems are also real-time systems.
A real-time system has well-defined, fixed time constraints. Processing
must be done within the defined constraints, or the system will fail. For
instance, it would not do for a robot arm to be instructed to halt after it had
smashed into the car it was building. A real-time system functions correctly
only if it returns the correct result within its time constraints. Contrast this system with a traditional laptop system where it is desirable (but not mandatory)
to respond quickly.
65
Free and Open-Source Operating Systems
The study of operating systems has been made easier by the availability of a vast number of free software and open-source releases.
Both free operating systems and open-source operating systems
are available in source-code format rather than as compiled binary
code. Note, though, that free software and open-source software are
two different ideas championed by different groups of people (see
http://gnu.org/philosophy/open-source-misses-the-point.html/ for a
discussion on the topic). Free software (sometimes referred to as free/libre
software) not only makes source code available but also is licensed to allow
no-cost use, redistribution, and modification. Open-source software does
not necessarily offer such licensing. Thus, although all free software is open
source, some open-source software is not “free.” GNU/Linux is the most
famous open-source operating system, with some distributions free and
others open source only (http://www.gnu.org/distros/). Microsoft Windows
is a well-known example of the opposite closed-source approach. Windows
is proprietary software—Microsoft owns it, restricts its use, and carefully
protects its source code. Apple’s macOS operating system comprises a hybrid approach. It contains an open-source kernel named Darwin but includes
proprietary, closed-source components as well.
Starting with the source code allows the programmer to produce binary
code that can be executed on a system. Doing the opposite—reverse engineering the source code from the binaries—is quite a lot of work, and useful
items such as comments are never recovered. Learning operating systems by
examining the source code has other benefits as well. With the source code
in hand, a student can modify the operating system and then compile and
run the code to try out those changes, which is an excellent learning tool.
This text includes projects that involve modifying operating-system source
code, while also describing algorithms at a high level to be sure all important
operating-system topics are covered. Throughout the text, we provide pointers
to examples of open-source code for deeper study.
There are many benefits to open-source operating systems, including a
community of interested (and usually unpaid) programmers who contribute to
the code by helping to write it, debug it, analyze it, provide support, and suggest changes. Arguably, open-source code is more secure than closed-source
code because many more eyes are viewing the code. Certainly, open-source
code has bugs, but open-source advocates argue that bugs tend to be found
and fixed faster owing to the number of people using and viewing the code.
Companies that earn revenue from selling their programs often hesitate to
open-source their code, but Red Hat and a myriad of other companies are doing
just that and showing that commercial companies benefit, rather than suffer,
when they open-source their code. Revenue can be generated through support
contracts and the sale of hardware on which the software runs, for example.
66
Free Operating Systems
To counter the move to limit software use and redistribution, Richard Stallman
in 1984 started developing a free, UNIX-compatible operating system called
GNU(which is a recursive acronym for “GNU’s Not Unix!”). To Stallman, “free”
refers to freedom of use, not price. The free-software movement does not object
to trading a copy for an amount of money but holds that users are entitled to
four certain freedoms: (1) to freely run the program, (2) to study and change
the source code, and to give or sell copies either (3) with or (4) without changes.
In 1985, Stallman published the GNU Manifesto, which argues that all software
should be free. He also formed the Free Software Foundation (FSF) with the
goal of encouraging the use and development of free software.
The FSF uses the copyrights on its programs to implement “copyleft,” a
form of licensing invented by Stallman. Copylefting a work gives anyone that
possesses a copy of the work the four essential freedoms that make the work
free, with the condition that redistribution must preserve these freedoms. The
GNU General Public License (GPL) is a common license under which free
software is released. Fundamentally, the GPL requires that the source code be
distributed with any binaries and that all copies (including modified versions)
be released under the same GPL license. The Creative Commons “Attribution
Sharealike” license is also a copyleft license; “sharealike” is another way of
stating the idea of copyleft.
67
GNU/Linux
As an example of a free and open-source operating system, consider
GNU/Linux. By 1991, the GNU operating system was nearly complete. The
GNU Project had developed compilers, editors, utilities, libraries, and games
— whatever parts it could not find elsewhere. However, the GNU kernel never
became ready for prime time. In 1991, a student in Finland, Linus Torvalds,
released a rudimentary UNIX-like kernel using the GNU compilers and tools
and invited contributions worldwide. The advent of the Internet meant that
anyone interested could download the source code, modify it, and submit
changes to Torvalds. Releasing updates once a week allowed this so-called
“Linux” operating system to grow rapidly, enhanced by several thousand
programmers. In 1991, Linux was not free software, as its license permitted
only noncommercial redistribution. In 1992, however, Torvalds rereleased
Linux under the GPL, making it free software (and also, to use a term coined
later, “open source”).
The resulting GNU/Linux operating system (with the kernel properly
called Linux but the full operating system including GNU tools called
GNU/Linux) has spawned hundreds of unique distributions, or custom
builds, of the system. Major distributions include Red Hat, SUSE, Fedora,
Debian, Slackware, and Ubuntu. Distributions vary in function, utility,
installed applications, hardware support, user interface, and purpose. For
example, Red Hat Enterprise Linux is geared to large commercial use.
PCLinuxOS is a live CD—an operating system that can be booted and run
from a CD-ROM without being installed on a system’s boot disk. A variant of
PCLinuxOS—called PCLinuxOS Supergamer DVD—is a live DVD that includes
graphics drivers and games. A gamer can run it on any compatible system
simply by booting from the DVD. When the gamer is finished, a reboot of the
system resets it to its installed operating system.
You can run Linux on a Windows (or other) system using the following
simple, free approach:
1. Download the free Virtualbox VMM tool from
https://www.virtualbox.org/
and install it on your system.
2. Choose to install an operating system from scratch, based on an
installation image like a CD, or choose pre-built operating-system images
that can be installed and run more quickly from a site like
http://virtualboxes.org/images/
These images are preinstalled with operating systems and applications
and include many flavors of GNU/Linux.
3. Boot the virtual machine within Virtualbox.
An alternative to using Virtualbox is to use the free program Qemu
(http://wiki.qemu.org/Download/), which includes the qemu-img command
for converting Virtualbox images to Qemu images to easily import them.
With this text, we provide a virtual machine image of GNU/Linux running
the Ubuntu release. This image contains the GNU/Linux source code as well as
tools for software development. We cover examples involving the GNU/Linux
image throughout this text, as well as in a detailed case study in Chapter 20.
68
BSD UNIX
has a longer and more complicated history than Linux. It started in
1978 as a derivative of AT&T’s UNIX. Releases from the University of California
at Berkeley (UCB) came in source and binary form, but they were not open
source because a license from AT&T was required. BSD UNIX’s development was
slowed by a lawsuit by AT&T, but eventually a fully functional, open-source
version, 4.4BSD-lite, was released in 1994.
Just as with Linux, there are many distributions of BSD UNIX, including
FreeBSD, NetBSD, OpenBSD, and DragonflyBSD. To explore the source code
of FreeBSD, simply download the virtual machine image of the version of
interest and boot it within Virtualbox, as described above for Linux. The
source code comes with the distribution and is stored in /usr/src/. The
kernel source code is in /usr/src/sys. For example, to examine the virtual memory implementation code in the FreeBSD kernel, see the files in
/usr/src/sys/vm. Alternatively, you can simply view the source code online
at https://svnweb.freebsd.org.
As with many open-source projects, this source code is contained in
and controlled by a version control system—in this case, “subversion”
(https://subversion.apache.org/source-code). Version control systems allow
a user to “pull” an entire source code tree to his computer and “push” any
changes back into the repository for others to then pull. These systems also
provide other features, including an entire history of each file and a conflict
resolution feature in case the same file is changed concurrently. Another version control system is git, which is used for GNU/Linux, as well as other
programs (http://www.git-scm.com).
Darwin, the core kernel component of macOS, is based on BSD
UNIX and is open-sourced as well. That source code is available from
http://www.opensource.apple.com/. Every macOS release has its open-source
components posted at that site. The name of the package that contains the
kernel begins with “xnu.” Apple also provides extensive developer tools,
documentation, and support at http://developer.apple.com.
69
THE STUDY OF OPERATING SYSTEMS
There has never been a more interesting time to study operating systems,
and it has never been easier. The open-source movement has overtaken operating systems, causing many of them to be made available in both source and
binary (executable) format. The list of operating systems available in both
formats includes Linux, BSD UNIX, Solaris, and part of macOS. The availability of source code allows us to study operating systems from the inside out.
Questions that we could once answer only by looking at documentation or
the behavior of an operating system we can now answer by examining the
code itself.
Operating systems that are no longer commercially viable have been
open-sourced as well, enabling us to study how systems operated in a
time of fewer CPU, memory, and storage resources. An extensive but
incomplete list of open-source operating-system projects is available from
http://dmoz.org/Computers/Software/Operating Systems/Open Source/.
In addition, the rise of virtualization as a mainstream (and frequently free)
computer function makes it possible to run many operating systems on top
of one core system. For example, VMware (http://www.vmware.com) provides a free “player” for Windows on which hundreds of free “virtual appliances” can run. Virtualbox (http://www.virtualbox.com) provides a free,
open-source virtual machine manager on many operating systems. Using
such tools, students can try out hundreds of operating systems without dedicated hardware.
In some cases, simulators of specific hardware are also available, allowing the operating system to run on “native” hardware, all within the confines of a modern computer and modern operating system. For example,
a DECSYSTEM-20 simulator running on macOS can boot TOPS-20, load the
source tapes, and modify and compile a new TOPS-20 kernel. An interested
student can search the Internet to find the original papers that describe the
operating system, as well as the original manuals.
The advent of open-source operating systems has also made it easier to
make the move from student to operating-system developer. With some
knowledge, some effort, and an Internet connection, a student can even create
a new operating-system distribution. Not so many years ago, it was difficult
or impossible to get access to source code. Now, such access is limited only
by how much interest, time, and disk space a student has.
70
Solaris
Solaris is the commercial UNIX-based operating system of Sun Microsystems.
Originally, Sun’s SunOS operating system was based on BSD UNIX. Sun moved
to AT&T’s System V UNIX as its base in 1991. In 2005, Sun open-sourced most
of the Solaris code as the OpenSolaris project. The purchase of Sun by Oracle
in 2009, however, left the state of this project unclear.
Several groups interested in using OpenSolaris have expanded its features,
and their working set is Project Illumos, which has expanded from the OpenSolaris base to include more features and to be the basis for several products.
Illumos is available at http://wiki.illumos.org
71
Open-Source Systems as Learning Tools
The free-software movement is driving legions of programmers to create
thousands of open-source projects, including operating systems. Sites like
http://freshmeat.net/ and http://distrowatch.com/ provide portals to many of
these projects. As we stated earlier, open-source projects enable students to
use source code as a learning tool. They can modify programs and test them,
help find and fix bugs, and otherwise explore mature, full-featured operating
systems, compilers, tools, user interfaces, and other types of programs. The
availability of source code for historic projects, such as Multics, can help students to understand those projects and to build knowledge that will help in the
implementation of new projects.
Another advantage of working with open-source operating systems is their
diversity. GNU/Linux and BSD UNIX are both open-source operating systems,
for instance, but each has its own goals, utility, licensing, and purpose. Sometimes, licenses are not mutually exclusive and cross-pollination occurs, allowing rapid improvements in operating-system projects. For example, several
major components of OpenSolaris have been ported to BSD UNIX. The advantages of free software and open sourcing are likely to increase the number
and quality of open-source projects, leading to an increase in the number of
individuals and companies that use these projects.
