History

Л/р 4 - Синхронизация

Необходимо на языке C средствами библиотеки PThreads смоделировать одну из классических задач синхронизации.

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

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

  • Необходимо обеспечить, чтобы чтение могло происходить несколькими нитями одновременно.
  • Необходимо обеспечить, чтобы каждый писатель ждал возможности записи не больше необходимого (т.е. если писатель запросил запись в то время, как какие-то нити читали, он должен ожидать права записи только до того момента, как эти нити закончат чтение (но не другие нити читателей).
Результаты работы программы должны отображаться по мере их появления следующим образом:
12:01:10.353 Читатель 1 хочет читать данные. Ресурс не занят.
12:01:10.354 Читатель 1 начал чтение.
12:01:10.453 Читатель 2 хочет читать данные. Читатель 1 читает ресурс.
12:01:10.456 Читатель 2 начал чтение.
12:01:11.000 Писатель 1 хочет писать данные. Читатели 1, 2 читают ресурс.
12:01:11.001 Писатель 1 ожидает.
12:01:11.100 Читатель 1 закончил чтение. Читатель 2 читает ресурс. Писатель 1 ожидает. 
12:03:08.500 Читатель 3 хочет читать данные. Читатель 2 читает ресурс. Писатель 1 ожидает. 
12:03:08.501 Читатель 3 ожидает. Читатель 2 читает ресурс. Писатель 1 ожидает. 
12:05:11.100 Читатель 2 закончил чтение. Ресурс свободен. Писатель 1 ожидает. Читатель 3 ожидает.
12:05:11.105 Писатель 1 начал запись. Писатель 1 пишет. Читатель 3 ожидает.
...

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

В парикмахерской работает 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
...

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

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

Необходимо избежать ситуаций deadlock или голодание.

Результаты работы программы должны отображаться по мере их появления следующим образом:
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.813 Философ 4 положил левую вилку. Состояние вилок: 11101
12:01:11.815 Философ 2 положил левую вилку (№2). Состояние вилок: 10101
...

Задания по вариантам (номер варианта — остаток от деления номера зачетки на 3 плюс 1):

  1. Задача Спящий парикмахер (примечание: не использовать Read-write lock, только обычные семафоры).
  2. Задача Обедающие философы.
  3. Задача Читатели-писатели.

Литература:

Оценка: 10 баллов.

Дополнительно можно решить любую из 3х задач методом передачи сообщений на языке Erlang или с помощью STM на языке Clojure — +10 баллов.

Срок сдачи: 16.11.2011

Also available in: HTML TXT