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

• Соколов, Андрей Владимирович
• доктор физико-математических наук
• 2006

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

Введение

1 Динамическое распределение памяти

1.1 Базовые структуры данных.

1.1.1 Линейные списки

1.1.2 Стеки, очереди и деки.

1.1.3 Последовательное представление стека

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

1.1.5 Связанное представление линейных списков

1.1.6 Список свободной памяти.

1.1.7 Последовательное представление нескольких линейных списков.

1.1.8 Бинарные деревья.

1.1.9 Произвольные деревья.

1.1.10 Применение динамических структур в машинной графике.

1.1.11 Другие области применения стеков и очередей

1.1.12 Применение очередей в 1Ш1Х-подобных системах

1.2 Виртуальная память.

1.2.1 Развитие способов адресации

1.2.2 Организация обмена информацией между уровнями памяти.

1.2.3 Фрагментация памяти.

1.2.4 Методы динамического распределения нестраничной памяти.

1.3 Применение стеков в процессорах.

1.3.1 Классификация стековых компьютеров

1.3.2 Методы управления памятью в стековых компьютерах.

1.3 3 Управление регистровыми окнами в Препроцессорах

Оптимальное управление стеками

2.1 Оптимальное управление одним стеком в двухуровневой памяти.

2.1.1 Минимизация среднего числа перераспределений стека.

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

2.2 Немарковская модель поведения стека

2.2.1 Максимизация среднего времени

2.2.2 Минимизация средних затрат времени с учетом перераспределения.

2.3 Решение задачи Д. Кнута о двух стеках, растущих навстречу друг другу

2.4 Оптимальное управление двумя стеками, растущими навстречу друг другу в двухуровневой памяти

2.4.1 Минимизация среднего числа перераспределений стеков

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

2.4.3 Оптимальное управление двумя параллельными стеками

2.5 Оптимальное расположение п стеков в памяти

2.6 Оптимальное распределение п стеков в памяти одного уровня

2.6.1 Оптимальное начальное распределение памятиИБ

2.6.2 Случай п=3.

2.6.3 Оптимальное управление тремя стеками, допускающими только включения.

2.6.4 Оптимальное управление четырьмя стеками, допускающими только включения.

2.6.5 Оптимальное управление тремя стеками в общем случае.

2.6.6 Оптимальное распределение четырех и более стеков в одноуровневой памяти

2.6.7 Оптимальное управление тремя стеками, когда два стека растут навстречу друг другу, а третий растет навстречу им обоим одновременно

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

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

2.7 Оптимальное управление тремя стеками в двухуровневой памяти

2.8 Оптимальное управление п ^ 4 стеками в двухуровневой памяти

3 Оптимальное управление очередями

3.1 Оптимальное управление одной очередью в двухуровневой памяти.

3.1.1 Параметризованная реализация циклической очереди в двухуровневой памяти.

3.1.2 Математическая модель.

3.1.3 Результаты вычислений.

3.2 Оптимальное управление двумя циклическими очередями в случае раздельной реализации.

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

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

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

3.4.1 Выбор оптимального размера страницы

3.4.2 Матрица переходных вероятностей.

3.5 Численные результаты.

3.6 Оптимальное управление двумя очередями в случае, когда очереди двигаются друг за другом по кругу

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

3.7 Оптимальное управление к очередями в памяти одного уровня

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

3.8.1 Случай раздельной последовательной циклической реализации.

3.8.2 Случай, когда очереди двигаются друг за другом по кругу.

3.9 Оптимальное управление очередями в общей памяти в случае бесконечного времени блуждания

4 Оптимальные методы распределения памяти сегментами разных длин

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

4.2 Оценка эффективности методов динамического распределения нестраничной памяти

4.2.1 Модель метода "FIRST-FIT".

4.2.2 Модель метода "BEST-FIT".

4.2.3 Модель метода "OPT-FIT".

4.2.4 Модель метода динамического распределения памяти в ОС ЕС ЭВМ.

4.2.5 Анализ численных результатов.

Введение диссертации (часть автореферата) на тему «Математические модели и алгоритмы оптимального управления динамическими структурами данных»

Настоящий бум сейчас переживает индустрия производства программного и аппаратного обеспечения для различных устройств типа мобильных телефонов, встроенных систем, различных сетевых устройств, например, маршрутизаторов, и т. п. Такие устройства имеют жесткие ограничения на ресурсы памяти. Разработка программных систем для них требует особого внимания к алгоритмам управления памятью. В настоящее время достаточно хорошо развита теория страничной виртуальной памяти. Различные модели и алгоритмы оптимального замещения страниц исследовались в работах Ахо А., Деннинга Р, Ульмана Дж., Михновского С.Д., Шора Н.З., Авена О.И., Когана Я.А., Стояна Ю.А., Кутепова В.П., Пьянкова В.П. и других ученых, которые будут проанализированы в первой главе диссертации.

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

Этот вывод подтвердила и практика разработки, например, стековых компьютеров и RISC процессоров, где для управления стеками в двухуровневой памяти (регистры — оперативная память) использовались специальные алгоритмы, а не универсальные алгоритмы кэш-памяти. Еще один пример - алгоритмы работы с FIFO-очередями, необходимые при разработке встроенных операционных систем, управляющих потоками пакетов в сетевых маршрутизаторах, таких, например, как Cisco IOS, где требования на время обработки пакетов маршрутизатором очень жесткие. Механизм страничной виртуальной памяти здесь не используется и вся работа происходит в нескольких пулах оперативной памяти.

Кроме того на практике достаточно широко используются системы с нестраничной организацией памяти. Теория нестраничной организации памяти развита недостаточно. Выводы большинства работ [Кнут Д., Грисс Д., Танненбаум Э., Цикритзис Д., Берн-стайн Ф., Bays С.A., Fenton LS, Paim P.W., Campbell I.A., Shore J. и др.] основаны на имитационном моделировании и часто противоречивы.

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

Первой задачей математического анализа динамических структур данных, рассмотренной нами, была задача, которая состоит в следующем: пусть в памяти объема m расположены два стека, растущие навстречу друг другу. В этом случае место их встречи можно рассматривать как случайную величину. Пусть известно, что на каждом шаге с вероятностью р может произойти исключение элемента из одного из стеков и с вероятностью 1-р может произойти включение информации в один из стеков. Обозначим через М(т,р) математическое ожидание случайной величины тах(к\,к2), где к\ик2- длины стеков при встрече. Д.Кнут поставил задачу разработать математическую модель этого процесса и установить вид функции М(т,р). В работах [Соколов A.B. 1980, Yao A.C. 1981, P. Flajolet 1986, G.Louchard 1990,1994,R.S.Maier 1991] была построена математическая модель процесса в виде двумерного случайного блуждания в треугольной области с двумя отражающими экранами и одним поглощающим экраном. Эта задача была важна как ступень в разработке новых математических моделей и постановке и решении новых задач оптимального управления динамическими структурами данных. Была, в частности, предложена математическая модель метода динамического распределения памяти в широко известной в 1980-е годы операционной системе ОС ЕС ЭВМ(1ВМ 360) и даны рекомендации по его улучшению, а также высказана гипотеза об улучшении метода управления памятью в МВК Эльбрус-1.

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

Исследуются базовые линейные структуры — стеки, очереди, динамические таблицы, а также список свободных блоков переменной длины. В данной работе в задачах оптимального управления последовательными стеками в двухуровневой памяти мы будем иметь в виду чистые стеки, в которых разрешен доступ только к последнему включенному в стек элементу, а в задачах оптимального управления стеками в одноуровневой памяти доступ внутрь стека разрешен. Это замечание справедливо и по отношению к последовательным очередям. Дело в том, что в чистых стеках и очередях в случае ситуации переполнения быстрой памяти возможно часть структуры данных переместить в память второго уровня, а в быстрой памяти хранить только ту часть, где производятся исключения и доступ к элементам. В случае стека в эту же часть производятся и включения элементов, а в случае очереди включения производятся в другой конец списка, который также хранится в быстрой памяти. Если же разрешен доступ внутрь структуры данных, то такая оптимизация невозможна.

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

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

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

Анализ ситуации переполнения стека также может быть полезен в связи с проблемой информационной безопасности компьютерных сетей, так как по некоторым данным, проблема переполнения стека (обычно, когда буфер переменной длины затирает адрес возврата, находящийся в вершине стека) оказывается источником ошибок, например, в программах под Unix и Windows NT примерно в 2/3 случаев.

Задачи управления стеками возникают при разработке RISC-процессоров. В этом случае для работы со скалярными аргументами и локальными переменными процедур организуются перекрывающиеся окна регистров, которые связаны в кольцо. По существу, в этом случае мы имеем один обычный стек с элементами типа "окно" в главной памяти, несколько верхних элементов которого образуют циклический стек на регистрах. Если вершина регистрового стека совпала с указателем начала с той или другой стороны, т. е. произошло переполнение (или опустошение) вершины стека, то необходимо какое-то число окон переписать в главную память из регистров или наоборот.

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

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

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

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

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

Результаты работы программ показывают, что среднее время в случае представления трех стеков как четырех, когда память разделена интуитивно, для некоторых вероятностей может быть лучше, чем в случае интуитивного последовательного представления стеков, (см. строки Таблицы 22: 3,4,5,8,9). Это происходит тогда, когда все вероятности исключения ^ 0.2 и также тогда, когда среди вероятностей исключения хотя бы одна близка к нулю. В остальных случаях среднее время интуитивного последовательного представления стеков лучше, чем в случае интуитивного представления трех стеков как четырех.

Также, если среди вероятностей исключения хотя бы одна близка к нулю, то среднее время в случае оптимального последовательного представления трех стеков хуже, чем среднее время в случае оптимального представления трех стеков, как четырех, (см. строки Таблицы 22: 4,8,9).

Рассмотрим теперь случай, когда информационная часть имеет произвольный размер поле связи имеет единичную длину, размер памяти т кратен / +1. Тогда в качестве математической модели имеем случайное блуждание по целочисленной решетке, с расстоянием между узлами I + 1, в пирамиде: х\ + х2 + £3 < щ.

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

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

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

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

1. Абрамов В. Г., Трифонов Н. П., Трифонова Г. Н. Введение в паскаль. М.: Наука, 1988.

2. Авен О. И., Коган Я. А. Управление вычислительным процессом в ЭВМ. М.: "Энергия", 1978.

3. Аксенова Е. А., Волкова О. В., Лазутина А. А., Соколов А. В. Методы оптимального управления стеками в двухуровневой памяти // Труды Института прикладных математических исследований КарНЦ РАН. 2002. Вып. 3. С. 127-152.

4. Аксенова Е.А., Лазутина A.A., Соколов A.B. Об оптимальном распределении памяти для стеков // Обозрение прикладной и промышленной матем. 2003 т. 10, в. 1, с. 86-87.

5. Аксенова Е.А., Лазутина A.A., Соколов A.B. Об оптимальных методах представления динамических структур данных

6. Аксенова Е.А., Лазутина A.A. , Соколов A.B. Исследование немарковской модели управления стеком в двухуровневой памяти // Программирование, 2004, N1, с. 1-10.

7. Аксенова Е.А., Соколов A.B. Об оптимальном управлении двумя FIFO очередями. Материалы VIII Международного семинара "Дискретная математика и ее приложения", с. 167-169. М.: Изд-во механико-математического факультета МГУ, 2004, 444 с.

8. Аксенова Е.А., Лазутина A.A., Соколов A.B. Анализ методов представления динамических структур данных // Обозрение прикладной и промышленной математики. 2004, т.11, в.2, с. 233-234

9. Аксенова Е.А., Соколов A.B. Некоторые задачи оптимального управления FIFO-очередями. Труды Второй Всероссийской научной конференции "Методы и средства обработки информации". Изд. отдел ВМК МГУ им. М.В. Ломоносова, 2005. с. 318-322.

10. Ахо А., Деннинг Р., Ульман Дж. Принципы оптимального замещения страниц // Новая серия. Вып. 9. М.: Мир, 1972. С. 34-102.

11. Боллапрагада В., Мэрфи К., Уайт Р. Структура операционной системы Cisco IOS // Вильяме , 2002.

12. Брайант Р., О'Халларон Д. Компьютерные системы. Архитектура и программирование. БХВ-Петербург, 2005.

13. Брусенцов Н. П. Миникомпьютеры. М.: Наука, 1979.

14. Бурцев В. С. Тенденции развития высокопроизводительных систем и многопроцессорные вычислительные комплексы. Препринт / ИТМ и ВТ АН СССР. М., 1977.

15. Вайнгартен Ф. Трансляция языков программирования. М.: Мир, 1979.

16. Ван-дер-Варден Б. Л. Алгебра. М.: Наука, 1976.

17. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.

18. Гоисс Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975.

19. Жоголев Е. A., Pay О. И. Принципы оптимального распределения памяти // Вычислительные методы и программирование. М.: Изд-во МГУ, 1971. С. 18-38.

20. Иванов А. П., Шевяков В. С. Управление памятью в МВК ЭЛЬБРУС-1. Препринт № 3 / ИТМ и ВТ АН СССР. М., 1981.

21. Ивченко Г. И. Время ожидания и связанные с ним характеристики в полиномиальной схеме // Дискретная математика. 1993. Вып. 5. № 3. С. 3-34.

22. Ивченко Г. И., Иванов А. В. Разделимые статистики в обратных урновых задачах // Дискретная математика. 1995. Вып. 7. № 2. С. 103-117.

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

24. Кнут Д. Искусство программирования для ЭВМ. Т. 1. М.: Мир, 1976.

25. Кнут Д. Искусство программирования для ЭВМ. Т. 3. М.: Вильяме, 2001.

26. Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. Случайные размещения. М.: Наука, 1976.

27. Колчин В. Ф. Случайные отображения. М.: Наука, 1984.

28. Кормен Е., Лейзерсон Ч., Ривест Р. Алгоритмькпостроение и анализ. М.:МЦНМО, 2000.

29. Королев Л. Н. Структуры ЭВМ и их математическое обеспечение. М.: Наука, 1978.

30. Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982.

31. Кутепов В. П., Пьянков В. П. Алгоритмы определения множества активных страниц (сегментов) программы, основанные на понятии динамического цикла // Программирование. 1979. № 4. С. 44-52.

32. Лавров С. С., Гончарова Л. И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971.

33. Лазутина А. А. , Соколов A.B. Оптимальное управление тремя стеками в памяти одного уровня // Тезисы докладов XIV Международной конференции "Проблемы теоретической кибернетики". Изд. -во центра прикладных исследований при

34. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

35. Мазалов В. В. Метод динамического распределения нестраничной памяти // Программирование. 1995. № 4. С. 29-32.

36. Мазалов В. В., Соколов А. В. Об оптимальном динамическом распределении нестраничной памяти. Управление в динамических системах. Л., 1979. Деп. в ВИНИТИ 24.07.1979.

37. Медведев Ю. И. Некоторые теоремы об асимптотическом распределении статистики х2 II Доклады АН СССР. 1970. Вып. 192. № 5. С. 987-989.

38. Михновский С. Д., Шор Н. 3. Оценка минимального числа пересылок при динамическом распределении страничной памяти // Кибернетика. 1965. № 5. С. 18-21.

39. Олифер Н. Маршрутизатор как он есть // Журнал сетевых решений LAN. 2001. Т. 7. № 7-8 С. 20-24.

40. Поливанный И. В. Оценка размера буфера для флагового STACK/QUEUE алгоритма заполнения 4-связной области на дискретном растре // Программирование. 1998. № 3. С. 3845.

41. Пратт Т. Языки программирования. М.: Мир, 1979.

42. Ранделл Б. Разбиение памяти и сегментация программ // Экспресс-информация. Вычислительная техника. 1969. №47.

43. RISC: Эффективные архитектуры для СБИС-компьютеров. Электроника СБИС. Проектирование микроструктур

44. Робачевский А. М. Операционная система UNIX. СПб.: BHV-Санкт-Петербург, 1998.

45. Роджерс Д. Алгоритмические основы машинной графики. М.: Мир, 1989.

46. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. Изд.-во "ДиаСофт", 2001. 688 с.

47. Соколов А. В. Анализ метода динамического распределения памяти в ОС ЕС ЭВМ // Математическое обеспечение ЭВМ и систем управления. Петрозаводск, 1985. С. 28-32.

48. Соколов А. В. Анализ эффективности алгоритмов динамического распределения нестраничной памяти // Труды II Меж-дунар. конф. "Развитие и применение открытых систем". Петрозаводск, 1995. С. 76-77.

49. Соколов А. В. Математические модели динамического распределения памяти // Тезисы докл. I Всесоюз. науч. конф. "Вероятностные методы в дискретной математике" / КФ АН СССР. Петрозаводск, 1983. С. 28-32.

50. Соколов А. В. Математические модели и алгоритмы оптимального управления динамическими структурами данных // Обозрение прикладной и промышленной математики. 2000. Т. 7. Вып. 1. С. 199-200.

51. Соколов А. В. Об оптимальном управлении стековой памятью // Тезисы докл. I Всесоюз. науч. конф. "Вероятностные методы в дискретной математике" / КФ АН СССР. Петрозаводск, 1988. С. 115.

52. Соколов А. В. Оптимальное динамическое распределение нестраничной виртуальной памяти: Дис. . канд. физ.-мат. наук. ЛГУ, 1981.

53. Соколов А. В. Оптимизация динамических структур данных. Учебное пособие. Петрозаводск: Изд-во ПетрГУ, 1993. 58 с.

54. Соколов А. В. О распределении памяти для двух стеков // Автоматизация эксперимента и обработки данных. Петрозаводск, 1980. С. 65-71.

55. Соколов A.B. Оценка минимального размера памяти, необходимого для динамического распределения сегментов разных длин // Автоматизация эксперимента и обработки данных. Петрозаводск, 1980. С. 59-65.

56. Соколов А. В. Оценка эффективности методов динамического распределения нестраничной памяти // Программирование. 1986. № 5. С. 65-71.

57. Соколов А. В., Тарасюк А. В. Об оптимальном управлении циклическими очередями // Труды Института прикладных математических исследований КарНЦ РАН. 2001. Вып. 3. С. 190-195.

58. Соколов A.B. Вероятностные модели динамических структур данных // Труды третьего Всероссийского симпозиума по

59. Соколов A.B. Математические модели и алгоритмы оптимального управления динамическими структурами данных. Из.- во ПГУ. 2002 г. 215 с.

60. Соколов A.B. Математические задачи теории структур данных. Карелия и РФФИ // Тезисы докладов научной конференции, посвященной 10-летию РФФИ. Петрозаводск 2002, С. 96-97.

61. Соколов A.B., Тарасюк A.B. Об оптимальном управлении двумя последовательными очередями // Обозрение прикладной и промышленной матем. 2003 т. 10, в. 1, с. 223-224.

62. Соколов A.B. , Ислентьев Д.О., Колосов A.C. Анализ нестандартных методов представления связных списков // Труды ИПМИ КарНЦ РАН. Методы математического моделирования и информационные технологии. Выпуск 4. 2003, 188-193.

63. Соколов A.B., Соломатов В.А. Анализ методов управления двумя FIFO очередями // Труды ИПМИ КарНЦ РАН. Методы математического моделирования и информационные технологии. Выпуск 5. 2004, 121-127.

64. Соколов A.B., Тарасюк A.B. Об оптимальном управлении двумя FIFO-очередями на бесконечном времени. Тезисы докладов

65. XIV Международной конференции "Проблемы теоретической кибернетики"// Изд.-во центра прикладных исследований при механико-математическом факультете МГУ, Москва 2005, с. 148.

66. Соколов A.B., Тарасюк A.B. Об оптимальном управлении циклическими FIFO-очередями // Системы управления и информационные технологии. 2005, N3(20), с. 29-33.

67. Спицер Ф. Принципы случайного блуждания. М.: Мир, 1969.

68. Стоян Ю. А. Результаты оценки эффективности оптимального алгоритма замещения // Программирование. 1975. № 2. С. 17-23.

69. Супервизор ОС ЕС ЭВМ. М.: Статистика, 1975.

70. Танненбаум Э. Многоуровневая организация ЭВМ. М.: Мир, 1977.

71. Танненбаум Э. Современные операционные системы. 2-издание. Питер, 2002.

72. Феллер В. Введение в теорию вероятностей и ее приложения. М.: Мир, 1964.

73. Футы К., Судзуки Н. Языки программирования и схемотехника СБИС. М.: Мир, 1988.

74. Алгол 68. Методы реализации. Под. ред. Г.С. Цейтина. Издательство Ленинградского университета. Ленинград 1976.

75. Цикритзис Д., Бернстайн Ф. Операционные системы. М.: Мир, 1977.

76. Шилдт Г. Теория и практика С++. СПб.: BHV-Санкт-Петербург, 1996.

77. Юрченко А. С. Методы динамического распределения нестраничной памяти // Управляющие системы и машины. 1978. № 5. С. 68-74.

78. Яковлев Е. И. Машинная имитация. М.: Наука, 1975.

79. Auiezri S. Fraenkel Paired sequential lists in a memory interval // Inform. Process Lett. 1979. № 8. P. 9-10.

80. Batson A., Shy-Ming Jn., Wood D. C. Measurements of segment Size // Second Symposium on operating systems principles. October 20-22. 1969. Princeton: Princeton University, 1969. P. 25-29.

81. Bays C. A. A comparison of Next-fit, First-fit and Best-fit // CACM. 1977. V. 20, № 3. P. 191-192.

82. Campbell /. A. A note an optimal-fit method for dynamic allocation of storage // The Computer Journal. 1971. V. 14, № 1. P. 7-9.

83. Dening P. J. The working set model for program behaviour // CACM. 1968. V. 11, № 8. P. 323-333.

84. Dening P. J. Virtual Memory // Computing Surveys. 1970. V. 2, 3. P. 153-189.

85. Ditzel David R., McLellan H. R. Register Allocation for Free: The С Machine Stack Cache // Proc. Symp. Archit. Support Progr. Lang. Oper. Systems. 1982. P. 48-56.

86. Ertl Anton M. Stack caching for interpreters // SIGPLAN'95 Conf. Program. Lang. Des. and Implem. (PLDI). June 1995. P. 315-327.

87. Flajolet P. The evolution of two stacks in bounded space and random walks in a triangle // Lec. Notes Computer Sci. 1986. Vol. 223. P. 325-340.

88. Harlan D. Mills, Richard C. Linger. Data structured progamming: program design without arrays and pointers // IEEE Trans. Software Eng. 1986. V. 12, № 2. P. 192-197.

89. Hasegava M., Shigei Y. High-speed top-of-stack scheme for VLSI processor: a management algorithm and its analysis // Proceedings of 12th Symposium on Computer Architecture. June. 1985. P. 48-54.

90. Koopman P. Stack Computers. Ellis Horwood, 1989. URL: http://www.cs.cmu.edu/~koopman/stackcomputers/

91. Leung C. H. An improved optimal-fit procedure for dynamic storage allocation // Comp. J. 1982. V. 25, № 2. P. 199-206.

92. Louchard G. Random walks, heat equation and distributed algorithms / G. Louchard, R. Schott, M. Tolley, P. Zimmermann // J. Comput. Appl. Math. 1994. № 53. P. 243-274.

93. Louchard G., Schott R. Probabilistic analysis of some distributed algorithms // Lect. Notes Computer Sci. 1990. № 431. P. 239253.

94. Maier R. S. Colliding Stacks: A Large Deviations Analysis // Random Structures and Algorithms. 1991. № 2. P. 379-421.

95. Patterson D. A., Sequin C. H. Reduced Instruction Set VLSI Computer // Proceedings of 8th Symposium on Computer Architecture. 1980. № 6. P. 72-86.

96. Sokolov A. V. On the problem of optimal stack control in two levels memory // Probabilistic methods in discrete mathematics: Proceedings of the Fourth International Petrozavodsk Conference. Utrecht, Netherlands: VSP, 1997. P. 349-351.

97. Sokolov A. V. On the problem of stack control // Proceedings' of Finnish Data Processing Week. 1999. Vol. 2. Petrozavodsk: Petrozavodsk University Press. P. 95-106.

98. Sokolov A. V., Lemetti A. A, On the problem of optimal stack control // Probabaiistic methods in discrete mathematics: Proceedings of the Fifth International Conference. Utrecht, Netherlands: VSP, 2001. P. 351-366.

99. Sokolov A.V. Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control.// Abstracts. The 3rd Moscow International Conference On Operations Research(ORM2001)(Moscow, April 4-6, 2001) p. 109-110.

100. Sokolov A. V., Aksenova E.A., Lazutina A.A., Tarasyuk A.V. Mathematical models of dynamic data structure. // V international congress on mathematical modelling. Book of abstract, vol. II, JINR, Dubna 2002, P. 127

101. Sokolov A.V. Optimization strategies of stack control // Proceedings of the Second Workshop on Intermediate

102. Reprezentation Engineering for Virtual Machins and Inaugural Conference on the Principles and Practice of Progrmming in Java. Trinity College Dublin, PPPJ 2002/IRE 2002, June 13-14, 2002. P. 151-156.

103. Sokolov A.V. // Optimization strategies of stack control. Chapter 22. In. Recent Advances in Java Technology. Theory, Application, Implementation. Intermediate Reprezentation Engineering. Computer Science Press, Trinity College Dublin 2002. P. 193-203

104. Stanley T., Wedig R. A performance analysis of automatically managed top of stack buffers // Proceeding of 14th Symposuim on Computer Architecture. June. 1987. P. 272-281.

105. Taivalsaari A. Implementing a Java™ Virtual Machine in the Java Programming Language. Sun microsystems 11 Technical Report Series. March. 1998.

106. Tamir Y., Sequin C. Strategies of control register's file // IEEE Trans. Comput. C-32(ll). 1983. P. 977-1037.

107. URL: http://www.hackzone.ru/articles/ntbo.html

108. Yao A. C. An analysis of a memory allocation scheme for implementating stacks // SIAM J. Computing. 1981. № 10. P. 398-403.