Математическая модель виртуальной машины Java, автоматически адаптирующейся к особенностям выполняемого кода тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Погибельский, Дмитрий Александрович

• Погибельский, Дмитрий Александрович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Погибельский, Дмитрий Александрович

Список иллюстраций.

Список таблиц

Введение.б

Глава 1. Модель представления байт-кода Java во время выполнения программы

1.1. Применение платформонезависимого представления готовых программ

1.2. Методы трансляции программ.

1.3. Цель исследования

1.4. Структура байт-кода Java

1.5. Модель представления байт-кода во время выполнения

Глава 2. Управление памятью на низком уровне

2.1. Технологии автоматического управления памятью

2.2. Явное управление памятью.

2.3. Оценка эффективности управления динамической памятью

2.4. Теоретические оценки эффективности автоматического управления памятью.

Глава 3. Решение задачи оптимизации структуры метаданных

3.1. Постановка задачи для генетического алгоритма

3.2. Численный эксперимент

3.3. Результаты эксперимента.

3.4. Перспективы.

Введение диссертации (часть автореферата) на тему «Математическая модель виртуальной машины Java, автоматически адаптирующейся к особенностям выполняемого кода»

Актуальность работы обусловлена появлением в середине 90-х годов технологии программирования Java, что привело к бурному развитию и распространению концепции управляемого кода. На сегодняшний день эта концепция нашла свое отражение в таких технологиях как Java и Microsoft.NET. Они прочно закрепились на лидирующих позициях в вопросах разработки программного обеспечения. Изначально технология Java проектировалась как средство разработки программного обеспечения для интернета. Именно этой причиной вызвано применение высокоуровневого машиннонезависимого формата представления готовых программ. Исходный текст программы на Java компилируется в универсальный байт-код, одинаковый для всех аппаратно программных платформ. Затем этот код выполняется с помощью специальной разновидности транслятора, который также называется виртуальной машиной Java, которая сама по себе является сложным и требовательным к ресурсам системы приложением. Вопросы, связанные с опытом применения плат-формонезависимого и переносимого представления готовых программ изложены в 1.1.

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

Пока Java-приложения были относительно небольшими и выполнялись внутри интернет-браузера, это не считалось серьезным недостатком. Помимо переносимости, у технологии Java были выявлены и другие достоинства, как то безопасность, простота и удобство для разработчика, развитые концепции объектно-ориентированного программирования, которые сегодня являются основополагающими в разработке сложных программных систем [12, 13]. С помощью Java возможно быстро и качественно разрабатывать программное обеспечение для разнообразного парка устройств, в том числе и мобильных. Все эти факторы способствовали выдвижению Java в качестве универсального языка программирования, пригодного для разработки сложных информационных систем. С этого момента вопрос повышения производительности выдвинулся на первое место. В первую очередь, это возобновило интерес исследователей к теме динамической компиляции, которая на сегодняшний день является доминирующей в этой области. Этот и другие применяемые в настоящее время подходы к повышению производительности Java-приложений подробно рассмотрены в 1.2.

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

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

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

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

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

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

1. Предложить критерий оптимальности представления Java-приложения в памяти;

2. Разработать способ выделения и учета особенностей байт-кода Java;

3. Предложить конкретную методику оптимизации.

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

На сегодняшний день вопросы построения компиляторов тщательно исследованы [9, 10], однако, доминирующим направлением является изучение вопросов построения оптимального кода [15] и вопросов организации языков программирования в целом [11]. Вопросы оптимизации промежуточного представления кода и разработки интерпретаторов считаются второстепенными и рассмотрены мало.

Разработана математическая модель процесса трансляции байт-кода Java. На основе ее анализа предложен многопараметрический критерий оптимальности структуры представления метаданных Java-приложения во время его трансляции. Сформулирована задача структурной оптимизации представления метаданных Java-приложения. В отличие от других исследований в этой области [51, 54, 63], разработана математическая модель процесса трансляции байт-кода Java, абстрагированная от деталей реализации транслятора.

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

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

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

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

2. Метод эффективного решения задачи структурной оптимизации графа метаданных Java-приложения, основанный на применении аппарата генетических алгоритмов.

3. Методика управления динамической памятью, демонстрирующая наилучшие асимптотические характеристики для большинства Java-приложений в случае дефицита памяти.

Апробация работы. Материалы исследования докладывались и получили положительную оценку на научных конференциях и семинарах: II Московский научный форум, 6-я научно-практическая конференция «Московская наука, проблемы и перспективы» Москва, 13 - 17 июля 2005г.; V Международная конференция «Электроника и информатика 2005» Москва, 23 - 25 ноября 2005 г.; 13-я Всероссийская конференция «Микроэлектроника и информатика 2006», Москва, 19 - 21 апреля 2006 г.; «INTERMATIC-2006», Москва 5 - 9 декабря 2006 г., научные конференции МФТИ, Долгопрудный в 2005-2006 гг.; Семинарах кафедры прикладных информационных технологий МФТИ 2004-2007 гг.

Практическая ценность работы. Результаты исследований по построению методики оптимального управления памятью [1] и модель самоадаптации виртуальной машины Java применялись при разработке интерпретатора Java для систем цифрового телевидения в компании «Samsung Electronics». Работа проводилась в рамках стажировки в лаборатории Infra Team IP STB Lab, г. Сувон, Южная Корея, июле-августе 2006 г.

Публикации. По теме диссертации опубликовано восемь работ, в том числе две - из списка изданий, рекомендованных ВАК РФ.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Погибельский, Дмитрий Александрович

Основные результаты диссертации

1. Исследован процесс трансляции Java-приложения с точки зрения использования метаданных.

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

3. Проведено теоретическое исследование эффективности сочетания явной и автоматической методик управления динамической памятью. На основе исследования разработана гибридная методика управления динамической памятью. Разработан соответствующий программный комплекс. Эффективность методики подтверждена экспериментально.

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

СПИСОК ИСПОЛЬЗОВАННЫХ источников

1. Дъяков О. Н., Погибелъский Д. А. Организация управления динамической памятью во встраиваемых операционных системах, основанных на технологии Java // 6-я научно-практическая конференция «Московская наука, проблемы и перспективы»: Материалы конференции, - М.: МКНТ, 2005. - С. 694-702.

2. Погибелъский Д. А. Оптимизация способа хранения метаданных в интерпретаторе Java.// Оборонный комплекс научно-техническому прогрессу. - 2007 - вып.З - С. 61-65.

3. Погибелъский Д. А., Никитов С. А. Применение генетических алгоритмов для оптимизации структуры метаданных Java-приложе-ния.// Известия ВУЗов. Электроника. - 2007 - вып.5 - С. 63-68.

4. Погибелъский Д. А. Гибридный механизм управления динамической памятью в системах, основанных на технологии Java.// Электроника и информатика - 2005. V Международная научно-техническая конференция: Материалы конференции. Часть 2. - М.: МИ-ЭТ, 2005. - С. 43-44.

5. Погибелъский Д. А. Механизм автоматического управления динамической памятью в системах, основанных на технологии Java.// Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLVIII научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2005. - С. 157-158.

6. Погибелъский Д. А. Математическая модель для исследования производительности подсистемы управления памятью с помощью математического аппарата цепей Маркова.// Микроэлектроника и информатика 2006. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов.

- М.: МИЭТ, 2006. - С. 170.

7. Погибелъский Д. А. Модель самоадаптирующегося контролирующего окружения для языка программирования Java.//CoBpeMeHHbie проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLIX научной конференции. /Моск. физ. - техн. ин-т. - М.

- Долгопрудный, 2006. - С. 158-159.

8. Погибелъский Д. А. Математическая модель адаптивного контролирующего окружения для языка программирования высокого уровня.// «INTERMATIC-2006» Материалы Международной научно-технической конференции «Фундаментальные проблемы радиоэлектронного приборостроения», 5-9 декабря 2006 г., Москва. - М.: МИРЭА, 2006, часть 2. - С. 21.

9. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. - М. «Мир», 1978. - 612 с.

10. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты.: Пер. с англ. - М.:Издательский дом «Вильяме», 2003. - 768 с. ил.

11. Галочкин М.П., Гончар Д.Р., Серебряков В.А. Теория и реализация языков программирования. Учебное пособие, 2-е изд.: Издательство «МЗ-Пресс», 2006. - 352 с.

12. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного программирования. Паттерны проектирования - СПб: Питер, 2001. - 368 е.: ил. (Серия «Библиотека программиста»)

13. Грэхем И. Объектно-ориентированные методы. Принципы и практика (3-е издание) - СПб: «Вильяме», 2006. - 880 с.

14. Еремеев А. В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд. физ.-мат. наук. - Омск, 2000. - 112 с.

15. Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. - Новосибирск: Наука, 1986. - 344 с.

16. Кнут Д. Искусство программирования. Том 1. Основные алгоритмы (3-е издание).: Пер. с англ. - М.:Издательский дом «Вильяме», 2002. - 720 с.

17. Кормен Т. X., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е издание. - М.: «Вильяме», 2005. - 1296 с.

18. Седжвик Р. Фундаментальные алгоритмы на С.: Пер. с англ. -СПб: ООО «ДиаСофтЮП», 2003. - 1136 с.

19. Цой Ю. Р. Один способ вычисления времени смешивания для генетических операторов скрещивания.// Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-2006 (25-28 сентября 2006 г., Обнинск): Труды конференции. В 3-х т. Т.З. - М.: Физматлит, 2006. С. 1047-1054.

20. Adl-Tabatabai A.-R., Cierniak М., Lueh G.-Y., Parikh V. M., Stichnoth J. M. Fast, effective code generation in a just-in-time Java compiler. SIGPLAN, volume 33(6), Monthreal, ACM 1998. P. 280-290.

21. Appel A. Garbage collection. // Lee P. editor: Topics in Advanced Language Implementation, MIT Press, Cambridge, Massachusets, 1991. P. 89-100.

22. Arnold K., Gosling J. The Java Programming Language. - Addison-Wesley, 1996.

23. Baker H. G., Jr. The Treadmill: Realtime garbage collection without motion sickness. In OOPSLA '91 Workshop on Garbage Collection in Object-Oriented Systems [69].

24. Bala V., Duesterwald E., Banerja S. Transparent dynamic optimization. Technical Report HPL-1999-77, Hewlet-Packard, 1999

25. Bartlet J. F. Compacting garbage collection with ambiguous roots. - Technical Report 88/2, Digital Equipment Corporation Western Research Laboratory, Paolo Alto, California, February 1988.

26. Bekkers Y., Cohen J. International Workshop on Memory Management, number 637 in Lecture Notes in Computer Science, St. Malo, France, September 1992, Springer-Verlag.

27. Blunden В. Memory management: algorithms and implementation in C/C++. -Piano, TX: Worldware Publishing Inc. 2002. - 360 p.

28. Boehm H.-J., Bemers A. J., Shenker S. Mostly parallel garbage collection. In Proceedings of the 1991 SSIGPLAN Conference on Programming Language Besign and Implementation [71]. P. 157-164.

29. Boehm H.-J., Weiser M. Garbage collection in an uncooperative environment. - Software Practice and Experience, 18(9):807-820, September 1988.

30. Cardeli L. et al. Modula-3 Report (revised). Research Report 52, Digital Equipment Corporation Systems Research Center, 1989.

31. Caudill P., Wirfs-Brock A. A third-generation Smalltalk-80 implementation.// In Conference OOPSLA '86 proceedings, P. 119-130, ACM Press, October 1986.

32. Chen W.-K., Lerner S., Chaiken R., Gillies В. M. Mojo: A dynamic optimization system.// In Third ACM Workshop on Feedback-directed and Dynamic Optimization (FDDO-3), 2000.

33. Clarck B. Measurements of dynamic list structure use in Lisp. // IEEE Transactions of Software Enginering, vol. 5 (1) 1979. P. 51-59.

34. Clarck В., Green C. An empirical study of list structure in LISP. // Communications of the ACM, vol. 20 (3), 1977. P. 78-87.

35. Clausen L. R. Java bytecode compression for low-end embedded systems. ACM Transactions on Programming Languages and Systems, Vol. 22, No. 3, May 2000, P. 471-489.

36. Cmelik В., Keppel D. Shade: A fast instruction-set simulator for execution profiling. In Proc. 1994 Conference of Measurement and Modeling of Computer Systems. P. 128-137.

37. Cohen J. Garbage collection of linked data structures. // Computing Surveys, vol 13 (3), 1981. P. 341-367.

38. Collins G. E. A method for overlapping and erasure of lists. // Communications of the ACM, vol. 2 (12), 1960. P. 655.

39. Cohen J., Nicolau A. Comparison of compacting algorithms for garbage collection. // ACM Transactions on Programming Languages and Systems, vol. 5 (4), 1983. P. 532-553.

40. Cramer Т., Friedman R., Miller Т., Seberger D., Wilson R., Wolczko M. Compiling Java just in time. // IEEE Micro 17, 3, 1997. P. 36-43.

41. Dakin R. J., Poole P. C. A mixed code approach. // The Computer Journal 16, 3, 1973. P. 219-222.

42. Dawson J. L. Combining interpretive code with machine code. // The Computer Journal 16, 3, 1973. P. 216-219.

43. Deaver D., Gorton R., Rubin N. Wiggins/Redstone: An ol-line program specialize^// In Proc. IEEE Hot Chips XI Conference, August 1999.

44. Delacour V. Allocation regions and implementation contracts. In [26], P. 426-439.

45. Deutsch L. P., Schiffman A. M. Efficient Implementation of the

Smalltalk-80 System, 11th Annual Symposium on Principles of Programming Languages, Jan 1984, P. 297-302.

46. Dieckmann S., Holzle U. A Study of the Allocation Behavior of the SPECjvm98 Java Benchmarks. - Technical Report: TRCS98-33, Year of Publication: 1998, University of California, Santa Barbara, CA, USA.

47. Ebicoglu K., Altman E., Hokenek E. A Java ILP machine based on fast dynamic compilation.// In MASCOTS'97 - International Workshop on Security and Efficiency Aspects of Java, 1997.

48. Ebicioglu K., Altman E. R. Daisy: Dynamic compilation for 100% architectural compatibility. //In ISCA£)7, 1997, P. 26-37.

49. Ellis J., Detlefs D. Safe, efficient garbage collection for С++. Technical Report 102, Digital Equipment Corporation Systems Research Center, 1993.

50. Eliot J., Moss B. Addressing large distributed collections of persistent objects: The Mneme project's approach. In Second International Workshop on Database Programming Languages, Glenedon Beach, Oregon, June 1989. P. 269-285.

51. Ertl M. A. Implementation of Stack-Based Languages on Register Machines.: PhD thesis - Technische Universitat Wien, April 1996.

52. Ertl M. A., Maierhofer M. Translating Forth to efficient C. // In EuroForth'95, 1995.

53. Ertl M. A., Pirker С. The structure of a Forth native code compiler. // EuroForth'97 Conference Proceedings, 1997. P. 107-116.

54. Gagnon E. A portable research framework for the execution of Java bytecode.: Ph.D. Thesis. - School of Computer Science McGill University, Montreal 2002.

55. Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. - Reading. MA: Addison-Wesley. 1989.

56. Gschwind M., Altman E. R., Sathaye S., Ledak P., Appenzeller D. Dynamic and transparent binary translation. // IEEE Computer 33, 3, 2000. P. 54-59.

57. Hayes B. Using key objects opportunism to collect old objects. // OOPSLA'91. 1991. P. 33-46.

58. Holland J.H. Adaptation in Natural and Artificial Systems. - The University of Michigan Press, 1975.

59. Jones R., bins R. Garbage collection: algorithms for automatic dynamic memory management. - Chichester: John Wiley к Sons, 1996. - 379 p.

60. De Jong K.A., Spears W.M. A formal analysis of the role of multi-point crossover in genetic algorithms - Annals of Mathematics and Artificial Intelligence. 1992. 5(1). P. 1-26.

61. Kim J.-S., Hsu Y. Memory system behavior of Java programs: methodology and analysis. // Proc. International conference on measurements and modeling of computer systems, 2000. P. 264-274.

62. Knuth В. E. An empirical study of Fortran programs. Software // Practice and Experience 1, 1971. P. 105-133.

63. Krall A. Efficient JavaVM just-in-time compilation.// In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, 1998, P. 54-61.

64. Lang В., Dupont F. Incremental incrementally compacting garbage collection.// In SIGPLAN 1987 Symposium on Interpreters and Interpretive Techniques, P. 253-263. Saint Paul, Minnesota, June 1987.

65. Lindholm Т., Yellin F. The Java virtual Machine Specification. -Addison-Wesley, 1999. 437 p.

66. McBeth H. J. On the reference counter method. // Communications of the ACM, vol. 6 (9), 1963. P. 575.

67. McCarthy J. Recursive functions of symbolic expressions and their computation by machine. // Communications of the ACM, vol. 3 (4), 1960. P. 184-195.

68. Meyrowitz N. editor, OOPSLA '88 Proceedings, San Diego, California, September 1988. ACM Press, November 1988.

69. OOPSLA '91 Workshop on Garbage Collection in Object-Oriented Systems, October 1991. Доступен с анонимного ftp sc.utexas.edu in / pub / garbage/GC91.

70. Pemberton S., Baniels M. C. Pascal Implementation, The P4 Compiler. - Ellis Horwood: Prentice Hall, 1982. - 376 P.

71. Proceedings of the 1991 SSIGPLAN Conference on Programming Language Design and Implementation, Toronto, Ontario, June 1991. ACM Press. SIGPLAN Notices 26(6), June 1992.

72. Prugel-Bennett A. The mixing rate of different crossover operators // Foundations of Genetic Algorithms 6. 2001. P. 261-274.

73. Quing Li Real-Time concepts for embedded systems. - San Francisco: CMP Books, 2003.

74. Robson J. M. An estimate of the store size necessary for dynamic storage allocation. - Journal of the ACM, 1971, vol. 18(3). P. 416-423.

75. Schoeberl M. JOP: A Java Optimized Processor for Embedded RealTime Systems.: Ph.D. thesis. - Vienna University of Technology, 2005.

76. Steel Т. B. A First Version Of UNCOL.// In Proceedings of the Western-Joint IRE-AIEE-ACM Computer Conference, 1961, P. 371-377.

77. Sun Microsystems. The Java HotSpot virtual machine. White paper, 2001.

78. Тута P. Why are we using Java again? // Commun. ACM 41, 6,1998. P. 38-42.

79. Ungar В., Jackson F. Tenuring policies for generation-based storage reclamation. In [68], P. 1-17.

80. Wang T. MM garbage collector for С++.: Master's thesis. - California Polytechnic State University, San Luis Obispo, California, October 1989.

81. Wilson P. R. Dynamic storage allocation: A survey and critical review. // International Workshop on Memory Management. Kinross, Scotland, UK, 1995. P. 1.

82. Wilson P. R. Uniprocessor Garbage Collection Techniques. //In Proc of International Workshop on Memory Management in the Springer-Verlag Lecture Notes in Computer Science series., St. Malo, France, September 1992.

83. Zheng C., Thompson C. PA-RISC to IA-64: Transparent execution, no recompilation. // IEEE Computer 33, 3, 2000. P. 47-52.

84. Zorn B. The measured cost of conservative garbage collection. // Software - Practice and Experience, vol. 23 (7), 1993. P. 733-756.

Заключение

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

Были изучены технологии платформонезависимого представления программ и основные методики их трансляции. В отличие от большинства исследований в данной области, основное внимание сосредоточено на предварительной стадии трансляции - загрузке байт-кода приложения в память. Изучены необходимые для выполнения приложения данные и их взаимосвязи. Разработана расширяемая математическая модель, описывающая эти взаимосвязи и процесс использования данных во время трансляции байт-кода. Модель опирается на терминологию теории анализа алгоритмов и широко использует ее методы. Модель одинаково хорошо согласуется с обоими способами трансляции: как интерпретацией, так и динамической компиляцией и остается согласованной в широком диапазоне детализации и характерных значений параметров процесса.

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Погибельский, Дмитрий Александрович, 2007 год

1. Дьяков о. Н., Погибелъский Д. А. Организация управления динамической памятью во встраиваемых операционных системах, основанных на технологии Java 6-я научно-практическая конференция «Московская наука, проблемы и перспективы»: Материалы конференции, М.: МКНТ, 2005. 694-702.

2. Погибелъский Д. А. Оптимизация способа хранения метаданных в интерпретаторе Java.// Оборонный комплекс научно-техническому прогрессу. 2007 вып.З 61-65.

3. Погибелъский Д. А., Никитов А. Применение генетических алгоритмов для оптимизации структуры метаданных Java-приложения.// Известия ВУЗов. Электроника. 2007 вып.5 63-68.

4. Погибелъский Д. А. Гибридный механизм управления динамической памятью в системах, основанных на технологии Java.// Электроника и информатика 2005. V Международная научно-техническая конференция: Материалы конференции. Часть 2. М.: МИЭТ, 2005. 43-44.

5. Погибелъский Д. А. Механизм автоматического управления динамической памятью в системах, основанных на технологии Java.// Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLVIII научной конференции. /Моск. физ. техн. ин-т. М. Долгопрудный, 2005. 157-158.

6. Погибелъский Д. тролирующего А. Модель для самоадаптирующегося языка кон- окружения нрограммирования и приклад- Java.//CoBpeMeHHbie проблемы фундаментальных ных наук. Часть VII. Управление и прикладная математика: Труды XLIX научной конференции. /Моск. физ. техн. ин-т. М. Долгопрудный, 2006. 158-159.

7. Гамма Э., Хелм Р., Дотонсон Р., Влиссидес Дою. Приемы объектно-ориентированного программирования. Паттерны проектирования СПб: Питер, 2001. 368 с ил. (Серия «Библиотека программиста»)

8. Грэхем И. Объектно-ориентированные методы. Принципы и практика (3-е издание) СПб: «Вильяме», 2006. 880 с.

9. Еремеев А. В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд. физ.-мат. наук. Омск, 2000. 112 с.

10. Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. Новосибирск: Наука, 1986. 344 с.

11. Кнут Д. Искусство программирования. Том

12. Основные алгоритмы (3-е издание).: Пер. с англ. М.:Издательский дом «Вильяме», 2002. 720 с.

13. Кормен Т. X., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: «Вильяме», 2005. 1296 с.

14. Седлсвик Р. Фундаментальные алгоритмы на С Пер. с англ. СПб: 0 0 0 «ДиаСофтЮП», 2003. 1136 с. 92

15. Appel A. Garbage collection. Lee P. editor: Topics in Advanced Language Implementation, MIT Press, Cambridge, Massachusets, 1991. P. 89-100.

16. Arnold K., Gosling J. The Java Programming Language. AddisonWesley, 1996.

17. Baker H. G., Jr. The Treadmill: Realtime garbage collection without motion sickness. In OOPSLA 91 Workshop on Garbage Gollection in Object-Oriented Systems [69].

18. Bala Y., Duesterwald E., Banerja S. Transparent dynamic optimization. Technical Report HPL-1999-77, Hewlet-Pacbrd, 1999

19. Bartlet J. F. Compacting garbage collection with ambiguous roots. Technical Report 88/2, Digital Equipment Corporation Western Research Laborotory, Paolo Alto, California, February 1988.

20. Bekkers Y., Cohen J. International Workshop on Memory Management, number 637 in Lecture Notes in Computer Science, St. Malo, France, September 1992, Springer-Verlag. 93

21. Boehm H.-J., Demers A. J., Shenker S. Mostly parallel garbage collection. In Proceedings of the 1991 SSIGPLAN Conference on Programming Language Design and Implementation [71]. P. 157-164.

22. Boehm H.-J., Weiser M. Carbage collection in an uncooperative environment. Software Practice and Experience, 18(9):807-820, September 1988.

23. Cardeli L. et al. Modula-3 Report (revised). Research Report 52, Digital Equipment Corporation Systems Research Center, 1989.

24. Caudill P., Wirfs-Brock A. A third-generation Smalltalk-80 implementation.// In Conference OOPSLA 86 proceedings, P. 119-130, ACM Press, October 1986.

25. Chen W.-K., Lerner 5., Chaiken R., Cillies D. M. Mojo: A dynamic optimization system.// In Third ACM Workshop on Feedback-directed and Dynamic Optimization (FDDO-3), 2000.

26. Clarck D. Measurements of dynamic list structure use in Lisp. IEEE Transactions of Software Enginering, vol. 5 (1) 1979. P. 51-59.

27. Clarck D., Creen C. An empirical study of list structure in LISP. Communications of the ACM, vol. 20 (3), 1977. P. 78-87.

28. Clausen L. R. Java bytecode compression for low-end embedded systems. ACM Transactions on Programming Languages and Systems, Vol. 22, No. 3, May 2000, P. 471-489. 94

29. Dieckmann S., Holzle U. A Study of the Allocation Behavior of the SPECjvm98 Java Benchmarks. Technical Report: TRCS98-33, Year of Publication: 1998, University of California, Santa Barbara, CA, USA.

30. Ebicoglu K., Altman E., Hokenek E. A Java ILP machine based on fast dynamic compilation.// In MASCOTS97 International Workshop on Security and Efficiency Aspects of Java, 1997.

31. Ebicioglu K., Altman E. R. Daisy: Dynamic compilation for 100% architectural compatibility. In ISCA7, 1997, P. 26-37.

32. Ellis J., Detlefs D. Safe, efficient garbage collection for C+4-. Technical Report 102, Digital Equipment Corporation Systems Research Center, 1993.

33. Eliot J., Moss B. Addressing large distributed collections of persistent objects: The Mneme projects approach. In Second International Workshop on Database Programming Languages, Glenedon Beach, Oregon, June 1989. P. 269-285.

34. Ertl M. A. Implementation of Stack-Based Languages on Register Machines.: PhD thesis Technische Universita,t Wien, April 1996.

35. Ertl M. A., Maierhofer M. Translating Forth to efficient C. In EuroForth95, 1995. 96

36. Gagnon E. A portable research framework for the execution of Java bytecode.: Ph.D. Thesis. School of Computer Science McGill University, Montreal 2002.

37. Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. Reading. MA: Addison-Wesley. 1989.

38. Gschwind M., Altman E. R., Sathaye S., Ledak P., Appenzeller D. Dynamic and transparent binary translation. IEEE Computer 33, 3, 2000. P. 54-59.

39. Hayes B. Using key objects opportunism to collect old objects. 00PSLA91. 1991. P. 33-46.

40. Holland J.H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975.

41. Krall A. Efficient JavaVM just-in-time compilation.// In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, 1998, P. 54-61.

42. Lang В., Dupont F. Incremental incrementally compacting garbage collection.// In SIGPLAN 1987 Symposium on Interpreters and Interpretive Techniques, P. 253-

44. Lindholm Т., Yellin F. The Java virtual Machine Specification. Addison-Wesley, 1999. 437 p. 66. McBeth H. J. On the reference counter method. Communications of the ACM, vol. 6 (9), 1963. P. 575. 67. McCarthy J. Recursive functions of symbolic expressions and their computation by machine. Communications of the ACM, vol. 3 (4), 1960. P. 184-195.

45. Meyrowitz N. editor, OOPSLA 88 Proceedings, San Diego, California, September 1988. ACM Press, November 1988. 69. OOPSLA 91 Workshop on Garbage Collection in Object-Oriented Systems, October 1

46. Доступен с анонимного ftp sc.utexas.edu in /pub/garbage/GC91.

47. Pemberton S., Daniels M. C. Pascal Implementation, The P4 Compiler. Ellis Horwood: Prentice Hall, 1982. 376 P. 98

48. Prugel-Bennett A. The mixing rate of different crossover operators Foundations of Genetic Algorithms 6. 2001. P. 261-274.

49. Quing Li Real-Time concepts for embedded systems. San Francisco: CMP Books, 2003.

50. Robson J. M. An estimate of the store size necessary for dynamic storage allocation. Journal of the ACM, 1971, vol. 18(3). P. 416-423.

51. Schoeberl M. JOP: A Java Optimized Processor for Embedded RealTime Systems.: Ph.D. thesis. Vienna University of Technology, 2005.

52. Steel T. B. A First Version Of UNCOL.// In Proceedings of the Western-Joint IRE-AIEE-ACM Computer Conference, 1961, P. 371-377. 77. Sun Microsystems. The Java HotSpot virtual machine. White paper, 2001.

53. Тута P. Why are we using Java again? Commun. ACM 41, 6,1998. P. 38-42.

54. Ungar D., Jackson F. Tenuring policies for generation-based storage reclamation. In [68], P. 1-17.

55. Wang T. MM garbage collector for С-Ь-f-.: Masters thesis. California Polytechnic State University, San Luis Obispo, California, October 1989. 99

56. Wilson P. R. Uniprocessor Garbage Collection Techniques. In Proc of International Workshop on Memory Management in the SpringerVerlag Lecture Notes in Computer Science series., St. Malo, France, September 1992.

57. Zheng C, Thompson C. PA-RISC to IA-64: Transparent execution, no recompilation. IEEE Computer 33, 3, 2000. P. 47-52.

58. Zorn B. The measured cost of conservative garbage collection. Software Practice and Experience, vol. 23 (7), 1993. P. 733-756. 100