Proceedings of the 24th IEEE International Real-Time Systems Symposium, Cancun, Mexico, December 2003 1Rotational-Position-Aware Real-Time Disk SchedulingUsing a Dynamic Active Subset (DAS)Lars Reuther Martin PohlackDresden University of TechnologyDepartment of Computer Science01062 Dresden, Germany{reuther, pohlack}@os.inf.tu-dresden.deAbstractScheduling disk requests with service guarantees hasto bring the demand to meet guarantees in line with theneed to optimize disk utilization. This paper presents thedesign, implementation and experimental evaluation of adisk-scheduling framework which optimizes the disk utiliza-tion under the constraints of both hard and statistical ser-vice guarantees. The framework is based on two princi-ples: 1) upon each scheduling decision, the calculation ofa subset of the outstanding disk requests such that all ser-vice guarantees can be enforced under worst-case assump-tions and 2) the scheduling of this subset based on the ro-tational position of requests in order to improve the diskutilization. Results are presented through an implementa-tion of the scheduling framework in DROPS, the DresdenReal-Time Operating System.1. IntroductionDisk-storage usage in modern systems includes tradi-tional, best-effort file access as well as the storage and re-trieval of video and audio streams. The latter applicationconstrains the ability of a disk-request scheduler to optimizethe disk utilization. While best-effort applications have rel-atively weak requirements, like “good” response times, theretrieval of a video stream requires that deadlines for indi-vidual disk requests are met. A disk-request scheduler hasto bring these constraints in line with the need to optimizethe disk utilization which is crucial for good overall perfor-mance of the storage system.Giving service guarantees for disk requests is a challeng-ing requirement for a disk-requestscheduler. Because of thephysical design of disk drives, the execution times of diskrequests have a poor ratio of average and worst-case execu-tion times. However, the knowledge of the execution-timedistributions can be used to give statistical service guar-antees. If an application can tolerate occasional deadlinemisses, statistical service guarantees can be used to substan-tially improve the disk utilization compared to hard serviceguarantees [4].This paper introduces and evaluates an admission-control and scheduling algorithm which (a) can provideboth hard and statistical service guarantees for disk re-quests and (b) uses an SATF (shortest access time first)based request scheduler to optimize the disk utiliza-tion. Service guarantees are ensured by calculating the ac-tive subset of the outstanding disk requests upon eachscheduling decision such that no guarantees will be vio-lated regardless of which request of this subset is executed.Then, this subset is scheduled based on the rotational posi-tion of the disk requests.The rest of this paper is organized as follows: The nextsection gives an overviewof a general admission-control al-gorithm which can give both hard and statistical real-timeguarantees. In Section 3, we describe the application ofthat admission-control algorithm to disk storage and a disk-scheduling algorithm which enforces service guarantees aswell as optimizes the disk utilization. In Section 4, we eval-uate the implementation of ourscheduler. Section 5 gives anoverview of related work and Section 6 concludes the paper.2. Background: Quality-Assuring Schedulingin DROPSThe interest in statistical guarantees in real-time systemshas been sparked by the observation that certain types ofapplications (most notably multimedia applications) can-not afford the poor resource utilization yielded by abso-lute guarantees, but at the same time, such applications cantolerate occasional deadline misses to a certain extent. Thework we present in this paper was conducted in the contextof DROPS, the Dresden Real-Time Operating System [5].DROPS employs Quality-Assuring Scheduling (QAS) [4]Proceedings of the 24th IEEE International Real-Time Systems Symposium, Cancun, Mexico, December 2003 2which aims to improve the resource utilization of real-timesystems by:• splitting calculations into one mandatory part and sev-eral optional parts. The mandatory part has to be exe-cuted under any circumstances, whereas optional partsmay be dropped in case of resource shortage; and• using a probabilistic model in the admission controlwhich assures a certain quality parameter (i.e., the per-centage of optional parts which meet their deadline).The goal is to schedule active resources such that underoverload the system behavior degrades gracefully and pre-dictably.Gracefullymeans that onlyoptional parts are omit-ted, and predictablymeans that the number of dropped partscan be predicted.More precisely, a periodic task Tiis a sequence of jobsJij, where Jijis to be executed in the jthperiod of Ti. Eachjob Jijconsists of a mandatory part Mijand one or moreoptional parts Oij1, Oij2, ..., Oijci; the number ciof op-tional parts is fixed for each task. Each of these parts is con-sidered successful if it is completely executed. This condi-tion must hold for all mandatory parts of a task, but it is suf-ficient that only a given percentage of optional parts is suc-cessful. To ensure that all optional parts reach the requestedquality but do not consume more resources than necessaryin case of resource shortage, a resource scheduler must en-force a reservation time ri. The reservation time is a con-stant amount of time which is assigned to each task Tiineach period to execute the optional parts. When an optionalpart has exhausted this time, the optional part is abortedand later parts of the same job are not started. The reserva-tion time is calculated on the basis of worst-case executiontimes for mandatory parts and the expected execution timesof both the optional and mandatory parts for optional parts.Therefore the execution time of the mandatory parts Mijand the optional parts Oijkare represented as non-negativerandom variables Xijand Yijk, (k = 1, ..., ci). In the con-text of this work, for each task TiXijand Yijkare assumedto be identically distributed.To summarize, with QAS a task is described by a tuple:Ti= (Xi, Yi, ci, wi, qi, t), i ∈ N (1)where:Xiexecution time of the mandatory part;Yiexecution time of an optional part;cinumber of optional parts;wiworst-case execution time of the mandatory part, i.e.,P(Xi≤ wi) = 1;qiquality