3.t

早期freebsd实现

total	24.2 ms/call	19.2%
.TE
.ce
Table 4. Call times for \fInamei\fP in 4.2BSD.
.DE
.KE
.NH 3
Clock processing
.PP
Nearly 25% of the time spent in the kernel is spent in the clock
processing routines.
(This is a clear indication that to avoid sampling bias when profiling the
kernel with our tools
we need to drive them from an independent clock.)
These routines are responsible for implementing timeouts,
scheduling the processor,
maintaining kernel statistics,
and tending various hardware operations such as
draining the terminal input silos.
Only minimal work is done in the hardware clock interrupt
routine (at high priority), the rest is performed (at a lower priority)
in a software interrupt handler scheduled by the hardware interrupt
handler.
In the worst case, with a clock rate of 100 Hz
and with every hardware interrupt scheduling a software
interrupt, the processor must field 200 interrupts per second.
The overhead of simply trapping and returning
is 3% of the machine cycles,
figuring out that there is nothing to do
requires an additional 2%.
.NH 3
Terminal multiplexors
.PP
The terminal multiplexors supported by 4.2BSD have programmable receiver
silos that may be used in two ways.
With the silo disabled, each character received causes an interrupt
to the processor.
Enabling the receiver silo allows the silo to fill before
generating an interrupt, allowing multiple characters to be read
for each interrupt.
At low rates of input, received characters will not be processed
for some time unless the silo is emptied periodically.
The 4.2BSD kernel uses the input silos of each terminal multiplexor,
and empties each silo on each clock interrupt.
This allows high input rates without the cost of per-character interrupts
while assuring low latency.
However, as character input rates on most machines are usually
low (about 25 characters per second),
this can result in excessive overhead.
At the current clock rate of 100 Hz, a machine with 5 terminal multiplexors
configured makes 500 calls to the receiver interrupt routines per second.
In addition, to achieve acceptable input latency
for flow control, each clock interrupt must schedule
a software interrupt to run the silo draining routines.\**
.FS
\** It is not possible to check the input silos at
the time of the actual clock interrupt without modifying the terminal
line disciplines, as the input queues may not be in a consistent state \**.
.FE
\** This implies that the worst case estimate for clock processing
is the basic overhead for clock processing.
.NH 3
Process table management
.PP
In 4.2BSD there are numerous places in the kernel where a linear search
of the process table is performed: 
.IP \(bu 3
in \fIexit\fP to locate and wakeup a process's parent;
.IP \(bu 3
in \fIwait\fP when searching for \fB\s-2ZOMBIE\s+2\fP and
\fB\s-2STOPPED\s+2\fP processes;
.IP \(bu 3
in \fIfork\fP when allocating a new process table slot and
counting the number of processes already created by a user;
.IP \(bu 3
in \fInewproc\fP, to verify
that a process id assigned to a new process is not currently
in use;
.IP \(bu 3
in \fIkill\fP and \fIgsignal\fP to locate all processes to
which a signal should be delivered;
.IP \(bu 3
in \fIschedcpu\fP when adjusting the process priorities every
second; and
.IP \(bu 3
in \fIsched\fP when locating a process to swap out and/or swap
in.
.LP
These linear searches can incur significant overhead.  The rule
for calculating the size of the process table is:
.ce
nproc = 20 + 8 * maxusers
.sp
that means a 48 user system will have a 404 slot process table.
With the addition of network services in 4.2BSD, as many as a dozen
server processes may be maintained simply to await incoming requests.
These servers are normally created at boot time which causes them
to be allocated slots near the beginning of the process table.  This
means that process table searches under 4.2BSD are likely to take
significantly longer than under 4.1BSD.  System profiling shows
that as much as 20% of the time spent in the kernel on a loaded
system (a VAX-11/780) can be spent in \fIschedcpu\fP and, on average,
5-10% of the kernel time is spent in \fIschedcpu\fP.
The other searches of the proc table are similarly affected.
This shows the system can no longer tolerate using linear searches of
the process table.
.NH 3
File system buffer cache
.PP
The trace facilities described in section 2.3 were used
to gather statistics on the performance of the buffer cache.
We were interested in measuring the effectiveness of the
cache and the read-ahead policies.
With the file system block size in 4.2BSD four to
eight times that of a 4.1BSD file system, we were concerned
that large amounts of read-ahead might be performed without
being used.  Also, we were interested in seeing if the
rules used to size the buffer cache at boot time were severely
affecting the overall cache operation.
.PP
The tracing package was run over a three hour period during
a peak mid-afternoon period on a VAX 11/780 with four megabytes
of physical memory.
This resulted in a buffer cache containing 400 kilobytes of memory
spread among 50 to 200 buffers
(the actual number of buffers depends on the size mix of
disk blocks being read at any given time).
The pertinent configuration information is shown in Table 5.
.KF
.DS L
.TS
center box;
l l l l.
Controller	Drive	Device	File System
_
DEC MASSBUS	DEC RP06	hp0d	/usr
		hp0b	swap
Emulex SC780	Fujitsu Eagle	hp1a	/usr/spool/news
		hp1b	swap
		hp1e	/usr/src
		hp1d	/u0 (users)
	Fujitsu Eagle	hp2a	/tmp
		hp2b	swap
		hp2d	/u1 (users)
	Fujitsu Eagle	hp3a	/
.TE
.ce
Table 5. Active file systems during buffer cache tests.
.DE
.KE
.PP
During the test period the load average ranged from 2 to 13
with an average of 5.
The system had no idle time, 43% user time, and 57% system time.
The system averaged 90 interrupts per second 
(excluding the system clock interrupts),
220 system calls per second,
and 50 context switches per second (40 voluntary, 10 involuntary).
.PP
The active virtual memory (the sum of the address space sizes of
all jobs that have run in the previous twenty seconds)
over the period ranged from 2 to 6 megabytes with an average
of 3.5 megabytes.
There was no swapping, though the page daemon was inspecting
about 25 pages per second.
.PP
On average 250 requests to read disk blocks were initiated
per second.
These include read requests for file blocks made by user 
programs as well as requests initiated by the system.
System reads include requests for indexing information to determine
where a file's next data block resides,
file system layout maps to allocate new data blocks,
and requests for directory contents needed to do path name translations.
.PP
On average, an 85% cache hit rate was observed for read requests.
Thus only 37 disk reads were initiated per second.
In addition, 5 read-ahead requests were made each second
filling about 20% of the buffer pool.
Despite the policies to rapidly reuse read-ahead buffers
that remain unclaimed, more than 90% of the read-ahead
buffers were used.
.PP
These measurements showed that the buffer cache was working
effectively.  Independent tests have also showed that the size
of the buffer cache may be reduced significantly on memory-poor
system without severe effects;
we have not yet tested this hypothesis [Shannon83].
.NH 3
Network subsystem
.PP
The overhead associated with the 
network facilities found in 4.2BSD is often
difficult to gauge without profiling the system.
This is because most input processing is performed
in modules scheduled with software interrupts.
As a result, the system time spent performing protocol
processing is rarely attributed to the processes that
really receive the data.  Since the protocols supported
by 4.2BSD can involve significant overhead this was a serious
concern.  Results from a profiled kernel show an average
of 5% of the system time is spent
performing network input and timer processing in our environment
(a 3Mb/s Ethernet with most traffic using TCP).
This figure can vary significantly depending on
the network hardware used, the average message
size, and whether packet reassembly is required at the network
layer.  On one machine we profiled over a 17 hour
period (our gateway to the ARPANET)
206,000 input messages accounted for 2.4% of the system time,
while another 0.6% of the system time was spent performing
protocol timer processing.
This machine was configured with an ACC LH/DH IMP interface
and a DMA 3Mb/s Ethernet controller.
.PP
The performance of TCP over slower long-haul networks
was degraded substantially by two problems.
The first problem was a bug that prevented round-trip timing measurements
from being made, thus increasing retransmissions unnecessarily.
The second was a problem with the maximum segment size chosen by TCP,
that was well-tuned for Ethernet, but was poorly chosen for
the ARPANET, where it causes packet fragmentation.  (The maximum
segment size was actually negotiated upwards to a value that
resulted in excessive fragmentation.)
.PP
When benchmarked in Ethernet environments the main memory buffer management
of the network subsystem presented some performance anomalies.
The overhead of processing small ``mbufs'' severely affected throughput for a
substantial range of message sizes.
In spite of the fact that most system ustilities made use of the throughput
optimal 1024 byte size, user processes faced large degradations for some
arbitrary sizes. This was specially true for TCP/IP transmissions [Cabrera84,
Cabrera85].
.NH 3
Virtual memory subsystem
.PP
We ran a set of tests intended to exercise the virtual
memory system under both 4.1BSD and 4.2BSD.
The tests are described in Table 6.
The test programs dynamically allocated
a 7.3 Megabyte array (using \fIsbrk\fP\|(2)) then referenced
pages in the array either: sequentially, in a purely random
fashion, or such that the distance between
successive pages accessed was randomly selected from a Gaussian
distribution.  In the last case, successive runs were made with
increasing standard deviations.
.KF
.DS L
.TS
center box;
l | l.
Test	Description
_
seqpage	sequentially touch pages, 10 iterations
seqpage-v	as above, but first make \fIvadvise\fP\|(2) call
randpage	touch random page 30,000 times
randpage-v	as above, but first make \fIvadvise\fP call
gausspage.1	30,000 Gaussian accesses, standard deviation of 1
gausspage.10	as above, standard deviation of 10
gausspage.30	as above, standard deviation of 30
gausspage.40	as above, standard deviation of 40
gausspage.50	as above, standard deviation of 50
gausspage.60	as above, standard deviation of 60
gausspage.80	as above, standard deviation of 80
gausspage.inf	as above, standard deviation of 10,000
.TE
.ce
Table 6. Paging benchmark programs.
.DE
.KE
.PP
The results in Table 7 show how the additional
memory requirements
of 4.2BSD can generate more work for the paging system.
Under 4.1BSD,
the system used 0.5 of the 4.5 megabytes of physical memory
on the test machine;
under 4.2BSD it used nearly 1 megabyte of physical memory.\**
.FS
\** The 4.1BSD system used for testing was really a 4.1a 
system configured
with networking facilities and code to support
remote file access.  The
4.2BSD system also included the remote file access code.
Since both
systems would be larger than similarly configured ``vanilla''
4.1BSD or 4.2BSD system, we consider out conclusions to still be valid.
.FE
This resulted in more page faults and, hence, more system time.
To establish a common ground on which to compare the paging
routines of each system, we check instead the average page fault
service times for those test runs that had a statistically significant
number of random page faults.  These figures, shown in Table 8, show
no significant difference between the two systems in
the area of page fault servicing.  We currently have
no explanation for the results of the sequential
paging tests.
.KF
.DS L
.TS
center box;
l || c s || c s || c s || c s
l || c s || c s || c s || c s
l || c | c || c | c || c | c || c | c
l || n | n || n | n || n | n || n | n.
Test	Real	User	System	Page Faults
\^	_	_	_	_
\^	4.1	4.2	4.1	4.2	4.1	4.2	4.1	4.2
=
seqpage	959	1126	16.7	12.8	197.0	213.0	17132	17113
seqpage-v	579	812	3.8	5.3	216.0	237.7	8394	8351
randpage	571	569	6.7	7.6	64.0	77.2	8085	9776
randpage-v	572	562	6.1	7.3	62.2	77.5	8126	9852
gausspage.1	25	24	23.6	23.8	0.8	0.8	8	8
gausspage.10	26	26	22.7	23.0	3.2	3.6	2	2
gausspage.30	34	33	25.0	24.8	8.6	8.9	2	2
gausspage.40	42	81	23.9	25.0	11.5	13.6	3	260
gausspage.50	113	175	24.2	26.2	19.6	26.3	784	1851
gausspage.60	191	234	27.6	26.7	27.4	36.0	2067	3177
gausspage.80	312	329	28.0	27.9	41.5	52.0	3933	5105
gausspage.inf	619	621	82.9	85.6	68.3	81.5	8046	9650
.TE
.ce
Table 7. Paging benchmark results (all times in seconds).
.DE
.KE
.KF
.DS L
.TS
center box;
c || c s || c s
c || c s || c s
c || c | c || c | c
l || n | n || n | n.
Test	Page Faults	PFST
\^	_	_
\^	4.1	4.2	4.1	4.2
=
randpage	8085	9776	791	789
randpage-v	8126	9852	765	786
gausspage.inf	8046	9650	848	844
.TE
.ce
Table 8. Page fault service times (all times in microseconds).
.DE
.KE