Файл: Курсовая работа по ТВП. Шишиморов Александр.docx

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

В общем  виде  можно указать два примитива  взаимоисключений:

• примитив вход взаимоисключения – с его помощью фиксируется захват критического ресурса данным процессом и устанавливается запрет на использование его другими  процессами;

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

Один из простых алгоритмов синхронизации, где примененяется  примитив взаимоисключения состоит в следующем. Главный процесс запускает  в работу два параллельных процесса П1 и П2, после чего он завершает работу. У каждого из параллельных процессов в своем теле есть области работы с критическим ресурсом. Эти области обрамляются примитивами вход_взаимоисключения и выход_взаимоисключения. В случае с двумя процессами эти примитивы работают  следующим образом. После того, как процесс П1 выполняет примитив вход_взаимоисключения и при условии, что процесс П2 находится вне своего критического участка, П1 входит в свой критический участок, выполняет работу с критическим ресурсом, а затем выполняет примитив выход_взаимоисключения, то есть показывает, что он вышел из своего критического участка. Если П2 находится на своем критическом участке и П1 выполняет вход_взаимоисключения, то процесс П1 переводится в состояние ожидания, пока П2 не выполнит выход_взаимоисключения. Лишь после этого П1 может выйти из состояния ожидания и войти в свой критический участок. Если  вход_взаимоисключения выполняется одновременно двумя процессами, то одному из них операционная система позволяет  продолжить работу, а другой переводит в состояние ожидания. Всю эту схему можно посмотреть на рисунке 2.

Рисунок 2 – Схема применения примитивов взаимоисключения

---

3. Алгоритм деккера

Алгоритм Деккера является первым известным точным решением взаимного исключения без запрещения прерываний. Название алгоритма связано с голландским математиком Теодором Деккером, который разработал решение данной проблемы. Алгоритм позволяет двум потокам совместно использовать одноразовый ресурс без конфликтов, используя для связи лишь общую память.

Алгоритм Деккера имеет следующие ограничения:

1. Алгоритм рассчитан строго на 2 процесса;

2. При ожидании ресурса, процессы впустую тратят процессорное время, так как не снимаются с очереди на обслуживание;

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

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

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

Алгоритм Деккера основан на использовании 3-х переменных: ПР1 (процесс 1), ПР2 (процесс 2) и ОЧЕРЕДЬ.

1. Если первый процесс хочет войти в свой критический интервал, то переменная ПР2 принимает значение TRUE, т.е. значение переменной ОЧЕРЕДЬ показывает чьё именно сейчас право войти в критический интервал.

2. Если ПР1= TRUE, а ПР2=FALSE, то независимо от значения переменной ОЧЕРЕДЬ исполняется ПР1.

3. Если ПР1= TRUE и ПР2= TRUE, то дальше исполняется процесс, который определяется значением переменной ОЧЕРЕДЬ.

Завершив своё исполнение этот процесс сбрасывает флаг своего исполнения в FALSE и меняет значение переменной ОЧЕРЕДЬ на противоположное. Диапазон значений переменной ОЧЕРЕДЬ обычно колеблется в пределах [0;1] или [1;2]. Значение переменной ОЧЕРЕДЬ по сути тоже является флагом.

Begin integer C1,C2, очередь;

C1:=0; C2:=0; очередь=1;

begin

ПРОЦЕСС_1: begin C1:=1;

do while (C2=C1)

if (очередь=2) then

begin

C1:=0;

do while (очередь=2);

end;

end;

/* Критический участок ПРОЦЕССА_1 */

C1=0;

очередь=2;

/*Оставшаяся часть процесса*/

end;

ПРОЦЕСС_2: begin C2:=C1;

do while (C1=1);

if (очередь=1) then

begin

C2:=0;

do while (очередь=1);

end;

C2=1;

end;

end;

/* Критический участок ПРОЦЕССА_2 */

C2=0;

очередь=1;

/*Оставшаяся часть процесса*/

---

end;

end;

end.

Алгоритм Деккера обеспечивает взаимное исключение, невозможность возникновения deadlock или starvation. (Deadlock – это ситуация, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами; starvation – это зависание процессов).

Одним из преимуществ данного алгоритма является то, что он не требует специальных Test-and-set инструкций (атомарная операция чтения, модификации и записи), следовательно, он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость к случаю только с двумя процессами и использование Busy waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы должны проводить минимальное количество времени внутри критической секции).

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

Многие современные микропроцессоры исполняют инструкции не по порядку. Алгоритм не будет работать на SMP-машинах (Symmetric Multi Processing – симметричная мультипроцессорная обработка), оборудованных такими CPU (central processing unit - центральное обрабатывающее устройство), если не использовать барьеры памяти.

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

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

---

4. Алгоритм петерсона

Алгоритм Петерсона – это программный алгоритм взаимного исключения потоков без запрещения прерываний. Он был предложен в 1981 году Гарри Петерсоном из университета Рочестер (США). В основу алгоритма Петерсона лег алгоритм Деккера. Изначально алгоритм был сформулирован для 2-поточного случая, но он может быть обобщен для произвольного количества потоков. Алгоритм не основан на использовании таких команд процессора, которые запрещают прерывания, блокировки шины памяти, в нём используются только общие переменные памяти и цикл ожидания входа в критическую секцию кода, поэтому условно алгоритм называют программным. Алгоритм Петерсона учитывает отсутствие атомарности в операциях чтения и записи переменных и может применяться без использования команд управления прерываниями.

Алгоритм работает следующим образом: у каждого процесса есть своя переменная flag[i] и общая переменная turn. Хранение всех переменных происходит в общей памяти. Факт захвата ресурса запоминается в переменной flag , в переменной turn – номер захватившего ресурс процесса.

Когда исполняется пролог критической секции, процесс Pi заявляет о готовности к выполнению критического участка и сразу предлагает другому процессу приступить к его выполнению. В случае, когда оба процесса подошли к прологу единовременно, они оба объявят о своей готовности и предложат друг другу выполняться. При этом каждое предложение следует друг за другом. Тем самым работу в критическом участке продолжит процесс, которому было сделано последнее предложение.

flag[0] = 0

flag[1] = 0

turn = 0

P0: flag[0] = 1 P1: flag[1] = 1

turn = 1 turn = 0

while( flag[1] && turn == 1 ); while( flag[0] && turn == 0);

// ожидаем // ожидаем

// начало критической секции // начало критической секции

... ... ... …

// её конец // её конец

flag[0] = 0 flag[1] = 0

Сначала процесс устанавливает флаг занятости, потом – номер процесса соседа. После этих действий каждый из процессов входит в цикл ожидания. Выход из цикла происходит, в случае, если флаг занятости установлен, и номер процесса соответствует номеру соседа.

Еще один вариант реализации алгоритма Петерсона:

void mut_excl(int me /* 0 or 1 */)

{

---

static int loser;

static int interested[2] = {0, 0};

int other; /* локальная переменная */

other = 1 - me;

interested[me] = 1;

loser = me;

while (loser == me && interested[other])

;

/* критическая секция*/

interested[me] = 0;

}

Алгоритм Петерсона, разработанный в 1981 году, состоит из двух процедур, написанных на С.

#define FALSE 0

#define TRUE 1

#define N 2

int turn; int interested[N];

void enter_region(int process)

{

int other;

other=1-process;

interested[process]=TRUE;

turn=process;

while(turn==process && interested[other]==TRUE) { } // Пустой цикл

}

void leave_region(int process)

{

interested[process]=FALSE;

}

При попытке обратиться к критическому ресурсу процесс вызывает функцию enter_regian, передавая в неё свой номер. Если критический ресурс в это время уже занят, то функция войдёт в так называемый "тугой" цикл ожидания, пока ресурс не будет освобождён. Освобождение ресурса производится функцией leave_regian. Данный алгоритм основан на идее, так называемого, активного ожидания, т.е. на постоянном опросе состояние собственной переменной блокировки во время нахождения в "тугом" цикле. Неэффективность главного алгоритма заключается в том, что тратится много процессорного времени на режим активного ожидания во время занятости ресурса другими процессами.

Существуют приёмы синхронизации, позволяющие избежать "активного ожидания":

1. Блокировка. Этот механизм используется для управления параллельным доступом к ресурсам. Если какая-либо операция получает доступ к ресурсу, то механизм блокировки отклоняет попытку получения доступа к этому же ресурсу со стороны других процессов или других операций. Наиболее часто в качестве ресурсов в этом способе выступают данные, а сам механизм соответственно применяется при разработке СУБД.

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

Каждая система проводит собственную политику разрешения тупиковых ситуаций. Существует 3 основных подхода:

---