Критические области

Межпроцессорное взаимодействие.

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

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

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

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

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

2. Текст прогарммы должен исключить предположение о скорости вычисления системы либо количестве процессов.

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

4. Процесс не должен вечно ждать попадания в критическую секцию.

Методы синхронизации разделены на 2 направления:

1) Синхронизация с активным ожиданием.

2) Синхронизация с блокировкой процессов (пассивным ожиданием)

Методы активной синхронизации:

1. Зпрет на прерывание состоит в запрете приреваний при входе в критическую секцию и разделении при выходе из нее.

Достоинства: самое простое решение, запрет прирывания исключает доступ к процессору любому процессу.

Недостаток: нарушается 4-ре условия синхронизации. При этом никакой другой процесс его из ожидания не выведет, это приводит к краху системы.

Указанное решение применяется в ядре ОС для обеспечения наивысшего приоритета при работе с переменными. Для пользовательских программ указанный метод не приемлем. Этот метод применяется при программировании контроллеров.

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

Достоиства: простота решения.

Недостатки: не соблюдаются условия 1 и 3 т.к. не блокируются другие процессы не находящиеся в критической секции. В следствии этогог снижается вероятность но не исключается возможность двух процессов в критической секции.

В некоторой литературе переменные блокировки называются симафорами. В противовес симафоры деструкторы которые по сути являются счетчиками процесса в очереди.

3. Метод строгого чередования.

while(TRUE)

{

while(turn!=0);

critical_selection();

turn=1;

noncritical_selection();

}

while(TRUE)

{

while(turn!=1);

critical_selection();

turn=0;

noncritical_selection();

}

turn – распределяемая переменная блокировки.

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

Достоинства: процессы гарантированно будут выполнены.

Недостатки: если один процесс значительно медленнее другого, работа всего множества процессов замедляется, что может привести к нарунению условий 3 и 4.

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

Деккером был продложен метод взаимного исключения без строгого чередования, что позволяло процессам не задерживать друг друга. В настоящее время метод не используется из-за сложности, вместо его использется метод Петерсона.

5. Алгоритм Петерсона предложен в 1981 г.

#define №2

int turn;

bool interested[N];

void enter_region(int process)

{

int other; //номер другого процесса.

other=1-process;

interessted[process]=true;

turn=process;

while(turn==process && interessted[other]==true); //ожидание перед входом в критическую секцию.

}

//вызывается перед выходом из критической секции

void leave_region(int process)

{

interessted[process]=false;

}

Пусть дано 2 процесса совмесно использующих область, enter_region – перед входом.

Использование команды tsl – это асемблерная программа внедренная в многопроцессорные системы поддерживается на аппаратном уровне, расшифровывается как «проверить и заблокировать», работает следущимобразом: в регистр процессора считывается содержимое ячейки памяти и затем в эту ячейку устанавливается единица.

Команда tsl неделима, во время ее выполнения процессором системная шина блокируется.

enter_region:

tsl register, block; - блокирует ячейку памяти и записует в регистр;

cmp register, #0 – команда сравнить;

jne enter_region; - переход по несовпадению;

leav_region:

move lock, #0;

ret – ретурн;

Преймущества: использования команды tsl перед методом использования переменной блокировки в том что при использовании tsl модификация блокировки не делима что исключает состязание между процессами.

Недостатки: не все вычисительные программы поддерживают метод tsl;

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

Дата добавления: 2013-12-12