из параллельно выполняемых) вычисление делится
Предполагается, что в каждой задаче ( из параллельно выполняемых) вычисление делится на критическую (critical) и некритическую (non-critical) секцию (section), которые неоднократно выполняются:
task body T_i is
begin
loop
Prologue;
Critical_Section;
Epilogue;
Non_Critical_Section;
end loop;
end T_i:
Для решения проблемы взаимных исключений мы должны найти такие последовательности кода, называемые прологом (prologue) и эпилогом (epilogue), чтобы программа удовлетворяла следующим требованиям, которые должны выполняться для всех чередований последовательностей команд из набора задач:
Взаимное исключение. В любой момент времени только одна задача выполняет свою критическую секцию.
Отсутствие взаимоблокировки (no deadlock). Всегда есть, по крайней мере, одна задача, которая в состоянии продолжить выполнение.
Жизнеспособность. Если задаче необходимо выполнить критическую секцию, в конце концов она это сделает.
Справедливость. Доступ к критическому участку предоставляется «по справедливости».
Существуют варианты решения проблемы взаимных исключений, использующие в качестве атомарных команд только load (загрузить) и store (сохранить), но эти решения трудны для понимания и выходят за рамки данной книги, поэтому мы отсылаем читателя к учебникам по параллельному программированию.
Э. Дейкстра (E.W. Dijkstra) определил абстракцию синхронизации высокого уровня, называемую семафором, которая тривиально решает эту проблему. Семафор S является переменной, которая имеет целочисленное значение; для семафоров определены две атомарные команды:
Wait(S): when S > 0 do S := S -1;
Signal(S): S:=S+1;
Процесс, выполняющий команду Wait(S), блокируется на время, пока значение S неположительно. Обратите внимание, что, поскольку команда является атомарной, то, как только процесс удостоверится, что S положительно, он сразу уменьшит S (до того, как любой другой процесс выполнит команду!).
