implement

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

However, if the swapping device must
also be used for file storage,
the swapping traffic severely
impacts the file system traffic.
It is exactly these small systems
that tend to double usage of limited disk
resources.
.NH 2
Synchronization and scheduling
.PP
Process synchronization is accomplished by having processes
wait for events.
Events are represented by arbitrary integers.
By convention,
events are chosen to be addresses of
tables associated with those events.
For example, a process that is waiting for
any of its children to terminate will wait
for an event that is the address of
its own process table entry.
When a process terminates,
it signals the event represented by
its parent's process table entry.
Signaling an event on which no process
is waiting has no effect.
Similarly,
signaling an event on which many processes
are waiting will wake all of them up.
This differs considerably from
Dijkstra's P and V
synchronization operations,
.[
dijkstra sequential processes 1968
.]
in that
no memory is associated with events.
Thus there need be no allocation of events
prior to their use.
Events exist simply by being used.
.PP
On the negative side,
because there is no memory associated with events,
no notion of ``how much''
can be signaled via the event mechanism.
For example,
processes that want memory might
wait on an event associated with
memory allocation.
When any amount of memory becomes available,
the event would be signaled.
All the competing processes would then wake
up to fight over the new memory.
(In reality,
the swapping process is the only process
that waits for primary memory to become available.)
.PP
If an event occurs
between the time a process decides
to wait for that event and the
time that process enters the wait state,
then
the process will wait on an event that has
already happened (and may never happen again).
This race condition happens because there is no memory associated with
the event to indicate that the event has occurred;
the only action of an event is to change a set of processes
from wait state to run state.
This problem is relieved largely
by the fact that process switching can
only occur in the kernel by explicit calls
to the event-wait mechanism.
If the event in question is signaled by another
process,
then there is no problem.
But if the event is signaled by a hardware
interrupt,
then special care must be taken.
These synchronization races pose the biggest
problem when
.UX
is adapted to multiple-processor configurations.
.[
hawley meyer multiprocessing unix
.]
.PP
The event-wait code in the kernel
is like a co-routine linkage.
At any time,
all but one of the processes has called event-wait.
The remaining process is the one currently executing.
When it calls event-wait,
a process whose event has been signaled
is selected and that process
returns from its call to event-wait.
.PP
Which of the runable processes is to run next?
Associated with each process is a priority.
The priority of a system process is assigned by the code
issuing the wait on an event.
This is roughly equivalent to the response
that one would expect on such an event.
Disk events have high priority,
teletype events are low,
and time-of-day events are very low.
(From observation,
the difference in system process priorities
has little or no performance impact.)
All user-process priorities are lower than the
lowest system priority.
User-process priorities are assigned
by an algorithm based on the
recent ratio of the amount of compute time to real time consumed
by the process.
A process that has used a lot of
compute time in the last real-time
unit is assigned a low user priority.
Because interactive processes are characterized
by low ratios of compute to real time,
interactive response is maintained without any
special arrangements.
.PP
The scheduling algorithm simply picks
the process with the highest priority,
thus
picking all system processes first and
user processes second.
The compute-to-real-time ratio is updated
every second.
Thus,
all other things being equal,
looping user processes will be
scheduled round-robin with a
1-second quantum.
A high-priority process waking up will
preempt a running, low-priority process.
The scheduling algorithm has a very desirable
negative feedback character.
If a process uses its high priority
to hog the computer,
its priority will drop.
At the same time, if a low-priority
process is ignored for a long time,
its priority will rise.
.NH
I/O SYSTEM
.PP
The I/O system
is broken into two completely separate systems:
the block I/O system and the character I/O system.
In retrospect,
the names should have been ``structured I/O''
and ``unstructured I/O,'' respectively;
while the term ``block I/O'' has some meaning,
``character I/O'' is a complete misnomer.
.PP
Devices are characterized by a major device number,
a minor device number, and
a class (block or character).
For each class,
there is an array of entry points into the device drivers.
The major device number is used to index the array
when calling the code for a particular device driver.
The minor device number is passed to the
device driver as an argument.
The minor number has no significance other
than that attributed to it by the driver.
Usually,
the driver uses the minor number to access
one of several identical physical devices.
.PP
The use of the array of entry points
(configuration table)
as the only connection between the
system code and the device drivers is
very important.
Early versions of the system had a much
less formal connection with the drivers,
so that it was extremely hard to handcraft
differently configured systems.
Now it is possible to create new
device drivers in an average of a few hours.
The configuration table in most cases
is created automatically by a program
that reads the system's parts list.
.NH 2
Block I/O system
.PP
The model block I/O device consists
of randomly addressed, secondary
memory blocks of 512 bytes each.
The blocks are uniformly addressed
0, 1, .\|.\|. up to the size of the device.
The block device driver has the job of
emulating this model on a
physical device.
.PP
The block I/O devices are accessed
through a layer of buffering software.
The system maintains a list of buffers
(typically between 10 and 70)
each assigned a device name and
a device address.
This buffer pool constitutes a data cache
for the block devices.
On a read request,
the cache is searched for the desired block.
If the block is found,
the data are made available to the
requester without any physical I/O.
If the block is not in the cache,
the least recently used block in the cache is renamed,
the correct device driver is called to
fill up the renamed buffer, and then the
data are made available.
Write requests are handled in an analogous manner.
The correct buffer is found
and relabeled if necessary.
The write is performed simply by marking
the buffer as ``dirty.''
The physical I/O is then deferred until
the buffer is renamed.
.PP
The benefits in reduction of physical I/O
of this scheme are substantial,
especially considering the file system implementation.
There are,
however,
some drawbacks.
The asynchronous nature of the
algorithm makes error reporting
and meaningful user error handling
almost impossible.
The cavalier approach to I/O error
handling in the
.UX
system is partly due to the asynchronous
nature of the block I/O system.
A second problem is in the delayed writes.
If the system stops unexpectedly,
it is almost certain that there is a
lot of logically complete,
but physically incomplete,
I/O in the buffers.
There is a system primitive to
flush all outstanding I/O activity
from the buffers.
Periodic use of this primitive helps,
but does not solve, the problem.
Finally,
the associativity in the buffers
can alter the physical I/O sequence
from that of the logical I/O sequence.
This means that there are times
when data structures on disk are inconsistent,
even though the software is careful
to perform I/O in the correct order.
On non-random devices,
notably magnetic tape,
the inversions of writes can be disastrous.
The problem with magnetic tapes is ``cured'' by
allowing only one outstanding write request
per drive.
.NH 2
Character I/O system
.PP
The character I/O system consists of all
devices that do not fall into the block I/O model.
This includes the ``classical'' character devices
such as communications lines, paper tape, and
line printers.
It also includes magnetic tape and disks when
they are not used in a stereotyped way,
for example, 80-byte physical records on tape
and track-at-a-time disk copies.
In short,
the character I/O interface
means ``everything other than block.''
I/O requests from the user are sent to the
device driver essentially unaltered.
The implementation of these requests is, of course,
up to the device driver.
There are guidelines and conventions
to help the implementation of
certain types of device drivers.
.NH 3
Disk drivers
.PP
Disk drivers are implemented
with a queue of transaction records.
Each record holds a read/write flag,
a primary memory address,
a secondary memory address, and
a transfer byte count.
Swapping is accomplished by passing
such a record to the swapping device driver.
The block I/O interface is implemented by
passing such records with requests to
fill and empty system buffers.
The character I/O interface to the disk
drivers create a transaction record that
points directly into the user area.
The routine that creates this record also insures
that the user is not swapped during this
I/O transaction.
Thus by implementing the general disk driver,
it is possible to use the disk
as a block device,
a character device, and a swap device.
The only really disk-specific code in normal
disk drivers is the pre-sort of transactions to
minimize latency for a particular device, and
the actual issuing of the I/O request.
.NH 3
Character lists
.PP
Real character-oriented devices may
be implemented using the common
code to handle character lists.
A character list is a queue of characters.
One routine puts a character on a queue.
Another gets a character from a queue.
It is also possible to ask how many
characters are currently on a queue.
Storage for all queues in the system comes
from a single common pool.
Putting a character on a queue will allocate
space from the common pool and link the
character onto the data structure defining the queue.
Getting a character from a queue returns
the corresponding space to the pool.
.PP
A typical character-output device
(paper tape punch, for example)
is implemented by passing characters
from the user onto a character queue until
some maximum number of characters is on the queue.
The I/O is prodded to start as
soon as there is anything on the queue
and, once started,
it is sustained by hardware completion interrupts.
Each time there is a completion interrupt,
the driver gets the next character from the queue
and sends it to the hardware.
The number of characters on the queue is checked and,
as the count falls through some intermediate level,
an event (the queue address) is signaled.
The process that is passing characters from
the user to the queue can be waiting on the event, and
refill the queue to its maximum
when the event occurs.
.PP
A typical character input device
(for example, a paper tape reader)
is handled in a very similar manner.
.PP
Another class of character devices is the terminals.
A terminal is represented by three
character queues.
There are two input queues (raw and canonical)
and an output queue.
Characters going to the output of a terminal
are handled by common code exactly as described
above.
The main difference is that there is also code
to interpret the output stream as
.UC  ASCII
characters and to perform some translations,
e.g., escapes for deficient terminals.
Another common aspect of terminals is code
to insert real-time delay after certain control characters.
.PP
Input on terminals is a little different.
Characters are collected from the terminal and
placed on a raw input queue.
Some device-dependent code conversion and
escape interpretation is handled here.
When a line is complete in the raw queue,
an event is signaled.
The code catching this signal then copies a
line from the raw queue to a canonical queue
performing the character erase and line kill editing.
User read requests on terminals can be
directed at either the raw or canonical queues.
.NH 3
Other character devices
.PP
Finally,
there are devices that fit no general category.
These devices are set up as character I/O drivers.
An example is a driver that reads and writes
unmapped primary memory as an I/O device.
Some devices are too
fast to be treated a character at time,
but do not fit the disk I/O mold.
Examples are fast communications lines and
fast line printers.
These devices either have their own buffers
or ``borrow'' block I/O buffers for a while and
then give them back.
.NH
THE FILE SYSTEM
.PP
In the
.UX
system,
a file is a (one-dimensional) array of bytes.
No other structure of files is implied by the
system.
Files are attached anywhere
(and possibly multiply)
onto a hierarchy of directories.