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.