автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математическая модель двуху109ровневого управления ресурсами в операционных системах с закрытыми исходными кодами

ВВЕДЕНИЕ.

Актуальность темы.

Цель работы, объект и предмет исследования.

Методы исследования.

Научная новизна.

Практическая значимость.

Апробация и реализация результатов работы.

Положения, выносимые на защиту.

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ МАТЕМАТИЧЕСКИХ АЛГОРИТМОВ УПРАВЛЕНИЯ.

1.1. Планировщик задач, основанный на их приоритетах (PD scheduler).

1.1.1 Rate-Monolithic алгоритм.

1.1.2. EDF (Earliest Deadline First) алгоритм.

1.2. Планировщик задач, основанный на долях процессорного времени (SD).

1.2.1. Fair CPU scheduler.

1.3. Планировщики, основанные на времени (TD).

1.4. Другие планировщики.

1.5. Роль планировщиков. Комбинированные планировщики.

ВЫВОДЫ ПО ГЛАВЕ 1.

ГЛАВА 2. ПОСТАНОВКА ЗАДАЧИ. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ДВУХУРОВНЕВОГО УПРАВЛЕНИЯ.

2.1. Постановка задачи.

2.2. Математическая модель двухуровневого управления.

2.3. Классификация ресурсов.

2.3.1. Возобновляемые ресурсы.

2.3.2. Невозобновляемые и частично возобновляемые ресурсы.

ВЫВОДЫ ПО ГЛАВЕ 2.

ГЛАВА 3. МОДЕЛЬ И МЕТОД ДВУХУРОВНЕВОГО УПРАВЛЕНИЯ РЕСУРСАМИ CPU.

3.1. Построение модели.

3.2. Алгоритм планирования в Windows 2003 Server.

3.3. Экспериментальное подтверждение математической модели.

ВЫВОДЫ ПО ГЛАВЕ 3.

Актуальность темы

Современные вычислительные мощности позволяют даже на домашнем компьютере производить за считанные минуты расчеты, на которые всего пять-шесть лет назад потребовалось бы несколько часов. Объем оперативной памяти, экономически доступной конечному пользователю, превосходит размеры дисков, стоявших в персональных компьютерах шесть лет назад. В десятки раз выросли и производительность, и объем современных жестких дисков.

И тем не менее в ряде областей, таких как предоставление провайдерских услуг, корпоративном обслуживании клиентов, предоставлять конечному пользователю физически выделенный сервер нецелесообразно[102]:

• высокая стоимость аппаратуры серверов

• высокие затраты на аренду помещений для размещения серверов

• электричество и охлаждение

• обслуживание

• большое время на развертывание и восстановление нового сервера

Размещение нескольких виртуальных серверов на одном физическом усугубляет проблемы безопасности и обеспечения надлежащего качества обслуживания, важным элементом которого является разграничение ресурсов между виртуальными серверами, таких как различные виды памяти, пропускная способность сети, пропускная способность жесткого диска, время центрального процессора.

Для обеспечения надлежащего качества обслуживания возникает необходимость ограничения потребление ресурсов группами процессов.

В способах разграничения потребления ресурсов наиболее простым является выставление ограничения на всю группу процессов на так называемом микро-уровне - когда управление выполняется на интервалах, сравнимых по величине с минимальными интервалами изменения регулируемого параметра. Как правило, это делается на уровне ядра операционной системы. Таким образом, достигается эффект, при котором все процессы в группе не могут потребить в сумме больше, чем разрешено.

Такой способ является достаточно эффективным, но в ряде случаев не может быть реализован в силу разных причин. Например, для реализации подобного решения может потребоваться вмешательство в ядро операционной системы, что опять-таки в ряде случаев ограниченно как соображениями безопасности, так и некоторыми другими.[109]

Примером реализации подобного рода управления ресурсами может послужить технология Virtuozzo.[108].

Альтернативным решением является наложение ограничений на группу процессов на так называемом макро-уровне - когда управление выполняется на интервалах, как правило, превосходящих минимальные интервалы изменения управляемого параметра и осуществляется средствами высокого уровня, опираясь на механизмы, предоставляемые нижним уровнем. Примером такого управления может послужить технология Aurema[107], корректирующая поведение стандартного планировщика Windows 2003 Server с помощью изменения базового приоритета процессов в системе. Однако в этом случае пики потребления ресурсов между такого рода макро-воздействиями могут существенно снизить точность управления [104].

Будем называть двухуровневым управлением управление, удовлетворяющее ниже перечисленным критериям:

1) осуществляет управление, используя механизмы, предоставляемые, явно или неявно, системой управления нижележащего уровня основным управлением ресурсами операционных систем или микроуправлением) 2) интервалы воздействия этого управления, как правило, превышают интервалы, характерные для системы управления нижележащего уровня.

Алгоритмы и методы двухуровневого управления - это новая область в теории управления ресурсами операционных систем. Существующие математические модели не учитывают особенности алгоритмов управления нижнего уровня, что приводит к существенному ухудшению точности управления.

Цель работы, объект и предмет исследования

Цель диссертационной работы - разработка математических моделей и методов двухуровневого управления ресурсами в современных операционных системах с закрытыми исходными кодами.

Задачи исследования:

• разработка математической модели двухуровневого управления ресурсами в современных операционных системах с закрытыми исходными кодами

• объяснение, в рамках данной модели, механизмов существующих методов контроля ресурсов в современных операционных системах

• исследование ограничений, которые нужно задать в системе, чтобы обеспечить требуемое качество управления

Объект исследования - механизмы управления ресурсами в современных операционных системах, используемые для предоставления надлежащего качества обслуживания.

Предмет исследования - модель двухуровневого управления ресурсами в современных операционных системах.

Методы исследования

В ходе научных исследований по разработке математической модели двухуровневого управления ресурсами в современных операционных системах с закрытыми исходными кодами использовались аналитические методы теории массового обслуживания, теории цифровой фильтрации, методы имитационного моделирования, методы теории операционных систем и системного программирования, методы, используемые в современных системах виртуализации.

Научная новизна

Научная новизна работы заключается в том, что автором предложена математическая модель двухуровневого управления виртуализованными ресурсами вычислительных систем и комплексов при предоставлении различных видов сервиса в современных операционных системах с закрытыми исходными кодами, основанных на формировании виртуальной среды пользователя.

В отличие от ранее существовавших моделей виртуализации, разработанная в ходе диссертационного исследования математическая модель более полно учитывает особенности, налагаемые собственными механизмами управления ОС, что позволяет существенно повысить утилизацию ресурсов системы, повысить ее надежность и обеспечить необходимое качество обслуживания.

Разработанная математическая модель двухуровневого управления виртуализированными ресурсами современных операционных систем с закрытыми исходными кодами является новым вкладом в развитие теории операционных систем, системного программирования и технологий виртуализации операционных систем.

Практическая значимость

Разработанные математические модели могут быть использованы при создании новых программных комплексов, предназначенных для решения задач виртуализации с целью достижения максимального уровня утилизации ресурсов, надежности систем и обеспечения высокого качества обслуживания.

Также разработанные математические модели и методы могут быть использованы в качестве самостоятельных решений различных задач, возникающих в ходе предоставления различных видов сервиса в современных операционных системах.

Так, математическая модель двухуровневого управления позволяют решить ряд технических проблем, связанных с обеспечением заданного распределения ресурсов, которое имеет огромное практическое значение для обеспечения бесперебойной работы консолидированных сервисов, используемых как крупными коммерческими и государственными корпорациями, так и образовательными учреждениями.

На сегодняшний день разработанные математические модели двухуровневого управления виртуализованных ресурсов на основе виртуальных сред использованы при создании коммерческого программного продукта Virtuozzo[108], являющегося одним из наиболее популярных решений для создания виртуальных выделенных серверов. На сегодняшний день это решение обеспечивает бесперебойную работу нескольких сот тысяч виртуальных выделенных серверов в десятках стран мира, используемых для предоставления провайдерских услуг, консолидации сервисов в крупных государственных и коммерческих корпорациях, обучения в образовательных учреждениях.

Апробация и реализация результатов работы

По выполненным диссертационным исследованиям опубликовано 11 работ. В опубликованных работах автору принадлежит более 40% материала, связанного с изложением основ математической модели виртуализации ресурсов с использованием виртуальных сред.

Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на нескольких конференциях: МФТИ 2004-2005 г, Москва [96,98,110], Х-ой Всероссийской научно практической конференции, 2006 г, Анджеро-Судженск [102,100], Всероссийской научно-практической конференции, посвященной 60-летию ТОИПКРО, 2006 г. Томск [99,103,104] и др.

Также результаты докладывались и получили одобрение специалистов на научных семинарах, проводимых кафедрой информатики МФТИ.

Результаты работы реализованы при создании программного комплекса Virtuozzo[108]. В настоящее время этот программный комплекс занимает лидирующее положение в сфере предоставления услуг виртуализации операционных систем.

Положения, выносимые на защиту

На защиту выносятся следующие основные положения:

1. Математическая модель двухуровневого управления ресурсами операционных систем с закрытыми исходными кодами

2. Математическая модель и метод группового управления ресурсами центрального процессора в условиях функционирования виртуальных выделенных серверов с целью ограничения потребления времени центрального процессора сверху

Выводы по главе 3.

В главе рассматривалась модель и метод управления распределяемыми ресурсами центрального процессора.

На основе модели, рассмотренной в главе 2, была выведена наблюдаемая функция потребления процесса и приведена модель обеспечения качества обслуживания, использующая ограничение на потребление ресурса в среднем.

Далее использовался подход, принятый в теории цифровой фильтрации, для оптимизации потребления памяти, необходимой для хранения истории потребления процессом.

В результате была получена законченная модель и метод управления распределяемыми ресурсами центрального процессора

В качестве практической иллюстрации предложенных подходов была рассмотрена модель двухуровневого управления ресурсами центрального процессора, основанная на динамической балансировке базовыми приоритетами в рамках системы Windows 2003.

В рамках модели с использованием разработанного аппарата было проведено исследование влияния различных параметров на точность управления. И был осуществлен ряд практических измерений с использованием стороннего продукта Aurema. Измерения полностью подтвердили предложенную теорию.

Заключение

Таким образом, на основании вышеизложенного, можно сделать вывод, что поставленная в диссертационной работе задача решена полностью.

Разработанные автором математические модели и методы позволяют существенно упростить разработку систем управления ресурсами операционных систем в условиях виртуальных выделенных серверов.

Так же модель охватывает некоторые другие аспекты, не связанные напрямую с технологиями виртуализации, такие как, например, технологии резервного копирования данных без выключения системы с обеспечением целостности копируемых данных.

Непосредственный, личный вклад автора в работу состоит в том, что им лично решены следующие задачи:

1. Разработана математическая модель двухуровневого управления ресурсами в ОС с закрытыми исходными кодами. В рамках данной модели, объяснены существующие механизмы контроля ресурсов в современных ОС.

2. Исследованы и явно выражены ограничения, которые нужно наложить на управляемую систему, чтобы обеспечить требуемое качество управления.

3. Разработана математическая модель и метод группового управления ресурсами центрального процессора в условиях функционирования виртуальных выделенных серверов с целью ограничения потребления времени центрального процессора сверху.

4. Разработанные модели реализованы в виде комплекса программ, обеспечивающего требуемое качество обслуживания. В рамках данной модели научно обосновано поведение реального программного комплекса с экспериментальным подтверждением теоретического предсказания, выполненного на основе модели.

Разработанная модель двухуровневого управления позволяет описать наиболее распространенные алгоритмы управления ресурсами операционных систем.

Так же данная модель позволила явно выделить предположения о поведении желаемых функций потребления процессов, при которых обеспечивается надлежащее качество управления даже при отсутствии прямого контроля над собственными механизмами управления операционной системы. Полученные решения позволяют разрабатывать программные решения на основе операционных систем с закрытым или условно-закрытым исходным кодом (в последнем случае имеется в виду ситуация, когда исходный код программного продукта распространяется на особых условиях - например, только образовательным учреждениям без права коммерческого использования).

Программные решения, разработанные в рамках данной модели, широко используются в программном комплексе Virtuozzo.

Предложенная математическая модель и метод двухуровневого управления возобновляемыми ресурсами операционной системы позволяет обеспечить надлежащее качество обслуживания в системах, где непосредственный контроль над ядром операционной системы невозможен в силу различных как юридических, так и чисто технических ограничений.

В качестве дальнейших направлений работы предлагаются:

• дальнейшее совершенствование математической модели наложенного управления;

• отработка предложенных подходов для оптимизации производительности консолидированных решений на основе виртуальных выделенных серверов.

1. Almeida,J. Dabu,M. Manikutty, A. and Сао.Р. Providing differentiated quality of service in web hosting services.In WISP, June 1998.

2. 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/.

3. 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.

4. Bennett,J. and Zhang.H. WFQ: Worst-case fair weighted fair queueing. In IEEE Infocom, Mar. 1996.

5. J. Bennett , H. Zhang, Hierarchical packet fair queueing algorithms, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.675-689, Oct. 1997

6. 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

7. 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

8. Bruno,J. Brustoloni,J. Gabber, E. 6zden,B. and Silberschatz A. . Disk scheduling with quality of service guarantees. IEEE ICMCS, June 1999.

9. Candea G. M., Jones M. B. Vassal: loadable scheduler support for multi-policy scheduling. 1998

10. 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.

11. Cormen, T. Leiserson, C., Rivest, R, and Stein C. Introduction to Algorithms, Second Edition. МГГ Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 6.5: Priority queues, pp. 138-142.

12. Cromar, S. Solaris process scheduling. http://www.princeton.edu/~unix/Solaris/troubleshoot/schedule.html

13. Deianov В. Fair CPU Scheduler for Linux: Электронный ресурс. http://fairsched.sourceforge.net/doc/fairsched.txt

14. Demers,A. Keshav, S. Shenker, S ."Analysis and simulation of a fair queueing algorithm",Proceedings ofSIGCOMM '89,1989,pp. 1-12.

15. Golubchik, L. Lui, Gail, H Evaluation of tradeoffs in resource management techniques for multimedia storage servers.IEEE ICMCS, June 1999.

16. 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).

17. Iyer, S. and Druschel.P. The effect of deceptive idleness on disk schedulers. Technical Report CSTRO1-379, Rice University, June 2001.

18. S. J. Golestani, "A self-clocked fair queueing scheme for broadband applications," in Proc. IEEE INFOCOM, Toronto, Canada, June 1994, pp. 636-646.

19. 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

20. 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.

21. John L. Hennessy, David A. Patterson, Computer Architecture, A Quantitative Approach (ISBN 1-55860-724-2)

22. Huang, L. and Chiueh, T. . Implementation of a rotation latency sensitive disk scheduler. Technical Report ECSL-TR81, SUNY, Stony Brook, Mar. 2000.

23. Jacobson, D and Wilkes, J .Disk scheduling algorithms based on rotational position. Technical Report HPL-CSP-91-7revl, Hewlett-Packard, Feb. 1991.

24. 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 112122,1985.

25. Jones M. В., Regebr J. CPU reservation and time constraints: implementation experience on Windows NT. 1999

26. R. Jones and R. Lins, Garbage Collection: Algorithms for Automated Dynamic Memory Management, Wiley and Sons (1996), ISBN 0-471-94148-4

27. Goyal P., Vin H. M. Generalized Guaranteed Rate Scheduling Algorithms: A Framework. University of Texas at Austin, Austin, TX, 1995.

28. 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

29. 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.

30. 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

31. 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

32. 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.

33. 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.

34. 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.

35. Knuth, D. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0201-89683-4. Section 2.4: Dynamic Storage Allocation, pp.435-456.

36. Kopetz, H "The time-triggered model of computation". IEEE Real-time systems symposium стр168-177, дек 1998

37. 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

38. 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

39. 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.

40. 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.

41. 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

42. 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.

43. 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.

44. 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.

45. 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

46. 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.

47. Liu C.L., Layland. J. "Scheduling algorithms for multiprogramming in hard real-time environment" Journal of the ACM, 20(1):46-61,1973

48. Liu, С and Layland, J . Scheduling Algorithms for Multiprogramming in a Hard Realtime Environment. Journal of the ACM, 20(1):46~61, Jan. 1973.

49. 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. 184188. 23

50. С. 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.

51. J. Mirkovic, S. Dietrich, D. Dittrich, P. Reiher Internet Denial of Service: Attack and Defense Mechanisms. Prentice Hall, 2005

52. T. Mowry, A. Demke, and O. Krieger.Automatic compiler inserted I/O prefetching for out-of-core applications. 2nd USENIX OSDI, Oct. 1996.

53. D. Roselli, J. R. Lorch, and Т. E. Anderson.A comparison of file system workloads. USENIX Annual Technical Conference, June 2000.

54. 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.

55. C. Ruemmler and J. Wilkes. An introduction to disk drive modeling.IEEE Computer, 27(3): 17-28,1994.

56. 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/479768.html

57. H. Patterson, G. Gibson, E. Ginting, D. Stodolsky, and J. Zelenka.Informed prefetching and caching. In 15th ACM SOSP, Dec. 1995.

58. 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.

59. 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

60. Seltzer,M. Chen,P. and Ousterhout, J. . Disk scheduling revisited. USENIX Winter Technical Conference, Jan. 1990.

61. 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.

62. Shenoy, P and Vin, H. Cello: A disk scheduling framework for next generation operating systems. ACM Sigmetrics, June 1998.

63. B. A. Shirazi, A. R. Hurson, and К. M. Kavi, "Scheduling and load balancing in parallel and distributed systems," IEEE CS Press, 1995.

64. 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

65. E. Shriver, C. Small, and K. Smith. Why does file system prefetching work? USENIX Annual Technical Conference, June 1999.

66. Solomon D.A, Russinovich M.E. Inside Microsoft® Windows® 2000, Third Edition, Microsoft Press, 2000

67. 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.

68. Stewart, D, Barr, M. "Rate Monotonic Scheduling" Embedded Systems Programming, March 2002, pp. 79-80. Электронный ресурс: http://www.netrino.com/Publications/Glossary/RMA.html

69. 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

70. 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

71. 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

72. D. Sullivan and M. Seltzer. Isolation with flexibility: A resource management framework for central servers. USENIX Annual Technical Conference, June 2000.

73. F. Toutain, "Decoupled generalized processor sharing: A fair queuing principle for adaptive multimedia applications," in Proc. IEEE INFOCOM , San Francisco, CA, Mar.-Apr. 1998, pp. 291-298.

74. 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

75. 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.

76. R. Vaswani and J. Zahorjan. The implications of cache affinity on processor scheduling for shared memory multiprocessors. 13th ACM SOSP, Oct. 1991.

77. В. Verghese, A. Gupta, and M. Rosenblum. Performance isolation: Sharing and isolation in shared memory multiprocessors. ASPLOS, Oct. 1998.

78. C. Waldspurger and W. Weihl. Lottery scheduling: Flexible proportional-share resource management. In 1st USENIX OSDI, Nov. 1994.

79. C. Waldspurger and W. Weihl. Stride scheduling: Deterministic proportional resource management. Technical report, MIT/LCS/TM-528, June 1995.

80. 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

81. 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

82. Williams, P. Jun 2000 Unitied States Patent 6,758,889

83. B. Worthington, G. Ganger, and Y. Patt. Scheduling algorithms for modern disk drives.In ACM Sigmetrics, 1994.

84. J. Yao, J. Guo, and Z. Xu, "Scheduling real-time multimedia tasks in network processors," IEEE GLOBECOM, Dallas,, November 2004.

85. 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.

86. H. Zhang. Providing end-to-end performance guarantees using non-work-conserving disciplines. Computer Communications, 18(10), Oct. 1995.

87. Zhang, H Resource Management For Service-Oriented Internet. School of Computer Science, Carnegie Mellon University. http://www.cra.org/Policy/NGI/papers/zhangWP

88. H. Zhang, "Service disciplines for guaranteed performance service in packet-switching networks," Proc. IEEE, vol. 83, pp. 1374-1396, Oct. 1995.

89. Браммер К., Зиффлинг Г. Фильтр Калмана-Быоси. М.: Наука, 1982.

90. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. -М.: Наука, 1987. 336 с.

91. Емельянов, П.В. Коротаев, К.С. Луковников, И.В. Основные проблемы реализации алгоритмов пропорционального планирования// Процессы и методы обработки информации: Сб.ст/Моск. физико-техн. ин-т. М., 2006.

92. Кемени Дж., Снелл Дж. Конечные цепи Маркова: Пер. с англ. М.: Наука, 1970.

93. Леви. Л. Применение фильтров Калмана в навигационной аппаратуре,. http://www.navgeocom.ru/gps/kalman/index.htm

94. Луковников, И.В. Коротаев, К.С, Кобец А.Л Проблемы управления распределяемыми ресурсами ОС// Информационные технологии №10. М. 2006, с 71-78

95. Нуммелин Е. Общие неприводимые цепи Маркова и неотрицательные операторы. М.: Мир. - 1989. - 207с.

96. Проект Aurema Электронный ресурс. http://aurema.com

97. Проект Virtuozzo Электронный ресурс. http://virtuozzo.com

98. Феллер В. Введение в теорию вероятностей и ее приложения. Т.1. М.: Мир, 1984.

99. Хинчин А.Я. Работы по математической теории массового обслуживания. М.: Физматгиз, 1963.