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

На правах рукописи

Погибельский Дмитрий Александрович

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ВИРТУАЛЬНОЙ МАШИНЫ JAVA, АВТОМАТИЧЕСКИ АДАПТИРУЮЩЕЙСЯ К ОСОБЕННОСТЯМ ВЫПОЛНЯЕМОГО КОДА

Специальность 05 13 18 - Математическое моделирование численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2007

003158748

Работа выполнена на кафедре прикладных информационных технологий Московского физико-технического института (х осударственного университета)

Научный руководитель доктор физико-математических наук,

член-корреспондент РАН профессор Никитов Сергей Аполлонович

Официальные оппоненты доктор физико-математических наук

профессор

Крюковский Андрей Сергеевич

кандидат физико-математических наук Бельчик Александр Анатольевич

Ведущая организация Институт проблем информатики РАН

Защита состоится * ^ 2007 г в часов на заседа-

нии диссертационного совета К212 156 02 в Московском физико-техническом институте (государственном университете) по адресу 141700 Московская область, г Долгопрудный Институтский пер , д 9, ауд 903 КПМ

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета)

Автореферат разослан « »¿¿УтЯ^/и/ 2007 г

Ученый секретарь

диссертационного совета К212_156^32 к ф -м н

О С Федько

Общая характеристика работы Актуальность работы

В середине 90-х годов появилась технология программирования Java Это привело к бурному развитию и распространению концепции управляемого кода На сегодняшний день реализации этой технологии такие как Java и Microsoft NET прочно закрепились на лидирующих позициях в вопросах разработки программного обеспечения Главные их достоинства состоят в безопасности и переносимости кода, простоте и удобстве для разработчика, что позволяет быстро и качественно разрабатывать программное обеспечение (ПО) для разнообразного парка устройств в том числе и мобильных Это происходит за счет компиляции исходного текста программы в универсальный байт-код одинаковый для всех платформ К сожалению, производительность управляемого кода, как правило ниже по сравнению с неуправляемым Это вызвано наличием дополнительного слоя ПО с помощью которого и выполняется управляемый код Этот слой получил название контролирующего окружения или виртуальной машины На сегодняшний день наиболее универсальным языком программирования использующим технологию управляемого кода, является язык Java, потому сосредоточим внимание именно на нем

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

зуются крайне малым объемом доступной памяти и это также должно быть учтено

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

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

Цели и задачи диссертационной работы

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

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

2 Разработать способ выделения особенностей байткода кода Java,

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

Научная новизна работы

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

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

Основное достоинство модели заключается в абстрагировании от конкретных особенностей аппаратно-программной платформы в то же время она позволяет вводить в рассмотрение формальные поправки для

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

Применение математического аппарата генетических алгоритмов (ГА) позволило предложить эффективный метод численного решения поставленной задачи оптимизации

На защиту выносятся:

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

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

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

Апробация работы.

Материалы исследования докладывались и получили положительную оценку на научных конференциях и семинарах 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 г

Публикации.

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

Структура и объем диссертации.

Диссертация состоит из введения трех 1лав заключения, списка использованных источников включающего 84 работы и изложена на 100 страницах

Основное содержание работы

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

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

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

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

Метаданные Java-приложения удобно моделировать взвешенным ориентированным графом G = (V Е) Ею вершинам V соответствуют эле-

менты метаданных а ребра Е представляют информационные зависимости между ними Под информационной зависимостью 6 от о понимается тот факт что для вычисления Ь необходимо вычислить а, например чтобы при создании нового объекта определить размер выделяемого блока памяти (Ь) необходимо определить тип (а), создаваемого объекта

Вершина R соответствует указателю на начало управляемой памяти, вершины С( 1) , С(Мс) соответствуют данным загруженных классов В каждом классе есть Ср( 1), Ср(Мср) - набор статических определений F начало блока определения переменных F(l), , F(Mf) -определения переменных М - начало блока определения методов М( 1) , М(Mm) -определения методов Через Мс Мер, Mf, Mm обозначены соответственно математические ожидания количества классов в приложении, длины списков определений переменных и методов в каждом классе приложения Функции распределения этих величин будем считать атрибутами байт-кода

Другие вершины обозначают s - размер переменных класса, ts -размер объекта класса, с учетом унаследованных переменных, п - имя класса, sn - имя родительского класса, sr - ссылка на одну из вершин С соответствующую родительскому классу Выполнение каждой команды байт-кода Java сводится к последовательности операций поиска путей между двумя вершинами на рассматриваемом графе Такие операции будем называть элементарными, пусть они составляют множество Z Например, поиск имени класса С( 1) соответствует поиску пути между С(1) и п Поиск одного из классов по имени соответствует последовательному просмотру всех вершин С( 1) , С(Мс) и проведению для каждой из них поиска имени На практике для ускорения таких операций поиска пользуются хэш-таблицами На i рафе они промоделированы узлами СН для классов, CF и СМ для полей и методов внутри класса соответ-

6 2 5 9 l\

ь А

) L s" ) ( МН J 10 (пен

\ 11 \ 8 V 8Г У

F(Mf) ) ( IS )

С М )-KVO-)-М(Мш)

ственно

Обратим внимание на то что множество Е может состоять из ребер двух типов ссылки получаемые «естественным путем» те при загрузке связною списка данных с диска в память, и ссылки добавляемые дополнительно для ускорения навигации по структуре метаданных Первые составляют множество Eq и на рисунке изображены сплошными линиями а вторые составляют множество Е Они изображены пунктиром и помечены числами от 1 до 12 Очевидно что ЕцПЕ = 0 и любая конфигурация Е может быть представлена как Е — EqUE', где Е' С Е Добавление в граф ребер второго типа сопряжено с дополнительными расходами памяти Например эксперимент показывает что разница необходимых объемов памяти для одного и того же приложения при Е' = 0 и Е' = Е составляет до 40%

Для простоты принято что эффективность выполнения Java-приложения определяется только вычислительной сложностью производимых действий и объемом необходимой оперативной памяти Каждому ребру графа G поставим в соответствие вес w = (wc wm)T Компонента wc обозначает вычислительную сложность алгоритма перехода между вершинами, a ibm требуемый объем дополнительной памяти для организации такого ребра Характерно что wm = 0 для ребер из Ец и wc = 1 для ребер из Е Сложность алгоритмов в каждом конкретном случае оценивается теоретически и уточняется в соответствие с их реализацией на языке программирования

Для учета требований обусловленных особенностями платформы вводится вектор штрафов q = (qc qm)T 0 < q, qm и qc+4m = 1 Чем больше первая компонента тем больше штраф за нагрузку на процессор чем больше вторая - тем больше штраф за перерасход оперативной памяти В первом приближении набор команд байт-кода Java можно разде-

лить на пс = 4 классов «арифметические», доступ к переменным объекта доступ к методам объекта создание нового объекта Под «арифметическими» командами понимаются все операции ограничивающиеся работой с локальными переменными, как арифметические так и например, условные операторы Более глубокое расщепление команд на классы может привнести большую гибкость но велик риск потерять наглядность Для каждого класса команд можно выделить строгую последовательность элементарных операций Например чтобы создать объект, необходимо выделить для него место в памяти, для этого необходимо подсчитать необходимый размер, для это, в свою очередь необходимо найти метаданные класса, к которому принадлежит объект и т д Эти операции необходимо производить именно в таком порядке и ни в каком другом Каждой элементарной операции соответствует множество источников R{zk) С V и цель d(zf¡) £ V Тогда математическая сложность выполнения команды определенного типа может быть оценена как

N,

1= £ f(E,zk),

к=О

где Т(Е, 2jt) - оператор, вычисляющий математическое ожидание сложности разрешения информационной зависимости для операции zi Она численно равна сумме весов ребер входящих в кратчайший путь к вершине d{zi) из любой вершины R(zk) Эта величина носит вероятностный характер из-за того, что такой же характер носит сама структура i рафа G Для «арифметических» операций положим li = (1 0)г

Введем вектор £ = (£ь £„с) задающий частотное распределение для встречающихся в приложении команд байткода каждого класса,

Tic

& > 0, 1 = 1 «си £> = 1

7=1

Все такие £ образуют множество 3 Вектор £ также включим во множество атрибутов байт-кода Можно составить функционал для расчета математическою ожидания сложности выполнения Лауа-приложения

Матрица А служит для учета особенностей системы управления памятью на используемой платформе, если они не рассматриваются то она тождественно равна единичной матрице Если q и £ рассматривать как параметры то задача оптимального выполнения байт-кода Java сводится к задаче структурной оптимизации множества Е за счет оптимального выбора ребер, формирующих множество Е' Пространством поиска является множество всех подмножеств множества Е, обозначенное как О Каждый его элемент задает допустимую конфигурацию множества ребер графа Формально задача оптимизации может быть записана следующим образом

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

Очевидно что эффективность низкоуровневой работы с памятью критична для производительности виртуальной машины В математической модели это нашло отражение посредством матрицы А в (1)

(1)

з=\

о* = argmax J(£, q Eq U о)

(2)

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

1 Обеспечить выделение и освобождение блоков памяти

2 Обеспечить способ отслеживать неиспользуемые более блоки и помечать их для освобождения и последующего повторного использования

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

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

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

Р = -1 > 1

¿2т1

где М(; - суммарный размер памяти М] - объем свободной памяти, тг - размеры запрашиваемых у системы блоков Чем ближе </? к 1 тем методика более эффективная

В основу разработанной методики положена хорошо исследованная простейшая методика единого списка блоков Отличие заключается в том, что доступная память делится на две части В одной подряд выделяются блоки, а в другой ведется оглавление - список всех выделенных блоков как свободных так и занятых по аналогии с методикой «битовой маски» В этом списке содержится информация о начальном адресе блока его размере, соседях а также может храниться любая служебная информация регламентирующая работу с этим блоком В ответ на запрос о выделении памяти прикладное программное обеспечение получает указатель на строку в этом списке Оглавление отделено от списка для удобства работы прикладного программного обеспечения если для уменьшения внешней фрагментации блок будет перемещен то это никак не скажется на работе Такой подход в литературе получил название косвенной адресации Следуя принятой в литературе нотации для сложности алгоритмов можно оценить сложность выполнения арифметических операций Стоимость операции выделения нового блока в общем случае пропорциональна длине списка оглавления ЛГ(, В случае если необходимо производить уплотнение памяти то сложность этой операции также

пропорциональна количеству выделенных блоков ©(Аь), таким образом сложность выделения нового блока равна ©(ЛГ&) Операция освобождения блока сводится к добавлению пометки в списке и, возможно проведению слияния блоков если один или оба соседей на тот момент свободны В любом случае число требуемых операций фиксировано и может быть оценено как г = 9(1) Поскольку выделенные блоки непрерывны и в прикладной программе содержится указатель на начало блока, то стоимость операций чтения или записи пропорциональна только длине данных для одного машинного слова это ©(1) Методика являет собой определенный компромисс между быстродействием и экономичностью памяти Она разрабатывалась специально для применения во встраиваемых системах с жестким дефицитом памяти

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

Матрица А имеет смысл некоторою уточняющего коэффициента учитывающего особенности низкоуровневой работы с памятью

В третьей главе предлагается решение задачи оптимизации структуры метаданных ^уа-приложения Решение основано на применении математического аппарата генетических алгоритмов (ГА)

Применение классических методов оптимизации для таких задач как (2) чрезвычайно затруднено непредсказуемостью ландшафта целевой функции Действительно нельзя априори постулировать ни дифференциру-

емость ни непрерывную зависимость от параметров ни даже монотонность В решении подобных задач хорошо себя зарекомендовали генетические алгоритмы (ГА) Их первые применения относятся к 70-м годам 20-го века и к настоящему времени они доказали свою пригодность и к решению NР-трудных задач Поскольку теоретические обоснования методики ГА выходят за рамки диссертационной работы то при решении поставленной задачи оптимизации (2) применялись только простейшие методы, теоретические обоснования которых тщательно проверены

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

е 0-*Нь пусть Уо € О е(о) = (хо(0), .Хо(1,-1))

где Ь = 12 число структурных элементов (в нашем случае ребер) подлежащих оптимизации а Хо(») _ характеристическая функция множества о Она показывает, входит ли в множество о, ребро помеченное на рис 1 числом г В терминах ГА элементы Нь называются хромосомами а элементы множества О особями Очевидно что такое преобразование представления обратимо и Эе-1 Нь —» О так что \//1 £ Й£ Зе~1(К) £ О Это позволяет эффективнее использовать аппарат ГА для поиска решения

Общая схема применяемого генетического алгоритма выглядит следующим образом

1 Случайным образом формируется начальная популяция /0 Способ ее выбора влияет на скорость но не на факт сходимости поиска Текущим поколением объявляется начальная популяция I <— /о Стрелка влево обозначает операцию присваивания Наилучшая

особь определяется как

о* = argmax /(е-1(Л)) (3)

hei

где / О —> R, ограниченная функция принимающая неотрицательные значения

2 Анализируется условие остановки и схождения поиска

3 Осуществляется переход к новому поколению п пока \1п < Л |

а Производится селекция X — S(I) б Производится скрещивание Y = В(Х) в Производится мутация Уд еУ => д <— М(д) г Потомство переносится в новую популяцию 1п «— U Y

4 Новое поколение объявляется текущим / <— In п <~ п + 1 Новая оптимальная особь по аналогии с (3) определяется как

max ( argmax f(e l(h)) о* J

V bei J

Для применения аппарата ГА к численному исследованию модели автором был разработан программный комплекс на языке Java На этапе селекции действует оператор S I —> 21, который выбирает из I некоторое его подмножество В работе в основном, использовался пропорциональный оператор селекции за один шаг в множество X для скрещивания отбирается ровно два родителя и вероятность для каждой особи о быть выбранной пропорциональна /(о)

f(e-4h))

p{h ех} =

На этапе скрещивания действует простейший одноточечный оператор В 2Й£ —> 2я*- Он обладает несколько худшей способностью к перемешиванию по сравнению с более сложными однако его характеристики хорошо изучены Его действие заключается в том, что случайным образом выбирается к Е N 1 < к < Ь — 1 обе родительские хромосомы разрезаются перед к-м битом и обмениваются фрагментами с к-то по £-й бит

На этапе мутации действует оператор однородной мутации В Н1 —> #£ Он с небольшой вероятностью рт £ (0 1) инвертирует каждый бит хромосомы-аргумента Так вероятность того, что хромосома 1г — {0000} перейдет в хромосому Ь! = {0011} составляет

Р{Н К] = (1 - Рт) (1 - Рт) Рт Рт > 0

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

Функция / построена на основе функционала (1) следующим образом

/{о) = л« ч,£„и0)

Она удовлетворяет требованиям предъявленным к / и принимает наибольшее значение на наилучшем графе С

Численный эксперимент наглядно демонстрирует эффективность ГА и преимущества этого метода по сравнению с поиском оптимальной структуры графа полным перебором В худшем случае для решения задачи структурной оптимизации (2) требуется примерно на 50% меньше вычислений функционала (1) в лучшем - на 85%

19

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

В то же время, полученные результаты исследования модели позволяют выдвинуть гипотезу что если o*(f) - решение задачи оптимизации (2) при £ = С для

Vf Г - Н < <5 \\0*(О ~ о*Г)И < £(<*),

где метрика в Е используется евклидова, а в Hi Хеммиш ова Тогда достаточно будет предварительного вычисления о*(£) для £ образующих ¿-сеть над S, и для текущего значения £ не будет необходимости решать задачу оптимизации, а можно будет выбрать о*, соответствующее ближайшему узлу сети Впрочем эта гипотеза нуждается в тщательной проверке, что и является главным направлением дальнейших исследований

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

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

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

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

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

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

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

Список опубликованных работ

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

2 Погибельский Д А Оптимизация способа хранения метаданных в интерпретаторе Java /'/ Оборонный комплекс научно-техническому прогрессу - 2007 - вып 3 - С 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 / /Современные проблемы фундаментальных и прикладных наук Часть VII Управление и прикладная математика Труды XLIX научной конференции /Моек физ - техн ин-т - М - Долгопрудный 2006 - С 158-159

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

В работах, выполненных в соавторстве личный вклад автора состоит в следующем [1] - построение и программная реализация алгоритмов управления динамической памятью [3] - участие в разработке ключевых идей построение и программная реализация алгоритма решения задачи оптимизации структуры метаданных

Подписано в печать

Формат 60x84 1/16 Уч -изд л Тираж-^00 экз Заказ$

Отпечатано в типографии ИПК МИЭТ

124498, Москва, г Зеленоград, проезд4806, д 5, МИЭТ

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

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

Введение.б

Глава 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. Перспективы.

Актуальность работы обусловлена появлением в середине 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-приложения. Для апробации предложенного метода, разработана расширяемая программная библиотека, содержащая программный код, реализующий основную функциональность генетических методов. Полученные при исследовании простейшей модели метаданных результаты подтверждают эффективность предложенного метода оптимизации структуры метаданных.

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