Optimal Real Time Disk Scheduling Algorithms for Tasks with Fixed Deadlines

This paper summarizes the state of the art algorithms in the areas of scheduling and operating system kernels suited for real time. Given the vast amount of work that has been done by both the operations research and computer science communities in the scheduling area, five traditional scheduling approaches are discussed. A good scheduling algorithm should be fast and fair and should be able to serve as many I/O requests as possible in a given period of time, while not causing starvation for some requests. The two main concerns of disk scheduling algorithms are, therefore, to reduce the total time needed to serve a number of requests (access time) and the average time between the arrival of requests and them being served (waiting time). The access time for any I/O consists of the time needed for the disk arm to move the head to the requested track (seek time) in addition to the time required for the disk to rotate to the specified sector on track (rotational latency). The dominant factor of the access time is the seek time; hence, rotational latency is usually ignored by scheduling algorithms. Traditional real-time disk-scheduling algorithms service real time tasks according to their deadlines. Such a priority based algorithm, although satisfying real-time constraints, yields low disk utilization due to the excessive disk-seek time. Furthermore, it results in prolonged response time or even starvation for periodic tasks. The problem of disk scheduling to enhance disk performance is presented. According to the results obtained, the best competing of the conventional scheduling algorithms are the C-LOOK and the LOOK algorithms.