Параллельные процессы (concurrent processes), страница 2

Где выход? Эту задачу можно решить, если каждому процессу предоставить исключительное монопольное право доступа к переменной NumberOfStrings. Когда один процесс заполучил эту переменную для увеличения, всем остальным процессам, которым тоже нужно произвести приращение, придется ждать, когда этот процесс завершит свое обращение к переменной. После этого очередному процессу будет разрешен доступ к переменной. Таким образом, каждый процесс, получивший доступ к переменой, исключает для всех остальных процессов возможность одновременного с ним обращения к этим данным. Это называется взаимоисключением.

В Win32 API этот механизм получил название Mutex (MUTual  Exclusion - взаимное исключение).

3.2.2.  Критические участки.

Взаимоисключение необходимо только в том случае, когда процессы обращаются к разделяемым, общим данным. Если же они выполняют операции, которые не приводят к конфликтным ситуациям, они должны иметь возможность работать параллельно. Когда процесс производит обращение к разделяемым данным, то говорят, что он находится в своем критическом участке. Впервые это понятие ввел Эдсгер Дейкстра (E.W. Dijkstra) в статье “Cooperating Sequential Processes”. Очевидно, что для решения задачи, о которой мы только что говорили в предыдущем разделе, необходимо, в случае, если один процесс находится в своем критическом участке, исключить возможность вхождения для всех других процессов в их критические участки (или, по крайней мере, для тех процессов, которые пользуются разделяемыми данными).

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

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

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

3.2.3.  Примитивы взаимоисключения. Вариант реализации.

Рассмотрим пример параллельной программы, которая реализует функцию подсчета строк. Для начала обсудим некоторый язык изложения параллельных возможностей. Поскольку мы не имеем возможности воспользоваться языком параллельного программирования (например, Concurrent Pascal), то введем некоторую абстракцию:

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

int NumberOfStrings ;

main ()

{

NumberOfStrings = 0;

parbegin;

proc1();

proc2();

parend;

}

proc1()

{

while (some_conditions1)

{

GetNextString();

MutexStart;

NumberOfStrings = NumberOfStrings + 1;

MutexEnd;

}

}

proc2()

{

while (some_conditions2)

{

GetNextString();

MutexStart;

NumberOfStrings = NumberOfStrings + 1;

MutexEnd;

}

}

Мы ввели два новых оператора MutexStart и MutexEnd. Причем обязанности за соблюдение правильности взаимоисключения возложили на систему. Но не всегда система поддерживает такие операторы, да и просто интересно узнать, как она это делает (если умеет). Поэтому сейчас мы попытаемся реализовать примитив взаимоисключения с соблюдением следующих условий:

n  на машине нет специальных команд взаимоисключения;

n  мы ничего не знаем об относительных скоростях выполнения асинхронных процессов;

n  Если процесс находится вне критического участка, он не может помешать другому процессу войти в свой критический участок;

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

3.3.   Алгоритм Деккера.

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

int NumberOfStrings ;

int ProcessNumber;

main ()

{

NumberOfStrings = 0;

ProcessNumber = 1;

parbegin;

proc1();

proc2();

parend;

}

proc1()

{

while (some_conditions1)

{

while (ProcessNumber != 1) wait();

GetNextString();

//                  MutexStart;

NumberOfStrings = NumberOfStrings + 1;

ProcessNumber = 2;

//                  MutexEnd;

}

}

proc2()

{

while (some_conditions2)

{

while (ProcessNumber != 2) wait();

GetNextString();

//                  MutexStart;

NumberOfStrings = NumberOfStrings + 1;

ProcessNumber = 1;

//                  MutexEnd;

}

}

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

n  Процесс 1 должен выполняться первым;

n  После того, как процесс один войдет в свой критический участок и выйдет из него, должен строго выполняться процесс 2( то есть они обязаны входить в критические участки по очереди).