5.1. Принципы параллельных вычислений

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

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

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

2. Операционной системе трудно управлять распределением ресурсов опти­мальным образом. Например, процесс А может затребовать и получить кон­троль над некоторым каналом ввода-вывода, после чего временно приоста­новить работу. Нежелательно, чтобы операционная система при этом блокировала канал и не давала другим процессам возможности использовать его — такая политика может привести к возникновению условий взаимо­блокировки, описываемых в главе 6, "Взаимоблокировка и голодание".

3. Становится очень трудно обнаружить программную ошибку, поскольку обычно результат работы программы перестает быть детерминированным и воспроизводимым (см., например, [LEBL87, CARR89]).

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

Простой пример

Рассмотрим следующую процедуру:

void echo()

{

chin = getchar();

chout = chin;

putchar(chout);

}

Она демонстрирует основные элементы отображения вводимых символов. Входной символ, получаемый с клавиатуры, сохраняется в переменной chin; по­сле этого значение переменной chin присваивается переменной chout и выво­дится на экран. Данная процедура может неоднократно вызываться любым про­цессом для получения ввода пользователя и отображения его на экране.

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

Разделение основной памяти между процессами способствует эффективному и тесному взаимодействию процессов. Однако такое разделение может привести к проблемам. Рассмотрим последовательность событий.

1. Процесс Р1 вызывает процедуру echo и прерывается немедленно по выпол­нении функции getchar. В этот момент последний введенный символ х со­хранен в переменной chin.

2. Активируется процесс Р2, который вызывает процедуру echo. Эта процеду­ра выполняется до конца; при этом считывается с клавиатуры и выводится на экран очередной символ у.

3. Продолжается выполнение процесса Р1. Однако к этому моменту значение х в переменной chin перезаписано — теперь эта переменная содержит зна­чение у, которое присваивается переменной chout и выводится на экран.

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

1. Процесс Р1 вызывает процедуру echo и прерывается немедленно по выпол­нении функции getchar. В этот момент последний введенный символ х со­хранен в переменной chin.

2. Активируется процесс Р2, который вызывает процедуру echo. Однако, по­скольку приостановленный процесс Р1 находится в процедуре echo, P2 блоки­руется от входа в данную процедуру. Следовательно, выполнение Р2 приоста­навливается до тех пор, пока процедура echo не окажется свободной.

3. В некоторый более поздний момент продолжается выполнение процесса Р1, который завершает выполнение процедуры echo, выводя на экран верный символ — х.

4. После того как Р1 покидает echo, блокировка Р2 удаляется и позже, при во­зобновлении работы процесса Р2, им успешно выполняется процедура echo.

Урок, который следует извлечь из данного примера, заключается в том, что разделяемые глобальные переменные (как и другие разделяемые глобальные ре­сурсы) нуждаются в защите, и единственный способ сделать это состоит в управ­лении кодом, осуществляющим доступ к этим переменным. Если мы добьемся того, что в определенный момент времени только один процесс сможет входить в процедуру echo и она обязательно будет полностью выполнена вошедшим в нее процессом до того, как станет возможно выполнение ее другим процессом, то мы будем застрахованы от возникновения рассматриваемой ошибки. Каким образом этого добиться — основной вопрос данной главы.

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

1. Одновременно выполняются процессы Р1 и Р2 — каждый на своем процес­соре. Оба процесса вызывают процедуру echo.

2. Происходят следующие события (события в одной строке происходят па­раллельно):

Процесс Р1 Процесс Р2

• • in = getchar(); .

• in = getchar();

chout = chin; chout = chin;

putchar(chout); .

• putchar(chout);

• •

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

1. Одновременно выполняются процессы Р1 и Р2 — каждый на своем процес­соре. Процесс Р1 вызывает процедуру echo.

2. В то время как процесс Р1 находится в процедуре echo, эту же процедуру вы­зывает процесс Р2. Однако, поскольку процесс Р1 находится в процедуре echo (неважно, выполняется ли в этот момент процесс Р1 или приостановлен), Р2 блокируется от входа в данную процедуру. Следовательно, выполнение Р2 при­останавливается до тех пор, пока процедура echo не окажется свободной.

3. В некоторый более поздний момент времени выполнение процессом Р1 про­цедуры echo завершается, после чего немедленно продолжается выполнение, процесса Р2 и им успешно выполняется процедура echo.

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

Участие операционной системы

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

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

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

• Процессорное время: это функция планирования, рассматриваемая в час­ти 4, "Планирование".

• Память: большинство операционных систем используют схему виртуаль­ной памяти. Этот вопрос рассматривается в части 3, "Память".

• Файлы: обсуждаются в главе 12, "Управление файлами".

• Устройства ввода-вывода: обсуждаются в главе 11, "Управление вводом-выводом и дисковое планирование".

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

4. Результат работы процесса не должен зависеть от скорости его выполнения по отношению к другим параллельно выполняющимся процессам. Этому вопросу посвящена данная глава.

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