Классические задачи синхронизации¶

Задание: необходимо решить эти задачи с помощью различных подходов к синхронизации:

• классический: замки, семафоры, мониторы
• передача сообщений
• STM (программная транзакционная память)

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

Иначе — по вариантам:

1. Спящий парикмахер (сообщения), Обедающие философы (STM), Читатели-писатели (классика)
2. Спящий парикмахер (сообщения), Обедающие философы (классика), Читатели-писатели (STM)
3. Спящий парикмахер (классика), Обедающие философы (сообщения), Читатели-писатели (STM)
4. Спящий парикмахер (классика), Обедающие философы (STM), Читатели-писатели (сообщения)
5. Спящий парикмахер (STM), Обедающие философы (сообщения), Читатели-писатели (классика)
6. Спящий парикмахер (STM), Обедающие философы (классика), Читатели-писатели (сообщения)

Производитель-потребитель¶

http://en.wikipedia.org/wiki/Producer-consumer_problem

Есть буффер ограниченного размера N, к которому имеют доступ 2 нити: производитель и потребитель. Производитель в бесконечном цикле генерирует пакет данных в течение случайного интервала времени и записывает их в буфер в течение какого-то времени t1, если в нем есть свободное место. Потребитель в бесконечном цикле считывает и удаляет данные из буфера (если они там есть) по 1 пакету в течение времени t2, а затем случайный интервал времени обрабатывает их.

Задание: Необходимо смоделировать эту ситуацию в программе в виде 2 нитей исполнения (производителя и потребителя). Работа нитей должна фиксироваться в виде журнала и отображаться на экране. Например (размер буфера: 20):

12:01:10.353 Производитель создал новый пакет данных. В буфере: 19
12:01:11.353 Производитель записал пакет в буфер. В буфере: 20
12:01:11.700 Производитель создал новый пакет данных. В буфере: 20
12:01:11.701 Производитель ожидает. В буфере: 20
12:01:11.910 Потребитель считал пакет из буфера. В буфере: 19
12:01:13.011 Потребитель обработал данные. В буфере: 19
12:01:14.005 Потребитель считал пакет из буфера. В буфере: 18
12:01:14.243 Производитель записал пакет в буфер. В буфере: 19
...

Читатели-писатели¶

http://en.wikipedia.org/wiki/Readers-writers_problem

Есть общий участок памяти, N нитей исполнения, которые только читают из него (читатели), и M нитей, которые только пишут в него (писатели). Когда какая-то из нитей производит запись, остальные нити не должны иметь доступа к памяти.

Задание: Необходимо обеспечить, чтобы чтение могло происходить несколькими нитями одновременно. Необходимо обеспечить, чтобы каждый писатель ждал возможности записи не больше необходимого (т.е. если писатель запросил запись в то время, как какие-то нити читали, он должен ожидать права записи только до того момента, как эти нити закончат чтение, но не до того момента, как его закончат другие, которые могли бы начать чтение позже, чем писатель запросил запись).

Отображение работы программы должно быть подобно задаче Производитель-потребитель.

Спящий парикмахер¶

http://en.wikipedia.org/wiki/Sleeping_barber_problem

В парикмахерской работает 1 парикмахер, у которого есть 1 кресло для стрижки, и N кресел для ожидания клиентов. Клиенты приходят к парикмахеру через случайные промежутки времени. Когда клиентов нет, парикмахер спит в кресле. Когда приходит клиент он будит парикмахера и начинается стрижка. Если парикмахер стрижет кого-то, клиент садится в одно из свободных кресел. Если все кресла заняты, клиент уходит. Когда парикмахер освобождается, он начинает стричь клиента, который ждет дольше всего, или засыпает, если в очереди нет клиентов. Время стрижки клиента также является случайной величиной.

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

12:01:10.353 Парикмахер спит.
12:01:11.412 Клиент 1 пришел в парикмахерску. Очередь: 0
12:01:11.700 Клиент 1 будит парикмахера.
12:01:11.701 Клиент 1 садится на стрижку. Очередь: 0
12:01:11.910 Клиент 2 пришел в парикмахерскую. Очередь: 0
12:01:11.815 Клиент 2 садится в кресло для ожидания. Очередь: 1
12:01:14.810 Клиент 3 пришел в парикмахерскую. Очередь: 1
12:01:14.951 Клиент 1 постригся и уходит из парикмахерской.
12:01:15.115 Клиент 3 садится в кресло для ожидания. Очередь: 2
12:01:15.222 Клиент 1 садится на стрижку. Очередь: 1
...

Обедающие философы¶

http://en.wikipedia.org/wiki/Dining_philosophers_problem

5 философов сидят за столом. Они могут быть в 2-х взаимоисключающих состояниях: думать и есть. Между каждым философом лежит 1 вилка, а перед каждым -- тарелка. Для того чтобы начать есть, философу нужно взять 2 вилки (левую и правую). Сначала философ берет левую, а затем правую.

Задание: Необходимо смоделировать эту ситуацию в программе в виде 5 нитей исполнения (для каждого философа). Работа нитей должна фиксироваться в виде журнала и отображаться на экране. Например:

12:01:10.353 Философ 1 думает. Состояни вилок: 01100
12:01:10.389 Философ 5 взял левую вилку (№5). Состояни вилок: 01101
12:01:10.390 Философ 5 взял правую вилку (№1). Состояни вилок: 11101
12:01:10.391 Философ 5 начал есть.
12:01:11.800 Философ 3 закончил есть.
12:01:11.812 Философ 4 взял левую вилку (№4). Состояни вилок: 11111
12:01:11.813 Философ 4 не смог взять правую вилку (№5). Состояни вилок: 11111
12:01:11.815 Философ 2 положил левую вилку (№2). Состояни вилок: 10111
...

При этом не должно возникать ситуаций deadlock, когда каждый философ взял по одной вилке и ожидает вторую вилку.