Решение задачи писателя-читателя

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

1. использование общей переменной (N), указывающей номер процесса, чья очередь войти в критическую секцию в данный момент.

procedure INIT; common integer N;

Begin N: =1; start (P₁); start (P₂); end;

Process P₁; common integer N;

Begin while true do begin BEFORE₁; while N=2 do; CS₁; N: =2; AFTER₁; end; end;

Process P₂; common integer N;

Begin while true do begin BEFORE₂; while N=1 do; CS₂; N: =1; AFTER₂; end; end;

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

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

Procedure INIT; common Boolean C1, C2;

Begin C1:=false; C2:=false; start (P₁); start (P₂); end;

Process P₁; common Boolean C1, C2;

Begin while true do begin BEFORE₁; while C2 do; C1:=true; CS₁; C1:=false; AFTER₁; end; end;

Process P₂; common Boolean C1, C2;

Begin while true do begin BEFORE₂; while C1 do; C2:=true; CS₂; C2:=false; AFTER₂; end; end;

Если оба процесса одновременно подойдут к проверке значений флажков своих конкурентов перед входом в критическую секцию, они смогут пройти в нее одновременно. Таким образом, нарушается самое главное требование к реализации критической секции - требование взаимного исключения.

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

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

Procedure INIT; common Boolean C1, C2; common integer N;

Begin C1:=false; C2:=false; N: =1; start (P₁); start (P₂); end;

Process P₁; common Boolean C1, C2;

Begin while true do begin BEFORE₁; C1:=true; while C2 do begin if N=2 then begin C1:=false; while N=2 do; C1:=true; end; end; CS₁; C1:=false; N: =2; AFTER₁; end; end;

Process P₂; common Boolean C1, C2;

Begin while true do begin BEFORE₂; C2:=true; while C1 do begin if N=1 then begin C2:=false; while N=1 do; C2:=true; end; end; CS₂; C2:=false; N: =1; AFTER₂; end; end;

 

Семафор - защищенная переменная, которую можно опрашивать и изменять только при помощи специальных примитивов.

P (d) - опрашивает семафорную переменную, т.е. организует потенциальное ожидание, V (d) – изменяет значение семафорной переменной и открывает семафор, если он закрыт.

Типы семафоров.

Бинарный семафор (Binary Semaphore) - принимает 2 значения: открыт или закрыт (0-закрыт, 1-открыт).

Считающий семафор (Integer Semaphore) - принимает целочисленные значения в заданных диапазонах:

1) неотрицательный: такой семафор используется как счетчик ресурсов. Считается открытым, если S>0 (т.к. в наличии есть ресурсы и процессы могут получить к ним доступ). При S=0 процесс должен ждать освобождения ресурсов.

2) допускаются отрицательные значения: они интерпретируются как длина очереди процессов, ожидающих освобождения ресурса.

 

Решение задачи писателя-читателя.

Есть писатель, который записывает n записей начиная с 1-ой в циклический буфер. И есть читатель, который считывает то, что записал писатель. При этом писатель, доходя до конца буфера, переписывает 1 строку в нем. Он не может переписать не прочитанную строку. Читатель же не должен читать дважды одну и ту же запись и читать еще не заполненную запись. Для решения задачи требуется 2 семафора, считающие ресурсы читателя и писателя, и 1 бинарный семафор для защиты буфера.

INIT: Binary Semaphore B; Integer Semaphore E, F; F: =1; E: =N; B: =1; Start (W); Start(R); end;

Process W: begin … while true do begin P(B); P(E); V(B); V(F) {запись в буфер}; end; …; end;

Process R: begin … while true do begin P(F); P(B); Read(P) {чтение данных, подготовленных писателем}; V(B); V(E) {обработка считанных данных}; end; …; end;

 

Средства синхронизации WinNT.

1. Ожидание завершения задачи или процесса. Иногда требуется организовать ожидание окончания работы процесса или потока. WaitForSingleObject - организовывает ожидание завершения одной задачи или одного процесса. В результате выполнения этой функции вызвавший ее поток приостанавливает работу, пока указанный объект (процесс или поток) не завершит свою работу. Результат функции WAIT_OBJECT_0 – задача завершилась «естественным образом»; WAIT_TIMEOUT – завершилось время ожидания; WAIT_ABANDONED – ожидание было отменено (для объектов синхронизации типа Mutex).

2. Синхронизация с помощью событий. Схема использования событий достаточно проста. Один из потоков процесса создает объект-событие с помощью функции CreateEvent, присваивая ему имя, которое будет доступно всем потокам активных процессов. При создании событие переводится в заданное начальное состояние. Другие потоки того же самого или других процессов могут получить описатель объекта по его имени, вызвав функцию OpenEvent. Изменить состояние объекта-события можно с помощью функций SetEvent, ResetEvent или PulseEvent. Организовать ожидание момента, когда событие перейдет в отмеченное (сигнализированное) состояние, можно с помощью функций WaitForSingleObject или WaitForMultipleObject. Если объект становится ненужным его можно закрыть с помощью функции CloseObject.

3. Объект синхронизации Mutex. Этот объект можно использовать для синхронизации задач, выполняющихся в рамках различных процессов. Как и объект-событие, мутекс может находиться в двух состояниях – отмеченном и неотмеченном. С помощью полученного описателя можно получить доступ к мутексу. Для захвата объекта используются функции WaitForSingleObject или WaitForMultipleObjects.

4. Синхронизация с помощью семафоров. Объекты-семафоры позволяют установить счетчик при организации доступа к ресурсу: возможность параллельной работы с ресурсом обеспечивается для заранее определенного ограниченного числа задач (потоков). Потоки, пытающиеся получить доступ к ресурсам сверх установленного лимита, будут переведены в состояние ожидания, пока какой-либо поток, получивший доступ к ресурсу раньше, не освободит его. Значение счетчика семафора уменьшается с помощью функций, которые позволяют захватить ресурс или организовать его ожидание.