Введение 4
1. Формализация и моделирование алгоритмов управления процессами в
многопроцессорных системах 9
1.1. Формализация классической задачи «о работе парикмахерской» на основе
НДА 9
1.2. Проблема спящего парикмахера и задача о работе парикмахерской 9
Задача о работе парикмахерской 11
1.3. Формализация алгоритма управления процессами в задаче «о спящем
парикмахере» на основе НДА 19
1.4. Формализация алгоритма управления процессами в задаче «работа
парикмахерской» на основе НДА 23
1.5. Структура аппаратного планировщика/ диспетчера с глобальной очередью
задач 29
Выводы к первой главе 42
2. Аналитическое моделирование планировщика/диспетчера задач 43
2.1 Анализ методов планирования и диспетчеризации задач современных
операционных систем 43
2.2 Аналитическое моделирование диспетчеров задач с однородным входящим
потоком задач, бесприоритетной очередью с ограничением числа мест 52
2.3 Аналитическое моделирование планировщиков/диспетчеров задач с
неоднородным потоком задач 57
2.4 Расчет характеристик планировщиков/диспетчеров задач с бесприоритетным
обслуживанием и ограничением числа мест в очередях 64
3. Разработка программы расчета характеристик стохастических сетей массового
обслуживания 73
3.1. Алгоритм расчета характеристик систем и сетей массового обслуживания 73
3.2. Алгоритм расчета характеристик многоканальных СМО с приоритетным
обслуживанием 78
3.3. Структура входных и выходных данных 81
3.4 Разработка алгоритмов решения задачи 82
3.5 Описание программы 87
Заключение 91
Список литературы 92
ПриложениеА
Для функционирования передовых вычислительных систем в режиме реального времени, практически регулярно применяют многопроцессорные, а помимо этого и многоядерные архитектуры, которые создаются вместе с решением задач управления процессами и ресурсами с использованием диспетчеризации. Эффективность работы функций диспетчеров задач прибывает в зависимости от скорости переключения процессов. Частота вызова приложениями планировщика и диспетчера, в многопроцессорной системе существенно выше, нежели в однопроцессорных системах, и именно по данной причине обращение к общим ресурсам формируют конфликтные ситуации. Значительно чаще подобное явление представляется возможным в многоядерных системах на кристалле, которые обладают потенциально высокой производительностью. Традиционная программная реализация диспетчеров задач далеко не всегда предоставляет требуемую производительность системы. В соответствии с данной причиной, в процессе проектирования ядра операционной системы требуется выбирать более эффективные технические средства его разработки.
Задача диспетчеризации процессов в многопроцессорной системе выступает в качестве двумерной. В период работы функции назначения задачи осуществляется функция выделения целевого процессора, вследствие чего возникают дополнительные издержки времени. Помимо этого, в диспетчере задач с разделением во времени формируется процесс перезагрузки кэш-памяти, который взаимосвязан с переключением задач, когда прерванная задача с достаточно высокой вероятностью способна быть направлена для продолжения обслуживания в иной процессорный узел. Данный процесс повышает частоту кэш -промахов, и в абсолютно любом случае отрицательно воздействует на производительность многопроцессорной системы. Другое противоречие в диспетчерах задач с разделением в пространстве, которое требуется разрешить, взаимосвязано с тем, что автоматическое поддержание различного уровня нагрузки процессорных узлов невозможно. Решение представленной задачи лежит в плоскости принудительного обеспечения баланса методами планировщика/диспетчера, что в любом случае порождает дополнительные временные расходы на исполнение определенной программы балансирования. Представленные выше факторы неизбежно формируют рост трудности программной реализации ядра операционных систем, приводят к уменьшению общей производительности многопроцессорной системы, а помимо этого уменьшают надежность и безопасность.
Во время обращения к критическим ресурсам операционной системы, а помимо этого и в процессе планирования и диспетчеризации задач к данным ресурсам возникают очереди процессов, которые ожидают выполнения иных процессов. Согласно данной причине для аналитического описания многопроцессорной системы, зачастую, используется теория массового обслуживания. В подобном случае математическая модель многопроцессорной системы представляется в качестве стохастической сети массового обслуживания, в которой роли узлов берут на себя модели ресурсов, а заявки - запросы на выполнение пользовательских программ.
Преимущественно большая часть задач проектирования многопроцессорных вычислительных систем взаимосвязаны с распределением и диспетчеризацией ресурсов среди конкурирующих требований, притом, что моменты возникновения данных требований носят случайный характер. Правильным решением данных задач выступает математическое моделирование многопроцессорных систем, которые включают в себя диспетчеры задач, что предоставит возможность ускорить процесс проектирования диспетчеров для специальных многопроцессорных систем, а помимо этого уменьшить себестоимость проекта. Представленные аспекты обуславливают актуальность выбранной темы исследования.
Объект исследования - планировщики и диспетчеры задач в многопроцессорных вычислительных системах.
Предмет исследования - математическое и функциональное моделирование планировщиков/диспетчеров вычислительных процессов с использованием языка недетерминированных автоматов (НДА), разомкнутых систем и сетей массового обслуживания и на языке моделирования аппаратуры VHDL.
Цель данной работы - получение временных характеристик и сравнительная оценка планировщиков/диспетчеров задач с программной и аппаратной реализацией...
Разработана программа для расчета вероятностно-временных характеристик стохастических сетей массового обслуживания и предназначенная для оценки производительности функций ОС. Программа обеспечивает возможность расчета сетей массового обслуживания, содержащих системы массового обслуживания с ограниченной длиной очереди, систем массового обслуживания (как одноканальных, так и многоканальных) с приоритетами, а также расчет сети по нескольким одновременно варьируемым исходным параметрам.
Разработана программа для расчета характеристик стохастических сетей массового обслуживания (например, многопроцессорных систем с диспетчерами задач и другими ресурсами), кроме анализа характеристик многопроцессорных систем выполняет ввод исходных данных и вывод результата. Созданные в программе модели вычислительных систем можно сохранять на диск и загружать сохраненные ранее проекты в виде файлов специализированного формата.
