Задача о читателях и писателях

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

 

Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. В общем случае поток-писатель и поток-читатель могут иметь различные скорости и обращаться к буферному пулу с переменой интенсивностью. В один период скорость записи может превышать скорость чтения, в другой – наоборот.

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

 

 

Введем два семафора: е – число пустых буферов, и f – число заполненных буферов, причем в исходном состоянии е =N, a f =0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом.

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

Задача о философах

 

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

Философы проводят жизнь, чередуя приемы пищи и размышления

Чтобы съесть свою порцию, философ должен пользоваться двумя вилками

К несчастью, философам дали всего пять вилок. Между каждой парой философов лежит одна вилка и философы могут пользоваться только теми вилками, которые лежат рядом с ним (слева и справа).

Задача – написать программу, моделирующую поведение философов.

 

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

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

Действия (процессы), выполняемые философами, идентичны друг другу. Например, каждый процесс может сначала взять левую вилку, потому правую. Однако это может привести ко взаимной блокировке процессов. Например, если все философы возьмут свои левые вилки, то они навсегда останутся в ожидании возможности взять правую вилку.

Чтобы избежать взаимной блокировки, можно сделать, чтобы один из философов сперва брал правую вилку, а потом уже левую.

 

Ситуация взаимной блокировки:

Взаимная блокировка, тупик, клинч, дедлок (deadlock) – ситуация, которая может возникнуть в системе, выполненной на безе модели вычислений «сеть процессов», при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, захваченных этими процессами.

Пусть имеются 2 процесса A и B, которым перед началом работы предоставлены ресурсы S_A и S_B, соответственно.

В какой-то момент времени процессу A понадобился S_B, а процессу B – S_A, но они их не получат, т.к. удерживаются предыдущими процессами

Предотвращение данной ситуации:

· Прежде чем процесс начнет свою работу, ему должны быть предоставлены все требуемые ресурсы.

· В том случае, если во время работы ему понадобился дополнительный ресурс, ему необходимо возвратить все ранее выделенные ресурсы ОС и затем запросить все требуемые ресурсы с этим дополнительным ресурсом.