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