Моделирование ядра многопроцессорных операционных систем с аппаратной поддержкой

Введение 5
1 Обзор методов планирования 10
1.1 Временные характеристики существующих систем реального времени 10
1.1.1 Время реакции системы (латентность) 10
1.1.2 Время переключения контекста 10
1.1.3 Дедлайн 11
1.1.4 Джиттер 11
1.2 Существующие алгоритмы приоритетного планирования 11
1.2.1 Алгоритмы, основанные на приоритетах (классификация по принципу
выбора процесса на выполнение из очереди) 11
1.2.2 Смешанные алгоритмы планирования (квантование с приоритетами) 13
1.3 Алгоритмы, основанные на приоритетных очередях задач 14
1.3.1 Разделение времени 15
1.4 Анализ схем аппаратного приоритетного выбора готовых к выполнению задач 18
1.4.1 Схема приоритетного выбора «полное дерево» 20
1.4.2 Схема последовательного приоритетного выбора 21
1.4.3 Схема гибридного приоритетного выбора 22
1.5 Выводы 24
2 Моделирование алгоритмов приоритетного планирования на языке
недетерминированных автоматов 25
2.1 Возможности языка НДА для формального описания алгоритмов
управления параллельными процессами и ресурсами 25
2.2 Формализация алгоритмов управления параллельными процессами на
основе использования механизма «рандеву» 32
2.3 Формализация алгоритмов управления параллельными процессами с использованием механизма монитора и согласующего кольцевого буфера ... 37
2.4 Выводы 44
3 Аппаратная реализация алгоритмов приоритетного планирования 46
3.1 Проблемы управления ресурсами и процессами в многопроцессорных
системах 46
3.2 Структура аппаратного планировщика с глобальной очередью 56
3.3 Моделирование аппаратного планировщика с глобальной очередью на
языке VHDL 59
3.4 Структура аппаратного планировщика с локальными очередями 72
3.5 Моделирование аппаратного планировщика с локальными очередями на
языке VHDL 74
3.6 Получение временных диаграмм и временных характеристик 84
3.7 Выработка критериев сравнительной оценки планировщиков 92
3.8 Выводы 96
Заключение 97
Список используемых источников 99
Приложение А Модуль блока генерации задач 101
Приложение B Модуль блока управления очередью планировщика с глобальной очередью 104
Приложение C Модуль блока приоритетной очереди планировщика с глобальной очередью 107
Приложение D Модуль блока синхронизации и назначения задач планировщика с глобальной очередью 121
Приложение E Модуль блока выбора процессора планировщика с глобальной очередью 128
Приложение F Модуль блока процессора 131
Приложение G Модуль блока назначения задач планировщика с локальными очередями 134
Приложение H Модуль блока локального диспетчера с приоритетной очередью планировщика с локальными очередями 137
Приложение I Модуль выбора очереди планировщика с локальными очередями
151
Приложение J Презентация 153

Купить

При разработке и совершенствовании вычислительных систем (ВС) необходимо проводить исследования ее характеристик. Для изучения характеристик ВС применяют программные модели, не являющиеся физическим устройством, а описанные данными и алгоритмами в памяти ЭВМ. Следовательно, их построение и изменение производится без финансовых затрат.
Проблема эффективной диспетчеризации пакетов задач является одним из наиболее важных аспектов эффективного использования вычислительных ресурсов при распараллеливании вычислительного процесса на уровне задач. Использование оптимальных или, по крайней мере, приближенных расписаний для реализации крупных пакетов задач на многопроцессорных и многомашинных ВС позволяет сократить время исполнения таких пакетов и уменьшить при этом затраты машинного времени.
Таким образом, разработка и исследование различных методов, моделей и алгоритмов, позволяющих строить эффективные расписания для различных типов пакетов задач и структур параллельных ВС приобретает особую актуальность.
В данной работе предлагается метод выбора приоритетного планировщика задач для встроенных многоядерных систем реального времени, основанный на имитационных моделях массового обслуживания, который позволяет оценивать как характеристики производительности планировщиков задач, так и их функционирование.
Задача планирования процессов в многопроцессорной системе, в отличие от однопроцессорной, является двумерной. В период работы функции назначения задачи осуществляется функция выделения целевого процессора, вследствие чего возникают дополнительные издержки времени. Помимо этого, в планировщике задач с разделением во времени формируется процесс перезагрузки кэш-памяти, который взаимосвязан с переключением задач, когда прерванная задача с достаточно высокой вероятностью способна быть направлена для продолжения обслуживания в иной процессорный узел. Данный процесс повышает частоту кэш-промахов, и в абсолютно любом случае отрицательно воздействует на производительность многопроцессорной системы. Другое противоречие в диспетчерах задач с разделением в пространстве, которое требуется разрешить, взаимосвязано с тем, что автоматическое поддержание различного уровня нагрузки процессорных узлов невозможно. Решение представленной задачи лежит в плоскости принудительного обеспечения баланса методами планировщика/диспетчера, что в любом случае порождает дополнительные временные расходы на исполнение определенной программы балансирования. Представленные выше факторы неизбежно формируют рост трудности программной реализации ядра операционных систем, приводят к уменьшению общей производительности многопроцессорной системы, а помимо этого уменьшают надежность и безопасность.
Во время обращения к критическим ресурсам операционной системы, а помимо этого и в процессе планирования и диспетчеризации задач к данным ресурсам возникают очереди процессов, которые ожидают выполнения иных процессов. По этой причине для оценки вероятностно-временных характеристик многопроцессорных систем применяют методы теории массового обслуживания.
Большая часть задач проектирования многопроцессорных вычислительных систем связаны с распределением ресурсов среди конкурирующих требований, притом, что моменты возникновения данных требований носят случайный характер. Это обстоятельство приводит к невозможности предсказать времена выполнения задач в многопроцессорных системах, что особенно важно для систем реального времени. Решением данных проблем выступает аналитическое, имитационное и функционально¬логическое моделирование, дающее возможность ускорить процесс проектирования, в частности, аппаратных планировщиков задач в составе ядра специализированных многопроцессорных операционных систем, а также уменьшить себестоимость проекта. Представленные аспекты обуславливают актуальность выбранной темы исследования.
Объект исследования - алгоритмы планирования и диспетчеризации задач в многопроцессорных вычислительных системах.
Предмет исследования - математическое и функционально-логическое моделирование планировщиков/диспетчеров задач в составе ядра многопроцессорных операционных систем с использованием языка недетерминированных автоматов (НДА), систем массового обслуживания и языка моделирования аппаратуры VHDL.
Цель данной работы - получение временных характеристик и сравнительная оценка планировщиков/диспетчеров задач с аппаратной реализацией.
С целью достижения поставленной цели в диссертационной работе решаются следующие задачи:
1) разработка автоматной модели на основе языка НДА и на её основе VHDL-модели приоритетного планировщика/диспетчера задач и оценка характеристик аппаратной реализации;
2) разработка имитационной модели приоритетного планировщика/диспетчера задач для получения его вероятностно-временных характеристик;
3) разработка функционально - логической модели планировщика/диспетчера задач для оценки возможности реализации аппаратными средствами;
4) проведение вычислительных экспериментов с использованием разработанных моделей.
Методы исследований. Для того чтобы решить поставленные задачи в диссертационной работе применены методы:
- теории недетерминированных автоматов.
- теории аналитического и имитационного моделирования;
- теории вероятностей;
Научная новизна работы состоит в следующем:
1) разработаны на основе языка НДА автоматные модели приоритетных планировщиков/диспетчеров задач с разделением времени с локальными и глобальными очередями в составе многопроцессорной системы.
2) созданы на основе НДА модели VHDL - программы аппаратной реализации планировщиков/диспетчеров задач с разделением времени с локальными и глобальными очередями в составе многопроцессорной системы и произведена оценка характеристик этих моделей;
3) разработан программный модуль сбора статистики в составе VHDL - программы для оценки вероятностно-временных характеристик подсистемы «диспетчер задач - процессорный узел».
Практическая значимость работы.
Применение предложенных аналитической и программной моделей обеспечивает сравнительную оценку временных характеристик планировщика/диспетчера задач на этапе эскизного проектирования, без проведения дорогостоящих физических экспериментов.
Реализация и внедрение результатов работы. Методы моделирования диспетчеров задач многопроцессорных систем будут применены в учебном процессе кафедры «Вычислительная техника» Пензенского государственного университета при осуществлении основной образовательной программы по дисциплинам «Вычислительные системы» для магистрантов, которые обучаются по направлению «Информатика и вычислительная техника».
Достоверность результатов работы подтверждается имитационным моделированием, применением известных методов математического моделирования, а помимо этого докладами на научных конференциях и публикацией в научных журналах.
На защиту выносятся.
1. Алгоритмы приоритетного планирования и диспетчеризации с глобальной и локальной очередями задач в составе многопроцессорных операционных систем.
2. Программный комплекс, включающий в себя VHDL-программу функционально-логического моделирования для оценки функционирования, а также программу имитационного моделирования и определения вероятностно-временных характеристик многопроцессорных приоритетных планировщиков задач.
3. Результаты комплексных исследований вероятностно-временных характеристик планировщиков задач с использованием разработанных математических методов и комплекса программ.

Купить