Математическая модель планирования групп процессов с гарантированным качеством обслуживания
Диссертация
Предложена математическая модель пропорционального планирования групп процессов, позволяющая управлять распределением процессорного времени. Данная модель гарантирует выделение указанной доли времени группе процессов и включает математические оценки точности и задержки в обслуживании, что позволяет использовать эту модель в системах с гарантированным качеством обслуживания. В дополнение… Читать ещё >
Список литературы
- Andrzejak A., Martin A., Jerry R. Bounding the Resource Savings of Utility Computing Models: Technical Report HPL-2002−339: HP Labs, 2002.
- Price D., Tucker A. Solaris zones: Operating system support for consolidating commercial workloads // Proceedings of the USENIX 18th Large Installation System Administration Conference (LISA'04). 2004.
- Tucker A., Comay D. Solaris zones: Operating system support for server consolidation // Proceedings of the USENIX Third Virtual Machine Research & Technology Symposium (VM'04). 2004.
- Increasing the Load: Virtualization Moves Beyond Proof of Concept in the Volume Server Market, According to IDC: IDC Press Release: 18 Oct 2005.
- Bittman T. Predicts 2004: Server Virtualization Evolves Rapidly: SPA-21−5502: Gartner Research, 2003.6. 2006 technology of the year awards. — Режим доступа: http://www.infoworld.com/reports/0lSRtoy06.html, свободный. — Загл. с экрана. — Яз. англ.
- Intel. vanderpool technology. — Режим доступа: http://www.intel.com/technology/computing/vptech/, свободный. — Загл. с экрана. — Яз. англ.
- Diagnosing Performance Overheads in the Xen Virtual Machine Environment / A. Menon, J. R. Santos, Y. Turner et al. // First ACM/USENIX Conference on Virtual Execution Environments (VEE'05). 2005. — Pp. 13−23.
- Fedora Core Project Электронный ресурс. / RedHat company, [2006]. — Режим доступа: http://www.redhat.com/fedora/, свободный. — Загл. с экрана. — Яз. англ.
- SUSE Linux Электронный ресурс. / Novell company, [2006]. — Режим доступа: http://www.novell.com/linux/, свободный. — Загл. с экрана. — Яз. англ.
- И. XenSource: Delivering the power of Хеп Электронный ресурс. / Cambridge University, [2006]. — Режим доступа: http://www.xensource.com/, свободный. — Загл. с экрана. — Яз. англ.
- Хеп and the art of virtualization / В. Dragovic, К. Fraser, S. Hand et al. // Proceedings of the ACM Symposium on Operating Systems Principles. 2003. — Pp. 164−177.
- Емельянов П., Савочкин А. Расширение функциональности существующей модели контроля памяти в ядре linux // Процессы и методы обработки информации: Сб.ст. — М.: Моск. физ.-техн. ин-т, 2005.- С. 77−80.
- CKRM linux open source project, class based kernel resource management Электронный ресурс. / IBM, [2006]. — Режим доступа: http://ckrm.sourceforge.net/, свободный. — Загл. с экрана. — Яз. англ. N
- Improving Linux resource control using CKRM / S. Nagar, R. van Riel, H. Franke et al. // Proceedings of the Ottawa Linux Symposium. Vol. 2. — 2004. — Pp. 511−524.
- Banga G., Druschel P., Mogul J. Resource containers: A new facility for resource management in server systems // Proceedings of the USENIX Symposium on Operating System Design and Implementation (OSDI). 1999. — Pp. 45−48.
- Kay J., Lauder P. A Fair Share Scheduler // Communications of the ACM. 1988. — no. 31(1). — Pp. 44−55.
- Chan W. C., Nieh J. Group Ratio Round-Robin: An 0(1) Proportional Share Scheduler // Proceedings of the 2005 USENIX Annual Technical Conference. 2005. — Pp. 337−352.
- Nieh J., Vaill C., Zhong H. Virtual-Time Round-Robin: An 0(1) Proportional Share Scheduler // In Proceedings of the 2001 USENIX Annual Technical Conference. 2001. — Pp. 245−259.
- Bavier A. The Tyche CPU Scheduler: Phd thesis / Princeton University. — Nov. 2004.
- Klamann R. Opportunity scheduling: An unfair CPU scheduler for UNICOS // Proceedings of Cray User Group (CUG).- 1997.-Pp. 57−64.
- Jones M. В., Rosu D., Rosu M.-C. CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities // Symposium on Operating Systems Principles.— 1997.-Pp. 198−211.
- A proportionate fair scheduling rule with good worst-case performance / M. Adler, P. Berenbrink, T. Friedetzky et al. //
- Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures. — 2003. — Pp. 101−108.
- Протасов С., Белоусов С., Тормасов А. Прошлое, настоящее и будущее: развитие архитектуры и принципов создания операционных систем // «Объединенный научный журнал». — 2004.— № 24(116).- С. 83−86.
- OpenVZ Server Virtualization Open Source Project Электронный ресурс. / [2006]. — Режим доступа: http://openvz.org/, свободный. — Загл. с экрана. — Яз. англ.
- VMware virtualization software Электронный ресурс. / EMC Company, [2006]. — Режим доступа: http://vmware.com, платный. — Загл. с экрана. — Яз. англ.
- Microsoft Virtual PC virtualization Электронный ресурс. / Microsoft corporation, [2006]. — Режим доступа: http://www.microsoft.com/windows/virtualpc, платный. — Загл. с экрана. — Яз. англ.
- Multiprocessor Specification Электронный ресурс. / Intel, [2006]. — Режим доступа: http://www.intel.com/design/archives/processors/pro/docs/242 016.htm, свободный. — Загл. с экрана. — Яз. англ.
- Lawton К. The Cross Platform IA-32 Emulator Электронный ресурс. / Open Source project, [2006]. — Режим доступа: http://bochs.sourceforge.net/, свободный. — Загл. с экрана. — Яз. англ.
- Bellard F. Qemu: open source processor emulator Электронный ресурс. / Open Source project, [2006]. — Режим доступа: http://www.qemu.com/, свободный. — Загл. с экрана. — Яз. англ.
- McEwan W. Virtual machine technology and their application in the delivery of ICT.
- Waldspurger C. Memory resource management in VMware ESX Server // Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI '02). 2002.
- Virtuozzo: server virtualization, consolidation and management Электронный ресурс. / SWsoft Inc., [2006]. — Режим доступа: http://virtuozzo.com/, свободный. — Загл. с экрана. — Яз. англ.
- Linux-Vserver project Электронный ресурс. / Herbert Poetzl, [2006]. — Режим доступа: http://linux-vserver.org/, свободный. — Загл. с экрана. — Яз. англ.
- Virtualization of linux based computers: the linux-VServer project // Proceedings of 19th International Symposium on High Performance Computing Systems and Applications. — May 2005. — Pp. 340−346.
- Solaris containers Электронный ресурс. / Sun microsystems, [2006]. — Режим доступа: http://www.opensolaris.org/os/community/zones/, свободный. — Загл. с экрана. — Яз. англ.
- HP-UX lli virtual partitions Электронный ресурс. / Hewlett Packard, [2006]. — Режим доступа: http://h20338.www2.hp.com/hpuxlli/cache/323 722−0-0−0-121.html, свободный. — Загл. с экрана. — Яз. англ.
- Diagnosing Performance Overheads in the Xen Virtual Machine Environment: Technical Report HPL-2005−80 / A. Menon, J. R. Santos, Y. Turner et al.: HP Labs, 2005.
- Cherkasova L., Gardner R. Measuring CPU Overhead for I/O Processing in the Xen Virtual Machine Monitor: Technical Report HPL-2005−62: HP Labs, 2005.
- Petrou D., Milford J. W., Gibson G. A. Implementing Lottery Scheduling: Matching the Specializations in Traditional Schedulers // Proceedings of the USENIX 1999 Annual Technical Conference. 1999. — Pp. 1−14.
- Golestani S. J. A Self-Clocked Fair Queueing Scheme for Broadband Applications. // Proceedings of IEEE INFOCOM'94. -Jun 1994.-Pp. 636−646.
- Емельянов П., Коротаев К., Луковников И. Основные проблемы реализации алгоритмов пропорционального планирования // Процессы и методы обработки информации: Сб.ст. — М.: Моск. физ.-техн. ин-т, 2006. С. 86−91.
- Etsion Y., Tsafrir D., Feitelson D. G. Desktop scheduling: how can we know what the user wants? // Proceedings of the 14th international workshop on Network and operating systems support for digital audio and video. — 2004. — Pp. 110−115.
- Liu С., Layland J. Scheduling algorithms for multiprogramming in a hard real-time environment // Journal of the ACM. — Jan 1973. no. 1(20). — Pp. 46−61.
- Serlin O. Scheduling of Time Critical Processes // Proceedings of the 1972 AFIPS Spring Joint Computer Conference. Vol. 40. -1972.
- Lehoczky J., Sha L., Ding Y. The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior // Proceedings of the 10th IEEE Real-Time Systems Symposium (RTSS '89). Dec 1989. — Pp. 166−171.
- Zhang Y., Sivasubramaniam A. Scheduling best-effort and realtime pipelined applications on time-shared clusters // Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures. 2001. — Pp. 209−219.
- Multimedia Applications Require Adaptive CPU Scheduling / V. Baiceanu, C. Cowan, D. McNamee et al. // Proceedings of the Workshop on Resource Allocation Problems in Multimedia Systems. Dec 1996.
- Biyabani S., Ramamritham K., Stankovic J. The Integration of Deadline and Criticalness in Hard Real-Time Scheduling // Proceedings of the 9th IEEE Real-Time Systems Symposium (RTSS '88). Dec 1988. — Pp. 152−160.
- The design and implementation of an operating system to support distributed multimedia applications / I. Leslie, D. McAuley, R. Black et al. // IEEE Journal on Selected Areas in Communications. Sept. 1996. — no. 14(7). — Pp. 1280−1297.
- Chandra A., Adler M., Shenoy P. Deadline fair scheduling: Bridging the theory and practice of proportionate-fair schedulingin multiprocessor servers // In Proceedings of the 7th IEEE RealTime Technology and Applications Symposium. — 2001.— Pp. 314.
- Link-sharing and Resource Management Models for Packet Networks // IEEE/ACM Transactions on Networking. — Aug 1995. Vol. 3, no. 4. — Pp. 365−386.
- A Simulation Study of Fair Queueing and Policy Enforcement // ACM Computer Communication Review. — Oct 1990. — Vol. 20, no. 5. Pp. 23−29.
- Bennett J. C. R., Zhang H. Hierarchical packet fair queueing algorithms // IEEE/ACM Transactions on Networking. — 1997. — Vol. 5, no. 5. Pp. 675−689.
- Goyal P., Vin H. M., Cheng H. Start-Time Fair Queuing: A Scheduling Algorithm for Integrated Services Packet Switching Networks // Proceedings of ACM SIGCOMM'96.- 1996. — Pp. 157−168.
- Analysis and Simulation of a Fair Queueing Algorithm // Proceedings of the ACM SIGCOMM '89. 1989. — Pp. 1−12.
- Greenberg A., Madras N. How Fair is Fair Queuing // The Journal of ACM. July 1992. — Vol. 39(3). — Pp. 568−598.
- Adaptive reservations in a linux environment / L. Abeni, T. Cucinotta, G. Lipari et al. // Proceedings of the 10th IEEE RealTime and Embedded Technology and Applications Symposium (RTAS'04).- 2004.- P. 238.
- Waldspurger C. A., Weihl W. E. Lottery scheduling: Flexible proportional-share resource management // Proceedings of the First USENIX Symposium on Operating System Design and Implementation (OSDI). Nov. 1994. — Pp. 1−11.
- Waldspurger С. A., Weihl W. E. Stride Scheduling: Deterministic Proportional-Share Resource Management: Tech. Rep. MIT/LCS/TM-528: 1995.
- Duda K. J., Cheriton D. R. Borrowed-virtual-time (BVT) scheduling: Supporting latency-sensitive threads in a general-purpose scheduler // Proceedings of the 17th ACM Symposium on Operating Systems Principles (SOSP). Dec 1999. — Pp. 261−276.
- Goyal P., Guo X., Vin H. A Hierarchical CPU Scheduler for Multimedia Operating Systems // Proceedings of the Second USENIX Symposium on Operating System Design and Implementation (OSDI).- 1996.-Pp. 107−122.
- Nieh J., Lam M. The Design, Implementation and Evaluation of SMART: A Scheduler for Multimedia Applications // Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP). Oct 1997. — Pp. 184−197.
- Waldspurger C. Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management: PhD thesis / Massachusetts Institute of Technology. — Sept. 1995.
- Stoica I., Abdel-Wahab H., Jey K. On the duality between resource reservation and proportional share resource allocation // Proceedings of Multimedia Computing and Networking 1997 (MMCN97). Feb. 1997. — Pp. 207−214.
- A proportional share resource allocation algorithm for real-time time-shared systems / I. Stoica, H. Abdel-Wahab, K. Jey et al. // Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96). Dec. 1996. — Pp. 288−299.
- Zhang L. Virtual clock: A new traffic control algorithm for packet switching // ACM Transactions on Computer Systems.— May 1991. no. 9(2). — Pp. 101−124.
- Gunther N. J. Solaris System Resource Manager: All I Ever Wanted Was My Unfair Advantage (And Why You Can’t Have It!) // Proceedings of CMG'99 Conference. 2000. — Pp. 194−205.
- Newhouse Т., Pasquale J. ALPS: An Application-Level Proportional-Share Scheduler // Proceeedings of the 15th IEEE International Symposium on High Performance Distributed Computing (HPDC). 2006. — Pp. 45−57.
- Tanenbaum A. Modern Operating Systems, 2nd edition. — Prentice Hall, 2001.
- Aas J. Understanding the linux 2.6.8.1 CPU scheduler.- 2005. http://josh.trancesoftware.com/linux/linuxcpuscheduler.pdf.
- Love R. Linux Kernel Development. — Novell Press, 2005. — Chapter 04: Process Scheduling.
- A Linux Implementation of a Differentiated Services Router / T. Braun, H. J. Einsiedler, M. Scheidegger et al. // Networks and Services for the Information Society: 5th IFIP TC6 International Symposium, INTERWORKING 2000, 2000. — Pp. 302−315.
- Kolyshkin K., Korotaev K. OpenVZ Project OS Server Virtualization // Proceedings of the LinuxTag conference. — 2006. http://www.linuxtag.org/2006/de/besucher/material.html.
- Korotaev K. Hierarchical CPU Schedulers for Multiprocessor Systems, Fair CPU scheduling and Processes Isolation // Proceedings of Cluster'05. Boston: 2005. — Pp. 53−54.
- Ford В., Susarla S. CPU Inheritance Scheduling // Usenix Association Second Symposium on Operating Systems Design and Implementation (OSDI). 1996. — Pp. 91−105.
- Duda K. J., Cheriton D. R. Borrowed virtual-time (BVT) scheduling. — 2000. http://www.dsg.standford.edu/pub/bvt.html.
- Application performance in the QLinux multimedia operating system / V. Sundaram, A. Chandra, P. Goyal et al. // Proceedings of 8th ACM Conference on Multimedia. 2000. — Pp. 127−136.
- Коротаев К., Савочкин А. Концепция виртуальных процессоров для планировщика задач, реализующего изоляцию групп процессов // Процессы и методы обработки информации: Сб.ст. — М.: Моск. физ.-техн. ин-т, 2005. С. 81−87.
- Enforcing Performance Isolation Across Virtual Machines in Xen: Technical Report HPL-2006−77 / D. Gupta, L. Cherkasova, R. Gardner, A. Vahdat: HP Labs, 2006.
- Regehr J. Using Hierarchical Scheduling to Support Soft Real-Time Applications on General-Purpose Operating Systems: PhD thesis / University of Virginia. — 2001.
- Devine S. W., Bugnion E., Rosenblum M. US patent #6,397,242: Virtualization system including a virtual machine monitor for a computer with a segmented architecture. — May 28, 2002.
- Bulpin J. R., Pratt I. A. Hyper-Threading Aware Process Scheduling Heuristics // Proceedings on the 2005 USENIX Annual Technical Conference. 2005. — Pp. 103−106.
- Siddha S. Chip Multi Processing aware Linux Kernel Scheduler // Proceedings on the 2005 Linux Symposium. 2005. — Pp. 337−347.
- Nakajima J., Pallipadi V. Enhancements for Hyper-Threading technology in the operating system. Seeking the optimal scheduling //In Proceedings of the 2nd Workshop on Industrial Experiences with Systems Software. — 2002. — Pp. 25−38.
- Squillante M. S., Lazowska E. D. Using Processor-Cache Affinity Information in Shared-Memory Multiprocessor Scheduling // IEEE Transactions on Parallel and Distributed Systems. — Feb 1993. — Vol. 4, no. 2.- Pp. 131−144.
- Коротаев К., Емельянов П. Многоуровневый планировщик процессорного времени для групп процессов, обеспечивающий гарантии в обслуживании // Информационные технологии. — М.2006.-№ 6.-С. 58−63.