WRR-SCAN: a rate-based real-time disk-scheduling algorithm

ABSTRACT

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 aperiodic tasks. In this paper, we propose a novel rate-based real-time disk-scheduling algorithm called WRR-SCAN (Weighted-Round-Robin SCAN). WRR-SCAN guarantees to meet the deadline of a real-time task by reserving disk bandwidth according to its real-time constraints. WRR-SCAN services scheduled tasks in scan order to minimize the disk-seek time. In addition, WRR-SCAN delivers better response time for aperiodic tasks which are served in best-effort manner by priority based algorithms. We conducted a set of extensive experiments to compare WRR-SCAN and SCAN-EDF, a priority-based algorithm studied extensively in literature. The experimental results show that WRR-SCAN reduces non-transmission overhead significantly and produces a guaranteed minimum data rate for aperiodic tasks while keeping the deadlines of real-time tasks.

REFERENCES

• 1: David P. Anderson, Metascheduling for continuous media, ACM Transactions on Computer Systems (TOCS), v.11 n.3, p.226-252, Aug. 1993 [doi>10.1145/152864.152866]
• 2: David P. Anderson , Yoshitomo Osawa , Ramesh Govindan, A file system for continuous media, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.311-337, Nov. 1992 [doi>10.1145/138873.138875]
• 3: Jim Gemmell , Stavros Christodoulakis, Principles of delay-sensitive multimedia data storage retrieval, ACM Transactions on Information Systems (TOIS), v.10 n.1, p.51-90, Jan. 1992 [doi>10.1145/128756.128758]
• 4: W. G. Aref , I. Kamel , S. Ghandeharizadeh, Disk Scheduling in Video Editing Systems, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.933-950, November 2001 [doi>10.1109/69.971188]
• 5: R.-I. Chang , W.-K. Shih , R.-C. Chang, Deadline-Modification-SCAN with Maximum-Scannable-Groups for Multimedia Real-Time Disk Scheduling, Proceedings of the IEEE Real-Time Systems Symposium, p.40, December 02-04, 1998
• 6: T.-S. Chen and W.-P. Yang. Amortized Analysis of Disk Scheduling Algorithm V(R)*. Journal of Information Science and Engineering, 8(1):223--242, 1992.
• 7: Tung-Shou Chen , Wei-Pang Yang , R. C. T. Lee, Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and N-step SCAN, BIT, v.32 n.4, p.546-558, 1992 [doi>10.1007/BF01994839]
• 8: A. Dan , D. Sitaram , P. Shahabuddin, Scheduling policies for an on-demand video server with batching, Proceedings of the second ACM international conference on Multimedia, p.15-23, October 15-20, 1994, San Francisco, California, United States [doi>10.1145/192593.192614]
• 9: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.1-12, Sep. 1989
• 10: Craig S. Freedman , David J. DeWitt, The SPIFFI scalable video-on-demand system, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.352-363, May 22-25, 1995, San Jose, California, United States
• 11: T.-Y. Huang, C.-C. Chou, and P.-Y. Chen. Bounding the Execution Times of DMA I/O Tasks on Hard-Real-Time Embedded Systems. In Proceedings of RTCSA, pages 516--529, 2003.
• 12: I. Kamel and Y. Ito. Disk Bandwidth Study for Video Servers. Technical Report TR-153-96, Matsushita Information Technology Laboratory, 1996.
• 13: I. Kamel, T. Niranjan, and S. Ghandeharizedah. A Novel Deadline Driven Disk Scheduling Algorithm for Multi-Priority Multimedia Objects. In Proceedings of Internatilnal Conference on Data Engineering, 2002.
• 14: Salil S. Kanhere , Harish Sethu , Apha B. Parekh, Fair and Efficient Packet Scheduling Using Elastic Round Robin, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.324-336, March 2002 [doi>10.1109/71.993210]
• 15: D. R. Kenchammana-Hosekote and J. Srivastava. Scheduling Continuous Media in a Video-On-Demand Server. In IEEE International Conference on Multimedia Computing and Systems, pages 19--28, May 1994.
• 16: M. H. Klein and T. Ralya. An Anlysis of Input/Output Paradigms for Real-Time Systems. Technical Report CMU/SEI-90-TR-19, CMU Software Engineering Institute, July 1990.
• 17: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 18: J. W.-S. Liu. Predictability of Real-time Software on Commodity Platform. In Lecture Notes of European Summer School on Embedded and Real-Time Systems, 2004.
• 19: P. Lougher and D. Shepherd. The Design of a Storage Server for Continuous Media. The Computer Journal, 36(1):32--42, 1993.
• 20: Anirban Mahanti , Derek L. Eager , Mary K. Vernon , David Sundaram-Stukel, Scalable on-demand media streaming with packet loss recovery, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.97-108, August 2001, San Diego, California, United States
• 21: P. Venkat Rangan , Harrick M. Vin, Designing file systems for digital video and audio, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.81-94, October 13-16, 1991, Pacific Grove, California, United States
• 22: P. V. Rangan , H. M. Vin, Efficient Storage Techniques for Digital Continuous Multimedia, IEEE Transactions on Knowledge and Data Engineering, v.5 n.4, p.564-573, August 1993 [doi>10.1109/69.234769]
• 23: A. L. Narasimha Reddy , Jim Wyllie, Disk scheduling in a multimedia I/O system, Proceedings of the first ACM international conference on Multimedia, p.225-233, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.166292]
• 24: A. L. Narasimha Reddy , James C. Wyllie, I/O issues in a multimedia system, Computer, v.27 n.3, p.69-74, March 1994 [doi>10.1109/2.268888]
• 25: Chris Ruemmler , John Wilkes, An introduction to disk drive modeling, Computer, v.27 n.3, p.17-28, March 1994 [doi>10.1109/2.268881]
• 26: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round-robin, IEEE/ACM Transactions on Networking (TON), v.4 n.3, p.375-385, June 1996 [doi>10.1109/90.502236]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Algorithms, Performance

Keywords:
real-time disk-scheduling, real-time multimedia servers, weighted round-robin