Mostly from Steve Ward in 1998, edited by J. H. Saltzer, February 23, 1999 and January 2001.
This paper describes an operating system with very low-key, but carefully-chosen and hard-to-discover objectives. UNIX provides a hierarchical catalog structure, and succeeds in keeping naming completely distinct from file management. For these reasons, it can (and has been) used in 6.033 in at least three ways:
A second problem is that the modern reader is unfamiliar with the milieu of the late 1960's, when UNIX was being designed, so some of the design decisions that are carefully defended by the authors seem trivially obvious. They were equally obvious in the 1960's, but there was also a large contingent of commercial designers who believed that economics forced computer system design in the direction of large, batch-processing systems. The arrival on the scene of magnetic disk storage, which provided always-online persistent memory, led to a particularly sharp division. The CTSS-Multics-UNIX model of abstracting the disk into a file system contrasted sharply with the batch processing model of abstracting the disk into a set of permanently allocated physical regions, one per client. Put succinctly, the abstractions that appeared to be appropriate for interactive use and the abstractions thought to be appropriate for batch use were markedly different.
(Well, these are the original designers and implementors of UNIX. That seems to be a good qualification.)
(Because it illustrates a lot of things already discussed in 6.033.)
(In 1970, this was an advance in thinking--not all system designers had figured out that this was the way to design a file system. The standard of the day was set by IBM, and IBM's file systems provided structured files. The most widely-used structure was a file of sequential 80-character records. A file with this structure haad the advantage that it could be used by legacy programs that were originally written to read and punch decks of cards.)
(Because any particular structure is likely to be useful to only a small class of applications, and other applications will have to work hard to fit their data into one of the pre-defined structures. Programs that needed to deal with records of varying lengths found it incredibly tedious to cram their data into 80-character records. Besides, if you want 80-character records, you can easily write a user-mode library program that imposes that format on any file.
This is an example of an "End-to-end argument", which says that the system shouldn't do things in the kernel that the application can do for itself, because the application knows better what it really needs.)
(In the X Window System, which requires that every X server must provide an interpretation for every one of the subroutine calls in Xlib.)
The following suggestions were contributed by Steve Ward in 1998.
CONTEXT: Unix originated, in large part, as a reaction to Multics. Although it subsumed many features pioneered by Multics, Thompson & Ritchie, both stark minimalists, faulted Multics for its complexity and were determined to explore simpler alternatives. Early UNIX indeed demonstrated an elegant simplicity compared to extant systems, as measured by capabilities/mechanism ratio. This characteristic was largely responsible for its original appeal to the CS community.
Many of the Multics features axed by R&T during this process, such as virtual memory and dynamic linking, eventually reappeared during the post-BTL evolution of UNIX. Historically, the R&T spartan minimalism was abandoned when UNIX development moved to Berkeley during the 80s, where new features, and mechanism to support them, were added at a furious rate. Admirers of the original UNIX elegance view the last BTL release, UNIX System 7, as the pinnacle of its evolution. Andy Tannenbaum captured this sentiment in the remark that System 7 was a dramatic improvement over its predecessors, and over its successors as well... a view that reflects general consensus among at least a vocal segment of the OS community.
(From Kaashoek) it might also be interesting to look forward from system 7. In particular, tracing back the free operating systems to system 7. Most of the students are familiar with Linux and the other free other operating systems. A related question that one can explore is how is it possible that these free operating systems are better than most (all?) commercial operating systems. [using internet users as a pool of free hiqh-quality programmers seems to be very effective]
UNIX is currently viewed as a platform-independent OS standard. How were UNIX decisions influenced by the PDP-11 and other hardware it was originally targetted to? [Significant examples have to do with the limited address space of the PDP-11 and the user I/O devices available in the early 70s. Specific influences:]
1. The use as file IO as its semantic basis. The two extant communication models were/are (largely random) memory access and (largely serial) file access. Like all computer systems, UNIX sought to unify communications as much as possible around a single semantic. Multics had explored subsuming file access using the memory model -- one could map a file into an address space, and randomly access its contents. Such an approach was out of the question on a PDP-11, due to its 16-bit address space (even then, 65KB was a small file...)
R&T thus chose serial file access as the unifying communication semantic: files, directories, devices, and IPC were based on serial read & write calls. This constrained communication model turned out to be a win, since it readily extended to the network communications that subsequently demanded transparent integration. It is noteworthy that certain Multics offshoots (those of Prime and Apollo) went the other way and tried to map memory accesses onto networks; where are they now?
(Saltzer footnote) Multics (naturally) provided both forms of unifying semantics: a memory-based model, and a switched I/O stream model. Ken Thompson and Joe Ossanna of BTL were the architects of the Multics switched I/O stream model, and the UNIX model is a stripped-down version of that.
2. A related consequence of the 16-bit address space is the UNIX relegation of processes to the role of small modular building blocks. Since a 65Kb address space is hardly sufficient to hold a complex program (like a compiler), big programs were divided into process-sized chunks and interconnected using pipes. Only a little of this structure persists in modern 32-bit UNIX systems; but on the PDP-11 there was little alternative.
Among other things, this bias made enrichment of the intra-process environment (by features such as virtual memory or dynamic linking or threads) much less attractive than the development of extra-process glue for bundling process-sized chunks into useful systems. Pipes, filters, and exec all reflect this view of processes as bounded-function building blocks rather than extensible application environments. If the PDP-11 had had a 32-bit address space, UNIX might have been quite different.
In view of our recent attention to virtual memory, it may be worth noting that high-end PDP-11 models (11/45, 11/70) had hardware support for VM. However, they were among the few machines whose physical address space was bigger than their virtual address space (eg 24 bits vs 16 bits). VM on a PDP-11 was not a means to present a process with the illusion of a large addressable memory; it was a means to support many processes each having a small address space. This will come as a surprise to many students, who assume that VM is used only to implement an address space bigger than physical memory.
3. UNIX was developed for printing terminals, which conform reasonably well to the constraints of serial I/O. One of the major differences between UNIX and subsequent graphics-based systems (developed at PARC, Apple, elsewhere) is that in UNIX graphics are an obvious afterthought, addressed by outboard packages (notably, X). It may be interesting to discuss with your class the impact of this difference.
1. File names. Why a strict hierarchy?
[links are reference counted, allowing a file to be deleted when its
last link is removed. For this to work, the directory graph must
be acyclic. UNIX ensures this by providing only two ways of making
links:
link(f, path)
mkdir(path)
(Footnote from Costa Sapuntzakis) UNIX v7 allowed hard links to be created between directories, allowing cycles to be potentially created. However, only the super-user could do this.
The discussion on p 1909 refers to the restriction that each directory
have a unique parent, and implies that this restriction simplifies the
reclamation of file storage. Why?
[Because this restriction is mechanized by the constraint that the link
call, above, creates links only for non-directories. The discussion
on p 1909 is actually addressing the problems arising from lifting this
restriction, i.e. allowing new links to be made to existing directories.
This would simultaneously (a) allow multiple parents of directories, and
(b) allow cyclic graphs. While (a) is mentioned explicitly, it is
actually (b) that causes the troubles mentioned (reclamation of
disconnected subgraphs).]
You might question your class on the impact of allowing arbitary links. [presumably garbage collection would be required to collect cycles.]
NB: Symlinks were added much later. These can be cyclic; doesn't this require gc? [no, since dangling symlinks can be tolerated].
Other interesting questions re name hierarchy:
- Whats the advantage of having "."? You can always say "x" instead of "./x"... [allows the current working directory to be named, hence opened. This is critical for such things as expanding "*", which is done by a library routine called within an application; if you type "rm *", the rm program must read "." to delete every file listed
Correction from Costa Sapuntzakis: The "*" is actually expanded by the shell, not the rm program or a library call.]
- Why have ".."? [This was somewhat controversial, since it requires that directories have unique parents. Proponents argued that .. entries allow relative pathnames to be expanded to absolute ones, since a program can traverse upward to the root of a filesystem. Corollary advantages include the ability of programs to refer to files positioned in arbitrary positions relative to the working directory (eg, in siblings of the WD). Opponents argued that .. perpetuated the non-essential restriction that the name graph be acyclic, ie hierarchical.]
- Why were names restricted to 14 characters? [Directory structure allocated a convenient 16 bytes/entry, 2 of which were inumber, leaving 14 for name.]
2. File system structure: inodes. Why not put the inode info, eg physical location of data, into the directory entry?
[Layering. R&T deliberately built the file system in two layers:
1. The inode level, in which a device has a set of files named by consecutive numbers corresponding to entries of a vector of inodes; and
2. The directory level, in which certain files provide mapping of ascii names to inumbers.
This layering was viewed as innovative in the early 70s, when file systems typically mixed physical space allocation parameters into the directory structures which named files. Interestingly, 25 years later leading researchers (Ganger & Kaashoek, C-FFS) proposed an innovative improvement over UNIX in which inode information is integrated into the directory structure... But Costa Sapuntzakis observes that The logical separation between inode and file name remains in C-FFS - it's just the physical on-disk separation that has been removed. This is an example of optimizing the common case.]
3. Processes. Each process (except init) has a unique parent, leading to a tree. This structure allows (eg) an entire process subtree to be killed when a command is aborted. [It also constrains IPC, as noted in the paper: two processes may communicate only if they share an ancestor which anticipates their need to communicate. Subsequent UNIX derivatives alleviated this restriction, e. g. by allowing pipe-ends to be entered in the name hierarchy where they can be referenced and opened by arbitrary processes]
(observation triggered by a comment by Costa Sapuntzakis) The process hierarchy is clearly present, but there is some question as to how useful it is, because there isn't much support by way of system calls such as "who is the parent of X", or "signal/terminate all the descendents of X". The primary programmer-visible feature is the ability to wait for a child process to finish and return a value. The hierarchy is used by the system, however, in the sense that things like signal handlers, pipes, and file descriptors are inherited along the process hierarchy.
(From Dave Mazieres) I think the point this paragraph really wants to make involves *inheritance* of attributes across process creation (whether it be of file descriptors, the signal mask, controlling terminal, or more), and not anything to do with parent processes. So, use the word "inheritance." Maybe use the word "create," since each process other than init was created by one other process (which may no longer be around). But don't use the word parent. Unix uses the term "parent process" to mean something very specific (namely what the getppid() system call returns). That concept is only marginally related to all the inheritance, and mentioning it there confuses things.
The process hierarchy is not very compelling for another reason: Hierarchies are usually assumed to be transitive. Beginning Unix programmers often don't understand why the "parent process" relation is not transitive--why an orphaned grandchild gets reparented to init rather than to its grandparent. More importantly, process attributes are not inherited down this "parent process" tree, precisely because of this dynamic reparenting.
UNIX was used by its developers nearly from the start. What is the impact of this? [It certainly made UNIX adept at maintenance of system software; it probably did little for its applicability to transaction processing, graphics, or databases. The "living in the environment you're building" is a good influence on the environment provide that you -- the environment builder -- are representive of the intended user community.]
R&T say that file locks are neither necessary or sufficient.
- Is this realistic? [For some models, eg their file editing example. In other applications, eg transaction processing, their argument is less compelling.]
- Can one not lock a file during editing in UNIX? [One can implement locks using file protection. This is considered elegant minimalism by some, and a dirty kludge by others. Dave Mazieres points out that processes running as super-user cannot use this mechanism because their system calls always succeed, no matter what the permission bits say.]
What is a file descriptor? What information does it contain?
[A file descriptor is an integer "handle" used by a process to refer
to an open file. It identifies a kernel data structure which
points to a position where the next byte will be read/written
from the file.]
Why maintain the position info in the kernel?
[This is another controversial UNIX decision. Proponents argue that
including position in the file state allows the conceptually simple
"read next byte" to be implemented in a straightforward way.
Opponents, probably including the majority of the OS community who
have opinions on the topic, view the UNIX approach as a mistake. They
argue that the state of a read operation should be maintained by the
process doing the reading, ie that the pointer (relative byte position)
should be passed as an argument to read rather than being implicit
in the file descriptor's state. This argument is compelling in view
of the UNIX fork() semantics, which clones a process which shares the
file descriptors of its parent. A read by the parent of a shared
file descriptor, eg stdin, changes the read pointer seen by the
child. Most consider this to be a semantic bug.]
[(comment from Saltzer): Storing the offset in the kernel leads to examples of semantic bugs, but Robert Morris points out that it also has uses. If the position information were maintained by the process, the example given in the paper
(date ; ls) > xwould result in the output of ls overwriting the output of date. This seems to be a case where sometimes you want the variable shared between processes and sometimes you don't. The structure of UNIX limited the designers to only two choices: always or never. If the system had more flexible sharing options, a variable such as the position could be moved outside the kernel and still shared in those cases that the application finds useful. An end-to-end argument would suggest that storing the position in the kernel preempts a decision that the application should be allowed to make. So if your environment allows flexible sharing, move it out, if it doesn't you are stuck with a choice that some applications will find problematic.]
(From Costa Sapuntzakis) Why is the current directory
maintained in the kernel?
(Dave Mazieres pointed this out) The current directory could
just be another open file descriptor passed to the process on
startup (like the STDIN, STDOUT and STDERR are).
The stat, link (first argument), chdir, exec, mount, and
unmount calls could have taken file descriptors instead of their
path argument. In fact, this would get rid of some possible race
conditions. However, this would require that the current working
directory be remembered by the process, and UNIX didn't have good
ways of maintaining static state shared among all processes
belonging to a given user. The easiest way is to create shared
state is to place it in the kernel.
Response from Steve Ward: File descriptors are not
"handles to the file", in the sense (say) of unique IDs. They
are state information associated with an I/O stream. Of course
the underlying file (say, the inumber) can be recovered from
them, but the shared mutable state makes them inappropriate for
use as file handles (inumbers would be more appropriate). The
notion of having to open a directory before you change to it
seems awkward, and may in fact introduce race conditions rather
than eliminating them. I agree that pathnames are not ideal as
identifiers (primarily since they are not unique) but suspect
that file descriptors are a step in the wrong direction.
Was UNIX really "not designed to meet any predefined objectives"?
[Hardly. UNIX was designed to help R&T do what they do, which
was, incestuously, building UNIX. UNIX is nearly ideal for
UNIX maintenance, a fixed point property shared only with
a few compilers and other software-building-software tools.
Happily, aptitude for UNIX development has much in common with
other software development applications, making UNIX a reasonably
good general-purpose development environment. Most contemporary
complaints about UNIX center on its applicability as a delivery
vehicle for applications unrelated to program development, an
area in which it certainly seems not to have had predefined
objectives...]
(Saltzer comment #1) They also wrote the man pages, which required text editing (ed) and formatting (roff), and UNIX immediately found application within Bell Labs as a word-processing system; the feedback from that application strongly influenced its evolution.
(Saltzer comment #2) But from another perspective, the designers of UNIX did not have a fixed target, set out in advance by someone else. As a result, they were able to maintain simplicity, parsimony, and uniformity of style by, when necessary, adjusting the specifications of what they were building. Put another way, because the goals were not cast in concrete, they had the luxury of being able to say "no" to anything that didn't fit in.
The following ideas are drawn from the files, and are all over the map. They largely reflect a use of this paper to reinforce the naming topic, which may or may not have been discussed yet.
A characteristic of this sytem, which the authors are clearly proud of, is its very "regular" approach to files and I/O. This regularity proved to be a powerful tool that greatly simplified ths system description and implementation. Consequently, a large part of this paper is devoted to the description of the file system interface and its implementation.
Question: In the original UNIX system, the implementation of the file system was deeply inter-twined with the rest of the kernel. To what extent is this integration necessary in order to preserve the "regular" (device-independent) model of I/O that is so attractive? What UNIX features might be difficult to implement using a client/server design that partitions the file server from the rest of the kernel?
How do the file names "." and ".." fit in? For eveything in the list above, identify the context mechanisms and the closure mechanisms. UNIX of course is a complete system, not just a naming system. What does it do about allocation in memory and on the disk. Is there any multilevel storage management?
Saltzer@mit.edu