臺灣博碩士論文加值系統

現今有許多的硬碟排程器(disk scheduler)，以一般個人電腦用途而言，他們的目標大多為在增加硬碟的生產量(throughput)與程式所要求的服務的反應時間(respose time)之間取得平衡，也就是說,雖然我們希望硬碟的生產量越大越好; 但是也不能讓應用程式所要求的disk I/O等待的太久.而有特定服務需求或是時間限制的程式，像是real-time system,主要在滿足對特定程式的要求的完成時間的限制。
我們所提出的硬碟排程器，針對在同時多個I/O bound的程式的情況下，可以讓特定的高優先權的程式有較短的執行時間(elapsed time)。在同時執行5個程式的狀況下以某特定程式而言,比未修改的anticipatory scheduler 增進效能 45%到81%。

1 簡介
1.1 動機
1.2 磁碟的特性

2 Linux Kernel的硬碟排程器
2.1 Linux Elevator
2.2 Deadline硬碟排排程器
2.3 Anticipatory Scheduler

3 Deceptive Idleness
3.1 Deceptive Idleness發生的原因
3.1 Deceptive Idleness發生的充要條件

4 Anticipatory Scheduler

5 Anticiapatory Scheduler by Process Design and Implementation

6 Noop Scheduler by Process

7 未來目標

8 結論

[1] R. Abbott and H. Garcia-Molina. Scheduling I/O requests with deadlines: A performance evaluation. In Proceedings of the IEEE Real-Time Systems Symposium, pages 113–124, 1990.
[2] W. G. Aref, K. El-Bassyouni, I. Kamel, and M. F. Mokbel. Scalable QoS-Aware Disk-Scheduling. In Proceedings of the 20th International Conference on Data Engineering, pages 255–256, 2002.
[3] S. A. Brandt, S. Banachowski, C. Lin, and T. Bisson. integrated scheduling of hard real-time, soft real-time and non-real-time processes. In Proceedings of the IEEE Real-Time Systems Symposium,2003.
[4] J. L. Bruno, J. C. Brustoloni, E. Gabber, B. Ozden, and A.Silberschatz. Disk scheduling with quality of service guarantees. In IEEE ICMCS, pages 400–405, 1999.
[5] J. Gemmell, H. M. Vin, D. D. Kandlur, P. V. Rangan, and L. A. Rowe. Multimedia storage servers: A tutorial and survey. In IEEE Compute, pages 40–49, 1995.
[6] P. Goyal, X. Guo, and H. M. Vin. A hierarchical cpu scheduler for multimedia operating systems. In Proceedings of the 2nd Symposium on Operating Systems Desgin and Implementation OSDI, pages 107–112, 1996.
[7] L. J. Guibas and R. Sedgewick. A diochromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science, pages 8–21,
1978.
[8] L. Huang and T. cker Chiueh. Implementation of a rotation latency sensitive disk scheduler.
In Tech[9] S. Iyer and P. Druschel. Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O. In the 18th ACM Symposium on Operating Systems Principles (SOSP 2001), pages 117– 130, 2001.
[10] D. Jacobson and J. Wilkes. Disk scheduling algorithms based on rotational position. In Technical Report HPL-CSP-91-7rev1, Hewlett-Packard, 1991.
[11] C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real time environments. In Journal of ACM JACM, pages 46–61, 1973.
[12] C. W. Mercer, S. Savage, and H. Tokuda. Processor capacity reserves: Operating system support for multimedia applications. In International Conference on Multimedia Computing and Systems, pages 90–99, 1994.
[13] M. F. Mokbel, W. G.Aref, K. M. Elbassioni, and I. Kamel. Scalable multimedia disk scheduling. In Proceedings of the 20th International Conference on Data Engineering, pages 498–509, 2004.
[14] D. A. Patterson and J. L. Henness. Computer architectureh. In A Quantitative Approach, ISE, 3rd ed., 2002.
[15] A. L. N. Reddy and J. Wyllie. Disk scheduling in a multimedia I/O system. In Proceedings of ACM Conference on Multimedia, pages 225–233, 1993.
[16] M. Seltzer, P. Chen, and J. Ousterhout. Disk scheduling revisited. In USENIX Winter Technical Conference, pages 313–324, 1990.
[17] P. J. Shenoy and H. M. Vin. Cello: A disk scheduling framework for next generation operating systems. In Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, 1998.
[18] R. Wijayaratne and A. Reddy. Integrated QoS management for disk I/O. In Proceedings of the IEEE International Conference on Multimedia Computing and Systems, pages 487–492,
1999.
[19] B. L. Worthington, G. R. Ganger, and Y. N. Patt. Scheduling algorithms for modern disk drives. In ACM Sigmetrics, pages 146–156, 1994.
[20] R. R. Zoran Dimitrijevic. Quality of service support for real-time storage systems. In International IPSI-2003 Conference, 2003.