Dining philosophers problem

@Gepar · Регистрация: 01.07.2009

Студворк — интернет-сервис помощи студентам

Не уверен что это тот раздел что мне надо, но раз уж я реализовываю на java то пускай будет он.

Собственно сама задача если кто никогда не встречался с ней:
Пять безмолвных философов сидят вокруг круглого стола, перед каждым философом стоит тарелка спагетти. Вилки лежат на столе между каждой парой ближайших философов.
Каждый философ может либо есть, либо размышлять. Приём пищи не ограничен количеством оставшихся спагетти — подразумевается бесконечный запас. Тем не менее, философ может есть только тогда, когда держит две вилки — взятую справа и слева.
Каждый философ может взять ближайшую вилку (если она доступна), или положить — если он уже держит её. Взятие каждой вилки и возвращение её на стол являются раздельными действиями, которые должны выполняться одно за другим.

Классическая задача, думаю всем известно почему может возникнуть deadlock и голодание философов, так вот я при написании решения сделал некую хитрость и теперь не могу до конца понять спасает ли она меня от деадлока или нет, но опишу всё подробно:
Есть 5 философов (объекты Philosopher), каждый из них при создании узнаёт свой номер + получает объекты левая и правая вилка чтобы знать что хватать (у меня это объекты Lock).

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

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    public void takeFirstFork()
    {
        //если номер философа число парное то он хватает левую вилку первой
        if ( number % 2 == 0 ) {
            state = TAKING_FIRST_FORK_LEFT;
            leftFork.lock();
        }
        //иначе он пытается сначала ухватить правую вилку
        else {
            state = TAKING_FIRST_FORK_RIGHT;
            rightFork.lock();
        }
    }
 
    public void takeSecondFork()
    {
        if ( number % 2 == 0 ) {
            state = TAKING_SECOND_FORK_RIGHT;
            rightFork.lock();
        }
        else {
            state = TAKING_SECOND_FORK_LEFT;
            leftFork.lock();
        }
    }

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

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Объект класса Lock может быть захвачен один потоком один раз.
 * Следующие потоки которые будут пытаться ухватить объект будут поставлены в fifo очередь.
 */
public class Lock
{
    /**
     * очередь потоков которые хотят заблокировать этот объект
     */
    private Vector queue = new Vector();
 
    /**
     * текущий владелец этой блокировки
     */
    private Thread owner = null;
 
    /**
     * возвращает true если поток заблокирван, иначе - false
     */
    public synchronized boolean locked()
    {
        return owner != null;
    }
 
    /**
     * Запросить блокироку. Если блокировка доступна то поток становится владельцем блокировки
     * Иначе поток ожидает до тех пор пока блокировка не освободится.
     */
    public synchronized void lock()
    {
        Thread caller = Thread.currentThread();
        if ( owner != null ) {
            queue.addElement( caller );
            while ( owner != null || caller != queue.firstElement() )
                try { wait(); }
                catch ( InterruptedException e ) {}
            queue.removeElement( caller );
        }
        owner = caller;
    }
 
    /**
     * Снять блокировку. Снять блокировку может только поток который её изначально установил.
     */
    public synchronized void unlock()
    {
        Thread caller = Thread.currentThread();
        if ( caller == owner ) {
            owner = null;
            notifyAll();
        }
    }
}

Вопрос: маленькой хитрости с тем что философы хватают вилки с разных сторон (типичный дедлок по моим наблюдениям получается только когда у всех философов только левая или только правая вилка, те если все пытаються хватить с одной стороны) и того что мой Lock представляет из себя очередь так что никакой философ голодовать постоянно не должен, достаточно или нет ?

На практике пробовал ганять с временем на размышление = 0 и кушанием = пару секунд и до дедлока ни разу не доходило, но всё же нет ли какого-то варианта когда он таки наступит в моём случае?

@mutagen · 03.05.2013, 23:27

это у вас рейс кондишен скорее чем дедлок )
всем надо 2 вилки и их могут захватить разные потоки
в вашей вилке синхронизация по классу и так у вас никакого дедлока не будет, так как одномоментно доступен только 1 метод
можно было даже не брать синхронизированный вектор

итак в метод никого не пустят

вы проверьте у вас в векторе не более 1 обьекта за раз )
принтите его после постановки в очередь

@Gepar · 04.05.2013, 14:36 **[ТС]**

mutagen, ну я проверил тем что установил время кушания = пара секунд, а время размышления = 0 ну и за 5 минут дедлок не получился так что вроде всё хорошо.

Добавлено через 3 минуты

Сообщение от mutagen

это у вас рейс кондишен скорее чем дедлок )

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

@mutagen · 04.05.2013, 14:39

Сообщение от Gepar

тем что есть очередь тех кто "забил" вилку)

ну вот тут какраз и не работает, так как синхронизация по классу, в очереди всегда 1, не более

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@mutagen 2587 / 2260 / 257 Регистрация: 14.09.2011 Сообщений: 5,185 Записей в блоге: 18
	03.05.2013, 23:27
	это у вас рейс кондишен скорее чем дедлок ) всем надо 2 вилки и их могут захватить разные потоки в вашей вилке синхронизация по классу и так у вас никакого дедлока не будет, так как одномоментно доступен только 1 метод можно было даже не брать синхронизированный вектор итак в метод никого не пустят вы проверьте у вас в векторе не более 1 обьекта за раз ) принтите его после постановки в очередь 1