Алгоритмы реализации взаимоисключений

Алгоритм:

Блокирующая глобальная переменная(замок):

shared int lock = 0; // замок открыт

process1

while (lock); // пролог

//Если тут прерывания, то произойдет ппц. Сюда может зайти второй и тогда оба могу зайти в //к.р.

lock = 1; // пролог

{к.с.}

locl = 0; // эпилог

Строгое чередование:

shared int turn = 0;

process I

while(turn!= I);

{к.с.}

turn = 1-i;

если 1 из процессов не выполняет свою секцию, то он не отдаст второму.

Алгоритм флагов готовности:

shared int ready[2]={0,0};

process I

ready[i]=1;

Прерывание оба процесса тут. Оба подняли флаги, тогда оба насмерть вешаются(взаим.блок).

while (ready[1-i]);

{к.с.}

ready[i]=0;

Алгоритм Пэтерсона (взаимной вежливости):

shared int ready[2]= {0,0}

shared int turn;

process I

ready[i]=1;

turn = 1 – I;

while(ready[1-i] && turn == 1- I)

{к.с.}

ready[i]=0;

Проблема появляется, когда много процессов, много проверок будет. Большое время разрешения коллизий. Эффективен для малого количества процессов.

 

Среди ресурсов ОС существуют такие, которые могут быть использованы только одним процессом.

Лучшее решение: блокировать только в момент, когда коду требуется обратиться к такому ресурсу. Такая секции кода называется критической секцией. В таком случае в стеке команд у процесса будет: пролог{ крит секция } эпилог. В момент входа и выхода в крит секцию требуется объявлять об этом системе.

Методы решения проблем взаимоблокировки:

1. однопрограммное выполнение. В прологе блокируются выполнение любых процессов с этими данными. В unix – psw используется для обновления pcb

2. блокирующая глобальна переменная (мьютекс/замок). При не атомарности между while и lock = 1, возникает одновременное использование крит секции.

shared int lock = 0;

процесс 1

while (lock);

lock = 1;

{крит секция}

lock = 0;

3. алгоритм строго чередовании (семафор) Недостаток – передача управлении над критической секцией когда другому процессу она не нужна.

i = 0 или 1;

shared int turn = 0;

процесс i:

while (turn!= i);

{крит секция}

turn = 1-i;

4. Алгоритм флагов готовности. Недостаток: при прерывание между ready[i] и while(ready[1-i]) возникает взаимоблокрировка.

shared int ready[2] = {0, 0};

процесс i:

ready[i] = 1;

while (ready[1-i]);

{ крит секция}

ready [i] = 0;

 

23. Семафоры Дейкстра. Решение проблемы «производитель-потребитель» с помощью семафоров.

Семафор (S) – целочисленная переменная >=0

p(S): пока S == 0 – блокировать процесс; S--; (атомарная операция)

v(S): S++ (атомарная операция)

 

Модель работы:

Producer ->buffer[n] -> Consumer; если буфер не полный – producer отправляет туда данные, иначе ждет. Consumer читает данные если есть, иначе ждет.

 

Объявим 3 семафора.

1. mutex = 1 (0 или 1)

2. empty = N (количество свободных мест в буфере)

3. full = 0 (сколько байт занято в буфере)

Producer:

while (true)

{

produce_item();

p(empty);

p(mutex)

put_item();

v(mutex);

v(full);

}

 

Consumer:

while (true)

{

p(full)

p(mutex)

get_item()

v(mutex)

v(empty)

consume_item()

}