implement

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

.de P1
.DS
..
.de P2
.DE
..
.de UL
.lg 0
.if n .ul
\%\&\\$3\f3\\$1\fR\&\\$2
.lg
..
.de UC
\&\\$3\s-1\\$1\\s0\&\\$2
..
.de IT
.lg 0
.if n .ul
\%\&\\$3\f2\\$1\fR\&\\$2
.lg
..
.de SP
.sp \\$1
..
.hw device
.TL
UNIX Implementation
.AU "MH 2C-523" 2394
K. Thompson
.AI
.MH
.AB
This paper describes in high-level terms the
implementation of the resident
.UX
kernel.
This discussion is broken into three parts.
The first part describes
how the
.UX
system views processes, users, and programs.
The second part describes the I/O system.
The last part describes the
.UX
file system.
.AE
.NH
INTRODUCTION
.PP
The
.UX
kernel consists of about 10,000
lines of C code and about 1,000 lines of assembly code.
The assembly code can be further broken down into
200 lines included for
the sake of efficiency
(they could have been written in C)
and 800 lines to perform hardware
functions not possible in C.
.PP
This code represents 5 to 10 percent of what has
been lumped into the broad expression
``the
.UX
operating system.''
The kernel is the only
.UX
code that
cannot be substituted by a user to his
own liking.
For this reason,
the kernel should make as few real
decisions as possible.
This does not mean to allow the user
a million options to do the same thing.
Rather, it means to allow only one way to
do one thing,
but have that way be the least-common divisor
of all the options that might have been provided.
.PP
What is or is not implemented in the kernel
represents both a great responsibility and a great power.
It is a soap-box platform on
``the way things should be done.''
Even so, if
``the way'' is too radical,
no one will follow it.
Every important decision was weighed
carefully.
Throughout,
simplicity has been substituted for efficiency.
Complex algorithms are used only if
their complexity can be localized.
.NH
PROCESS CONTROL
.PP
In the
.UX
system,
a user executes programs in an
environment called a user process.
When a system function is required,
the user process calls the system
as a subroutine.
At some point in this call,
there is a distinct switch of environments.
After this,
the process is said to be a system process.
In the normal definition of processes,
the user and system processes are different
phases of the same process
(they never execute simultaneously).
For protection,
each system process has its own stack.
.PP
The user process may execute
from a read-only text segment,
which is shared by all processes
executing the same code.
There is no
.IT functional
benefit
from shared-text segments.
An
.IT efficiency
benefit comes from the fact
that there is no need to swap read-only
segments out because the original
copy on secondary memory is still current.
This is a great benefit to interactive
programs that tend to be swapped while
waiting for terminal input.
Furthermore,
if two processes are
executing
simultaneously
from the same copy of a read-only segment,
only one copy needs to reside in
primary memory.
This is a secondary effect,
because
simultaneous execution of a program
is not common.
It is ironic that this effect,
which reduces the use of primary memory,
only comes into play when there is
an overabundance of primary memory,
that is,
when there is enough memory
to keep waiting processes loaded.
.PP
All current read-only text segments in the
system are maintained from the
.IT "text table" .
A text table entry holds the location of the
text segment on secondary memory.
If the segment is loaded,
that table also holds the primary memory location
and the count of the number of processes
sharing this entry.
When this count is reduced to zero,
the entry is freed along with any
primary and secondary memory holding the segment.
When a process first executes a shared-text segment,
a text table entry is allocated and the
segment is loaded onto secondary memory.
If a second process executes a text segment
that is already allocated,
the entry reference count is simply incremented.
.PP
A user process has some strictly private
read-write data
contained in its
data segment.
As far as possible,
the system does not use the user's
data segment to hold system data.
In particular,
there are no I/O buffers in the
user address space.
.PP
The user data segment has two growing boundaries.
One, increased automatically by the system
as a result of memory faults,
is used for a stack.
The second boundary is only grown (or shrunk) by
explicit requests.
The contents of newly allocated primary memory
is initialized to zero.
.PP
Also associated and swapped with
a process is a small fixed-size
system data segment.
This segment contains all
the data about the process
that the system needs only when the
process is active.
Examples of the kind of data contained
in the system data segment are:
saved central processor registers,
open file descriptors,
accounting information,
scratch data area,
and the stack for the system phase
of the process.
The system data segment is not
addressable from the user process
and is therefore protected.
.PP
Last,
there is a process table with
one entry per process.
This entry contains all the data
needed by the system when the process
is
.IT not
active.
Examples are
the process's name,
the location of the other segments,
and scheduling information.
The process table entry is allocated
when the process is created, and freed
when the process terminates.
This process entry is always directly
addressable by the kernel.
.PP
Figure 1 shows the relationships
between the various process control
data.
In a sense,
the process table is the
definition of all processes,
because
all the data associated with a process
may be accessed
starting from the process table entry.
.KS
.sp 2.44i
.sp 2v
.ce
Fig. 1\(emProcess control data structure.
.KE
.NH 2
Process creation and program execution
.PP
Processes are created by the system primitive
.UL fork .
The newly created process (child) is a copy of the original process (parent).
There is no detectable sharing of primary memory between the two processes.
(Of course,
if the parent process was executing from a read-only
text segment,
the child will share the text segment.)
Copies of all writable data segments
are made for the child process.
Files that were open before the
.UL fork
are
truly shared after the
.UL fork .
The processes are informed as to their part in the
relationship to
allow them to select their own
(usually non-identical)
destiny.
The parent may
.UL wait
for the termination of
any of its children.
.PP
A process may
.UL exec
a file.
This consists of exchanging the current text and data
segments of the process for new text and data
segments specified in the file.
The old segments are lost.
Doing an
.UL exec
does
.IT not
change processes;
the process that did the
.UL exec
persists,
but
after the
.UL exec
it is executing a different program.
Files that were open
before the
.UL exec
remain open after the
.UL exec .
.PP
If a program,
say the first pass of a compiler,
wishes to overlay itself with another program,
say the second pass,
then it simply
.UL exec s
the second program.
This is analogous
to a ``goto.''
If a program wishes to regain control
after
.UL exec ing
a second program,
it should
.UL fork
a child process,
have the child
.UL exec
the second program, and
have the parent
.UL wait
for the child.
This is analogous to a ``call.''
Breaking up the call into a binding followed by
a transfer is similar to the subroutine linkage in
SL-5.
.[
griswold hanson sl5 overview
.]
.NH 2
Swapping
.PP
The major data associated with a process
(the user data segment,
the system data segment, and
the text segment)
are swapped to and from secondary
memory, as needed.
The user data segment and the system data segment
are kept in contiguous primary memory to reduce
swapping latency.
(When low-latency devices, such as bubbles,
.UC CCD s,
or scatter/gather devices,
are used,
this decision will have to be reconsidered.)
Allocation of both primary
and secondary memory is performed
by the same simple first-fit algorithm.
When a process grows,
a new piece of primary memory is allocated.
The contents of the old memory is copied to the new memory.
The old memory is freed
and the tables are updated.
If there is not enough primary memory,
secondary memory is allocated instead.
The process is swapped out onto the
secondary memory,
ready to be swapped in with
its new size.
.PP
One separate process in the kernel,
the swapping process,
simply swaps the other
processes in and out of primary memory.
It examines the
process table looking for a process
that is swapped out and is
ready to run.
It allocates primary memory for that
process and
reads its segments into
primary memory, where that process competes for the
central processor with other loaded processes.
If no primary memory is available,
the swapping process makes memory available
by examining the process table for processes
that can be swapped out.
It selects a process to swap out,
writes it to secondary memory,
frees the primary memory,
and then goes back to look for a process
to swap in.
.PP
Thus there are two specific algorithms
to the swapping process.
Which of the possibly many processes that
are swapped out is to be swapped in?
This is decided by secondary storage residence
time.
The one with the longest time out is swapped in first.
There is a slight penalty for larger processes.
Which of the possibly many processes that
are loaded is to be swapped out?
Processes that are waiting for slow events
(i.e., not currently running or waiting for
disk I/O)
are picked first,
by age in primary memory,
again with size penalties.
The other processes are examined
by the same age algorithm,
but are not taken out unless they are
at least of some age.
This adds
hysteresis to the swapping and
prevents total thrashing.
.PP
These swapping algorithms are the
most suspect in the system.
With limited primary memory,
these algorithms cause total swapping.
This is not bad in itself, because
the swapping does not impact the
execution of the resident processes.