OPERATING SYSTEM DESIGN
Part of the i-node cache for Fig. 4-34.
is presented, the cache returns the fact that
is i-node 26,
so the search can start there, eliminating four disk accesses.
A problem with caching paths is that the mapping between file name and i-
node number is not fixed for all time. Suppose that the file
moved from the system and its i-node reused for a different file owned by a dif-
ferent user. Later, the file
is created again, and this time it gets i-node
106. If nothing is done to prevent it, the cache entry will now be wrong and subse-
quent lookups will return the wrong i-node number. For this reason, when a file or
directory is deleted, its cache entry and (if it is a directory) all the entries below it
must be purged from the cache.
Disk blocks and path names are not the only items that are cacheable.
can be cached, too.
If pop-up threads are used to handle interrupts, each one of
them requires a stack and some additional machinery. These previously used
threads can also be cached, since refurbishing a used one is easier than creating a
new one from scratch (to avoid having to allocate memory).
Just about anything
that is hard to produce can be cached.
Cache entries are always correct.
A cache search may fail, but if it finds an
entry, that entry is guaranteed to be correct and can be used without further ado.
some systems, it is convenient to have a table of
These are suggestions
about the solution, but they are not guaranteed to be correct. The called must verify
the result itself.
A well-known example of hints are the URLs embedded on Web pages. Click-
ing on a link does not guarantee that the Web page pointed to is there.
In fact, the
page pointed to may have been removed 10 years ago. Thus the information on the
pointing page is really only a hint.
Hints are also used in connection with remote files. The information in the hint
tells something about the remote file, such as where it is located. However, the file
may have moved or been deleted since the hint was recorded, so a check is always
needed to see if it is correct.
12.4.6 Exploiting Locality
Processes and programs do not act at random. They exhibit a fair amount of lo-
cality in time and space, and this information can be exploited in various ways to
improve performance. One well-known example of spatial locality is the fact that
processes do not jump around at random within their address spaces. They tend to
use a relatively small number of pages during a given time interval. The pages that
a process is actively using can be noted as its working set, and the operating sys-
tem can make sure that when the process is allowed to run, its working set is in
memory, thus reducing the number of page faults.
The locality principle also holds for files. When a process has selected a partic-
ular working directory, it is likely that many of its future file references will be to
files in that directory.
By putting all the i-nodes and files for each directory close
together on the disk, performance improvements can be obtained. This principle is
what underlies the Berkeley Fast File System (McKusick et al., 1984).
Another area in which locality plays a role is in thread scheduling in multi-
processors. As we saw in Chap. 8, one way to schedule threads on a multiproces-
sor is to try to run each thread on the CPU it last used, in hopes that some of its
memory blocks will still be in the memory cache.
12.4.7 Optimize the Common Case
It is frequently a good idea to distinguish between the most common case and
the worst possible case and treat them differently. Often the code for the two is
quite different. It is important to make the common case fast. For the worst case, if
it occurs rarely, it is sufficient to make it correct.
As a first example, consider entering a critical region. Most of the time, the
entry will succeed, especially if processes do not spend a lot of time inside critical
regions. Windows 8 takes advantage of this expectation by providing a WinAPI
that atomically tests a flag in user mode (using
quivalent). If the test succeeds, the process just enters the critical region and no
kernel call is needed.
If the test fails, the library procedure does a
on a sema-
phore to block the process. Thus, in the normal case, no kernel call is needed. In
Chap. 2 we saw that futexes on Linux likewise optimize for the common case of no
As a second example, consider setting an alarm (using signals in UNIX).
alarm is currently pending, it is straightforward to make an entry and put it on the
timer queue. However, if an alarm is already pending, it has to be found and re-
moved from the timer queue. Since the
call does not specify whether there is
already an alarm set, the system has to assume worst case, that there is. However,
since most of the time there is no alarm pending, and since removing an existing
alarm is expensive, it is a good idea to distinguish these two cases.