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

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

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

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

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

Решение с помощью механизма семафоров:

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

Выделим ячейку памяти C, в которую будем записывать 0, если ни один из процессов не требует доступа к критическому ресурсу, и номер i того процесса (или выполняющего процессора), который вступил в свой критический интервал. Тогда условием вхождения i-го процесса в критический интервал является результат выполнения следующего оператора:

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

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

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

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

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

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

Возможная схема решения задачи с помощью семафоров:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание раздела