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

• Автор: Логинова, Ирина Валентиновна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Москва
• Количество страниц: 131 c. : ил

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

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

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

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

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

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

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

Глава II. АНАЛИЗ ЗАДАЧ ДИНАМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ ПАМЯТИ

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

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

при использовании одного канала

§ 2. Распределение памяти при обязательных вводах
при использовании нескольких каналов
§ 3. Распределение памяти для повторяющихся групп
запросов
Глава III. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ ПРИ
НЕПЕРИОДИЧЕСКИХ ЗАПРОСАХ
§ I. Исследование свойств допустимых приведенных
расписаний
§ 2. Алгоритм построения допустимого приведенного
расписания
§ 3. Доказательство правильности алгоритма

ГЛАВА 17. РЕАЛИЗАЦИЯ И ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ
АЛГОРИТМОВ ДИНАМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ
ПАМЯТИ
§ I. Описание программы и методики численных
экспериментов
§ 2. Исследование задания на использование памяти
§ 3. Исследование алгоритма
3.1. Влияние основных параметров на время построения расписания
3.2. Один из способов ускорения поиска
расписания
3.3. Одно из решений проблемы, когда допустимого расписания для задания нет
§ 4. К вопросу о реализации алгоритмов динамического распределения памяти
Заключение
Литература

В настоящее время развитие современной вычислительной тех-
‘ /
ники идет по двум основным направлениям: с одной стороны созда-ние универсальных многомашинных вычислительных комплексов и на базе их сетей ЭВМ, с другой стороны разработка специализированных вычислительных систем (ВС), связанных с конкретными приложениями. В данной диссертации рассматриваются системы, функционирующие в непосредственном взаимодействии с внешней средой, называемые системами реального времени (РВ). Область применения систем РВ очень широка [I, 2, 37 ^. Автоматизированные системы управления технологическими процессами внедрены или разрабатываются во всех отраслях народного хозяйства. Это системы управления атомными реакторами, доменными печами, программные логические контроллеры, станки с программным управлением, система обнаружения дефекта с помощью радиометрического и ультрозвукового контроля, конвейеры, роботы и т.д. К системам РВ относятся системы массового обслуживания, например, резервирование и продажа билетов на самолеты и поезда. Для проведения наблюдений в темпе эксперимента с целью выработки управляющих воздействий и оперативного контроля за течением эксперимента тоже необходимы системы РВ. Примерами таких систем могут служить система автоматизации ядерно-физических экспериментов, система исследования физических процессов и явлений взаимодействия электромагнитного излучения с атмосферой, система наблюдения за радиолокационными и телеметрическими сигналами, сигналами из космоса и т.д.
Под системой, работающей в реальном масштабе времени, понимается система, которая должна обрабатывать поступающую в нее
- ?] V - ^ , J - ,
Доказательство.
Справедливость леммы вытекает из следствий I и 2 леммы 3.
Лемма 5.
Пусть даны две последовательности чисел ф* СС ^ Т9 К1*) и (Ту7 Т? К2 у) , определяемые по формулам (1.34), причем вектора КIу и К2У имеют следующий вид
К1^= { КгУ, . • • , Кс^р 1 ‘ ^а~т ? &}
К2 ~ { К^р ^г'р • » • р О? , *• • у Кс*-т р 1 ]
Тогда для первых (£+*) члена последовательностей (^{Ъ^рТр К1*) и С^г(г^рТ, К2*) справедливы следующие неравенства
?/ ' ?/ Ъ 0 > (1*40)
Доказательство.
Л
Рассмотрим две подпоследовательности чисел £1 =■ £ ^^ и (£г = ( }> К-Т+г/и последовательностей С
Ту К1>) и <£г ( г УР Тр К2У) . Применив к ним следствие 2 леммы 3, получим следующие неравенства
- ?/ гу+?е,
Из справедливости предыдущего неравенства и из формул (1.34) следует, что выполнятся следующие неравенства
I.1 - 1;г ^ ТУ ■'-’£* ;-с+2,Ь-* (1*41)
2 «/ " 7
Теперь проанализируем подпоследовательности ц1 - { I и С£г - {е- С-1-1 последовательностей (гу Т? К1У) и <^г [ ТУр Т> К 2 у) . Для этого рассмотрим следующие случаи соотношения между 1^2. * и *