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

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

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

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

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

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

• мультипроцессорная система;
• мультикомпьютерная система;
• распределенная система.

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

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

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

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

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

Рисунок 3. Различия в способах хранения и работы с данными в системах (5 кадров, 5 циклов повторения, 61,8 Кбайта):

а) мультипроцессорная система из 12 процессоров, использующих общую память;

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

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

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

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

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

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

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

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

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

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

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

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

• процесс завершился и покинул систему,
• произошла ошибка,
• процесс перешел в состояние ОЖИДАНИЕ,
• исчерпан квант процессорного времени, отведенный данному процессу.

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

Сами кванты могут отличаться для различных процессов или же вообще изменяться с течением времени. Процессы, которые не полностью использовали выделенное им для работы время (например, из-за ухода на выполнение операций ввода-вывода), зачастую получают в системе дополнительные привилегии при последующем обслуживании. По-разному может быть организована и сама очередь готовых процессов: циклически, по правилу «первый пришел - первый обслужился» (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).