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

На правах рукопису

Гусев Игорь Сергеевич

ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ДЛЯ ОПЕРАЦИОННЫХ СИСТЕМ, ПОДДЕРЖИВАЮЩИХ РАСПРЕДЕЛЕННУЮ ОБРАБОТКУ И МЯГКОЕ РЕАЛЬНОЕ ВРЕМЯ

05.13.11- «Математическое и программное обеспечение вычислительных машин, комплектов и компьютерных сетей»

Автореферат диссертации на соискание ученой степени кандидата технических наук

Томск - 2004

Работа выполнена в Томском государственном университете

Научный руководитель:

Доктор технических наук, профессор Сущенко СП.

Официальные оппоненты:

Доктор технических наук, профессор Матросова А.Ю. Кандидат технических наук, Гриценко Ю.Б.

Ведущая организация: Томский государственный политехнический университет

Защита состоится 7 октября 2004 г. в 10:30 на заседании диссертационного совета Д 212.267.08 при Томском государственном университете (634050, г. Томск, пр. Ленина, 36).

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета.

Отзывы на автореферат просьба высылать по адресу: 634050, г. Томск, пр. Ленина 36, Томский государственный университет, ученому секретарю университета Буровой Н.Ю.

Автореферат разослан « 2 » сентября 2004 г.

Ученый секретарь ////

Диссертационного Совета, д.т.н., доцент /шУ/ A.B. Скворцов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Применение операционных систем в новых областях, таких как кластерные вычисления, системы реального времени, встроенные система, приводит к необходимости пересмотра функциональности операционных систем и алгоритмов, реализующих эту функциональность. В данной работе проводится исследование существующих алгоритмов функционирования операционных систем, выявляются их преимущества и недостатки, а также предлагаются более эффективные способы решения задач управления ресурсами вычислительной системы.

Целью работы является разработка методов повышения эффективности операционных систем, исследование возможности расширения их функций, а также реализация предложенных методов в модульной универсальной операционной системе, предназначенной как для индивидуального использования, так и в качестве серверной платформы, а также в системах реального времени и встроенных системах.

В рамках вышеуказанной цели выделяются следующие задачи.

1. Разработать подход к планированию задач и реализующий его алгоритм для прогнозируемого распределения процессорного времени при наличии нескольких участников, использующих вычислительную систему, и нескольких задач мягкого реального времени, которые можно было бы применить в выгружаемых операционных системах, в том числе и ВС с SMP-архитектурой.

2. Разработать базовый алгоритм распределения ресурсов по запросам от многих участников системы к нескольким устройствам в рамках всей вычислительной системы. Для алгоритма предъявляются следующие требования: не оказывать значительного не прогнозируемого влияния на остальную часть вычислительной системы, возможность использования в невыгружаемых операционных системах, возможность использования в вычислителях с SMP-архитектурой и проведения оптимизации очередей запросов с целью увеличения эффективности обслуживания.

3. Разработать подход к реализации расширенной терминальной подсистемы и основные организующие алгоритмы, удовлетворяющие следующим требованиям: возможность временного отключения от системы, возможность перехода на другой терминал, независимость от физических и технических возможно-

ЙОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

стей терминала, устойчивость работы при обрыве канала связи с терминалом.

4. Разработать программное обеспечение, реализующее предложенные алгоритмы и подходы.

Методы исследования. При выполнении диссертационной работы использовались системный анализ, теория построения операционных систем, методы алгоритмизации и построения эффективных управляющих структур данных, практические эксперименты. Научная новизна работы состоит в следующем:

1. Разработан метод планирования задач с прогнозируемым распределением времени процессоров, при интенсивном изменении состояния готовности последних. Данный метод в отличие от известных учитывает при распределении процессорного времени принадлежность потоков процессам, а процессов -пользователям, тем самым, исключая взаимное влияние процессов разных пользователей и разных типов друг на друга.

2. Предложена новая схема взаимодействия основных объектов ядра операционной системы для эффективного выполнения блокировок в выгружаемых системах, основанная на иерархических взаимосвязях между объектами. В отличие от широко распространенных одноранговых этот подход позволяет минимизировать время блокирования локальных объектов, в то время как необходимость блокировать глобальные объекты возникает значительно реже.

3. Предложен и реализован механизм активных интерфейсов для удобного манипулирования модулями ядра, позволяющий захватить ресурс еще до появления его в системе, а также убрать ресурс из системы, даже если он используется. Данный механизм в отличие от существующих позволяет «на лету» производить замену модулей (например, драйверов устройств), не внося значительных изменений в работу системы в целом.

4. Предложен алгоритм распределения частично разделяемых ресурсов для выгружаемых операционных систем с гарантированным максимальным временем пребывания в критических участках, основанный на использовании АВЛ-дерева. В отличие от классических алгоритмов, которые минимизируют среднее время и ничего не гарантируют в наихудшем случае, когда время работы потенциально может быть неопределенно большим, данный алгоритм гарантирует фиксированное время работы в наихудшем случае, что позволяет применять его в системах реального времени.

5. Предложена система расширенных терминалов для взаимодействия пользователя с вычислительной системой. Разработаны алгоритмы функционирования расширенного терминала для выгружаемых операционных систем. Данный подход в отличие от имеющихся сглаживает разницу между локальной и удаленной работой с вычислительной системой, включая в набор терминальных устройств любую периферию (в том числе и виртуальную), позволяет использование в архитектурах вычислительных систем, не поддерживают виртуализацию адресных пространств.

Практическая ценность диссертационной работы. В рамках данной работы была спроектирована и создана универсальная операционная система НИКОС на базе современных достижений и с учетом возросшего количества требований, предъявляемых к системам. В данной системе были опробованы предложенные технические решения, что позволило значительно увеличить гибкость системы и расширить потенциальный круг задач, для которых эта система может использоваться. ОС НИКОС предназначена для индивидуального использования, а также для встроенных систем и систем реального времени.

Апробация работы. Основные положения диссертации и ее отдельные результаты докладывались и обсуждались на

1. Научно-практической конференции «Наука и образование: пути интеграции», 1998, г. Анжеро-Судженск.

2. Второй всероссийский симпозиум по прикладной и промышленной математике, 2001, г. Йошкар-Ола.

3. Всероссийская научно-практическая конференция «Новые технологии и комплексные решения: наука, образование, производство», 2001, Кемерово.

Объём работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Общий объём работы составляет 144 страницы, из них, 10 страниц- список литературы, содержащий 94 наименования. Текст диссертационной работы иллюстрируется 17 рисунками и 5 таблицами.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертационной работы, дается краткий анализ работ других авторов по оценке алгоритмов операционных систем, формулируется цель работы, приводится краткое изложение полученных в работе результатов.

В первой главе проводится анализ функциональности существующих операционных систем и их базовых алгоритмов. Обзор

позволил классифицировать как сами системы, так и алгоритмы, а также помог выявить свойственные им недостатки. В существующих операционных системах общего назначения выявлен ряд узких мест, которые значительно ограничивают показатели этих систем при использовании для решения широкого круга задач. Это связанно с высокой трудоемкостью применяемых в них алгоритмов, высокими издержками при блокировках ресурсов и неустойчивой работой в условиях изменения нагрузки. В некоторых случаях применяемые алгоритмы просто не позволяют реализовать некоторые современные требования. Основными такими задачами являются задачи планирования процессорного времени с учетом пользователей, распределения ресурсов и поддержки модульности. В этой главе исследуется возможность построения операционной системы для широкого круга применений от рабочих станций и серверных платформ до встроенных систем и систем реального времени. В конце главы формулируются основные требования к современной операционной системе.

Рис. 1. Пул задач готовых к выполнению

Во второй главе рассматривается задача распределения процессорного времени. Проводится сравнительный анализ существующих алгоритмов планирования. Предлагается алгоритм древовидного планирования с использованием системы классов элементов (структурированное множество элементов для выбора) для нового метода выбора элемента, где используются статические приоритеты. Схема предлагаемого метода приведена на рис. 1. Алгоритм планирования спускается по ветке дерева до потока, которому в последствии будет отдан квант процессорного времени. На верхнем уровне происходит выбор между пулами (системами классов) реального времени и разделения времени (фактически между виртуальными системами реального времени и разделения времени). Затем выбирается подпул (система классов), обычно это подпул задач пользователя. У пользователя выбирается система классов процесса, и в конце концов поток.

С помощью системы классов достигается прогнозируемый выбор элементов независимо от количества элементов. На рис. 2 приводится структура системы классов.

Рис 2 Система классов приоритетов

Для реализации предложенного метода используется итеративный алгоритм подсчета количества элементов для выбора и погрешностей. Все элементы разделаются на классы в соответствии с приоритетов, который может быть от 0 до N-1. Каждому классу назначается вес - некоторое положительное целое число. Классы сортируются по значению веса. Вводятся следующие переменные:

IV,

ции;

число элементов в классе; вес класса;

число элементов для выбора из класса на итера-погрешности при вычислении числа элементов для выбо-

ра на итерации;

/ - текущий класс; } - итерация для /-го класса;

- максимальный вес непустого класса;

Алгоритм планирования последовательно выбирает из классов количество элементов, определяемое следующими соотношениями:

Необходимость в использовании погрешности Оу вызнана тем,

что количество выбираемых элементов является целочисленным, а остаток должен использоваться при следующем выборе, чтобы не потерять точность, а соответственно не пропустить элементы.

При добавлении и удалении необходимо пересчитывать погрешности по следующему соотношению:

где

■ это новый максимальный вес.

' пах

Алгоритмы реализации приведенного выше общего подхода требуют достаточно много времени для выполнения, так как в них используется множество операций умножения и деления. С практической точки зрения выгоден частный случай алгоритма с экспоненциальной зависимостью между приоритетами, который позволя-

ет добиться максимально быстрой скорости работы за счет замены операций умножения и деления битовыми сдвигами. Веса в этом случае задают возрастающими вдвое - 1, 2, 4, 8 и т.д. Алгоритм планирования фактически выбирает из первого класса все элементы, из второго половину, из третьего - четверть и т.д. В нем используются следующие соотношения для получения количества элементов выбранных из класса:

где к- это номер непустого класса с максимальным весом, & - побитовая операция «И».

Трудоемкость полученных алгоритмов установки задачи в очередь, удаления задачи из очереди и выбора задачи для выполнения составляет 0(1) и не зависит от числа планируемых задач. Предлагаются комбинированные алгоритмы планирования, где в качестве базы используется алгоритм древесного планирования, а для выбора элементов используются классические алгоритмы или базовым алгоритмом используется один из известных, а для выбора элементов используется система классов со статическими приоритетами.

В третьей главе рассматривается модульный принцип проектирования и реализации ядра операционной системы. Исследуется проблема блокировки объектов ядра и межмодульной блокировки. Предлагаются методы синхронизации использования и принципы

Рис. 3. Взаимодействие базовых объектов

взаимоотношения между разделяемыми ресурсами, обеспечивающие минимальное время нахождения в критической секции (рис. 3). Исследуется взаимное влияние на блокировки нескольких процессоров в SMP-системах, предлагается способ локализации блокировок, основной принцип которых - это частое блокирование локальных объектов и уменьшение количества блокировок глобальных объектов для доступа к локальным.

Автором предлагается структура и алгоритмы функционирования активного интерфейса (рис. 4), который позволяет выполнять замену модулей без удаления зависимых модулей, а также захватывать интерфейсы для работы еще до появления модуля с их реализацией в системе. Сам интерфейс состоит из набора таблиц функций, счетчиков использования этих функций и объекта синхронизации. Для работы с интерфейсом используются пять функций: добавление набора функций (возможно просто задекларировать интерфейс), удаление набора, захват интерфейса, освобождение интерфейса и собственно функция вызова через захваченный интерфейс. Гарантируется, что вызов произойдет корректно, даже если все наборы функций будут удалены, хотя вместо результата вернется ошибка.

Внешнее представление интерфейса (првдстжвляггсяиианж}

______ п ..... ■ . - ,. . __ — и п - -.... _ _

1 | Табпищ ноеых . функций интерфейса Таблица притих " функции ингорфойса Таблица прежних функций интерфейса

1 и и 11 ■

1 1 Функции модуля 1 1 1 I! Функции модуля 11 ¡1 Функции модуля

Рис. 4. Структура объекта-интерфейса

Далее исследуется важная задача распределения блоковых ресурсов. Блоковые ресурсы - это ресурсы, которые не требуются целиком, а только частями (блоками). Рассматриваются алгоритмы кэширования. Предлагаются алгоритмы функционирования блоковой подсистемы, которые в этой главе оптимизируются для оказания минимальной задержки при блокировке очередей, что является важным критерием для систем реального времени. Для достижения поставленной цели применяется АВЛ-дерево, с помощью которого

достигается быстрый поиск блоков. Теоретически трудоемкость поиска однако количество блоков в кэше ограничено и,

как правило, не больше 4 миллионов (что уже требует 2 Гб ОЗУ), и соответственно максимальный количество итераций алгоритмов поиска, добавления и удаления будет меньше 50, что позволяет отказаться от использования мутексов и применить межпроцессорные блокировки.

В четвертой главе исследуется задача удаленного доступа к вычислительной системе. Предлагается «расширенная терминальная подсистема», где понятие терминала значительно расширяется: в него включаются дополнительные устройства, такие как: дисковод, принтер, устройство считывания компакт-дисков и др. Предлагается метод виртуализации терминальных устройств и алгоритмы его реализации.

На рис. 5 приводится взаимодействие внутренних объектов системы и физических устройств. Основными объектами данной

Рис. 5. Взаимодействие компонент терминала

подсистемы являются физический терминал (или просто терминал) и виртуальный терминал. Физический терминал используется для объединения терминальных устройств в единое целое, обеспечивает механизмы вызова драйверов устройств для локальных терминалов, а также осуществляет перенаправление и передачу данных на удаленный терминал. С каждым физическим терминалов ассоциируется системный процесс называемый «системным монитором». Этот процесс осуществляет регистрацию пользователя на терминале и подключение группы виртуальных терминалов пользователя к физическому терминалу. Виртуальный терминал, предназначен для

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

На рис. 6 приводится схема взаимодействия программных компонент. Для каждого терминального устройства создается канал взаимодействия с ним. При работе с устройством приложения посылают данные в соответствующий канал и из него же принимают

Рис. 6. Схема терминальной системы

результат. Существуют виртуальные каналы, которые опираются не на устройства, а на другие каналы (консоль, одно в графической подсистеме и др.). В случае удаленного терминала, данные этих каналов могут быть напрямую переданы на удаленный терминал, что во многих случаях позволяет существенно понизить сетевой трафик. Например, приложение открывает звуковой виртуальный канал с форматом данных МРЗ, в случае локального терминала данные модулем поддержки этого канала будут развернуты в «сырой» поток и посланы в обычный звуковой канал, в случае же удаленного терминала данные сразу будут направлены в сеть, а развернуты они будут на удаленном терминале.

Так же в главе предлагаются алгоритмы подключения пользователя к терминалу, отключения, обмена данными с устройствами через виртуальные терминал и алгоритм функционирования терминала, который осуществляет настройку физических устройств по параметрам из виртуального терминала. Показано что трудоемкости этих алгоритмов линейные или меньше. Время нахождения в блокировках минимально.

В пятой главе кратко описана созданная на основе полученных теоретических результатов универсальная операционная система НИКОС. Структура ядра системы спроектирована с учетом минимальной сложности и универсальности. Для построения использовался модульный подход, позволяющий обеспечить новое качество системы при выборе тех или иных компонент ядра. Несмотря на новые подходы и реализацию новых алгоритмов, в операционной системе поддержаны основные промышленные стандарты программирования и интерфейсы, что позволяет использовать уже существующее программное обеспечение.

В табл. 1 приведено сравнение базовых функциональных возможностей реализованных в ОС НИКОС с наиболее распространенными в мире операционными системами. В таблице не приводится сравнение скоростных характеристик, так как в эталонных ОС компоненты, рассмотренные в данной работе, построены по другому принципу, и адекватного сравнения провести не возможно, подсистемы приемлемые для скоростного сравнения построены в ОС НИ-КОС по стандартным схемам и алгоритмам и не выносятся в качестве положений в данной работе.

Табл. 1. Сравнение ОС НИКОС с другими ОС

при распределении ЦП

Поддержка мягкого реального времени + - - - + +

Многопотоковость на уровне ядра + - - + + +

Восстанавливаемое удаленное соединение + - - - + -

Разрыв жестких связей между модулями + - - - - -

В заключении кратко рассматривается возможность применения полученных результатов, а так же потенциальная область применения разработанной операционной системы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведен анализ функциональности операционных систем, который позволил выяснить современные тенденции развития операционных систем, а также выявить присущие этим системам недостатки, часть которых не могут быть устранены в рамках упомянутых систем. Помимо этого выявлен ряд узких мест, которые требуют тщательной проработки при реализации новой среды. Сформулированы требования к универсальной операционной системе.

2. Предложен алгоритм древовидного планирования, который гарантирует справедливое распределение процессорного времени между потоками, процессами и пользователями, имеет трудоемкость 0(1) относительно числа планируемых задач и О(п) относительно количества используемых приоритетов. Алгоритм гарантирует стабильный интервал получения квантов процессом и равномерно распределяет кванты процессов на всем периоде распределения квантов для всех процессов (время полного повторения цикла работы алгоритма). Предложены несколько комбинаций предложенного алгоритма с классическими алгоритмами планирования, что дает упрощение реализации с сохранением основных свойств предложенного алгоритма.

3. Предложена схема взаимодействия базовых и вспомогательных объектов ядра, в котором устанавливаются древовидные взаимосвязи между этими объектами, для обеспечения локализации частых обращений к объектам, что позволяет иметь минимальное время нахождения в блокировках.

4. Предложен подход к построению и алгоритмы функционирования активного интерфейса, который позволяется разорвать жесткую зависимость между модулями, что обеспечивает возможность обновления базовой функциональности системы без ее остановки, а также без остановки работающих приложений.

5. В алгоритмах функционирования подсистемы блоковых устройств предложено использование ЛВЛ-дерева для гарантированного быстрого поиска в блоковом кэше. Данный подход позволяет фиксировать максимальное время поиска и, следовательно, гарантирует поиск блока за фиксированное время (в классических подходах с хэш-функцией в наихудшем случае поиск блока может происходить неопределенно долго). Приводятся предлагаемые алгоритмы функционирования блоковой подсистемы и анализируются их трудоемкости. Показано, что

трудоемкость данных алгоритмов составляет

Это свойство позволяет применять эти алгоритмы в системах реального времени.

6. Предложено понятие «расширенного терминала» и свойства, которыми должен обладать этот терминал; дано определение терминальных устройств, которые должны функционировать через терминальную подсистему. Предложена схема взаимодействия вычислительной системы и терминальной подсистемы. Предложены алгоритмы функционирования терминальной подсистемы. Показано, что трудоемкость этих алгоритмов равна 0(1), а время нахождения в критических секциях постоянно и мало.

7. Разработана универсальная операционная система НИКОС, в которой воплощены полученные в работе теоретические результаты.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Гусев И.С. Активный интерфейс для ядра ОС // Новые технологии и комплексные решения: наука, образование, производство. Материалы Всероссийской научно-практической конференции. Часть VI (Информатика).- КемГУ, 2001, с. 1718.

2. Гусев И.С. Алгоритм планирования, основанный на справедливом распределении процессорного времени // Вестник Томского госуниверситета, 2002, № 275, с. 120-123.

3. Гусев И.С. Взаимодействие основных объектов ядра для эффективного выполнения блокировок в выгружаемых систе-

мах // Новые технологии и комплексные решения: наука, образование, производство. Материалы Всероссийской научно-практической конференции. Часть VI (Информатика).- Кем-ГУ,2001,с. 19-20.

4. Гусев И.С. Выполнение запросов от многих участников системы к нескольким устройствам // Вестник Томского госуниверситета, 2002, № 275, с. 124-126.

5. Гусев И.С. Использование криптографии на уровне операционной системы // Новые технологии и комплексные решения: наука, образование, производство. Материалы Всероссийской научно-практической конференции. Часть VI (Информати-ка).-Кем ГУ, 2001, с. 21.

6. Гусев И.С. Распределение процессорного времени с учетом современных требований к операционным системам // Тезисы докладов научно-практической конференции "Наука и образование: пути интеграции" г. Анжеро-Судженск, 1998, с. 1317.

Гусев И.С. Распределение процессорного времени в узлах суперкомпьютера // Обозрение прикладной и промышленной математики, г. Йошкар-Ола, 2001, с. 582-583. Гусев И.С. Расширенный терминал удаленного доступа // Новые технологии и комплексные решения: наука, образование, производство. Материалы Всероссийской научно-практической конференции. Часть VI (Информатика).- Кем-ГУ,2001,с. 16-17.

Гусев И.С. Расширенный терминал: алгоритмы функционирования и синхронизации // Вестник Томского госуниверситета, 2002, № 275, с. 117-119.

Гусев И.С. Эффективные методы синхронизации в выгружаемых операционных системах // Вестник Томского госуниверситета, 2002, № 275, с. 127-129.

7.

8.

9.

10.

Отпечатано на участке оперативной полиграфии Редакционно-издательского отдела ТГУ Лицензия ПД №00208 от 20 декабря 1999 г.

Заказ № "(29 от "16 " 08 2004 г. Тираж Щ экз.

■ 16105

ВВЕДЕНИЕ.

ГЛАВА 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. Терминалы в UNIX системах.

4.1.2. Терминалы в семействе ОС Windows.

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. ВЫВОДЫ.

С момента появления операционные системы заняли важное место в программном обеспечении для больших вычислительных систем и для персональных компьютеров. На сегодняшний день насчитывается несколько сотен операционных систем, разработанных в коммерческих компаниях и научных учреждениях. Широко известных и применяемых систем всего лишь несколько десятков. Именно эти системы представляют наибольший интерес для рассмотрения и детального изучения. Классификация операционных систем довольно обширна, однако выделяются два основных класса, которые в свою очередь могут делиться на подклассы: системы реального времени и системы разделения времени. В большинстве случаев операционная система принадлежит одному из этих классов. Те же, которые можно отнести к обоим классам, как правило, имеют существенные ограничения и не перекрывают возможности операционных систем каждого класса. Использование компьютерной техники в разных областях приводит к необходимости создания такой операционной среды, которая бы могла после нетрудоемкой настройки применяться в качестве операционной системы разных классов, тем самым сокращая затраты на приобретение и обслуживание нескольких операционных систем.

Актуальность проблемы. Применение операционных систем в новых областях, таких как кластерные вычисления, системы реального времени, встроенные системы, приводит к необходимости пересмотра функциональности операционных систем и алгоритмов, реализующих эту функциональность. В данной работе приводится исследование существующих алгоритмов функционирования операционных систем, выявляются их преимущества и недостатки и предлагаются более эффективные способы решения задач управления ресурсами вычислительной системы.

Целью работы является разработка методов повышения эффективности операционных систем, исследование возможности расширения их функций, а также реализация предложенных методов в модульной универсальной операционной системе, предназначенной как для индивидуального использования, так и в качестве серверной платформы, а также в системах реального времени и встроенных системах.

В рамках вышеуказанной цели выделяются следующие задачи.

1. Разработать подход и алгоритм планирования задач для прогнозируемого распределения процессорного времени при наличии нескольких участников, использующих вычислительную систему, и нескольких задач мягкого реального времени, которые можно было бы применить в невыгружаемых операционных системах, в том числе и для вычислительных установок с SMP-архитектурой.

2. Разработать базовый алгоритм распределения ресурсов по запросам от многих участников системы к нескольким устройствам в рамках всей вычислительной системы. Для алгоритма предъявляются следующие требования: не оказывать значительного не прогнозируемого влияния на остальную часть вычислительной системы, возможность использования в невыгружаемых операционных системах, возможность использования в вычислителях с SMP-архитектурой и проведения оптимизации очередей запросов с целью увеличения эффективности обслуживания.

3. Разработать подход и основные алгоритмы для реализации расширенной терминальной подсистемы, для которой выполняются следующие требования: возможность временного отключения от системы, возможность перехода на другой терминал, независимость от физических и технических возможностей терминала, устойчивость работы при обрыве канала связи с терминалом.

4. Разработать программное обеспечение, реализующее предложенные алгоритмы и подходы.

Методы исследования. При выполнении диссертационной работы использовались системный анализ, теория построения операционных систем, методы алгоритмизации и построения эффективных управляющих структур данных, практические эксперименты.

Научная новизна работы состоит в следующем:

1. Разработан метод планирования задач с прогнозируемым распределением времени процессоров, при интенсивном изменении состояния готовности последних. Данный метод в отличие от известных учитывает при распределении процессорного времени принадлежность потоков процессам, а процессов - пользователям, тем самым, исключая взаимное влияние процессов разных пользователей и разных типов друг на друга.

2. Предложена новая схема взаимодействия основных объектов ядра операционной системы для эффективного выполнения блокировок в выгружаемых системах, основанная на иерархических взаимосвязях между объектами. В отличие от широко распространенных одноранговых этот подход позволяет минимизировать время блокирования локальных объектов, в то время как необходимость блокировать глобальные объекты возникает значительно реже.

3. Предложен и реализован механизм активных интерфейсов для удобного манипулирования модулями ядра, позволяющий захватить ресурс еще до появления его в системе, а также убрать ресурс из системы, даже если он используется. Данный механизм в отличие от существующих позволяет «на лету» производить замену модулей (например, драйверов устройств), не внося значительных изменений в работу системы в целом. щ, 4. Предложен алгоритм распределения частично разделяемых ресурсов для выгружаемых операционных систем с гарантированным максимальным временем пребывания в критических участках, основанный на использовании

АВЛ-дерева. В отличие от классических алгоритмов, которые минимизируют среднее время и ничего не гарантируют в наихудшем случае, когда время работы потенциально может быть неопределенно большим, данный алгоритм гарантирует фиксированное время работы в наихудшем случае, что позволяет применять его в системах реального времени.

5. Предложена система расширенных терминалов для взаимодействия пользователя с вычислительной системой. Разработаны алгоритмы функционирования расширенного терминала для выгружаемых операционных систем. Данный подход в отличие от имеющихся сглаживает разницу между локальной и удаленной работой с вычислительной системой, включая в набор терминальных устройств любую периферию (в том числе и виртуальную), позволяет использование в архитектурах вычислительных систем, не поддерживают виртуализацию адресных пространств.

Практическая ценность диссертационной работы. В рамках данной работы была спроектирована и создана универсальная операционная система НИКОС на базе современных достижений и с учетом возросшего количества требований, предъявляемых к системам. В данной системе были опробованы предложенные технические решения, что позволило значительно увеличить гибкость системы и расширить потенциальный круг задач, для которых эта система может использоваться. ОС НИКОС предназначена для индивидуального использования, а также для встроенных систем и систем реального времени.

Апробация работы. Основные положения диссертации и ее отдельные результаты докладывались и обсуждались на

1. Научно-практическая конференция «Наука и образование: пути интеграции», 1998, г. Анжеро-Судженск.

2. Второй всероссийский симпозиум по прикладной и промышленной матек* матике, 2001, г. Йошкар-Ола.

3. Всероссийская научно-практическая конференция «Новые технологии и комплексные решения: наука, образование, производство», 2001, Кемерово.

Проведенный в первой главе анализ функциональности существующих операционных систем и их базовых алгоритмов позволил классифицировать как сами системы, так и алгоритмы, а также помог выявить свойственные им недостатки. В операционных системах общего назначения выявлен ряд узких мест, которые значительно ограничивают показатели этих систем при использовании для решения широкого круга задач. Это связанно с высокой трудоемкостью применяемых в них алгоритмов, высокими издержками при; блокировках ресурсов и неустойчивой работой в условиях изменения нагрузки. В некоторых случаях применяемые алгоритмы не позволяют реализовать недавно возникшие требования. Основными такими задачами являются задачи планирования процессорного времени с учетом пользователей, распределения ресурсов и поддержки модульности. В этой главе исследуется возможность построения операционной системы широкого применения, начиная от рабочих станций и серверных платформ, и, заканчивая встроенными системами и системами реального времени. Сформулированы требования к современной операционной системе.

Во второй главе рассматривается задача распределения процессорного времени. Проводится сравнительный анализ существующих алгоритмов планирования. Предлагается алгоритм древесного планирования с применением системы классов элементов для нового метода выбора элемента, где используются статические приоритеты. Предлагаются модификации данного алгоритма для линейной и экспоненциальной зависимости приоритетов. Трудоемкость полученных алгоритмов установки задачи в очередь, удаления задачи из очереди и выбора задачи для выполнения составляет 0(1) и не зависит от числа планируемых задач. Предлагаются комбинированные алгоритмы планирования, где в качестве базы используется алгоритм древесного планирования, а для выбора элементов используются классические алгоритмы или базовым алгоритмом используется один из известных, а для выбора элементов используется система классов со статическими приоритетами.

В третьей главе рассматривается модульный принцип проектирования и реализации ядра операционной системы. Исследуется проблема блокировки объектов ядра и межмодульной блокировки. Предлагаются синхронизации использования разделяемых ресурсов, обеспечивающие минимальное время между блокированием ресурсов и их разблокированием. Исследуется взаимное влияние на блокировки нескольких процессоров в вычислительных системах с симметричной многопроцессорностью. Предлагается структура и алгоритмы функционирования активного интерфейса, который позволяет выполнять замену модулей без удаления зависимых модулей. Исследуется важная задача распределения блоковых ресурсов и их кэширования. Блоковые ресурсы - это ресурсы, которые не требуются целиком, а только частями - блоками. Классическим примером блоковых ресурсов могут служить дисковые накопители. Предлагаются алгоритмы функционирования данной подсистемы, которые в этой главе исследуются на оказание минимальной задержки при блокировке очередей, что является важным критерием для систем реального времени.

В четвертой главе исследуется задача удаленного доступа к вычислительной системе. Анализируются подходы к реализации удаленного доступа в существующих операционных системах, выявляются достоинства и недостатки различных подходов. Предлагается расширенная терминальная система, где понятие терминала значительно расширяется: в него включаются дополнительные устройства, такие как: дисковод, принтер, устройство считывания компакт дисков и т.д. Предлагается метод виртуализации терминальных устройств и алгоритмы его реализации.

На основе полученных теоретических результатов создана универсальная операционная система «НИКОС», рассмотренная в пятой главе. Структуpa ядра системы спроектирована с учетом минимальной сложности и масштабируемости. Для построения использовался модульный подход, позволяющий обеспечить новое качество системы при выборе тех или иных компонент ядра. Несмотря на новые подходы и реализацию новых алгоритмов, в операционной системе поддержаны основные стандарты программирования и интерфейсы, что позволяет использовать уже существующее программное обеспечение.

Выводы в работе подробно представлены по главам. Здесь мы отметим наиболее важные выводы, а также рассмотрим перспективы использования полученных результатов.

Проведенный в первой главе анализ функциональности операционных систем позволил выяснить современные тенденции развития операционных I систем, а также выявить присущие этим системам недостатки, часть которых не могут быть устранены в рамках упомянутых систем. Помимо этого выявлен ряд узких мест, которые требуют тщательной проработки при реализации новой среды. Также в главе формулируются; требования к универсальной операционной системе. Все это позволяет разработчикам новой операционной системы учесть существующие недостатки.

Полученные во второй главе результаты могут найти применение при реализации алгоритмов планирования операционных систем, поддерживающих мягкое реальное время и параллельные вычисления. Предложен алгоритм древовидного планирования, который гарантирует справедливое распределение процессорного времени между потоками, процессами и пользователями. Он имеет трудоемкость 0(1) относительно числа планируемых задач и 0(п) относительно количества используемых приоритетов; гарантирует получение квантов через определенный интервал; равномерно распределяет кванты на интервале времени. Также предложены его модификации: 1) использование системы классов с линейной зависимостью приоритетов для более точной настройки количества выделяемого процессорного времени; 2) комбинирование предложенного алгоритма с классическими алгоритмами планирования, что дает упрощение реализации с сохранением большинства свойств предложенного алгоритма.

Полученные в третьей главе результаты позволяют формализовать разработку модульных систем, организовать эффективное разделение кода программ и данных по модулям, снять проблему тупиков при блокировке ресурсов, что является ценным в многопроцессорных системах. Предложен метод взаимодействия базовых и вспомогательных объектов ядра, в котором устанавливаются древовидные взаимосвязи между этими объектами, для обеспечения локализации частых обращений к объектам. Это позволяет иметь минимальное время нахождения в блокировках. Предложен подход к построению и алгоритмы функционирования активного интерфейса, который позволяется разорвать жесткую зависимость между модулями. Это позволяет обновлять базовую функциональность системы без ее остановки, а также без остановки работающих приложений. Разработанные алгоритмы функционирования и использования блоковых ресурсов можно использовать в операционных системах реального времени. Проведен анализ структуры и функционирования блоковой подсистемы, который позволил выявить места, где происходят максимальные задержки и длительные блокировки. Предложена структура блокового кэша. Предложено использование ABJI-дерева для гарантированного быстрого поиска. Данный подход позволяет фиксировать максимальное время поиска в кэше и, следовательно, гарантирует нахождение блока за фиксированное время (в классических подходах с хэш функцией в наихудшем случае поиск блока может выполняться за линейное время). Предложены алгоритмы функционирования блоковой подсистемы и проанализированы их трудоемкости. Показано, что трудоемкость данных алгоритмов составляет 1,4 • log(«). Это свойство позволяет применять эти алгоритмы в системах реального времени.

Описанные в четвертой главе результаты, позволяют гибко манипулировать терминальными устройствами и ресурсами (как локальными, так и удаленными) в рамках одного расширенного терминала. Предложено понятие расширенного терминала и свойства, которыми должен обладать этот терминал. Дается определение терминальных устройств, которые должны функционировать через терминальную подсистему. Предложена схема взаимодействия вычислительной системы и терминальной подсистемы. Предложены алгоритмы функционирования терминальной подсистемы. Показано, что трудоемкость этих алгоритмов равна O(l) относительно количества виртуальных терминалов, а время нахождения в критических секциях постоянно.

Описанная в пятой главе, разработанная автором, универсальная модульная операционная система НИКОС позволяет легко расширять свои возможности путем добавления или замены модулей. В этой системе были опробованы все подходы и алгоритмы, описанные в данной работе.

ЗАКЛЮЧЕНИЕ

1. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 535 с.

2. Бертмен Ж., Риту М., Ружие Ж. Работа ЭВМ с разделением времени. М.: «Наука», Главная редакция физико-математической литературы, 1970.-208 с.

3. Головкин Б.А. Параллельные вычислительные системы. М.: «Наука», Главная редакция физико-математической литературы, 1980.520с.

4. Гусев И. С. Активный интерфейс для ядра ОС // Новые технологии и комплексные решения: наука, образование, производство. Материалы Всероссийской научно-практической конференции. Часть VI (Информатика). КемГУ, 2001, с. 17-18.

5. Гусев И. С. Алгоритм планирования, основанный на справедливом распределении процессорного времени // Вестник Томского госуниверситета, 2002, № 275, с. 120-123.

6. Гусев И. С. Выполнение запросов от многих участников системы к нескольким устройствам // Вестник Томского госуниверситета, 2002, №275, с. 124-126.

7. Гусев И. С. Использование криптографии на уровне операционной системы // Новые технологии и комплексные решения: наука, образование, производство. Материалы Всероссийской научнопрактической конференции. Часть VI (Информатика). КемГУ, 2001, с. 21.

8. Гусев И. С. Распределение процессорного времени с учетом современных требований к операционным системам // Тезисы докладов научно-практической конференции "Наука и образование: пути интеграции" г. Анжеро-Судженск, 1998, с. 13-17.

9. Гусев И. С. Эффективные методы синхронизации в выгружаемых операционных системах // Вестник Томского госуниверситета, 2002, №275, с. 127-129.

10. ХЪ.Егоров Г.А., Кароль B.JI., Мостов И.С. и др. Операционная система ОСРВМ СМ ЭВМ. М.: Финансы и статистика, 1990. - 303 с.

11. Кастер X. Основы Windows NT и NTFS/Пер. с англ. М.: Издательский отдел «Русская редакция» ТОО «Channel Trading Ltd.», 1996. 440 с.

12. ХЪ.Кейлингерт /7. Элементы операционных систем. Введение для пользователей/Пер. с англ. М.:Мир, 1985, - 295 с.

13. Кейслер С. Проектирование операционных систем для малых ЭВМ/Пер. с англ. М.:Мир, 1986. - 680с.

14. П.Кнут Д. Искусство программирования для ЭВМ. Том 1. Основные алгоритмы. М: Мир, 1976. - 736 с.

15. Ковалик Я. Высокоскоростные вычисления. Архитектура, производительность, прокладные алгоритмы и программы суперЭВМ. М.: «Радио и связь». - 432 с.

16. Корнеев В.В. Параллельные вычислительные системы. М.: «Но-лидж», 1999.-320 с.

17. Ю.Королев Л.Н. Операционные системы. -М.: «Знание», 1977, 64 с.21 .Коэн Л. Д. Анализ и разработка операционных систем/Пер. с англ. -М.: «Наука», 1975. 192 с.

18. Олифер В.Г., Олифер НА. Сетевые операционные системы. СПб.: Питер, 2001. - 544 с.2Ъ.Перегрудов Ф.И., Тарасенко Ф.П. Основы системного анализа: учебник. 3-е издание. Томск.: «Издательство HTJ1», 2001. - 396 с.

19. Робачевский А.М. Операционная система UNIX.- СПб.: БХВ -Санкт-Петербург, 1999. 528с.

20. Соколов А.В. Математические модели и алгоритмы оптимального управления динамическими структурами данных. ПетрГУ. Петрозаводск, 2002. - 216 с.

21. Стерн М., Монти Г., Бэчманн В. Сети предприятий на основе Windows NT для профессионалов/Пер. с англ. СПб.: Питер Ком, 1999. -448 с.

22. Страуструп Б. Язык программирования С++, 3-е изд. / Пер. с англ. СПб.; М.: «Невский Диалект» - «Издательство БИНОМ», 1999. -991 с.

23. Уилкс М. Системы с разделением времени. М.: «Мир», 1972. - 124 с.

24. Цикритзис Д., Бернстайн Ф. Операционные системы/Пер. с англ. -М: Мир, 1977.-333с.

25. Шоу А. Логическое проектирование операционных систем/Пер. с англ. М.: Мир, 1981. - 360с.31 .Шпаковский Г.И. Архитектура параллельных ЭВМ: Учеб. Пособие для вузов. Мн.: Университетское, 1989, 192 с.

26. Эви Немен, Гарт Снайдер, Скотт Сибасс, Трент Р. Хейн. UNIX: руководство системного администратора/Пер. с англ. К.: BHV, 1996.-832 с.

27. Энслоу Ф.Г. Мультипроцессорные системы и параллельные вычисления. М.: «Мир», 1976. - 384 с.34Alvarez G.A., Fernandez МО. Efficient management of multiple outstanding timeouts // Information Processing Letters, Vol. 54, No. 3, 1995, pp. 139-145.

28. Bayne J.S. A distributed programming model for real-time industrial control // Control Engineering Practice, Vol. 3, No. 8, 1995, pp. 11331138.

29. Brandt S. A., Nutt G. J. Flexible Soft Real-Time Processing in Middleware // Real-Time Systems, Vol. 22 , No. 1/2, 2002, pp. 77-118.

30. Burns A., Wellings A.J. Synchronous sessions and fixed priority schedul4ing // Journal of Systems Architecture, Vol. 44 , No. 2, 1997, pp. 107118.

31. Burton A.N., Kelly P.H.J. Tracing and reexecuting operating system calls for reproducible performance experiments // Computers & Electrical Engineering, Vol. 26 , No. 3-4,2000, pp. 261-278.

32. Butler R., Gropp W., Lusk E. Components and interfaces of a process management system for parallel programs // Parallel Computing, Vol. 27, No. 11,2001, pp. 1417-1429.

33. DengX., Ip H., Law K., LiJ., Zheng W., Zhu S. Parallel Models and Job Characterization for System Scheduling // Lecture Notes in Computer Science, Vol. 2074, 2001. 648 p.

34. Djordjevic G.L., Tosic M.B. A heuristic for scheduling task graphs with; communication delays onto multiprocessors // Parallel Computing, Vol. 22, No. 9,1996, pp. 1197-1214.

35. Djordjevic J., Tomasevic M., Bojovic M. A hardware implementation of the mechanism of multiprocessing // Microprocessors and Microsystems, Vol. 23, No. 8-9, 1999, pp. 471-479.

36. Al.Domjan H., Gross T. R. Extending a Best-Effort Operating System to Provide QoS Processor Management // Lecture Notes in Computer Science, 2092,2001, pp. 92-106.

37. Drozdowski M. Real-time scheduling of linear speedup parallel tasks // Information Processing Letters, Vol. 57, No. 1, 1996, pp. 35-40.

38. Drozdowski M. Scheduling multiprocessor tasks An overview // European Journal of Operational Research, Vol. 94, No. 2,1996, pp. 215-230.

39. Goscinski A.M. Towards an operating system managing parallelism of computing on clusters // Future Generation Computer Systems, Vol. 17, No. 3,2000, pp. 293-314.

40. Guan H., Cheung T.-Y. Efficient approaches for constructing a massively parallel processing system // Journal of Systems Architecture, Vol. 46, No. 13,2000, pp. 1185-1190.

41. SA.Haghighi A.M. An analysis of the number of tasks in a parallel multiprocessor system with task-splitting and feedback // Computers & Operations Research, Vol. 25, No. 11, 1998, pp. 941-956.

42. Hobbs M., Goscinski A. The GENESIS parallelism management system employing concurrent process-creation services // Microprocessors and Microsystems, Vol. 24, No. 8,2000, pp. 415-427.

43. Ноотап J., Vain J. Integrating methods for the design of real-time systems // Journal of Systems Architecture, Vol. 42, No. 6-7, 1996, pp. 489502.

44. Kauler B. A tiny microcontroller dataflow kernel // Microprocessors and Microsystems, Vol. 20, No. 2,1996, pp. 105-110.

45. Keane J.A., Hussak W. A Design Phase Directed Formal Verification Process // Software Quality Journal, Vol. 8, No. 4, 1999, pp. 255-269.

46. Krone Oliver, Josef Alex. Using Corba in the Web Operating System // Lecture Notes in Computer Science, Vol. 1830,2000. 133 p.

47. Lew A. Nondeterministic dynamic programming on a parallel coprocessing system // Applied Mathematics and Computation 120, 2001, pp. 139147.

48. Li-Chi F., Ruei-Chuan C. Using Asynchronous Writes on Metadata to Improve File System Performance // Journal of Systems and Software, Vol. 35, No. 1,1996, pp. 43-54.

49. Lopriore L. Protection in a single-address-space environment // Information Processing Letters, Vol. 76, No. 1-2,2000, pp. 25-32.

50. Moreira Jose E. Blue Gene: A Massively Parallel System // Lecture Notes in Computer Science, Vol. 2073, 2001. 10 p.

51. Schultheiss В. C., Baalbergen E. H. Utilizing Supercomputer Power from Your Desktop // Lecture Notes in Computer Science, Vol. 2110, 2001, p. 52.

52. Solomon D.A., Russinovich M.E. Inside Microsoft Windows 2000 // Microsoft Corporation press, 2000. 944 p.

53. M.Taisuke В., Matsubara M., Ken'ichi /. PIO: Parallel I/O System for Massively Parallel Processors // Lecture Notes in Computer Science, Vol. 2110,2001, p. 383.

54. SS.Takeda K., AUsopp N. K, Hardwick J. С., Macey P. C., Nicole D. A., Cox S. J., Lancaster D. J. An Assessment of MPI Environments for Windows NT // The Journal of Supercomputing, Vol. 19, No. 3, 2001, pp. 315-323.

55. Terekhov I., Camp T. Time efficient deadlock resolution algorithms // Information Processing Letters, Vol. 69, No. 3, 1999, pp. 149-154.

56. Tomasevic M., Djordjevic J., Randjic S., Potic V., Bojovic M. An operating system accelerator // Journal of Systems Architecture, Vol. 44, No. 910, 1998, pp. 737-754.

57. SS.Tsai L.-J., Tsai S.-R., Hou C.-L. An 0-0 Logical Machine Monitor supporting disk block migration // Journal of Systems Architecture, Vol. 43, No. 9, 1997, pp. 639-642.

58. Utard G., Hains G. Deadlock-free absorption of barrier synchronizations // Information Processing Letters. Vol 56, No. 4,1995, pp. 221-227.

59. Wake A.S., Miller P.R., Moxon P., Fletcher M.A. Modular avionics operating system software concept // Microprocessors and Microsystems, Vol. 21, No. 1, 1997, pp. 63-68.

60. Wu J., Wynn A. The effect of compression on performance in a demand paging operating system // Journal of Systems and Software, Vol. 50, No. 2, 2000, pp. 151-170.

61. Zegzhda D.P., Stepanov P.G., Otavin A.D. Fenix Secure Operating System: Principles, Models and Architecture // Lecture Notes in Computer Science, 2052, 2001, p. 207.