\chapter[Introduction]{
\hfill\parbox{3.4in}{%
\normalsize\rm
\begin{quotation}
{\it
\noindent
\llap{``}And every single block\\
Looked like every single block\\
Looked like every single block\\
Looked like every single block\\
But she kept driving\\
'Cause everyone else kept driving\\
And cause gridlock is evil\\
And not knowing your way is evil''\\
}
\null\quad\quad\quad---Dan Bern, \emph{Wasteland}
\end{quotation}
}\newline
Introduction}
\label{chap:introduction}

It's been a long time since computer processors have been the bottleneck for most
uses of computer systems.  The data flow in today's computation goes through a
hierarchy of memories and mediums whose speeds vary by orders of magnitude.
To browse a web page, for example, the data is first requested by the client
from the web server.  The server will send a request to the database server
to fetch the data.  The database server finds and loads data from physical
storage and serves it back to the web server, which will send it back to the
client.  When in the client side, the web page will go through the process of
text layout and rendering, requiring fonts to be loaded from the local
storage, and finally the resulting image is pushed to the display.  Caches
have been used in a variety of layers to impedance-match these various levels.
In the simplest case, a typical two-level memory architecture consists of a
small but fast cache and a relatively large but slower memory.  Examples
include:
the cache in the CPU versus the main memory; the page cache (the main
memory as the cache, versus the hard disk as the external memory); the web
browser cache versus the web resources; the web server's cache versus all
the documents it serves from local files or network resources like databases.

For caches to be effective they should have a high hit ratio.  The cache
performance is mostly determined by the cache size, the cache evacuation
algorithm, and the workload.  In many caching scenarios, the external memory
is unused for long periods of time.  To further improve cache performance,
many computer systems try to predict which chunk of data will be needed next
and fetch it into the cache (if it is not already in cache) before it is
requested.  This method is called \emph{prefetching}.


\section{Desktop Computers}

This thesis focuses on desktop computers.  Desktop computers are commonly used
in homes and small offices.  They are mainly used for web browsing,
email exchange, instant messaging, reading and writing letters, listening to
music, and watching movies.  For the purposes of our analysis, desktop
computers typically have one or two regular users---unlike servers.  While
many desktop computers are often not turned off for long periods of time (days
and weeks), statistically speaking they spend most of their time idling.  This
is mostly because of their single-user-at-a-time nature and having few users
in total, which means, even at times that the computer is being used by a user,
the processor is not busy processing for most of the time.  In fact, assuming
the system is not short in main memory, the majority of times that the system
limits are pushed are when new applications are started.  Application start-up
consumes a lot of processing time and generates lots of I/O traffic from the
external storage that is the local hard disk.

Hard disks are the main means of storage on desktop computers (as opposed to
network storage).  Because of their mechanical nature, hard disks are a few
orders of magnitude slower than the main memory.  The ones used in desktop
systems have a transfer rate of 20 to 50 megabytes per second, have disks
rotating at 5400 rounds per minute, and a
\emph{seek-time} of 10 to 20 milliseconds \cite{hubert05faster}.  Seek time is
the time it takes for the head to move to the target track.
The overhead associated with a reading an arbitrary location on the disk
involves the seek time and the rotational latency for the head to be
positioned on top of the target sector on the track.  We call this time
\emph{disk access time}.
It is this large disk access time that disk I/O schedulers try to minimize by
sorting and merging disk access requests in batches, such that the disk head
moves in an \emph{elevator-like} path (going to one side and then the other in
a loop) instead of jumping around randomly.  In the next section we identify
disk access time as a bottle-neck of application start-up time, and in the
rest of the thesis we will try to come up with a scheme to avoid delays caused
by disk access time during application start-up.


\section{Startup-Time Problem}

When hard disks in their current shape and scale found their way into
micro-computers in the eighties they were not particularly a bottleneck of the
system's operation.  However, during the past decades various measures have
had growing rates of varying scales.  In particular, in the personal computer
market, processor power, size of main memory, hard disk capacities have been
growing at least 40\% a year on average: doubling every two years
\cite{papathan05aggressive}.
However, disk throughput and access time have been improving at most at a 10\%
a year rate, being limited by the mechanically moving parts of the drive.
This has caused hard disks to have a more important impact on overall
system performance.
% cite mooreslaw and the harddisk law?

With the computer's processing power and memory sizes growing fast, software
applications have also grown in processor and memory size requirements at a high
rate.  Where an application typically was a few tens of files that could fit
on a 1.4 megabyte floppy disk in the 1980's, there are applications and
games available in 2006 that fill a CD or DVD, broken into thousands of
files.

The bigger the software applications become, the more they are broken into
modular and partially standalone pieces, for sharing and for manageability
reasons.  Shared libraries are one way that this is achieved.  Shared
libraries (or shared objects) were introduced as a way to decrease memory and
disk requirements by sharing the code for common functionality between
applications and keeping only one copy of such code in main memory and on the
external storage.  A side effect of using shared libraries is that not every
application uses all the code in all the shared libraries that it uses (by
linking to them).  Another elegant idea in the history of operating systems has
been load-on-demand: instead of reading all the needed files in memory before
running the application, they are mapped into the address space and the
program starts running.  The kernel then encounters a page fault when data is
missing, leading to disk read operations to fill the memory with the required
data \cite{hubert05faster}.

To understand what we call \emph{the startup-time problem} now, we just need
to summarize the logical consequences of the above changes and compare their
rates:
\begin{itemize}
\item Faster processors and bigger hard disk and main memory sizes result in
more and larger applications,
\item More/larger applications result in more files in the application
distribution, and consequently, more files to load at application start-up
time,
\item Use of shared objects results in more files to be loaded at application
start-up time,
\item More files loaded cause more disk access times to wait as the hard disk head has
to move around the hard disk to find various files to read,
\item Use of load-on-demand causes more disk access times to be experienced.  As
elegant as the load-on-demand idea is, it can lead to unpredictable seek
behaviors, like occasional hits going backwards on disk, and disks perform
very poorly in those situations \cite{hubert05faster}.
\end{itemize}
Given that disk access time has been the slowest of all the factors to improve,
it is not surprising that software start-up time (and system boot time
similarly) has been slowing down over the years no matter how fast the
hardware running it has been getting faster \cite{ousterhout90faster}.
The end result of this all is that in 2006, on a decent desktop computer
it takes:
\begin{itemize}
\item from 30 seconds to 2 minutes to boot, depending on configurations and
services to start up,
\item 30 seconds to log into the desktop environment before the system gets
back to a steady state,
\item 15 seconds to start a word processor application
\item 11 seconds to start a web browser
\end{itemize}
For hardware and software configurations, see \autoref{chap:experimental}.


\section{Prefetching}

Prefetching has been studied in depth across all areas of the systems
literature as a way to improve performance.  Hardware prefetching is performed
in all modern processors to load instructions ahead of time into the cache.
Database and virtual memory are two other systems in which prefetching is widely
studied \cite{curewitz93datacompression}.  With the wide-spread use of
networks and the Internet in recent years, Web prefetching and remote file
system prefetching have gained in interest too.

When reading data from the hard disk, most modern kernels detect sequential
read access pattern and prefetch data ahead, saving time that could
have been wasted in disk access time when the read operation for the next chunk comes
in.  In fact, designing the readahead algorithm has become one of the crucial 
aspects of file-system performance \cite{pai04linux}.  There has been a lot of
work to go beyond sequential readahead. The goal is to reduce hitting the
lengthy disk access time.  Prefetching and caching strategies are either heuristic or
hinted \cite{orourke01parallelism}.  There has been work on both areas, and
even work that falls in between, heuristically adding hints to applications.
Hinted approaches only affect programs that are modified to generate prefetch
requests and so are mostly viable in server-side applications that are
optimized for the highest possible performance.  In the rest of this thesis we
mainly deal with heuristic approaches to prefetching.

In the absence of hints and sophisticated heuristics, several operating systems
targeting desktop computers have taken na\"ive approaches to prefetching and
reducing boot and start-up times.  We review some of these systems in the rest
of this section.


\subsection{Windows XP}\label{subsec:winxp}

Windows XP claims to be a self-tuning operating system.  It essentially
records file accesses during boot and application start-up times and uses this
information to prefetch those files in subsequent events and to lay those
files out near each other on the disk, and towards the more dense outer edge
of the disk \cite{winxp:benchmark}.

It has been part of the design goals for Windows XP to boot to a usable state
in a total of 30 seconds, measured from the time the power switch is pressed
to being able to start a program from a desktop shortcut.  To achieve this,
Windows XP also \emph{cheats} by delaying various initializations and service
start-ups to after the login \cite{winxp:fastboot}.  This gives the impression
of a faster boot process but may also make the first few seconds after login
almost unusable due to heavy I/O traffic.

\subsection{Fedora Readahead}\label{subsec:fedora-readahead}

The Fedora Core\footnote{A GNU/Linux-based operating system} 5 system contains
a package called \texttt{readahead} that contains a static list of about 2500
files that are read ahead during the boot process, in two stages.  This is
supposed to make for a smoother login experience as many files needed during
the login on a system with default settings will be in memory already.  We
analyze the performance of this system more in \autoref{chap:discussion}.

\subsection{SuSE Preload}\label{subsec:suse-preload}

Similar to Fedora's \texttt{readahead} package, SuSE\footnote{Another
GNU/Linux-based operating system} systems have a package called
\texttt{preload}\footnote{Incidentally, we did not know of this other system
called \emph{preload} before naming ours.} that reads files and directory entries
into memory, from static lists pre-generated by tracing system calls during
the system boot in the standard configuration.

\subsection{GNOME Display Manager}\label{subsec:gnome-display-manager}

A display manager is the piece of software that manages the graphical login
screen.  The GNOME Display Manager (\texttt{gdm}) can be configured to call a
\emph{prefetching program} when the initial login screen is displayed.  This
period of time is particularly good for prefetching as the system is idle
otherwise.  Solaris systems use this functionality of \texttt{gdm} to prefetch
a list of about thirty shared library files.  It is documented as ``preloading
these libraries improves first-time login performance for the GNOME desktop.''
\cite{gdmprefetchlist}


\section{Contributions}

We introduce a new approach to prefetching from hard disk into main memory on
desktop systems: to predict what applications a user may run soon based on her
currently-running applications.  This is the first work to perform prefetching at this
level as far as we know.
We further develop a probabilistic model of the problem based on
continuous-time Markov chains, and deduce prediction algorithms that are used
to implement a user-space prefetcher.

We implemented this scheme as a user-space daemon monitoring applications and
predicting and prefetching online on Linux 2.6 systems, and we measured its
performance on various tasks.

While our experimental results look promising, we question the merits
of prefetching on desktop systems, and recommend alternatives to prefetching
for desktop systems seeking to improve boot and application start-up times.


\section{Organization of Thesis}

This thesis is organized as follows.  \autoref{chap:related} reviews related
work.  \autoref{chap:fundamentals} discusses the terminology we use and our
system model.  \autoref{chap:algorithms} provides the algorithms for
implementing the proposed model. \autoref{chap:implementation} presents the
implementation of the system.  \autoref{chap:experimental} presents our
experimental results.  \autoref{chap:discussion} discusses the solution and
the experimental results achieved, and \autoref{chap:conclusions} concludes
the thesis.