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

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

Разбить на страницы
Показывать лекцию целиком

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

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. Значение $$Сб \ne 0$$ означает: семафор C "закрыт по считыванию".

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

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

Перечислим основные процедуры над семафорами, реализуемые в МВК "Эльбрус".

Процедура ОБЪЯВИТЬ (С) объявляет список семафоров, который рассматривается как описание, действующее внутри данного блока в алгоритмическом языке. Этим обеспечивается выделение памяти и тип переменной при трансляции.

Процедура ЗАКРЫТЬ (С) сначала присваивает семафорам, перечисленным в списке C, значение "закрыт". Затем для каждого семафора она проверяет, был ли он закрыт ранее. Если в списке C семафоров указан один или несколько семафоров, которые были закрыты до выполнения данной процедуры, происходит прерывание процесса (задачи). Процедура ОС, запустившаяся по прерыванию, ставит данный процесс в очередь к тем семафорам, которые были закрыты ранее. Таким образом, процесс задерживается до тех пор, пока другие процессы не откроют эти семафоры. После прерывания процесса и обработки прерывания процессор обращается к очереди для выборки следующего задания — "готового" процесса. Если до выполнения данной процедуры все семафоры из списка С были открыты, выполняется следующая инструкция программы.

Процедура ЖДАТЬ (С) в случае, если в C указаны семафоры со значением "закрыт", организует прерывание процесса. Процесс, ставший пассивным, дополняет очереди к закрытым семафорам из списка C. Концом выполнения процедуры является переход к анализу очереди "к процессору" для последующей загрузки процессора.

Процедура ЖУЖ (С) не переводит процесс в очереди к семафорам, а организует ожидание процессором, на котором выполняется процесс, момента открытия всех семафоров в режиме "жужжания" — непрерывного опроса семафоров, указанных в списке C.

Процедура ЖДАТЬ (С,Т) ограничивает время ожидания семафоров, указанных в списке C, значением T.

Процедура ОТКРЫТЬ (С) присваивает семафорам, указанным в списке C, значение "открыт". Процессы снимаются с очереди к указанным в C семафорам и, если они не стоят в очереди к другим семафорам, переводятся в очередь "к процессору" в соответствии с их приоритетом. Выполнение этих процессов на процессорах будет продолжено с повторного выполнения тех процедур ЗАКРЫТЬ (C') или ЖДАТЬ (C''), на которых ранее произошло прерывание данной задачи. Таким образом, если прерывание произошло при выполнении процедуры ЗАКРЫТЬ (C'), то всем семафорам, указанным в списке C', вновь присваивается значение "закрыт". При этом, если среди множества семафоров $$C' C \ne \varnothing$$ окажутся такие, которые ранее были закрыты, или другой процесс (на другом процессоре) успел закрыть семафор из C' раньше, то выполнение данного процесса вновь прервется и он станет в очередь к закрытым семафорам.

Процедура ПРОПУСТИТЬ (С) полностью соответствует упрощенной версии процедуры ОТКРЫТЬ (C). Семафорам, перечисленным в списке C, присваивается значение "открыт", и процессы из очередей к данным семафорам переводятся в очередь "к процессору". Если процессы находились в очереди к семафорам из С после прерывания в результате выполнения процедур ЗАКРЫТЬ или ЖДАТЬ, то повторного выполнения этих процедур не происходит; процессы выполняются со следующей инструкции.

Пример.

Пусть в однопроцессорной ВС в режиме реального времени решаются две задачи A и B с разной частотой решения. Задачи оформлены и запускаются как отдельные процедуры. Задача A решается в цикле длительности T0, задача B — в цикле длительности T1 = 4T0, но не ранее, чем в цикле длительности T1 будет решена один раз задача A. Можно предположить использование сигналов прерывания в моменты времени, кратные T0. Однако для организации временного режима решения задач мы воспользуемся возможностями операций над семафорами.

Будем полагать, что в моменты времени, кратные T0, но не кратные T1, запускается управляющий процесс (супервизор) УПР0, а в моменты времени, кратные T1, — управляющий процесс (супервизор) УПР1. Требуемая временная диаграмма решения задач представлена на рис. 11.2.

(рис 11.2) Синхронизация совместного решения задач в циклах разной длительности

Пусть предварительно объявлены семафоры D1, D2, A, B1, B2.

Тогда в каждом из процессов могут быть запланированы операции над семафорами, как показано на рис. 11.3.

(рис 11.3) Использование операций над семафорами

Предположим, первоначально t0 = t1 = 0. Тогда из первых команд УПР0 видно, что он включается в моменты

T0, 2T0, 3T0, 5T0,....

УПР1 включается в моменты

0, T1, 2T1,....

Начальные значения семафоров A и B1 — "закрыт", семафора В2 — "открыт". Первоначально задачи A и B находятся в очереди "к процессору". При их назначении на процессор и при выполнении первых процедур ЖДАТЬ (А) и ЖДАТЬ (В1, В2) произойдет прерывание. После него задача A находится в очереди к семафору A, задача B — к семафору В1. Пусть приоритет задачи A выше приоритета задачи B. (Задачи, решаемые с большей частотой, как правило, снабжаются более высоким приоритетом.)

В момент времени, кратный T1, задача УПР1 закрывает семафор B2, но открывает семафоры A и B1. Задача A переводится в очередь "к процессору". Пусть одного процессора достаточно для выполнения всех задач. Тогда с учетом приоритета в мультипрограммном режиме задача В решается в промежутки времени, не занятые решением других задач. После выполнения задачи УПР1 начинается выполнение задачи A с закрытия семафора A. Так как до выполнения процедуры ЗАКРЫТЬ(А) семафор А имел значение "открыт", то прерывания выполнения задачи A не произойдет и она будет решена до конца. В конце ее решения по процедуре ПРОПУСТИТЬ(В2) откроется семафор B2 и задача B перейдет в очередь "к процессору". Задача A организована по принципу зацикливания, т.е. после ее окончания управление передается на ее начало с процедуры ЗАКРЫТЬ(А). Так как к моменту выполнения этой процедуры семафор A закрыт в результате ее предыдущего выполнения, произойдет прерывание и постановка задачи A в очередь к семафору A. Этот семафор откроется только при выполнении задачи УПР0 после увеличения текущего времени на T0. При этом, т.к. открытие семафора A в задаче УПР0 производится процедурой ОТКРЫТЬ, а прерывание задачи A произошло по процедуре ЗАКРЫТЬ, то выполнение задачи A продолжится с выполнения процедуры ЗАКРЫТЬ(А). Таким образом, более чем однократное решение задачи A без прерывания вновь окажется невозможным.

Аналогично по принципу зацикливания организовано и решение задачи B. После однократного выполнения она будет прервана при повторном выполнении процедуры ЗАКРЫТЬ(В1). Семафор B1 откроется только при следующем выполнении задачи УПР1 после увеличения текущего времени на . При этом выполнение задачи B продолжится с повторного выполнения процедуры ЗАКРЫТЬ(В1), т.к. семафор B1 открывается процедурой ОТКРЫТЬ. Однако продолжение выполнения задачи B станет возможным после открытия семафора B2. Он же окажется открытым только после однократного выполнения задачи A в цикле длительности T1 после выполнения процедуры ПРОПУСТИТЬ(В2) в конце решения задачи A. Использования этой процедуры в данном случае достаточно.

Таким образом, соблюдается требуемый порядок решения задач.

Теперь усложним пример. Предположим, что для решения задачи A одного процессора недостаточно и необходимо использовать возможности ее параллельного решения. Мы представляем эту задачу в виде частично упорядоченного множества информационно- взаимосвязанных работ — подзадач — и используем механизм семафоров для соблюдения порядка следования этих работ. При этом мы предполагаем, что в ВС реализовано децентрализованное диспетчирование, т.е. свободные процессоры обращаются за очередным заданием к очереди "к процессору". На рис. 11.4 представлена примерная граф-схема задачи на основе составляющих ее подзадач. Каждая вершина соответствует подзадаче. Стрелки определяют информационную преемственность. Процедура над семафорами, изображенная выше вершины, показывает, что соответствующая подзадача начинается с выполнения этой процедуры. Процедура, изображенная ниже вершины, показывает, что подзадача заканчивается выполнением этой процедуры.

(рис 11.4) Синхронизация параллельных вычислений с помощью семафоров

3. Передача сообщений, "почтовый ящик". Метод "почтовых ящиков" является распространенной формой метода передачи сообщений.

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

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

С помощью "почтовых ящиков" реализуется схема управления потоком данных (data flow), когда явное задание исходной информации для процесса является необходимым условием его запуска.

4. Механизм закрытия адресов. Осуществляется командой вида "закрыть адрес (по считыванию)". Адрес запоминается в специальном ЗУ, и при попытке считывания по нему производится ожидание — по аналогии с процедурой ЖУЖ. Открывается адрес по записи по нему. Для избежания тупиковых ситуаций, например,

ЗАКР    a
      СЧИТАТЬ    a

указывается номер того процессора, который закрыл адрес. Тогда есть возможность принять какое-то решение. Например, разрешить процессору, закрывшему адрес, открыть его.

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

Такой способ синхронизации был приведен при рассмотрении архитектуры SPMD.

5. Механизм активного ожидания.

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

Пример рассмотрим далее, совместив его с рассмотрением одной из задач синхронизации.

6. Монитор.

Монитор - скорее сервисное средство, позволяющее пользователю избежать заботы о синхронизации использования разделяемых ресурсов. Это программный компонент, в котором разделяемые переменные (представленные именами разделяемых ресурсов) определены как локальные переменные монитора. Определены операции над этими переменными - процедуры монитора. Одновременно только один процесс работает с монитором! Когда процессу требуется работать с разделяемой переменной, активизируется соответствующая процедура монитора. Если при обращении процесса к монитору ресурс занят, то вызывающий процесс должен быть задержан.

С каждой причиной задержки процесса связана специальная переменная типа CONDITION (условие), и задерживаемый процесс ставится в очередь к некоторой переменной этого типа.

К переменным указанного типа применяются операции WAIT и SIGNAL. Операция WAIT ставит процесс в очередь к данной переменной (например, указывающей на занятость соответствующего ресурса). Операция SIGNAL позволяет активизировать процесс (в случае, когда условие выполнено).

Задачи синхронизации при использовании разделяемых ресурсов

Основные понятия

Объектами распараллеливания являются неделимые процессы — работы, на которые разбивается исходный алгоритм или разрабатываемая программная система.

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

Ресурсы, используемые несколькими процессами, называются разделяемыми.

Разделяемые ресурсы, которые одновременно могут использоваться не более чем одним процессом, называются критическими ресурсами. (Например, очередь "к процессору" — критический ресурс.)

Участки программы (процесса), где процессы обращаются к разделяемому ресурсу, называются критическими интервалами (блоками, секциями).

Процессы называются взаимосвязанными, если они используют общие критические ресурсы.

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

Например, процессу A необходимы внешние устройства X, Y. С устройством Y пока работает процесс B. Тогда процесс A "захватывает" пока устройство X и ждет освобождения Y. Но устройство X потребовалось и процессу B, который также "зависает" в ожидании его освобождения.

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

Выше был приведен пример:

  • "Закрыть адрес по считыванию" a
  • "Считать по адресу" а
    •

    Здесь возможен локальный тупик — бесконечное выполнение команды (2), если другой процесс (на другом процессоре) или ОС не "откроет" адрес а.

    Задачи синхронизации

    Известны типичные задачи синхронизации, к которым могут быть сведены практически все известные способы упорядочения работ во времени. Эти задачи, как правило, решаются при реализации второго способа распараллеливания.

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

    Требования к решению этой задачи:

  • задержка любого процесса вне его критического интервала не должна влиять на развитие других процессов;
  • решение должно быть симметрично относительно процессов;
  • решение не должно допускать тупиков.
    •

    Решение с помощью механизма семафоров:$$\begin{center} \fbox{\parbox{0.5\textwidth}{\centering ЗАКРЫТЬ(С)\\ <Критический интервал >\\ Открыть(С) }} \end{center}$$

    Для сравнения приведем альтернативный способ решения с помощью механизма активного ожидания.

    Выделим ячейку памяти C, в которую будем записывать 0, если ни один из процессов не требует доступа к критическому ресурсу, и номер i того процесса (или выполняющего процессора), который вступил в свой критический интервал. Тогда условием вхождения i -го процесса в критический интервал является результат выполнения следующего оператора:$$\begin{center} \fbox{\parbox{0.5\textwidth}{\centering L: if C<>0 then go to L else C:= i;\\ if C<> i then go to L;\\ <Критический интервал>;>\\ C:=0 }} \end{center}$$

    Действительно, если (C) = 0, то процесс может войти в критический интервал. Однако возможно, что через небольшое время другой процесс (на другом процессоре) тоже сделал такую же проверку и следом за первым произвел засылку в C своего номера. Поэтому требуется повторная проверка того, что в C находится именно номер данного процесса. При положительном результате повторного анализа процесс может вступить в критический интервал, т.е. занять критический ресурс. После выполнения критического интервала в C засылается 0.

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

    2. Задача "поставщики — потребители". Имеется ограниченный буфер на несколько порций информации. Он является критическим ресурсом для процессов двух типов:

  • процессы "поставщики", получая доступ к ресурсу, помещают на свободное место в буфере несколько или одну порцию информации;
  • процессы "потребители", получая доступ к ресурсу, считывают из него порции информации.
    •

    Требуется исключить одновременный доступ к ресурсу любых двух процессов. При опустошении буфера следует задерживать процессы "потребители", при полном заполнении буфера — процессы "поставщики".

    Эта задача возникает, например, при обмене с внешними устройствами и заключается в программной имитации кольцевого или бесконечного буфера.

    Возможная схема решения задачи с помощью семафоров:$$\begin{center} Процесс "ПОСТАВЩИК":\hspace{20mm} Процесс "ПОТРЕБИТЕЛЬ":\\ \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С)\\ if <Буфер неполон> then\\ begin < запись>;\\ <изменение индикатора\\ заполнения>\\ end\\ ОТКРЫТЬ(С) }} \hspace{7mm} \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С)\\ if<Буфер непуст> then\\ begin < считывание>;\\ <изменение индикатора\\ заполнения>\\ end\\ ОТКРЫТЬ(С) }} \end{center}$$

    Имитация кольцевого (бесконечного) буфера показана на рис. 11.5.

    (рис 11.5) Кольцевой (бесконечный) буфер)

    Тогда уточним данную процедуру с учетом используемых индикаторов считывания и заполнения.$$\begin{center} Процесс "ПОСТАВЩИК":\hspace{20mm} Процесс "ПОТРЕБИТЕЛЬ": \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С)\\ if (in + 1)mod N \ne out \; then\\ begin\\ in := (in + 1)mod N ;\\ <запись(in)>\\ end\\ ОТКРЫТЬ(С) }} \hspace{7mm} \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С)\\ if (out + 1)mod N \ne in \; then\\ begin\\ out := (out + 1)mod N ;\\ <считывание(out)>\\ end\\ ОТКРЫТЬ(С) }} \end{center}$$

    3. Задача "читатели — писатели".

    Имеется разделяемый ресурс — область памяти, к которой требуется доступ процессам двух типов:

    Процессы первого типа — "ЧИТАТЕЛИ" — могут получать доступ к разделяемому ресурсу одновременно. Они считывают информацию.

    Процессы второго типа — "ПИСАТЕЛИ" — взаимно исключают и друг друга, и "читателей". Они записывают в разделяемую область памяти данные.

    Задача известна в двух вариантах:

  • "Читатели", изъявившие желание получить доступ к ресурсу, должны получить его как можно быстрее; это — первая задача ЧП.
  • 2. "Читатели", изъявившие желание получить доступ к ресурсу, должны получить его как можно быстрее, если отсутствуют запросы от "писателей". "Писатель", требующий доступ к ресурсу, должен получить его как можно быстрее, но после обслуживания "читателей", подошедших к ресурсу до первого "писателя". Это — вторая задача ЧП.
    •

    Приведем возможное решение задач с помощью комбинированного семафора.

    Считаем, что процедура ОТКРЫТЬ ПО СЧИТЫВАНИЮ выполняется подобно процедуре ПРОПУСТИТЬ, изменяя только значение семафора-счетчика. Процедура ОТКРЫТЬ ПО ЗАПИСИ выполняется подобно процедуре ОТКРЫТЬ, "открывая" семафор и обеспечивая запуск "задержанных" процессов с процедур ЗАКРЫТЬ ПО ЗАПИСИ или ЖДАТЬ ПО ЗАПИСИ, при выполнении которых произошло прерывание.

    Тогда критические интервалы для каждой задачи могут быть выполнены по следующим схемам.$$\begin{center} ЧП-1\\ Процесс "ЧИТАТЕЛЬ": \hspace{20mm} Процесс "ПИСАТЕЛЬ":\\ \fbox{\parbox{0.4\textwidth}{\centering ЖДАТЬ ПО ЗАПИСИ(С)\\ ЗАКРЫТЬ ПО СЧИТЫВАНИЮ(С)\\ < читать >\\ ОТКРЫТЬ ПО СЧИТЫВАНИЮ(С)\\ }} \hspace{7mm} \fbox{\parbox{0.4\textwidth}{\centering ЖДАТЬ ПО СЧИТЫВАНИЮ(С)\\ ЗАКРЫТЬ ПО ЗАПИСИ(С)\\ < писать >\\ ОТКРЫТЬ ПО ЗАПИСИ(С) }} \end{center} \begin{center} ЧП-2\\ Процесс "ЧИТАТЕЛЬ":\hspace{20mm} Процесс "ПИСАТЕЛЬ":\\ \fbox{\parbox{0.4\textwidth}{\centering ЖДАТЬ ПО ЗАПИСИ(С)\\ ЗАКРЫТЬ ПО СЧИТЫВАНИЮ(С)\\ < читать >\\ ОТКРЫТЬ ПО СЧИТЫВАНИЮ(С) }} \hspace{7mm} \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ ПО ЗАПИСИ(С)\\ ЖДАТЬ ПО СЧИТЫВАНИЮ(С)\\ < писать >\\ ОТКРЫТЬ ПО ЗАПИСИ(С) }} \end{center}$$

    4. Задача "обедающие философы". За круглым столом сидят k философов, которые проводят время, чередуя философские размышления с потреблением пищи. Перед каждым — тарелка спагетти, между тарелками — по одной вилке. Для еды каждому философу требуются две вилки. Использовать можно только вилки, лежащие рядом с тарелками. Так как переходы от размышления к принятию пищи производятся в непредсказуемые моменты времени, то возможны конфликты и требуется синхронизация процессов.

    Представим следующую модель, требующую решение данной задачи, — модель оперативного обмена между процессорами векторной ВС или строк (столбцов) матричной ВС (рис. 11.6).

    (рис 11.6) Связь по схеме "обедающие философы"

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

    Пусть с i -м процессором для передачи влево связан "левый" семафор Ci, для передачи вправо — "правый" семафор Ci+1 (или наоборот). Пусть каждый процессор, нуждающийся в передаче двум соседям, пытается сначала закрыть свой "правый" (аналогично, "левый") семафор. Затем, если это не успел сделать левый сосед, он попытается закрыть "левый" семафор и произвести передачу. Тогда возможен общий тупик, если все процессоры одновременно закроют все семафоры. (При одновременном пересчете значений функции в узлах сетки вероятность такой ситуации высока.)

    Разрешим четным процессорам сначала закрывать "левые" ("правые") семафоры, а нечетным — "правые" ("левые"). Тогда схемы программ для них будут выглядеть следующим образом:$$\begin{center} Для четных процессоров:\hspace{20mm} Для нечетных процессоров:\\ \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С_i)\\ ЗАКРЫТЬ(С_{i+1})\\ < передача >\\ ОТКРЫТЬ(С_i,C_{i+1}) }} \hspace{7mm} \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С_{i+1})\\ ЗАКРЫТЬ(С_i)\\ < передача >\\ ОТКРЫТЬ(С_i,C_{i+1}) }} \end{center}$$

    Пусть процессор с нечетным номером i нуждается в обмене — влево и вправо. Он пытается выполнить процедуру ЗАКРЫТЬ (Ci+1). Предположим, что этот семафор (для него — "правый") закрыт i+1 -м процессором. Но для этого процессора с четным номером этот семафор — также первый в порядке закрытия ("левый"). Следовательно, он либо ждет возможности закрытия своего "правого" семафора, либо ведет обмен. Если он ждет своего "правого" семафора, то он его дождется, т.к. он — второй для процессора i+2, ведущего обмен. Значит, этот процессор закончит обмен и откроет свой "левый" семафор. Тогда процессор i+1 выполнит обмен и откроет семафор Ci+1. Тогда и процессор i, наконец, сможет выполнить необходимую процедуру. После этого он попытается выполнить процедуру ЗАКРЫТЬ (Ci). Этот семафор является "правым", т.е. вторым для процессора с четным номером i-1. Следовательно, этот процессор закрыл оба связанных с ним семафора и ведет обмен. По окончании обмена он откроет семафоры, и процессор i дождется необходимого "левого" семафора и сможет его закрыть для себя. Таким образом, тупиковая ситуация возникнуть не может.

    Обычно n — степень двойки. Если же n нечетно, то на границе $$n \leftrightarrow 1$$ взаимодействуют два "нечетных" процесса обмена. Здесь возможна блокировка, когда процессор 1 закроет C2, а процессор n — семафор C1 (1 = (n+1)mod n). Однако, процессор n обязательно дождется открытия семафора Cn и выполнит обмен. Значит и процессор 1 дождется открытия семафора C1, выполнит обмен и откроет C2. Так что тупики и в данном случае исключены.

    Рассмотрение данной задачи синхронизации выводит нас за рамки традиционного применения мультипроцессорной системы типа MIMD, к каким относятся, например, ВС семейства "Эльбрус". Однако универсальность такой архитектуры допускает принципиальную возможность воспроизведения на ней более "жестких" архитектур — матричных и векторных, т.е. типа SIMD. Реализация метода "сеток" на матричных ВС или на структурах типа "гиперкуб" требует подобной передачи не только двум соседним процессорам по строке, но и соседним по столбцу, по диагонали и т.д. Значит, возможно обобщение данной задачи и алгоритма синхронизации. Указанный выше прием разделения процессоров на четные и нечетные может быть применен по всем направлениям обмена — по строкам, по столбцам, по диагонали и т.д.

    5.Задача обновления данных. Предполагает запрет на использование обновляемых данных. Например, процессор обновляет запись в базе данных. В простейшем случае может быть использован признак, по которому запрещается обращение к данной записи, пока она не будет обновлена. (Конечно, мы не рассматриваем того примитивного решения, когда БД превращается в ресурс с последовательным доступом. Мы стремимся к многоканальному, параллельному доступу.)

    Вместо признака может быть использован семафор. Ожидание может быть организовано процедурами ЖДАТЬ или ЖУЖ.

    Страницы:

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

    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. Значение $$Сб \ne 0$$ означает: семафор C "закрыт по считыванию".

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

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

    Перечислим основные процедуры над семафорами, реализуемые в МВК "Эльбрус".

    Процедура ОБЪЯВИТЬ (С) объявляет список семафоров, который рассматривается как описание, действующее внутри данного блока в алгоритмическом языке. Этим обеспечивается выделение памяти и тип переменной при трансляции.

    Процедура ЗАКРЫТЬ (С) сначала присваивает семафорам, перечисленным в списке C, значение "закрыт". Затем для каждого семафора она проверяет, был ли он закрыт ранее. Если в списке C семафоров указан один или несколько семафоров, которые были закрыты до выполнения данной процедуры, происходит прерывание процесса (задачи). Процедура ОС, запустившаяся по прерыванию, ставит данный процесс в очередь к тем семафорам, которые были закрыты ранее. Таким образом, процесс задерживается до тех пор, пока другие процессы не откроют эти семафоры. После прерывания процесса и обработки прерывания процессор обращается к очереди для выборки следующего задания — "готового" процесса. Если до выполнения данной процедуры все семафоры из списка С были открыты, выполняется следующая инструкция программы.

    Процедура ЖДАТЬ (С) в случае, если в C указаны семафоры со значением "закрыт", организует прерывание процесса. Процесс, ставший пассивным, дополняет очереди к закрытым семафорам из списка C. Концом выполнения процедуры является переход к анализу очереди "к процессору" для последующей загрузки процессора.

    Процедура ЖУЖ (С) не переводит процесс в очереди к семафорам, а организует ожидание процессором, на котором выполняется процесс, момента открытия всех семафоров в режиме "жужжания" — непрерывного опроса семафоров, указанных в списке C.

    Процедура ЖДАТЬ (С,Т) ограничивает время ожидания семафоров, указанных в списке C, значением T.

    Процедура ОТКРЫТЬ (С) присваивает семафорам, указанным в списке C, значение "открыт". Процессы снимаются с очереди к указанным в C семафорам и, если они не стоят в очереди к другим семафорам, переводятся в очередь "к процессору" в соответствии с их приоритетом. Выполнение этих процессов на процессорах будет продолжено с повторного выполнения тех процедур ЗАКРЫТЬ (C') или ЖДАТЬ (C''), на которых ранее произошло прерывание данной задачи. Таким образом, если прерывание произошло при выполнении процедуры ЗАКРЫТЬ (C'), то всем семафорам, указанным в списке C', вновь присваивается значение "закрыт". При этом, если среди множества семафоров $$C' C \ne \varnothing$$ окажутся такие, которые ранее были закрыты, или другой процесс (на другом процессоре) успел закрыть семафор из C' раньше, то выполнение данного процесса вновь прервется и он станет в очередь к закрытым семафорам.

    Процедура ПРОПУСТИТЬ (С) полностью соответствует упрощенной версии процедуры ОТКРЫТЬ (C). Семафорам, перечисленным в списке C, присваивается значение "открыт", и процессы из очередей к данным семафорам переводятся в очередь "к процессору". Если процессы находились в очереди к семафорам из С после прерывания в результате выполнения процедур ЗАКРЫТЬ или ЖДАТЬ, то повторного выполнения этих процедур не происходит; процессы выполняются со следующей инструкции.

    Пример.

    Пусть в однопроцессорной ВС в режиме реального времени решаются две задачи A и B с разной частотой решения. Задачи оформлены и запускаются как отдельные процедуры. Задача A решается в цикле длительности T0, задача B — в цикле длительности T1 = 4T0, но не ранее, чем в цикле длительности T1 будет решена один раз задача A. Можно предположить использование сигналов прерывания в моменты времени, кратные T0. Однако для организации временного режима решения задач мы воспользуемся возможностями операций над семафорами.

    Будем полагать, что в моменты времени, кратные T0, но не кратные T1, запускается управляющий процесс (супервизор) УПР0, а в моменты времени, кратные T1, — управляющий процесс (супервизор) УПР1. Требуемая временная диаграмма решения задач представлена на рис. 11.2.

    (рис 11.2) Синхронизация совместного решения задач в циклах разной длительности

    Пусть предварительно объявлены семафоры D1, D2, A, B1, B2.

    Тогда в каждом из процессов могут быть запланированы операции над семафорами, как показано на рис. 11.3.

    (рис 11.3) Использование операций над семафорами

    Предположим, первоначально t0 = t1 = 0. Тогда из первых команд УПР0 видно, что он включается в моменты

    T0, 2T0, 3T0, 5T0,....

    УПР1 включается в моменты

    0, T1, 2T1,....

    Начальные значения семафоров A и B1 — "закрыт", семафора В2 — "открыт". Первоначально задачи A и B находятся в очереди "к процессору". При их назначении на процессор и при выполнении первых процедур ЖДАТЬ (А) и ЖДАТЬ (В1, В2) произойдет прерывание. После него задача A находится в очереди к семафору A, задача B — к семафору В1. Пусть приоритет задачи A выше приоритета задачи B. (Задачи, решаемые с большей частотой, как правило, снабжаются более высоким приоритетом.)

    В момент времени, кратный T1, задача УПР1 закрывает семафор B2, но открывает семафоры A и B1. Задача A переводится в очередь "к процессору". Пусть одного процессора достаточно для выполнения всех задач. Тогда с учетом приоритета в мультипрограммном режиме задача В решается в промежутки времени, не занятые решением других задач. После выполнения задачи УПР1 начинается выполнение задачи A с закрытия семафора A. Так как до выполнения процедуры ЗАКРЫТЬ(А) семафор А имел значение "открыт", то прерывания выполнения задачи A не произойдет и она будет решена до конца. В конце ее решения по процедуре ПРОПУСТИТЬ(В2) откроется семафор B2 и задача B перейдет в очередь "к процессору". Задача A организована по принципу зацикливания, т.е. после ее окончания управление передается на ее начало с процедуры ЗАКРЫТЬ(А). Так как к моменту выполнения этой процедуры семафор A закрыт в результате ее предыдущего выполнения, произойдет прерывание и постановка задачи A в очередь к семафору A. Этот семафор откроется только при выполнении задачи УПР0 после увеличения текущего времени на T0. При этом, т.к. открытие семафора A в задаче УПР0 производится процедурой ОТКРЫТЬ, а прерывание задачи A произошло по процедуре ЗАКРЫТЬ, то выполнение задачи A продолжится с выполнения процедуры ЗАКРЫТЬ(А). Таким образом, более чем однократное решение задачи A без прерывания вновь окажется невозможным.

    Аналогично по принципу зацикливания организовано и решение задачи B. После однократного выполнения она будет прервана при повторном выполнении процедуры ЗАКРЫТЬ(В1). Семафор B1 откроется только при следующем выполнении задачи УПР1 после увеличения текущего времени на . При этом выполнение задачи B продолжится с повторного выполнения процедуры ЗАКРЫТЬ(В1), т.к. семафор B1 открывается процедурой ОТКРЫТЬ. Однако продолжение выполнения задачи B станет возможным после открытия семафора B2. Он же окажется открытым только после однократного выполнения задачи A в цикле длительности T1 после выполнения процедуры ПРОПУСТИТЬ(В2) в конце решения задачи A. Использования этой процедуры в данном случае достаточно.

    Таким образом, соблюдается требуемый порядок решения задач.

    Теперь усложним пример. Предположим, что для решения задачи A одного процессора недостаточно и необходимо использовать возможности ее параллельного решения. Мы представляем эту задачу в виде частично упорядоченного множества информационно- взаимосвязанных работ — подзадач — и используем механизм семафоров для соблюдения порядка следования этих работ. При этом мы предполагаем, что в ВС реализовано децентрализованное диспетчирование, т.е. свободные процессоры обращаются за очередным заданием к очереди "к процессору". На рис. 11.4 представлена примерная граф-схема задачи на основе составляющих ее подзадач. Каждая вершина соответствует подзадаче. Стрелки определяют информационную преемственность. Процедура над семафорами, изображенная выше вершины, показывает, что соответствующая подзадача начинается с выполнения этой процедуры. Процедура, изображенная ниже вершины, показывает, что подзадача заканчивается выполнением этой процедуры.

    (рис 11.4) Синхронизация параллельных вычислений с помощью семафоров

    3. Передача сообщений, "почтовый ящик". Метод "почтовых ящиков" является распространенной формой метода передачи сообщений.

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

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

    С помощью "почтовых ящиков" реализуется схема управления потоком данных (data flow), когда явное задание исходной информации для процесса является необходимым условием его запуска.

    4. Механизм закрытия адресов. Осуществляется командой вида "закрыть адрес (по считыванию)". Адрес запоминается в специальном ЗУ, и при попытке считывания по нему производится ожидание — по аналогии с процедурой ЖУЖ. Открывается адрес по записи по нему. Для избежания тупиковых ситуаций, например,

    ЗАКР    a
      СЧИТАТЬ    a

    указывается номер того процессора, который закрыл адрес. Тогда есть возможность принять какое-то решение. Например, разрешить процессору, закрывшему адрес, открыть его.

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

    Такой способ синхронизации был приведен при рассмотрении архитектуры SPMD.

    5. Механизм активного ожидания.

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

    Пример рассмотрим далее, совместив его с рассмотрением одной из задач синхронизации.

    6. Монитор.

    Монитор - скорее сервисное средство, позволяющее пользователю избежать заботы о синхронизации использования разделяемых ресурсов. Это программный компонент, в котором разделяемые переменные (представленные именами разделяемых ресурсов) определены как локальные переменные монитора. Определены операции над этими переменными - процедуры монитора. Одновременно только один процесс работает с монитором! Когда процессу требуется работать с разделяемой переменной, активизируется соответствующая процедура монитора. Если при обращении процесса к монитору ресурс занят, то вызывающий процесс должен быть задержан.

    С каждой причиной задержки процесса связана специальная переменная типа CONDITION (условие), и задерживаемый процесс ставится в очередь к некоторой переменной этого типа.

    К переменным указанного типа применяются операции WAIT и SIGNAL. Операция WAIT ставит процесс в очередь к данной переменной (например, указывающей на занятость соответствующего ресурса). Операция SIGNAL позволяет активизировать процесс (в случае, когда условие выполнено).

    Задачи синхронизации при использовании разделяемых ресурсов

    Основные понятия

    Объектами распараллеливания являются неделимые процессы — работы, на которые разбивается исходный алгоритм или разрабатываемая программная система.

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

    Ресурсы, используемые несколькими процессами, называются разделяемыми.

    Разделяемые ресурсы, которые одновременно могут использоваться не более чем одним процессом, называются критическими ресурсами. (Например, очередь "к процессору" — критический ресурс.)

    Участки программы (процесса), где процессы обращаются к разделяемому ресурсу, называются критическими интервалами (блоками, секциями).

    Процессы называются взаимосвязанными, если они используют общие критические ресурсы.

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

    Например, процессу A необходимы внешние устройства X, Y. С устройством Y пока работает процесс B. Тогда процесс A "захватывает" пока устройство X и ждет освобождения Y. Но устройство X потребовалось и процессу B, который также "зависает" в ожидании его освобождения.

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

    Выше был приведен пример:

  • "Закрыть адрес по считыванию" a
  • "Считать по адресу" а
    •

    Здесь возможен локальный тупик — бесконечное выполнение команды (2), если другой процесс (на другом процессоре) или ОС не "откроет" адрес а.

    Задачи синхронизации

    Известны типичные задачи синхронизации, к которым могут быть сведены практически все известные способы упорядочения работ во времени. Эти задачи, как правило, решаются при реализации второго способа распараллеливания.

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

    Требования к решению этой задачи:

  • задержка любого процесса вне его критического интервала не должна влиять на развитие других процессов;
  • решение должно быть симметрично относительно процессов;
  • решение не должно допускать тупиков.
    •

    Решение с помощью механизма семафоров:$$\begin{center} \fbox{\parbox{0.5\textwidth}{\centering ЗАКРЫТЬ(С)\\ <Критический интервал >\\ Открыть(С) }} \end{center}$$

    Для сравнения приведем альтернативный способ решения с помощью механизма активного ожидания.

    Выделим ячейку памяти C, в которую будем записывать 0, если ни один из процессов не требует доступа к критическому ресурсу, и номер i того процесса (или выполняющего процессора), который вступил в свой критический интервал. Тогда условием вхождения i -го процесса в критический интервал является результат выполнения следующего оператора:$$\begin{center} \fbox{\parbox{0.5\textwidth}{\centering L: if C<>0 then go to L else C:= i;\\ if C<> i then go to L;\\ <Критический интервал>;>\\ C:=0 }} \end{center}$$

    Действительно, если (C) = 0, то процесс может войти в критический интервал. Однако возможно, что через небольшое время другой процесс (на другом процессоре) тоже сделал такую же проверку и следом за первым произвел засылку в C своего номера. Поэтому требуется повторная проверка того, что в C находится именно номер данного процесса. При положительном результате повторного анализа процесс может вступить в критический интервал, т.е. занять критический ресурс. После выполнения критического интервала в C засылается 0.

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

    2. Задача "поставщики — потребители". Имеется ограниченный буфер на несколько порций информации. Он является критическим ресурсом для процессов двух типов:

  • процессы "поставщики", получая доступ к ресурсу, помещают на свободное место в буфере несколько или одну порцию информации;
  • процессы "потребители", получая доступ к ресурсу, считывают из него порции информации.
    •

    Требуется исключить одновременный доступ к ресурсу любых двух процессов. При опустошении буфера следует задерживать процессы "потребители", при полном заполнении буфера — процессы "поставщики".

    Эта задача возникает, например, при обмене с внешними устройствами и заключается в программной имитации кольцевого или бесконечного буфера.

    Возможная схема решения задачи с помощью семафоров:$$\begin{center} Процесс "ПОСТАВЩИК":\hspace{20mm} Процесс "ПОТРЕБИТЕЛЬ":\\ \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С)\\ if <Буфер неполон> then\\ begin < запись>;\\ <изменение индикатора\\ заполнения>\\ end\\ ОТКРЫТЬ(С) }} \hspace{7mm} \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С)\\ if<Буфер непуст> then\\ begin < считывание>;\\ <изменение индикатора\\ заполнения>\\ end\\ ОТКРЫТЬ(С) }} \end{center}$$

    Имитация кольцевого (бесконечного) буфера показана на рис. 11.5.

    (рис 11.5) Кольцевой (бесконечный) буфер)

    Тогда уточним данную процедуру с учетом используемых индикаторов считывания и заполнения.$$\begin{center} Процесс "ПОСТАВЩИК":\hspace{20mm} Процесс "ПОТРЕБИТЕЛЬ": \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С)\\ if (in + 1)mod N \ne out \; then\\ begin\\ in := (in + 1)mod N ;\\ <запись(in)>\\ end\\ ОТКРЫТЬ(С) }} \hspace{7mm} \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С)\\ if (out + 1)mod N \ne in \; then\\ begin\\ out := (out + 1)mod N ;\\ <считывание(out)>\\ end\\ ОТКРЫТЬ(С) }} \end{center}$$

    3. Задача "читатели — писатели".

    Имеется разделяемый ресурс — область памяти, к которой требуется доступ процессам двух типов:

    Процессы первого типа — "ЧИТАТЕЛИ" — могут получать доступ к разделяемому ресурсу одновременно. Они считывают информацию.

    Процессы второго типа — "ПИСАТЕЛИ" — взаимно исключают и друг друга, и "читателей". Они записывают в разделяемую область памяти данные.

    Задача известна в двух вариантах:

  • "Читатели", изъявившие желание получить доступ к ресурсу, должны получить его как можно быстрее; это — первая задача ЧП.
  • 2. "Читатели", изъявившие желание получить доступ к ресурсу, должны получить его как можно быстрее, если отсутствуют запросы от "писателей". "Писатель", требующий доступ к ресурсу, должен получить его как можно быстрее, но после обслуживания "читателей", подошедших к ресурсу до первого "писателя". Это — вторая задача ЧП.
    •

    Приведем возможное решение задач с помощью комбинированного семафора.

    Считаем, что процедура ОТКРЫТЬ ПО СЧИТЫВАНИЮ выполняется подобно процедуре ПРОПУСТИТЬ, изменяя только значение семафора-счетчика. Процедура ОТКРЫТЬ ПО ЗАПИСИ выполняется подобно процедуре ОТКРЫТЬ, "открывая" семафор и обеспечивая запуск "задержанных" процессов с процедур ЗАКРЫТЬ ПО ЗАПИСИ или ЖДАТЬ ПО ЗАПИСИ, при выполнении которых произошло прерывание.

    Тогда критические интервалы для каждой задачи могут быть выполнены по следующим схемам.$$\begin{center} ЧП-1\\ Процесс "ЧИТАТЕЛЬ": \hspace{20mm} Процесс "ПИСАТЕЛЬ":\\ \fbox{\parbox{0.4\textwidth}{\centering ЖДАТЬ ПО ЗАПИСИ(С)\\ ЗАКРЫТЬ ПО СЧИТЫВАНИЮ(С)\\ < читать >\\ ОТКРЫТЬ ПО СЧИТЫВАНИЮ(С)\\ }} \hspace{7mm} \fbox{\parbox{0.4\textwidth}{\centering ЖДАТЬ ПО СЧИТЫВАНИЮ(С)\\ ЗАКРЫТЬ ПО ЗАПИСИ(С)\\ < писать >\\ ОТКРЫТЬ ПО ЗАПИСИ(С) }} \end{center} \begin{center} ЧП-2\\ Процесс "ЧИТАТЕЛЬ":\hspace{20mm} Процесс "ПИСАТЕЛЬ":\\ \fbox{\parbox{0.4\textwidth}{\centering ЖДАТЬ ПО ЗАПИСИ(С)\\ ЗАКРЫТЬ ПО СЧИТЫВАНИЮ(С)\\ < читать >\\ ОТКРЫТЬ ПО СЧИТЫВАНИЮ(С) }} \hspace{7mm} \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ ПО ЗАПИСИ(С)\\ ЖДАТЬ ПО СЧИТЫВАНИЮ(С)\\ < писать >\\ ОТКРЫТЬ ПО ЗАПИСИ(С) }} \end{center}$$

    4. Задача "обедающие философы". За круглым столом сидят k философов, которые проводят время, чередуя философские размышления с потреблением пищи. Перед каждым — тарелка спагетти, между тарелками — по одной вилке. Для еды каждому философу требуются две вилки. Использовать можно только вилки, лежащие рядом с тарелками. Так как переходы от размышления к принятию пищи производятся в непредсказуемые моменты времени, то возможны конфликты и требуется синхронизация процессов.

    Представим следующую модель, требующую решение данной задачи, — модель оперативного обмена между процессорами векторной ВС или строк (столбцов) матричной ВС (рис. 11.6).

    (рис 11.6) Связь по схеме "обедающие философы"

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

    Пусть с i -м процессором для передачи влево связан "левый" семафор Ci, для передачи вправо — "правый" семафор Ci+1 (или наоборот). Пусть каждый процессор, нуждающийся в передаче двум соседям, пытается сначала закрыть свой "правый" (аналогично, "левый") семафор. Затем, если это не успел сделать левый сосед, он попытается закрыть "левый" семафор и произвести передачу. Тогда возможен общий тупик, если все процессоры одновременно закроют все семафоры. (При одновременном пересчете значений функции в узлах сетки вероятность такой ситуации высока.)

    Разрешим четным процессорам сначала закрывать "левые" ("правые") семафоры, а нечетным — "правые" ("левые"). Тогда схемы программ для них будут выглядеть следующим образом:$$\begin{center} Для четных процессоров:\hspace{20mm} Для нечетных процессоров:\\ \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С_i)\\ ЗАКРЫТЬ(С_{i+1})\\ < передача >\\ ОТКРЫТЬ(С_i,C_{i+1}) }} \hspace{7mm} \fbox{\parbox{0.4\textwidth}{\centering ЗАКРЫТЬ(С_{i+1})\\ ЗАКРЫТЬ(С_i)\\ < передача >\\ ОТКРЫТЬ(С_i,C_{i+1}) }} \end{center}$$

    Пусть процессор с нечетным номером i нуждается в обмене — влево и вправо. Он пытается выполнить процедуру ЗАКРЫТЬ (Ci+1). Предположим, что этот семафор (для него — "правый") закрыт i+1 -м процессором. Но для этого процессора с четным номером этот семафор — также первый в порядке закрытия ("левый"). Следовательно, он либо ждет возможности закрытия своего "правого" семафора, либо ведет обмен. Если он ждет своего "правого" семафора, то он его дождется, т.к. он — второй для процессора i+2, ведущего обмен. Значит, этот процессор закончит обмен и откроет свой "левый" семафор. Тогда процессор i+1 выполнит обмен и откроет семафор Ci+1. Тогда и процессор i, наконец, сможет выполнить необходимую процедуру. После этого он попытается выполнить процедуру ЗАКРЫТЬ (Ci). Этот семафор является "правым", т.е. вторым для процессора с четным номером i-1. Следовательно, этот процессор закрыл оба связанных с ним семафора и ведет обмен. По окончании обмена он откроет семафоры, и процессор i дождется необходимого "левого" семафора и сможет его закрыть для себя. Таким образом, тупиковая ситуация возникнуть не может.

    Обычно n — степень двойки. Если же n нечетно, то на границе $$n \leftrightarrow 1$$ взаимодействуют два "нечетных" процесса обмена. Здесь возможна блокировка, когда процессор 1 закроет C2, а процессор n — семафор C1 (1 = (n+1)mod n). Однако, процессор n обязательно дождется открытия семафора Cn и выполнит обмен. Значит и процессор 1 дождется открытия семафора C1, выполнит обмен и откроет C2. Так что тупики и в данном случае исключены.

    Рассмотрение данной задачи синхронизации выводит нас за рамки традиционного применения мультипроцессорной системы типа MIMD, к каким относятся, например, ВС семейства "Эльбрус". Однако универсальность такой архитектуры допускает принципиальную возможность воспроизведения на ней более "жестких" архитектур — матричных и векторных, т.е. типа SIMD. Реализация метода "сеток" на матричных ВС или на структурах типа "гиперкуб" требует подобной передачи не только двум соседним процессорам по строке, но и соседним по столбцу, по диагонали и т.д. Значит, возможно обобщение данной задачи и алгоритма синхронизации. Указанный выше прием разделения процессоров на четные и нечетные может быть применен по всем направлениям обмена — по строкам, по столбцам, по диагонали и т.д.

    5.Задача обновления данных. Предполагает запрет на использование обновляемых данных. Например, процессор обновляет запись в базе данных. В простейшем случае может быть использован признак, по которому запрещается обращение к данной записи, пока она не будет обновлена. (Конечно, мы не рассматриваем того примитивного решения, когда БД превращается в ресурс с последовательным доступом. Мы стремимся к многоканальному, параллельному доступу.)

    Вместо признака может быть использован семафор. Ожидание может быть организовано процедурами ЖДАТЬ или ЖУЖ.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^