implement

unix v7是最后一个广泛发布的研究型UNIX版本

Directories are simply files that
users cannot write.
For a further discussion
of the external view of files and directories,
see Ref.\0
.[
ritchie thompson unix bstj 1978
%Q This issue
.].
.PP
The
.UX
file system is a disk data structure
accessed completely through
the block I/O system.
As stated before,
the canonical view of a ``disk'' is
a randomly addressable array of
512-byte blocks.
A file system breaks the disk into
four self-identifying regions.
The first block (address 0)
is unused by the file system.
It is left aside for booting procedures.
The second block (address 1)
contains the so-called ``super-block.''
This block,
among other things,
contains the size of the disk and
the boundaries of the other regions.
Next comes the i-list,
a list of file definitions.
Each file definition is
a 64-byte structure, called an i-node.
The offset of a particular i-node
within the i-list is called its i-number.
The combination of device name
(major and minor numbers) and i-number
serves to uniquely name a particular file.
After the i-list,
and to the end of the disk,
come free storage blocks that
are available for the contents of files.
.PP
The free space on a disk is maintained
by a linked list of available disk blocks.
Every block in this chain contains a disk address
of the next block in the chain.
The remaining space contains the address of up to
50 disk blocks that are also free.
Thus with one I/O operation,
the system obtains 50 free blocks and a
pointer where to find more.
The disk allocation algorithms are
very straightforward.
Since all allocation is in fixed-size
blocks and there is strict accounting of
space,
there is no need to compact or garbage collect.
However,
as disk space becomes dispersed,
latency gradually increases.
Some installations choose to occasionally compact
disk space to reduce latency.
.PP
An i-node contains 13 disk addresses.
The first 10 of these addresses point directly at
the first 10 blocks of a file.
If a file is larger than 10 blocks (5,120 bytes),
then the eleventh address points at a block
that contains the addresses of the next 128 blocks of the file.
If the file is still larger than this
(70,656 bytes),
then the twelfth block points at up to 128 blocks,
each pointing to 128 blocks of the file.
Files yet larger
(8,459,264 bytes)
use the thirteenth address for a ``triple indirect'' address.
The algorithm ends here with the maximum file size
of 1,082,201,087 bytes.
.PP
A logical directory hierarchy is added
to this flat physical structure simply
by adding a new type of file, the directory.
A directory is accessed exactly as an ordinary file.
It contains 16-byte entries consisting of
a 14-byte name and an i-number.
The root of the hierarchy is at a known i-number
(\fIviz.,\fR 2).
The file system structure allows an arbitrary, directed graph
of directories with regular files linked in
at arbitrary places in this graph.
In fact,
very early
.UX
systems used such a structure.
Administration of such a structure became so
chaotic that later systems were restricted
to a directory tree.
Even now,
with regular files linked multiply
into arbitrary places in the tree,
accounting for space has become a problem.
It may become necessary to restrict the entire
structure to a tree,
and allow a new form of linking that
is subservient to the tree structure.
.PP
The file system allows
easy creation,
easy removal,
easy random accessing,
and very easy space allocation.
With most physical addresses confined
to a small contiguous section of disk,
it is also easy to dump, restore, and
check the consistency of the file system.
Large files suffer from indirect addressing,
but the cache prevents most of the implied physical I/O
without adding much execution.
The space overhead properties of this scheme are quite good.
For example,
on one particular file system,
there are 25,000 files containing 130M bytes of data-file content.
The overhead (i-node, indirect blocks, and last block breakage)
is about 11.5M bytes.
The directory structure to support these files
has about 1,500 directories containing 0.6M bytes of directory content
and about 0.5M bytes of overhead in accessing the directories.
Added up any way,
this comes out to less than a 10 percent overhead for actual
stored data.
Most systems have this much overhead in
padded trailing blanks alone.
.NH 2
File system implementation
.PP
Because the i-node defines a file,
the implementation of the file system centers
around access to the i-node.
The system maintains a table of all active
i-nodes.
As a new file is accessed,
the system locates the corresponding i-node,
allocates an i-node table entry, and reads
the i-node into primary memory.
As in the buffer cache,
the table entry is considered to be the current
version of the i-node.
Modifications to the i-node are made to
the table entry.
When the last access to the i-node goes
away,
the table entry is copied back to the
secondary store i-list and the table entry is freed.
.PP
All I/O operations on files are carried out
with the aid of the corresponding i-node table entry.
The accessing of a file is a straightforward
implementation of the algorithms mentioned previously.
The user is not aware of i-nodes and i-numbers.
References to the file system are made in terms of
path names of the directory tree.
Converting a path name into an i-node table entry
is also straightforward.
Starting at some known i-node
(the root or the current directory of some process),
the next component of the path name is
searched by reading the directory.
This gives an i-number and an implied device
(that of the directory).
Thus the next i-node table entry can be accessed.
If that was the last component of the path name,
then this i-node is the result.
If not,
this i-node is the directory needed to look up
the next component of the path name, and the
algorithm is repeated.
.PP
The user process accesses the file system with
certain primitives.
The most common of these are
.UL open ,
.UL create ,
.UL read ,
.UL write ,
.UL seek ,
and
.UL close .
The data structures maintained are shown in Fig. 2.
.KS
.sp 22P
.ce
Fig. 2\(emFile system data structure.
.KE
In the system data segment associated with a user,
there is room for some (usually between 10 and 50) open files.
This open file table consists of pointers that can be used to access
corresponding i-node table entries.
Associated with each of these open files is
a current I/O pointer.
This is a byte offset of
the next read/write operation on the file.
The system treats each read/write request
as random with an implied seek to the
I/O pointer.
The user usually thinks of the file as
sequential with the I/O pointer
automatically counting the number of bytes
that have been read/written from the file.
The user may,
of course,
perform random I/O by setting the I/O pointer
before reads/writes.
.PP
With file sharing,
it is necessary to allow related
processes to share a common I/O pointer
and yet have separate I/O pointers
for independent processes
that access the same file.
With these two conditions,
the I/O pointer cannot reside
in the i-node table nor can
it reside in the list of
open files for the process.
A new table
(the open file table)
was invented for the sole purpose
of holding the I/O pointer.
Processes that share the same open
file
(the result of
.UL fork s)
share a common open file table entry.
A separate open of the same file will
only share the i-node table entry,
but will have distinct open file table entries.
.PP
The main file system primitives are implemented as follows.
.UL \&open
converts a file system path name into an i-node
table entry.
A pointer to the i-node table entry is placed in a
newly created open file table entry.
A pointer to the file table entry is placed in the
system data segment for the process.
.UL \&create
first creates a new i-node entry,
writes the i-number into a directory, and
then builds the same structure as for an
.UL open .
.UL \&read
and
.UL write
just access the i-node entry as described above.
.UL \&seek
simply manipulates the I/O pointer.
No physical seeking is done.
.UL \&close
just frees the structures built by
.UL open
and
.UL create .
Reference counts are kept on the open file table entries and
the i-node table entries to free these structures after
the last reference goes away.
.UL \&unlink
simply decrements the count of the
number of directories pointing at the given i-node.
When the last reference to an i-node table entry
goes away,
if the i-node has no directories pointing to it,
then the file is removed and the i-node is freed.
This delayed removal of files prevents
problems arising from removing active files.
A file may be removed while still open.
The resulting unnamed file vanishes
when the file is closed.
This is a method of obtaining temporary files.
.PP
There is a type of unnamed
.UC  FIFO
file called a
.UL pipe.
Implementation of
.UL pipe s
consists of implied
.UL seek s
before each
.UL read
or
.UL write
in order to implement
first-in-first-out.
There are also checks and synchronization
to prevent the
writer from grossly outproducing the
reader and to prevent the reader from
overtaking the writer.
.NH 2
Mounted file systems
.PP
The file system of a
.UX
system
starts with some designated block device
formatted as described above to contain
a hierarchy.
The root of this structure is the root of
the
.UX
file system.
A second formatted block device may be
mounted
at any leaf of
the current hierarchy.
This logically extends the current hierarchy.
The implementation of
mounting
is trivial.
A mount table is maintained containing
pairs of designated leaf i-nodes and
block devices.
When converting a path name into an i-node,
a check is made to see if the new i-node is a
designated leaf.
If it is,
the i-node of the root
of the block device replaces it.
.PP
Allocation of space for a file is taken
from the free pool on the device on which the
file lives.
Thus a file system consisting of many
mounted devices does not have a common pool of
free secondary storage space.
This separation of space on different
devices is necessary to allow easy
unmounting
of a device.
.NH 2
Other system functions
.PP
There are some other things that the system
does for the user\-a
little accounting,
a little tracing/debugging,
and a little access protection.
Most of these things are not very
well developed
because our use of the system in computing science research
does not need them.
There are some features that are missed in some
applications, for example, better inter-process communication.
.PP
The
.UX
kernel is an I/O multiplexer more than
a complete operating system.
This is as it should be.
Because of this outlook,
many features are
found in most
other operating systems that are missing from the
.UX
kernel.
For example,
the
.UX
kernel does not support
file access methods,
file disposition,
file formats,
file maximum size,
spooling,
command language,
logical records,
physical records,
assignment of logical file names,
logical file names,
more than one character set,
an operator's console,
an operator,
log-in,
or log-out.
Many of these things are symptoms rather than features.
Many of these things are implemented
in user software
using the kernel as a tool.
A good example of this is the command language.
.[
bourne shell 1978 bstj
%Q This issue
.]
Each user may have his own command language.
Maintenance of such code is as easy as
maintaining user code.
The idea of implementing ``system'' code with general
user primitives
comes directly from
.UC  MULTICS .
.[
organick multics 1972
.]
.LP
.[
$LIST$
.]