Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / Новая постановка старой задачи с обедающими философами / 17 сообщений из 17, страница 1 из 1
23.08.2016, 12:49
    #39296190
liberum
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
За круглым столом сидит 6 философов, перед каждым тарелка с едой, по сторонам у каждого философа вилка и нож, всего 3 ножа и 3 вилки. То есть последовательность - философ-вилка-философ-нож-философ-вилка- и т.д.
Что бы поесть философ должен взять вилку и нож в руки, если нет вилки или ножа, философ ждет недостающий прибор, поев философ освобождает приборы.

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

Не понятно, как сделать круглый стол с приборами, рассадив туда философов.
...
Рейтинг: 0 / 0
23.08.2016, 13:23
    #39296229
liberum
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
Покуда ходил в магазин, придумал такое.
Есть обьект стол, у которого есть поля вилка1, вилка2, вилка3 и нож1, нож2, нож3 - буллеановские, показывающие доступность прибора.

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

Я с потоками больше, чем просто запустить по клику выполнение цикла в отдельном потоке не сталкивался, какие могут быть подводные камни, о чем прежде всего почитать?
И вопрос хватит ли буллеановых полей, или надо создавать обьекты вилка и нож, и работать с ними?
...
Рейтинг: 0 / 0
23.08.2016, 13:43
    #39296248
Сергей Арсеньев
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
liberumНе понятно, как сделать круглый стол с приборами, рассадив туда философов.

Преамбула.

Главное достоинство объектной модели - интуитивно понятная логика переходящая от модели реального мира. Главный недостаток - неоднозначность перехода. Усугубляется еще и тем, что в зависимости от того, как модель реального мира будет представлена в объектной модели зависит то, какие алгоритмы можно будет применять для решения поставленной задачи и их сложность. Да и люди мыслят не тривиально, поэтому простое и очевидное для одного - темный лес для другого и наоборот. :)

Собственно ответ.
Философ это детерминированный автомат с признаком состояния голоден/сыт (собственно цель накормить всех). Двумя слотами (нож и вилка). (соответственно 4 состояния от пусто-пусто до занято-занято, последнее состояние и меняет первый признак).
И ссылки на двух соседей (право-лево).
Ну и правила передачи предметов (только из полного в пустой). Два одновременно передавать третьему одинаковый предмет не могут.

P.S. Главный интерес в игре - вызвать deadlock, понять почему. Добиться чтоб не вызывался и перейти к следующему. :)
...
Рейтинг: 0 / 0
23.08.2016, 16:11
    #39296456
liberum
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
Сергей Арсеньев,

спасибо, как я понимаю, должно быть что-то типа кольцевого связного списка?

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
public class Feeder{
	
	class Philosopher{
		String name;
		boolean feed;
		Philosopher next;
		Philosopher prev;
		boolean fork;
		boolean khine;
		public Philosopher(boolean fork, boolean khine){
			this.fork = fork;
			this.khine = khine;
		}
	}
	Philosopher root = null;
		
	public boolean takeFork(){
		boolean fork = false;
		if(!root.next.fork)
			fork = true;
		return fork;
	}
}



ну и реализация остальных методов..

Если я мыслю в правильном направлении, то как инициировать? Я работал со связным списком без потоков, понимаю, как он работает, а что меняется для запуска каждой ноды в отдельном потоке? Как получать доступ к нодам в других потоках?
...
Рейтинг: 0 / 0
23.08.2016, 17:25
    #39296533
Паша01
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
Я пока что на первой строчке остановился, судя по описанию, последовательность должна быть, к примеру, философ-вилка-нож-философ-вилка-нож-...
...
Рейтинг: 0 / 0
23.08.2016, 18:17
    #39296567
liberum
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
Паша01Я пока что на первой строчке остановился, судя по описанию, последовательность должна быть, к примеру, философ-вилка-нож-философ-вилка-нож-...
нет, так каждому философу будет по прибору и задача потеряет смысл, задача в том, что бы на 3 пары приборов поели 6 человек, в классической задаче 1 вилка, и потому все обращаются по таймауту к одному предмету в случайном диапазоне времени, а в моем случаи одна часть прибора справа и вторая слева.

вот схематично нарисовал
https://i.gyazo.com/d94e44fbec76c5780cc742c80db62198.png
...
Рейтинг: 0 / 0
23.08.2016, 18:55
    #39296594
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
liberum, ты все напутал. В классической постановке задача моделировала дедлок при условии
что все 5 филосов берут вилки с лева направо.

Решение дедлока - смена порядка рук. 2 из трех философоф меняют руки и проблема решена.

Но ты зачем-то ввел еще и нож (непонятно что это дает кроме запутывания читателя).

Кроме того ты пишешь что в классической задаче - 1 вилка - это НЕПРАВДА.
...
Рейтинг: 0 / 0
23.08.2016, 19:10
    #39296607
liberum
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
maytonliberum, ты все напутал. В классической постановке задача моделировала дедлок при условии
что все 5 филосов берут вилки с лева направо.

Решение дедлока - смена порядка рук. 2 из трех философоф меняют руки и проблема решена.

Но ты зачем-то ввел еще и нож (непонятно что это дает кроме запутывания читателя).

Кроме того ты пишешь что в классической задаче - 1 вилка - это НЕПРАВДА.
Возможно я не прав в плане классической задачи, но моя нарисована на рисунке, там не одна вилка а вилка и нож, что бы поесть надо 2 взять и нож и вилку. если у тебя только нож, надо ждать вилку, возможен вариант, что у всех будет или нож или вилка, и цикл замкнется, это не исключается. В целом задача более глобально, поесть надо несколько раз, со временем хочется есть снова, характер у разных философов разный, одни берут один прибор и ждут пока не появится второй, другие если нет второго прибора, первый кладут на место, и через время пробуют снова.. Но у меня сейчас проблема в понимании стола, выше вариант где стола нет, а идет проверка только на наличие у соседа прибора, но тут надо как то надо создать в разных потоках и взаимодействовать между ними, читаю сейчас о работе с потоками статьи.. пока не придумал как сделать..
...
Рейтинг: 0 / 0
23.08.2016, 20:43
    #39296660
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
liberum, убери стол вообще из рассуждений. Он тебя путает.

Философ - thread. Вилка - мутекс.
...
Рейтинг: 0 / 0
23.08.2016, 20:50
    #39296663
Partisan M
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
Три философа пусть набивают брюхо. Надо пристроить ещё троих. Один пусть займётся решением этой задачи. Второго послать в магазин за недостающими ножами-вилками (и стаканами, естественно). Последнего послать в магазин за бутылками. И ничего программировать не надо.
...
Рейтинг: 0 / 0
23.08.2016, 21:02
    #39296667
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
На то они и философы. Будь это обедающие гангстеры - нам бы пришлось вводить в задачу
ножи и Tommy-Guns.
...
Рейтинг: 0 / 0
24.08.2016, 00:47
    #39296718
liberum
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
maytonliberum, убери стол вообще из рассуждений. Он тебя путает.

Философ - thread. Вилка - мутекс.

Спасибо..
Получается, нужно создать класс философов, реализующий Runnable, потом класс где будет synchronized метод вилок и класс где будет synchronized метод ножей, потом в мейне создать 6 экземпляров философов, 3 экземпляра вилок, 3 экземпляра ножей, раздать из расчета 1 вилка и 1 нож на каждые два философа и смотреть кто когда поест..
Я правильно понял?
...
Рейтинг: 0 / 0
24.08.2016, 01:18
    #39296725
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
liberum, пиши код. Слова ничего не значат. Иначе мы еще пару недель будем обсуждать
свойства ножей в отличие от вилок.
...
Рейтинг: 0 / 0
24.08.2016, 07:59
    #39296789
liberum
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
авторliberum, пиши код. Слова ничего не значат.
Как-то так..

Код: 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.
public class Philosopher implements Runnable{
	
	private int strategy;
	private String name; 
	Thread t;
	Khine k;
	Fork f;
	
	Random rnd = new Random();
	
	Philosopher(String name, int st, Khine k, Fork f) {
	this.name = name;
	strategy = st;
	this.k = k;
	this.f = f;
	t = new Thread(this, name);
	System.out.println("Новый поток: " + t) ;
	t.start(); 
	}
	 
	public void run () {
		System.out.println(name + ": khine=" + k.isKhine() + ", fork = " + f.isFork());
		try {
			Thread.sleep(rnd.nextInt(3000));
		}
		catch (InterruptedException e) {
		System.out.println(name +" прерван");
		}
	System.out.println(name + " завершен.");
	}	
}



Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
public class Khine
{
	private boolean khine = true;

	synchronized public boolean isKhine()
	{
		return khine;
	}

	public void setKhine(boolean khine)
	{
		this.khine = khine;
	}
}



Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
public class Fork
{
	private boolean fork= true;

	synchronized public boolean isFork()
	{
		return fork;
	}

	public void setFork(boolean fork)
	{
		this.fork = fork;
	}
}



Код: 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.
public class Main
{

	public static void main(String[] args)	{
		Khine k1 = new Khine();
		Khine k2 = new Khine();
		Khine k3 = new Khine();
		
		Fork fr1 = new Fork();
		Fork fr2 = new Fork();
		Fork fr3 = new Fork();
		
		Philosopher f1 = new Philosopher("One", 1, k1, fr1);
		Philosopher f2 = new Philosopher("Two", 1, k2, fr1);
		Philosopher f3 = new Philosopher("Three", 1, k2, fr2);
		Philosopher f4 = new Philosopher("Four", 1, k3, fr2);
		Philosopher f5 = new Philosopher("Fife", 1, k3, fr3);
		Philosopher f6 = new Philosopher("Six", 1, k1, fr3);
		
		try { 
			System.out.println("Ожидание завершения потоков.");
			f1.t.join();
			f2.t.join();
			f3.t.join();
			f4.t.join();
			f5.t.join();
			f6.t.join();
			}
			catch (InterruptedException e) {
			System.out.println("Главный поток прерван");
			}
			System.out.println("Главный поток завершен.");
	}
}



Теперь попробую сделать остальную часть задачи, надеюсь дальше будет проще для понимания..
...
Рейтинг: 0 / 0
24.08.2016, 08:53
    #39296811
XDiaBLo
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
khine - это нож на каком языке?
...
Рейтинг: 0 / 0
24.08.2016, 09:29
    #39296842
liberum
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
XDiaBLokhine - это нож на каком языке?

Затупил, весь день читал потоки вчера, в голове каша :)

Но дальнейшее развитие..

Наш философ претерпел некоторые изменения, теперь он начал кушать и поправляться.. И периодически думать, пока не занят едой :D Собственно код:

Код: 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.
54.
55.
56.
57.
58.
59.
60.
61.
62.
package main;

import java.util.Random;

public class Philosopher implements Runnable{
	
	private int strategy;
	private String name; 
	Thread t;
	Knife k;
	Fork f;
	int life = 50;
	
	Random rnd = new Random();
	
	Philosopher(String name, int st, Knife k, Fork f) {
	this.name = name;
	strategy = st;
	this.k = k;
	this.f = f;
	t = new Thread(this, name);
	System.out.println("Новый поток: " + t) ;
	t.start(); 
	}
	 
	public void run () {
		StratRND();
	System.out.println(name + " завершен.");
	}
	
	private void StratRND(){
		while(life < 100){
			if(k.isKnife() && f.isFork()){
				k.setKnife(false);
				try {
					Thread.sleep(500);
					life += 10;
					System.out.println(name +" +10 HP(" + life + ")");
				}
				catch (InterruptedException e) {
				System.out.println(name +" прерван");
				}
				k.setKnife(true);
				try {
					Thread.sleep(200);
				}
				catch (InterruptedException e) {
				System.out.println(name +" прерван");
				}
			} else {
				try {
					System.out.println(name +" ожидает");
					Thread.sleep(200 + rnd.nextInt(100));
				}
				catch (InterruptedException e) {
				System.out.println(name +" прерван");
				}
			}
		}
		System.out.println(name +" Life=" + life);
	}
}



У кода большой минус, во время активных размышлений философ не тратит силы.. А должен.. Каким-то образом, раз в секунду он должен терять 10 НР.. Я так понимаю, это поток внутри потока, и из того, что я читал вчера, это должен быть демон поток. Если философ умирает (0 НР), то поток прекращается. На этот случай я видел ставят буллеановскую переменную, которую проверяют в while(true), и при смене значения этой переменной, завершают поток.


И еще вопрос, если вдруг все философы будут сыты, 100 НР у каждого, то надо завершить потоки, собственно вопрос, это должен быть еще один класс, в котором и надо хранить НР философов, сами философы будут туда скидывать +10НР или -10НР, а там будет бегать бесконечный цикл, который вернет false всем, если у всех НР 100, или вернет false одному, если у него НР 0.
Или это решается как то проще?
...
Рейтинг: 0 / 0
26.08.2016, 14:46
    #39298644
Atum1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Новая постановка старой задачи с обедающими философами
Видео Вам в помощь

YouTube Video
...
Рейтинг: 0 / 0
Форумы / Java [игнор отключен] [закрыт для гостей] / Новая постановка старой задачи с обедающими философами / 17 сообщений из 17, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]