![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to implement CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 04.implement|
Return to implement CVS log | Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 04.implement |
1.1 root 1: .\" @(#)implement 6.2 (Berkeley) 6/17/86
2: .\"
3: .EH 'PS2:4-%''UNIX Implementation'
4: .OH 'UNIX Implementation''PS2:4-%'
5: .de P1
6: .DS
7: ..
8: .de P2
9: .DE
10: ..
11: .de UL
12: .lg 0
13: .if n .ul
14: \%\&\\$3\f3\\$1\fR\&\\$2
15: .lg
16: ..
17: .de UC
18: \&\\$3\s-1\\$1\\s0\&\\$2
19: ..
20: .de IT
21: .lg 0
22: .if n .ul
23: \%\&\\$3\f2\\$1\fR\&\\$2
24: .lg
25: ..
26: .de SP
27: .sp \\$1
28: ..
29: .hw device
30: .TL
31: UNIX Implementation
32: .AU "MH 2C-523" 2394
33: K. Thompson
34: .AI
35: .MH
36: .AB
37: This paper describes in high-level terms the
38: implementation of the resident
39: .UX
40: kernel.
41: This discussion is broken into three parts.
42: The first part describes
43: how the
44: .UX
45: system views processes, users, and programs.
46: The second part describes the I/O system.
47: The last part describes the
48: .UX
49: file system.
50: .AE
51: .NH
52: INTRODUCTION
53: .PP
54: The
55: .UX
56: kernel consists of about 10,000
57: lines of C code and about 1,000 lines of assembly code.
58: The assembly code can be further broken down into
59: 200 lines included for
60: the sake of efficiency
61: (they could have been written in C)
62: and 800 lines to perform hardware
63: functions not possible in C.
64: .PP
65: This code represents 5 to 10 percent of what has
66: been lumped into the broad expression
67: ``the
68: .UX
69: operating system.''
70: The kernel is the only
71: .UX
72: code that
73: cannot be substituted by a user to his
74: own liking.
75: For this reason,
76: the kernel should make as few real
77: decisions as possible.
78: This does not mean to allow the user
79: a million options to do the same thing.
80: Rather, it means to allow only one way to
81: do one thing,
82: but have that way be the least-common divisor
83: of all the options that might have been provided.
84: .PP
85: What is or is not implemented in the kernel
86: represents both a great responsibility and a great power.
87: It is a soap-box platform on
88: ``the way things should be done.''
89: Even so, if
90: ``the way'' is too radical,
91: no one will follow it.
92: Every important decision was weighed
93: carefully.
94: Throughout,
95: simplicity has been substituted for efficiency.
96: Complex algorithms are used only if
97: their complexity can be localized.
98: .NH
99: PROCESS CONTROL
100: .PP
101: In the
102: .UX
103: system,
104: a user executes programs in an
105: environment called a user process.
106: When a system function is required,
107: the user process calls the system
108: as a subroutine.
109: At some point in this call,
110: there is a distinct switch of environments.
111: After this,
112: the process is said to be a system process.
113: In the normal definition of processes,
114: the user and system processes are different
115: phases of the same process
116: (they never execute simultaneously).
117: For protection,
118: each system process has its own stack.
119: .PP
120: The user process may execute
121: from a read-only text segment,
122: which is shared by all processes
123: executing the same code.
124: There is no
125: .IT functional
126: benefit
127: from shared-text segments.
128: An
129: .IT efficiency
130: benefit comes from the fact
131: that there is no need to swap read-only
132: segments out because the original
133: copy on secondary memory is still current.
134: This is a great benefit to interactive
135: programs that tend to be swapped while
136: waiting for terminal input.
137: Furthermore,
138: if two processes are
139: executing
140: simultaneously
141: from the same copy of a read-only segment,
142: only one copy needs to reside in
143: primary memory.
144: This is a secondary effect,
145: because
146: simultaneous execution of a program
147: is not common.
148: It is ironic that this effect,
149: which reduces the use of primary memory,
150: only comes into play when there is
151: an overabundance of primary memory,
152: that is,
153: when there is enough memory
154: to keep waiting processes loaded.
155: .PP
156: All current read-only text segments in the
157: system are maintained from the
158: .IT "text table" .
159: A text table entry holds the location of the
160: text segment on secondary memory.
161: If the segment is loaded,
162: that table also holds the primary memory location
163: and the count of the number of processes
164: sharing this entry.
165: When this count is reduced to zero,
166: the entry is freed along with any
167: primary and secondary memory holding the segment.
168: When a process first executes a shared-text segment,
169: a text table entry is allocated and the
170: segment is loaded onto secondary memory.
171: If a second process executes a text segment
172: that is already allocated,
173: the entry reference count is simply incremented.
174: .PP
175: A user process has some strictly private
176: read-write data
177: contained in its
178: data segment.
179: As far as possible,
180: the system does not use the user's
181: data segment to hold system data.
182: In particular,
183: there are no I/O buffers in the
184: user address space.
185: .PP
186: The user data segment has two growing boundaries.
187: One, increased automatically by the system
188: as a result of memory faults,
189: is used for a stack.
190: The second boundary is only grown (or shrunk) by
191: explicit requests.
192: The contents of newly allocated primary memory
193: is initialized to zero.
194: .PP
195: Also associated and swapped with
196: a process is a small fixed-size
197: system data segment.
198: This segment contains all
199: the data about the process
200: that the system needs only when the
201: process is active.
202: Examples of the kind of data contained
203: in the system data segment are:
204: saved central processor registers,
205: open file descriptors,
206: accounting information,
207: scratch data area,
208: and the stack for the system phase
209: of the process.
210: The system data segment is not
211: addressable from the user process
212: and is therefore protected.
213: .PP
214: Last,
215: there is a process table with
216: one entry per process.
217: This entry contains all the data
218: needed by the system when the process
219: is
220: .IT not
221: active.
222: Examples are
223: the process's name,
224: the location of the other segments,
225: and scheduling information.
226: The process table entry is allocated
227: when the process is created, and freed
228: when the process terminates.
229: This process entry is always directly
230: addressable by the kernel.
231: .PP
232: Figure 1 shows the relationships
233: between the various process control
234: data.
235: In a sense,
236: the process table is the
237: definition of all processes,
238: because
239: all the data associated with a process
240: may be accessed
241: starting from the process table entry.
242: .KF
243: .in .375i
244: .so fig1.pic
245: .in -.375i
246: .sp 2v
247: .ce
248: Fig. 1\(emProcess control data structure.
249: .KE
250: .NH 2
251: Process creation and program execution
252: .PP
253: Processes are created by the system primitive
254: .UL fork .
255: The newly created process (child) is a copy of the original process (parent).
256: There is no detectable sharing of primary memory between the two processes.
257: (Of course,
258: if the parent process was executing from a read-only
259: text segment,
260: the child will share the text segment.)
261: Copies of all writable data segments
262: are made for the child process.
263: Files that were open before the
264: .UL fork
265: are
266: truly shared after the
267: .UL fork .
268: The processes are informed as to their part in the
269: relationship to
270: allow them to select their own
271: (usually non-identical)
272: destiny.
273: The parent may
274: .UL wait
275: for the termination of
276: any of its children.
277: .PP
278: A process may
279: .UL exec
280: a file.
281: This consists of exchanging the current text and data
282: segments of the process for new text and data
283: segments specified in the file.
284: The old segments are lost.
285: Doing an
286: .UL exec
287: does
288: .IT not
289: change processes;
290: the process that did the
291: .UL exec
292: persists,
293: but
294: after the
295: .UL exec
296: it is executing a different program.
297: Files that were open
298: before the
299: .UL exec
300: remain open after the
301: .UL exec .
302: .PP
303: If a program,
304: say the first pass of a compiler,
305: wishes to overlay itself with another program,
306: say the second pass,
307: then it simply
308: .UL exec s
309: the second program.
310: This is analogous
311: to a ``goto.''
312: If a program wishes to regain control
313: after
314: .UL exec ing
315: a second program,
316: it should
317: .UL fork
318: a child process,
319: have the child
320: .UL exec
321: the second program, and
322: have the parent
323: .UL wait
324: for the child.
325: This is analogous to a ``call.''
326: Breaking up the call into a binding followed by
327: a transfer is similar to the subroutine linkage in
328: SL-5.
329: .[
330: griswold hanson sl5 overview
331: .]
332: .NH 2
333: Swapping
334: .PP
335: The major data associated with a process
336: (the user data segment,
337: the system data segment, and
338: the text segment)
339: are swapped to and from secondary
340: memory, as needed.
341: The user data segment and the system data segment
342: are kept in contiguous primary memory to reduce
343: swapping latency.
344: (When low-latency devices, such as bubbles,
345: .UC CCD s,
346: or scatter/gather devices,
347: are used,
348: this decision will have to be reconsidered.)
349: Allocation of both primary
350: and secondary memory is performed
351: by the same simple first-fit algorithm.
352: When a process grows,
353: a new piece of primary memory is allocated.
354: The contents of the old memory is copied to the new memory.
355: The old memory is freed
356: and the tables are updated.
357: If there is not enough primary memory,
358: secondary memory is allocated instead.
359: The process is swapped out onto the
360: secondary memory,
361: ready to be swapped in with
362: its new size.
363: .PP
364: One separate process in the kernel,
365: the swapping process,
366: simply swaps the other
367: processes in and out of primary memory.
368: It examines the
369: process table looking for a process
370: that is swapped out and is
371: ready to run.
372: It allocates primary memory for that
373: process and
374: reads its segments into
375: primary memory, where that process competes for the
376: central processor with other loaded processes.
377: If no primary memory is available,
378: the swapping process makes memory available
379: by examining the process table for processes
380: that can be swapped out.
381: It selects a process to swap out,
382: writes it to secondary memory,
383: frees the primary memory,
384: and then goes back to look for a process
385: to swap in.
386: .PP
387: Thus there are two specific algorithms
388: to the swapping process.
389: Which of the possibly many processes that
390: are swapped out is to be swapped in?
391: This is decided by secondary storage residence
392: time.
393: The one with the longest time out is swapped in first.
394: There is a slight penalty for larger processes.
395: Which of the possibly many processes that
396: are loaded is to be swapped out?
397: Processes that are waiting for slow events
398: (i.e., not currently running or waiting for
399: disk I/O)
400: are picked first,
401: by age in primary memory,
402: again with size penalties.
403: The other processes are examined
404: by the same age algorithm,
405: but are not taken out unless they are
406: at least of some age.
407: This adds
408: hysteresis to the swapping and
409: prevents total thrashing.
410: .PP
411: These swapping algorithms are the
412: most suspect in the system.
413: With limited primary memory,
414: these algorithms cause total swapping.
415: This is not bad in itself, because
416: the swapping does not impact the
417: execution of the resident processes.
418: However, if the swapping device must
419: also be used for file storage,
420: the swapping traffic severely
421: impacts the file system traffic.
422: It is exactly these small systems
423: that tend to double usage of limited disk
424: resources.
425: .NH 2
426: Synchronization and scheduling
427: .PP
428: Process synchronization is accomplished by having processes
429: wait for events.
430: Events are represented by arbitrary integers.
431: By convention,
432: events are chosen to be addresses of
433: tables associated with those events.
434: For example, a process that is waiting for
435: any of its children to terminate will wait
436: for an event that is the address of
437: its own process table entry.
438: When a process terminates,
439: it signals the event represented by
440: its parent's process table entry.
441: Signaling an event on which no process
442: is waiting has no effect.
443: Similarly,
444: signaling an event on which many processes
445: are waiting will wake all of them up.
446: This differs considerably from
447: Dijkstra's P and V
448: synchronization operations,
449: .[
450: dijkstra sequential processes 1968
451: .]
452: in that
453: no memory is associated with events.
454: Thus there need be no allocation of events
455: prior to their use.
456: Events exist simply by being used.
457: .PP
458: On the negative side,
459: because there is no memory associated with events,
460: no notion of ``how much''
461: can be signaled via the event mechanism.
462: For example,
463: processes that want memory might
464: wait on an event associated with
465: memory allocation.
466: When any amount of memory becomes available,
467: the event would be signaled.
468: All the competing processes would then wake
469: up to fight over the new memory.
470: (In reality,
471: the swapping process is the only process
472: that waits for primary memory to become available.)
473: .PP
474: If an event occurs
475: between the time a process decides
476: to wait for that event and the
477: time that process enters the wait state,
478: then
479: the process will wait on an event that has
480: already happened (and may never happen again).
481: This race condition happens because there is no memory associated with
482: the event to indicate that the event has occurred;
483: the only action of an event is to change a set of processes
484: from wait state to run state.
485: This problem is relieved largely
486: by the fact that process switching can
487: only occur in the kernel by explicit calls
488: to the event-wait mechanism.
489: If the event in question is signaled by another
490: process,
491: then there is no problem.
492: But if the event is signaled by a hardware
493: interrupt,
494: then special care must be taken.
495: These synchronization races pose the biggest
496: problem when
497: .UX
498: is adapted to multiple-processor configurations.
499: .[
500: hawley meyer multiprocessing unix
501: .]
502: .PP
503: The event-wait code in the kernel
504: is like a co-routine linkage.
505: At any time,
506: all but one of the processes has called event-wait.
507: The remaining process is the one currently executing.
508: When it calls event-wait,
509: a process whose event has been signaled
510: is selected and that process
511: returns from its call to event-wait.
512: .PP
513: Which of the runable processes is to run next?
514: Associated with each process is a priority.
515: The priority of a system process is assigned by the code
516: issuing the wait on an event.
517: This is roughly equivalent to the response
518: that one would expect on such an event.
519: Disk events have high priority,
520: teletype events are low,
521: and time-of-day events are very low.
522: (From observation,
523: the difference in system process priorities
524: has little or no performance impact.)
525: All user-process priorities are lower than the
526: lowest system priority.
527: User-process priorities are assigned
528: by an algorithm based on the
529: recent ratio of the amount of compute time to real time consumed
530: by the process.
531: A process that has used a lot of
532: compute time in the last real-time
533: unit is assigned a low user priority.
534: Because interactive processes are characterized
535: by low ratios of compute to real time,
536: interactive response is maintained without any
537: special arrangements.
538: .PP
539: The scheduling algorithm simply picks
540: the process with the highest priority,
541: thus
542: picking all system processes first and
543: user processes second.
544: The compute-to-real-time ratio is updated
545: every second.
546: Thus,
547: all other things being equal,
548: looping user processes will be
549: scheduled round-robin with a
550: 1-second quantum.
551: A high-priority process waking up will
552: preempt a running, low-priority process.
553: The scheduling algorithm has a very desirable
554: negative feedback character.
555: If a process uses its high priority
556: to hog the computer,
557: its priority will drop.
558: At the same time, if a low-priority
559: process is ignored for a long time,
560: its priority will rise.
561: .NH
562: I/O SYSTEM
563: .PP
564: The I/O system
565: is broken into two completely separate systems:
566: the block I/O system and the character I/O system.
567: In retrospect,
568: the names should have been ``structured I/O''
569: and ``unstructured I/O,'' respectively;
570: while the term ``block I/O'' has some meaning,
571: ``character I/O'' is a complete misnomer.
572: .PP
573: Devices are characterized by a major device number,
574: a minor device number, and
575: a class (block or character).
576: For each class,
577: there is an array of entry points into the device drivers.
578: The major device number is used to index the array
579: when calling the code for a particular device driver.
580: The minor device number is passed to the
581: device driver as an argument.
582: The minor number has no significance other
583: than that attributed to it by the driver.
584: Usually,
585: the driver uses the minor number to access
586: one of several identical physical devices.
587: .PP
588: The use of the array of entry points
589: (configuration table)
590: as the only connection between the
591: system code and the device drivers is
592: very important.
593: Early versions of the system had a much
594: less formal connection with the drivers,
595: so that it was extremely hard to handcraft
596: differently configured systems.
597: Now it is possible to create new
598: device drivers in an average of a few hours.
599: The configuration table in most cases
600: is created automatically by a program
601: that reads the system's parts list.
602: .NH 2
603: Block I/O system
604: .PP
605: The model block I/O device consists
606: of randomly addressed, secondary
607: memory blocks of 512 bytes each.
608: The blocks are uniformly addressed
609: 0, 1, .\|.\|. up to the size of the device.
610: The block device driver has the job of
611: emulating this model on a
612: physical device.
613: .PP
614: The block I/O devices are accessed
615: through a layer of buffering software.
616: The system maintains a list of buffers
617: (typically between 10 and 70)
618: each assigned a device name and
619: a device address.
620: This buffer pool constitutes a data cache
621: for the block devices.
622: On a read request,
623: the cache is searched for the desired block.
624: If the block is found,
625: the data are made available to the
626: requester without any physical I/O.
627: If the block is not in the cache,
628: the least recently used block in the cache is renamed,
629: the correct device driver is called to
630: fill up the renamed buffer, and then the
631: data are made available.
632: Write requests are handled in an analogous manner.
633: The correct buffer is found
634: and relabeled if necessary.
635: The write is performed simply by marking
636: the buffer as ``dirty.''
637: The physical I/O is then deferred until
638: the buffer is renamed.
639: .PP
640: The benefits in reduction of physical I/O
641: of this scheme are substantial,
642: especially considering the file system implementation.
643: There are,
644: however,
645: some drawbacks.
646: The asynchronous nature of the
647: algorithm makes error reporting
648: and meaningful user error handling
649: almost impossible.
650: The cavalier approach to I/O error
651: handling in the
652: .UX
653: system is partly due to the asynchronous
654: nature of the block I/O system.
655: A second problem is in the delayed writes.
656: If the system stops unexpectedly,
657: it is almost certain that there is a
658: lot of logically complete,
659: but physically incomplete,
660: I/O in the buffers.
661: There is a system primitive to
662: flush all outstanding I/O activity
663: from the buffers.
664: Periodic use of this primitive helps,
665: but does not solve, the problem.
666: Finally,
667: the associativity in the buffers
668: can alter the physical I/O sequence
669: from that of the logical I/O sequence.
670: This means that there are times
671: when data structures on disk are inconsistent,
672: even though the software is careful
673: to perform I/O in the correct order.
674: On non-random devices,
675: notably magnetic tape,
676: the inversions of writes can be disastrous.
677: The problem with magnetic tapes is ``cured'' by
678: allowing only one outstanding write request
679: per drive.
680: .NH 2
681: Character I/O system
682: .PP
683: The character I/O system consists of all
684: devices that do not fall into the block I/O model.
685: This includes the ``classical'' character devices
686: such as communications lines, paper tape, and
687: line printers.
688: It also includes magnetic tape and disks when
689: they are not used in a stereotyped way,
690: for example, 80-byte physical records on tape
691: and track-at-a-time disk copies.
692: In short,
693: the character I/O interface
694: means ``everything other than block.''
695: I/O requests from the user are sent to the
696: device driver essentially unaltered.
697: The implementation of these requests is, of course,
698: up to the device driver.
699: There are guidelines and conventions
700: to help the implementation of
701: certain types of device drivers.
702: .NH 3
703: Disk drivers
704: .PP
705: Disk drivers are implemented
706: with a queue of transaction records.
707: Each record holds a read/write flag,
708: a primary memory address,
709: a secondary memory address, and
710: a transfer byte count.
711: Swapping is accomplished by passing
712: such a record to the swapping device driver.
713: The block I/O interface is implemented by
714: passing such records with requests to
715: fill and empty system buffers.
716: The character I/O interface to the disk
717: drivers create a transaction record that
718: points directly into the user area.
719: The routine that creates this record also insures
720: that the user is not swapped during this
721: I/O transaction.
722: Thus by implementing the general disk driver,
723: it is possible to use the disk
724: as a block device,
725: a character device, and a swap device.
726: The only really disk-specific code in normal
727: disk drivers is the pre-sort of transactions to
728: minimize latency for a particular device, and
729: the actual issuing of the I/O request.
730: .NH 3
731: Character lists
732: .PP
733: Real character-oriented devices may
734: be implemented using the common
735: code to handle character lists.
736: A character list is a queue of characters.
737: One routine puts a character on a queue.
738: Another gets a character from a queue.
739: It is also possible to ask how many
740: characters are currently on a queue.
741: Storage for all queues in the system comes
742: from a single common pool.
743: Putting a character on a queue will allocate
744: space from the common pool and link the
745: character onto the data structure defining the queue.
746: Getting a character from a queue returns
747: the corresponding space to the pool.
748: .PP
749: A typical character-output device
750: (paper tape punch, for example)
751: is implemented by passing characters
752: from the user onto a character queue until
753: some maximum number of characters is on the queue.
754: The I/O is prodded to start as
755: soon as there is anything on the queue
756: and, once started,
757: it is sustained by hardware completion interrupts.
758: Each time there is a completion interrupt,
759: the driver gets the next character from the queue
760: and sends it to the hardware.
761: The number of characters on the queue is checked and,
762: as the count falls through some intermediate level,
763: an event (the queue address) is signaled.
764: The process that is passing characters from
765: the user to the queue can be waiting on the event, and
766: refill the queue to its maximum
767: when the event occurs.
768: .PP
769: A typical character input device
770: (for example, a paper tape reader)
771: is handled in a very similar manner.
772: .PP
773: Another class of character devices is the terminals.
774: A terminal is represented by three
775: character queues.
776: There are two input queues (raw and canonical)
777: and an output queue.
778: Characters going to the output of a terminal
779: are handled by common code exactly as described
780: above.
781: The main difference is that there is also code
782: to interpret the output stream as
783: .UC ASCII
784: characters and to perform some translations,
785: e.g., escapes for deficient terminals.
786: Another common aspect of terminals is code
787: to insert real-time delay after certain control characters.
788: .PP
789: Input on terminals is a little different.
790: Characters are collected from the terminal and
791: placed on a raw input queue.
792: Some device-dependent code conversion and
793: escape interpretation is handled here.
794: When a line is complete in the raw queue,
795: an event is signaled.
796: The code catching this signal then copies a
797: line from the raw queue to a canonical queue
798: performing the character erase and line kill editing.
799: User read requests on terminals can be
800: directed at either the raw or canonical queues.
801: .NH 3
802: Other character devices
803: .PP
804: Finally,
805: there are devices that fit no general category.
806: These devices are set up as character I/O drivers.
807: An example is a driver that reads and writes
808: unmapped primary memory as an I/O device.
809: Some devices are too
810: fast to be treated a character at time,
811: but do not fit the disk I/O mold.
812: Examples are fast communications lines and
813: fast line printers.
814: These devices either have their own buffers
815: or ``borrow'' block I/O buffers for a while and
816: then give them back.
817: .NH
818: THE FILE SYSTEM
819: .PP
820: In the
821: .UX
822: system,
823: a file is a (one-dimensional) array of bytes.
824: No other structure of files is implied by the
825: system.
826: Files are attached anywhere
827: (and possibly multiply)
828: onto a hierarchy of directories.
829: Directories are simply files that
830: users cannot write.
831: For a further discussion
832: of the external view of files and directories,
833: see Ref.\0
834: .[
835: ritchie thompson unix bstj 1978
836: %Q This issue
837: .].
838: .PP
839: The
840: .UX
841: file system is a disk data structure
842: accessed completely through
843: the block I/O system.
844: As stated before,
845: the canonical view of a ``disk'' is
846: a randomly addressable array of
847: 512-byte blocks.
848: A file system breaks the disk into
849: four self-identifying regions.
850: The first block (address 0)
851: is unused by the file system.
852: It is left aside for booting procedures.
853: The second block (address 1)
854: contains the so-called ``super-block.''
855: This block,
856: among other things,
857: contains the size of the disk and
858: the boundaries of the other regions.
859: Next comes the i-list,
860: a list of file definitions.
861: Each file definition is
862: a 64-byte structure, called an i-node.
863: The offset of a particular i-node
864: within the i-list is called its i-number.
865: The combination of device name
866: (major and minor numbers) and i-number
867: serves to uniquely name a particular file.
868: After the i-list,
869: and to the end of the disk,
870: come free storage blocks that
871: are available for the contents of files.
872: .PP
873: The free space on a disk is maintained
874: by a linked list of available disk blocks.
875: Every block in this chain contains a disk address
876: of the next block in the chain.
877: The remaining space contains the address of up to
878: 50 disk blocks that are also free.
879: Thus with one I/O operation,
880: the system obtains 50 free blocks and a
881: pointer where to find more.
882: The disk allocation algorithms are
883: very straightforward.
884: Since all allocation is in fixed-size
885: blocks and there is strict accounting of
886: space,
887: there is no need to compact or garbage collect.
888: However,
889: as disk space becomes dispersed,
890: latency gradually increases.
891: Some installations choose to occasionally compact
892: disk space to reduce latency.
893: .PP
894: An i-node contains 13 disk addresses.
895: The first 10 of these addresses point directly at
896: the first 10 blocks of a file.
897: If a file is larger than 10 blocks (5,120 bytes),
898: then the eleventh address points at a block
899: that contains the addresses of the next 128 blocks of the file.
900: If the file is still larger than this
901: (70,656 bytes),
902: then the twelfth block points at up to 128 blocks,
903: each pointing to 128 blocks of the file.
904: Files yet larger
905: (8,459,264 bytes)
906: use the thirteenth address for a ``triple indirect'' address.
907: The algorithm ends here with the maximum file size
908: of 1,082,201,087 bytes.
909: .PP
910: A logical directory hierarchy is added
911: to this flat physical structure simply
912: by adding a new type of file, the directory.
913: A directory is accessed exactly as an ordinary file.
914: It contains 16-byte entries consisting of
915: a 14-byte name and an i-number.
916: The root of the hierarchy is at a known i-number
917: (\fIviz.,\fR 2).
918: The file system structure allows an arbitrary, directed graph
919: of directories with regular files linked in
920: at arbitrary places in this graph.
921: In fact,
922: very early
923: .UX
924: systems used such a structure.
925: Administration of such a structure became so
926: chaotic that later systems were restricted
927: to a directory tree.
928: Even now,
929: with regular files linked multiply
930: into arbitrary places in the tree,
931: accounting for space has become a problem.
932: It may become necessary to restrict the entire
933: structure to a tree,
934: and allow a new form of linking that
935: is subservient to the tree structure.
936: .PP
937: The file system allows
938: easy creation,
939: easy removal,
940: easy random accessing,
941: and very easy space allocation.
942: With most physical addresses confined
943: to a small contiguous section of disk,
944: it is also easy to dump, restore, and
945: check the consistency of the file system.
946: Large files suffer from indirect addressing,
947: but the cache prevents most of the implied physical I/O
948: without adding much execution.
949: The space overhead properties of this scheme are quite good.
950: For example,
951: on one particular file system,
952: there are 25,000 files containing 130M bytes of data-file content.
953: The overhead (i-node, indirect blocks, and last block breakage)
954: is about 11.5M bytes.
955: The directory structure to support these files
956: has about 1,500 directories containing 0.6M bytes of directory content
957: and about 0.5M bytes of overhead in accessing the directories.
958: Added up any way,
959: this comes out to less than a 10 percent overhead for actual
960: stored data.
961: Most systems have this much overhead in
962: padded trailing blanks alone.
963: .NH 2
964: File system implementation
965: .PP
966: Because the i-node defines a file,
967: the implementation of the file system centers
968: around access to the i-node.
969: The system maintains a table of all active
970: i-nodes.
971: As a new file is accessed,
972: the system locates the corresponding i-node,
973: allocates an i-node table entry, and reads
974: the i-node into primary memory.
975: As in the buffer cache,
976: the table entry is considered to be the current
977: version of the i-node.
978: Modifications to the i-node are made to
979: the table entry.
980: When the last access to the i-node goes
981: away,
982: the table entry is copied back to the
983: secondary store i-list and the table entry is freed.
984: .KF
985: .in .25i
986: .so fig2.pic
987: .in -.25i
988: .sp 2v
989: .ce
990: Fig. 2\(emFile system data structure.
991: .sp
992: .KE
993: .PP
994: All I/O operations on files are carried out
995: with the aid of the corresponding i-node table entry.
996: The accessing of a file is a straightforward
997: implementation of the algorithms mentioned previously.
998: The user is not aware of i-nodes and i-numbers.
999: References to the file system are made in terms of
1000: path names of the directory tree.
1001: Converting a path name into an i-node table entry
1002: is also straightforward.
1003: Starting at some known i-node
1004: (the root or the current directory of some process),
1005: the next component of the path name is
1006: searched by reading the directory.
1007: This gives an i-number and an implied device
1008: (that of the directory).
1009: Thus the next i-node table entry can be accessed.
1010: If that was the last component of the path name,
1011: then this i-node is the result.
1012: If not,
1013: this i-node is the directory needed to look up
1014: the next component of the path name, and the
1015: algorithm is repeated.
1016: .PP
1017: The user process accesses the file system with
1018: certain primitives.
1019: The most common of these are
1020: .UL open ,
1021: .UL create ,
1022: .UL read ,
1023: .UL write ,
1024: .UL seek ,
1025: and
1026: .UL close .
1027: The data structures maintained are shown in Fig. 2.
1028: In the system data segment associated with a user,
1029: there is room for some (usually between 10 and 50) open files.
1030: This open file table consists of pointers that can be used to access
1031: corresponding i-node table entries.
1032: Associated with each of these open files is
1033: a current I/O pointer.
1034: This is a byte offset of
1035: the next read/write operation on the file.
1036: The system treats each read/write request
1037: as random with an implied seek to the
1038: I/O pointer.
1039: The user usually thinks of the file as
1040: sequential with the I/O pointer
1041: automatically counting the number of bytes
1042: that have been read/written from the file.
1043: The user may,
1044: of course,
1045: perform random I/O by setting the I/O pointer
1046: before reads/writes.
1047: .PP
1048: With file sharing,
1049: it is necessary to allow related
1050: processes to share a common I/O pointer
1051: and yet have separate I/O pointers
1052: for independent processes
1053: that access the same file.
1054: With these two conditions,
1055: the I/O pointer cannot reside
1056: in the i-node table nor can
1057: it reside in the list of
1058: open files for the process.
1059: A new table
1060: (the open file table)
1061: was invented for the sole purpose
1062: of holding the I/O pointer.
1063: Processes that share the same open
1064: file
1065: (the result of
1066: .UL fork s)
1067: share a common open file table entry.
1068: A separate open of the same file will
1069: only share the i-node table entry,
1070: but will have distinct open file table entries.
1071: .PP
1072: The main file system primitives are implemented as follows.
1073: .UL \&open
1074: converts a file system path name into an i-node
1075: table entry.
1076: A pointer to the i-node table entry is placed in a
1077: newly created open file table entry.
1078: A pointer to the file table entry is placed in the
1079: system data segment for the process.
1080: .UL \&create
1081: first creates a new i-node entry,
1082: writes the i-number into a directory, and
1083: then builds the same structure as for an
1084: .UL open .
1085: .UL \&read
1086: and
1087: .UL write
1088: just access the i-node entry as described above.
1089: .UL \&seek
1090: simply manipulates the I/O pointer.
1091: No physical seeking is done.
1092: .UL \&close
1093: just frees the structures built by
1094: .UL open
1095: and
1096: .UL create .
1097: Reference counts are kept on the open file table entries and
1098: the i-node table entries to free these structures after
1099: the last reference goes away.
1100: .UL \&unlink
1101: simply decrements the count of the
1102: number of directories pointing at the given i-node.
1103: When the last reference to an i-node table entry
1104: goes away,
1105: if the i-node has no directories pointing to it,
1106: then the file is removed and the i-node is freed.
1107: This delayed removal of files prevents
1108: problems arising from removing active files.
1109: A file may be removed while still open.
1110: The resulting unnamed file vanishes
1111: when the file is closed.
1112: This is a method of obtaining temporary files.
1113: .PP
1114: There is a type of unnamed
1115: .UC FIFO
1116: file called a
1117: .UL pipe.
1118: Implementation of
1119: .UL pipe s
1120: consists of implied
1121: .UL seek s
1122: before each
1123: .UL read
1124: or
1125: .UL write
1126: in order to implement
1127: first-in-first-out.
1128: There are also checks and synchronization
1129: to prevent the
1130: writer from grossly outproducing the
1131: reader and to prevent the reader from
1132: overtaking the writer.
1133: .NH 2
1134: Mounted file systems
1135: .PP
1136: The file system of a
1137: .UX
1138: system
1139: starts with some designated block device
1140: formatted as described above to contain
1141: a hierarchy.
1142: The root of this structure is the root of
1143: the
1144: .UX
1145: file system.
1146: A second formatted block device may be
1147: mounted
1148: at any leaf of
1149: the current hierarchy.
1150: This logically extends the current hierarchy.
1151: The implementation of
1152: mounting
1153: is trivial.
1154: A mount table is maintained containing
1155: pairs of designated leaf i-nodes and
1156: block devices.
1157: When converting a path name into an i-node,
1158: a check is made to see if the new i-node is a
1159: designated leaf.
1160: If it is,
1161: the i-node of the root
1162: of the block device replaces it.
1163: .PP
1164: Allocation of space for a file is taken
1165: from the free pool on the device on which the
1166: file lives.
1167: Thus a file system consisting of many
1168: mounted devices does not have a common pool of
1169: free secondary storage space.
1170: This separation of space on different
1171: devices is necessary to allow easy
1172: unmounting
1173: of a device.
1174: .NH 2
1175: Other system functions
1176: .PP
1177: There are some other things that the system
1178: does for the user\-a
1179: little accounting,
1180: a little tracing/debugging,
1181: and a little access protection.
1182: Most of these things are not very
1183: well developed
1184: because our use of the system in computing science research
1185: does not need them.
1186: There are some features that are missed in some
1187: applications, for example, better inter-process communication.
1188: .PP
1189: The
1190: .UX
1191: kernel is an I/O multiplexer more than
1192: a complete operating system.
1193: This is as it should be.
1194: Because of this outlook,
1195: many features are
1196: found in most
1197: other operating systems that are missing from the
1198: .UX
1199: kernel.
1200: For example,
1201: the
1202: .UX
1203: kernel does not support
1204: file access methods,
1205: file disposition,
1206: file formats,
1207: file maximum size,
1208: spooling,
1209: command language,
1210: logical records,
1211: physical records,
1212: assignment of logical file names,
1213: logical file names,
1214: more than one character set,
1215: an operator's console,
1216: an operator,
1217: log-in,
1218: or log-out.
1219: Many of these things are symptoms rather than features.
1220: Many of these things are implemented
1221: in user software
1222: using the kernel as a tool.
1223: A good example of this is the command language.
1224: .[
1225: bourne shell 1978 bstj
1226: %Q This issue
1227: .]
1228: Each user may have his own command language.
1229: Maintenance of such code is as easy as
1230: maintaining user code.
1231: The idea of implementing ``system'' code with general
1232: user primitives
1233: comes directly from
1234: .UC MULTICS .
1235: .[
1236: organick multics 1972
1237: .]
1238: .LP
1239: .[
1240: $LIST$
1241: .]
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.