М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 34
Текст из файла (страница 34)
Прямой параллелизм знаком большинству программистов в следующих формах:
• Мультипрограммные (multi-programming) операционные системы дают возможность одновременно использовать компьютер нескольким пользователям. Системы разделения времени, реализованные на обычных больших машинах и миникомпьютерах, в течение многих лет были единственным способом сделать доступными вычислительные средства для таких больших коллективов, как университеты.
• Многозадачные (multi-tasking) операционные системы дают возможность одновременно выполнять несколько компонентов одной программы (или программ одного пользователя). С появлением персональных компьютеров мультипрограммные компьютеры стали менее распространенными, но даже одному человеку часто необходим многозадачный режим для одновременного выполнения разных задач, как, например, фоновая печать при диалоговом режиме работы с документом.
• Встроенные системы (embedded systems) на заводах, транспортных системах и в медицинской аппаратуре управляют наборами датчиков и приводов в «реальном масштабе времени». Для этих систем характерно требование, чтобы они выполняли относительно небольшие по объему вычисления через очень короткие промежутки времени: каждый датчик должен быть считан и проинтерпретирован, затем программа должна выбрать соответствующее действие, и, наконец, данные в определенном формате должны быть переданы к приводам. Для реализации встроенных систем используются многозадачные операционные системы, позволяющие координировать десятки обособленных вычислений.
Проектирование и программирование параллельных систем являются чрезвычайно сложным делом, и целые учебники посвящены различным аспектам этой проблемы: архитектуре систем, диспетчеризации задач, аппаратным интерфейсам и т. д. Цель этого раздела состоит в том, чтобы дать краткий обзор языковой поддержки параллелизма, который традиционно обеспечивался функциями операционной системы и аппаратурой.
Параллельная программа (concurent program) состоит из одного или нескольких программных компонентов (процессов), которые могут выполняться параллельно. Параллельные программы сталкиваются с двумя проблемами:
Синхронизация. Даже если процессы выполняются одновременно, иногда один процесс должен будет синхронизировать свое выполнение с другими процессами. Наиболее важная форма синхронизации — взаимное исключение: два процесса не должны обращаться к одному и тому же ресурсу (такому, как диск или общая таблица) одновременно.
Взаимодействие. Процессы не являются полностью независимыми; они должны обмениваться данными. Например, в программе управления полетом процесс, считывающий показания датчика высоты, должен передать результат процессу, который делает расчеты для автопилота.
12.2. Общая память
Самая простая модель параллельного программирования — это модель с общей памятью (см. рис. 12.1). Два или несколько процессов могут обращаться к одной и той же области памяти, хотя они также могут иметь свою собственную частную, или приватную, (private) память. Предположим, что у нас есть два процесса, которые пытаются изменить одну и ту же переменную в общей памяти:
procedure Main is
N: Integer := 0;
task T1;
task T2;
task body T1 is
begin
for I in 1 ..100 loop N := N+1; end loop;
end T1;
task body T2 is
begin
for I in 1 ..100 loop N := N+1; end loop;
end T2;
begin
null;
end Main;
Рассмотрим теперь реализацию оператора присваивания:
load R1,N Загрузить из памяти
add R1,#1 Увеличить содержимое регистра
store R1,N Сохранить в памяти
Если каждое выполнение тела цикла в Т1 завершается до того, как Т2 выполняет свое тело цикла, N будет увеличено 200 раз. Однако каждая задача может быть выполнена на отдельном компьютере со своим набором регистров. В этом случае может иметь место следующая последовательность событий:
• Т1 загружает N в свой регистр R1 (значение равно и).
• Т2 загружает N в свой регистр R1 (значение равно «).
• Т1 увеличивает R1 (значение равно п + 1).
• Т2 увеличивает R1 (значение равно и + 1).
• Т1 сохраняет содержимое своего регистра R1 в N (значение равно п + 1).
• Т2 сохраняет содержимое своего регистра R1 в N (значение равно п + 1).
Результат выполнения каждого из двух тел циклов состоит только в том, что N увеличится на единицу. Результирующее значение N может лежать между 100 и 200 в зависимости от относительной скорости каждого из двух процессоров.
Важно понять, что это может произойти даже на компьютере, который реализует многозадачный режим путем использования единственного ЦП. Когда ЦП переключается с одного процесса на другой, регистры, которые используются заблокированным процессом, сохраняются, а затем восстанавливаются, когда этот процесс продолжается.
В теории параллелизма выполнение параллельной программы определяется как любое чередование атомарных команд задач. Атомарная команда — это всего лишь команда, которую нельзя выполнить «частично» или прервать, чтобы продолжить выполнение другой задачи. В модели параллелизма с общей памятью команды загрузки и сохранения являются атомарными.
Если говорить о чередующихся вычислениях, то языки и системы, которые поддерживают параллелизм, различаются уровнем определенных в них атомарных команд. Реализация команды должна гарантировать, что она выполняется атомарно. В случае команд загрузки и сохранения это обеспечивается аппаратным интерфейсом памяти. Атомарность команд высокого уровня реализуется с помощью базисной системы поддержки времени выполнения и поддерживается специальными командами ЦП.
12.3. Проблема взаимных исключений
Проблема взаимных исключений (mutual exclusion problem) для параллельных программ является обобщением приведенного выше примера. Предполагается, что в каждой задаче (из параллельно выполняемых) вычисление делится на критическую (critical) и некритическую (non-critical) секцию (section), которые неоднократно выполняются:
task body T_i is
begin
loop
Prologue;
Critical_Section;
Epilogue;
Non_Critical_Section;
end loop;
end T_i:
Для решения проблемы взаимных исключений мы должны найти такие последовательности кода, называемые прологом (prologue) и эпилогом (epilogue), чтобы программа удовлетворяла следующим требованиям, которые должны выполняться для всех чередований последовательностей команд из набора задач:
Взаимное исключение. В любой момент времени только одна задача выполняет свою критическую секцию.
Отсутствие взаимоблокировки (no deadlock). Всегда есть, по крайней мере, одна задача, которая в состоянии продолжить выполнение.
Жизнеспособность. Если задаче необходимо выполнить критическую секцию, в конце концов она это сделает.
Справедливость. Доступ к критическому участку предоставляется «по справедливости».
Существуют варианты решения проблемы взаимных исключений, использующие в качестве атомарных команд только load (загрузить) и store (сохранить), но эти решения трудны для понимания и выходят за рамки данной книги, поэтому мы отсылаем читателя к учебникам по параллельному программированию.
Э. Дейкстра (E.W. Dijkstra) определил абстракцию синхронизации высокого уровня, называемую семафором, которая тривиально решает эту проблему. Семафор S является переменной, которая имеет целочисленное значение; для семафоров определены две атомарные команды:
Wait(S): when S > 0 do S := S -1;
Signal(S): S:=S+1;
Процесс, выполняющий команду Wait(S), блокируется на время, пока значение S неположительно. Обратите внимание, что, поскольку команда является атомарной, то, как только процесс удостоверится, что S положительно, он сразу уменьшит S (до того, как любой другой процесс выполнит команду!). Точно так же Signal(S) выполняется атомарно без возможности прерывания другим процессом между загрузкой и сохранением S. Проблема взаимных исключений решается следующим образом:
| Ada |
S: Semaphore := 1 ;
task T_i; -- Одна из многих
task body T_i is
begin
loop
Wait(S);
Critical_Section;
Signal(S);
Non_Critical_Section;
end loop;
end T_i;
begin
null;
end Main;
Мы предлагаем читателю самостоятельно убедиться в том, что это решение является правильным.
Конечно, самое простое — это переложить бремя решения проблемы на разработчика системы поддержки этапа выполнения.
12.4. Мониторы и защищенные переменные
Проблема, связанная с семафорами и аналогичными средствами, обеспечиваемыми операционной системой, состоит в том, что они не структурны. Если нарушено соответствие между Wait и Signal, программа может утратить синхронизацию или блокировку. Для решения проблемы структурности была разработана концепция так называемых мониторов (monitors), и они реализованы в нескольких языках. Монитор — это совокупность данных и подпрограмм, которые обладают следующими свойствами:
• Данные доступны только подпрограммам монитора.
• В любой момент времени может выполняться не более одной подпрограммы монитора. Попытка процесса вызвать процедуру монитора в то время, как другой процесс уже выполняется в мониторе, приведет к приостановке нового процесса.
Поскольку вся синхронизация и связь выполняются в мониторе, потенциальные ошибки параллелизма определяются непосредственно программированием самого монитора; а процессы пользователя привести к дополнительным ошибкам не могут. Интерфейс монитора аналогичен интерфейсу операционной системы, в которой процесс вызывает монитор, чтобы запросить и получить обслуживание. Синхронизация процессов обеспечивается автоматически. Недостаток монитора в том, что он является централизованным средством.
Первоначально модель параллелизма в языке Ada (описанная ниже в разделе 12.7) была чрезвычайно сложной и требовала слишком больших затрат для решения простых проблем взаимных исключений. Чтобы это исправить, в Ada 95 были введены средства, аналогичные мониторам, которые называются защищенными переменными (protected variables). Например, семафор можно смоделировать как защищенную переменную. Этот интерфейс определяет две операции, но целочисленное значение семафора рассматривает как приватное (private), что означает, что оно недоступно для пользователей семафора:
protected type Semaphore is
entry Wait;
procedure Signal;
private
Value: Integer := 1;
end Semaphore;
Реализация семафора выглядит следующим образом:
protected body Semaphore is
entry Wait when Value > 0 is
begin
| Ada |
end Wait;
procedure Signal is
begin
Value := Value + 1 ;
end Signal;
end Semaphore;
Выполнение entry и procedure взаимно исключено: в любой момент времени только одна задача будет выполнять операцию с защищенной переменной. К тому же entry имеет барьер (barrier), который является булевым выражением. Задача, пытающаяся выполнить entry, будет заблокирована, если выражение имеет значение «ложь». Всякий раз при завершении защищенной операции все барьеры будут перевычисляться, и будет разрешено выполнение той задачи, барьер которой имеет значение «истина». В приведенном примере, когда Signal увеличит Value, барьер в Wait будет иметь значение «истина», и заблокированная задача сможет выполнить тело entry.
12.5. Передача сообщений
По мере того как компьютерные аппаратные средства дешевеют, распределенное программирование приобретает все большее значение. Программы разбиваются на параллельные компоненты, которые выполняются на разных компьютерах. Модель с разделяемой памятью уже не годится; проблема синхронизации и связи переносится на синхронную передачу сообщений (synchronous message passing), изображенную на рис. 12.2. В этой модели канал связи с может существовать между любыми двумя процессами. Когда один процесс посылает сообщение m в канал, он приостанавливается до тех пор, пока другой процесс не будет готов его получить. Симметрично, процесс, который ожидает получения сообщения, приостанавливается, пока посылающий процесс не готов послать. Эта приостановка используется для синхронизации процессов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
