Two-Level Directory

As we have seen, a single-level directory often leads to confusion of file names among different users. The standard solution is to create a separate directory for each user.
In the two-level directory structure, each user has his own user file directory (LTD). The UFDs have similar structures, but each lists only the files of a single user. When a user job starts or a user logs in, the system's master file directory (MFD) is searched. The MFD is indexed by user name or account number, and each entry points to the UFD for that user.
When a user refers to a particular file, only his own UFD is searched. Thus, different users may have files with the same name, as long as all the file names within each UFD are unique. To create a file for a user, the operating system searches only that user's UFD to ascertain whether another file of that name exists. To delete a file, the operating system confines its search to the local UFD; thus, it cannot accidentally delete another user's file that has the same name.
The user directories themselves must be created and deleted as necessary. A special system program is run with the appropriate user name and account information. The program creates a new UFD and adds an entry or it to the PvlFD. The execution of this program might be restricted to system administrators. Although the two-level directory structure solves the name-collision problem, it still has disadvantages. This structure effectively isolates one user from another. Isolation is an advantage wrhen the users are completely independent but is a disadvantage when the users want to cooperate on some task and to access one another's files. Some systems simply do not allow local user files to be accessed by other users.
If access is to be permitted, one user must have the ability to name a file in another user's directory. To name a particular file uniquely in a two-level directory, we must give both the user name and the file name. A two-level directory can be thought of as a tree, or an inverted tree, of height 2. The root of the tree is the MFD. Its direct descendants are the UFDs. The descendants of the UFDs are the files themselves. The files are the leaves of the tree. Specifying a user name and a file name defines a path in the tree from the root (the MFD)
to a leaf (the specified file). Thus, a user name and a file name define a path name. Every file in the system has a path name. To name a file uniquely, a user must know the path name of the file desired.
For example, if user A wishes to access her own test file named test, she can simply refer to test. To access the file named test of user B (with directory-entry name userb), however, she might have to refer to /userb/test. Every system has its own syntax for naming files in directories other than the user's own.
Additional syntax is needed to specify the volume of a file. For instance, in MS-DOS a volume is specified by a letter followed by a colon. Thus, a file specification might be C:\ userb\test. Some systems go even further and separate the volume, directory name, and file name parts of the specification. For
instance, in VMS, the file login.com might be specified as: u:[sst.jdeckllogin.com;l, where u is the name of the volume, sst is the name of the directory, jdeck is the name of the subdirectory, and 1 is the version number. Other systems simply treat the volume name as part of the directory name. The first name given is
that of the volume, and the rest is the directory and file. For instance, /u/pbg/test might specify volume it, directory pbg, and file test. A special case of this situation occurs with the system files. Programs provided
as part of the system—loaders, assemblers, compilers, utility routines, libraries, and so on—are generally defined as files. When the appropriate commands are given to the operating system, these files are read by the loader and executed. Many command interpreters simply treat such a command as the name of a file to load and execute. As the directory system is defined presently, this file name would be searched for in the current UFD. One solution would be to copy the system files into each UFD. However, copying all the system files would waste an enormous amount of space. (If the system files require 5 MB, then supporting 12 users would require 5 x 12 = 60 MB just for copies of the system files.) The standard, solution is to complicate the search procedure slightly. A special user directory is defined to contain the system files (for example, user 0). Whenever a file name is given to be loaded, the operating system first searches the local UFD. If the file is found, it is used. If it is not found, the system automatically searches the special user directory that contains the system files. The sequence of directories searched when a file is named is called the search path. The search path can be extended to contain an unlimited list of directories
to search when a command name is given. This method is the one most used in UNIX and MS-DOS. Systems can also be designed so that each user has his own search path.

Directory Structure

Up to this point, we have been discussing "a file system." In reality, systems may have zero or more file systems, and the file systems may be of varying types. For example, a typical Solaris system may have a few UFS file systems, a VFS file system, and some NFS file systems. The file systems of computers, then, can be extensive. Some systems store millions of files on terabytes of disk. To manage all these data, we need to organize them. This organization involves the use of directories. In this section, we explore the topic of directory structure. First, though, we explain some basic features of storage structure.

1. Storage Structure
A disk (or any storage device that is large enough) can be used in its entirety for a file system. Sometimes, though, it is desirable to place multiple file systems on a disk or to use parts of a disk for a file system and other parts for other things, such as swap space or unformatted (raw) disk space. These parts are known variously as partitions, slices, or (in the IBM world) minidisks. A file system can be created on each of these parts of the disk. As we shall see in the next chapter, the parts can also be combined to form larger structures known as volumes, and file systems can be created on these as well. For now, for clarity, we simply refer to a chunk of storage that holds a file system as a volume. Each volume can be thought of as a virtual disk. Volumes can also store multiple operating systems, allowing a system to boot and run more than one. Each volume that contains a file system must also contain information about the files in the system. This information is kept in entries in a device directory or volume table of contents. The device directory (more commonly known simply as a directory) records information—such as name, location, size, and type—for all files on that volume. Figure 10.6 shows a typical file-system organization.

2. Directory Overview

The directory can be viewed as a symbol table that translates file names into their directory entries. If we take such a view, we see that the directory itself can be organized in many ways. We want to be able to insert entries, to delete entries, to search for a named entry, and to list all the entries in the directory. In this section, we examine several schemes for defining the logical structure of the directory system. When considering a particular directory structure, we need to keep in mind the operations that are to be performed on a directory: 

• Search for a file. We need to be able to search a directory structure to find the entry for a particular file. Since files have symbolic names and similar names may indicate a relationship between files, we may want to be able to find all files whose names match a particular pattern. 
• Create a file. New files need to be created and added to the directory.
•  Delete a file. When a file is no longer needed, we want to be able to remove it from the directory.
•  List a directory. We need to be able to list the files in a directory and the contents of the directory entry for each file in the list.
•  Rename a file. Because the name of a file represents its contents to its users, we must be able to change the name when the contents or use of the file changes. Renaming a file may also allow its position within the directory structure to be changed.
•  Traverse the file system. We may wish to access every directory and every file within a directory structure. For reliability, it is a good idea to save the contents and structure of the entire file system at regular intervals. Often, we do this by copying all files to magnetic tape. This technique provides a backup copy in case of system failure. In addition, if a file is no longer in use., the file can be copied to tape and the disk space of that file released for reuse by another file.

In the following sections, we describe the most common schemes for defining
the logical structure of a directory.

3. Single-Level Directory

A single-level directory has significant limitations, however, when the number of files increases or when the system has more than one user. Since all files are in the same directory, they must have unique names. If two users call their data file test, then the unique-name rule is violated. For example, in one programming class, 23 students called the program for their second assignment progl; another 11 called i\ assign!. Although file names are generally selected to reflect the content of the file, they are often limited in length, complicating the

task of making file names unique. The MS-DOS operating system allows only 11-character file names; UNIX, in contrast, allows 255 characters.

Even a single user on a single-level directory may find it difficult to remember the names of all the files as the number of files increases. It is not uncommon for a user to have hundreds of files on one computer system and an equal number of additional files on another system. Keeping track of so many

files is a daunting task.

Access Methods

1. Sequential Access
The simplest access method is sequential access. Information in the file is processed in order, one record after the other. This mode of access is by far the most common; for example, editors and compilers usually access files in this fashion. Reads and writes make up the bulk of the operations on a file. A read operation—read next—reads the next portion of the file and automatically advances a file pointer, which tracks the I/O location. Similarly, the write operation—write next—appends to the end of the file and advances to the end of the newly written material (the new end of file). Such a file can be reset to the beginning; and on some systems, a program .may be able to skip forward or backward n records for some integer n—perhaps only for n = 1. Sequential access, which is depicted in Figure 10.3, is based on a tape model of a file and works as well on sequential-access devices as it does on random-access ones.

2. Direct Access

Another method is direct access (or relative access). A file is made up of fixedlength logical records that allow programs to read and write records rapidly in no particular order. The direct-access method is based on a disk model of a file, since disks allow random access to any file block. For direct access, the file is viewed as a numbered sequence of blocks or records. Thus, we may read block 14, then read block 53, and then write block 7. There are no restrictions on the order of reading or writing for a direct-access file. Direct-access files are of great use for immediate access to large amounts of information. Databases are often of this type. When a query concerning a particular subject arrives, we compute which block contains the answer and then read that block directly to provide the desired information.

As a simple example, on an airline-reservation system, we might store all the information about a particular flight (for example, flight 713) in the block identified by the flight number. Thus, the number of available seats for flight 713 is stored in block 713 of the reservation file. To store information about a larger set, such as people, we might compute a hash function on the people's names or search a small in-memory index to determine a block to read and search.

For the direct-access method, the file operations must be modified to include the block number as a parameter. Thus, we have read n, where n is the block number, rather than read next, and write n rather than write next. An alternative approach is to retain read next and write next, as with sequential access, and to add an operation position file to n, where n is the block number. Then, to effect a read n, we would, position to n and then read next.

The block number provided by the user to the operating system is normally a relative block number. A relative block number is an index relative to the beginning of the file. Thvis, the first relative block of the file is 0, the next is 1, and so on, even though the actual absolute disk address of the block may be 14703 for the first block and 3192 for the second. The use of relative block numbers allows the operating system to decide where the file should be placed (called the allocation problem, as discussed in Chapter 11) and helps to prevent the user from accessing portions of the file system that may not be part of her file. Some systems start their relative block numbers at 0; others start at 1.

How then does the system satisfy a request for record N in a file? Assuming we have a logical record length L, the request for record A/ is turned into an I/O request for L bytes starting at location L * (N) within the file (assuming the first record is N - 0). Since logical records are of a fixed size, it is also easy to read, write, or delete a record.

Not all operating systems support both sequential and direct access for files. Some systems allow only sequential file access; others allow only direct access. Some systems require that a file be defined as sequential or direct when it is created; such a file can be accessed only in a manner consistent with its declaration. We can easily simulate sequential access on a direct-access file by simply keeping a variable cp that defines our current position. Simulating a direct-access file on a sequential-access file, however,

is extremely inefficient and clumsy.

3. Other Access Methods

Other access methods can be built on top of a direct-access method. These methods generally involve the construction of an index for the file. The index, like an index in the back of a book, contains pointers to the various blocks. To find a record in the file, we first search the index and then use the pointer to access the file directly and to find the desired record.

For example, a retail-price file might list the universal product codes (UPCs) for items, with the associated prices. Each record consists of a 10-digit UPC and a 6-digit price, for a 16-byte record, if our disk has 1,024 bytes per block, we can store 64 records per block. A file of 120,000 records would occupy about 2,000 blocks (2 million bytes). By keeping the file sorted by UPC, we can define an index consisting of the first UPC in each block. This index would have 2,000 entries of 10 digits each, or 20,000 bytes, and thus could be kept in memory To find the price of a particular item, we can make a binary search of the index.

From this search, we learn exactly which block contains the desired record and access that block. This structure allows us to search a large file doing little I/O.

With large files, the index file itself may become too large to be kept in memory. One solution is to create an index for the index file. The primary index file would contain pointers to secondary index files, which would point to the actual data items. For example, IBM's indexed sequential-access method (ISAM) uses a small

master index that points to disk blocks of a secondary index. The secondary index blocks point to the actual file blocks. The file is kept sorted on a defined key. To find a particular item, we first make a binary search of the master index, which provides the block number of the secondary index. This block is read in, and again a binary search is used to find the block containing the desired record. Finally, this block is searched sequentially. In this way, any record can be located from its key by at most two direct-access reads.

Internal File Structure

Internally, locating an offset within a file can be complicated for the operating system. Disk systems typically have a well-defined block size determined by the size of a sector. All disk I/O is performed in units of one block (physical record), and all blocks are the same size. It is unlikely that the physical record size will exactly match the length of the desired logical record. Logical records may even vary in length. Packing a number of logical records into physical blocks is a common solution to this problem.
For example, the UNIX operating system defines all files to be simply streams of bytes. Each byte is individually addressable by its offset from the beginning (or end) of the file. In this case, the logical record size is 1 byte. The file system automatically packs and unpacks bytes into physical disk blocks—
say, 512 bytes per block—as necessary.
The logical record size, physical block size, and packing technique determine how many logical records are in each physical block. The packing can be done either by the user's application program or by the operating system. In either case, the file may be considered to be a sequence of blocks. All the basic I/O functions operate in terms of blocks. The conversion from logical records to physical blocks is a relatively simple software problem.
Because disk space is always allocated in blocks, some portion of the last block of each file is generally wasted. If each block were 512 bytes, for example, then a file of 1,949 bytes would be allocated four blocks (2,048 bytes); the last 99 bytes would be wasted. The waste incurred to keep everything in units
of blocks (instead of bytes) is internal fragmentation. All file systems suffer from internal fragmentation; the larger the block size, the greater the internal fragmentation.

File Operations

A file is an abstract data type. To define a file properly, we need to consider the operations that can be performed on files. The operating system can provide system calls to create, write, read, reposition, delete, and truncate files. Let's examine what the operating system must do to perform each of these six basic file operations. It should then be easy to see how other, similar operations, such as renaming a file, can be implemented.

» Creating a file. Two steps are necessary to create a file. First, space in the
file system must be found for the file. Second, an entry for the new file must be made in
the directory.
• Writing a file. To write a file, we make a system call specifying both the
name of the file and the information to be written to the file. Given the
name of the file, the system searches the directory to find the file's location.
The system must keep a write pointer to the location in the file where the
next write is to take place. The write pointer must be updated whenever a
write occurs.
• Reading a file. To read from a file, we use a system call that specifies the
name of the file and where (in memory) the next block of the file should
be put. Again, the directory is searched for the associated entry, and the
system needs to keep a read pointer to the location in the file where the
next read is to take place. Once the read has taken place, the read pointer
is updated. Because a process is usually either reading from or writing to
a file, the current operation location can be kept as a per-process currentfile-
position pointer. Both the read and write operations use this same
pointer, saving space and reducing system complexity.
» Repositioning within a file. The directory is searched for the appropriate
entry, and the current-file-position pointer is repositioned to a given value.
Repositioning within a file need not involve any actual I/O. This file
operation is also known as a file seek.
• Deleting a file. To delete a file, we search the directory for the named file.
Having found the associated directory entry, we release all file space, so
that it can be reused bv other files, and erase the directory entry.
• Truncating a file. The user may want to erase the contents of a file but
keep its attributes. Rather than forcing the user to delete the file and then
recreate it, this function allows all attributes to remain unchanged—except
for file length—but lets the tile be reset to length zero and its file space
released.

These six basic operations comprise the minimal set of required file
operations. Other common operations include appending new information
to the end of an existing file and renaming an existing file. These primitive
operations can then be combined to perform other file operations. For instance,
we can create a copy of a file, or copy the file to another I/O device, such as
a printer or a display, by creating a new file and then reading from the old
and writing to the new. We also want to have operations that allow a user to
get and set the various attributes of a file. For example, we may want to have
operations that allow a user to determine the status of a file, such as the file's
length, and to set file attributes, such as the file's owner.
Most of the file operations mentioned involve searching the directory for
the entry associated with the named file. To avoid this constant searching, many
systems require that an openO system call be made before a file is first used
actively. The operating system keeps a small table, called the open-file table,
containing information about all open files. When a file operation is requested,
the file is specified via an index into this table, so no searching is required.
When the file is no longer being actively used, it is closed by the process, and
the operating system removes its entry from the open-file table, create and
delete are system calls that work with closed rather than open files.
Some systems implicitly open a file when the first reference to it is made.
The file is automatically closed when the job or program that opened the
file terminates. Most systems, however, require that the programmer open a
file explicitly with the openO system call before that file can be used. The
openO operation takes a file name and searches the directory, copying the
directory entry into the open-file table. The openO call can also accept accessmode
information—create, read-only, read—write, append-only, and so on.
This mode is checked against the file's permissions. If the request mode is
allowed, the file is opened for the process. The openO system call typically
returns a pointer to the entry in the open-file table. This pointer, not the actual
file name, is used in all I/O operations, avoiding any further searching and
simplifying the system-call interface.
The implementation of the openO and close() operations is more
complicated in an environment where several processes may open the file at
the same time. This may occur in a system where several different applications
open the same file at the same time. Typically, the operating system uses two
levels of internal tables: a per-process table and a system-wide table. The perprocess
table tracks all files that a process has open. Stored in this table is
information regarding the use of the file by the process. For instance, the
current file pointer for each file is found here. Access rights to the file and
accounting information can also be included.
Each entry in the per-process table in turn points to a system-wide open-file
table. The system-wide table contains process-independent information, such
as the location of the file on disk, access dates, and file size. Once a file has been
opened by one process, the system-wide table includes an entry for the file.
When another process executes an openQ call, a new entry is simply added
to the process's open-file table pointing to the appropriate entry in the systemwide
table. Typically., the open-file table also has an open count associated with
each file to indicate how many processes have the file open. Each close 0
decreases this open count, and when the open count reaches zero, the file is no
longer in use, and the file's entry is removed from the open-file table.
In summary, several pieces of information are associated with an open file.
• File pointer. On systems that do not include a file offset as part of the
readO and write () system calls, the system must track the last readwrite
location as a current-file-position pointer. This pointer is unique to
each process operating on the file and therefore must be kept separate from
the on-disk file attributes.
• File-open count. As files are closed, the operating system must reuse its
open-file table entries, or it could run out of space in the table. Because
multiple processes may have opened a file, the system must wait for the
last file to close before removing the open-file table entry. The file-open
counter tracks the number of opens and closes and reaches zero on the last
close. The system can then remove the entry.
• Disk location of the file. Most file operations require the system to modify
data within the file. The information needed to locate the file on disk is
kept in memory so that the system does not have to read it from disk for
each operation.
• Access rights. Each process opens a file in an access mode. This information
is stored on the per-process table so the operating system can allow or deny
subsequent I/O requests.
Some operating systems provide facilities for locking an open file (or
sections of a file). File "locks allow one process to lock a file and prevent other
processes from gaining access to it. File locks are useful for files that are shared
by several processes—for example, a system log file that can be accessed and
modified by a number of processes in the system.

The Java Virtual Machine

Java is a popular object-oriented programming language introduced by Sun
Microsystems in 1995. In addition to a language specification and a large API
library, Java also provides a specification for a Java virtual machine—or JVM.
Java objects are specified with the class construct; a Java program
consists of one or more classes. For each Java class, the compiler produces
an architecture-neutral bytecode output (.class) file that will run on any
implementation of the JVM.
The JVMis a specification for an abstract computer. It consists of a class
loader and a Java interpreter that executes the architecture-neutral bytecodes,
as diagrammed in Figure 2.17. The class loader loads the compiled . class
files from both the Java program and the Java API for execution by the Java
interpreter. After a class is loaded, the verifier checks that the . class file is
valid Java bytecode and does not overflow or underflow the stack. It also
ensures that the bytecode does not perform pointer arithmetic, which could
provide illegal memory access. If the class passes verification, it is run by the
Java interpreter. The JVM also automatically manages memory by performing
garbage collection—the practice of reclaiming memory from objects no longer
in use and returning it to the system. Much research focuses on garbage
collection algorithms for increasing the performance of Java programs in the
virtual machine.
The JVM may be implemented in software on top of a host operating
system, such as Windows, Linux, or Mac OS X, or as part of a web browser.
Alternatively, the JVM may be implemented in hardware on a chip specifically
designed to run Java programs. If the JVM is implemented in software, the
Java interpreter interprets the bytecode operations one at a time. A faster
software technique is to use a just-in-time (JIT) compiler. Here, the first time a
Java method is invoked, the bytecodes for the method are turned into native
machine language for the host system. These operations are then cached so that
subsequent invocations of a method are performed using the native machine
instructions and the bytecode operations need not be interpreted all over again.
A technique that is potentially even faster is to run the JVM in hardware on a
special Java chip that executes the Java bytecode operations as native code, thus
bypassing the need for either a software interpreter or a just-in-time compiler.

Modules

Perhaps the best current methodology for operating-system design involves
using object-oriented programming techniques to create a modular kernel.
Here, the kernel has a set of core components and dynamically links in
additional services either during boot time or during run time. Such a
strategy uses dynamically loadable modules and is common in modern
implementations of UNIX, such as Solaris, Linux, and Mac OS X. For example, the
Solaris operating system structure, shown in Figure 2.13, is organized around
a core kernel with seven types of loadable kernel modules:
1. Scheduling classes
2. File systems
3. Loadable system calls
4. Executable formats
5. STREAMS modules
6. Miscellaneous
7. Device and bus drivers

Such a design allows the kernel to provide core services yet also allows

certain features to be implemented dynamically. For example, device and

bus drivers for specific hardware can be added to the kernel, and support

for different file systems can be added as 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 in that any

module can call any other module. Furthermore, the approach is like 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.

The Apple Macintosh Mac OS X operating system uses a hybrid structure.

Mac OS X (also known as Danvin) structures the operating system using a

layered technique where one layer consists of the Mach microkernel. The

structure of Mac OS X appears in Figure 2.14.

The top layers include application environments and a set of services

providing a graphical interface to applications. Below these layers is the kernel

environment, which consists primarily of the Mach microkernel and the BSD

kernel. Mach provides memory management; support for remote procedure

calls (RPCs) and interprocess communication (IPC) facilities, including message

passing; and thread scheduling. The BSD component provides a BSD command

line interface, support for networking and file systems, and an implementation

of POSIX APIs, including Pthreads. In addition to Mach and BSD, the kernel

environment provides an I/O kit for development of device drivers and

dynamically loadable modules (which Mac OS X refers to as kernel extensions).

As shown in the figure, applications and common services can make use of

either the Mach or BSD facilities directly.

Microkernels

We have already seen that as UNIX expanded, the kernel became large
and difficult to manage. 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 system and user-level programs. 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.
The main function of the microkernel is to provide a communication facility
between the client program and the various services that are also running
in user space. Communication is provided by message passing, which was
described in Section 2.4.5. For example, if the client program wishes to access
a file, it must 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 ease of extending the operating
system. 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.
Several contemporary operating systems have used the microkernel
approach. Tru64 UNIX (formerly Digital UNIX) provides a UNIX interface to
the user, but it is implemented with a Mach kernel. The Mach kernel maps
UNIX system calls into messages to the appropriate user-level services.
Another example is QNX. QNX is a real-time operating system that is also
based on the microkernel design. The QNX microkernel provides services
for message passing and process scheduling. It also handles low-level network
communication and hardware interrupts. All other services in QNX are
provided by standard processes that run outside the kernel in user mode.
Unfortunately, microkernels can suffer from performance decreases due
to increased system function overhead. Consider the history of Windows NT.
The first release had a layered microkernel organization. However, this version
delivered low performance compared with that of Windows 95. Windows NT
4.0 partially redressed the performance problem by moving layers from user
space to kernel space and integrating them more closely. By the time Windows
XP was designed, its architecture was more monolithic than microkernel.

Operating-System Layered Approach

With proper hardware support, operating systems can be broken into pieces
that are smaller and more appropriate than those allowed by the original
MS-DOS or UNIX systems. The operating system can then retain much greater
control over the computer and over the applications that make use of that
computer. Implementers have more freedom in changing the inner workings
of the system and in creating modular operating systems. Under the topdown
approach, the overall functionality and features are determined and are separated into components. Information hiding is also important, because it
leaves programmers free to implement the low-level routines as they see fit,
provided that the external interface of the routine stays unchanged and that
the routine itself performs the advertised task.

A system can be made modular in many ways. One method is the layered

approach, in which the operating system is broken up 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.12.

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 routines 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)

and services of only lower-level layers. This approach simplifies debugging

and system verification. The first layer can be debugged without any concern

for the rest of the system, because, by definition, it uses only the basic hardware

(which is assumed correct) to implement its functions. Once the first layer is

debugged, its correct functioning can be assumed while the second layer is

debugged, and so on. If an error is found during the debugging of a particular

layer, the error must be on that layer, because the layers below it are already

debugged. Thus, the design and implementation of the system is simplified.

Each layer is implemented with only those operations provided by lowerlevel

layers. A layer does not need to know how these operations are

implemented; it needs to know only what these operations do. Hence, each

layer hides the existence of certain data structures, operations, and hardware

from higher-level layers.

The major difficulty with the layered approach involves appropriately

defining the various layers. Because a layer can use only lower-level layers,

careful planning is necessary. For example, the device driver for the backing store (disk space used by virtual-memory algorithms) must be at a lower

level than the memory-management routines, because memory management

requires the ability to use the backing store.

Other requirements may not be so obvious. The backing-store driver would

normally be above the CPU scheduler, because the driver may need to wait for

I/O and the CPU can be rescheduled during this time. However, on a large

system, the CPU scheduler may have more information about all the active

processes than can fit in memory. Therefore, this information may need to be

swapped in and out of memory, requiring the backing-store driver routine to

be below the CPU scheduler.

A final problem with layered implementations is that they tend to be less

efficient than other types. For instance, when a user program executes an I/O

operation, it executes a system call that is trapped to the I/O layer, which calls

the memory-management layer, which in turn calls the CPU-scheduling layer,

which is then passed to the hardware. At each layer, the parameters may be

modified, data may need to be passed, and so on. Each layer adds overhead to

the system call; the net result is a system call that takes longer than does one

on a nonlayered system.

These limitations have caused a small backlash against layering in recent

years. Fewer layers with more functionality are being designed, providing most

of the advantages of modularized code while avoiding the difficult problems

of laver definition and interaction.

Operating-System Simple Structure

Many commercial systems do not have well-defined structures. Frequently,
such operating systems started as small, simple, and limited systems and then
grew beyond their original scope. MS-DOS is an example of such a system. It was
originally designed and implemented by a few people who had no idea that it
would become so popular. It was written to provide the most functionality in the least space, so it was not divided into modules carefully.

instance, application programs are able to access the basic I/O routines

to write directly to the display and disk drives. Such freedom leaves MS-DOS

vulnerable to errant (or malicious) programs, causing entire system crashes

when user programs fail. Of course, MS-DOS was also limited by the hardware

of its era. Because the Intel 8088 for which it was written provides no dual

mode and no hardware protection, the designers of MS-DOS had no choice but

to leave the base hardware accessible.

Another example of limited structuring is the original UNIX operating

system. UNIX is another system that initially was limited by hardware functionality.

It 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, as shown in

Figure 2.11. 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 operating-system functions through system

calls. Taken in sum, that is an enormous amount of functionality to be combined

into one level. This monolithic structure was difficult to implement and

maintain.

Device Management

A process may need several resources to execute—main memory, disk drives,
access to files, and so on. If the resources are available, they can be granted,
and control can be returned to the user process. Otherwise, the process will
have to wait until sufficient resources are available.
The various resources controlled by the operating sysstem can be thought
of as devices. Some of these devices are physical devices (for example, tapes),
while others can be thought of as abstract or virtual devices (for example,
files). If there are multiple users of the system, the system may require us to
first request the device, to ensure exclusive use of it. After we are finished
with the device, we release it. These functions are similar to the open and
close system calls for files. Other operating systems allow unmanaged access
to devices. The hazard then is the potential for device contention and perhaps
deadlock, which is described in Chapter 7.
Once the device has been requested (and allocated to us), we can read,
write, and (possibly) reposition the device, just as we can with files. In fact,
the similarity between I/O devices and files is so great that many operating
systems, including UNIX, merge the two into a combined file-device structure.
In this case, a set of system calls is used on files and devices. Sometimes,
I/O devices are identified by special file names, directory placement, or file
attributes.
The UI can also make files and devices appear to be similar, even though
the underlying system calls are dissimilar. This is another example of the many
design decisions that go into building an operating system and user interface.

Graphical User Interfaces

A second strategy for interfacing with the operating system is through a userfriendly
graphical user interface or GUI. Rather than having users directly enter
commands via a command-line interface, a GUI allows provides a mouse-based
window-and-menu system as an interface. A GUI provides a desktop metaphor
where the mouse is moved 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 a menu that contains commands.
Graphical user interfaces first appeared due in part to research taking place
in the early 1970s at Xerox PARC research facility. The first GUI appeared on
the Xerox Alto computer in 1973. However, graphical interfaces became more
widespread with the advent of Apple Macintosh computers in the 1980s. The
user interface to the Macintosh operating system (Mac OS) has undergone
various changes over the years, the most significant being the adoption of
the Aqua interface that appeared with Mac OS X. Microsoft's first version
of Windows—version 1.0—was based upon a GUI interface to the MS-DOS
operating system. The various versions of Windows systems proceeding this
initial version have made cosmetic changes to the appearance of the GUI and
several enhancements to its functionality, including the Windows Explorer.
Traditionally, UNIX systems have been dominated by command-line interfaces,
although there are various GUI interfaces available, including the Common
Desktop Environment (CDE) and X-Windows systems that are common on commercial versions of UNIX such as Solaris and IBM's AIX system. However,
there has been significant development in GUI designs from various opensource
projects such as K Desktop Environment (or KDE) and the GNOME desktop
by the GNU project. Both the KDE and GNOME desktops rim on Linux and
various UNIX systems and are available under open-source licenses, which
means their source code is in the public domain.
The choice of whether to use a command-line or GUI interface is mostly
one of personal preference. As a very general rule, many UNIX users prefer
a command-line interface as they often provide powerful shell interfaces.
Alternatively, most Windows users are pleased to use the Windows GUI
environment and almost never use the MS-DOS shell interface. The various
changes undergone by the Macintosh operating systems provides a nice study
in contrast. Historically, Mac OS has not provided a command line interface,
always requiring its users to interface with the operating system using its GUI.
However, with the release of Mac OS X (which is in part implemented using a
UNIX kernel), the operating system now provides both a new Aqua interface
and command-line interface as well.
The user interface can vary from system to system and even from user
to user within a system. It typically is substantially removed from the actual
system structure. The design of a useful and friendly user interface is therefore
not a direct function of the operating system. In this book, we concentrate on
the fundamental problems of providing adequate service to user programs.
From the point of view of the operating system, we do not distinguish between
user programs and system programs.

Command Interpreter

Some operating systems include the command interpreter in the kernel. Others, such as Windows XP and UNIX, treat the command interpreter as a special program that is running when a job 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, there are several different shells a user may choose from including the Bourne shell, C shell, Bourne-Again shell, the Korn shell, etc. Most shells provide similar functionality with only minor differences; most users choose a shell based upon personal preference.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 MS-DOS and UNIX shells operate in this way. There are two general ways in which these commands can be implemented. In one approach, the command interpreter itself contains the code to execute the command. For example, a command to delete a file may cause the command interpreter to jump to a section of its code that sets up the parameters and makes the appropriate system call. In this case, the number of commands that can be given determines the size of the command interpreter, since each command requires its own implementing code. An alternative approach—used by UNIX, among other operating systems —implements most commands through system programs. In this case, the command interpreter does not understand the command in any way; it merely uses the command to identify a file to be loaded into memory and executed. Thus, the UNIX command to delete a file rm f i l e . t x t would search for a file called rm, load the file into memory, and execute it with the parameter f i l e . txt. The function associated with the rm command would be defined completely by the code in the file rm. In this way, programmers can add new commands to the system easily by creating new files with the proper names. The command-interpreter program, which can be small, does not have to be changed for new commands to be added.

Process Concept

A question that arises in discussing operating systems involves what to call all
the CPU activities. A batch system executes jobs, whereas a time-shared system
has user programs, or tasks. Even on a single-user system such as Microsoft
Windows, a user may be able to run several programs at one time: a word
processor, a web browser, and an e-mail package. Even if the user can execute only one program at a time, the operating system may need to suppoft its
own internal programmed activities, such as memory management. In many
respects, all these activities are similar, so we call all of them processes.
The terms job and process are used almost interchangeably in this text.
Although we personally prefer the term process, much of operating-system
theory and terminology was developed during a time when the major activity
of operating systems was job processing. It would be misleading to avoid
the use of commonly accepted terms that include the word job (such as job
scheduling) simply because process has superseded job.

Storage Management

provides a uniform, logical view of information storage. The operating system
abstracts from the physical properties of its storage devices to define a logical
storage unit, the file. The operating system maps files onto physical media and
accesses these files via the storage devices.

File-System Management


File management is one of the most visible components of an operating system.
Computers can store information on several different types of physical media.
Magnetic disk, optical disk, and magnetic tape are the most common. Each
of these media has its own characteristics and physical organization. Each
medium is controlled by a device, such as a disk drive or tape drive, that capacity', data-transfer rate, and access method (sequential or random).
A file is a collection of related information defined by its creator. Commonly,
files represent programs (both source and object forms) and data. Data files may
be numeric, alphabetic, alphanumeric, or binary. Files may be free-form (for
example, text files), or they may be formatted rigidly (for example, fixed fields).
Clearly, the concept of a file is an extremely general one.
The operating system implements the abstract concept of a file by managing
mass storage media, such as tapes and disks, and the devices that control them.
Also, files are normally organized into directories to make them easier to use-
Finally, when multiple users have access to files, it may be desirable to control
by whom and in what ways (for example, read, write, append) files may be
accessed.
The operating system is responsible for the following activities in connection
with file management:

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

Mass-Storage Management

As we have already seen, because main memory is too small to accommodate

all data and programs, and because the data that it holds are lost when power

is lost, the computer system must provide secondary storage to back up main

memory. Most modern computer systems use disks as the principal on-line

storage medium for both programs and data. Most programs—including

compilers, assemblers, word processors, editors, and formatters—are stored

on a disk until loaded into memory and then use the disk as both the source

and destination of their processing. Hence, the proper management of disk

storage is of central importance to a computer system. The operating system is

responsible for the following activities in connection with disk management:

• Free-space management
• Storage allocation
• Disk scheduling

Because secondary storage is used frequently, it must be used efficiently. The

entire speed of operation of a computer may hinge on the speeds of the disk

subsystem and of the algorithms that manipulate that subsystem.

There are, however, many uses for storage that is slower and lower in cost

(and sometimes of higher capacity) than secondary storage. Backups of disk

data, seldom-used data, and long-term archival storage are some examples. Magnetic tape drives and their tapes and CD and DVD drives and platters are

typical tertiary storage devices. The media (tapes and optical platters) vary

between WORM (write-once, read-many-times) and RW (read-write) formats.

Tertiary storage is not crucial to system performance, but it still must

be managed. Some operating systems take on this task, while others leave

tertiary-storage management to application programs. Some of the functions

that operating systems can provide include mounting and unmounting media

in devices, allocating and freeing the devices for exclusive use by processes,

and migrating data from secondary to tertiary storage.

Memory Management

Main memory is a large array of words or bytes, its own address. Main memory is a repository of quickly accessible data shared
by the CPU and I/O devices. The central processor reads instructions from main
memory during the instruction-fetch cycle and both reads and writes data from
main memory during the data-fetch cycle (on a Von Neumann architecture).
The main memory is generally the only large storage device that the CPU is able
to address and access directly. For example, for the CPU to process data from
disk, those data must first be transferred to main memory by CPU-generated
I/O calls. In the same way, instructions must be in memory for the CPU to
execute them.
For a program to be executed, it must be mapped to absolute addresses and
loaded into memory. As the program executes, it accesses program instructions
and data from memory by generating these absolute addresses. Eventually,
the program terminates, its memory space is declared available, and the next
program can be loaded and executed.
To improve both the utilization of the CPU and the speed of the computer's
response to its users, general-purpose computers must keep several programs
in memory, creating a need for memory management. Many different memorymanagement
schemes are used. These schemes reflect various approaches, and
the effectiveness of any given algorithm depends on the situation. In selecting a
memory-management scheme for a specific system, we must take into account
many factors—especially on the hardware design of the system. Each algorithm
requires its own hardware support.
The operating system is responsible for the following activities in connection
with memory management:

•  Keeping track of which parts of memory are currently being used and by whom
•  Deciding which processes (or parts thereof) and data to move into and out of memory
•  Allocating and deallocating memory space as needed

Process Management

program does nothing unless its instructions are executed by a CPU. A
program in execution, as mentioned, is a process. A time-shared user program
such as a compiler is a process. A word-processing program being run by an individual user on a PC is a process. A system task, such as sending ©utput
to a printer, can also be a process (or at least part of one). For now, you can
consider a process to be a job or a time-shared program, but later you will learn
that the concept is more general. As we shall see in Chapter 3, it is possible
to provide system calls that allow processes to create subprocesses to execute
concurrently.
A process needs certain resources—including CPU time, memory, files,
and I/O devices—to accomplish its task. These resources are either given to
the process when it is created or allocated to it while it is running. In addition
to the various physical and logical resources that a process obtains when it is
created, various initialization data (input) may be passed along. For example,
consider a process whose function is to display the status of a file on the screen
of a terminal. The process will be given as an input the name of the file and will
execute the appropriate instructions and system calls to obtain and display
on the terminal the desired information. When the process terminates, the
operating system will reclaim any reusable resources.
We emphasize that a program by itself is not a process; a program is a passive
entity, such as the contents of a file stored on disk, whereas a process is an active
entity. A single-threaded process has one program counter specifying the next
instruction to execute. (Threads will be covered in Chapter 4.) The execution
of such a process must be sequential. The CPU executes one instruction of the
process after another, until the process completes. Further, at any time, one
instruction at most is executed on behalf of the process. Thus, although two
processes may be associated with the same program, they are nevertheless
considered two separate execution sequences. A multithreaded process has
multiple program counters, each pointing to the next instruction to execute for
a given thread.
A process is the unit of work in a system. Such a system consists of a
collection of processes, some of which are operating-system processes (those
that execute system code) and the rest of which are user processes (those that
execute user code). All these processes can potentially execute concurrently—
by multiplexing the CPU among them on a single CPU, for example.
The operating system is responsible for the following activities in connection
with process management:

•  Creating and deleting both user and system processes
•  Suspending and resuming processes
•  Providing mechanisms for process synchronization
•  Providing mechanisms for process communication
•  Providing mechanisms for deadlock handling

Dual-Mode Operation

In order to ensure the proper execution of the operating system, we must be
able to distinguish between the execution of operating-system code and userdefined
code. The approach taken by most computer systems is to provide
hardware support that allows us to differentiate among various modes of
execution.
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 are able
to 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), it must transition from user to kernel mode to fulfill the request.
This is shown in Figure 1.8. 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.
The dual mode of operation provides us with the means for protecting the
operating system from errant users—and errant users from one another. We
accomplish this protection by designating some of the machine instructions that may cause harm as privileged instructions. The hardware allows privileged
instructions to be executed only in kernel mode. If an attempt is made to
execute a privileged instruction in user mode, the hardware does not execute
the instruction but rather treats it as illegal and traps it to the operating system.
The instruction to switch to user mode is an example of a privileged
instruction. Some other examples include I/O control, timer management, and
interrupt management. As we shall see throughout the text, there are many
additional privileged instructions.

We can now see the life cycle of instruction execution in a computer system.

Initial control is within the operating system, where instructions are executed

in kernel mode. When control is given to a user application, the mode is set to

user mode. Eventually, control is switched back to the operating system via an

interrupt, a trap, or a system call.

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 t r a p instruction, although some systems

(such as the MIPS R2000 family) have a specific syscall instruction.

When a system call is executed, it is 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 systemcall

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.

STRUCTURE AND FUNCTION

Acomputer is a complex system; contemporary computers contain millions of elementary
electronic components.How, then,can one clearly describe them?The key is to recognize
the hierarchical nature of most complex systems, including the computer
[SIMO96].Ahierarchical system is a set of interrelated subsystems, each of the latter, in
turn, hierarchical in structure until we reach some lowest level of elementary subsystem.
The hierarchical nature of complex systems is essential to both their design and
their description.The designer need only deal with a particular level of the system at
a time. At each level, the system consists of a set of components and their interrelationships.
The behavior at each level depends only on a simplified, abstracted characterization
of the system at the next lower level. At each level, the designer is
concerned with structure and function:
• Structure: The way in which the components are interrelated
• Function: The operation of each individual component as part of the structure
In terms of description, we have two choices: starting at the bottom and building
up to a complete description, or beginning with a top view and decomposing the
system into its subparts. Evidence from a number of fields suggests that the topdown
approach is the clearest and most effective [WEIN75].
The approach taken in this book follows from this viewpoint. The computer
system will be described from the top down.We begin with the major components of
a computer, describing their structure and function, and proceed to successively
lower layers of the hierarchy. The remainder of this section provides a very brief
overview of this plan of attack.

Function

Both the structure and functioning of a computer are, in essence, simple. Figure 1.1

depicts the basic functions that a computer can perform. In general terms, there are

only four:

• Data processing

• Data storage

• Data movement

• Control

The computer, of course, must be able to process data.The data may take a wide

variety of forms, and the range of processing requirements is broad. However, we shall

see that there are only a few fundamental methods or types of data processing.

It is also essential that a computer store data. Even if the computer is processing

data on the fly (i.e., data come in and get processed, and the results go out immediately),

the computer must temporarily store at least those pieces of data that are being worked on at any given moment.Thus, there is at least a short-term data storage function.

Equally important, the computer performs a long-term data storage function.

Files of data are stored on the computer for subsequent retrieval and update.

The computer must be able to move data between itself and the outside world.

The computer’s operating environment consists of devices that serve as either sources or destinations of data.When data are received from or delivered to a device

that is directly connected to the computer, the process is known as input–output

(I/O), and the device is referred to as a peripheral.When data are moved over longer

distances, to or from a remote device, the process is known as data communications.

Finally, there must be control of these three functions. Ultimately, this control

is exercised by the individual(s) who provides the computer with instructions.Within

the computer, a control unit manages the computer’s resources and orchestrates the

performance of its functional parts in response to those instructions.

At this general level of discussion, the number of possible operations that can

be performed is few. Figure 1.2 depicts the four possible types of operations. The

computer can function as a data movement device (Figure 1.2a), simply transferring

data from one peripheral or communications line to another. It can also function as

a data storage device (Figure 1.2b), with data transferred from the external environment

to computer storage (read) and vice versa (write). The final two diagrams

show operations involving data processing, on data either in storage (Figure 1.2c) or

en route between storage and the external environment (Figure 1.2d).

The preceding discussion may seem absurdly generalized. It is certainly possible,

even at a top level of computer structure, to differentiate a variety of functions,

but, to quote [SIEW82],

ORGANIZATION AND ARCHITECTURE

In describing computers, a distinction is often made between computer architecture and
computer organization. Although it is difficult to give precise definitions for these
terms, a consensus exists about the general areas covered by each (e.g., see [VRAN80],
[SIEW82], and [BELL78a]); an interesting alternative view is presented in [REDD76].
Computer architecture refers to those attributes of a system visible to a programmer
or, put another way, those attributes that have a direct impact on the logical
execution of a program. Computer organization refers to the operational units
and their interconnections that realize the architectural specifications. Examples of
architectural attributes include the instruction set, the number of bits used to represent
various data types (e.g., numbers, characters), I/O mechanisms, and techniques
for addressing memory. Organizational attributes include those hardware details
transparent to the programmer, such as control signals; interfaces between the computer
and peripherals; and the memory technology used.
For example, it is an architectural design issue whether a computer will have a
multiply instruction. It is an organizational issue whether that instruction will be implemented
by a special multiply unit or by a mechanism that makes repeated use of
the add unit of the system.The organizational decision may be based on the anticipated
frequency of use of the multiply instruction, the relative speed of the two approaches,
and the cost and physical size of a special multiply unit.
Historically, and still today, the distinction between architecture and organization
has been an important one. Many computer manufacturers offer a family of
computer models, all with the same architecture but with differences in organization.
Consequently, the different models in the family have different price and performance
characteristics. Furthermore, a particular architecture may span many years
and encompass a number of different computer models, its organization changing
with changing technology. A prominent example of both these phenomena is the IBM System/370 architecture. This architecture was first introduced in 1970 and included
a number of models. The customer with modest requirements could buy a
cheaper, slower model and, if demand increased, later upgrade to a more expensive,
faster model without having to abandon software that had already been developed.
Over the years, IBM has introduced many new models with improved technology to
replace older models, offering the customer greater speed, lower cost, or both.These
newer models retained the same architecture so that the customer’s software investment
was protected. Remarkably, the System/370 architecture, with a few enhancements,
has survived to this day as the architecture of IBM’s mainframe product line.
In a class of computers called microcomputers, the relationship between architecture
and organization is very close. Changes in technology not only influence organization
but also result in the introduction of more powerful and more complex
architectures. Generally, there is less of a requirement for generation-to-generation
compatibility for these smaller machines. Thus, there is more interplay between organizational
and architectural design decisions. An intriguing example of this is the
reduced instruction set computer (RISC), which we examine in Chapter 13.
This book examines both computer organization and computer architecture.
The emphasis is perhaps more on the side of organization. However, because a computer
organization must be designed to implement a particular architectural specification,
a thorough treatment of organization requires a detailed examination of
architecture as well.
Source : Computer Organization and Architecture Designing for Performance