Помощь в написании студенческих работ
Антистрессовый сервис

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

Диссертация: Математические модели и алгоритмы оптимального управления динамическими структурами данных
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

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

Содержание

  • 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. Случай п=
      • 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.

Показать весь текст

Список литературы

  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. 239 253.
  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. 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.
Заполнить форму текущей работой

Сессия? Спокойно!