Prashant J. Shenoy
Harrick M. Vin
ABSTRACT
In this paper, we present the Cello disk scheduling framework for meeting the diverse service requirements of applications. Cello employs a two-level disk scheduling architecture, consisting of a class-independent scheduler and a set of class-specific schedulers. The two levels of the framework allocate disk bandwidth at two time-scales: the class-independent scheduler governs the coarse-grain allocation of bandwidth to application classes, while the class-specific schedulers control the fine-grain interleaving of requests. The two levels of the architecture separate application-independent mechanisms from application-specific scheduling policies, and thereby facilitate the co-existence of multiple class-specific schedulers. We demonstrate that Cello is suitable for next generation operating systems since: (i) it aligns the service provided with the application requirements, (ii) it protects application classes from one another, (iii) it is work-conserving and can adapt to changes in work-load, (iv) it minimizes the seek time and rotational latency overhead incurred during access, and (v) it is computationally efficient.
- 1.R K. Abbott and H. Garcia-Molina. Scheduling I/O Requests with Deadlines: A Performance Evaluation. In Proceedings oJRTSS, pages 113-124, December 1990.Google Scholar
Cross Ref
- 2.D. Anderson, Y. Osawa, and R. Govindan. A File System for Continuous Media. ACM Transactions on Computer Systems, 10(4):311-337, November 1992. Google ScholarDigital Library
- 3.P. Barham. A Fresh Approach to File System Quality of Service. In Proceedings of NOSSDA V'97, St. Louis, Missouri, pages 119-128, May 1997.Google ScholarCross Ref
- 4.M J. Carey, R. Jauhari, and M. Linvy. Priority in DBMS Resource Scheduling. In Proceedings of the 15th VLDB Conference, 1989. Google ScholarDigital Library
- 5.S. Chen, J. A. Stankovic, J. F. Kurose, and D. Towsley. Performance Evaluation of Two New Disk Scheduling Algorithms for Real-Time Systems. Journal of Real-Time Systems, 3:307-336, 1991.Google ScholarCross Ref
- 6.E G. Coffman and M. Hofri. On the Expected Performance of Scanning Disks. SIAM Journal of Computing, 10(1):60-70, February 1982.Google Scholar
- 7.E G. Coffman, L A. Klimko, and B. Ryan. Analysis of Scanning Policies for Reducing Disk Seek Times. SlAM Journal of Computing, 1(3):269-279, September 1972.Google ScholarCross Ref
- 8.P J. Denning. Effects of Scheduling on File Memory Operations. In Proceedings ofAFIPS SJCC, pages 9-21, 1967.Google ScholarDigital Library
- 9.R. Geist and S. Daniel. A Continuum of Disk Scheduling Algorithms. ACM Transactions on Computer 5)#stems, 5(1):77-92, February 1987. Google ScholarDigital Library
- 10.M. Hofri. Disk Scheduling: FCFS vs. SSTF Revisited. Communications of the ACM, 23(11):645-653, November 1980. Google ScholarDigital Library
- 11.D M. Jacobson and J. Wilkes. Disk Scheduling Algorithms Based on Rotational Position. Technical report, Hewlett Packard Labs, February 1991.Google Scholar
- 12.M.B. Jones, P. Leach, R. Draves, and J. Barrera. Support for User-Centric Modular Real-Time Resource Management in Rialto Operating System. In Proceedings of NOSSDAV'95, Durham, New Hampshire, April 1995. Google ScholarDigital Library
- 13.J. P. Lehoczky and S. Ramos-Thuel. An optimal algorithm for scheduling soft-aperiodic tasks in fixedpriority preemptive systems. In Proceedings of Real Time Systems Symposium, pages 110-123, December 1992.Google ScholarCross Ref
- 14.C L. Liu and J W. Layland. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. .lournal of the ACM, 30:47-61, 1973. Google ScholarDigital Library
- 15.A. Molano, K. Juvva, and R. Rajkumar. Real-time File Systems: Guaranteeing Timing Constraints for Disk Accesses in RT-Mach. In Proceedings of IEEE Real-time 5),stems Syny#osium, December 1997. Google ScholarDigital Library
- 16.A.L. Narasimha Reddy and J. Wyllie. Disk Scheduling in Multimedia I/O System. In Proceedings of ACM Multimedia'93, Anaheim, CA, pages 225-234, August 1993. Google ScholarDigital Library
- 17.M. Seltzer, P. Chen, and J. Ousterhout. Disk Scheduling Revisited. In Proceedings of the 1990 Winter USENIX Conference, Washington, D.C., pages 313-323, Jan 1990.Google Scholar
- 18.T. Teorey and T. B. Pinkerton. A Comparative Analysis of Disk Scheduling Policies. Communications of the ACM, 15(3):177-184, March 1972. Google ScholarDigital Library
- 19.N. C. Wilhehn. An Anomaly in Disk Scheduling: A Comparison of FCFS and SSTF Seek Scheduling using and Empirical Model for Disk Access. Communications oftheACM, 19(1):13-17, January 1976. Google ScholarDigital Library
- 20.B L. Worthington, G R. Ganger, and Y N. Patt. Scheduling Algorithms for Modern Disk Drives. In Proceedings of ACM SIGMETRICS'94, pages 241-251, May 1994. Google ScholarDigital Library
Index Terms
- Cello: a disk scheduling framework for next generation operating systems
Recommendations
Cello: A Disk Scheduling Framework for Next Generation Operating Systems*
Flexible Scheduling on Real-Time SystemsIn this paper, we present the Cello disk scheduling framework for meeting the diverse service requirements of applications. Cello employs a two-level disk scheduling architecture, consisting of a class-independent scheduler and a set of class-specific ...
Cello: a disk scheduling framework for next generation operating systems
In this paper, we present the Cello disk scheduling framework for meeting the diverse service requirements of applications. Cello employs a two-level disk scheduling architecture, consisting of a class-independent scheduler and a set of class-specific ...
Comments