Эта статья - краткий обзор работы планировщиков в операционных системах. Также вниманию читателей предоставляется Bossa, проект по исследованию планировщиков в операционных системах и платформо-зависимых языков.
<br /><br />
Статья опубликована с разрешения портала <a href=http://www.osnews.com rel=external>OSNews.com</a>. Оригинал статьи находится <a href=http://www.osnews.com/story.php?news_id=7623 rel=external></a>.<br />
Перевод на русский язык - <a href=user.php?id.2>Олег Шимчик aka Wanderer</a>.
<hr>

Краткий обзор

В последнее время основная активность в группе разработчиков ядра Linux вызвана введением в строй нового планировщика, автором которого является Инго Молнар (Ingo Molnar). Этот факт подчеркивает для обычных пользователей Linux важность планировщиков в современных операционных системах. В этой статье вы поверхностно познакомитесь с разработкой планировщиков, получив возможность самому написаться свой собственных планировщик для Linux, с помощью Bossa, framework (англ. - каркас) специально предназначеннымдля этих целей.

Bossa, framework для разработки планировщиков

Работа планировщика

Большинство продаваемых в данный момент компьютеров могут исполнять одновременно только один процесс, и, тем не менее, пользователю кажется, что множество программ работают параллельно. Эта иллюзия создана планировщиком операционной системы. Для создания такой иллюзии, планировщик заставляет систему быстро переключаться между процессами. Каждый процесс запускается на определенное время и, когда время выполнения процесса подходит к концу, планировщик выбирает, какой из процессов CPU будет обрабатывать следующим. Поэтому, поведение системы главным образом зависит от планировщика. Равноправие процессов, эффективность, латентность - планировщик должен балансировать между этими качествами, чтобы поддерживать соответствующий режим работы. Следовательно, в то время как планировщик, нацеленный на применение в настольных системах должен особое внимание уделить комплексности, планировщик, используемый в серверных системах, должен иметь хорошую производительноть и эффективно решать проблемы масштабируемост. При реализации алгоритма планировщика, разработчик должен принять во внимание тот факт, что каждое из этих свойств тесно связано с другими.
Большинство наиболее распространенны операционных систем в данный момент являются системами общего назначения, и до тех пор, пока они могут быть запущены на различных типах систем (серверы, настольные системы, встраиваемые устройства), в них, как правило, реализуется уникальный планировщик, который, соответственно, должен работать хорошо на всех этих платформах. Именно таким является новый планировщиком Linux. Реализация новых O(1) алгоритмов и переписанная поддержка мультипроцессорости, увеличивает масштабируемост серверов, построенных на основе Linux 2.6. С другой стороны, новый планировщик предлагает механизмы для приблизительног подсчета комплексности процессов, который улучшает "" системы в настольных системах.
Параллельно с индустриальным миром, исследования на поприще разработки планировщиков были горячей темой с первых дней существования многозадачных систем, и признаком этого стало возрождение темы всвязи с ростом мультимедийных приложений. Несмотря на создание большого количества новых алгоритмов, они не нашли реализации в планировщиках, используемых коммерческими операционными системами. Задачи ясны: мультимедиа, работа в реальном времени, контроль ресурсов и т.д., и все же существующие алгоритмы работы планировщиков не нашли широкого применения. Удивительно? Нет. Одной из главных проблем, с которой сталкиваются разработчики при реализации политики планировщика в стандартной ОС состоит в том, что этот процесс требует хороших знаний сразу в двух областях: разработчик планировщика должен должен хорошо изучить ядро системы для последующей его модификации и быть в курсе исследований на этом поприще.
Bossa
Bossa - framework, призванный облегчить разработку и введение новых политик для планировщиков. Bossa разработан в Ecole des Mines de Nantes [http://webi.emn.fr] и Университете Копенгагена [http://www.diku.dk]. Основная цель разработки была буквально следующей: необходимо позволить людям делать свою работу. Если задача одних разрабатывать алгоритмы работы планировщиков, то у других необходимость ковыряться в коде ядра ОС должна отпасть.
Текущая версия framework основана на Linux и заменяет разбросанный по по всему ядру код фиксированным интерфейсом для событий планировщика. Интеграция новой политики сводится к лин ковке к ядру модуля, реализующего обработчики для этих событий. Реинжениринг ядра производиться только однажды (для каждой ОС), и затем интеграция планировщиков существенно упрощается.
Bossa включает платформо-зависимый язык (DSL), который обеспечивает высокий уровень абстракции для разработчика планировщиков. Этот язык используется для написания политики планировщика, и намного более подходит для этой задачи, чем C. После этого, специальный компилятор проверяет написанный на Bossa DSL код на совместимость с целевым ядром и интерпретирует этот код в код на C, после чего может быть собран как модуль ядра Linux.
Кроме упрощения разработки политик работы планировщика, использование DSL обеспечивает лучшие гарантии безопасности. Bossa DSL накладывает больше ограничений в это плане, чем C или C++. Например, указатели (которые, как известно, являются причиной многих ошибок) просто отсутствуют, а бесконечные циклы отлавливаются самими интерпретатором Кроме того, компилятор Bossa выполняет проверку политик.
Bossa также добавляет ядру Linux иерархию планировщиков. Эта концепция заключается в построения дерева планировщиков, что позволяет различным типам приложений запускаться под различными политиками. Листья дерева - планировщики процессов, и узлы - планировщики планировщиков (так же известные, как виртуальные планировщики).
На диаграмме ниже показан пример иерархии планировщиков. В этом примере есть два типа приложений: обычные и работающие в реальном времени. В то время, как обычные приложения обрабатываются стандартным планировщиком Linux, приложения, работающие в реальном времени обрабатываются другим планировщиком, реального времени. И оба эти планировщика процессов обрабатываются виртуальным планировщиком (планировщиком планировщиков).

<img src='files/images/articles/diagram0.png' />

Дерево планировщиков

Bossa распространяется абсолютно бесплатно и доступен на собственном web-сайте: http://www.emn.fr/x-info/bossa/ [http://www.emn.fr/x-info/bossa/]
Прямые ссылки на загрузку:
Модифицированно для поддержки Bossa ядро Linux. [http://www.emn.fr/x-info/bossa/versions/bossa2424.2406.tar.gz]
Загрузочный компакт-диск Bossa, основанный на Knoppix. [http://www.emn.fr/x-info/bossa/knoppix.iso]

Алгоритм кругового обслуживания

Дабы иллюстрировать процесс разработки политики планирования, используя Bossa, мы рассмотрим один из самых простых и все же наиболее широко используемыми алгоритмов: алгоритм кругового обслуживания. Этот алгоритм назначает каждому процессу некоторый промежуток времени, называемый квантом, который определяет время, в течение которого процесс работает. Если процесс все еще запущен по истечению своего кванта, он выгружается ядром, и CPU начинает обрабатывать другой процесс. Процессы, ожидающие выполнения, сохраняются в очереди, и первый процесс в очереди, соответственно, будет исполнен первым при следующем освобождении процессора. После того, как процесс выгружен, он помещается в самый конец очереди, что подразумевает, что ему придется ждать исполнение всех других процессов впереди себя в течении их квантов, чтобы получить очередную порцию своего времени. На рисунке, расположенном чуть ниже, показана схема исполнения четырех процессов по данному алгоритму.

<img src='files/images/articles/diagram1.png' />

Исполнение процессов по алгоритму кругового обслуживания с квантом, равным 3 мс.

Далее мы объясним, как написать планировщик, основанный на алгоритме кругового обслуживания, используя Bossa. Кроме того, мы посмотрим, как загрузить этот планировщик в модифицированно Bossa ядро Linux и запустим пару испытательных программ, чтобы показать, что он работает.
Реализация алгоритма кругового обслуживания на языке Bossa
Bossa вводит новый язык программировани для написания политик планировщиков. В этой секции мы сделаем краткий обзор этого языка, в процессе реализации алгоритма кругового обслуживания.

индекс статьи
страница 1 - текущая : страница без заголовка
страница 2 : страница без заголовка
страница 3 : страница без заголовка