Типовые задачи синхронизации

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

К типовым задачам синхронизации можно отнести:

• взаимное исключение;

• обедающие философы;

• поставщики - потребители;

• читатели - писатели.

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

Задача "обедающие философы": на круглом столе находятся k тарелок с едой, между которыми лежит столько же вилок, k>=2. В комнате имеется k философов, чередующих философские размышления с принятием пищи. За каждым философом закреплена своя тарелка; для еды философу нужны две вилки, причем он может использовать только вилки, примыкающие к его тарелке. Требуется так синхронизировать философов, чтобы каждый из них мог получить за ограниченное время доступ к своей тарелке. Предполагается, что длительность еды и размышлений философа конечна, но заранее недетерминирована.

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

Задача "читатели-писатели": имеется разделяемый ресурс - область памяти, к которой требуется обеспечить доступ процессам двух типов: процессы-читатели могут получать доступ к ресурсу одновременно, они считывают информацию (неразрушающее считывание); процессы-писатели взаимно исключают друг друга и читателей. Известны два варианта этой задачи:

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

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

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

Механизм семафоров

Пусть S - семафор - переменная специального типа с целочисленными значениями, над которой определены две операции: Р (закрытие) и V (открытие). Определим эти операции.

P(S): если S≥1, то процесс продолжает выполняться, а S уменьшается на единицу; если S = 0, то процесс задерживается, а имя его передается в очередь процессов, ожидающих доступа к данному ресурсу (обычно семафоры связывают с некоторыми ресурсами).

V(S): если в очереди к семафору S есть процессы, то один из них выбирается и активизируется (переводится в состояние готовности: помещается в очередь процессов, претендующих на процессорное время); если в очереди нет процессов, то выполняется операция S = S+1 (при условии непревышения результатом максимально допустимого значения семафора; для двоичного семафора S ∈{0,1}).

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

Все упомянутые задачи синхронизации можно решить с помощью семафоров. Рассмотрим задачу взаимного исключения:

S=1;

Процесс_i:

P(S);

Критическая секция

V(S);

При неаккуратном использовании семафорных переменных могут возникать тупиковые состояния. Например, тупик возможен в случае представленных ниже двух процессов при их одновременном выходе на второй вызов P:

S1=1 S2=1 P(S1) P(S2) P(S2) P(S1)

V(S2) V(S1) V(S1) V(S2)

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