Содержание к диссертации
Введение
ГЛАВА I. ОБЩИЕ СВОЙСТВА РШЕНИЙ ЗАДАЧ ДИНАМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ ПАМЯТИ 20
I. Формальная постановка задачи 21
2. Независимые расписания 27
3. Расписания с выгрузкой страниц по запросам 29
4. Нормализованные расписания с правильным порядком 38
5, Анализ последовательности моментов ввода 45
ГЛАВА П. АНАЛИЗ ЗАДАЧ ДТШМЙЧЕСКОГО РАСПРЕДЕЛЕНИЯ ІШЛЯТИ ПРИ ПЕРИОДИЧЕСКИХ ЗАПРОСАХ НА ПАМЯТЬ . 53
I. Распределение памяти при обязательных вводах при использовании одного канала 55
2. Распределение памяти при обязательных вводах при использовании нескольких каналов . 62
3. Распределение памяти для повторяющихся групп запросов 68
ГЛАВА Ш. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ ПРИ НЕПЕРИОДИЧЕСКИХ ЗАПРОСАХ 74
I. Исследование свойств допустимых приведенных расписаний 75
2. Алгоритм построения допустимого приведенного расписания 89
3. Доказательство правильности алгоритма . 94
ГЛАВА ІУ. РЕАЛИЗАЦИЯ И ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ АЛГОРИТМОВ ДИНАМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ ПАМЯТИ 99
I. Описание программы и методики численных экспериментов ІОО
2. Исследование задания на использование памяти 106
3. Исследование алгоритма III
3.1. Влияние основных параметров на время построения расписания III
3.2. Один из способов ускорения поиска расписания 115
3.3. Одно из решений проблемы, когда допустимого расписания для задания нет II?
4. К вопросу о реализации алгоритмов динамического распределения памяти 117
Заключение 123
Литература , 125
- Формальная постановка задачи
- Распределение памяти при обязательных вводах при использовании одного канала
- Исследование свойств допустимых приведенных расписаний
- Описание программы и методики численных экспериментов
Введение к работе
В настоящее время развитие современной вычислительной тех-ники идет по двум основным направлениям: с одной стороны созда-ние универсальных многомашинных вычислительных комплексов и на базе их сетей ЭВМ, с другой стороны разработка специализированных вычислительных систем (ВС), связанных с конкретными приложениями. В данной диссертации рассматриваются системы, функционирующие в непосредственном взаимодействии с внешней средой, называемые системами реального времени (РВ). Область применения систем РВ очень широка [і, 2, 37^. Автоматизированные системы управления технологическими процессами внедрены или разрабатываются во всех отраслях народного хозяйства. Это системы управления атомными реакторами, доменными печами, программные логические контроллеры, станки с программным управлением, система обнаружения дефекта с помощью радиометрического и ультрозвукового контроля, конвейеры, роботы и т.д. К системам РВ относятся системы массового обслуживания, например, резервирование и продажа билетов на самолеты и поезда. Для проведения наблюдений в темпе эксперимента с целью выработки управляющих воздействий и оперативного контроля за течением эксперимента тоже необходимы системы РВ. Примерами таких систем могут служить система автоматизации ядерно-физических экспериментов, система исследования физических процессов и явлений взаимодействия электромагнитного излучения с атмосферой, система наблюдения за радиолокационными и телеметрическими сигналами, сигналами из космоса и т.д.
Под системой, работающей в реальном масштабе времени, понимается система, которая должна обрабатывать поступающую в нее информацию в течение заданного интервала времени с тем, чтобы результат был получен к моменту выдачи необходимых данных или управляющих воздействий [і ] . При этом информация не может поступить в систему раньше определенного момента времени.
За строго ограниченный сверху интервал времени, называемый временем ответа (Тотв.), система должна вернуть среде результаты обработки в виду управляющих воздействий или в виде сообщений пользователю. Невыполнение обработки за время Тотв. значительно обесценивает ее результат и может привести к нежелательным последствиям во внешней среде вплоть до нарушения работы управляемого объекта. На практике Тотв. зависит от динамических характеристик внешней среды. Это время может колебаться от нескольких миллисекунд до получаса и более [і 1.
Предметом настоящей диссертации является система жесткого реального времени (ЖРВ) [38J . Система ЖРВ - это такая система, в которой некоторым заданиям сопоставляются директивные сроки, не подлежащие нарушению, называемые крайними сроками Гз J. Директивный срок представляет собой момент времени, к которому желательно завершить выполнение задания.
Так как время в системе ЖРВ является одним из основных параметров, то разработка и исследование таких систем является более сложным, чем разработка любой другой вычислительной системы. Поэтому для обеспечения работоспособности и надежности системы ЖРВ необходимо применить метод моделирования [4 J.
Модель вычислительной системы, использующей многоуровневую память и функционирующей в режиме мультипрограммирования, слишком сложна для анализа ее функционирования с реальными входными данными. Поэтому для получения пригодных для практического применения результатов, целесообразно рассмотреть модель вычислитель- ной системы как декомпозицию следующих моделей [б J : модель однопроцессорной ВС без ограничений на память; модель иерархической памяти ВС с упрощенным описанием динамики исполнения заявок каждым процессором; модель многомашинной и многопроцессорной ВС без внешней памяти. Подобная декомпозиция естественна технически и подтверждается множеством исследований, .проведенных по каждой из моделей.
Математические модели многопроцессорных ВС и многомашинных комплексов рассматриваются в работах [6-9J.
При исследовании модели однопроцессорной ВС без ограничений на память и модели иерархической памяти применяются детерминированные и стохастические методы распределения ресурсов. Стохастические методы, такие как марковские модели массового обслуживания, сетевые модели систем с очередями и др. [I0-I3J используются, когда априорно известны и различимы статические характеристики поступления и обслуживания некоторых типов заявок. С помощью этих методов можно оценить среднее время ответа, среднее время ожидания, среднее время передачи данных. Эти методы применимы для систем РВ, где важно выполнение времени обслуживания в среднем, например, для системы резервирования авиабилетов, но они не применимы для систем ЖРВ, в которых некоторые требования должны быть обязательно выполнены к определенному сроку.
В данной диссертации исследование системы ЖРВ основывается на предположении, что нам известны оценки на время работы отдельных частей программы, например, максимальное время. Для получения таких оценок нужна специальная система измерений. Получив эти оценки, мы можем считать известными состав решаемых задач и длительность их решения, что позволяет рассматривать задачу распределения ресурсов ВС жесткого реального времени как де- - 7 -терминированную задачу, которую можно сформулировать в терминах теории расписаний и решать ее методами этой теории. После решения задачи распределения ресурсов ВС мы можем гарантировать результат, т.е. выполнение директивных сроков.
Основные математические модели и постановки задач в теории расписаний рассматриваются при следующих предположениях [l4j : все подлежащие выполнению работы определены и известны, т.е. известна последовательность значений времени поступления заявок на их исполнение и длительность решения каждой вызываемой задачи; все работы должны быть выполнены; на одном приборе может выполняться только одно задание; существуют ограничения на порядок выполнения заданий и на использование всех видов ресуроов; существуют ограничения при составлении расписания (составление расписания без прерываний, с прерываниями, но с соблюдением общего времени, требуемого для выполнения задания).
В настоящее время имеется значительное число работ, перечень которых приведен в [з, 14, 15J , связанных с конструированием точных и приближенных методов составления расписаний. Исследованию систем ЖРВ посвящены работы на отсутствие нарушений директивных сроков получения результатов каждой конкретной задачи [16, 17, 38-40J и на быстродействие [l8J . В работе [iej предлагается модель ВС, состоящая из центрального процессора (ЦП), оперативной и внешней памяти и внешних устройств. Особое внимание в работе уделено оптимальному по критерию быстродействия распределению ресурсов для требований, последовательность выполнения которых задана сетью. В данной модели не рассматривается механизм распределения памяти и не учитывается работа по выделению памя- - 8 -ти. Считается, что если память есть, то она выделяется мгновенно, что не соответствует действительности и может привести к ошибкам в реальной системе ЖРВ.
Среди работ, перечисленных выше, отметим работу [I7J В ней рассматривается модель однопроцессорной ВС, учитывающая влияние системы ввода/вывода на работу ЦП. Задача исследования такой ВС сводится к построению расписания работы этой системы, удовлетворяющего крайним срокам и заданной схеме обработки информации. В этой модели такой ресурс как память совсем не учитывается, т.е. считается, что нет ограничений на объем памяти.
Чтобы быть уверенными, что система ЖРВ не получит отказа из-за нехватки памяти, нужно дополнительно к расписанию использования процессора и устройств ввода/вывода построить расписание распределения памяти, что является предметом исследования данной диссертации.
Если памяти хватает, т.е. все программные модули помещаются в ОП, то память можно распределять статически однократно до начала функционирования системы РВ. Если же все команды и данные программных единиц не помещаются в ОП, то требуется выделять па-сять динамически, т.е. в процессе функционирования ВС. При этом возникает задача планирования подкачки каналом запрашиваемых программных единиц в системе РВ.
В данной диссертации рассматривается двухуровневая модель памяти, состоящая из внешней памяти неограниченного объема и оперативной памяти (ОП) ограниченной емкости. Обмен между ОП и внешней памятью осуществляется страницами фиксированного объема с помощью канала, пропускная способность которого ограничена.
Вопросы динамического распределения памяти изучались многими авторами, обзор этих работ будет приведен ниже. Отличительной - 9 - особенностью методов, предложенных в диссертации, является то, что в них учитывается влияние на распределение памяти времени использования, т.е. времени VI ; l=i;2,.--, L нахождения каж дой программной единицы в памяти, где L - общее число запросов на выделение памяти, и влияние времени загрузки LC ; С~1,Ьи выгрузки / } і - 1,L программных единиц.
В общем виде задачу динамического распределения памяти можно сформулировать следующим образом.
Пусть заранее определено время выполнения всех работ и составлено расписание [l7J , которое показывает, когда и какая программная единица должна выполняться на ВД. После определения такого расписания становится известной последовательность запросов на память X = { Ху 1 Х2 , . . . , XL j , последовательность
МОМеНТОВ Времени, В КОТОрые ПРОИСХОДЯТ ЗапрОСЫ7= /С/, *2 9"в;Ч[9 оценки на время пребывания каждой программной единицы в памяти Q = \1?i Vz і .' } "і\ и последовательность объемов запра-шваемых программных единиц V= [vt, V,,..., VL] .Если все программные единицы не помещаются в ОП, то возникает задача динамического распределения памяти.
Загрузка информации в ОП и выгрузка из нее осуществляется страницами постоянного объема за время U , которое складывается из двух компонент: постоянной - это поиск адресов, и переменной - это передача информации по каналу связи, затраты на которую прямо пропорциональны объему передаваемой информации, S*-кость памяти, т.е. число разделов, на которые разделена динамическая часть ОП, равна С. Каждый раздел имеет фиксированное число ячеек памяти, и в нем помещается ровно одна страница.
Задача распределения памяти сводится к следующей. Как разместить программные единицы в оперативной памяти, чтобы: сумма объемов, занимаемая программными единицами, в любой момент времени "С , О L й 7/1 не превышала бы объема С; __ каждая программная единица ОС с » C=1,L успевала бы счи-тываться в 0П с внешнего устройства к моменту своего запроса каждая программная единица 00^ ? і = 4,L удалялась бы из 0П не ранее времени своего использования и i=I,L ; число вводимых в 0П программных единиц не должно превышать числа используемых каналов и процесс загрузки/выгрузки осуществляется каналами без прерываний.
Решение задачи в общем виде сводится к решению задачи целочисленного программирования. Известно, что в такой постановке эта задача /YP - полна fl9j , т.е. не существует полиномиального алгоритма ее решения.
Без учета работы канала в различных упрощающих предположениях подобные задачи динамического распределения памяти рассмат*-ривались в литературе. Проведем краткий обзор работ, посвященных этим вопросам. динамическое распределение памяти - это назначение и освобождение ее для данных и команд во время выполнения программы. Существуют три способа динамического распределения памяти: с использованием базисных адресов, страничной и сегментной организации памяти [20 J.
Первый способ, называемый способом относительной адресации, заключается в том, что каждой программе присваивается свой базисный адрес, который используется для получения истинного адреса путем сложения условного адреса с этим базисным. - II -
Способ страничной и сегментной организации тесно связан с понятием виртуальной памяти. Впервые идея виртуальной памяти была предложена разработчиками машины AT LAS, созданной в 1958 году в Манчестерском университете 41J . В системе с виртуальной памятью операционная система заботится об организации обмена информацией между уровнями памяти, и, таким образом, несмотря на иерархическую структуру памяти, программисту как бы предоставляется память одного уровня и практически бесконечного размера.
С тех пор, как в 1971 году постепенно начала появляться на рынке представители семейства 370 фирмы IBM [42J , можно сказать, что все ведущие по вычислительной технике страны и фирмы выпускают ЭВМ с виртуальной памятью.
Для отображения виртуальной памяти на физическую в основном применяются два метода: страничная и сегментная организация памяти.
Распределение памяти страницами заключается в том, что вся память, в общем виде разнородная с физической точки зрения, но однородная для пользователя, физически разбивается на страницы, содержащие фиксированное число ячеек памяти. Все страницы независимо перемещаются в ОП и из нее; заданию могут быть выделены несмежные страницы, т.е. страницы одного задания могут располагаться в разных местах ОП. Размеры страниц зависят от конкретной системы. Типичные размеры страниц 256, 1024, 4096 байт.
Страничная организация памяти применяется в ряде современных вычислительных машин, например, в отечественной машине БЭСМ-6, в машинах серии ЕС ЭВМ-2. Большинство ЭВМ ІУ поколения будут иметь страничную структуру [21 ] .
Отметим достоинства этого метода. Распределение памяти страницами решает проблему фрагментации памяти без необходимое- -12-ти перемещения разделов после окончания некоторого задания. Оно позволяет рассматривать адресное пространство задания как непрерывное. Требуемые заданию страницы могут загружаться в ОП не одновременно, а по мере необходимости.
Сегментная организация памяти находит применение при составлении программ и последующем разделении их на отдельные массивы, способные решать самостоятельные участки задачи. Виртуальная память каждой программы при этом делится на части, называемые сегментами. Понятие сегмента в отличии от понятия страницы не имеет четкого физического значения. Сегмент представляет собой совокупность данных или программ, расположенных в разделенной или неразделенной памяти [20 J .
В системах со страничной и сегментной организацией понятие оперативной памяти утрачивает смысловое содержание и переходит в понятие виртуальной памяти.
Чтобы реализовать динамическое распределение памяти страницами, необходимы три возможности при управлении памятью. Рэндел и Кюнер [43 J называют их стратегиями выборки, размещения и замены.
Стратегия выборки определяет правило выбора страниц из внешней памяти. Имеются два подхода: подкачка страниц по запросу и опережающая подкачка. Было доказано [44, 45]] , что при определенных допущениях относительно стоимости соответствующих операций опережающая подкачка страниц фактически никогда не дает выигрыша по сравнению с подкачкой по запросу. Бывают же особые условия, когда метод опережающей подкачки пригоден. Например, может быть известно, что каждой программе нужен определенный набор системных таблиц и начальная группа команд, чтобы приступить к работе. В этом случае имеет смысл загрузить соответствующие стра- - ІЗ -ницы сразу, не дожидаясь, пока программа запросит их с помощью прерываний [46] . Если можно предсказать поведение программ,т.е. выяснить, какие страницы потребуются в ближайшем будущем, то разумеется, опережающая подкачка страниц сократит число прерываний из-за отсутствия страниц.
Стратегия размещения определяет, куда в оперативную память поместить запрашиваемую страницу. Учитывая, что все места в ОП обычно эквивалентны, стратегия размещения не оказывает влияния на характеристики обмена.
Стратегия замены определяет, какую страницу нужно переместить на внешнюю память, если памяти не хватает. Если есть незанятая физическая страница, то не возникает никаких трудностей. Но в большинстве случаев каждая физическая страница содержит какую-то математическую страницу, и следует решить, какую страницу следует вытеснить. Стратегия принятия таких решений называется правилом или алгоритмом замещения страниц.
В настоящее время разработано и находит применение множество стратегий управления памятью, с помощью которых можно оценить интенсивность обмена информацией между ОП и внешней памятью [22-28 ]. Рассмотрим наиболее известные из них, которые используются в различных машинах. Классификация алгоритмов замещения приведена в работах [29-31J .
Случайное удаление страниц raud При этой стратегии страница, которую нужно удалить из памяти, выбирается случайным образом. Конечно, этот алгоритм легко реализовать, но, очевидно, что часто вытесняются нужные страницы.
Циклическое удаление страниц FIFO (Fist In Fist Out) из памяти заключается в том, что удаляется самая "старая" страница, т.е. та, которая к моменту принятия решения находится в ОП доль- - 14 -ше всех. Несмотря на то, что стратегия FIFO привлекательна с точки зрения ее реализации, она существенно ограничивает производительность системы.
Замещение по давности использования LEV (Least Recently Used) . По этой стратегии удаляется страница, ссылки на которую не встречались дольше, чем на все другие страницы. В большинстве случаев стратегия LRV работает хорошо, но ее реализация дорого стоит.
Многие алгоритмы замещения страниц являются модификациями алгоритма рабочего набора ws (working set) , предложенного Ден-нингом [47 ] . Под рабочим набором программы понимают наименьшую совокупность ее страниц, которые должны находиться в ОП для того, чтобы программа выполнялась на некотором желаемом уровне эффективности без прерываний из-за отсутствия страниц [48, 49J.
Эвристические алгоритмы замещения страниц. Впервые эвристический алгоритм замещения был предложен Деннингом [51 J. Основная идея принципа Деннинга заключается в следующем. Пусть Х = {ос4 Х* .. , у ОсЛ9 Loo - последовательность обращений к страницам в процессе выполнения программы; В=іЧі?Уг>' y'Jtnj -состояние памяти, которая разделена на 17) -разделов в момент страничного сбоя t ; t{ 9 tc > t - первый момент времени, в который происходит следующее обращение к странице Ці (1= 4,2,...?). Положим A is ti - t . В момент времени t в ОП замещается та страница Ці , для которой условное математическое ожидание Е (&i | 0С^ Х2 ?.. v Xi) максимально. Для осуществления этого алгоритма необходимо сделать предположение о вероятностном распределении запросов, позволяющее вычислить математическое ожидание t . Из принципа Деннинга были получены многие алгоритмы замещения, в которых в зависимости от конкретных предположений по- - 15 -разному вычислялись значения Е 24, 41, 45J . Основные результаты, связанные с этими алгоритмами, отражены в работах [52-5б]. В них рассматриваются различные модели страничной организации памяти, на основе которых предлагаются численные методы для оценки вероятности замены страниц. Однако на практике эти методы реализовать довольно сложно даже при помощи ЭВМ, поскольку они недостаточно полно описывают реальную систему.
Оптимальное вытеснение страниц ОРТ. Суть этого алгоритма состоит в том, что замещается та страница, обращение к которой будет позже всех. Алгоритм предложен Михновским С.Д. и Шор Н.З. в 1965 году 23 J . В литературе ссылаются на Биледи, исследовавшего этот алгоритм в 1966 году [57J . В работе [44J было доказано, что при применении этого алгоритма отношение числа прерываний из-за отсутствия страницы к числу обращений к памяти минимально.
В 1970-1975 годах много работ было посвящено теоретическому и практическому исследованию алгоритмов замещения. Теоретики делают различные стохастические предположения о поведении программ 32-34J , практики исследуют реальные программы [43, 55-58J . Биледи, например, [57, 58J испытал ряд алгоритмов на множестве программ и сравнил результаты с результатами, использующими оптимальное замещение. Стратегии FIFO и ВДЖ> были наименее удовлетворительными, требуя приблизительно в три раза больше загрузок, чем ОРТ. Статистический подход всегда привлекал внимание большого количества авторов. В нашей стране в этом направлении наиболее активно работала группа авторов работ Г29, 33, 35 J.
Описанные выше алгоритмы, такие как rand , fifo ,lrv и другие не гарантируют соблюдение заданных директивных сроков пребывания программных единиц в памяти. Эвристические алгоритмы, позволяющие получить рациональное распределение памяти, ми- нимизирующее, например, среднее число обменов между внешней и оперативной памятью, тоже не подходят для системы ЖРВ.
Предложенные в данной диссертации алгоритмы распределения памяти являются модификациями оптимального алгоритма замещения страниц. Использование алгоритма ОРТ основывается на предположении, что нам известны моменты поступления заявок на память и длительность их обслуживания. В работах, посвященных применению и исследованию алгоритма ОРТ [^23, 24, 32, 44, 57J не учитывается такой важный ресурс ВС как канал ввода/вывода, затраты времени С на ввод/вывод программных единиц и требуемое время пребывания каждой программной единицы в памяти 1/с 7 ь ~ ',Ь
В системе ЖРВ распределение памяти должно вестись с учетом частоты обращения к отдельным массивам и модулям, времени их перезаписи и работы с ними, с учетом каналов обмена информацией между ОП и внешними устройствами, иначе в ОП могут не успеть ввестись к моменту обработки необходимые массивы или модули программ. В нашем случае необходимость строго соблюдения директивных сроков вынуждает рассматривать задачу распределения памяти как задачу дискретного программирования, точнее как задачу нахождения расписания использования памяти.
Коротко рассмотрим основное содержание диссертации. Диссертация состоит из введения, четырех глав и заключения.
В первой главе предлагается двухуровневая модель иерархической структуры памяти. Для этой модели предполагаем известными из расписания, построенного для модели однопроцессорной ВС с устройствами ввода/вывода, количество требований L на выделение памяти; для каждого требования 0С , б- iyL считаем известным время LI , не позже которого программный модуль должен быть помещен в память,и время 'иС » не раньше которого он может быть - 17 -удален из памяти.
Предполагается, что программные модули занимают фиксированное число ячеек памяти, их мы называем страницами. Обмен между ОП и внешней памятью осуществляется каналами одинаковой производительности.
В этой главе приводятся формулировки основных определений таких, как задание на использование памяти, расписание, вводится понятие независимых расписаний, понятие допустимого расписания, показывающего, в какой момент времени и какая страница должна загружаться в память и выгружаться из нее.
Основной результат, который был получен в этой главе, заключается в том, что при построении допустимого расписания можно ограничиться классом приведенных расписаний, т.е. нормализованных-расписаний с правильным порядком с выгрузкой страниц по запросам. Также проводится анализ последовательностей моментов ввода, необходимый для доказательств теорем, приведенных в следующих главах.
Во второй главе рассмотрены наиболее простые задачи динамического распределения памяти, когда запросы на выделение памяти периодические. Целесообразность отдельного изучения этих задач объясняется наличием линейных алгоритмов их решения и возможностью получения простых формул, связывающих необходимые объемы памяти с характеристиками задания и производительностью канала.
Одна из задач - задача распределения памяти для случая, когда входная информация представляет собой периодическую последовательность запросов на память и загрузка в ОП нужна при каждом поступлении данных. Предложенные в этой главе алгоритмы могут быть применимы для размещения в ОП входной информации, поступающей извне в виде блока кадров постоянного объема V с определенной частотой. На обработку такого блока кадров тратится одно - 18 -и тоже время, а это значит, что время хранения постоянно о^-const l-itL . Предполагается, что расстояние между запросами A is І; ~ t-i 7 ІФ-j) tj > ti постоянно, так как частота поступления информации одинакова. Для этой задачи рассмотрены случаи, когда загрузка и выгрузка данных производится одним каналом, несколькими каналами.
Другая задача - это задача распределения памяти, когда последовательность запросов на память представляет собой повторяющиеся группы из нескольких разных модулей постоянного объема. Для этой задачи тоже рассматриваются случаи использования для загрузки и выгрузки информации одного канала, нескольких каналов.
Для этих простых задач, описанных выше, получен результат в виде оценок объема памяти, необходимой для размещения информации в зависимости от частоты поступления данных или расстояния между запросами Л t , от времени использования If , времени загрузки и выгрузки *Г и числа используемых каналов.
Третья глава посвящена более общей и сложной задаче распределения памяти, когда запросы на размещение в ОП страниц поступают с разной частотой и канал ввода/вывода не может справиться с загрузкой и выгрузкой всех страниц, т.е. существуют ограничения на производительность канала. Первоначально все страницы находятся на внешней памяти. По мере необходимости они подкачиваются каналом в ОП. В этой главе предлагается алгоритм построения допустимого расписания, который является фактически алгоритмом страничного замещения. Суть алгоритма заключается в следующем. Всякий раз, когда запрашиваемой страницы нет в памяти и поэтому необходима ее загрузка, удаляется та страница, время следующего запроса на которую максимально, но такая, для которой выполняются все условия допустимого расписания. Отличительной особенностью - 19 -предложенного алгоритма динамического размещения программных модулей в памяти, как уже отмечалось выше, является учет такого важного ресурса ВС как канал ввода/вывода, учет времени использования программных модулей и расходов на ввод/вывод.
В этой главе также исследуются основные свойства допустимых расписаний и доказывается, что если существует допустимое расписание, то предложенный алгоритм построит его. Доказывается, что алгоритм минимизирует число обменов с внешней памятью.
В четвертой главе приводятся результаты экспериментов с алгоритмом динамического распределения памяти для наиболее общей задачи. Описана программа, которая была составлена для экспериментального исследования влияния основных параметров задания на область существования допустимого расписания, для анализа трудоемкости построения расписания и для изучения основных свойств допустимых расписаний.
В этой главе также обсуждаются вопросы использования предложенных алгоритмов динамического распределения памяти в системах реального времени на ЭВМ типа ЕС ЭВМ.
Формальная постановка задачи
Мы будем рассматривать двухуровневую иерархическую структуру памяти, которая показана на рис. I. Модель состоит из оперативной памяти емкости С и внешней памяти (Ш) п -типов неограниченного объема. Обмен между внешней и оперативной памятью осуществляется с помощью каналов, число которых А/ . Распределение ОП и планирование работы каналов производит программа управления памятью, которая является частью Управляющей программы (УП) системы. памяти, на которую могут быть переписаны единицы информации после обработки; длительности использования fy единиц информации задания J -/X 7! в, V7 М17 М2 и0 J определяются разностью
Видно, что все последовательности задания "J конечной длины конечны, тогда мы говорим о задании конечной длины. Наряду с такими заданиями мы будем рассматривать иногда задания бесконечной длины. В них все составляющие их последовательности будут бесконечными.
Распределение памяти при обязательных вводах при использовании одного канала
Пусть через равные промежутки времени А Г приходят запросы на размещение в памяти новой страницы, т.е. последовательность запросов на память имеет следующий вид: Х= fat, ,-; КС; - \ іЄА СФ Яу } (2-3)
Запись страницы в ОП и перепись ее на внешнюю память осуще-ствляется одним каналом за времена Ъ и 2 соответственно. При этом объемы страниц 1 и времена их использования У; для всех запросов одинаковы.
Опишем алгоритм АІ построения допустимого расписания $ = ?,#, Y,fi, К4} для задания J={X,T& В0} . На основании теорем I, 2 и определения нормализованного расписания будем строить расписание S приведенным. Это означает, что страницы должны загружаться в память в порядке поступления запросов и вектор Е равен вектору УС . Из определения задания (2.3) следует, что в память вводятся разные страницы, следовательно, ввод необходим при каждом запросе на память. Поэтому все компоненты вектора канала по загрузке К равны единице, т.е. К 1=1 . Мы строим приведенное расписание, значит в расписании о выгрузка страниц производится по запросам. Из определения такого расписания при условии, что в начальный момент времен память пуста, следует, что компоненты вектора канала по выгрузке страниц следующие
Моменты ввода Сі с строим по формулам (1.23) определения нормализованного расписания, а моменты вывода Z/ будем стро-ить так, чтобы удовлетворялись условия у/ (1-2) определения расписания с выгрузкой страниц по запросам.
Для построения расписания 5 применим стратегию замещения страниц FIFO , согласно которой удаляется та страница, которая раньше всех поступила в систему. Вектор удаляемых страниц У при такой стратегии будет иметь вид.
Исследование свойств допустимых приведенных расписаний
Пусть для задания J- [УС Т #, А j построено допустимое приведенное расписание $ = { 2 Gj fY R К } , т.е. нормализованное расписание с правильным порядком с выгрузкой страниц по запросам, по следующему правилу. Каждый раз, когда требуемой страницы нет в памяти и память полна, удаляется страница, имеющая наиболее позднее время следующего запроса, причем такая,при удалении которой удовлетворяются условия Y 0 (1-5) определения допустимого расписания. Для ввода и вывода страниц используется один канал.
Для определения основного свойства расписания S , построенного по описанному выше правилу, введем понятие опережающего промежутка. Пусть J = jpc? Т} Q В0\ - задание на использование памяти. Пусть "ік - время запроса на страницу Хк . Опережающим промежутком для страницы Q 9 Q Є Лр О в { oc Hf. .., ос Л от момента времени і к до момента ближайшего запроса , на страницу Q называется разность Л (ік7а) =. -cQ - tKf (З. і)
где LQ = min { і / ОС с = Q , І = K+1, L j і Если такого индекса Cq не существует, то опережающий про - 76 -межуток равен бесконечности, т.е. Л (t 7Q)= = Лемма 6.
Пусть для задания J = рС?Т? &? В0 j существуют два допустимых приведенных расписания S - { }Q ;У, R 7 К J и г- fez Сі]Уг7 Q К \ с числом вводов mL и тг соответственно. Пусть при этом расписания удовлетворяют следующим условиям Ь = Vj j = І, - -дґїк76) д( ,о) т.е. следующий запрос на страницу О после момента времени "$ последний.
Тогда существует допустимое приведенное расписание S = j В б) У7 R К } $ удовлетворяющее условиям f= У/ J (3.2) ЦІ = о число вводов гп3 у которого не больше, чем в расписании S , т.е. справедливо неравенство.
Доказательство.
Доказательство заключается в построении приведенного расписания 5 по расписаниям S и S и доказательстве выполнения условий У 0 (1-5) определения допустимого расписания.
Описание программы и методики численных экспериментов
Программа была составлена для экспериментального исследования алгоритма А5, определения влияния параметров задания на существование допустимого расписания, оценки трудоемкости построенного расписания, а также для анализа основных свойств допустимых расписаний. Написана она на языке АЛТОЛ-60 и реализована на ЭВМ БЭС№-6.
Функции программы следующие:
1. генерация задания;
2. построение допустимого расписания;
3. анализ исследуемых характеристик;
4. дополнительная проверка построенного расписания на допустимость;
5. генерация всех возможных расписаний с проверкой на допустимость;
6. выдача результатов.
Входной информацией для программы являются данные, необходимые для генерации задания. Это следующие параметры: общее число разных страниц А/ ; число запросов в задании L ; максимальное время запроса И СП Mi время ввода и вывода страниц Т ; нижняя и верхняя границы емкости памяти СО и С ; номер реализации У - произвольное целое четырехзначеное число.
Для генерации задания использовались две процедуры 8 U F и RA/W).
Процедура BUF(lfifiO,V) при заданных входных параметрах L » С СО t У , описанных выше, при использовании стандартной процедуры RA NdOM(V) генерации случайных чисел формирует массив Ъ f і 2L ] состояний памяти, показывающий число находящихся в памяти страниц в моменты загрузок и выгрузок.
Процедурой RA ND (СНдАTA,L,N, У, ИСГ/М, В) на основании полученного массива в при заданных входных данных L , А/ , ИСПМ, У проводится заполнение таблицы задания СИ DATA , которая имеет следующий формат п/п номер страницы ос с время запроса памяти -і время окончания использования памяти if I 2 3 4
Для получения последовательности страниц УС в процедуре RAND создается список страниц LTSTP [1 N] . При заполнении таблицы номер страницы sct- случайным образом выбирается или из списка новых страниц /.ISTP или из уже имеющихся в памяти страниц. С помощью процедуры RANI)ОМ случайным образом производится назначение времен запросов и освобождений памяти, не превышающих максимального времени запроса І/ІСП М .
Для построения допустимого расписания по алгоритму А5 используется процедура ЗАГРУЗ (USEDM, С7 ПР7 А/, А/ЬАПР , ОСЬ, СО А/А которая осуществляет выполнение одного запроса на выделение памяти и проводит проверку, необходим ли контроль построенного расписания на допустимость для выполненных требований, число которых есть А/ЪАПР .
Входные параметры С , А/ имеют тот же смысл, что и ранее, а остальные обозначают следующее.
US, Є DM І і с, 0ч 3 J - таблица, отражающая текущее состояние памяти. Она имеет следующий формат признак ввода номера страниц время освобождения время следующего запроса 0 I 2 ПР - целая переменная, принимающая значение нуль или единица. Если ПР - 0, то производится первоначальная загрузка страниц в память, т.е. заполнение памяти до начала выполнения первого запроса, в противном случае производится выполнение очередного требования.
Выходными параметрами являются переменные ОСВ и С О А/Т, принимающие одно из двух значений: нуль или единица. Если переменная ОСВ станет равной нулю, то выполнить запрос на выделение памяти не удалось и допустимого расписания не существует. Если переменной СОА/Т присвоится значение равное единицы, то это значит, что необходимо начать строить новое расписание при новых значениях моментов ввода. Во всех остальных случаях номер запроса Л/ЗАПР увеличивается на единицу.
Процедура ЗАГРУЗ состоит из трех дополнительных процедур ЗАГР, ПОИСК, ВВОД и использует процедуру А/1А/ . Блок-схема процедуры ЗАГРУЗ, поясняющая ее работу, показана на рис. I.
