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

• Автор: Овсянкин, Борис Петрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 118 c. : ил

ГЛАВА I. МЕТОДЕ ПОСТРОЕНИЯ БАЗИСА ДОПУСТИМЫХ РАСПИСАНИЙ ДОЯ ОДНОСТАДИЙНЫХ ДЕТЕРМИНИРОВАННЫХ СИСТЕМ

ОБСЛУЖИВАНИЯ

§ I. Основные определения

§ 2. Полные системы обслуживания

§ 3. Базис допустимых расписаний для системы обслуживания с одним прибором

§ 4. Базис допустимых расписаний для системы обслуживания с несколькими параллельными приборами
ГЛАВА II. АЛГОРИТМЫ СОСТАВЛЕНИЯ РАСПИСАНИЙ НА ОСНОВЕ МЕТОДОВ ПОСТРОЕНИЯ БАЗИСА ДОПУСТИМЫХ РАСПИСАНИЙ

§ I. Активные расписания

§ 2. Верхняя оценка числа прерываний в оптимальном

расписании

§ 3. Оптимизация расписаний с директивными сроками

§ 4. Множество допустимых расписаний для системы обслуживания с несколькими параллельными приборами
ГЛАВА III. РАСЧЁТ ХАРАКТЕРИСТИК И ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
РЕАЛЬНОГО ВРЕМЕНИ
§ I. Задачи расчёта характеристик и планирования вычислительного процесса при проектировании вычислительных систем реального времени

§ 2. Расчёт быстродействия процессора вычислительной
системы реального времени
§ 3. Оценка количества ресурсов, необходимых для управления объектом в реальном времени
§ 4. Результаты вычислительного эксперимента
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
Потребности в высоком быстродействии и большом объёме памяти, предъявляемые к современным вычислительным системам (ВС), в настоящее время значительно опережают возможности вычислительной техники. В связи с этим задача разработки методов эффективного использования ресурсов ВС весьма актуальна.
Важное значение эта проблема имеет для ВС, применяемых для управления различными техническими объектами в реальном времени, поскольку к таким системам обычно предъявляются требования высокой надёжности при жёстких ограничениях на использование вычислительных ресурсов.
Поэтому при проектировании ВС реального времени возникает целый ряд задач, связанных с расчётом различных временных характеристик и характеристик основных ресурсов ВС, необходимых для управления объектом в реальном времени. Среди этих задач весьма важными являются расчёт необходимого быстродействия процессора, оценки потребностей в основных ресурсах ВС и построение расписаний выполнения комплекса программ, осуществляющих обработку информации и управление объектом в реальном времени.
В настоящей работе эти задачи рассматриваются главным образом для однопроцессорных ВС реального времени с учётом основных ресурсов ВС таких, как время центрального процессора (ЦП), основная память, вспомогательная память, периферийные устройства.
Вычислительные системы реального времени расчитаны на автоматический приём и обработку информации, поступающей в процессе управления различными техническими объектами, и вы-

Поскольку последовательность чисел {а']| , ] = •••У*
монотонно возрастает и содержит не более М членов, а функция ^к(х) неубывает на полуинтервале (о, А'Р(ф)] , то для нахождения числа р из (4лз) достаточно О (М ^сг М) операций.
Нетрудно видеть, что на полуинтервале (б-р, 0-рм] функция УЦх) линейна, т.е. для нахождения ос* из (4.11), (4.134) также достаточно О"(М -Оод М ) операций.
Следовательно, для нахождения всех чисел хк , ке Б требуется не более &(ь/М&>^М) операций, значит, и для нахождения из (4Л0) достаточно &(ЫМ^ М)
операций.
Таким образом, для построения любого кортежа (|) £ ]-] (5) достаточно операций, а для вычисления Д
требуется б(ЫМХо^М) операций. Следовательно, для построения любого д! -базисного расписания достаточно
операций.
Оценим число операций, выполненных при построении любого расписания Р^9(п) методом построения базиса допустимых расписаний.
Пусть р* £ $ , а{) , тогца при известных М0* »
К.€ Б для нахождения всех чисел м^(р, и), & (г. л)
согласно (4.б) достаточно 0(м) операций. Для нахождения
чисел требуется & (Ь/1) операций.
Следовательно, если расписание Р е 2Р(17Ь) построено за к назначений, то число выполненных при этом операций не превосходит б (Ы1 + к Ь/М 'код. м)
Пусть Ум (П) - множество всех допустимых расписаний для системы обслуживания /П таких, что при каж-