Параллельное программирование



              

Средства синхронизации параллельных процессов


1. Матрица следования. Является эффективным средством синхронизации при реализации первого способа распараллеливания. Допускает автоматическое составление в процессе диспетчирования, как рассмотрено ранее. Легко составляется пользователем, планирующим параллельный процесс. Для оптимального планирования требует временной оценки работ либо оценки их сравнительной трудоемкости.

Например, пусть методом "разделяй и властвуй" производится распараллеливание сортировки слиянием. Известны оценки сложности такой сортировки (как функции параметра n — длины последовательности).

При разбиении последовательности на две можно построить граф G и его матрицу следования S (рис. 11.1).

Составление взвешенного информационного графа и матрицы следования

Рис. 11.1.  Составление взвешенного информационного графа и матрицы следования

Здесь t — время совместного анализа двух элементов последовательности. Значит, веса вершин t1, t2, t3 определены при заданных n и t.

2. Механизм семафоров.Различают двоичные семафоры, имеющие значения "открыт" и "закрыт", и семафоры-счетчики. "Закрытие" увеличивает их на единицу, "открытие" — уменьшает на единицу.

Анализ задач и, в частности, задач обработки больших массивов данных (баз данных и баз знаний) показал целесообразность совместной реализации этих двух принципов в многопроцессорной вычислительной системе. В одном семафоре, назовем его комбинированным, в действительности воплощены два семафора: двоичный и счетчик:

 \begin{center} С: \begin{tabular}{|c|c|} \hline Двоичный семафор Са & Семафор-счетчик Сб\\ \hline \end{tabular} \end{center}

В начале считывания из массива выполняется операция Сб := Сб+ 1; при окончании считывания — операция Сб := Сб - 1. Значение Сб

0 означает: семафор C "закрыт по считыванию".

При записи в массив выполняется операция: Са := 1, "закрыть", т.е. семафор C "закрывается по записи". При окончании записи выполняется операция Cа := 0 — "открыть", т.е. семафор C "открывается по записи".

Однако удобства семафора-счетчика могут быть реализованы в процедурах над двоичными семафорами.


Содержание    Вперед