Commit | Line | Data |
---|---|---|
8340f87c BJ |
1 | .ds n \s+2 |
2 | .hw above-mentioned | |
3 | .ds s \s-2 | |
4 | .ds m \v'-.3'.\v'.3' | |
5 | .TL | |
6 | The UNIX | |
7 | Time-Sharing System\f1\s10\v'-.2n'*\v'.2n'\s0\fP | |
8 | .AU | |
9 | D. M. Ritchie and K. Thompson | |
10 | .AB | |
11 | .FS | |
12 | * Copyright 1974, | |
13 | Association for Computing Machinery, Inc., | |
14 | reprinted by permission. | |
15 | This is a revised version of an article | |
16 | that appeared in Communications of the \*sACM\*n, | |
17 | .IT 17 , | |
18 | No. 7 (July 1974), pp. 365-375. | |
19 | That article was a | |
20 | revised version of a paper presented | |
21 | at the Fourth \*sACM\*n Symposium on Operating | |
22 | Systems Principles, | |
23 | \*sIBM\*n Thomas J. Watson Research Center, | |
24 | Yorktown Heights, | |
25 | New York, | |
26 | October 15-17, 1973. | |
27 | .FE | |
28 | .UX | |
29 | is a general-purpose, multi-user, interactive | |
30 | operating system for the larger Digital Equipment Corporation | |
31 | \*sPDP\*n-11 and | |
32 | the Interdata 8/32 computers. | |
33 | It offers a number of features | |
34 | seldom found even in larger operating | |
35 | systems, including | |
36 | .IP i | |
37 | A hierarchical file system incorporating | |
38 | demountable volumes, | |
39 | .IP ii | |
40 | Compatible file, device, and inter-process I/O, | |
41 | .IP iii | |
42 | The ability to initiate asynchronous processes, | |
43 | .IP iv | |
44 | System command language selectable on a per-user basis, | |
45 | .IP v | |
46 | Over 100 subsystems including a dozen languages, | |
47 | .IP vi | |
48 | High degree of portability. | |
49 | .LP | |
50 | This paper discusses the nature | |
51 | and implementation of the file system | |
52 | and of the user command interface. | |
53 | .AE | |
54 | .NH | |
55 | INTRODUCTION | |
56 | .PP | |
57 | There have been four versions of | |
58 | the | |
59 | .UX | |
60 | time-sharing system. | |
61 | .hy 12 | |
62 | The earliest (circa 1969-70) ran on | |
63 | the Digital Equipment Corporation \*sPDP\*n-7 and -9 computers. | |
64 | The second version ran on the unprotected | |
65 | \*sPDP\*n-11/20 computer. | |
66 | The third incorporated multiprogramming and ran | |
67 | on the \*sPDP\*n-11/34, /40, /45, /60, and /70 computers; | |
68 | it is the one described in the previously published version | |
69 | of this paper, and is also the most widely used today. | |
70 | .hy 14 | |
71 | This paper describes only the | |
72 | fourth, current | |
73 | system that runs on the \*sPDP\*n-11/70 and the | |
74 | Interdata 8/32 computers. | |
75 | In fact, the differences among the various systems is | |
76 | rather small; | |
77 | most of the revisions made to the originally published version of this | |
78 | paper, | |
79 | aside from those concerned with style, | |
80 | had to do with details of the implementation of the file system. | |
81 | .PP | |
82 | Since | |
83 | \*sPDP\*n-11 | |
84 | .UX | |
85 | became operational | |
86 | in February, 1971, | |
87 | over 600 installations have been put into service. | |
88 | Most of them are engaged in applications such as | |
89 | computer science education, | |
90 | the preparation and formatting of documents | |
91 | and other textual material, | |
92 | the collection and processing of trouble data | |
93 | from various switching machines within the Bell System, | |
94 | and recording and checking telephone service | |
95 | orders. | |
96 | Our own installation is used mainly for research | |
97 | in operating systems, languages, | |
98 | computer networks, | |
99 | and other topics in computer science, and also for | |
100 | document preparation. | |
101 | .PP | |
102 | Perhaps the most important achievement of | |
103 | .UX | |
104 | is to demonstrate | |
105 | that | |
106 | a powerful operating system for interactive use | |
107 | need not be expensive either in equipment or in human | |
108 | effort: | |
109 | it | |
110 | can run on hardware costing as little as $40,000, and | |
111 | less than two man-years were spent on the main system | |
112 | software. | |
113 | We hope, however, that users find | |
114 | that the | |
115 | most important characteristics of the system | |
116 | are its simplicity, elegance, and ease of use. | |
117 | .PP | |
118 | Besides the operating system proper, some major programs | |
119 | available under | |
120 | .UX | |
121 | are | |
122 | .DS | |
123 | .nf | |
124 | C compiler | |
125 | Text editor based on \*sQED\*n | |
126 | .[ | |
127 | qed lampson | |
128 | .] | |
129 | Assembler, linking loader, symbolic debugger | |
130 | Phototypesetting and equation setting programs | |
131 | .[ | |
132 | cherry kernighan typesetting mathematics cacm | |
133 | .] | |
134 | .[ | |
135 | kernighan lesk ossanna document preparation bstj | |
136 | %Q This issue | |
137 | .] | |
138 | .fi | |
139 | .in +3n | |
140 | .ll -5n | |
141 | .ti -3n | |
142 | Dozens of languages including | |
143 | Fortran 77, Basic, Snobol, \*sAPL\*n, Algol 68, M6, \*sTMG\*n, Pascal | |
144 | .in | |
145 | .ll | |
146 | .DE | |
147 | There is a host of maintenance, utility, recreation and novelty programs, | |
148 | all written locally. | |
149 | The | |
150 | .UX | |
151 | user community, which numbers in the thousands, | |
152 | has contributed many more programs and languages. | |
153 | It is worth noting that the system is totally self-supporting. | |
154 | All | |
155 | .UX | |
156 | software is maintained on | |
157 | the | |
158 | system; | |
159 | likewise, this paper and all other | |
160 | documents | |
161 | in this issue | |
162 | were generated and formatted by the | |
163 | .UX | |
164 | editor and text formatting | |
165 | programs. | |
166 | .SH | |
167 | II. HARDWARE AND SOFTWARE ENVIRONMENT | |
168 | .PP | |
169 | The \*sPDP\*n-11/70 on which the Research | |
170 | .UX | |
171 | system is installed is a 16-bit | |
172 | word (8-bit byte) computer with 768K bytes of core memory; | |
173 | the system kernel | |
174 | occupies 90K bytes | |
175 | about equally divided between code | |
176 | and data tables. | |
177 | This system, however, includes a very large number of | |
178 | device drivers | |
179 | and enjoys a generous allotment | |
180 | of space for I/O buffers and system tables; | |
181 | a minimal system capable of running the software | |
182 | mentioned above can | |
183 | require as little as 96K bytes | |
184 | of core altogether. | |
185 | There are even larger installations; | |
186 | see the description of the | |
187 | \*sPWB/UNIX\*n systems, | |
188 | .[ | |
189 | dolotta mashey workbench software engineering | |
190 | .] | |
191 | .[ | |
192 | dolotta haight mashey workbench bstj | |
193 | %Q This issue | |
194 | .] | |
195 | for example. | |
196 | There are also much smaller, though somewhat restricted, | |
197 | versions of the system. | |
198 | .[ | |
199 | lycklama microprocessor bstj | |
200 | %Q This issue | |
201 | .] | |
202 | .PP | |
203 | Our own \*sPDP\*n-11 has two | |
204 | 200-Mb moving-head disks | |
205 | for file system storage and swapping. | |
206 | There are 20 variable-speed | |
207 | communications interfaces | |
208 | attached to 300- and 1200-baud data sets, | |
209 | and an additional 12 communication lines | |
210 | hard-wired to 9600-baud terminals and | |
211 | satellite computers. | |
212 | There are also several 2400- and 4800-baud | |
213 | synchronous communication interfaces | |
214 | used for machine-to-machine file transfer. | |
215 | Finally, there is a variety | |
216 | of miscellaneous | |
217 | devices including | |
218 | nine-track magnetic tape, | |
219 | a line printer, | |
220 | a voice synthesizer, | |
221 | a phototypesetter, | |
222 | a digital switching network, | |
223 | and a chess machine. | |
224 | .PP | |
225 | The preponderance of | |
226 | .UX | |
227 | software is written in the | |
228 | abovementioned C language. | |
229 | .[ | |
230 | c programming language kernighan ritchie prentice-hall | |
231 | .] | |
232 | Early versions of the operating system were written in assembly language, | |
233 | but during the summer of 1973, it was rewritten in C. | |
234 | The size of the new system was about one-third greater | |
235 | than that of the old. | |
236 | Since the new system not only became much easier to | |
237 | understand and to modify but also | |
238 | included | |
239 | many functional improvements, | |
240 | including multiprogramming and the ability to | |
241 | share reentrant code among several user programs, | |
242 | we consider this increase in size quite acceptable. | |
243 | .SH | |
244 | III. THE FILE SYSTEM | |
245 | .PP | |
246 | The most important role of | |
247 | the system | |
248 | is to provide | |
249 | a file system. | |
250 | From the point of view of the user, there | |
251 | are three kinds of files: ordinary disk files, | |
252 | directories, and special files. | |
253 | .SH | |
254 | 3.1 Ordinary files | |
255 | .PP | |
256 | A file | |
257 | contains whatever information the user places on it, | |
258 | for example, symbolic or binary | |
259 | (object) programs. | |
260 | No particular structuring is expected by the system. | |
261 | A file of text consists simply of a string | |
262 | of characters, with lines demarcated by the newline character. | |
263 | Binary programs are sequences of words as | |
264 | they will appear in core memory when the program | |
265 | starts executing. | |
266 | A few user programs manipulate files with more | |
267 | structure; | |
268 | for example, the assembler generates, and the loader | |
269 | expects, an object file in a particular format. | |
270 | However, | |
271 | the structure of files is controlled by | |
272 | the programs that use them, not by the system. | |
273 | .SH | |
274 | 3.2 Directories | |
275 | .PP | |
276 | Directories provide | |
277 | the mapping between the names of files | |
278 | and the files themselves, and thus | |
279 | induce a structure on the file system as a whole. | |
280 | Each user has a directory of his own files; | |
281 | he may also create subdirectories to contain | |
282 | groups of files conveniently treated together. | |
283 | A directory behaves exactly like an ordinary file except that it | |
284 | cannot be written on by unprivileged programs, so that the system | |
285 | controls the contents of directories. | |
286 | However, anyone with | |
287 | appropriate permission may read a directory just like any other file. | |
288 | .PP | |
289 | The system maintains several directories | |
290 | for its own use. | |
291 | One of these is the | |
292 | .UL root | |
293 | directory. | |
294 | All files in the system can be found by tracing | |
295 | a path through a chain of directories | |
296 | until the desired file is reached. | |
297 | The starting point for such searches is often the | |
298 | .UL root . | |
299 | Other system directories contain all the programs provided | |
300 | for general use; that is, all the | |
301 | .IT commands . | |
302 | As will be seen, however, it is by no means necessary | |
303 | that a program reside in one of these directories for it | |
304 | to be executed. | |
305 | .PP | |
306 | Files are named by sequences of 14 or | |
307 | fewer characters. | |
308 | When the name of a file is specified to the | |
309 | system, it may be in the form of a | |
310 | .IT path | |
311 | .IT name , | |
312 | which | |
313 | is a sequence of directory names separated by slashes, ``/\^'', | |
314 | and ending in a file name. | |
315 | If the sequence begins with a slash, the search begins in the | |
316 | root directory. | |
317 | The name | |
318 | .UL /alpha/beta/gamma | |
319 | causes the system to search | |
320 | the root for directory | |
321 | .UL alpha , | |
322 | then to search | |
323 | .UL alpha | |
324 | for | |
325 | .UL beta , | |
326 | finally to find | |
327 | .UL gamma | |
328 | in | |
329 | .UL beta . | |
330 | .UL \&gamma | |
331 | may be an ordinary file, a directory, or a special | |
332 | file. | |
333 | As a limiting case, the name ``/\^'' refers to the root itself. | |
334 | .PP | |
335 | A path name not starting with ``/\^'' causes the system to begin the | |
336 | search in the user's current directory. | |
337 | Thus, the name | |
338 | .UL alpha/beta | |
339 | specifies the file named | |
340 | .UL beta | |
341 | in | |
342 | subdirectory | |
343 | .UL alpha | |
344 | of the current | |
345 | directory. | |
346 | The simplest kind of name, for example, | |
347 | .UL alpha , | |
348 | refers to a file that itself is found in the current | |
349 | directory. | |
350 | As another limiting case, the null file name refers | |
351 | to the current directory. | |
352 | .PP | |
353 | The same non-directory file may appear in several directories under | |
354 | possibly different names. | |
355 | This feature is called | |
356 | .IT linking ; | |
357 | a directory entry for a file is sometimes called a link. | |
358 | The | |
359 | .UX | |
360 | system | |
361 | differs from other systems in which linking is permitted | |
362 | in that all links to a file have equal status. | |
363 | That is, a file does not exist within a particular directory; | |
364 | the directory entry for a file consists merely | |
365 | of its name and a pointer to the information actually | |
366 | describing the file. | |
367 | Thus a file exists independently of any | |
368 | directory entry, although in practice a file is made to | |
369 | disappear along with the last link to it. | |
370 | .PP | |
371 | Each directory always has at least two entries. | |
372 | The name | |
373 | ``\|\fB.\|\fP'' in each directory refers to the directory itself. | |
374 | Thus a program | |
375 | may read the current directory under the name ``\fB\|.\|\fP'' without knowing | |
376 | its complete path name. | |
377 | The name ``\fB\|.\|.\|\fP'' by convention refers to the parent of the | |
378 | directory in which it appears, that is, to the directory in which | |
379 | it was created. | |
380 | .PP | |
381 | The directory structure is constrained to have the form | |
382 | of a rooted tree. | |
383 | Except for the special entries ``\|\fB\|.\|\fP'' and ``\fB\|.\|.\|\fP'', each directory | |
384 | must appear as an entry in exactly one other directory, which is its | |
385 | parent. | |
386 | The reason for this is to simplify the writing of programs | |
387 | that visit subtrees of the directory structure, and more | |
388 | important, to avoid the separation of portions of the hierarchy. | |
389 | If arbitrary links to directories were permitted, it would | |
390 | be quite difficult to detect when the last connection from | |
391 | the root to a directory was severed. | |
392 | .SH | |
393 | 3.3 Special files | |
394 | .PP | |
395 | Special files constitute the most unusual feature of the | |
396 | .UX | |
397 | file system. | |
398 | Each supported I/O device | |
399 | is associated with at least one such file. | |
400 | Special files are read and written just like ordinary | |
401 | disk files, but requests to read or write result in activation of the associated | |
402 | device. | |
403 | An entry for each special file resides in directory | |
404 | .UL /dev , | |
405 | although a link may be made to one of these files | |
406 | just as it may to an ordinary file. | |
407 | Thus, for example, | |
408 | to write on a magnetic tape | |
409 | one may write on the file | |
410 | .UL /dev/mt . | |
411 | Special files exist for each communication line, each disk, | |
412 | each tape drive, | |
413 | and for physical main memory. | |
414 | Of course, | |
415 | the active disks | |
416 | and the memory special file are protected from | |
417 | indiscriminate access. | |
418 | .PP | |
419 | There is a threefold advantage in treating | |
420 | I/O devices this way: | |
421 | file and device I/O | |
422 | are as similar as possible; | |
423 | file and device names have the same | |
424 | syntax and meaning, so that | |
425 | a program expecting a file name | |
426 | as a parameter can be passed a device | |
427 | name; finally, | |
428 | special files are subject to the same | |
429 | protection mechanism as regular files. | |
430 | .SH | |
431 | 3.4 Removable file systems | |
432 | .PP | |
433 | Although the root of the file system is always stored on the same | |
434 | device, | |
435 | it is not necessary that the entire file system hierarchy | |
436 | reside on this device. | |
437 | There is a | |
438 | .UL mount | |
439 | system request with two arguments: | |
440 | the name of an existing ordinary file, and the name of a special | |
441 | file whose associated | |
442 | storage volume (e.g., a disk pack) should have the structure | |
443 | of an independent file system | |
444 | containing its own directory hierarchy. | |
445 | The effect of | |
446 | .UL mount | |
447 | is to cause | |
448 | references to the heretofore ordinary file | |
449 | to refer instead to the root directory | |
450 | of the file system on the removable volume. | |
451 | In effect, | |
452 | .UL mount | |
453 | replaces a leaf of the hierarchy tree (the ordinary file) | |
454 | by a whole new subtree (the hierarchy stored on the | |
455 | removable volume). | |
456 | After the | |
457 | .UL mount , | |
458 | there is virtually no distinction | |
459 | between files on the removable volume and those in the | |
460 | permanent file system. | |
461 | In our installation, for example, | |
462 | the root directory resides | |
463 | on a small partition of one of | |
464 | our disk drives, | |
465 | while the other drive, | |
466 | which contains the user's files, | |
467 | is mounted by the system initialization | |
468 | sequence. | |
469 | A mountable file system is generated by | |
470 | writing on its corresponding special file. | |
471 | A utility program is available to create | |
472 | an empty file system, | |
473 | or one may simply copy an existing file system. | |
474 | .PP | |
475 | There is only one exception to the rule of identical | |
476 | treatment of files on different devices: | |
477 | no link may exist between one file system hierarchy and | |
478 | another. | |
479 | This restriction is enforced so as to avoid | |
480 | the elaborate bookkeeping | |
481 | that would otherwise be required to assure removal of the links | |
482 | whenever the removable volume is dismounted. | |
483 | .SH | |
484 | 3.5 Protection | |
485 | .PP | |
486 | Although the access control scheme | |
487 | is quite simple, it has some unusual features. | |
488 | Each user of the system is assigned a unique | |
489 | user identification number. | |
490 | When a file is created, it is marked with | |
491 | the user \*sID\*n of its owner. | |
492 | Also given for new files | |
493 | is a set of ten protection bits. | |
494 | Nine of these specify | |
495 | independently read, write, and execute permission | |
496 | for the | |
497 | owner of the file, | |
498 | for other members of his group, | |
499 | and for all remaining users. | |
500 | .PP | |
501 | If the tenth bit is on, the system | |
502 | will temporarily change the user identification | |
503 | (hereafter, user \*sID\*n) | |
504 | of the current user to that of the creator of the file whenever | |
505 | the file is executed as a program. | |
506 | This change in user \*sID\*n is effective only | |
507 | during the execution of the program that calls for it. | |
508 | The set-user-\*sID\*n feature provides | |
509 | for privileged programs that may use files | |
510 | inaccessible to other users. | |
511 | For example, a program may keep an accounting file | |
512 | that should neither be read nor changed | |
513 | except by the program itself. | |
514 | If the set-user-\*sID\*n bit is on for the | |
515 | program, it may access the file although | |
516 | this access might be forbidden to other programs | |
517 | invoked by the given program's user. | |
518 | Since the actual user \*sID\*n | |
519 | of the invoker of any program | |
520 | is always available, | |
521 | set-user-\*sID\*n programs | |
522 | may take any measures desired to satisfy themselves | |
523 | as to their invoker's credentials. | |
524 | This mechanism is used to allow users to execute | |
525 | the carefully written | |
526 | commands | |
527 | that call privileged system entries. | |
528 | For example, there is a system entry | |
529 | invokable only by the ``super-user'' (below) | |
530 | that creates | |
531 | an empty directory. | |
532 | As indicated above, directories are expected to | |
533 | have entries for ``\fB\|.\|\fP'' and ``\fB\|.\|.\|\fP''. | |
534 | The command which creates a directory | |
535 | is owned by the super-user | |
536 | and has the set-user-\*sID\*n bit set. | |
537 | After it checks its invoker's authorization to | |
538 | create the specified directory, | |
539 | it creates it and makes the entries | |
540 | for ``\fB\|.\|\fP'' and ``\fB\|.\|.\|\fP''. | |
541 | .PP | |
542 | Because anyone may set the set-user-\*sID\*n | |
543 | bit on one of his own files, | |
544 | this mechanism is generally | |
545 | available without administrative intervention. | |
546 | For example, | |
547 | this protection scheme easily solves the \*sMOO\*n | |
548 | accounting problem posed by ``Aleph-null.'' | |
549 | .[ | |
550 | aleph null software practice | |
551 | .] | |
552 | .PP | |
553 | The system recognizes one particular user \*sID\*n (that of the ``super-user'') as | |
554 | exempt from the usual constraints on file access; thus (for example), | |
555 | programs may be written to dump and reload the file | |
556 | system without | |
557 | unwanted interference from the protection | |
558 | system. |