The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Scheduling policies for disks and disk arrays
Author:	Liu, Chang
View Online:	njit-etd2005-079 (xiii, 116 pages ~ 9.3 MB pdf)
Department:	Department of Computer Science
Degree:	Doctor of Philosophy
Program:	Computer Science
Document Type:	Dissertation
Advisory Committee:	Leung, Joseph Y-T. (Committee chair) Czumaj, Artur (Committee member) Nakayama, Marvin K. (Committee member) Nassimi, David (Committee member) Yang, Jian (Committee member)
Date:	2005-05
Keywords:	Single/mirrored disk scheduling Performance analysis Shortest access time first (SATF) Simulation Trace-driven simulation RAID1 declustering
Availability:	Unrestricted
Abstract:	Recent rapid advances of magnetic recording technology have enabled substantial increases in disk capacity. There has been less than 10% improvement annually in the random access time to small data blocks on the disk. Such accesses are very common in OLTP applications, which tend to have stringent response time requirements. Scheduling of disk requests is intended to improve their response time, reduce disk service time, and increase disk access bandwidth with respect to the default FCFS scheduling policy. Shortest Access Time First policy has been shown to outperform other classical disk scheduling policies in numerous studies. Before verifying this conclusion, this dissertation develops an empirical analysis of the SATF policy, and produces a valuable by-product, expressed as x[m] = mp, during the study. Classical scheduling policies and some well-known variations of the SATE policy are re-evaluated, and three extensions are proposed. The performance evaluation uses self-developed simulators containing detailed disk information. The simulators, driven with both synthetic and trace workloads, report the measurements of requests, such as the mean and the 95th percentile of the response times, as well as the measurements of the system, such as the maximum throughput. A comprehensive arrangement of routing and scheduling schemes is presented or mirrored disk systems, or RAIDi. The performance evaluation is based on a twodimensional configuration classification: independent queues (i.e. a router sends the requests to one of the disks as soon as these requests arrive) versus a shared queue (i.e. the requests are held in a common queue at the router and are scheduled to be served); normal data layout versus transposed data layout (i.e. the data stored on the inner cylinders of one disk is duplicated on the outer cylinders of the mirrored disk). The availability of a non-volatile storage or NVS, which allows the processing of write requests to be deferred, is also investigated. Finally, various strategies of mirrored disk declustering are compared against the basic disk mirroring. Their competence of load balancing and their reliability are examined in both normal mode and degraded mode.