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