Алгоритмы динамического распределения памяти в системах реального времени тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

ГЛАВА I. ОБЩИЕ СВОЙСТВА РШЕНИЙ ЗАДАЧ ДИНАМИЧЕСКОГО

РАСПРЕДЕЛЕНИЯ ПАМЯТИ

§ I. Формальная постановка задачи

§ 2. Независимые расписания

§ 3. Расписания с выгрузкой страниц по запросам

§ 4. Нормализованные расписания с правильным порядком

§ 5. Анализ последовательности моментов ввода

ГЛАВА П. АНАЛИЗ ЗАДАЛ «ЩШМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ ПАМЯТИ

ПРИ ПЕРИОДИЧЕСКИХ ЗАПРОСАХ НА ПАМЯТЬ

§ I. Распределение памяти при обязательных вводах при использовании одного канала

§ 2. Расцределение памяти при обязательных вводах при использовании нескольких каналов

§ 3. Распределение памяти для повторяющихся групп запросов

ГЛАВА Ш. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ ПРИ

НЕПЕРИОДИЧЕСКИХ ЗАПРОСАХ

§ I. Исследование свойств допустимых приведенных расписаний

§ 2. Алгоритм построения допустимого приведенного расписания

§ 3. Доказательство правильности алгоритма

ГЛАВА 17. РЕАЛИЗАЦИЯ И ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ

АЛГОРИТМОВ ДИНАМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ

ПАМЯТИ

§ I, Описание программы и методики численных экспериментов . . IOO

§ 2. Исследование задания на использование памяти

§ 3. Исследование алгоритма . III

3.1. Влияние основных параметров на время построения расписания . III

3.2. Один из способов ускорения поиска расписания

3.3. Одно из решений проблемы, когда допустимого расписания для задания нет . II?

§ 4. К вопросу о реализации алгоритмов динамического распределения памяти

В настоящее время развитие современной вычислительной тех" / / ники идет по двум основным направлениям: с одной стороны создание универсальных многомашинных вычислительных комплексов и на базе их сетей ЭВМ, с другой стороны разработка специализированных вычислительных систем (ВС), связанных с конкретными приложениями. В данной диссертации рассматриваются системы, функционирующие в непосредственном взаимодействии с внешней средой, называемые системами реального времени (РВ). Область применения систем РВ очень широка [i, 2, 37 J. Автоматизированные системы управления технологическими процессами внедрены или разрабатываются во всех отраслях народного хозяйства. Это системы управления атомными реакторами, доменными печами, программные логические контроллеры, станки с программным управлением, система обнаружения дефекта с помощью радиометрического и ультрозвукового контроля, конвейеры, роботы и т.д. К системам РВ относятся системы массового обслуживания, например, резервирование и продажа билетов на самолеты и поезда. Для проведения наблюдений в темпе эксперимента с целью выработки управляющих воздействий и оперативного контроля за течением эксперимента тоже необходимы системы РВ. Примерами таких систем могут служить система автоматизации ядерно-физических экспериментов, система исследования физических процессов и явлений взаимодействия электромагнитного излучения с атмосферой, система наблюдения за радиолокационными и телеметрическими сигналами, сигналами из космоса и т.д.

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

За строго ограниченный сверху интервал времени, называемый временем ответа (Тотв.), система должна вернуть среде результаты обработки в виду управляющих воздействий или в виде сообщений пользователю. Невыполнение обработки за время Тотв. значительно обесценивает ее результат и может привести к нежелательным последствиям во внешней среде вплоть до нарушения работы управляемого объекта. На практике Тотв. зависит от динамических характеристик внешней среды. Это время может колебаться от нескольких миллисекунд до получаса и более [I ] .

Предметом настоящей диссертации является система жесткого реального времени (ЖРВ) [зв] . Система ЖРВ - это такая система, в которой некоторым заданиям сопоставляются директивные сроки, не подлежащие нарушению, называемые крайними сроками [з J . Директивный срок представляет собой момент времени, к которому желательно завершить выполнение задания.

Так как время в системе SPB является одним из основных параметров, то разработка и исследование таких систем является более сложным, чем разработка любой другой вычислительной системы. Поэтому для обеспечения работоспособности и надежности системы ЖРВ необходимо применить метод моделирования [4 J.

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

Математические модели многопроцессорных ВС и многомашинных комплексов рассматриваются в работах [6-9J.

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

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

Основные математические модели и постановки задач в теории

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

- все работы должны быть выполнены;

- на одном приборе может выполняться только одно задание;

- существуют ограничения на порядок выполнения заданий и на использование всех видов ресуроов;

- существуют ограничения при составлении расписания (составление расписания без прерываний, с прерываниями, но с соблюдением общего времени, требуемого для выполнения задания).

В настоящее время имеется значительное число работ, перечень которых цриведен в [з, 14, 15J , связанных с конструированием точных и приближенных методов составления расписаний. Исследованию систем ЖРВ посвящены работы на отсутствие нарушений директивных сроков получения результатов каждой конкретной задачи [16, 17, 38-40J и на быстродействие [l8] . В работе [iej предлагается модель ВС, состоящая из центрального процессора (ЦП), оперативной и внешней памяти и внешних устройств. Особое внимание в работе уделено оптимальному по критерию быстродействия распределению ресурсов для требований, последовательность выполнения которых задана сетью. В данной модели не рассматривается механизм распределения памяти и не учитывается работа по выделению памярасписаний рассматриваются при следующих предположениях ти. Считается, что если память есть, то она выделяется мгновенно, что не соответствует действительности и может привести к ошибкам в реальной системе SPB.

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

Чтобы быть уверенными, что система ЖРВ не получит отказа из-за нехватки памяти, нужно дополнительно к расписанию использования процессора и устройств ввода/вывода построить расписание распределения памяти, что является предметом исследования данной диссертации.

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

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

Вопросы динамического распределения памяти изучались многими авторами, обзор этих работ будет приведен ниже. Отличительной особенностью методов, предложенных в диссертации, является то, что в них учитывается влияние на распределение памяти времени использования, т.е. времени VI ; 1 = нахождения каждой программной единицы в памяти, где L - общее число запросов б—' 77 на выделение памяти, и влияние времени загрузки Uc ; ^ = и выгрузки ^Г/ ; L - 1,L программных единиц.

В общем виде задачу динамического распределения памяти можно сформулировать следующим образом.

Пусть заранее определено время выполнения всех работ и составлено расписание [l7J , которое показывает, когда и какая программная единица должна выполняться на ЦП. После определения такого расписания становится известной последовательность запросов на память X = { Ху , Х2 , . . . , DCL J , последовательность моментов времени, в которые происходят запросы7=jtjf t2,t^J, оценки на время пребывания каждой программной единицы в памяти 0-, * " ; J и последовательность объемов запрашиваемых программных единиц ~V~= { Ц ; ^ ? • • • ? Vt ] .Если все программные единицы не помещаются в ОП, то возникает задача динамического распределения памяти.

Загрузка информации в ОП и выгрузка из нее осуществляется страницами постоянного объема за время С , которое складывается из двух компонент: постоянной - это поиск адресов, и переменной - это передача информации по каналу связи, затраты на которую прямо пропорциональны объему передаваемой информации. Емкость памяти, т.е. число разделов, на которые разделена динамическая часть ОП, равна С. Каждый раздел имеет фиксированное число ячеек памяти, и в нем помещается ровно одна страница.

Задача распределения памяти сводится к следующей. Как разместить программные единицы в оперативной памяти, чтобы:

- 10

1. сумма объемов, занимаемая црограммными единицами, в любой момент времени не превышала бы объема С;

2. каждая программная единица ОС с » L-lfL успевала бы счи-тываться в 0П с внешнего устройства к моменту своего запроса

3. каждая программная единица р I - i,L удалялась бы из 0П не ранее времени своего использования ^ ;

4. число вводимых в 0П программных единиц не должно превышать числа используемых каналов и процесс загрузки/выгрузки осуществляется каналами без прерываний.

Решение задачи в общем виде сводится к решению задачи целочисленного программщювания. Известно, что в такой постановке эта задача /VP - полна [l9] , т.е. не существует полиномиального алгоритма ее решения.

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

Динамическое распределение памяти - это назначение и освобождение ее для данных и команд во время выполнения программы. Существуют три способа динамического распределения памяти: с использованием базисных адресов, страничной и сегментной организации памяти [20 ].

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

- II

Способ страничной и сегментной организации тесно связан с понятием виртуальной памяти. Впервые идея виртуальной памяти была предложена разработчиками машины AT LAS, созданной в 1958 году в Манчестерском университете [41J . В системе с виртуальной памятью операционная система заботится об организации обмена информацией между уровнями памяти, и, таким образом, несмотря на иерархическую структуру памяти, программисту как бы предоставляется память одного уровня и практически бесконечного размера.

С тех пор, как в 1971 году постепенно начала появляться на рынке представители семейства 370 фирмы IBM [42 ] , можно сказать, что все ведущие по вычислительной технике страны и фирмы выпускают ЭВМ с виртуальной памятью.

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

Распределение памяти страницами заключается в том, что вся память, в общем виде разнородная с физической точки зрения, но однородная для пользователя, физически разбивается на страницы, содержащие фиксированное число ячеек памяти. Все страницы независимо перемещаются в ОП и из нее; заданию могут быть выделены несмежные страницы, т.е. страницы одного задания могут располагаться в разных местах ОП. Размеры страниц зависят от конкретной системы. Типичные размеры страниц 256, 1024, 4096 байт.

Страничная организация памяти применяется в ряде современных вычислительных машин, например, в отечественной машине БЭСМ-6, в машинах серии ЕС ЭВМ-2. Большинство ЭВМ 1У поколения будут иметь страничную структуру [21] .

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

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

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

Чтобы реализовать динамическое распределение памяти страницами, необходимы три возможности при управлении памятью. Рэцдел и Кюнер [4з] называют их стратегиями выборки, размещения и замены.

Стратегия выборки определяет правило выбора страниц из внешней памяти. Имеются два подхода: подкачка страниц по запросу и опережающая подкачка. Было доказано [44, 45J , что при определенных допущениях относительно стоимости соответствующих операций опережающая подкачка страниц фактически никогда не дает выигрыша по сравнению с подкачкой по запросу. Бывают же особые условия, когда метод опережающей подкачки пригоден. Например, может быть известно, что каждой программе нужен определенный набор системных таблиц и начальная группа команд, чтобы приступить к работе. В этом случае имеет смысл загрузить соответствующие страницы сразу, не дожидаясь, пока программа запросит их с помощью прерываний [46] . Если можно предсказать поведение программ,т.е. выяснить, какие страницы потребуются в ближайшем будущем, то разумеется, опережающая подкачка страниц сократит число прерываний из-за отсутствия страниц.

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

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

В настоящее время разработано и находит применение множество стратегий управления памятью, с помощью которых можно оценить интенсивность обмена информацией между ОП и внешней памятью [2228 ]. Рассмотрим наиболее известные из них, которые используются в различных машинах. Классификация алгоритмов замещения приведена в работах [29-31J .

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

Циклическое удаление страниц FIFO (Fist In Fist Out) из памяти заключается в том, что удаляется самая "старая" страница, т.е. та, которая к моменту принятия решения находится в ОП дольше всех. Несмотря на то, что стратегия FIFO привлекательна с точки зрения ее реализации, она существенно ограничивает производительность системы.

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

Многие алгоритмы замещения страниц являются модификациями алгоритма рабочего набора ws (working set) , предложенного Ден-нингом [47] . Под рабочим набором программы понимают наименьшую совокупность ее страниц, которые должны находиться в ОП для того, чтобы программа выполнялась на некотором желаемом уровне эффективности без прерываний из-за отсутствия страниц [48, 49 J .

Эвристические алгоритмы замещения страниц. Впервые эвристический алгоритм замещения был предложен Деннингом [б1 ]. Основная идея принципа Деннинга заключается в следующем. Пусть Х = [oCi ^27 • • • у L4 °° - последовательность обращений к страницам в процессе выполнения программы; у "7 iff»} состояние памяти, которая разделена на (7) -разделов в момент страничного сбоя t ; 9 > t - первый момент времени, в который происходит следующее обращение к странице (L= Положим ti~ t .В момент времени t в ОП замещается та страница iji , для которой условное математическое ожидание Е I Х2 7. v максимально. Дня осуществления этого алгоритма необходимо сделать предположение о вероятностном распределении запросов, позволяющее вычислить математическое ожидание Е . Из принципа Деннинга были получены многие алгоритмы замещения, в которых в зависимости от конкретных предположений поразному вычислялись значения Е £"24, 41, 45J . Основные результаты, связанные с этими алгоритмами, отражены в работах В них рассматриваются различные модели страничной организации памяти, на основе которых предлагаются численные методы для оценки вероятности замены страниц. Однако на практике эти методы реализовать довольно сложно даже при помощи ЭВМ, поскольку они недостаточно полно описывают реальную систему.

Оптимальное вытеснение страниц ОРТ. Суть этого алгоритма состоит в том, что замещается та страница, обращение к которой будет позже всех. Алгоритм предложен Михновским С.Д. и Шор Н.З. в 1965 году £23 ] . В литературе ссылаются на Биледи, исследовавшего этот алгоритм в 1966 году £57] . В работе [м] было доказано, что при применении этого алгоритма отношение числа прерываний из-за отсутствия страницы к числу обращений к памяти минимально.

В 1970-1975 годах много работ было посвящено теоретическому и практическому исследованию алгоритмов замещения. Теоретики делают различные стохастические предположения о поведении программ £ 32-34] , практики исследуют реальные программы [43, 55-58J . Биледи, например, £б7, 58J испытал ряд алгоритмов на множестве программ и сравнил результаты с результатами, использующими оптимальное замещение. Стратегии fifo и ram) были наименее удовлетворительными, требуя приблизительно в три раза больше загрузок, чем ОРТ. Статистический подход всегда привлекал внимание большого количества авторов. В нашей стране в этом направлении наиболее активно работала группа авторов работ £29, 33, 35 ].

Описанные выше алгоритмы, такие как rand , pipo ,lrv и другие не гарантируют соблюдение заданных директивных сроков пребывания программных единиц в памяти. Эвристические алгоритмы, позволяющие получить рациональное расцределение памяти, минимизирующее, например, среднее число обменов между внешней и оперативной памятью, тоже не подходят для системы ЖРВ.

Предложенные в данной диссертации алгоритмы распределения памяти являются модификациями оптимального алгоритма замещения страниц. Использование алгоритма ОРТ основывается на предположении, что нам известны моменты поступления заявок на память и длительность их обслуживания. В работах, посвященных применению и исследованию алгоритма ОРТ [23, 24, 32 , 44 , 57J не учитывается такой важный ресурс ВС как канал ввода/вывода, затраты времени С на ввод/вывод программных единиц и требуемое время пребывания каждой программной единицы в памяти ; Is ij*

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

Коротко рассмотрим основное содержание диссертации. Диссертация состоит из введения, четырех глав и заключения.

ЗАКЛЮЧЕНИЕ

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

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

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

Полученные алгоритмы динамического распределения памяти могут быть использованы при проектировании систем жесткого реального времени.

1. Мартин Дж. Программирование для вычислительных систем реального времени. М., "Мир", 1975.

2. Никитин А.И. Общее программное обеспечение систем реального времени. Киев, Наукова думка, 1980.

3. Теория расписаний и вычислительные системы (пер. с анг. под ред. Коффмана Э.Г.). М., Наука, 1984.

4. Сушков Б.Г. Проблемы проектирования вычислительных систем реального времени. В сб. Теория и реализация систем реального времени. М., ВЦ АН СССР, 1984.

5. Липаев В.В. Распределение ресурсов в вычислительных системах. М., Статистика, 1979.

6. Овсянкин Б.П. Об одной задаче организации обработки данных в многопроцессорных вычислительных системах. М., IBM и МФ, 1983.

7. Мультипроцессорные системы и параллельные вычисления (пер. с анг. Ю.С.Голубева-Новожилова и А.Л.Щорса), под ред.Ф.Г.Энслоу . М., Мир, 1976.

8. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М., Сов.радио, 1983.

9. Штрик А.А. Оценка затрат производительности на обмен данными в управляющих многомашинных комплексах систем реального времени. Управ.системы и машины, № 2, 1978.

10. Ю.Артамонов Г.Т., Брехов О.М. Аналитические вероятностные модели функционирования ЭВМ. М., Энергия, 1978.

11. Авен О.И., Коган Я.А. Математические модели сложных вычислительных систем (обзор). Автоматика и телемеханика, № I, 1971.

12. Головкин Б.А. Построение вероятностной модели и анализ параллельных вычислительных процессов. йзв.АН СССР, Техн.кибернетика, № 3, 1973.

13. Клейнрок Л. Вычислительные системы с очередями. М., Мир, 1979.

14. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М., Наука, 1975.

15. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М., Наука, 1975.

16. Визинг В.Г. О расписаниях, не нарушающих директивные сроки выполнения работ. Кибернетика, № I, 1981.

17. Буланже Д.Ю., Сушков Б.Г. Алгоритмы управления вычислительными системами жесткого реального времени. Изв. АН СССР, Техн. кибернетика, № 6, 1982.

18. Мищенко А.В., Сушков Б.Г. Минимизация времени выполнения работ, представленных сетевой моделью, при нефиксированных параметрах сети. М., ВЦ АН СССР, 1980.

19. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., Мир, 1982.

20. Журавлев Ю.П., Акиныпин Ю.С. Системное проектирование памяти. ЦВМ. М., Сов.радио, 1976.

21. Ершов А.П. Математическое обеспечение четвертого поколения. Кибернетика, № I, 1972.

22. Наумов Б.Н., Левин И.А., Компельмахер В.Л. Выбор оптимального состава базы данных для систем управления в реальном масштабе времени. Управляющие системы и машины, $ 4, 1979.

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

24. Бронштейн И.И. Об оптимальной стратегии замещения программ равных длин в оперативной памяти ЦВМ. Автоматика и телемеханика, $ 3, 1972.

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

26. Мэдник С., Донован Дд. Операционные системы. М., Мир, 1978.

27. Горицкий Ю.А., Кутепов В.П., Старобогатова Н.Н. О выборе оптимального числа программ для ВС со страничной стратегией распределения памяти. Изв. АН СССР, Техн. кибернетика, Л I, 1975.

28. Маковенко Е.Т. Об одном подходе к выбору оптимального размещения страниц. Управляющие системы и машины, I, 1973.

29. Коган Я.А., Кимельфельд Б.Н., Авен О.И. Управление многоуровневой памятью вычислительных систем (обзор). Автоматика и телемеханика, № II, 1972.

30. Королев Л.Н., Ивани A.M. Классификация страничных алгоритмов и методов оценки. В сб. Некоторые вопросы автоматизации обработки физического эксперимента, вып. 3, М., Изд.МГУ, 1975.

31. Юрченко А.С. Методы динамического распределения страничной памяти. Препринт 79-41, Киев, ИК АН УССР, 1979.

32. Стоян Ю.А. Результаты оценки эффективного оптимального алгоритма замещения. АН СССР, Программирование, № 2, 1975.

33. Богуславский Л.Б. Аналитическое исследование алгоритмов замещения страниц в двухуровневой памяти. Автоматика и телемеханика, II, 1974.

34. Стоян Ю.А. Оценка эффективности алгоритмов замещения. АН СССР, Программирование, № I, 1975.

35. Богуславский Л.Б., Коган Я.А., Леман А.А. Моделирование алгоритмов замещения страниц иерархического кламса. В кн. Математическое обеспечение автоматизированных чистем управления. М., Изд. МЭСИ, 1975.- 128

36. Auslander M.A., Jaffe J.F. Functional structure of IBM virtual storage operating system, Part I, IBM System J*, 12,1. N 4, 1973.

37. Randell В., Kuehner C.J. Dynamic storage allocation system, Comm. of ACM, 11, N 5, 1968.

38. Gecsei J,, Mattson R.L. and others Evaluation techniques for storage hierarchies, IBM System Journal, 9, К 2, 1970.

39. Aho A.V., Denning P.J,, Ullman J.D, Principles of Optimal Page Replacement, J. ACM, 18, N 1, 1971,

40. Oppenheimer G., Weiaer N. Resource Management for a medium Scale Time-Sharing Operating System, CACM, 11, N 5, 1968.

41. Denning P.J. The working set model for program behavior. Comm. of ACM, 11, N 5, 1968,

42. Belady L.A. and others. Dynamic space-sharing in computer system, Comm. of ACM, 12, К 5, 1969.