Форум программистов, компьютерный форум, киберфорум
Наши страницы
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
Gepar
1182 / 538 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
1

Dining philosophers problem

03.05.2013, 14:44. Просмотров 577. Ответов 3
Метки нет (Все метки)

Не уверен что это тот раздел что мне надо, но раз уж я реализовываю на 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 и кушанием = пару секунд и до дедлока ни разу не доходило, но всё же нет ли какого-то варианта когда он таки наступит в моём случае?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.05.2013, 14:44
Ответы с готовыми решениями:

class problem
package ta; import java.util.Random; /* @author */ public class Main { public static...

Problem with JAVA!
У меня есть строка к примеру String str = "hafsdhdbsf! sfhguhgsu saags? gaga. aggf."; ← и есть...

Unresolved Compilation Problem
Проверял ошибок нет вечно в консоле выдает ошибку Exception in thread "main"...

installing software has encountered a problem
вот такая проблема захотел поставить ADT 22 и тут ошибка помогите!!:(

jaxb annotation problem if reciprocal links in objects
Есть такая ситуация: @XmlRootElement Class A{ List<B> b; void setB()List<B>{...} @XmlElement...

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

вы проверьте у вас в векторе не более 1 обьекта за раз )
принтите его после постановки в очередь
1
Gepar
1182 / 538 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
04.05.2013, 14:36  [ТС] 3
mutagen, ну я проверил тем что установил время кушания = пара секунд, а время размышления = 0 ну и за 5 минут дедлок не получился так что вроде всё хорошо.

Добавлено через 3 минуты
Цитата Сообщение от mutagen Посмотреть сообщение
это у вас рейс кондишен скорее чем дедлок )
Не-не, тут именно дедлок, в обычной задаче может получиться так что все могут ухватить по левой вилке сразу и потом правой ни для кого не останется же. Ещё возможно голодание одного из философов (у меня это решено тем что есть очередь тех кто "забил" вилку) если какой-то поток не очень удачно будет попадать по времени так что у него всё время перед носом будут вытягивать ресурс.
0
mutagen
2568 / 2241 / 257
Регистрация: 14.09.2011
Сообщений: 5,185
Записей в блоге: 18
04.05.2013, 14:39 4
Цитата Сообщение от Gepar Посмотреть сообщение
тем что есть очередь тех кто "забил" вилку)
ну вот тут какраз и не работает, так как синхронизация по классу, в очереди всегда 1, не более
0
04.05.2013, 14:39
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.05.2013, 14:39

Problem
George likes arithmetics very much. Especially he likes the integers series. His most favourite...

Problem
New->Other->File CPP пишу код cout<<"ll"; getch(); и никак запустить не могу. при F9 реакция...

Socket problem
Добрый день у меня возникла проблема c обменом информацией между компьютерами а точнее есть...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru