Эффективные алгоритмы для операционных систем, поддерживающих распределенную обработку и мягкое реальное время

• Автор: Гусев, Игорь Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Томск
• Количество страниц: 144 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

ГЛАВА 1. ОПЕРАЦИОННЫЕ СИСТЕМЫ ОБЗОР

1.1. ОБЛАСТИ ПРИМЕНЕНИЯ ОПЕРАЦИОННЫХ СИСТЕМ.

1.1.1. ОС для прикладных задач

1.1.2. ОС для многопроцессорных систем

1.1.3. Сетевые ОС.

1.1.4. ОС для параллельных вычислительных систем

1.2. КЛАССИФИКАЦИЯ ЗАДАЧ И ОПЕРАЦИОННЫХ СИСТЕМ

1.2.1. Классы задач и операционных систем.

1.2.2. Выгружаемые и невыгружаемые ОС.

1.2.3. Монолитные и модульные ОС
1.2.4. Платформенно зависимые и независимые ОС
1.3. ВЗАИМОДЕЙСТВИЕ ПОЛЬЗОВАТЕЛЕЙ С ОС
1.3.1. Удаленный терминал.
1.3.2. Взаимодействие с консоли.
1.3.3. Удаленный рабочий стол.
1.4. ТРЕБОВАНИЯ К УНИВЕРСАЛЬНОЙ ОС
1.4.1. Общие цели и свойства
1.4.2. Планирование процессорного времени.
1.4.3. Модульность операционных систем
1.4.4. Взаимодействие с ОС
1.4.5. Алгоритмические проблемы.
1.5. ВЫВОДЫ О НАПРАВЛЕНИЯХ РАБОТ
ГЛАВА 2. СПРАВЕДЛИВОЕ ПЛАНИРОВАНИЕ ПРОЦЕССОРНОГО ВРЕМЕНИ.
2.1. ВВЕДЕНИЕ.
2.2. ИЗВЕСТНЫЕ АЛГОРИТМЫ ПЛАНИРОВАНИЯ.
2.2.1. Требования эффективности алгоритма.
2.2.2. Алгоритмы планирования.
2.3. АЛГОРИТМ ДРЕВОВИДНОГО ПЛАНИРОВАНИЯ.
2.3.1. Общий алгоритм планирования
2.3.2. Система классов приоритетов
2.3.3. Система классов приоритетов с экспоненциальной зависимостью
2.3.4. Алгоритмы работы с системой классов
2.3.5. Характеристики алгоритма.
2.4. КОМБИНИРОВАНИЕ С ИЗВЕСТНЫМИ АЛГОРИТМАМИ
2.5. ВЫВОДЫ.
ГЛАВА 3. ОРГАНИЗАЦИЯ ЭФФЕКТИВНОГО ВЗАИМОДЕЙСТВИЯ ОБЪЕКТОВ ЯДРА
3.1. ВВЕДЕНИЕ.
3.2. БАЗОВЫЕ ОБЪЕКТЫ И ИХ ВЗАИМОДЕЙСТВИЕ
3.2.1. Древовидные взаимосвязи между объектами
3.2.2. Основные типы доступа к объектам.
3.3. ВСПОМОГАТЕЛЬНЫЕ ОБЪЕКТЫ
3.3.1. Способы взаимодействия.
3.3.2. Синхронизация и борьба с тупиками
3.4. МОДУЛЬНЫЙ ПОДХОД К РЕАЛИЗАЦИИ ЯДРА.
3.5. АКТИВНЫЙ ИНТЕРФЕЙС.
3.5.1. Логическая структура интерфейса
3.5.2. Алгоритмы реализации функций интерфейса
3.6. ЭФФЕКТИВНОЕ ФУНЦИОНИРОВАНИЕ КЭШИРУЕМЫХ БЛОКОВЫХ УСТРОЙСТВ В ОС РВ.
3.6.1. Связь задержки и блокировки ресурсов.
3.6.2. Обработка блоковых запросов
3.6.3. Алгоритмы функционирования.
3.7. ВЫВОДЫ.
ГЛАВА 4. РАСШИРЕННАЯ ТЕРМИНАЛЬНАЯ ПОДСИСТЕМА
4.1. ВВЕДЕНИЕ.
4.1.1. Терминалы в ЦМХ системах.
4.1.2. Терминалы в семействе ОС Vi
4.1.3. Требования к универсальной терминальной подсистеме.
4.2. ПОНЯТИЕ РАСШИРЕННОГО ТЕРМИНАЛА.
4.2.1. Физический терминал
4.2.2. Виртуальный терминал
4.2.3. Регистрация пользователя на терминале.
4.2.4. Первичный локальный терминал
4.3. АЛГОРИТМЫ ФУНКЦИОНИРОВАНИЯ
4.3.1. Поток обновления
4.3.2. Установка активного виртуального терминала
4.3.3. Захват и освобождение терминала.
4.3.4. Создание, удаление и наследование виртуального терминала
4.4. СРАВНЕНИЕ С АНАЛОГАМИ.
4.5. ВЫВОДЫ.
ГЛАВА 5. ОПЕРАЦИОННАЯ СИСТЕМА НИКОС
5.1. ОБЩАЯ ХАРАКТЕРИСТИКА
5.2. АРХИТЕКТУРА СИСТЕМЫ.
5.3. СТРУКТУРА ЯДРА СИСТЕМЫ
5.3.1. Объекты ядра
5.3.2. Активные интерфейсы
5.3.3. Расширенная терминальная подсистема
5.3.4. Файловая и блоковая подсистемы.
5.3.5. Модуль безопасности
5.3.6. Подсистемы запуска приложений
5.4. ПРИКЛАДНОЙ ПРОГРАММНЫЙ УРОВЕНЬ
5.5. СРАВНЕНИЕ ОС НИКОС С ДРУГИМИ ОС.
5.6. ВЫВОДЫ
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Научно-практическая конференция «Наука и образование: пути интеграции», , г. Анжеро-Судженск. Второй всероссийский симпозиум по прикладной и промышленной математике, , г. Йошкар-Ола. Всероссийская научно-практическая конференция «Новые технологии и комплексные решения: наука, образование, производство», , Кемерово. Проведенный в первой главе анализ функциональности существующих операционных систем и их базовых алгоритмов позволил классифицировать как сами системы, так и алгоритмы, а также помог выявить свойственные им недостатки. В операционных системах общего назначения выявлен ряд узких мест, которые значительно ограничивают показатели этих систем при использовании для решения широкого круга задач. Это связанно с высокой трудоемкостью применяемых в них алгоритмов, высокими издержками при блокировках ресурсов и неустойчивой работой в условиях изменения нагрузки. В некоторых случаях применяемые алгоритмы не позволяют реализовать недавно возникшие требования. Основными такими задачами являются задачи планирования процессорного времени с учетом пользователей, распределения ресурсов и поддержки модульности. В этой главе исследуется возможность построения операционной системы широкого применения, начиная от рабочих станций и серверных платформ, и, заканчивая встроенными системами и системами реального времени. Сформулированы требования к современной операционной системе. Во второй главе рассматривается задача распределения процессорного времени. Проводится сравнительный анализ существующих алгоритмов планирования. Предлагается алгоритм древесного планирования с применением системы классов элементов для нового метода выбора элемента, где используются статические приоритеты. Предлагаются модификации данного алгоритма для линейной и экспоненциальной зависимости приоритетов. Трудоемкость полученных алгоритмов установки задачи в очередь, удаления задачи из очереди и выбора задачи для выполнения составляет 0(1) и не зависит от числа планируемых задач. В третьей главе рассматривается модульный принцип проектирования и реализации ядра операционной системы. Исследуется проблема блокировки объектов ядра и межмодульной блокировки. Предлагаются синхронизации использования разделяемых ресурсов, обеспечивающие минимальное время между блокированием ресурсов и их разблокированием. Исследуется взаимное влияние на блокировки нескольких процессоров в вычислительных системах с симметричной многопроцессорностью. Предлагается структура и алгоритмы функционирования активного интерфейса, который позволяет выполнять замену модулей без удаления зависимых модулей. Исследуется важная задача распределения блоковых ресурсов и их кэширования. Блоковые ресурсы - это ресурсы, которые не требуются целиком, а только частями - блоками. Классическим примером блоковых ресурсов могут служить дисковые накопители. Предлагаются алгоритмы функционирования данной подсистемы, которые в этой главе исследуются на оказание минимальной задержки при блокировке очередей, что является важным критерием для систем реального времени. В четвертой главе исследуется задача удаленного доступа к вычислительной системе. Анализируются подходы к реализации удаленного доступа в существующих операционных системах, выявляются достоинства и недостатки различных подходов. Предлагается расширенная терминальная система, где понятие терминала значительно расширяется: в него включаются дополнительные устройства, такие как: дисковод, принтер, устройство считывания компакт дисков и т. Предлагается метод виртуализации терминальных устройств и алгоритмы его реализации. На основе полученных теоретических результатов создана универсальная операционная система «НИКОС», рассмотренная в пятой главе. Для построения использовался модульный подход, позволяющий обеспечить новое качество системы при выборе тех или иных компонент ядра. Несмотря на новые подходы и реализацию новых алгоритмов, в операционной системе поддержаны основные стандарты программирования и интерфейсы, что позволяет использовать уже существующее программное обеспечение.