UNIX
Operating System Characteristics
by Rebecca Orton
for Operating Systems class
taught by Professor Wayne
UNIX System
The characteristics covered
in the UNIX system are process management, interprocess communication, memory
management and CPU scheduling, secondary storage management, input/output
management, and file management.
Process Management
When the kernel copies a
program into memory and begins its execution, this executing program is called
a process. A distinction is made between a program that is kept in a file on
the disk and a process that is in memory. (Kochan and Wood, 1985, pg. 43). A
process is represented by a process structure and a user structure (U structure) (S ilberschatz and Peterson, 1988, pg.
507). These are the two data structures under the control of the kernel that
are used to store information about a process. The information stored in the
process table includes the process identifier (pid), user-id, the size of the
process, the location, and whether the process is swapped in or out. When a
process is in primary storage it has its u structure with it. The u structure
contains information about the process that is needed only when the process is
resident or swapped in. The u structure stores the user—id used for file access,
and the registers that are saved when the process is blocked (Keller, 1988, pg.
229).
A new process is produced by
the fork call. The fork call creates two almost identical process with the same
variables and values (Silberschatz and Peterson, 1988, pg. 472). The fork call
allocates a new process structure with a new pid for the child process and the
u structure is copied (Silberschatz and Peterson, 1988, pg. 481). But parent
and child processes do not share their memory (Keller, 1988, pg. 236).
The exec call is used to
replace the current process with a different process (Kochan and Wood, 1985,
pg. 244). The exec call initiates execution of the process along with its
arguments. Unlike other commands that are executed as new processes, the exec
call doesn’t create a new process. Once the exec call starts execution, there
is no return to the process that initiated the exec call (Kochan and Wood,
1985, pg. 368). The exec call doesn’t create a new process structure or u
structure, rather the executable text and data of the process are replaced
(Silberschatz and Peterson, 1988, pg. 482). Both parent and child processes
continue execution at the instruction after the fork call with only one
difference. The return code for the fork call is zero for the child process,
and the pid of the child is returned to the parent (Silberschatz and Peterson,
1988, pg. 472) Memory is allocated to
the child process. If the child process grows and there is insufficient memory
available, then memory large enough to contain the expanding process is
allocated by using a first—fit strategy. If there is none, then secondary
storage is allocated, and the process is swapped out. The process will be
swapped in when enough memory becomes available again (Keller, 1988, pg. 236).
A process may terminate by
using the exit call. Its parent process may wait for that event by using the
wait call (Silberschatz and Peterson, 1988, pg. 473). A waiting parent process
is notified by the exit call in the child process that the child has finished (Keller,
1988, pg. 237). When a process completes execution, it returns an exit status.
The exit status is an integer indicating whether or not the process
successfully ran. An exit status of zero indicates that a process succeeded,
and a nonzero status indicates that it failed. The execution of the exit call
causes the current process to be immediately terminated (Kochan and Wood, 1985,
pg. 369). The wait call causes the suspension of a process until the process
finished executing. If the process waited for is not specified, then the
process waits for all child processes to finish executing (Kochan and Wood,
1985, pg. 384).
All user processes are
descendants of one original process, mit with the
pid of 1 (Silberschatz and Peterson, 1988, pg. 473). The main process is the
shell. The shell major responsibilities are process execution, environment
control, and pipelines (Kochan and Wood, 1985, pg. 46). The kernel is hidden by
the shell that surrounds it. The kernel’s major responsibilities are process
management, input/output management, and file management (Keller, 1988, pg.
228). A subshell is an new shell that is executed by the login shell in order
to run a process. Whenever a new shell runs, it runs in its own environment,
with its own set of local variables (Kochan and Wood, 1985, pg. 222). If the
command line sequence is terminated by an ampersand character “&“ before the end of line character, then the process is
run asynchronously in the background. The process number is displayed at the
terminal when this is entered (Kochan and Wood, 1985, pg. 357).
Interprocess Communication
Two processes can only
communicate with each other through temporary files or by knowing beforehand
each other’s pid. Pids are allocated sequentially starting at 1 at system
startup. The control structures in the operating system are tree structured so
that there is limited communication up and down the tree, from parent to child
and vice versa (Keller, 1988, pg. 242). Signals are like software interrupts.
They inform a process that an error occurred, and most can be ignored (Keller,
1988, pg. 237).
Pipes is another form of
communication between processes. They may be created before the fork call, and
the endpoints are then set up between the fork process and the exec process
(Silberschatz and Peterson, 1988, pg. 473). A pipe accepts data from another
process as they are produced. The pipe is a sink into which data is sent for
processing. Data written into one end of the pipe is read from the other end.
The synchronization, scheduling, and buffering of pipes are handled
automatically (Keller. pg. 214). A pipe can be considered as a reliable
unidirectional byte stream between two processes (Silberschatz and Peterson,
1988, pg. 501). Pipes process data in FIFO order while the process that
initiated the pipe continues execution and production of data (Keller, pg.
145). A pipeline is essentially queues of bytes between processes (Silberschatz
and Peterson, 1988, pg. 473). The pipe connects the standard output of one
process to the standard input of another process (Keller, 1988, pg. 214). In a
pipeline, the exit status comes from the last command in the pipe (Kochan and
Wood, 1985, pg. 142). A pipe is an open file with a fixed size connecting two
processes and is accessed by a file descriptor, like an ordinary file
(Silberschatz and Peterson, 1988, pg. 473). It is implemented as an ordinary
file, with the following exceptions. There is no permanent name in the file
system, when it is created by the pipe call. If the pipeline was interrupted abnormally,
temporary files with the extension of $$$ might be
found in the file system. If a process attempts to write to a full pipe, the
process is suspended. Once all data previously written into the pipe is read
out, then writing continues at the beginning of the file. Pipes are not really
true circular buffers (Silberschatz and Peterson, 1988, pg. 501). A filter
which is related to pipes, reads the standard input, selects from it or
modifies it and passes the output as standard output (Keller, pg. 215).
Memory Management and CPU
scheduling
Memory management is a first
fit variable partition strategy with swapping. Other systems may have
sophisticated algorithms for dealing with memory problems, but Unix just does a
controlled crash, and tries instead to prevent problems (Silberschatz and
Peterson, 1988, pg. 467-468). Pre—virtual memory systems used swapping solely
to handle memory contention. Without virtual memory, a process larger than than
non—kernel main memory cannot be run at all (Silberschatz and Peterson, 1988,
pg. 484). Many USG systems, particularly System V, currently use the swapping
scheme. Berkeley systems rely on paging for memory contention management and
only rely secondarily on swapping (Silberschatz and Peterson, 1988, pg. 485).
CPU scheduling is a combined
priority and round-robin strategy with dynamically computed priorities.
Processes are given small time quantums by a priority algorithm. For CPU bound
processes, scheduling reduces to round—robin (Silberschatz and Peterson, 1988,
pg. 507). CPU scheduling benefits interactive processes (Silberschatz and
Peterson, 1988, pg. 482), and CPU bound processes can fill the gabs created by
the input/output bound processes (Keller, 1988, pg. 235). Every process has a
scheduling priority, and large numbers are low priority. Processes doing disk
input/output have negative priorities and cannot be killed by signals. The more
CPU time a process accumulates, the more positive its priority becomes.
Negative feedback makes it difficult for a process to take over the CPU. There
is no preemption of one process by another, and aging is used to prevent
individual starvation. Newer systems use a 1/10th of a second time quantum
while earlier ones use a full second (Silberschatz and Peterson, 1988, pg. 482—483).
If there is too much
contention, processes are swapped out until enough memory is available. The
system data segment includes the u structure and the kernel stack. The user
data segment includes non—sharable pure text, data and the stack. Both the u
structure and the user data segment are swapped in together (Keller, 1988, pg.
229). All of these are kept in contiguous memory to keep swapping efficient but
some serious external fragmentation of memory may result. A sharable text
segment does not have to be swapped out, because it is read—only, nor does a
sharable text segment have to be swapped in for a process when another instance
is already in memory. Less swap traffic results, and is one of the main reasons
for keeping track of sharable text segments. Another reason is the smaller
amount of memory needed for multiple processes using the same text segments
(Silberschatz and Peterson, 1988, pg. 484—485). When a process executes
read—only code, reentrant code, or sharable pure text, a text table linked to
the process table is used. The process table uses the text table to access a
separate memory region containing read—only code (Keller, 1988, pg. 229).
Decisions on which processes
to swap in or out are made by the swapper scheduler, process 0. The scheduler
checks at least once every four seconds for processes to swap in or out
(Silberschatz and Peterson, 1988, pg. 485). The switch between user and kernel
modes due to a clock interrupt is a manifestation of context switching. The
active process may be suspended or blocked. The active process may have
initiated a call such as an input/output request or the scheduler may have
required the process to be suspended. Then the active process is suspended, and
it is marked as suspended. The current program counter is saved on the stack,
and other process data including register contents are saved. Finally, the new
program counter address associated with the processing of the input/output
request is placed in the current program counter and executed. This sequence is
reversed in order to restore the suspended process when the input/output
request has been completed by the system (Keller, pg. 232). A process is more
likely to be swapped out if it is idle, has been in memory a long time, or has
a large size. If no easy victims are found, other processes are picked by age.
A process is more likely to be swapped in if it has been swapped out a long
time, or has a small size. To prevent endless swapping, a process is not
allowed to be swapped out if it has not been in memory for a set amount of
time. If there are no current processes to swap out, then the process table is
searched for another process that deserves to be brought in. The process picked
is determined by how small it is and how long it has been swapped out. If there
is not enough memory available for the picked process, processes are swapped
out until there is (Silberschatz and Peterson, 1988, pg. 485).
When a process decides to
release the CPU, it goes to sleep on an event. The sleep call is used. It takes
as an argument the address of a kernel structure related to an event that the
process wants to wakeup on (Silberschatz and Peterson, 1988, pg. 483). The
event being waited for is noted in the process table (Keller, 1988, pg. 235).
When a kernel process is suspended, the reason for its suspension is stored in
the process table, coded as an integer. This integer then represents an event.
The event uses the kernel stack of the system process currently executing, and
that system process is responsible for waking up the suspended processes for
that event.
When the event occurs, the
system process involved issues the wakeup call which takes as an argument the
address corresponding to the event (Silberschatz and Peterson, 1988, pg. 483).
Then the process table is searched for processes waiting for that event
(Keller, 1988, pg. 238). All the processes sleeping on the same address are put
the ready queue. But the scheduler picks the process that actually does run.
The sleep call also takes as a second argument the scheduling priority. If the
priority argument is negative then the sleep call also prevents the process
from being prematurely awakened by an exceptional event, such as signal. If a
process decides to sleep on an event on account of a flag that it checked, for
example, and the event occurs before the process can execute the sleep call,
then the process may sleep forever. Raising the hardware processor priority
during the processes’ critical section prevents processes from sleeping
forever. No events can occur, and only the process desiring the event can run
until it is sleeping. The hardware processor priority is used to protect
critical regions throughout the kernel and causes the most difficulty in moving
Unix to machines with multiple processors (Silberschatz and Peterson, 1988, pg.
483—484).
Secondary Storage Management
Direct access and sequential
access are supported through system calls (Silberschatz and Peterson, 1988, pg.
507). The file system is a directed graph, specifically a hierarchical tree structure
(Keller, 1988, pg. 218). Each of the nodes in the tree is called an mode, which
is a file definition. The modes on the disk contain a number of block addresses
for accessing a file, including a indirect address, one double indirect
address, and yet another triple indirect address (Keller, 1988, pg. 220). The
kernel uses a logical device and a mode number pair to identify a file. The
logical device number defines the file system involved. A bit used in the mode
structure indicates if the mode has a mounted file system. The mode structure
is an in—core copy of the mode on the disk. A reference to a file causes a
search through the mount table to find the device number of the mounted device.
The device number is used to find the mode of the root directory of the mounted
file system~ Finally that mode is used to find the file. The actual number of
file systems on a drive varies according to the size of the disk. The purpose
of the computer system as a whole is also considered, for example whether it is
single user or multi—user. The root file system is always available. Others may
be mounted or in other words, integrated into the directory hierarchy of the
root file system (Silberschatz and Peterson, 1988, pg. 492).
The disk on which the files
reside is structured with a boot block, superblock, mode list, and the data
blocks (Keller, 1988, pg. 220). The super-block contains the file system header
and the static parameters of the file system, for example the free space
parameters. The superblock also includes the total size of the file system, the
number of modes, and the block size of the data blocks. The superbiock of each
mounted file system is kept in memory for accessing speed. For example, every
30 seconds, the super-block is written to disk, to keep the in-core and disk
copies synchronized. This is done by using the sync call. When system or
hardware bugs destroy the in—core superblock during a system crash then the
free block list is lost. The recovery of the free block linked list accessed by
the superbiock is difficult because it requires a long examination of all
blocks in the file system (Silberschatz and Peterson, 1988, pg. 493-495).
Input/Output Management
The details of input/output
devices are hidden from the rest of the kernel. The input/output system
consists of buffer caching, general device driver code, and specific drivers
for hardware devices. The device drivers are the implementation of the details
of specific devices (Silberschatz and Peterson, 1988, pg. 496—497). The devices
are accessed using special device files within the file system (Keller, 1988,
pg. 218). A special file is an interface between processes and the kernel. Each
device is connected to a special file (Keller, 1988, pg. 219). modes are
associated with special files. The major and minor device numbers, and the
class are stored in the mode (Keller, 1988, pg. 225). Device drivers are
accessed by one of two arrays or tables of entry points. One is for block
devices, and the other is for character devices. The major device number is
used as an index to find an entry into the appropriate device driver
(Silberschatz and Peterson, 1988, pg. 497-498). The minor device number selects
a device out of a group of identical physical devices (Keller, 1988, pg. 226).
It is used by the device driver to interpret a device. A device driver module
is connected to the rest of the kernel only by the entry points, and by the use
of the common buffering systems. This separation of device drivers is an aid to
portability and configuration (Silberschatz and Peterson, 1988, pg. 498). The
entry point tables contain pointers used to access the buffers for devices.
Buffers are not permanently assigned but are allocated as needed from a pool of
empty buffers. For block devices, there is in the block table code, routines
for optimizing reads and writes (Keller, 1988, pg. 226).
The block buffer cache
consists of buffer headers, each of which points to a piece of physical memory
as well as a device number and a block number on the device. The buffer headers
are kept in linked lists. The buffers in these lists are hashed by device and
block number to make searches efficient. When a block is wanted from a device
during a read, the cache is searched first. If the block is found, then it is
used and input/output transfer becomes unnecessary. If the block isn’t found, a
buffer is picked from the list of empty buffers. Then the device and block
numbers associated with the empty buffer are updated, memory is found for it,
and new data is transferred into it from the device. If there are no empty
buffers, the least recently used buffer is written to its device and then it is
used. On a write, if the block is already in the buffer cache, the new data is
written to the buffer. The buffer header is marked to indicate the buffer has
been modified, and that input/output doesn’t have to be done immediately. The
data will be written when the buffer is selected again for different data. If
the block is not found in the buffer cache, an empty buffer is picked the same
way as with a read operation and data is transferred to the buffer. Writes are
forced for dirty buffer blocks once in a while in order to minimize potential
inconsistencies in the file system if a system crash occurs (Silberschatz and
Peterson, 1988, pg. 498).
Some devices, such as
magnetic tapes, require blocks to be written in sequential order, so
synchronous writes of buffers to these devices are forced. Directory blocks are
also written synchronously. When data from a disk file is read, some read—
ahead occurs, but reads are closer to asynchronous than writes (Silberschatz
and Peterson, 1988, pg. 499). Read-ahead usually keep the buffers filled.
Writing is often delayed and results in less physical input/output. A system
crash may result in the loss of data in the buffers that have not been
transferred physically even though the processes associated with the data may
have terminated (Keller, 1988, pg. 225). The sync call is used to start
flushing all the buffers out.
The terminal is the standard
input, output, and error (Kochan and Wood, pg. 33). Terminal drivers use
character buffers (Silberschatz and Peterson, 1988, pg. 500). C-lists are
buffers smaller than those of the block buffer cache (Silberschatz and
Peterson, 1988, pg. 497) and the blocks of characters are kept in linked links.
A write call to a terminal puts characters on a queue for the device. An
transfer is initiated, and interrupts cause the outputting to the device of
characters from the queue. Further transfers occur on subsequent interrupts. Input
is similarly interrupt driven as well (Silberschatz and Peterson, 1988, pg.
500). Terminal input/output differs from other character input/output in that
some preprocessing of the queue occurs. For example erase editing to
incorporate changes the user has made during the time the line was entered is
performed (Keller, 1988, pg. 225). Terminal drivers support two input queues,
and conversion from the raw queue to the canonical queue is triggered by an end
of line character on the raw queue (Silberschatz and Peterson, 1988, pg. 500).
File Management
All files are defined to be
simply a stream of bytes and each byte is individually addressable by its
offset from the start of the file. Since the logical record is one byte, the
file system automatically packs and unpacks bytes into physical disk blocks
(Silberschatz and Peterson, 1988, pg. 351). A file has no intrinsic structure,
and the user is the one that imposes a structure on it, if any. An Unix file
uses less space than a file in a file system that stores fixed length records
because space is not wasted by filled-in blanks. Time is used to keep a count
of the number of characters processed in variable — length records. Unix’s general purpose process tools
would be more difficult to implement if the files existed in a variety of forms
(Keller, 1988, pg. 218).
Access to a file can be given
at three levels of permission: read (r), write (w), and execute (x) (Keller,
1988, pg. 219). For the file permissions, a domain such as owner, group, and
public, is associated with the user. Domain switching is when the user
identification is changed temporarily. Associated with each file are an owner
identification and domain bit (Silberschatz and Peterson, 1988, pg. 394-395).
When a user “Albert” with a userid “A” starts executing a file owned by “Barry”
with a user-id of “B”, the user-id of “Albert” is set to “B”,provided that the
associated domain bit of “Barry’s” file set to on. After the file finished
executing, then “Albert’s” user-id is reset to “A”. There are actually two user
identifiers used by the kernel. The effective user identifier is the identifier
used in determining file access permissions. The real user identifier is left
alone. This allows certain processes like mail to have higher privileges while
still being executable by users (Silberschatz and Peterson, 1988, pg. 473).
There are both absolute
pathnames and relative pathnames. Absolute pathnames start at the root
directory of the file system and are distinguished by a slash at the beginning
of the pathname. Relative pathnames begin in the current directory and is an
attribute carried within the process accessing the pathnaine (Silberschatz and
Peterson, 1988, pg. 470). Always associated with each user of the system is a
home directory. When a user logs into the system, the user is placed
automatically into the home directory (Kochan and Wood, 1985, pg. 10). The user
refers to a file through the pathname, while the file system refers to the file
definition through the mode. A file may be known by more than one name in more
than one directory. Such multiply names are known as links and all links are
treated equally (Silberschatz and Peterson, 1988, pg. 470). An empty directory
at any level can be replaced by a new branch corresponding to the files on a newly
mounted disk volume. Once the volume is incorporated into the file system, its
physical identity is lost. To find out where files actually reside is difficult
and file system cross-linkings are prohibited as a result (Keller, 1988, pg.
219).
The kernel maps the pathnaine
to an mode through the directories (Silberschatz and Peterson, 1988, pg. 491).
Directories are files and can be recorded in other directories higher up in the
file system (Keller, pg. 215). A directory contains only the filename and a reference
number. More detailed information is contained in the mode for a file, such as
user—id, protection status, disk block addresses where the file is stored, file
size, and other information. Inodes are stored in i—lists and the offset of the
modes from the start of the i-list is the modes’ i—number, which is the
reference number stored in the directory (Keller, 1988, pg. 220).
When a file is opened during
a open call, the file’s mode is fetched and placed in the system mode table. A
pointer to the mode is placed in the allocated file structure. A second pointer
to the mode is placed in the system file table. Finally, a third pointer to the
entry of the system file table is placed in the u structure for the process.
The system file table holds the file pointer because the file pointer of a
sharable file cannot reside in the mode table nor in the open file section of
the process table (Keller, 1988, pg. 223). In other words, the file descriptors
refer to the file structures (Silberschatz and Peterson, 1988, pg. 491). The
file descriptors are the reference numbers of the files in the system file
table. The entries in the system table contain pointers to the corresponding
modes for the files in the system mode table (Keller, 1988, pg. 222). The file
descriptors index a open file table for the current processes in the process
table. The entries in the open file table contain pointers to file structures.
The file structures contain pointers to the modes (Silberschatz and Peterson,
1988, pg. 491). The file structures contain the offsets. File structures are
inherited by the child process after a fork, so some processes may have the
same offset into a file. The mode structures pointed to by the file structures
are allocated out of a fixed — length table. The in—core modes
have a few extra fields, namely a reference count of how many file structures
are pointing at it. The file structures have a similar reference count for how
many modes refer to it (Silberschatz and Peterson, 1988, pg. 491—492).
The locations of specific
files and directories in the file system have been defined by programmers, but
the kernel actually depends only on the existence of the directory /etc/init,
which is used to initialize terminal processes (Silberschatz and Peterson,
1988, pg. 470). The root directory contains special purpose subdirectories
called dev, bin, lib, etc, tmp and usr. The dev subdirectory is for special
files for devices. The bin subdirectory is for executable utility programs. The
lib subdirectory is for libraries of system utilities, the etc subdirectory is
for restricted system data, for example the algorithmic password file resides
here. The tmp subdirectory is for temporary files used by the system utilities,
and the usr directory contains all the user subdirectories, and other less used
subdirectories such as bin, tmp, dict which contains wordlists and spell
checkers, and the man subdirectory which contains the full Unix programmer’s
manual text files (Keller, 1988, pg. 216). Files can be created, opened, read,
written, closed, and unlinked. For manipulating device parameters, there is an
additional system call, ioctl, standing for input/output control (Silberschatz
and Peterson, 1988, pg. 472).
In summary, the Unix system
uses swapping and priorities with round robin scheduling to manage parent and
child processes, even though there is limited interprocess communications. The
management of secondary storage, input/output, and files are interrelated and
even combined. The conclusion of the Unix system characteristics is that it is
flexible and generic, perfect for programmers.
References
Keller, Laurie S. Communicating
with and Controlling the Computer . New York, London, Toronto,
Sydney, Tokyo: Prentice Hall International Ltd., 1988.
Kochan, Stephen G., and
Patrick H. Wood. Unix Shell Programming. Hasbrouck Heights, NJ,
Berkeley, CA: Hayden Book Company, 1985.
Silberchatz, Abraham, and
James L. Peterson. Operating System Concepts. Reading, MA, Menlo Park,
CA, New York, Don Mills, Ontario, Wokingham, England, Amsterdam, Bonn, Sydney,
Singapore, Tokyo, Madrid, San Juan: Addison-Wesley Publishing Company, 1988.