Решение задачи писателя-читателя
Программные методы реализации взаимного исключения.
1. использование общей переменной (N), указывающей номер процесса, чья очередь войти в критическую секцию в данный момент.
procedure INIT; common integer N;
Begin N: =1; start (P1); start (P2); end;
Process P1; common integer N;
Begin while true do begin BEFORE1; while N=2 do; CS1; N: =2; AFTER1; end; end;
Process P2; common integer N;
Begin while true do begin BEFORE2; while N=1 do; CS2; N: =1; AFTER2; end; end;
Нарушается одно из требований, предъявляемых к организации критической секции: процесс, имеющий право на вход в свою критическую секцию, но пока не вошедший, блокирует вход в критические секции другим процессам, которые могут быть готовы к обработке общих данных, но не могут получить к ним доступ, т.к. установлена не их очередь.
2. использование переменных-флажков, которые представляют собой признак, показывающий, не находится ли соответствующий ей процесс в своей критической секции.
Procedure INIT; common Boolean C1, C2;
Begin C1:=false; C2:=false; start (P1); start (P2); end;
Process P1; common Boolean C1, C2;
Begin while true do begin BEFORE1; while C2 do; C1:=true; CS1; C1:=false; AFTER1; end; end;
Process P2; common Boolean C1, C2;
Begin while true do begin BEFORE2; while C1 do; C2:=true; CS2; C2:=false; AFTER2; end; end;
Если оба процесса одновременно подойдут к проверке значений флажков своих конкурентов перед входом в критическую секцию, они смогут пройти в нее одновременно. Таким образом, нарушается самое главное требование к реализации критической секции - требование взаимного исключения.
3. Алгоритм Деккера
Процесс, пытающийся войти в КС, заявляет о своем намерении с помощью флажка. В случае если оба процесса заявили о своем намерении войти в КС, порядок входа определяется значением целочисленной переменной.
Procedure INIT; common Boolean C1, C2; common integer N;
Begin C1:=false; C2:=false; N: =1; start (P1); start (P2); end;
Process P1; common Boolean C1, C2;
Begin while true do begin BEFORE1; C1:=true; while C2 do begin if N=2 then begin C1:=false; while N=2 do; C1:=true; end; end; CS1; C1:=false; N: =2; AFTER1; end; end;
Process P2; common Boolean C1, C2;
Begin while true do begin BEFORE2; C2:=true; while C1 do begin if N=1 then begin C2:=false; while N=1 do; C2:=true; end; end; CS2; C2:=false; N: =1; AFTER2; 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. Синхронизация с помощью семафоров. Объекты-семафоры позволяют установить счетчик при организации доступа к ресурсу: возможность параллельной работы с ресурсом обеспечивается для заранее определенного ограниченного числа задач (потоков). Потоки, пытающиеся получить доступ к ресурсам сверх установленного лимита, будут переведены в состояние ожидания, пока какой-либо поток, получивший доступ к ресурсу раньше, не освободит его. Значение счетчика семафора уменьшается с помощью функций, которые позволяют захватить ресурс или организовать его ожидание.