\documentstyle[twocolumn,times]{article} \columnsep=0.33in \textwidth=6.5in \textheight=9.00in \evensidemargin=0in \oddsidemargin=0in \topmargin=-0.75in \topskip=0pt \baselineskip=12pt \parskip=0pt \parindent=0em \pagestyle{empty} \begin{document} \setcounter{page}{0} dsfsdafsdaf \newpage sdfsdfsdf \bibliographystyle{plain} \renewcommand{\thefootnote}{*} \begin{table*}[t] \begin{center} \font\wrrbftw=Times-Bold at 12pt {\wrrbftw Disk Performance Enhancement through \\ Markov-based Cylinder Remapping \footnotemark}\\ \quad \\ \begin{tabular}{rl} \multicolumn{2}{c}{Robert Geist\ \ \ \ \ \ \ \ }\\ Darrell Suggs & Robert Reynolds\\ Shardul Divatia & Fred Harris\\ Evan Foster & Priyadarshan Kolte\\ \end{tabular} \quad\\ \quad\\ Department of Computer Science\\ Clemson University\\ Clemson, SC 29634-1906\\ phone: 803-656-2258\\ email: rmg@cs.clemson.edu \end{center} \end{table*} \newpage %\footnotetext{This work was supported in part %by an equipment donation from Data General Corp.} \renewcommand{\thefootnote}{TM} \renewcommand{\section}[1]{\font\wrrbf=Times-Bold\topsep=0mm\parskip=0pt\begin{flushleft} \wrrbf #1\end{flushleft}} \section{Abstract} A scheme for disk subsystem performance enhancement that is based on (virtual) cylinder remapping is proposed. A natural workload on a real system is measured, and statistical tests are used to determine that disk accesses are appropriately modeled by a first order Markov chain. Maximum likelihood estimators of the Markov model parameters are used in a simulated annealing algorithm to find a permutation of the (virtual) cylinders that substantially reduces expected seek distance. This permutation is then installed in a real system and tested under a workload that is stochastically generated from the Markov model. The proposed scheme is seen to offer a 25.6\% reduction in mean service time when compared to the original (unmapped) cylinder arrangement. \parskip=12pt \parindent=0pt {\bf keywords:} Disk subsystem, Cylinder mapping, Markov models, Simulated annealing, UNIX\footnotemark, %\footnote{UNIX is a trademark of AT\&T.}, DG/UX\footnotemark %\footnote{DG/UX is a trademark of Data General Corp.} \baselineskip=12pt \parindent=3em \renewcommand{\section}[1]{\addtocounter{section}{1}\topsep=12pt\parskip=0pt\quad\begin{flushleft}\arabic{section}. \wrrbf #1\end{flushleft}} \section{INTRODUCTION} Although CPU speeds of workstations and minicomputers have increased by at least an order of magnitude in the last five years, most of us in the university environment have not witnessed an accompanying order of magnitude increase in overall computer system performance. The reality of using heavily loaded systems is that we compute at disk speed, not CPU speed, and the performance of disk hardware has \vspace*{0.75in} \begin{minipage}[b]{3.08888in} \renewcommand{\thefootnote}{*} \footnotetext{\footnotemark This work was supported in part by an equipment donation from Data General Corp.} \renewcommand{\thefootnote}{TM} \footnotetext{\footnotemark UNIX is a trademark of AT\&T.} \footnotetext{\footnotemark DG/UX is a trademark of Data General Corp.} \end{minipage} \pagebreak[4] %\textheight=9.0in \noindent simply not kept pace. As a result, the possibility of performance-enhancing modifications to disk device drivers and file system structures continues to receive substantial attention from operating system designers. We have previously investigated {\it disk scheduling algorithms} \cite{gd:acodsa,grp:dsisv,wrr:sbds,wrrandbeede,dgs:dswfk,suggs:ms} which are used to decide which of a queue of pending disk requests should be served next. The conclusions of those studies can be briefly summarized as follows: \begin{itemize} \item On heavily loaded systems, we can expect good scheduling to reduce average request waiting time by as much as 50\% from that experienced under first-come, first-served scheduling. \item The best overall performance appears to be provided by the WSCAN algorithm \cite{suggs:ms}: \begin{enumerate} \item Maintain a preferred read/write head direction, in (towards hub) or out (towards edge). \item Serve next the physically closest request in the preferred direction, unless a request falls in a very small ``window'' behind the head, in the opposite direction. In this case, serve the request in the window, but do not change the window location or the preferred direction. \item If no requests exist in the preferred direction, change the preferred direction. \end{enumerate} \end{itemize} The WSCAN algorithm has been independently tested by Data General, and will be incorporated in a forthcoming release of their DG/UX operating system. Another approach to disk subsystem performance improvement has been suggested recently by Vongsathorn and Carson \cite{vong}. They conjecture that seek times could be substantially reduced if the arrangement of information on the disk cylinders ``matched'' the natural arrangement of requests generated by the workload. They observe that on a disk with $N$ cylinders the sequence of cylinders visited can be approximately modeled by a discrete-time Markov chain with $N$ states. Using their notation, we let $\pi_i$ denote the steady-state probability that the read/write head is on cylinder $i$, and let $\rho_{ij}$ denote the conditional probability that the head moves next to cylinder $j$, given that it is on cylinder $i$. Minimizing expected seek distance then amounts to finding that permutation, $P$, of \{1,2,...,$N$\} that minimizes \begin{equation} E[P] = \sum_{i=1}^N \sum_{j=1}^N |P(i) - P(j)| \pi_i \rho_{ij}, \label{eqn:goal1} \end{equation} and then remapping the cylinders according to that permutation. Note that any such permutation remapping can be accomplished by a sequence of simple pairwise exchanges of cylinder contents. Nevertheless, the number of permutations to be considered in minimizing (\ref{eqn:goal1}) is $N$!, where a reasonable value of $N$ is 2000. Since 2000! $\approx 10^{5736}$, which dwarfs the number of atoms in the universe, the problem of finding this optimum permutation is clearly intractable. Vongsathorn and Carson resort to an approximation: they assume independent cylinder access, i.e. $\rho_{ij} = \pi_j$, and therefore they need only minimize \begin{equation} E[P|independent] = \sum_{i=1}^N \sum_{j=1}^N |P(i) - P(j)| \pi_i \pi_j. \label{eqn:goal2} \end{equation} From \cite{knuth} the permutation $P$ that minimizes (\ref{eqn:goal2}) is the so-called {\it pipe organ arrangement} in which the most frequently accessed cylinder is in the middle, the next two most frequently accessed cylinders are adjacent to the first and on opposite sides of it, and so on. They proceed to implement a fault-tolerant cylinder remapping scheme, based on pairwise cylinder exchange, which provides this pipe organ arrangement. The simplifying assumption of independent cylinder access is a point of contention among system designers. The designers of Data General's DG/UX operating system argue that cylinder sequence dependencies are extremely important \cite{kelly}. They find that, in typical user workloads, access to a file index node (inode) is often immediately followed by access to the blocks of the file itself. For this reason they partition file systems into Disk Allocation Regions (DAR's) which contain both inodes and the associated contiguous file blocks. This design might be regarded as a heuristic attempt to minimize (\ref{eqn:goal1}). The validity of the independent cylinder access assumption is clearly workload and architecture dependent, but, for any particular system, it is still best examined in two phases: \begin{enumerate} \item Do we have real data from our system that allows us to reject the independence assumption in favor of a specific Markov model? \item Does 1 matter, i.e., even if the answer is yes, can we improve significantly upon the pipe organ arrangement? \end{enumerate} In this paper we present a case study of a real workload on a real system for which the answer to both questions is a qualified ``yes.'' We describe a workload measurement and testing technique that allows us to determine when to reject independence in favor of a Markov model, and we describe an approach to the optimization problem, (\ref{eqn:goal1}), that allows significant performance gains. The remainder of the paper is organized as follows. In section 2 we describe the experimental platform, the workload, and the measurement facility. In section 3 we describe the Markov model derived from our measurement, the test for model order, and the results of its application to our measured workload. In section 4 we describe a technique for finding cylinder permutations, $P$, that ``match'' the measured workload in the sense of minimizing expected seek distance, (\ref{eqn:goal1}). Section 5 contains a description of the installation of our cylinder remapping facility and test results from its use in a real system. It also enumerates some implementation issues that must be addressed in a further study. Conclusions follow in section 6. \section{WORKLOAD} Our experiment was performed on a Data General AViiON\footnote{AViiON is a trademark of Data General Corp.} AV 4000 running the DG/UX 4.30 operating system, a symmetric multiprocessor implementation of UNIX. The test disk was a 179 Mbyte SCSI drive with an Adaptec AIC-6250 Protocol Chip as bus interface. This architecture presented two obstacles to remapping physical cylinders. First, SCSI drives attempt to hide physical cylinder layout from the operating system, and so extensive testing was necessary to determine the layout. Second, the extensive testing revealed a most inconvenient physical structure: on this 179 Mbyte disk, the number of sectors per track is variable, ranging from 31 to 53. With 5 surfaces, the cylinders then vary in size from 155 to 265 sectors. Since working directly with this unusual and inconvenient physical structure would have restricted portability and added to implementation overhead, we chose instead to focus on {\it virtual cylinders}. A virtual cylinder is a group of consecutive physical sectors which may cross physical cylinder boundaries. The size (in sectors) of a virtual cylinder was dictated by several considerations. It had to be small enough to capture real cylinder request dependencies, but not so small that the total number of virtual cylinders, which is the number of states in our workload model, would render the model unmanageable. Further, as discussed in section 5, implementation is facilitated by choosing a virtual cylinder size that is an integer multiple of the operating system's default transfer size. In DG/UX 4.30 this is 16 sectors (8 Kbytes). Thus we chose 160 sectors (32 sectors $\times$ 5 surfaces) as the virtual cylinder size, which gave us 2,181 virtual cylinders. The AViiON 4000 and its 179 Mbyte disk are reserved for special projects, such as this one, and thus its natural workload is not representative of the general programming mix we wished to study. Fortunately, this system is attached to (boots from) a Data General AViiON AV 200 with a 330 Mbyte SCSI disk drive which is in general use by students and faculty, and thus does support the desired workload mix. We chose to monitor the latter system and adapt its measured workload to the former. We built a new DG/UX kernel for the AV 200 which contained a global memory region to record disk requests. For each request we recorded the sector number, the time the request entered the WSCAN queue, and the time the request left the WSCAN queue to enter service. To extract the recorded information from kernel memory, we included a new system call that simply read the kernel variables and wrote them to user address space. An independent user process periodically exercised the system call and wrote results to a remote file via NFS in order to minimize interference with the natural load on the 330 Mbyte disk. We monitored the system for a period of three days, which yielded a stream of 163,681 disk accesses. Since WSCAN was in effect, and not FCFS, the stream leaving the queue differed from the stream arriving to the queue. The effects of the scheduling algorithm cannot be ignored, and thus it is the departure stream that is of interest. Finally, we partitioned the sectors of the 330 Mbyte drive to yield the desired 2,181 virtual cylinders, and then re-expressed the departure stream in terms of these virtual cylinders. This stream of virtual cylinder requests was then used to produce a Markov model representation of the workload that could be transferred to the test system. \section{A MARKOV MODEL} A {\it first-order} Markov chain, such as described in section 1, is one in which next state probabilities depend only upon the current state. If next state probabilities depend upon the last 2, 3, or, more generally, $n$ states visited, then the Markov chain is said to be of {\it order} 2, 3, or $n$. In this same terminology, an independent access model is an order 0 Markov chain, since next state probabilities do not depend upon any states visited. We assume that the measured sequence of virtual cylinders visited represents a Markov chain of some order, perhaps order 0. Following Haring \cite{harin}, we can test for this order. Let $vc(t) \in \{1,2,...,2181\}$ denote the virtual cylinder accessed on the $t^{th}$ request, where the total number of requests is $T$ = 163,681. Let \begin{eqnarray*} N_j(t) & = & \left\{ \begin{array}{ll} 1 & \mbox{if $vc(t)$=$j$}\\ 0 & \mbox{otherwise} \end{array} \right.\\ N_{ij}(t) & = & \left\{ \begin{array}{ll} 1 & \mbox{if $vc(t)$=$j$ and $vc(t-1)$=$i$}\\ 0 & \mbox{otherwise} \end{array} \right.\\ \end{eqnarray*} Maximum likelihood estimators of $\pi_j$ and $\rho_{ij}$ are then $$ \hat{\pi}_{j} = \sum_{t=1}^T N_j(t)/T $$ and $$ \hat{\rho}_{ij} = \sum_{t=2}^T N_{ij}(t)/\sum_{t=2}^T N_{i}(t-1) $$ We first tested the hypothesis $$ H_0: \rho_{ij} = \pi_j \quad \forall i,j \mbox{\quad (Markov chain is order 0)} $$ versus the alternative $$ H_1:\rho_{ij} \neq \pi_j \quad \forall i,j \mbox{\quad (Markov chain has order $\ge$ 1)} $$ From \cite{harin}, \[ \chi_0^2 = \sum_{i=1}^N \sum_{j=1}^N \sum_{t=2}^T N_{i}(t-1) \ [ \hat{\rho}_{i j} - \hat{\pi}_{j} ]^2 \ / \ \hat{\pi}_{j} \] has $\chi^2$ limiting distribution with $N(N-1)$ degrees of freedom. For such large degrees of freedom, we can regard $\sqrt{2 \chi_0^2} - \sqrt{2N(N-1) - 1}$ as a sample from a standard normal \cite{trive:book}. Our measured virtual cylinder stream yielded $\chi_0^2$ = 41.49 $\times 10^6$, which allowed us to reject $H_0$ at significance level less than 0.001. We tested for higher order using a similar procedure. Let $\gamma_{ijk}$ denote the conditional probability that the read/write head moves next to cylinder $k$, given that it is now on cylinder $j$ and arrived at cylinder $j$ from cylinder $i$. If \begin{eqnarray*} N_{ijk}(t) & = & \left\{ \begin{array}{ll} 1 & \mbox{if $vc(t)$=$k$, $vc(t-1)$=$j$,}\\ & \mbox{\ \ \ \ and $vc(t-2)$=$i$}\\ 0 & \mbox{otherwise} \end{array} \right.\\ \end{eqnarray*} then a maximum likelihood estimator of $\gamma_{ijk}$ is \[ \hat{\gamma}_{ijk} = \sum_{t=3}^T N_{ijk}(t)/\sum_{t=3}^T N_{ij}(t-1) \] and we can test $$ H_0: \gamma_{ijk} = \rho_{jk} \quad \forall i,j,k \mbox{\quad (Markov chain is order 1)} $$ versus the alternative $$ H_1:\gamma_{ijk} \neq \rho_{jk} \quad \forall i,j,k \mbox{\quad (order $\ge$ 2)} $$ by using \[ \chi_0^2 = \sum_{i=1}^N \sum_{j=1}^N \sum_{k=1}^N \sum_{t=3}^T N_{ij}(t-1) \ [ \hat{\gamma}_{ijk} - \hat{\rho}_{jk} ]^2 /\hat{\rho}_{jk} \] which has $\chi^2$ limiting distribution with $N(N-1)^2$ degrees of freedom. In this case we were unable to reject $H_0$ (even at the 0.1 significance level), and so we conclude that a first order Markov chain best describes the measured workload. Nevertheless, we must qualify this conclusion with the observation that $T$ = 163,681 may be insufficient for this second test, and additional measurement may be useful. \section{OPTIMIZATION} Simulated annealing \cite{Kirk:Osaqs} is a probabilistic algorithm that has been applied to many optimization problems in which the set of feasible solutions is so large that an exhaustive search for the optimum solution is out of the question. The optimal placement of 2,181 virtual cylinders on the disk drive yields a feasible set of 2181! $\approx 10^{6336}$ possible permutations, and so the problem would appear to be a good candidate for this approach. Although simulated annealing does not necessarily provide the optimum solution, it usually does provide a good solution in reasonable time. Input for this problem consisted of the measured estimators, $\hat{\pi_i}$ and $\hat{\rho_{ij}}$. For any permutation, $P$, the {\it energy} of the permutation was defined to be the estimated average seek distance, \begin{equation} energy[P] = \sum_{i=1}^N \sum_{j=1}^N |P(i) - P(j)| \hat{\pi_i} \hat{\rho_{ij}}, \label{eqn:goal3} \end{equation} The simulated annealing algorithm can then be described as a non-deterministic walk on an energy surface that is changing shape under the control of a ``cooling'' schedule. Specifically, {\small \baselineskip=12pt \begin{tabbing} xxxxx\=yyyyy\=zzzzz\= \kill \#define EQUILIBRIUM \\ \>\>(accepts$\ge$2000 AND rejects$\ge$5000) \\ \>\>\>OR (accepts+rejects $>$ 50000)\\ \#define FROZEN ((temperature $<$ 0.5) OR \\ \>\>((temperature $<$ 1.0) AND (accepts==0))) \\ \quad\\ while(not(FROZEN))\{\\ \>accepts = rejects = 0;\\ \>old\_energy = energy();\\ \>while(not(EQUILIBRIUM))\{ \\ \>\>cylinder1 = choose\_random\_cylinder();\\ \>\>cylinder2 = choose\_random\_cylinder();\\ \>\>swap\_cylinders(cylinder1,cylinder2);\\ \>\>new\_energy = energy();\\ \>\>$\Delta E$ = new\_energy - old\_energy;\\ \>\>if(rand(0,1) $< e^{min\{0.0,-\Delta E/\mbox{temperature}\}}$)\{ \\ \>\>\>accepts++;\\ \>\>\>old\_energy = new\_energy;\\ \>\>\>\} \\ \>\>else \{\\ \>\>\>/* put them back */\\ \>\>\>swap\_cylinders(cylinder1,cylinder2); \\ \>\>\>rejects++; \\ \>\>\>\} \\ \>\>\}\\ \>temperature = temperature*0.8;\\ \>\}\\ \end{tabbing} } \baselineskip=12pt The energy of the identity permutation, which describes the original cylinder arrangement, was 390.647935. Upon completion, the simulated annealing algorithm had arrived at a permutation with an energy of 32.3543347, and this permutation was used in the subsequent system test. \section{INSTALLATION AND TESTING} The installation of virtual cylinder remapping in an operating system requires implementation of both {\it relocation} and {\it remapping}. First, the virtual cylinders must be physically relocated on disk to match a desired permutation, and the operating system must be made aware that the permutation is in effect. Subsequently, the operating system must remap each disk sector request so that a request falling into virtual cylinder $i$ is translated into a request for virtual cylinder $P(i)$, where the desired information actually resides. To accomplish remapping, we installed in the kernel address space an array to hold the translation map, and we added a system call, {\it set\_disk\_map()}, to initialize the array so that $disk\_map[i] = P(i)$. We also added a system call, {\it disk\_map()}, to enable or disable remapping. When mapping is enabled, all requests for disk access are translated via the mapping array. To verify that mapping occurred correctly, we wrote unique identifiers at the beginning of each virtual cylinder, installed and activated a fictitious map, and read from each of the virtual cylinders. To measure the effects of remapping, we instrumented the disk request subsystem to record, for each disk access, the requested sector number, the time the request entered the queue, the time the request left the queue to begin service, and the time at which service was completed. Using this data, we computed mean service time under each of three disk arrangements: the initial unmapped configuration, the pipe organ arrangement, and the permutation produced by the annealing algorithm discussed in the previous section. For each test, we used the same request stream of 250,000 disk accesses, which was stochastically generated from the first order Markov model workload description. The measured mean service times for each map configuration are shown in Table \ref{table:results}. We see that the pipe organ configuration provided a significant improvement over the original unmapped arrangement. However, when first order dependencies are taken into account, we see that an additional improvement can be realized. These results indicate that, if the sequence of disk requests can be correctly characterized by a first order Markov model, as the tests of section 3 would suggest, then effective disk rearrangement can provide a noticeable performance improvement over both the unmapped disk and a rearrangement that assumes independent accesses. \begin{table} \centering \begin{tabular}{|lcc|} \hline \quad & Mean serv. time (ms) & Improvement \\ \hline Unmapped & 24.423321 & --- \\ Pipe organ & 19.217960 & 21.31\% \\ Markov & 18.158880 & 25.65\% \\ \hline \end{tabular} \caption{\label{table:results}Mean service times} \end{table} These results were obtained from a fairly simple prototype implementation of virtual cylinder remapping. A production implementation would require that we handle many details not addressed in the prototype. At present the operating system stores the translation map only in kernel memory, so that a system crash causes loss of ability to address the disk correctly. A production system would have to store the map on disk as well as in memory, so that it could recover from a crash. Furthermore, the map must be stored in a disk area which is not remapped, since otherwise the crash recovery process would face the recursive problem of needing the disk map to find the disk map. Fortunately, there is usually an area of the disk reserved for just such information (e.g. bad block maps). Crash recovery is not the only problem we face; even normal machine boot-up presents some challenges. Booting often proceeds in two stages. First, control is transferred to simple loader code stored in hardware PROM. This code reads a second-stage loader from a fixed location on disk, and transfers control to it. The second-stage loader contains enough file system information to find a file containing the operating system kernel, which it loads and executes. This boot process has two major implications for cylinder remapping. First, since we cannot change the boot PROM, the second stage bootstrap must remain in a fixed location, and hence cannot be remapped. Second, the second stage bootstrap must be modified to perform remapping so that the kernel file can be located. This means that the bootstrap code becomes somewhat larger and that we must implement remapping in two places: the bootstrap and the kernel. The operating system transfer size and protocol are also a concern. Requests arrive to the SCSI controller in the form: (starting sector, number of sectors to transfer). Care must be taken that such requests do not extend across virtual cylinder boundaries, since contiguous sectors may no longer be contiguous after remapping. In response to a user request for sector $n$, the DG/UX transfer protocol requests from the SCSI drive 16 consecutive sectors starting at sector $16\times \lfloor n/16 \rfloor$. Thus the choice of 160-sector virtual cylinders precludes the spanning problem. This was not an issue during the tests we have described, since driving the system from the Markov workload model allowed us to bypass the protocol and access the disk directly through the raw interface. The final major detail to be addressed is the time of the actual rearrangement of disk data. This rearrangement can be performed either online while the machine is in normal operation, or offline. While taking the machine out of normal operation makes rearrangement easy, machine availability is decreased. Online rearrangement keeps availability high but requires more effort to ensure disk consistency at all times. In either case, two major criteria must be satisfied: the translation map must be valid at all times during normal operation and rearrangement, and if there is a machine failure during the rearrangement process, the map must be valid after recovery and the rearrangement process must continue. \section{CONCLUSIONS} We have suggested a scheme for disk subsystem performance enhancement that is based on (virtual) cylinder remapping. We measured workload on a real UNIX system and found that disk accesses could be reasonably characterized by a first order Markov model. We used simulated annealing, together with maximum likelihood estimators of the Markov model parameters, to find a permutation of the (virtual) cylinders that substantially reduced expected seek distance. We then installed this permutation in a real system and tested it under a workload that was stochastically generated from the Markov model. We found this procedure offered a 25.6\% reduction in mean service time when compared to the original (unmapped) cylinder arrangement. Disk remapping provides an opportunity to optimize performance for multiple workloads, such as different shifts or days (e.g., many installations have a primarily interactive load during the day, but shift to batch and database processing in the evening). Normally a workload change would mean that a disk would have to be rearranged to accommodate a new disk map matching the new workload. Consider, however, a fault tolerant system maintaining multiple copies of physical disks. There is nothing to prevent each copy from having a unique translation map, tuned for a specific workload. In this case, a workload change could be met simply by a change in designation of the primary disk in a duplicated group. Finally, we should note that the realized 25.6\% improvement may be a conservative estimate of the potential for remapping. The distribution of requests across the virtual cylinders in our measured workload happened to be highly non-uniform. Should the distribution of requests become uniform, a pipe-organ arrangement would offer no improvement, and yet the Markov-based approach should still be effective. Further, the annealing algorithm strives to minimize average seek distance, but our interest is average seek time. Seek time is a nonlinear function of seek distance, and so the two averages are not equivalent with respect to optimization. A carefully measured seek time function should replace the more naive distance function, $|P(i) - P(j)|$, in future studies. \baselineskip=12pt \parindent=0pt \renewcommand{\section}[2]{\topsep=12pt\parskip=0pt\quad\begin{flushleft} \wrrbf #2\end{flushleft}} \begin{thebibliography}{10} \bibitem{gd:acodsa} R.~Geist and S.~Daniel. \newblock A continuum of disk scheduling algorithms. \newblock {\em ACM TOCS}, 5, 1987. \bibitem{grp:dsisv} R.~Geist, R.~Reynolds, and E.~Pittard. \newblock Disk scheduling in {S}ystem {V}. \newblock In {\em Proc. of the ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems}, pages 55--68, Banff, Alberta, May 1987. \bibitem{harin} G.~Haring. \newblock On stochastic models of interactive workloads. \newblock {\em Proc. of PERFORMANCE '83}, pages 133--152, May, 1983. \bibitem{kelly} M.H. Kelley. \newblock A look at the {DG/UX} file system. \newblock Technical Report~3, Data General Corporation, 1990. \bibitem{Kirk:Osaqs} S.~Kirkpatrick. \newblock Optimization by simulated annealing: quantitative studies. \newblock {\em Journal of Statistical Physics}, 34(5/6):pp. 975--986, March 1984. \bibitem{knuth} D.E. Knuth. \newblock {\em The Art of Computer Programming: Sorting and Searching}, volume~3. \newblock Addison-Wesley, 1973. \newblock pp. 404-405. \bibitem{wrr:sbds} R.~Reynolds. \newblock Sector-based disk scheduling in the {UNIX System V} environment. \newblock In {\em Proc. of the ACM Southeastern Regional Conf.}, pages 648--652, Mobile, Alabama, April 1988. \bibitem{wrrandbeede} R.~Reynolds and M.~Beede. \newblock An analytical comparison of disk scheduling algorithms. \newblock In {\em Proc. of the ACM Southeastern Regional Conf.}, pages 56--61, Birmingham, Alabama, April 1987. \bibitem{dgs:dswfk} D.~Suggs. \newblock Disk scheduling with future knowledge. \newblock In {\em Proc. of the ACM Southeastern Regional Conf.}, Greenville, South Carolina, April 1990. \bibitem{suggs:ms} D.~Suggs. \newblock The use of future knowledge in the design of a disk scheduling algorithm. \newblock Master's thesis, Clemson University, 1990. \bibitem{trive:book} K.~Trivedi. \newblock {\em Probability and Statistics with Reliability, Queueing and Computer Science Applications}. \newblock Prentice-Hall, 1982. \bibitem{vong} P.~Vongsathorn and S.D. Carson. \newblock A system for adaptive disk rearrangement. \newblock {\em Sofware Practice and Experience}, 20(3):pp. 225--242, March 1990. \end{thebibliography} \end{document}