Математическая модель двухуровневого управления ресурсами в операционных системах с закрытыми исходными кодами
Диссертация
В ходе научных исследований по разработке математической модели двухуровневого управления ресурсами в современных операционных системах с закрытыми исходными кодами использовались аналитические методы теории массового обслуживания, теории цифровой фильтрации, методы имитационного моделирования, методы теории операционных систем и системного программирования, методы, используемые в современных… Читать ещё >
Список литературы
- Almeida, J. Dabu, M. Manikutty, A. and Сао.Р. Providing differentiated quality of service in web hosting services. In WISP, June 1998.
- Aron, M. Iyer, S and Druschel, P A resource management framework for predictable quality of service in web servers, July 2001. http://www.cs.rice.edu/ ssiyer/r/mbqos/.
- Banga, G. Druschel, P. and Mogul.J. C. Resource containers: A new facility for resource management in server systems. In 3rd USENIX OSDI, Feb. 1999.
- Bennett, J. and Zhang.H. WFQ: Worst-case fair weighted fair queueing. In IEEE Infocom, Mar. 1996.
- J. Bennett, H. Zhang, Hierarchical packet fair queueing algorithms, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.675−689, Oct. 1997
- Black, D. «Scheduling and Resource Management Techniques for Multiprocessors». PhD Thesis, CMU-CS-90−152, Carnegie Mellon University, July 1990. http://citeseer.ist.psu.edu/article/black90scheduling.html
- A. Brodnik, S. Carlsson, J. Karlsson, J. Ian Munro, Worst case constant time priority queue, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.523−528, January 07−09, 2001, Washington, D.C., United States
- Bruno, J. Brustoloni, J. Gabber, E. Ozden, B. and Silberschatz A.. Disk scheduling with quality of service guarantees. IEEE ICMCS, June 1999.
- Candea G. M., Jones M. B. Vassal: loadable scheduler support for multi-policy scheduling. 1998
- Chen, S et el. Performance evaluation of two new disk scheduling algorithms for realtime systems. Journal of Real-Time Systems, 3(3):307−336, Sept. 1991.
- Cormen, T. Leiserson, C., Rivest, R, and Stein C. Introduction to Algorithms, Second Edition. МГГ Press and McGraw-Hill, 2001. ISBN 0−262−3 293−7. Section 6.5: Priority queues, pp. 138−142.
- Cromar, S. Solaris process scheduling. http://www.princeton.edu/~unix/Solaris/troubleshoot/schedule.html
- Deianov В. Fair CPU Scheduler for Linux: Электронный ресурс. http://fairsched.sourceforge.net/doc/fairsched.txt
- Demers, A. Keshav, S. Shenker, S /'Analysis and simulation of a fair queueing algorithm", Proceedings of SIGCOMM '89, 1989, pp. 1−12.
- Golubchik, L. Lui, Gail, H Evaluation of tradeoffs in resource management techniques for multimedia storage servers. ШЕЕ ICMCS, June 1999.
- Iyer, S. and Druschel.P. Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O. Technical Report. 18th ACM Symposium on Operating Systems Principles (SOSP 2001).
- Iyer, S. and Druschel.P. The effect of deceptive idleness on disk schedulers. Technical Report CSTR01−379, Rice University, June 2001.
- S. J. Golestani, «A self-clocked fair queueing scheme for broadband applications,» in Proc. IEEE INFOCOM, Toronto, Canada, June 1994, pp. 636−646.
- Goyal P., Guo X., Vin H. M. A hierarchical CPU scheduler for multimedia operating systems. Distributed multimedia computing laboratory. Department of Computer Sciences, University of Texas at Austin. 2001
- Hahne, E. «Round Robin Scheduling for Fair Flow Control in Data Communication Networks», Report LIDS-TH-1631, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts. December, 1986.
- John L. Hennessy, David A. Patterson, Computer Architecture, A Quantitative Approach (ISBN 1−55 860−724−2)
- Huang, L. and Chiueh, T.. Implementation of a rotation latency sensitive disk scheduler. Technical Report ECSL-TR81, SUNY, Stony Brook, Mar. 2000.
- Jacobson, D and Wilkes, J .Disk scheduling algorithms based on rotational position. Technical Report HPL-CSP-91−7revl, Hewlett-Packard, Feb. 1991.
- Jensen, E Locke, K. D and Tokuda. H A time driven scheduling model for real-time operating systems. In Proceedings ШЕЕ Real-Time Sytems Symposium, pages 112— 122, 1985.
- Jones M. В., Regebr J. CPU reservation and time constraints: implementation experience on Windows NT. 1999
- R. Jones and R. Lins, Garbage Collection: Algorithms for Automated Dynamic Memory Management, Wiley and Sons (1996), ISBN 0−471−94 148−4
- Goyal P., Vin H. M. Generalized Guaranteed Rate Scheduling Algorithms: A Framework. University of Texas at Austin, Austin, TX, 1995 .
- P. Goyal, H. Vin, H. Cheng, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.690−704, Oct. 1997
- Howard, J. Kazar, M. Menees, S. Nichols, D. Satyanarayanan, M. Sidebotham, R. and West, M.. Scale and performance in a distributed file system. ACM Transactions on Computer Systems, 6(1):51−81, Feb. 1988.
- S. Kanhere, H. Sethu, A. 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
- S. Kanhere, H. Sethu, On the Latency Bound of Pre-Order Deficit Round Robin, Proceedings of the 27th Annual IEEE Conference on Local Computer Networks, p.508−517, November 06−08, 2002
- Kargahi, M, Movaghar, A, «A Method for Performance Analysis of Earliest-Deadline-First Scheduling Policy,» dsn, p. 826, 2004 International Conference on Dependable Systems and Networks (DSN'04), 2004.
- M. Katevenis, S. Sidiropoulos, C. Courcoubetis: ««Weighted Round-Robin Cell Multiplexing in a General-Purpose ATM Switch Chip», IEEE Journal on Selected Areas in Communications, vol. 9, no. 8, October 1991, pp. 1265−1279.
- M. Katevenis: ««Fast Switching and Fair Control of Congested Flow in Broad-Band Networks», IEEE Journal on Selected Areas in Communications, vol. 5, no. 8, October 1987, pp. 1315−1326.
- Knuth, D. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0201−89 683−4. Section 2.4: Dynamic Storage Allocation, pp.43556.
- Kopetz, H «The time-triggered model of computation». IEEE Real-time systems symposium стр168−177, дек 1998
- Koren, G and Shasha, D. Skip-over: Algorithms and complexity for overloaded systems that allow skips. In Real-Time Systems Symposium, 1995. http://citeseer.ist.psu.edu/koren96skipover.html
- Kramp, T, Adrian, M and Koster, R. An open framework for real-time scheduling simulation. SFB 501 Report 01/00, Department of Computer Science, University of Kaiserslautern, Germany, January 2000. http://citeseer.ist.psu.edu/kramp00open.html
- Lampson, B.W. Redell, D. D. Experience with Processes and Monitors in Mesa. Communications of the ACM, Vol. 23, No. 2 (Feb 1980), pp. 105−117.
- Lehoczky, J. Sha, L. and Ding, Y. The Rate monotonic scheduling algorithm: exact characterization and average case behavior, IEEE Real-Time Systems Symposium, pp. 166−171, December 1989.
- L. Lenzini, E. Mingozzi, Giovanni Stea, A Unifying Service Discipline for Providing Rate-Based Guaranteed and Fair Queuing Services Based on the Timed Token Protocol, IEEE Transactions on Computers, v.51 n.9, p.1011−1025, September 2002
- L. Lenzini, E. Mingozzi, «Packet timed token service discipline: A scheduling algorithm based on the dual-class paradigm for providing QoS in integrated services networks,» Comput. Netw., vol. 39, pp. 363−384, July 2002.
- L. Lenzini, E. Mingozzi, and G. Stea, «Full exploitation of the Deficit Round-Robin capabilities by efficient implementation and parameter tuning,» Univ. of Pisa, Italy, Tech. Rep., Oct. 2003.
- Leung, J. Y., Whitehead J. Y. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 2(4):237—250, December 1982.
- L. Lenzini, E Mingozzi, G. Stea Tradeoffs between low complexity, low latency, and fairness with deficit round-robin schedulers. IEEE/ACM Transactions on Networking (TON.) Volume 12, Issue 4 (August 2004), pp 681 693. SSN: 1063−6692
- L. Lenzini, E. Mingozzi, and G. Stea, «Aliquem: A novel DRR implementation to achieve better latency and fairness at 0(1) complexity,» in Proc. 10th Int. Workshop on Quality of Service (IWQoS), Miami Beach, FL, May 2002, pp. 77−86.
- Liu C.L., Layland. J. «Scheduling algorithms for multiprogramming in hard real-time environment» Journal of the ACM, 20(1):46−61, 1973
- Liu, С and Layland, J. Scheduling Algorithms for Multiprogramming in a Hard Realtime Environment. Journal of the ACM, 20(1):46−61, Jan. 1973.
- Liu J.W.S. et al., «PERTS: A Prototyping Environment for Real-Time Systems,» Proc. 14 th IEEE Real-Time Systems Symp., Phoenix, AZ, December 1993, pp. 184 188. 23
- С. Lumb, J. Schindler, G. Ganger, D. Nagle, and E. Riedel. Towards higher disk head utilization: Extracting free bandwidth from busy disk drives. 4th USENIX OSDI, Oct. 2000.
- J. Mirkovic, S. Dietrich, D. Dittrich, P. Reiher Internet Denial of Service: Attack and Defense Mechanisms. Prentice Hall, 2005
- T. Mowry, A. Demke, and O. Krieger. Automatic compiler inserted I/O prefetching for out-of-core applications. 2nd USENIX OSDI, Oct. 1996.
- D. Roselli, J. R. Lorch, and Т. E. Anderson. A comparison of file system workloads. USENIX Annual Technical Conference, June 2000.
- E. Rosti, E. Smirni, G. Serazzi, and L. W. Dowdy. Analysis of non-work-conserving processor partitioning policies. Lecture Notes in Computer Science, 949:165−181, 1995.
- C. Ruemmler and J. Wilkes. An introduction to disk drive modeling. IEEE Computer, 27(3): 17−28, 1994.
- Parsons, E and Sevcik, K, «Implement- ing multiprocessor scheduling disciplines». In IPPS'97 Workshop Job Scheduling Strategies for Parallel Processing. http://citeseer.ist.psu.edu/479 768.html
- H. Patterson, G. Gibson, E. Ginting, D. Stodolsky, and J. Zelenka. Informed prefetching and caching. In 15th ACM SOSP, Dec. 1995.
- A. K. Parekh and R. G. Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case. IEEE/ACM Transactions on Networking, 1(3):344—357, June 1993.
- D. Saha, S. Mukherjee, Satish K. Tripathi, Carry-over round robin: a simple cell scheduling mechanism for ATM networks, IEEE/ACM Transactions on Networking (TON), v.6 n.6, p.779−796, Dec. 1998
- Seltzer, M. Chen, P. and Ousterhout, J.. Disk scheduling revisited. USENIX Winter Technical Conference, Jan. 1990.
- Sha, L. Rajkumar R. Lehoczky, J. P. Priority inheritance protocols: an approach to real-time synchronization, IEEE Transactions on Computers, vol. 39 no. 9, September 1990, pp. 1175−1185.
- Shenoy, P and Vin, H. Cello: A disk scheduling framework for next generation operating systems. ACM Sigmetrics, June 1998.
- B. A. Shirazi, A. R. Hurson, and К. M. Kavi, «Scheduling and load balancing in parallel and distributed systems,» IEEE CS Press, 1995.
- 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
- E. Shriver, C. Small, and K. Smith. Why does file system prefetching work? USENIX Annual Technical Conference, June 1999.
- Solomon D. A, Russinovich M.E. Inside Microsoft® Windows® 2000, Third Edition, Microsoft Press, 2000
- Stankovic, J.A. Spuri, M. Di Natale, M. and Buttazzo, G.C.. Implications of Classical Scheduling Results for Real-Time Systems. IEEE Computer, pp. 16— 25, 1995.
- Stewart, D, Barr, M. «Rate Monotonic Scheduling» Embedded Systems Programming, March 2002, pp. 79−80. Электронный ресурс: http://www.netrino.com/Publications/Glossary/RMA.html
- D. Stiliadis, A. Varma, Latency-rate servers: a general model for analysis of traffic scheduling algorithms, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.611−624, Oct. 1998
- D. Stiliadis, A. Varma, LATENCY-RATE SERVERS: A GENERAL MODEL FOR ANALYSIS OF TRAFFIC SCHEDULING ALGORITHMS, University of California at Santa Cruz, Santa Cruz, CA, 1995
- Stoica I., Zhang H., Eugene Ng. T.S. A hierarchical fair service curve algorithm for link-sharing, real-time and priority services. School of Computer Science. Carnegie Mellon University. 1997
- D. Sullivan and M. Seltzer. Isolation with flexibility: A resource management framework for central servers. USENIX Annual Technical Conference, June 2000.
- F. Toutain, «Decoupled generalized processor sharing: A fair queuing principle for adaptive multimedia applications,» in Proc. IEEE INFOCOM, San Francisco, С A, Mar.-Apr. 1998, pp. 291−298.
- S. Tsao, Y. Lin, Pre-order deficit round robin: a new scheduling algorithm for packet-switched networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.35 n.2−3, p.287−305, Feb. 2001
- P. Van Emde Boas, R. Kaas, and E. Zijlstra, «Design and implementation of an efficient priority queue,» Math. Syst. Theory, vol. 10, pp. 99−127, 1977.
- R. Vaswani and J. Zahorjan. The implications of cache affinity on processor scheduling for shared memory multiprocessors.13th ACM SOSP, Oct. 1991.
- В. Verghese, A. Gupta, and M. Rosenblum. Performance isolation: Sharing and isolation in shared memory multiprocessors. ASPLOS, Oct. 1998.
- C. Waldspurger and W. Weihl. Lottery scheduling: Flexible proportional-share resource management. In 1st USENDC OSDI, Nov. 1994.
- C. Waldspurger and W. Weihl. Stride scheduling: Deterministic proportional resource management. Technical report, MIT/LCS/TM-528, June 1995.
- Wang S., Wang Y.-Ch., Lin K.-J. A priority-based weighted fair queuing scheduler for real-time network, Electrical and Computer Engineering, University of California, Irvine. 2002
- Wang Y.-Ch., Lin K.-J. Implementing a general real-time scheduling framework on the RED-Linux real-time kernel. Department of Electrical and Computer Engineering, University of California, Irvine. 1999
- Williams, P. Jun 2000 Unitied States Patent 6,758,889
- B. Worthington, G. Ganger, and Y. Patt. Scheduling algorithms for modern disk drives. In ACM Sigmetrics, 1994.
- J. Yao, J. Guo, and Z. Xu, «Scheduling real-time multimedia tasks in network processors,» IEEE GLOBECOM, Dallas, November 2004.
- K. Yau, J. Lui, and F. Liang. Defending against distributed denial-of-service attacks with max-min fair server-centric router throttles. In Proceedings of IEEE International Workshop on Quality of Service (IWQoS), Miami Beach, FL, May 2002.
- H. Zhang. Providing end-to-end performance guarantees using non-work-conserving disciplines. Computer Communications, 18(10), Oct. 1995.
- Zhang, H Resource Management For Service-Oriented Internet. School of Computer Science, Carnegie Mellon University. http://www.cra.org/Policy/NGI/papers/zhangWP
- H. Zhang, «Service disciplines for guaranteed performance service in packet-switching networks,» Proc. IEEE, vol. 83, pp. 1374−1396, Oct. 1995.
- Браммер К., Зиффлинг Г. Фильтр Калмана-Быоси. М.: Наука, 1982.
- Гнеденко Б.В., Коваленко И. Н. Введение в теорию массового обслуживания. -М.: Наука, 1987. 336 с.
- Емельянов, П.В. Коротаев, К.С. Луковников, И. В. Основные проблемы реализации алгоритмов пропорционального планирования// Процессы и методы обработки информации: Сб. ст/Моск. физико-техн. ин-т. М., 2006.
- Кемени Дж., Снелл Дж. Конечные цепи Маркова: Пер. с англ. М.: Наука, 1970.
- Леви. Л. Применение фильтров Калмана в навигационной аппаратуре,. http://www.navgeocom.m/gps/kalman/index.htm
- Луковников, И.В. Коротаев, К.С, Кобец А. Л Проблемы управления распределяемыми ресурсами ОС// Информационные технологии № 10. М. 2006, с 71−78
- Нуммелин Е. Общие неприводимые цепи Маркова и неотрицательные операторы. М.: Мир. — 1989. — 207с.
- Проект Aurema Электронный ресурс. http://aurema.com
- Проект Virtuozzo Электронный ресурс. http://virtuozzo.com
- Феллер В. Введение в теорию вероятностей и ее приложения. Т.1. М.: Мир, 1984.
- Хинчин А.Я. Работы по математической теории массового обслуживания. М.: Физматгиз, 1963.