Разработка точных и приближенных алгоритмов составления расписаний и синтеза систем жесткого реального времени

• Автор: Гуз, Денис Сергеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 132 с. : ил.

1.1 Точный алгоритм.

1.2 Эвристические алгоритмы.

1.2.1 Эвристика 1.

1.2.2 Эвристика 2.

1.3 Сравнительный анализ алгоритмов Эвристика 1 и Эвристика 2.

Глава 2. Переключения с затратами. Связи полный граф. Отсутствие ограничений по памяти.

2.1 Алгоритм Эвристика П1.

2.2 Алгоритм Эвристика П2.

2.3 Сравнительный анализ алгоритмов Эвристика П1 и Эвристика П2.

2.3.1 Испытания алгоритмов в случае первой модели образования временных затрат на прерывания
2.3.2 Испытания алгоритмов в случае второй модели образования временных затрат на прерывания
2.3.3 Испытания алгоритмов в случае третьей модели образования временных затрат на прерывания
Глава 3. Ограничения по памяти и скорости загрузки. Связи полный граф. Общий директивный интервал.
3.1 Однопроцессорный случай.
3.1.1 Постановка задачи и предварительные соображения.
3.1.2 Построение оптимального порядка выполнения работ
3.1.3 Алгоритм построения однопроцессорного расписания
3.2 Многопроцессорный случай
3.2.1 Постановка задачи.
3.2.2 ЫРтрудность
3.2.3 Эвристический алгоритм
3.2.4 Анализ предложенного алгоритма
Глава 4. Ограничения по памяти. Произвольный граф связей. Переключения с затратами. Время дискретные такты.
4.1 Постановка задачи.
4.2 Построение сети
4.3 ЫРтрудность.
4.4 Необходимые и достаточные условия существования допустимого расписания.
4.5 Алгоритм построения расписания
Глава 5. Задача синтеза
5.1 Отсутствие ограничений на память процессоров
5.1.1 Постановка задачи.
5.1.2 Построение области допустимых параметров процессоров
5.2 Учет ограничений на память процессоров
5.2.1 Постановка задачи
5.2.2 Построение области допустимых параметров процессоров
Заключение
Список использованных источников


Далее рассматривается ранее неисследованная задача синтеза системы реального времени в случае ограничений по объему памяти процессоров, строится система неравенств, связывающая искомые производительности процессоров и их объемы памяти с параметрами работ, являющаяся необходимым и достаточным условием для существования в рассмотренной системе допустимого расписания с прерываниями, приводятся методы решения возникающих здесь различных оптимизационных задач. В Заключении формулируются основные результаты работы и рассматриваются направления развития предложенных подходов для решения задач поиска допустимого расписания и синтеза систем жесткого реального времени. Постановка задачи. Рассматривается вычислительная система, состоящая из т процессоров. Каждый процессор у 1 ,. Имеется п работ, каждая из которых определяется своим директивным сроком начала г, и директивным сроком окончания другими словами, директивным интервалом г,, ,, 1,. V,, который необходимо загрузить в процессор для ее выполнения. А. Время загрузки данных 1й работы на уй процессор равно . Все параметры задачи полагаются целыми. Загрузка данных может производиться на каждом процессоре одновременно с выполнением какоголибо задания. Память может быть загружена частично или полностью некоторыми данными уже в начальный момент времени. Удаление данных из памяти происходит мгновенно сразу после выполнения соответствующей работы. В фиксированный момент времени каждая работа может выполняться не более чем одним процессором, и каждый процессор может выполнять не более одной работы. При выполнении работ допускаются прерывания и переключения с одного процессора на другой.