Proceedings of the 24th IEEE International Real Time Systems Symposium Cancun Mexico December 2003 1 Rotational Position Aware Real Time Disk Scheduling Using a Dynamic Active Subset DAS Lars Reuther Martin Pohlack Dresden University of Technology Department of Computer Science 01062 Dresden Germany reuther pohlack os inf tu dresden de Abstract Scheduling disk requests with service guarantees has to bring the demand to meet guarantees in line with the need to optimize disk utilization This paper presents the design implementation and experimental evaluation of a disk scheduling framework which optimizes the disk utilization under the constraints of both hard and statistical service guarantees The framework is based on two principles 1 upon each scheduling decision the calculation of a subset of the outstanding disk requests such that all service guarantees can be enforced under worst case assumptions and 2 the scheduling of this subset based on the rotational position of requests in order to improve the disk utilization Results are presented through an implementation of the scheduling framework in DROPS the Dresden Real Time Operating System 1 Introduction Disk storage usage in modern systems includes traditional best effort file access as well as the storage and retrieval of video and audio streams The latter application constrains the ability of a disk request scheduler to optimize the disk utilization While best effort applications have relatively weak requirements like good response times the retrieval of a video stream requires that deadlines for individual disk requests are met A disk request scheduler has to bring these constraints in line with the need to optimize the disk utilization which is crucial for good overall performance of the storage system Giving service guarantees for disk requests is a challenging requirement for a disk request scheduler Because of the physical design of disk drives the execution times of disk requests have a poor ratio of average and worst case execution times However the knowledge of the execution time distributions can be used to give statistical service guarantees If an application can tolerate occasional deadline misses statistical service guarantees can be used to substantially improve the disk utilization compared to hard service guarantees 4 This paper introduces and evaluates an admissioncontrol and scheduling algorithm which a can provide both hard and statistical service guarantees for disk requests and b uses an SATF shortest access time first based request scheduler to optimize the disk utilization Service guarantees are ensured by calculating the active subset of the outstanding disk requests upon each scheduling decision such that no guarantees will be violated regardless of which request of this subset is executed Then this subset is scheduled based on the rotational position of the disk requests The rest of this paper is organized as follows The next section gives an overview of a general admission control algorithm which can give both hard and statistical real time guarantees In Section 3 we describe the application of that admission control algorithm to disk storage and a diskscheduling algorithm which enforces service guarantees as well as optimizes the disk utilization In Section 4 we evaluate the implementation of our scheduler Section 5 gives an overview of related work and Section 6 concludes the paper 2 Background Quality Assuring Scheduling in DROPS The interest in statistical guarantees in real time systems has been sparked by the observation that certain types of applications most notably multimedia applications cannot afford the poor resource utilization yielded by absolute guarantees but at the same time such applications can tolerate occasional deadline misses to a certain extent The work we present in this paper was conducted in the context of 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 which aims to improve the resource utilization of real time systems by splitting calculations into one mandatory part and several optional parts The mandatory part has to be executed under any circumstances whereas optional parts may be dropped in case of resource shortage and using a probabilistic model in the admission control which assures a certain quality parameter i e the percentage of optional parts which meet their deadline The goal is to schedule active resources such that under overload the system behavior degrades gracefully and predictably Gracefully means that only optional parts are omitted and predictably means that the number of dropped parts can be predicted More precisely a periodic task Ti is a sequence of jobs Jij where Jij is to be executed in the j th period of Ti Each job Jij consists of a mandatory part Mij and one or more optional parts Oij1 Oij2 Oijci the number ci of optional parts is fixed for each task Each of these parts is considered successful if it is completely executed This condition must hold for all mandatory parts of a task but it is sufficient that only a given percentage of optional parts is successful To ensure that all optional parts reach the requested quality but do not consume more resources than necessary in case of resource shortage a resource scheduler must enforce a reservation time ri The reservation time is a constant amount of time which is assigned to each task Ti in each period to execute the optional parts When an optional part has exhausted this time the optional part is aborted and later parts of the same job are not started The reservation time is calculated on the basis of worst case execution times for mandatory parts and the expected execution times of both the optional and mandatory parts for optional parts Therefore the execution time of the mandatory parts Mij and the optional parts Oijk are represented as non negative random variables Xij and Yijk k 1 ci In the context of this work for each task Ti Xij and Yijk are assumed to 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 Xi execution time of the mandatory part Yi execution time of an optional part ci number of optional parts wi worst case execution time of the mandatory part i e P Xi wi 1 qi quality parameter percentage of successful optional parts 0 qi 1 t length of period 2 These values must be