Основой для построения моделей функционирования программ, реализующих параллельные методы решения задач, является понятие процесса как конструктивной единицы построения параллельной программы. Описание программы в виде набора процессов, выполняемых параллельно на разных процессорах или на одном процессоре в режиме разделения времени, позволяет сконцентрироваться на рассмотрении проблем организации взаимодействия процессов, определить моменты и способы обеспечения синхронизации и взаимоисключения процессов, изучить условия возникновения или доказать отсутствие тупиков в ходе выполнения программ (ситуаций, в которых все или часть процессов не могут быть продолжены при любых вариантах продолжения вычислений).
Понятие процесса является одним из основополагающих в теории и практике параллельного программирования. В [6,13] приводится ряд известных по литературе определений процесса. Разброс в трактовке данного понятия является достаточно широким, но в целом большинство определений сводится к пониманию процесса как "некоторой последовательности команд, претендующей наравне с другими процессами программы на использование процессора для своего выполнения".
Конкретизация понятия процесса зависит от целей исследования параллельных программ. Для анализа проблем организации взаимодействия процессов процесс можно рассматривать как последовательность команд
(для простоты изложения материала будем предполагать, что процесс описывается единственной командной последовательностью). Динамика развития процесса определяется моментами времен начала выполнения команд
,
где 
, 
, есть время начала выполнения команды . Последовательность 
представляет временную траекторию
развития процесса. Предполагая, что команды процесса исполняются строго
последовательно, в ходе своей реализации не могут быть приостановлены (т.е.
являются неделимыми) и имеют одинаковую длительность выполнения, равную 1
(в тех или иных временных единицах), получим, что моменты времени траектории
процесса должны удовлетворять соотношениям
.
Рис. 5.1. Диаграмма переходов процесса из состояния в состояние
Равенство 
достигается, если для выполнения
процесса выделен процессор и после завершения очередной команды процесса сразу
же начинается выполнение следующей команды. В этом случае говорят, что процесс
является активным и находится в состоянии выполнения. Соотношение
означает,
что после выполнения очередной команды процесс приостановлен и ожидает
возможности для своего продолжения. Данная приостановка может быть вызвана
необходимостью разделения использования единственного процессора между одновременно
исполняемыми процессами. В этом случае приостановленный процесс находится
в состоянии ожидания момента предоставления процессора для своего выполнения.
Кроме того, приостановка процесса может быть вызвана и временной неготовностью
процесса к дальнейшему выполнению (например, процесс может быть продолжен
только после завершения операции ввода-вывода). В подобных ситуациях говорят,
что процесс является блокированным и находится в состоянии блокировки.
В ходе своего выполнения состояние процесса может многократно изменяться; возможные варианты смены состояний показаны на диаграмме переходов рис. 5.1.
Понятие ресурса обычно используется для обозначения любых объектов вычислительной системы, которые могут быть использованы процессом для своего выполнения. В качестве ресурса может рассматриваться процесс, память, программы, данные и т.п. По характеру использования могут различаться следующие категории ресурсов:
- выделяемые (монопольно используемые, неперераспределяемые) ресурсы характеризуются тем, что выделяются процессам в момент их возникновения и освобождаются только в момент завершения процессов; в качестве такого ресурса может рассматриваться, например, устройство чтения на магнитных лентах;
- повторно распределяемые ресурсы отличаются возможностью динамического запрашивания, выделения и освобождения в ходе выполнения процессов (таковым ресурсом является, например, оперативная память);
- разделяемые ресурсы, особенность которых состоит в том, что они постоянно остаются в общем использовании и выделяются процессам для использования в режиме разделения времени (как, например, процессор, разделяемые файлы и т.п.);
- многократно используемые (реентерабельные) ресурсы выделяются возможностью одновременного использования несколькими процессами (что может быть обеспечено, например, при неизменяемости ресурса при его использовании; в качестве примеров таких ресурсов могут рассматриваться реентерабельные программы, файлы, используемые только для чтения и т.д.).
Следует отметить, что тип ресурса определяется не только его конкретными характеристиками, но и зависит от применяемого способа использования. Так, например, оперативная память может рассматриваться как повторно распределяемый, так и разделяемый ресурс; использование программ может быть организовано в виде ресурса любого рассмотренного типа.
Понятие процесса может быть использовано в качестве основного конструктивного элемента для построения параллельных программ в виде совокупности взаимодействующих процессов. Такая агрегация программы позволяет получить более компактные (поддающиеся анализу) вычислительные схемы реализуемых методов, скрыть при выборе способов распараллеливания несущественные детали программной реализации, обеспечивает концентрацию усилий на решение основных проблем параллельного функционирования программ.
Рис. 5.2. Варианты взаиморасположения траекторий одновременно исполняемых процессов (отрезки линий изображают фрагменты командных последовательностей процессов)
Существование нескольких
одновременно выполняемых процессов приводит к появлению дополнительных соотношений,
которые должны выполняться для величин временных траекторий процессов. Возможные
типовые варианты таких соотношений на примере двух процессов 
и 
состоят
в следующем (см. рис. 5.2):
-
выполнение процессов осуществляется
строго последовательно, т.е. процесс начинает свое выполнение только после
полного завершения процесса (однопрограммный режим работы ЭВМ –
см. рис. 5.2а),
- выполнение процессов может осуществляться одновременно, но в каждый момент времени могут исполняться команды только какого либо одного процесса (режим разделения времени или многопрограммный режим работы ЭВМ – см. рис. 5.2б),
- параллельное выполнение процессов, когда одновременно могут выполняться команды нескольких процессов (данный режим исполнения процессов осуществим только при наличии в вычислительной системе нескольких процессоров - см. рис. 5.2в).
Приведенные варианты взаиморасположения траекторий процессов определяются не требованиями необходимых функциональных взаимодействий процессов, а являются лишь следствием технической реализации одновременной работы нескольких процессов. С другой стороны, возможность чередования по времени командных последовательностей разных процессов следует учитывать при реализации процессов. Рассмотрим для примера два процесса с идентичным программным кодом.
Процесс 1 Процесс 2
N = N + 1 N = N + 1
печать N печать N
Пусть начальное значение переменной N равно 1. Тогда при последовательном исполнении процесс 1 напечатает значение 2, процесс 2 – значение 3. Однако возможна и другая последовательность исполнения процессов в режиме разделения времени (с учетом того, что сложение N = N +1 выполняется при помощи нескольких машинных команд)
(в скобках для каждой команды указывается значение переменной N).
Как следует из приведенного примера, результат одновременного выполнения нескольких процессов, если не предпринимать специальных мер, может зависеть от порядка исполнения команд.
Выполним анализ возможных командных последовательностей, которые могут получаться для программ, образованных в виде набора процессов. Рассмотрим для простоты два процесса
,
.
Командная последовательность программы образуется чередованием команд отдельных процессов и, тем самым, имеет вид:
, 
.
Фиксация способа образования
последовательности 
из команд отдельных процессов может быть обеспечена
при помощи характеристического вектора
,
в котором следует положить
, если команда 
получена из процесса 
(иначе 
). Порядок следования команд
процессов в
должен соответствовать порядку расположения этих команд в исходных процессах
,
где 
есть команда процесса , соответствующая команде
в .
С учетом введенных обозначений,
под программой, образованной из процессов и 
, можно понимать множество всех возможных
командных последовательностей
.
Данный подход позволяет рассматривать программу так же, как некоторый обобщенный (агрегированный) процесс, получаемый путем параллельного объединения составляющих процессов
.
Выделенные особенности одновременного выполнения нескольких процессов могут быть сформулированы в виде ряда принципиальных положений, которые должны учитываться при разработке параллельных программ:
- моменты выполнения командных последовательностей разных процессов могут чередоваться по времени;
- между моментами исполнения команд разных процессов могут выполняться различные временные соотношения (отношения следования); характер этих соотношений зависит от количества и быстродействия процессоров и загрузки вычислительной системы и, тем самым, не может быть определен заранее;
- временные соотношения между моментами исполнения команд могут различаться при разных запусках программ на выполнение, т.е. одной и той же программе при одних и тех же исходных данных могут соответствовать разные командные последовательности вследствие разных вариантов чередования моментов работы разных процессов;
- доказательство правильности получаемых результатов должно проводиться для любых возможных временных соотношений для элементов временных траекторий процессов;
- для исключения зависимости результатов выполнения программы от порядка чередования команд разных процессов необходим анализ ситуаций взаимовлияния процессов и разработка методов для их исключения.
Перечисленные моменты свидетельствуют о существенном повышении сложности параллельного программирования по сравнению с разработкой "традиционных" последовательных программ.
Одной из причин зависимости результатов выполнения программ
от порядка чередования команд может быть разделение одних и тех же данных
между одновременно исполняемыми процессами (например, как это осуществляется
в выше рассмотренном примере).
Данная ситуация может рассматриваться как проявление общей проблемы использования
разделяемых ресурсов (общих данных, файлов, устройств и т.п.). Для организации
разделения ресурсов между несколькими процессами необходимо иметь возможность:
- определения доступности запрашиваемых ресурсов (ресурс свободен и может быть выделен для использования, ресурс уже занят одним из процессов программы и не может использоваться дополнительно каким-либо другим процессом);
- выделения свободного ресурса одному из процессов, запросивших ресурс для использования;
- приостановки (блокировки) процессов, выдавших запросы на ресурсы, занятые другими процессами.
Главным требованием к механизмам разделения ресурсов является гарантированное обеспечение использования каждого разделяемого ресурса только одним процессом от момента выделения ресурса этому процессу до момента освобождения ресурса. Данное требование в литературе обычно именуется взаимоисключением процессов; командные последовательности процессов, в ходе которых процесс использует ресурс, называется критической секцией процесса. С использованием последнего понятия условие взаимоисключения процессов может быть сформулировано как требование нахождения в критических секциях по использованию одного и того же разделяемого ресурса не более чем одного процесса.
Рассмотрим несколько вариантов программного решения проблемы взаимоисключения (для записи программ используется язык программирования C++). В каждом из вариантов будет предлагаться некоторый частный способ взаимоисключения процессов с целью демонстрации всех возможных ситуаций при использовании общих разделяемых ресурсов. Последовательное усовершенствование механизма взаимоисключения при рассмотрении вариантов приведет к изложению алгоритма Деккера, обеспечивающего взаимоисключение для двух параллельных процессов. Обсуждение способов взаимоисключения завершается рассмотрением концепции семафоров Дейкстра, которые могут быть использованы для общего решение проблемы взаимоисключения любого количества взаимодействующих процессов.
intProcessNum = 1; // номер процесса для доступа к ресурсу
Process_1() {
while (1) {
// повторять, пока право доступа к ресурсу у процесса 2
while
( ProcessNum == 2 );
< Использование общего ресурса >
// передача права доступа к ресурсу процессу 2
ProcessNum = 2;
}
}
Process_2()
{
while (1) {
// повторять, пока право доступа к ресурсу у процесса 1
while ( ProcessNum == 1 );
< Использование общего ресурса >
// передача права доступа к ресурсу процессу 1
ProcessNum = 1;
}
}
Реализованный в программе способ гарантирует взаимоисключение, однако такому решению присущи два существенных недостатка:
- ресурс используется процессами строго последовательно (по очереди) и, как результат, при разном темпе развития процессов общая скорость выполнения программы будет определяться наиболее медленным процессом;
- при завершении работы какого-либо процесса другой процесс не сможет воспользоваться ресурсом и может оказаться в постоянно блокированном состоянии.
Решение проблемы взаимоисключения подобным образом известно в литературе как способ жесткой синхронизации.
В данном варианте для ухода от жесткой синхронизации используются две управляющие переменные, фиксирующие использование процессами разделяемого ресурса.
int ResourceProc1 = 0; // = 1 – ресурс занят
процессом 1
int ResourceProc2 = 0; // = 1 – ресурс занят
процессом 2
Process_1() {
while (1) {
// повторять, пока ресурс используется процессом 2
while ( ResourceProc2 == 1 );
ResourceProc1 = 1;
< Использование общего ресурса >
ResourceProc1 = 0;
}
}
Process_2()
{
while (1) {
// повторять, пока ресурс используется процессом 1
while ( ResourceProc1 == 1 );
ResourceProc2 = 1;
< Использование общего ресурса >
ResourceProc2 = 0;
}
}
Предложенный способ разделения ресурсов устраняет недостатки жесткой синхронизации, однако при этом теряется гарантия взаимоисключения – оба процесса могут оказаться одновременно в своих критических секциях (это может произойти, например, при переключении между процессами в момент завершения проверки занятости ресурса). Данная проблема возникает вследствие различия моментов проверки и фиксации занятости ресурса.
Следует отметить, что в отдельных случаях взаимоисключение процессов в данном примере может произойти и корректно - все определяется конкретными моментами переключения процессов. Отсюда следует два важных вывода:
- успешность однократного выполнения не может служить доказательством правильности функционирования параллельной программы даже при неизменных параметрах решаемой задачи;
- для выявления ошибочных ситуаций необходима проверка разных временных траекторий выполнения параллельных процессов.
Возможная попытка в восстановлении взаимоисключения может состоять в установке значений управляющих переменных перед циклом проверки занятости ресурса.
int ResourceProc1 = 0; // = 1 – ресурс занят процессом 1
int ResourceProc2 = 0; // = 1 – ресурс занят процессом 2
Process_1() {
while (1) {
// установить, что процесс 1 пытается занять ресурс
ResourceProc1 = 1;
// повторять, пока ресурс занят процессом 2
while ( ResourceProc2 == 1 );
< Использование общего ресурса >
ResourceProc1 = 0;
}
}
Process_2()
{
while (1) {
// установить, что процесс 2 пытается занять ресурс
ResourceProc2 = 1;
// повторять, пока ресурс используется процессом 1
while ( ResourceProc1 == 1 );
< Использование общего ресурса >
ResourceProc2 = 0;
}
}
Представленный вариант восстанавливает взаимоисключение, однако при этом возникает новая проблема – оба процесса могут оказаться заблокированными вследствие бесконечного повторения циклов ожидания освобождения ресурсов (что происходит при одновременной установке управляющих переменных в состояние "занято"). Данная проблема известна под названием ситуации тупика (дедлока или смертельного объятия) и исключение тупиков является одной из наиболее важных задач в теории и практике параллельных вычислений. Более подробное рассмотрение темы будет выполнено далее в пп. 5.5 и 5.6; дополнительная информация по проблеме может быть получена в [6,13].
Предлагаемый подход для устранения тупика состоит в организации временного снятия значения занятости управляющих переменных процессов в цикле ожидания ресурса.
int ResourceProc1 = 0; // =1 – ресурс занят
процессом 1
int ResourceProc2 = 0; // =1 – ресурс занят
процессом 2
Process_1() {
while (1) {
ResourceProc1 = 1; // процесс 1 пытается занять ресурс
// повторять, пока ресурс занят процессом 2
while ( ResourceProc2 == 1 ) {
ResourceProc1 = 0; // снятие занятости ресурса
< временная задержка >
ResourceProc1 = 1;
}
< Использование общего ресурса >
ResourceProc1 = 0;
}
}
Process_2()
{
while (1) {
ResourceProc2 = 1; // процесс 2 пытается занять ресурс
// повторять, пока ресурс используется процессом 1
while ( ResourceProc1 == 1 ) {
ResourceProc2 = 0; // снятие занятости ресурса
< временная задержка >
ResourceProc2 = 1;
}
< Использование общего ресурса >
ResourceProc2 = 0;
}
}
Длительность временной задержки в циклах ожидания должна определяться при помощи некоторого случайного датчика. При таких условиях реализованный алгоритм обеспечивает взаимоисключение и исключает возникновение тупиков, но опять таки не лишен существенного недостатка (перед чтением следующего текста попытайтесь определить этот недостаток). Проблема состоит в том, что потенциально решение вопроса о выделении может откладываться до бесконечности (при синхронном выполнении процессов). Данная ситуация известна под наименованием бесконечное откладывание (starvation).
В алгоритме Деккера предлагается объединение предложений вариантов 1 и 4 решения проблемы взаимоисключения.
int ProcessNum=1; // номер процесса для доступа
к ресурсу
int ResourceProc1 = 0; // = 1 – ресурс занят
процессом 1
int ResourceProc2 = 0; // = 1 – ресурс занят
процессом 2
Process_1() {
while (1) {
ResourceProc1 = 1; // процесс 1 пытается занять ресурс
/* цикл ожидания доступа к ресурсу */
while ( ResourceProc2 == 1 ) {
if ( ProcessNum == 2 ) {
ResourceProc1 = 0;
// повторять, пока ресурс занят процессом 2
while ( ProcessNum == 2 );
ResourceProc1 = 1;
}
}
< Использование общего ресурса >
ProcessNum = 2;
ResourceProc1 = 0;
}
}
Process_2()
{
while (1) {
ResourceProc2 = 1; // процесс 2 пытается занять ресурс
/* цикл ожидания доступа к ресурсу */
while ( ResourceProc1 == 1 ) {
if ( ProcessNum == 1 ) {
ResourceProc2 = 0;
// повторять, пока ресурс используется процессом 1
while ( ProcessNum == 1 );
ResourceProc2 = 1;
}
}
< Использование общего ресурса >
ProcessNum = 1;
ResourceProc2 = 0;
}
}
Алгоритм Деккера гарантирует корректное решение проблемы взаимоисключения для двух процессов. Управляющие переменные ResourceProc1, ResourceProc1 обеспечивают взаимоисключение, переменная ProcessNum исключает возможность бесконечного откладывания. Если оба процесса пытаются получить доступ к ресурсу, то процесс, номер которого указан в ProcessNum, продолжает проверку возможности доступа к ресурсу (внешний цикл ожидания ресурса). Другой же процесс в этом случае снимает свой запрос на ресурс, ожидает своей очереди доступа к ресурсу (внутренний цикл ожидания) и возобновляет свой запрос на ресурс.
Алгоритм Деккера может быть обобщен на случай произвольного количества процессов (см. [16]), однако, такое обобщение приводит к заметному усложнению выполняемых действий. Кроме того, программное решение проблемы взаимоисключения процессов приводит к нерациональному использованию процессорного времени ЭВМ (процессу, ожидающему освобождения ресурса, постоянно требуется процессор для проверки возможности продолжения – активное ожидание (busy wait)).
Под семафором S обычно понимается [16] переменная особого типа, значение которой может опрашиваться и изменяться только при помощи специальных операций P(S) и V(S), реализуемых в соответствии со следующими алгоритмами:
· операция P(S)
если S>0
то S = S – 1
иначе <
ожидать S >
· операция V(S)
если
< один или несколько процессов ожидают S >
то < снять ожидание у одного из ожидающих процессов >
иначе
S = S + 1
Принципиальным в понимании семафоров является то, что операции P(S) и V(S) предполагаются неделимыми, что гарантирует взаимоисключение при использование общих семафоров (для обеспечения неделимости операции обслуживания семафоров обычно реализуются средствами операционной системы).
Различают два основных типа семафоров. Двоичные семафоры принимают только значения 0 и 1, область значений общих семафоров – неотрицательные целые значения. В момент создания семафоры инициализируются некоторым целым значением.
Семафоры широко используются для синхронизации и взаимоисключения процессов. Так, например, проблема взаимоисключения при помощи семафоров может иметь следующее простое решение.
Semaphore
Mutex=1; // семафор взаимоисключения процессов
Process_1() {
while (1) {
// проверить семафор и ждать, если ресурс занят
P(Mutex);
< Использование общего ресурса >
// освободить один из ожидающих ресурса процессов
// увеличить семафор, если нет ожидающих процессов
V(Mutex);
}
}
Process_2() {
while (1) {
// проверить семафор и ждать, если ресурс занят
P(Mutex);
< Использование общего ресурса >
// освободить один из ожидающих ресурса процессов
// увеличить семафор, если нет ожидающих процессов
V(Mutex);
}
}
Приведенный пример рассматривает взаимоисключение только двух процессов, но, как можно заметить, совершенно аналогично может быть организовано взаимоисключение произвольного количества процессов.
В самом общем виде тупик может быть определен [6] как ситуация, в которой один или несколько процессов ожидают какого-либо события, которое никогда не произойдет. Важно отметить, что состояние тупика может наступить не только вследствие логических ошибок, допущенных при разработке параллельных программ, но и в результате возникновения тех или иных событий в вычислительной системе (выход из строя отдельных устройств, нехватка ресурсов и т.п.). Простой пример тупика может состоять в следующем. Пусть имеется два процесса, каждый из которых в монопольном режиме обрабатывает собственный файл данных. Ситуация тупика возникнет, например, если первому процессу для продолжения работы потребуются файл второго процесса и одновременно второму процессу окажется необходимым файл первого процесса (см. рис. 5.3).
Рис. 5.3. Пример ситуации тупика
Проблема тупиков имеет многоплановый характер. Это и сложность диагностирования состояния тупика (система выполняет длительные расчеты или "зависла" из-за тупика), и необходимость определенных специальных действий для выхода из тупика, и возможность потери данных при восстановлении системы при устранении тупика.
В данном разделе будет рассмотрен один из аспектов проблемы тупика – анализ причин возникновения тупиковых ситуаций при использовании разделяемых ресурсов и разработка на этой основе методов предотвращения тупиков. Дополнительная информация по теме может быть получена в [6,13].
Могут быть выделены следующие необходимые условия тупика [13]:
- процессы требуют предоставления им права монопольного управления ресурсами, которые им выделяются (условие взаимоисключения);
- процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (условие ожидания ресурсов);
- ресурсы нельзя отобрать у процессов, удерживающих их, пока эти ресурсы не будут использованы для завершения работы (условие неперераспределяемости);
- существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся следующему процессу цепи (условие кругового ожидания).
Как результат, для обеспечения отсутствия тупиков необходимо исключить возникновение, по крайней мере, одного из рассмотренных условий. Далее будет предложена модель программы в виде графа "процесс-ресурс", позволяющего обнаруживать ситуации кругового ожидания.
Состояние программы может быть представлено в виде ориентированного графа (V,E) со следующей интерпретацией и условиями [13]:
1. Множество V разделено на два взаимно пересекающихся подмножества P и R, представляющие процессы
и ресурсы
программы.
2.
Граф является "двудольным"
по отношению к подмножествам вершин P и
R, т.е. каждое ребро 
соединяет вершину P с вершиной R. Если ребро 
имеет вид 
, то есть ребро запроса и интерпретируется
как запрос от процесса 
на единицу ресурса 
.
Если ребро
имеет вид 
,
то есть ребро назначения
и выражает назначение единицы ресурса процессу .
3.
Для каждого ресурса 
существует целое 
, обозначающее количество
единиц ресурса .
4.
Пусть 
- число ребер, направленных от вершины
к вершине
. Тогда при
принятых обозначениях для ребер графа должны выполняться условия:
-
Может быть сделано не более 
назначений (распределений)
для ресурса , т.е.
, 
;
- Сумма запросов и распределений относительно любого процесса для конкретного ресурса не может превышать количества доступных единиц, т.е.
, 
, .
Граф, построенный с соблюдением всех перечисленных правил, именуется в литературе как граф "процесс-ресурс". Для примера, на рис. 5.3 приведен граф программы, в которой ресурс 1 (файл 1) выделен процессу 1, который, в свою очередь, выдал запрос на ресурс 2 (файл 2). Процесс 2 владеет ресурсом 2 и нуждается для своего продолжения в ресурсе 1.
Состояние программы, представленное в виде графа "процесс-ресурс", изменяется только в результате запросов, освобождений или приобретений ресурсов каким-либо из процессов программы.
Запрос. Если
программа находится в состоянии S и процесс не имеет невыполненных запросов, то может запросить любое число
ресурсов (в пределах ограничения 4). Тогда программа переходит в состояние
T
Состояние T отличается от
S только дополнительными ребрами запроса от к затребованным ресурсам.
Приобретение. Операционная система
может изменить состояние программы S на состояние T в результате операции
приобретения ресурсов процессом тогда и только тогда, когда имеет запросы на выделение
ресурсов и все такие запросы могут быть удовлетворены, т.е. если
.
Граф T идентичен S за исключением
того, что все ребра запроса 
для обратны ребрам 
, что отражает выполненное распределение ресурсов.
Рис. 5.4. Пример переходов программы из состояния в состояние
Освобождение.
Процесс может
вызвать переход из состояния S в состояние T с помощью освобождения ресурсов
тогда и только тогда, когда не имеет запросов, а имеет некоторые распределенные
ресурсы, т.е.
, 
.
В этой операции
может освободить любое непустое подмножество своих ресурсов. Результирующее
состояние T идентично исходному состоянию S за
исключением того, что в T отсутствуют некоторые ребра приобретения из S (из
S удаляются ребра
каждой освобожденной единицы ресурса ).
Для примера на рис. 5.4. показаны состояния программы с одним ресурсом емкости 3 и двумя процессами после выполнения операций запроса, приобретения и освобождения ресурсов для первого процесса.
При рассмотрении переходов программы из состояния в состояние важно отметить, что поведение процессов является недетерминированным – при соблюдении приведенных выше ограничений выполнение любой операции любого процесса возможно в любое время.
Определение состояния программы и операций перехода между состояниями позволяет сформировать модель параллельной программы следующего вида.
Под программой будем понимать систему
,
где 
есть множество состояний программы
(S, T, U,…), а 
представляет множество процессов 
. Процесс 
есть частичная функция,
отображающая состояния программы в непустые подмножества состояний
,
где 
есть множество всех подмножеств . Обозначим множество состояний,
в которые может перейти программа при помощи процесса (область значений процесса
) при нахождении
программы в состоянии 
через 
. Возможность перехода программы из состояния
в состояние
в
результате некоторой операции над ресурсами в процессе (т.е. 
) будем пояснять при помощи записи
.
Обобщим данное обозначение
для указания достижимости состояния из состояния
в результате
выполнения некоторого произвольного количества переходов в программе
С учетом построенной модели и введенных обозначений можно выделить ряд ситуаций, возникающих при выполнении программы и представляющих интерес при рассмотрении проблемы тупика:
заблокирован в состоянии , если программа не может изменить свое состояние
при помощи этого процесса, т.е. если 
Ø; находится в тупике в состоянии , если этот процесс является заблокированным
в любом состоянии , достижимом из состояния , т.е.
Ø;
называется тупиковым, если существует процесс , находящийся в тупике
в этом состоянии; есть безопасное состояние, если любое состояние , достижимое
из , не
является тупиковым.
Рис. 5.5. Пример графа переходов программы
Для примера на рис. 5.5 приведен граф переходов программы, в котором состояния U и V являются безопасными, состояния S и T и W не являются безопасными, а состояние W есть состояние тупика.
Рассмотренная модель программы может быть использована для определения возможных состояний программы, обнаружения и недопущения тупиков. В качестве возможных теоретических результатов такого анализа может быть приведена теорема [13].
Теорема. Граф "процесс-ресурс" для состояния программы с ресурсами единичной емкости указывает на состояние тупика тогда и только тогда, когда он содержит цикл.
Дополнительный материал по исследованию данной модели может быть получен в [13].
Другим возможным способом моделирования состояний и функционирования
параллельной программы является использование математических моделей и методов
исследования дискретных систем, разработанных в рамках теории сетей Петри
[13]. При таком подходе в качестве модели программы может быть использована
сеть Петри, представляемая размеченным ориентированным графом 
(изложение материала осуществляется
в соответствии с работой [13] за исключением приведения системы обозначений
к виду, принятому в данном пособии):
1. Множество вершин сети V разделено на два взаимно пересекающихся подмножества вершин-переходов P и вершин-мест R
, .
Вершины-места обычно изображаются кружками, вершины-переходы представляются в виде прямоугольников или линий-барьеров.
2.
Граф сети является "двудольным"
по отношению к подмножествам вершин P и
R, т.е. каждое ребро
соединяет вершину P с вершиной R. Задание ребер графа может быть выполнено,
например, при помощи функций инцидентности
, 
,
ненулевые значения которых
задают множество ребер E (при 
сеть содержит ребро вида , при 
сеть содержит ребро вида ).
3. Функция
определяет собой начальную разметку сети, по которой для каждой вершины-места ставится в соответствие целое неотрицательное число (разметка места). При графическом изображении разметка сети показывается соответствующим числом точек (фишек) внутри кружков-мест.
Рис. 5.6. Пример сети Петри
Для пояснения введенных понятий на рис. 5.6 показан пример сети Петри с тремя переходами и четырьмя вершинами мест.
При использовании сетей Петри для описания параллельных программ переходы обычно соответствуют действиям (процессам), а места – условиям (выделению или освобождению ресурсов). Разметка мест в этом случае интерпретируется как количество имеющихся (нераспределенных) единиц ресурса.
Сеть Петри может функционировать (изменять свое
состояние), переходя от разметки к разметке. Обозначим через 
множество переходов, к которым
имеются ребра из вершины-места
;
по аналогии, 
есть множество переходов, из которых имеются ребра в вершину-место
С учетом введенных обозначений правила функционирования сети состоят в следующем:
-
Переход может сработать при разметке M только
при выполнении условия
.
Данное условие означает,
что все входные места перехода содержат хотя бы по одной фишке.
-
В результате срабатывания перехода
разметка сети
M сменяется разметкой M' по правилу:
.
Рис. 5.7. Состояние сети после срабатывания перехода
Другими словами, переход
изымает по одной фишке своего
входного места и добавляет по одной в каждое свое выходное место. Будем говорить
далее, что разметка M' следует за разметкой M, а M предшествует M', и обозначать
этот факт
.
Так, в сети на рис. 5.6
могут сработать переходы 
и ; состояние сети после срабатывания перехода
показано на рис. 5.7.
Если одновременно может сработать несколько переходов и они не имеют общих входных мест, то их срабатывания могут рассматриваться как независимые действия, выполняемые последовательно или параллельно. Если несколько переходов могут сработать и имеют хотя бы одно общее входное место, то сработать может только один, любой из них.
При исследовании процессов функционирования сетей Петри широко используется следующий ряд дополнительных понятий и обозначений:
,
если разметка M' может быть получена в результате некоторого количества срабатываний сети, начиная от разметки M;
;
множество всех достижимых разметок обозначим через M; достижим от разметки M, если
существует достижимая от M разметка M', в которой переход может сработать; достижим в сети, если он достижим
от 
; называется живым, если он
достижим от любой разметки из M; сеть является
живой, если все ее переходы живы; называется ограниченным, если
существует такое число k, что 
для любой разметки из M; сеть является ограниченной, если все ее места
ограничены.В рамках теории сетей Петри разработаны методы, позволяющие для произвольной сети определить [26], является ли сеть ограниченной или живой, проверить достижимость любого перехода или разметки сети. Как результат, данные методы позволяют определить наличие тупиков в сети.