ࡱ> Y YbjbjWW ,==9] " " "",",","@"@"@"@"8x"$"<@"@########>>>><#??[@$2B&D@,"#####@*,","###***#,"#,"#>@"@",",",","#>**@2P9k,",">#",0iC@"@" %>*An Open Operating System for a Single-User Machine, Butler W. Lampson Xerox Research Center Palo Alto, California 94304 Robert F. Sproull Carnegie-Mellon University Pittsburgh, Pennsylvania 15213 Abstract The file system and modularization of a single-user operating system are described. The main points of interest are the openness of the system, which establishes no sharp boundary between itself and the users programs, and the techniques used to make the system robust, 1. Introduction In the last few years a certain way of thinking about operating systems has come to be widely accepted. According to this view, the function of an operating system is to provide a kind of womb (or, if you like, a virtual machine) within which the user or her program can live and develop, safely insulated from the harsh realities of the outside world [2, 5, 13]. One of the authors, in fact, was an early advocate of such closed systems [12]. They have a number of attractive features: When the hardware is too dreadful for ordinary mortals to look upon, concealment is a kindness, if not a necessity. Useful and popular facilities can be made available in a uniform manner, with the name binding and storage allocation required to implement them kept out of the way. The system can protect itself from the users without having to make any assumptions about what they do (aside from those implicit in the definition of the virtual machine). A more robust facility can perhaps be provided if all of the underlying structure is concealed. On the other hand, a good deal may be lost by putting too much distance between the user and the hardware [4], especially if she needs to deal with unconventional input-output devices. Furthermore, a lot of flexibility is given up by the flat, all-or-nothing style of these systems, and it is extremely difficult for a user to extend or modify the system because of the sharp line which is drawn between the two. In this paper we explore a different, more open approach: the system is thought of as offering a variety of facilities, any of which the user may reject, accept, modify or extend. In many cases a facility may become a component out of which other facilities are built up: for example, files are built out of disk pages. When this happens, we try as far as possible to make the small components accessible to the user as well as the large ones. The success of such a design depends on the extent to which we can exploit the flexibility of the small components without destroying the larger ones. In particular, we must pay a great deal of attention to the robustness of the system, i.e., recovery from crashes and resistance to misuse. Another aspect of our system is that the file system and communications are standardized at a level below any of the software in the operating system. In fact, it is the representation of files on the disk and of packets on the network that are standardized. This has permitted programs written in radically different languages (BCPL [4], Mesa [8], Lisp [7] and Smalltalk [10]; the former came first, and is the host language of the software described in this paper) and executed using radically different instruction sets (implemented in writeable microcode) to share the same file system and remote facilities. In doing so, they do not give up any storage to an operating system written in a foreign language, or any cycles in switching from one programming environment and instruction set to another at every access to disk storage or communications. The price paid for this flexibility is that any change in these representations requires changing several pieces of code, written in several languages and maintained by several different people; the cost of this rewriting is so high that it is effectively impossible to make such changes. Thus the approach cannot be recommended when processor speed and memory are ample; standardization at a higher level is preferable in this case. In our situation, however, the policy has made many major applications of the machine possible which would otherwise have been completely infeasible. Furthermore, we have found that these restrictions have caused few practical problems, in spite of the fact that the range of uses of the system has been far greater than was initially anticipated. In a multi-user system, of course, there must be compulsory protection mechanisms that ensure equitable and safe sharing of the hardware resources, and this consideration sets limits to the openness that can be achieved. Within these limits, however, much can be done, and indeed the facilities discussed below can be provided in a protected way without any great changes, although this paper avoids an explicit analysis of the problem by confining itself to a single-user system. To describe an entire system in this way would be a substantial undertaking. We will confine ourselves here to the disk file system, the method of doing world swapping, and the way in which the system is constructed out of packages. 2. Background The operating system from which the examples in this paper are drawn was written for a small computer called the Alto [16], which has a 16-bit processor, 64k words of 800 ns memory, and one or two moving-head disk drives, each of which can store 2.5 megabytes on a single removable pack and can transfer 64k words in about one second. The machine and system can also support another disk with about twice the size and performance. The machine has no virtual memory hardware. The processor executes an instruction set that supports BCPL, including special instructions for procedure calls and returns. The system is written almost entirely in BCPL, and in fact this language is considered to be one of the standard ways of programming the machine. The compiler generates ordinary machine instructions, and uses no runtime support routines except for a small body of code that extends the instruction set slightly. Only one user at a time is supported, and peripheral equipment other than the disk and terminal is infrequently used. As a result, the current version of the system has only two processes, one of which puts keyboard input characters into a buffer, while the other does all the interesting work. The keyboard process is interrupt-driven and has no critical sections; hence there are no synchronization primitives and no scheduler other than the hardware interrupt system. As a result, the system does not control processor allocation, and in fact gets control only when a user program calls some system facility. The system does control storage allocation to some extent, both in main memory and on the disk, in order to make it possible for the users programs to coexist and to call each other. Thus the system can reasonably be viewed as a collection of procedures which implement various potentially useful abstract objects. There is no significant difference between these system procedures and a set of procedures that the user might write to implement his own abstract objects. In fact, the system code is made available as a set of independent subroutine packages, each implementing one of the objects, and these packages have received a great deal of independent use, in applications which do not need all the services of the system and cannot afford its costs. There are several kinds of abstract object: input-output streams, files, storage zones, physical disks. All of these objects are implemented in such a way that they can be values of ordinary variables; since BCPL is a typeless language this means that each object can be represented by a 16-bit machine word. In many cases, of course, this word will be a pointer to something bigger. The streams are copied wholesale from Stoy and Stracheys OS6 system [15], as are many aspects of the file system. We give a summary description here for completeness. A stream is an object that can produce or consume items. Items can be arbitrary BCPL objects: bytes, words, vectors, other streams etc. There is a standard set of operations defined on every stream: Get an item from the stream; Put an item into the stream (normally only one of these is defined); Reset, which puts the stream into some standard initial state (the exact meaning of this operation depends on the type of the stream); Test for end of input; and a few others. These operations are invoked by ordinary BCPL procedure calls. A stream is thus something like a Simula class [6]. It differs from a class in that the procedures that implement the operations are not the same for all streams, and indeed can change from time to time, even for a particular stream. A stream is represented by a record (actually a BCPL vector) whose first few components contain procedures that provide that streams implementation of the standard operations. The rest of the record holds state information, which may vary from stream to stream (e.g. word counts, pointers to buffers, disk addresses, or whatever is appropriate). The size of the record is not fixed, but rather is determined entirely by the procedure that creates the stream. It is also possible for the record to contain procedures that implement non-standard operations (e.g. set buffer size, read position in a disk file, etc.). Alternatively, arbitrary procedures can be written which perform such operations on certain types of stream. In both cases the procedure receives the record which represents the stream as an argument, and can store any permanent state information in that record. Of course, a program that uses a non-standard operation sacrifices compatibility, since it will only work with streams for which that operation is implemented. This scheme for providing abstract objects with multiple implementations is used throughout the system. Each abstract object is defined by the operations that can be invoked on it; the semantics of each operation are defined (more or less rigorously). Any number of concrete implementations are possible, each providing a concrete procedure for each of the abstract operations. Hierarchical structures can be built up in this way. For instance, the procedure to create a stream object of concrete type disk file stream takes as parameters two other objects: a disk object which implements operations to access the storage on which the file resides, and a zone object which is used to acquire and release working storage for the stream. 3. Pages and files The system organizes long-term storage (on disk) into files, each of which is a sequence of fixed-size pages; every page is represented by a single disk sector. Although a file is sufficient unto itself, one normally wants to be able to attach a string name to it, and for this purpose an auxiliary directory facility is provided. Since the integrity of long-term storage is of paramount importance to the user, a scavenging procedure is provided to reconstruct the state of the file system from whatever fragmented state it may have fallen into. The requirements of this procedure govern much of the system design. The remainder of this section expands on the outline just given. 3.1 Pages The simplest object that can be used for long-term storage is a page. It consists of: an addressone word which uniquely specifies a physical disk location (H); a label, which consists of: F: a file identifiertwo words (A); V: a version numberone word (A); PN: a page numberone word (A); L: a length (the number of bytes in this page that contain data)one word (A); NL: a next linkone word (H); PL: a previous linkone word (H); a value256 data words (A). The information that makes up a page is of two kinds: absolutes (A) and hints (H). The page is completely defined by the absolutes. The hints, therefore, are present solely to improve the efficiency of the implementation. Whenever a hint is used, it is checked against some absolute to confirm its continued validity. Furthermore, there is a recovery operation that reconstructs all the hints from the absolutes. Thus a page has a unique absolute name, which is the file identifier, version number and page number (represented by (FV, n), where n is the page number and FV is the file identifier and version), and it has a hint name, which is the address. The full name (FN) of a page is the pair (absolute name, hint name). The links of the page (FV, n) are the addresses of the pages whose absolute names are (FV, n-1) and (FV, n+1), or NIL if no such pages exist. The basic operations on a page are to read and write the data, and to read the links, given the full name. Note that it is easy to go from the full name of a page to the full names of the next and previous pages. 3.2 Files A file is a set of pages with absolute names (FV, 0), (FV, 1) (FV, n). The name of page (FV, 0) is also the name of the file. The basic operations on files are create a new, empty file; add a page to the end of a file; delete one or more pages from the end; delete the entire file. Thus, if page (FV, n) exists, pages (FV, i) exist for all i between 0 and n. Hence, if the address of one page of a file is known, every page can be found by following the links. If (FV, n) is the last page of the file, then pages (FV, i) for i--.p.{.////(0/091>11111 33j3k3t3u33333C4F444445566666666k7l7777777*8-8B8I888I9[99999BBCCNCUCLLQ\R\P]Q]X^Y^QaRa65EH 0J5EH j0J5EH U[6HzK }Jf $"##$P$6HzK }Jf $"###|$$$'),,{//ù{xuroif` D A/Ea U aB@         " :t%##|$$$'),,{///&0B0f0000171S125556O6p66//&0B0f0000171S125556O6p6667889G9e999L:::<=>??BCEC㱮|wrmjgbeO ZD{<V 4(Df9U%667889G9e999L:::<=>??BCECCCFH%HJN(RECCCFH%HJN(R7RTVX~Z[[v]^^h__` b)eKeikek]moplt@wWwCxxxzc{|}zurmjgC r% מEq6c & x _! Mg '(R7RTVX~Z[[v]^^h__` b)eKeikek]moplt@wWwCxxxzRaSaTa\a]a~aaaaaaaaaCcOcllmmDqUqqq r(rgwnwrw{wDxTxZxaxbxgxhxpxqx~xxxxx#y+yAyHyyyyyz z=zDzxzzzzzzzzzzzzzzz{{{{#{'{9{\{b{:|J|||||||}} }}~Āŀ؀ـ5:66H*axzc{|E[I"~ы C NƏqE[I"~ы C NƏq 'dУM~ytojd4 ` bNn lI1@=i8n &Fy  m N(ـ…ɅgnU[ ыŎю ɢآHRTУӣ0:<MPcZrۥbkln~Ѧbɧ^hjʨިߨ>PRSϩѩ!M j0JU 6OJQJ56^q 'dУM~{`ܩ ~{`ܩQVWXY  (KrTUY jU j0JUVWXY  * 00&P/ =!"#$% [:`:Normal dCJOJQJmH ```Heading 1,1,11,heading$$dh@&5CJ$N`NHeading 2,2,21$,<@& 5CJ```Heading 3,3,body,body1,31$@& hP6J`1RJHeading 4,4,q0,q01,41 h@&F`AbFHeading 5,5,q1,q11,51 @&8`Qr8Heading 6,6,q2 8@&8`a8Heading 7,7,q3 @&8`q8Heading 8,8,q4 @&B `B Heading 9,9 @&6CJOJQJ<A`<Default Paragraph Font0o0 b,bulleted  & F8o8code,cCJOJPJQJkHmHnH(o( e,emphasis6(o"(i,indentho!2ib,indent bulletedh & F>Tho!Biu. indent nUmberedh & F>Th.&oQ& m,coMment6>>`b>Title $<5CJ KHOJQJor u,nUmberedh & Fh>Th. AB 4s @& ocin&o&co,cont.o. code small,csCJ6*`6Endnote ReferenceH* o ex h8 `8Footerh H$CJ<&`<Footnote ReferenceCJEH<`< Footnote Text d$CJ,`,Header ! !$o"$Htitle"@& (2(ie#0   B in $P0 `R0Index 1 %dCJ<oqb<rule!&$= 8*or*cmd1' 8NoNcodepara(0d PCJOJQJmH$$sh )$6 o top1*$$o$top2 + # o top3,2o12type-h@& p ! 2a.@& CJ(o( v,variable6*o* -,subscriptH*0o0attrib1$xLo"Lcaption'2$dh/.CJ$o2$dash 3$x&o1&dashend4xJoRJGlossary entry5$hd<OJQJ& `Qb&Index 26& `&Index 37& `&Index 488&`&Index 59&`&Index 6:&(`& Line Number0o0mb<$d`@& CJ @o@mpr= P , CJOJQJ&)`& Page NumberDoDpicture#?$d/.FBFproc@ P 8$ CJOJQJkHptA"qtB*o*quote C06@oB@ ReferenceD$hdxOJQJ!RrtE,b,tbF$$darthG62`2TOC 2H X !2`2TOC 3I X !osbCJEH010tlKh@& hp4o4declheadL $ $o$decl M&o&routineN*o*cmd2O8 T*o*cmd3PT p*o*cmd4Qp  *o"*cmd5R  2o22modhead S@&5CJ*oB*cmd6T  oR modendU(ob(rtnvar V4Y`r4 Document MapW-D CJ&oq&cmd1s X#6/6 bs,bullSkip Y & Fh4Z`4 Plain TextZ CJOJQJosbi64oq4 us,nUmSkip \ & Fhyy]zz0oq0 um,nUmMult _ & F88p1`$1$d hnH 88p2a$1$d, hnH @"@p3"b$1$d, hhnH @2@p8"c$1$d, hhnH <B<p9d$1$ld  hnH .R.t5e1$dhnH .b.t6f1$dhnH .r.t7g1$dhnH FFp10%h$1$d hhnH ::p11i$1$PdhnH ::p12j$1$d hnH ::p13k$1$d,hnH 22c14l$1$dhnH @@p16m1$0d hnH 00p17n1$d,hnH 88p18o1$dhnH 88p19p1$d hnH 88p20q1$d, hnH @"@p21r1$d, hhnH <2<p22s1$$d |hnH BBBp23"t1$d hhnH @R@p24u1$Pd, hnH 0b0t15v1$dhnH 2r2c25w$1$dhnH @@p26x1$0d hnH 88p27y1$pd,hnH BBp28"z1$d hnH <<p29{1$d hnH 00t30|1$dhnH BBp31"}$1$d, hhnH ::p32~$1$d hnH >>p33$1$Ld ThnH BBp34!$1$d hhnH 88p361$0dhnH <"<p371$d hnH 424p391$8dhnH 0B0t351$d,hnH 8R8p411$d,hnH <b<p421$Ld ThnH 8r8p431$d hnH <<p441$8d hhnH 88p451$d,hnH 00t401$dhnH 00t471$dhnH 22c46$1$dhnH >>p551$d hhnH BBp56"1$d hnH 44p571$dhnH 0 0t581$dhnH : :p62$1$d hnH >" >p63$1$d hnH >2 >p54$1$d hnH 0B 0t591$dhnH 0R 0t601$dhnH 0b 0t611$dhnH 2r 2p49$1$d,hnH F Fp65%$1$d hnH 2 2c66$1$dhnH B Bp67"1$d hnH 8 8p681$d hnH 8 8p691$dhnH 0 0t731$dhnH 8 8p701$d hnH 8 8p711$d hnH 2 2c72$1$dhnH 0O 0refhd(CJ24YY 888;RaـYW_be#6(RxzqYXZ\^`cf/ECYY[]addfJNS]Q]S]]]g)gkkkatbtgtptqtut~vvvvvvvwwww#w'w9wxxxxgmӟٟPV£^b>BJNdhwMU')QWZK qls z { | &&'W''(++%,&,',A,B,[,`,e,f,,,,,,,---5-6-7-8-R-S----52;2N2O2R2o2p2v2222244444555F5G5H5d555K6L6M66666??D?E?H?????G1H _PID_GUIDAN{2BE085EE-6281-11D0-B4D5-000000000000}  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefgijklmnopqrstuvwxyz{|}~Root EntrymmaryInformationk: FiC1Tablejh6EWordDocument)WC)WC,SummaryInformation(DocumentSummaryInformation8CompObjjObjectPooliCiC  FMicrosoft Word Document MSWordDocWord.Document.89q