# To unbundle, run this file echo p.mac sed 's/.//' >p.mac <<'//GO.SYSIN DD p.mac' -.de P1 -.DS -.. -.de P2 -.DE -.. -.de UL -.lg 0 -.if n .ul -\%\&\\$3\f3\\$1\fR\&\\$2 -.lg -.. -.de UC -\&\\$3\s-1\\$1\\s0\&\\$2 -.. -.de IT -.lg 0 -.if n .ul -\%\&\\$3\f2\\$1\fR\&\\$2 -.lg -.. -.de SP -.sp \\$1 -.. //GO.SYSIN DD p.mac echo p1 sed 's/.//' >p1 <<'//GO.SYSIN DD p1' -.ds n \s+2 -.hw above-mentioned -.ds s \s-2 -.ds m \v'-.3'.\v'.3' -.TL -The UNIX -Time-Sharing System\f1\s10\v'-.2n'*\v'.2n'\s0\fP -.AU -D. M. Ritchie and K. Thompson -.AB -.FS -* Copyright 1974, -Association for Computing Machinery, Inc., -reprinted by permission. -This is a revised version of an article -that appeared in Communications of the \*sACM\*n, -.IT 17 , -No. 7 (July 1974), pp. 365-375. -That article was a -revised version of a paper presented -at the Fourth \*sACM\*n Symposium on Operating -Systems Principles, -\*sIBM\*n Thomas J. Watson Research Center, -Yorktown Heights, -New York, -October 15-17, 1973. -.FE -.UX -is a general-purpose, multi-user, interactive -operating system for the larger Digital Equipment Corporation -\*sPDP\*n-11 and -the Interdata 8/32 computers. -It offers a number of features -seldom found even in larger operating -systems, including -.IP i -A hierarchical file system incorporating -demountable volumes, -.IP ii -Compatible file, device, and inter-process I/O, -.IP iii -The ability to initiate asynchronous processes, -.IP iv -System command language selectable on a per-user basis, -.IP v -Over 100 subsystems including a dozen languages, -.IP vi -High degree of portability. -.LP -This paper discusses the nature -and implementation of the file system -and of the user command interface. -.AE -.NH -INTRODUCTION -.PP -There have been four versions of -the -.UX -time-sharing system. -.hy 12 -The earliest (circa 1969-70) ran on -the Digital Equipment Corporation \*sPDP\*n-7 and -9 computers. -The second version ran on the unprotected -\*sPDP\*n-11/20 computer. -The third incorporated multiprogramming and ran -on the \*sPDP\*n-11/34, /40, /45, /60, and /70 computers; -it is the one described in the previously published version -of this paper, and is also the most widely used today. -.hy 14 -This paper describes only the -fourth, current -system that runs on the \*sPDP\*n-11/70 and the -Interdata 8/32 computers. -In fact, the differences among the various systems is -rather small; -most of the revisions made to the originally published version of this -paper, -aside from those concerned with style, -had to do with details of the implementation of the file system. -.PP -Since -\*sPDP\*n-11 -.UX -became operational -in February, 1971, -over 600 installations have been put into service. -Most of them are engaged in applications such as -computer science education, -the preparation and formatting of documents -and other textual material, -the collection and processing of trouble data -from various switching machines within the Bell System, -and recording and checking telephone service -orders. -Our own installation is used mainly for research -in operating systems, languages, -computer networks, -and other topics in computer science, and also for -document preparation. -.PP -Perhaps the most important achievement of -.UX -is to demonstrate -that -a powerful operating system for interactive use -need not be expensive either in equipment or in human -effort: -it -can run on hardware costing as little as $40,000, and -less than two man-years were spent on the main system -software. -We hope, however, that users find -that the -most important characteristics of the system -are its simplicity, elegance, and ease of use. -.PP -Besides the operating system proper, some major programs -available under -.UX -are -.DS -.nf -C compiler -Text editor based on \*sQED\*n -.[ -qed lampson -.] -Assembler, linking loader, symbolic debugger -Phototypesetting and equation setting programs -.[ -cherry kernighan typesetting mathematics cacm -.] -.[ -kernighan lesk ossanna document preparation bstj -%Q This issue -.] -.fi -.in +3n -.ll -5n -.ti -3n -Dozens of languages including -Fortran 77, Basic, Snobol, \*sAPL\*n, Algol 68, M6, \*sTMG\*n, Pascal -.in -.ll -.DE -There is a host of maintenance, utility, recreation and novelty programs, -all written locally. -The -.UX -user community, which numbers in the thousands, -has contributed many more programs and languages. -It is worth noting that the system is totally self-supporting. -All -.UX -software is maintained on -the -system; -likewise, this paper and all other -documents -in this issue -were generated and formatted by the -.UX -editor and text formatting -programs. -.SH -II. HARDWARE AND SOFTWARE ENVIRONMENT -.PP -The \*sPDP\*n-11/70 on which the Research -.UX -system is installed is a 16-bit -word (8-bit byte) computer with 768K bytes of core memory; -the system kernel -occupies 90K bytes -about equally divided between code -and data tables. -This system, however, includes a very large number of -device drivers -and enjoys a generous allotment -of space for I/O buffers and system tables; -a minimal system capable of running the software -mentioned above can -require as little as 96K bytes -of core altogether. -There are even larger installations; -see the description of the -\*sPWB/UNIX\*n systems, -.[ -dolotta mashey workbench software engineering -.] -.[ -dolotta haight mashey workbench bstj -%Q This issue -.] -for example. -There are also much smaller, though somewhat restricted, -versions of the system. -.[ -lycklama microprocessor bstj -%Q This issue -.] -.PP -Our own \*sPDP\*n-11 has two -200-Mb moving-head disks -for file system storage and swapping. -There are 20 variable-speed -communications interfaces -attached to 300- and 1200-baud data sets, -and an additional 12 communication lines -hard-wired to 9600-baud terminals and -satellite computers. -There are also several 2400- and 4800-baud -synchronous communication interfaces -used for machine-to-machine file transfer. -Finally, there is a variety -of miscellaneous -devices including -nine-track magnetic tape, -a line printer, -a voice synthesizer, -a phototypesetter, -a digital switching network, -and a chess machine. -.PP -The preponderance of -.UX -software is written in the -abovementioned C language. -.[ -c programming language kernighan ritchie prentice-hall -.] -Early versions of the operating system were written in assembly language, -but during the summer of 1973, it was rewritten in C. -The size of the new system was about one-third greater -than that of the old. -Since the new system not only became much easier to -understand and to modify but also -included -many functional improvements, -including multiprogramming and the ability to -share reentrant code among several user programs, -we consider this increase in size quite acceptable. -.SH -III. THE FILE SYSTEM -.PP -The most important role of -the system -is to provide -a file system. -From the point of view of the user, there -are three kinds of files: ordinary disk files, -directories, and special files. -.SH -3.1 Ordinary files -.PP -A file -contains whatever information the user places on it, -for example, symbolic or binary -(object) programs. -No particular structuring is expected by the system. -A file of text consists simply of a string -of characters, with lines demarcated by the newline character. -Binary programs are sequences of words as -they will appear in core memory when the program -starts executing. -A few user programs manipulate files with more -structure; -for example, the assembler generates, and the loader -expects, an object file in a particular format. -However, -the structure of files is controlled by -the programs that use them, not by the system. -.SH -3.2 Directories -.PP -Directories provide -the mapping between the names of files -and the files themselves, and thus -induce a structure on the file system as a whole. -Each user has a directory of his own files; -he may also create subdirectories to contain -groups of files conveniently treated together. -A directory behaves exactly like an ordinary file except that it -cannot be written on by unprivileged programs, so that the system -controls the contents of directories. -However, anyone with -appropriate permission may read a directory just like any other file. -.PP -The system maintains several directories -for its own use. -One of these is the -.UL root -directory. -All files in the system can be found by tracing -a path through a chain of directories -until the desired file is reached. -The starting point for such searches is often the -.UL root . -Other system directories contain all the programs provided -for general use; that is, all the -.IT commands . -As will be seen, however, it is by no means necessary -that a program reside in one of these directories for it -to be executed. -.PP -Files are named by sequences of 14 or -fewer characters. -When the name of a file is specified to the -system, it may be in the form of a -.IT path -.IT name , -which -is a sequence of directory names separated by slashes, ``/\^'', -and ending in a file name. -If the sequence begins with a slash, the search begins in the -root directory. -The name -.UL /alpha/beta/gamma -causes the system to search -the root for directory -.UL alpha , -then to search -.UL alpha -for -.UL beta , -finally to find -.UL gamma -in -.UL beta . -.UL \&gamma -may be an ordinary file, a directory, or a special -file. -As a limiting case, the name ``/\^'' refers to the root itself. -.PP -A path name not starting with ``/\^'' causes the system to begin the -search in the user's current directory. -Thus, the name -.UL alpha/beta -specifies the file named -.UL beta -in -subdirectory -.UL alpha -of the current -directory. -The simplest kind of name, for example, -.UL alpha , -refers to a file that itself is found in the current -directory. -As another limiting case, the null file name refers -to the current directory. -.PP -The same non-directory file may appear in several directories under -possibly different names. -This feature is called -.IT linking ; -a directory entry for a file is sometimes called a link. -The -.UX -system -differs from other systems in which linking is permitted -in that all links to a file have equal status. -That is, a file does not exist within a particular directory; -the directory entry for a file consists merely -of its name and a pointer to the information actually -describing the file. -Thus a file exists independently of any -directory entry, although in practice a file is made to -disappear along with the last link to it. -.PP -Each directory always has at least two entries. -The name -``\|\fB.\|\fP'' in each directory refers to the directory itself. -Thus a program -may read the current directory under the name ``\fB\|.\|\fP'' without knowing -its complete path name. -The name ``\fB\|.\|.\|\fP'' by convention refers to the parent of the -directory in which it appears, that is, to the directory in which -it was created. -.PP -The directory structure is constrained to have the form -of a rooted tree. -Except for the special entries ``\|\fB\|.\|\fP'' and ``\fB\|.\|.\|\fP'', each directory -must appear as an entry in exactly one other directory, which is its -parent. -The reason for this is to simplify the writing of programs -that visit subtrees of the directory structure, and more -important, to avoid the separation of portions of the hierarchy. -If arbitrary links to directories were permitted, it would -be quite difficult to detect when the last connection from -the root to a directory was severed. -.SH -3.3 Special files -.PP -Special files constitute the most unusual feature of the -.UX -file system. -Each supported I/O device -is associated with at least one such file. -Special files are read and written just like ordinary -disk files, but requests to read or write result in activation of the associated -device. -An entry for each special file resides in directory -.UL /dev , -although a link may be made to one of these files -just as it may to an ordinary file. -Thus, for example, -to write on a magnetic tape -one may write on the file -.UL /dev/mt . -Special files exist for each communication line, each disk, -each tape drive, -and for physical main memory. -Of course, -the active disks -and the memory special file are protected from -indiscriminate access. -.PP -There is a threefold advantage in treating -I/O devices this way: -file and device I/O -are as similar as possible; -file and device names have the same -syntax and meaning, so that -a program expecting a file name -as a parameter can be passed a device -name; finally, -special files are subject to the same -protection mechanism as regular files. -.SH -3.4 Removable file systems -.PP -Although the root of the file system is always stored on the same -device, -it is not necessary that the entire file system hierarchy -reside on this device. -There is a -.UL mount -system request with two arguments: -the name of an existing ordinary file, and the name of a special -file whose associated -storage volume (e.g., a disk pack) should have the structure -of an independent file system -containing its own directory hierarchy. -The effect of -.UL mount -is to cause -references to the heretofore ordinary file -to refer instead to the root directory -of the file system on the removable volume. -In effect, -.UL mount -replaces a leaf of the hierarchy tree (the ordinary file) -by a whole new subtree (the hierarchy stored on the -removable volume). -After the -.UL mount , -there is virtually no distinction -between files on the removable volume and those in the -permanent file system. -In our installation, for example, -the root directory resides -on a small partition of one of -our disk drives, -while the other drive, -which contains the user's files, -is mounted by the system initialization -sequence. -A mountable file system is generated by -writing on its corresponding special file. -A utility program is available to create -an empty file system, -or one may simply copy an existing file system. -.PP -There is only one exception to the rule of identical -treatment of files on different devices: -no link may exist between one file system hierarchy and -another. -This restriction is enforced so as to avoid -the elaborate bookkeeping -that would otherwise be required to assure removal of the links -whenever the removable volume is dismounted. -.SH -3.5 Protection -.PP -Although the access control scheme -is quite simple, it has some unusual features. -Each user of the system is assigned a unique -user identification number. -When a file is created, it is marked with -the user \*sID\*n of its owner. -Also given for new files -is a set of ten protection bits. -Nine of these specify -independently read, write, and execute permission -for the -owner of the file, -for other members of his group, -and for all remaining users. -.PP -If the tenth bit is on, the system -will temporarily change the user identification -(hereafter, user \*sID\*n) -of the current user to that of the creator of the file whenever -the file is executed as a program. -This change in user \*sID\*n is effective only -during the execution of the program that calls for it. -The set-user-\*sID\*n feature provides -for privileged programs that may use files -inaccessible to other users. -For example, a program may keep an accounting file -that should neither be read nor changed -except by the program itself. -If the set-user-\*sID\*n bit is on for the -program, it may access the file although -this access might be forbidden to other programs -invoked by the given program's user. -Since the actual user \*sID\*n -of the invoker of any program -is always available, -set-user-\*sID\*n programs -may take any measures desired to satisfy themselves -as to their invoker's credentials. -This mechanism is used to allow users to execute -the carefully written -commands -that call privileged system entries. -For example, there is a system entry -invokable only by the ``super-user'' (below) -that creates -an empty directory. -As indicated above, directories are expected to -have entries for ``\fB\|.\|\fP'' and ``\fB\|.\|.\|\fP''. -The command which creates a directory -is owned by the super-user -and has the set-user-\*sID\*n bit set. -After it checks its invoker's authorization to -create the specified directory, -it creates it and makes the entries -for ``\fB\|.\|\fP'' and ``\fB\|.\|.\|\fP''. -.PP -Because anyone may set the set-user-\*sID\*n -bit on one of his own files, -this mechanism is generally -available without administrative intervention. -For example, -this protection scheme easily solves the \*sMOO\*n -accounting problem posed by ``Aleph-null.'' -.[ -aleph null software practice -.] -.PP -The system recognizes one particular user \*sID\*n (that of the ``super-user'') as -exempt from the usual constraints on file access; thus (for example), -programs may be written to dump and reload the file -system without -unwanted interference from the protection -system. //GO.SYSIN DD p1 echo p2 sed 's/.//' >p2 <<'//GO.SYSIN DD p2' -.SH -3.6 I/O calls -.PP -The system calls to do I/O are designed to eliminate -the differences between the various devices and styles of -access. -There is no distinction between ``random'' -and ``sequential'' I/O, nor is any logical record size imposed -by the system. -The size of an ordinary file is determined -by the number of bytes written on it; -no predetermination of the size of a file is necessary -or possible. -.PP -To illustrate the essentials of I/O, -some of the basic calls are -summarized below -in an anonymous language that will -indicate the required parameters without getting into the -underlying -complexities. -Each call to the system may potentially result in an error -return, which for simplicity is not represented -in the calling sequence. -.PP -To read or write a file assumed to exist already, it must -be opened by the following call: -.P1 -filep = open\|(\|name, flag\|) -.P2 -where -.UL name -indicates the name of the file. -An arbitrary path name may be given. -The -.UL flag -argument indicates whether the file is to be read, written, -or ``updated,'' that is, read and written simultaneously. -.PP -The returned value -.UL filep -is called a -.IT "file descriptor" . -It is a small integer used to identify the file -in subsequent calls to read, write, -or otherwise manipulate the file. -.PP -To create a new file or completely rewrite an old one, -there is a -.UL create -system call that -creates the given file if it does not exist, -or truncates it to zero length -if it does exist; -.UL create -also opens the new file for writing -and, like -.UL open , -returns a file descriptor. -.PP -The file system maintains no locks visible to the user, nor is there any -restriction on the number of users who may have a file -open for reading or writing. -Although it is possible for the contents of a file -to become scrambled when two users write on it simultaneously, -in practice difficulties do not arise. -We take the view that locks are neither -necessary nor sufficient, in our environment, -to prevent interference between users of the same file. -They are unnecessary because we are not -faced with large, single-file data bases -maintained by independent processes. -They are insufficient because -locks in the ordinary sense, whereby -one user is prevented from writing on a file that another -user is reading, -cannot prevent confusion -when, for example, both users are editing -a file with an editor that makes -a copy of the file being edited. -.PP -There are, however, -sufficient internal interlocks to maintain -the logical consistency of the file system -when two users engage simultaneously in -activities such as writing on -the same file, -creating files in the same directory, -or deleting each other's open files. -.PP -Except as indicated below, reading and writing -are sequential. -This means that if a particular -byte in the file was the last byte written (or read), -the next I/O call implicitly refers to the -immediately following byte. -For each open file there is a pointer, maintained -inside the system, -that indicates the next byte to be read -or written. -If -.IT n -bytes are read or written, the pointer advances -by -.IT n -bytes. -.PP -Once a file is open, the following calls -may be used: -.P1 -n = read\|(\|filep, buffer, count\|) -n = write\|(\|filep, buffer, count\|) -.P2 -Up to -.UL count -bytes are transmitted between the file specified -by -.UL filep -and the byte array -specified by -.UL buffer . -The returned value -.UL n -is the number of bytes actually transmitted. -In the -.UL write -case, -.UL n -is the same as -.UL count -except under exceptional conditions, such as I/O errors or -end of physical medium on special files; -in a -.UL read , -however, -.UL n -may without error be less than -.UL count . -If the read pointer is so near the end of the -file that reading -.UL count -characters -would cause reading beyond the end, only sufficient -bytes are transmitted to reach the end of the -file; -also, typewriter-like terminals -never return more than one line of input. -When a -.UL read -call returns with -.UL n -equal -to zero, the end of the file has been reached. -For disk files this occurs when the read pointer -becomes equal to the current -size of the file. -It is possible to generate an end-of-file -from a terminal by use of an escape -sequence that depends on the device used. -.PP -Bytes written affect only those parts of a file implied by -the position of the write pointer and the -count; no other part of the file -is changed. -If the last byte lies beyond the end of the file, the -file is made to grow as needed. -.PP -To do random (direct-access) I/O -it is only necessary to move the read or write pointer -to the appropriate location in the file. -.P1 -location = lseek\|(\|filep, offset, base\|) -.P2 -The pointer -associated with -.UL filep -is moved to a position -.UL offset -bytes from the beginning of the file, from the current position -of the pointer, or from the end of the file, -depending on -.UL base. -.UL \&offset -may be negative. -For some devices (e.g., paper -tape and -terminals) seek calls are -ignored. -The actual offset from the beginning of the file -to which the pointer was moved is returned -in -.UL location . -.PP -There are several additional system entries -having to do with I/O and with the file -system that will not be discussed. -For example: -close a file, -get the status of a file, -change the protection mode or the owner -of a file, -create a directory, -make a link to an existing file, -delete a file. -.SH -IV. IMPLEMENTATION OF THE FILE SYSTEM -.PP -As mentioned in Section 3.2 above, a directory entry contains -only a name for the associated file and a pointer to the -file itself. -This pointer is an integer called the -.IT i-number -(for index number) -of the file. -When the file is accessed, -its i-number is used as an index into -a system table (the -.IT i-list \|) -stored in a known -part of the device on which -the directory resides. -The entry found thereby (the file's -.IT i-node \|) -contains -the description of the file: -.IP i -the user and group-\*sID\*n of its owner -.IP ii -its protection bits -.IP iii -the physical disk or tape addresses for the file contents -.IP iv -its size -.IP v -time of creation, last use, and last modification -.IP vi -the number of links to the file, that is, the number of times it appears in a directory -.IP vii -a code indicating whether the file is a directory, an ordinary file, or a special file. -.LP -The purpose of an -.UL open -or -.UL create -system call is to turn the path name given by the user -into an i-number -by searching the explicitly or implicitly named directories. -Once a file is open, -its device, i-number, and read/write pointer are stored in a system table -indexed by the file descriptor returned by the -.UL open -or -.UL create . -Thus, during a subsequent -call to read or write the -file, -the descriptor -may be easily related to the information necessary to access the file. -.PP -When a new file is created, -an i-node is allocated for it and a directory entry is made -that contains the name of the file and the i-node -number. -Making a link to an existing file involves -creating a directory entry with the new name, -copying the i-number from the original file entry, -and incrementing the link-count field of the i-node. -Removing (deleting) a file is done by -decrementing the -link-count of the i-node specified by its directory entry -and erasing the directory entry. -If the link-count drops to 0, -any disk blocks in the file -are freed and the i-node is de-allocated. -.PP -The space on all disks that -contain a file system is divided into a number of -512-byte -blocks logically addressed from 0 up to a limit that -depends on the device. -There is space in the i-node of each file for 13 device addresses. -For nonspecial files, -the first 10 device addresses point at the first -10 blocks of the file. -If the file is larger than 10 blocks, -the 11 device address points to an -indirect block containing up to 128 addresses -of additional blocks in the file. -Still larger files use the twelfth device address -of the i-node to point to -a double-indirect block naming -128 indirect blocks, -each -pointing to 128 blocks of the file. -If required, -the thirteenth device address is -a triple-indirect block. -Thus files may conceptually grow to -[\|(10+128+128\u\s62\s0\d+128\u\s63\s0\d)\*m512\|] bytes. -Once opened, -bytes numbered below 5120 can be read with a single -disk access; -bytes in the range 5120 to 70,656 -require two accesses; -bytes in the range 70,656 -to 8,459,264 -require three accesses; -bytes from there to the -largest file -(1,082,201,088) -require four accesses. -In practice, -a device cache mechanism -(see below) -proves effective in eliminating -most of the indirect fetches. -.PP -The foregoing discussion applies to ordinary files. -When an I/O request is made to a file whose i-node indicates that it -is special, -the last 12 device address words are immaterial, -and the first specifies -an internal -.IT "device name" , -which is interpreted as a pair of numbers -representing, -respectively, a device type -and subdevice number. -The device type indicates which -system routine will deal with I/O on that device; -the subdevice number selects, for example, a disk drive -attached to a particular controller or one of several -similar terminal interfaces. -.PP -In this environment, the implementation of the -.UL mount -system call (Section 3.4) is quite straightforward. -.UL \&mount -maintains a system table whose -argument is the i-number and device name of the -ordinary file specified -during the -.UL mount , -and whose corresponding value is the -device name of the indicated special file. -This table is searched for each i-number/device pair -that turns up while a path name is being scanned -during an -.UL open -or -.UL create ; -if a match is found, -the i-number is replaced by the i-number of the root -directory -and the device name is replaced by the table value. -.PP -To the user, both reading and writing of files appear to -be synchronous and unbuffered. -That is, immediately after -return from a -.UL read -call the data are available; conversely, -after a -.UL write -the user's workspace may be reused. -In fact, the system maintains a rather complicated -buffering mechanism that reduces greatly the number -of I/O operations required to access a file. -Suppose a -.UL write -call is made specifying transmission -of a single byte. -The system -will search its buffers to see -whether the affected disk block currently resides in main memory; -if not, it will be read in from the device. -Then the affected byte is replaced in the buffer and an -entry is made in a list of blocks to be written. -The return from the -.UL write -call may then take place, -although the actual I/O may not be completed until a later time. -Conversely, if a single byte is read, the system determines -whether the secondary storage block in which the byte is located is already -in one of the system's buffers; if so, the byte can be returned immediately. -If not, the block is read into a buffer and the byte picked out. -.PP -The system recognizes when -a program has -made accesses to -sequential blocks of a file, -and asynchronously -pre-reads the next block. -This significantly reduces -the running time of most programs -while adding little to -system overhead. -.PP -A program that reads or writes files in units of 512 bytes -has an advantage over a program that reads or writes -a single byte at a time, but the gain is not immense; -it comes mainly from the avoidance of system overhead. -If a program is used rarely or does -no great volume of I/O, it may quite reasonably -read and write in units as small as it wishes. -.PP -The notion of the i-list is an unusual feature -of -.UX . -In practice, this method of organizing the file system -has proved quite reliable and easy to deal with. -To the system itself, one of its strengths is -the fact that each file has a short, unambiguous name -related in a simple way to the protection, addressing, -and other information needed to access the file. -It also permits a quite simple and rapid -algorithm for checking the consistency of a file system, -for example, verification -that the portions of each device containing useful information -and those free to be allocated are disjoint and together -exhaust the space on the device. -This algorithm is independent -of the directory hierarchy, because it need only scan -the linearly organized i-list. -At the same time the notion of the i-list induces certain -peculiarities not found in other file system organizations. -For example, there is the question of who is to be charged -for the space a file occupies, -because all directory entries for a file have equal status. -Charging the owner of a file is unfair in general, -for one user may create a file, another may link to -it, and the first user may delete the file. -The first user is still the owner of the -file, but it should be charged -to the second user. -The simplest reasonably fair algorithm -seems to be to spread the charges -equally among users who have links to a file. -Many installations -avoid the -issue by not charging any fees at all. //GO.SYSIN DD p2 echo p3 sed 's/.//' >p3 <<'//GO.SYSIN DD p3' -.SH -V. PROCESSES AND IMAGES -.PP -An -.IT image -is a computer execution environment. -It includes a memory image, -general register values, -status of open files, -current directory and the like. -An image is the current state of a pseudo-computer. -.PP -A -.IT process -is the execution of an image. -While the processor is executing on behalf of a process, -the image must reside in main memory; -during the execution of other processes it remains in main memory -unless the appearance of an active, higher-priority -process -forces it to be swapped out to the disk. -.PP -The user-memory part of an image is divided into three logical segments. -The program text segment begins at location 0 in the virtual address space. -During execution, this segment is write-protected -and a single copy of it is shared among -all processes executing the same program. -At the first hardware protection byte boundary above the program text segment in the -virtual address space begins a non-shared, writable data segment, -the size of which may be extended by a system call. -Starting at the highest -address in the virtual address space is a stack segment, -which automatically grows downward -as the stack pointer fluctuates. -.SH -5.1 Processes -.PP -Except while -the system -is bootstrapping itself into operation, a new -process can come into existence only -by use of the -.UL fork -system call: -.P1 -processid = fork\|(\|\|)\| -.P2 -When -.UL fork -is executed, the process -splits into two independently executing processes. -The two processes have independent -copies of the original memory image, -and share all open files. -The new processes differ only in that one is considered -the parent process: -in the parent, -the returned -.UL processid -actually identifies the child process -and is never 0, -while in the child, -the returned value is always 0. -.PP -Because the values returned by -.UL fork -in the parent and child process are distinguishable, -each process may determine whether -it is the parent or child. -.SH -5.2 Pipes -.PP -Processes may communicate -with related processes using the same system -.UL read -and -.UL write -calls that are used for file-system I/O. -The call: -.P1 -filep = pipe\|(\|\|)\| -.P2 -returns a file descriptor -.UL filep -and -creates an inter-process channel called a -.IT pipe . -This channel, like other open files, is passed from parent to child process in -the image by the -.UL fork -call. -A -.UL read -using a pipe file descriptor -waits until another process writes using the -file descriptor for the same pipe. -At this point, data are passed between the images of the -two processes. -Neither process need know that a pipe, -rather than an ordinary file, -is involved. -.PP -Although -inter-process communication -via pipes is a quite valuable tool -(see Section 6.2), -it is not a completely general -mechanism, -because the pipe must be set up by a common ancestor -of the processes involved. -.SH -5.3 Execution of programs -.PP -Another major system primitive -is invoked by -.P1 -execute\|(\|file, arg\*s\d1\u\*n, arg\*s\d2\u\*n, .\|.\|. , arg\*s\dn\u\*n\|)\| -.P2 -which requests the system to read in and execute the program -named by -.UL file , -passing it string arguments -.UL arg\v'.3'\*s1\*n\v'-.3'\| , -.UL arg\v'.3'\*s2\*n\v'-.3'\| , -.UL .\|.\|.\|\| , -.UL arg\v'.3'\*sn\*n\v'-.3' . -All the code and data in the process invoking -.UL execute -is replaced from the -.UL file , -but -open files, current directory, and -inter-process relationships are unaltered. -Only if the call fails, for example -because -.UL file -could not be found or because -its execute-permission bit was not set, does a return -take place from the -.UL execute -primitive; -it resembles a ``jump'' machine instruction -rather than a subroutine call. -.SH -5.4 Process synchronization -.PP -Another process control system call: -.P1 -processid = wait\|(\|status\|)\| -.P2 -causes its caller to suspend -execution until one of its children has completed execution. -Then -.UL wait -returns the -.UL processid -of the terminated process. -An error return is taken if the calling process has no -descendants. -Certain status from the child process -is also available. -.SH -5.5 Termination -.PP -Lastly: -.P1 -exit\|(\|status\|)\| -.P2 -terminates a process, -destroys its image, -closes its open files, -and generally obliterates it. -The parent is notified through -the -.UL wait -primitive, -and -.UL status -is made available -to it. -Processes may also terminate as a result of -various illegal actions or user-generated signals -(Section VII below). //GO.SYSIN DD p3 echo p4 sed 's/.//' >p4 <<'//GO.SYSIN DD p4' -.SH -VI. THE SHELL -.PP -For most users, -communication with -the system -is carried on with the -aid of a program called the \&shell. -The \&shell is a -command-line interpreter: it reads lines typed by the user and -interprets them as requests to execute -other programs. -(The \&shell is described fully elsewhere, -.[ -bourne shell bstj -%Q This issue -.] -so this section will discuss only the theory of its operation.) -In simplest form, a command line consists of the command -name followed by arguments to the command, all separated -by spaces: -.P1 -command arg\*s\d1\u\*n arg\*s\d2\u\*n .\|.\|. arg\*s\dn\u\*n -.P2 -The \&shell splits up the command name and the arguments into -separate strings. -Then a file with name -.UL command -is sought; -.UL command -may be a path name including the ``/'' character to -specify any file in the system. -If -.UL command -is found, it is brought into -memory and executed. -The arguments -collected by the \&shell are accessible -to the command. -When the command is finished, the \&shell -resumes its own execution, and indicates its readiness -to accept another command by typing a prompt character. -.PP -If file -.UL command -cannot be found, -the \&shell generally prefixes a string -such as -.UL /\|bin\|/ -to -.UL command -and -attempts again to find the file. -Directory -.UL /\|bin -contains commands -intended to be generally used. -(The sequence of directories to be searched -may be changed by user request.) -.SH -6.1 Standard I/O -.PP -The discussion of I/O in Section III above seems to imply that -every file used by a program must be opened or created by the program in -order to get a file descriptor for the file. -Programs executed by the \&shell, however, start off with -three open files with file descriptors -0, 1, and 2. -As such a program begins execution, file 1 is open for writing, -and is best understood as the standard output file. -Except under circumstances indicated below, this file -is the user's terminal. -Thus programs that wish to write informative -information ordinarily use file descriptor 1. -Conversely, file 0 starts off open for reading, and programs that -wish to read messages typed by the user -read this file. -.PP -The \&shell is able to change the standard assignments of -these file descriptors from the -user's terminal printer and keyboard. -If one of the -arguments to a command is prefixed by ``>'', file descriptor -1 will, for the duration of the command, refer to the -file named after the ``>''. -For example: -.P1 -ls -.P2 -ordinarily lists, on the typewriter, the names of the files in the current -directory. -The command: -.P1 -ls >there -.P2 -creates a file called -.UL there -and places the listing there. -Thus the argument -.UL >there -means -``place output on -.UL there .'' -On the other hand: -.P1 -ed -.P2 -ordinarily enters the editor, which takes requests from the -user via his keyboard. -The command -.P1 -ed