Файл: «Мультипроцессоры».pdf

Рисунок 6. Планирование зависимых процессов.

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

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

4.3 Планировщики мультикомпьютерных систем

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

•  планирование процессов на каждом из процессоров с помощью локального алгоритма (аналогично планированию в однопроцессорной системе);
•  распределение новых процессов по процессорам. 

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

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

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

Распределенный эвристический алгоритм, инициируемый получателем. При завершении процесса анализируется загруженность данного процессора. Если он свободен, то ищет случайным образом загруженный процессор и запрашивает процесс из его очереди на выполнение [3]. 

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

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

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

4.4 Планировщики распределенных систем

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

Списочное планирование. Метод состоит в том, чтобы отсортировать и упорядочить вершины графа задач в список по какому-либо признаку, а затем последовательно формировать план для каждой отдельной задачи так, чтобы время начала ее выполнения было минимальным. Порядок задач в списке определяется их приоритетом. Вместо приоритета можно использовать топологический порядок задач в графе, верхний или нижний уровень вершины графа или их сумма (ВУ + НУ).

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

Алгоритмы кластеризации задач [7]. Они направлены на минимизацию межпроцессорного взаимодействия. Это достигается за счет объединения сильно связанных между собой процессов в отдельные кластеры, которые затем отображаются на процессоры заданной вычислительной системы. Здесь на каждой итерации за основу берутся уже не вершины, а ребра графа задач.

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

Заключение

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

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

Список используемых источников

1. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация / А.Б. Барский. — М.: Радио и связь,1990. 256 с.
2. Таненбаум Э., ван Стеен М. Распределенные системы. Принципы и парадигмы. - СПб.: Питер, 2003. — 877 с.: ил. — (Серия «Классика Computer Science») — ISBN 5–272–00053–6.
3. Таненбаум Э.: «Современные операционные системы», 3-е издание - СПб.: «Питер», 2011.- 1115 с.
4. Морев Н. В. Сравнение алгоритмов планирования распределения задач для однородных распределенных вычислительных систем [Текст] / Н. В. Морев // Информационные технологии : Научно-технический и научно-производственный журнал. - 2010. - N 5. - С. 43-46
5. Афраймович Л.Г. Модели и методы эффективного использования распределенных вычислительных систем [Учебно-методическое пособие] — Нижний Новгород, 2012 – 17 с.
6. Принципы построения параллельных вычислительных систем. / Электронный ресурс. - Режим доступа: http://wiki.auditory.ru/Принципы_построения_параллельных_вычислительных_систем
7. Воронцов К. В. Лекции по алгоритмам кластеризации и многомерного шкалирования. / Электронный ресурс. - Режим доступа: http://www.ccas.ru/voron/download/Clustering.pdf