Размещено на http://www.allbest.ru

МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО ОБРАЗОВАНИЯ РЕСПУБЛИКИ УЗБЕКИСТАН

НАВОИЙСКИЙ ГОРНО-МЕТАЛЛУРГИЧЕСКИЙ КОМБИНАТ

НАВОИЙСКИЙ ГОСУДАРСТВЕННЫЙ ГОРНЫЙ ИНСТИТУТ

ЭНЕРГО-МЕХАНИЧЕСКИЙ ФАКУЛЬТЕТ

Самостоятельная работа

ПО ПРЕДМЕТУ: Автоматизация технологических процессов

Динамическое планирование вычислительных процессов управления (улучшение алгоритмов планирования в параллельных вычислительных системах)

2021



Содержание

Введение

1. Актуальность темы

2. Цель и задачи исследования, планируемые результаты

3. Обзор различных видов параллельных вычислительных систем

3.1 Мультипроцессорная система

3.2 Мультикомпьютерная система

3.3 Распределенная система

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

4.1 Различные характеристики планировщиков задач

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

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

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

Выводы

Список источников



Введение

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

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

· какой из процессов, стоящих в очереди на выполнение, должна система запустить в данный момент времени;

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

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



1. Актуальность темы

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

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

2. Цель и задачи исследования, планируемые результаты

Целью исследования является повышение эффективности этапа планирования процессов в параллельных вычислительных систем.

Основными задачами исследования ставятся:

1. Обзор различных существующих методов планирования задач.

2. Анализ и сравнительная оценка наиболее перспективных алгоритмов.

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

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

5. Разработка и улучшение наиболее эффективного из полученных методов планирования.

Объектом исследования является планировщик многопроцессорных систем.

Предмет исследования: улучшение алгоритма планирования для многопроцессорных вычислительных систем.

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

1. Создание более эффективного метода планирования процессов.

2. Определение перспективных направлений развития планировщиков.

3. Модификация известных алгоритмов планирования задач.



3. Обзор различных видов параллельных вычислительных систем

Для выполнения сложных расчетов и эффективной работы больших вычислительных систем обычно используют одну из следующих моделей:

· мультипроцессорная система;

· мультикомпьютерная система;

· распределенная система.

3.1 Мультипроцессорная система

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

3.2 Мультикомпьютерная система

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

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

Рисунок 1 Различия в способах хранения и работы с данными в системах (5 кадров, 5 циклов повторения, 61,8 Кбайта): а) мультипроцессорная система из 12 процессоров, использующих общую память; б) мультикомпьютерная система из 12 процессоров, каждый из которых имеет собственную память

3.3 Распределенные системы

Распределенной вычислительной системой (РВС) можно считать набор соединенных каналами связи независимых компьютеров, которые для постороннего пользователя являются единым целым [2]. РВС можно представить, как несколько отдельных персональных компьютеров или серверов, объединенных в единую систему с помощью сети Интернет. Естественно, сообщение данными через Интернет, как и сами способы организации подобного сообщения (обмен пакетами, маршрутизация и др. аспекты) между машинами, находящимися в различных частях земного шара (физически), нельзя назвать стабильным и определенно быстрым, а потому временные показатели подобных систем довольно низки. Однако РВС отличаются высокой надежностью, в виду того, что выход из строя одного элемента или узла сети не играет особой роли в ее работоспособности. К тому же, они обладают практически неограниченным потенциалом в плане наращивания производительности - чем больше компьютеров будет объединено этой структурой, тем выше будет их общая вычислительная мощность.

Рисунок 2 Общее представление распределенной сети (системы)



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

4.1 Различные характеристики планировщиков задач

Способ решения вопроса о планировании задач существенно зависит от того, независимы или зависимы (связаны друг с другом) процессы в списке, а потому их можно в целом разбить на две большие категории:

- планирование независимых процессов;

- планирование зависимых процессов.

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

Рисунок 3 Базовая классификация алгоритмов планирования

Алгоритмы, основанные на идеи квантования, осуществляют смену активного процесса, если происходит одно из следующего:

· процесс завершился и покинул систему,

· произошла ошибка,

· процесс перешел в состояние ОЖИДАНИЕ,

· исчерпан квант процессорного времени, отведенный данному процессу.

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

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

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

Non-preemptive multitasking (невытесняющая многозадачность) - это способ планирования процессов, при котором активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс.

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

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

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

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

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

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

* какой из готовых к выполнению процессов нужно запустить в данный конкретный момент времени;

* на каком из процессоров нужно запустить выбранный процесс.

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

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

Рассмотренная схема планирования позволяет:

1. Обеспечить процессорам режим разделения времени;

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

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

Весьма распространенный алгоритм для связных процессов состоит в статическом разбиении всего множества доступных процессоров на подмножества и назначении каждому из них отдельной группы связных процессов. Например, имеется четыре группы связанных процессов Q1-Q3, Q4-Q7, Q8-Q13 и Q14-Q20. Тогда, в соответствии с данным алгоритмом, процессы первой группы должны быть назначены первому подмножеству процессоров (P1-P3), процессы второй группы - второму подмножеству процессоров (P4-P7), и т.д. (см. рис. 4).

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



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

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

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

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

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

· распределение новых процессов по процессорам.

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

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

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

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

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

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

· определение исполнительных ресурсов для каждого задания;

· определение времени, в течение которого ресурсы отводятся заданию.



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

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

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

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

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

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



Выводы

планировщик мультипроцессорный алгоритм

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

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

Дальнейшие исследования будут направлены на:

1. Проведение анализ и сравнительной оценка наиболее перспективных алгоритмов.

2. Поиск и выявление тех характеристик планировщиков, что могут быть улучшены для получения более оптимальных результатов.

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

4. Разработку и улучшение наиболее эффективного из полученных методов планирования.

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2013 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.



Список источников

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

Размещено на Allbest.ru

...