Параллельное и распределенное программирование на С++
Шрифт:
Модель РРАМ
Модель PRAM (Parallel Random-Access Machine — машина с параллельным произвольным доступом) — это упрощенная модель с N процессорами, обозначаемыми P 1 , Р 2 , Р 5 , ... Р n , которые разделяют одну глобальную память. Все процессоры одновременно получают доступ для чтения и записи к совместно используемой глобальной памяти. Каждый из этих теоретических процессоров может получить доступ к разделяе м ой глобальной памяти в течение одного непрерываемого интервала времени. Модель PRAM включает алгоритмы параллельного, а также исключающего чтения и записи. Алгоритмы параллельного чтения позволяют
Рис. 5.3. Память, разделяемая между потоками и процессами
Параллельный и исключающий доступ к памяти
Алгоритмы параллельного и исключаю щ его чтения и записи можно скомбинировать и получить следующие типы объединенных алгоритмов, которые можно реализовать для организации доступа к данным:
• исключаю щ ее чтение и исключаю щ ая запись (exclusive read and exclusive write-EREW);
• параллельное чтение и исключающая запись (concurrent read and exclusive write-CREW);
• исключаю щ ее чтение и параллельная запись (exclusive read and concurrent write-ERCW);
• параллельное чтение и параллельная запись (concurrent read and concurrent write-CRCW).
Эти алгоритмы можно рассматривать как стратегии доступа, реализуемые задачами, которые совместно используют данные (рис. 5.4). Алгоритм EREW подразу м евает последовательный доступ к разделяемой памяти, т.е. к общей памяти в любой момент времени может получить доступ только одна задача. Примером стратегии доступа EREW может служить вариант реализации модели потоков «производитель-потребитель», рассмотренный в главе 4. Доступ к очереди, содержащей имена файлов, может быть ограничен исключающей записью «изготовителя» и исключающим чтением «потребителя». В любой момент времени доступ к очереди может быть разрешен только для одной задачи. Стратегия CREW позволяет множественный доступ для чтения общей памяти и исключающий доступ для записи в нее данных. Это означает отсутствие ограничений на количество задач, которые могут одновременно читать разделяемую память, но записывать в нее данные может только одна задача. При этом параллельное чтение может происходить одновременно с записью данных в общую память. При использовании этой стратегии доступа все читающие задачи могут прочитать различные значения, поскольку во время чтения значения из общей памяти записывающая задача может его модифицировать. Стратегия доступа ERCW — это прямая противоположность стратегии CREW. При использовании стратегии ERCW разрешены параллельные записи в общую память, но лишь одна задача может читать ее в любой момент времени. Стратегия доступа CRCW позволяет множеству задач выполнять параллельное чтение и запись.
Для этих четырех типов алгоритмов требуются различные уровни и типы синхронизации. Их диапазон довольно широк: от стратегии доступа, реализация которой требует минимальной синхронизации, до стратегии доступа, реализация которой требует максимальной синхронизации. Наша задача— реализовать эти стратегии, поддерживая целостность данных и удовлетворительную производительность системы. EREW — самая простая для реализации стратегия, поскольку она предполагает, по сути, только последовательную обработку. На первый взгляд самой простой может показаться стратегия CRCW, но она таит в себе массу трудностей. А ведь это только кажется, что если к памяти можно получить доступ без ограничений, то в ней и речь не идет о какой бы то ни было стратегии. Все как раз наоборот: CRCW — самая трудная для реализации стратегия, которая требует максимальной синхронизации.
Рис. 5.4. Стратегии доступа EREW, CREW, ERCW и CRCW
Что такое семафоры
Семафор —
Операции по управлению семафором
Как упоминалось выше, к семафору можно получить доступ только с помощью специальных операций, подобных тем, которые выполняются с объектами. Это операции декремента, P, и инкремента, V. Если объект Mutex представляет собой семафор, то логика реализации операций P (Mutex) и V (Mutex) м ожет выглядеть таки м образо м:
P(Mutex)
if (Mutex > 0) {
Mutex--;
} else {
Блокирование по объекту Mutex;
}
V(Mutex)
if(Oчepeдь доступа к объекту Mutex не пуста){
Передача объекта Мьютекс следующей задаче;
} else {
Mutex++;
}
Реализация зависит от конкретной систе м ы. Эти операции неделимы, т.е. их невозможно прервать. Если операцию P попытаются выполнить сразу несколько задач, то лишь одна из них получит разрешение продолжить работу. Если объект Mutex был уже декре м ентирован, то задача будет заблокирована и зай м ет м есто в очереди. Операци я V вызываетс я задачей, которая и м еет доступ к объекту Mutex. Если получения доступа к объекту Мьютекс ожидают дру г ие задачи, он «передается » следующей задаче из очереди. Если очередь задач пуста, объект Mutex инкрементируетс я.
Операции с семафором могут иметь другие имена:
Операци я P: lock
Операци я V: unlock
Значение семафора зависит от его типа. Двоичный семафор будет иметь значение 0 или 1. Вычислительный семафор (определяю щ ий лимиты ресурсов для процессов, получающих доступ к ним) может иметь некоторое неотрицательное целочисленное значение.
Стандарт POSIX определяет несколько типов семафоров. Эти семафоры испо л ьзуются процессами или потоками. Типы семафоров (а также их некоторые основные операции) перечислены в табл. 5.1.
Таблица 5 .1. Типы семафоров, определенные стандартом POSIX
Тип семафора
Пользователь
Описание
Мьютексный семафор
Процессы или потоки
Механизм, используемый для реализации взаимного исключения в критическом разделе кода
Блокировка для обеспечения чтения и записи
Процессы или потоки
Механизм, используемый д
л
я реализации стратегии доступа для чтения и записи среди потоков
Условная переменная
Процессы или потоки
Механизм, используемый д
л