Камерон Хьюз - Параллельное и распределенное программирование на С++

Модель PRAM (Parallel Random-Access Machine — машина с параллельным произвольным доступом) — это упрощенная модель с N процессорами, обозначаемыми P 1, Р 2 ,Р 5, ... Р n, которые разделяют одну глобальную память. Все процессоры одновременно получают доступ для чтения и записи к совместно используемой глобальной памяти. Каждый из этих теоретических процессоров может получить доступ к разделяе м ой глобальной памяти в течение одного непрерываемого интервала времени. Модель PRAM включает алгоритмы параллельного, а также исключающего чтения и записи. Алгоритмы параллельного чтения позволяют нескольким процессорам одновременно использовать одну и ту же область памяти без како г о бы то ни было искажения данных. Алгоритмы параллельной записи позволяют нескольким процессорам записывать данные в разделяемую область памяти. Алгоритмы исключающего чтения используются для получения гарантии того, что никакие два процессора никогда не будут считывать информацию из одной и той же области памяти одновременно. Алгоритмы исключающей записи гарантируют, что никакие два процессора никогда не будут записывать данные в одну и ту же область памяти одновременно. Модель 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 — самая трудная для реализации стратегия, которая требует максимальной синхронизации.

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

Как упоминалось выше, к семафору можно получить доступ только с помощью специальных операций, подобных тем, которые выполняются с объектами. Это операции декремента, 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инкрементируетс я.