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

@танкист34 · Регистрация: 15.03.2013

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

Добрый вечер! Возник такой вот вопрос:
Есть стандартная задача с обедающими философами, описанная в книге Таненбаума.
Но преподователь спрашивает, почему нельзя сделать всё циклом, он сказал что может сделать обыкновенным циклом и тоже все философы поедят.
Что именно решает эта задача? И почему подход с циклом не верен?
Заранее спасибо.

@Voivoid · 20.04.2014, 17:07

Эта задача актуальна для многопоточной среды

@IrineK · 20.04.2014, 17:12

Условие задачи

Проблема обедающих философов

@танкист34 · 20.04.2014, 17:22 **[ТС]**

Voivoid, подробнее можно?
просто он настаивает на том, что он циклом сможет решить эту задачу и никакой синхронизации не надо. Говорит: "докажи обратное".
Зачем то ещё пример работы планировщика задач приводил в NT системе. Дословно не помню, но смысл заключался в том, что процессы работают с всокими приоритетами и работают и не дают возможности запустится процессу с низким приоритетом, а потомм планировщик берёт и повышает приоритет процесса, который ожидал и он выполняется.(что-то типо того).
Это он дал в пример, когда сказал "давай, вот запустим на многопроцессорной системе".
В итоге: надо ему объяснить, что именно решает данная задача, если накормить философов, то их накормить можно и циклом.

Добавлено через 2 минуты
IrineK, я с книги брал условие, там аналогичное

@DrOffset · 20.04.2014, 18:04

Сообщение от танкист34

что именно решает данная задача

Задача решает проблему взаимных блокировок. Задача ставится именно в контексте параллельных вычислений.

Сообщение от танкист34

никакой синхронизации не надо

Синхронизация нужна, ибо вилки, по условию, разделяемый ресурс.

@танкист34 · 20.04.2014, 18:17 **[ТС]**

DrOffset, а если цклом, то его получится распараллелить? или же он будет выполнятся строго одним потоком (процессом)

@IrineK · 20.04.2014, 18:23

Здесь однопоточное решение на Java

@танкист34 · 20.04.2014, 18:39 **[ТС]**

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

@Voivoid · 20.04.2014, 18:44

Очевидно, что в общем случае цикл можно крутить только в одном потоке

@танкист34 · 20.04.2014, 18:47 **[ТС]**

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

Очевидно, что в общем случае цикл можно крутить только в одном потоке

что значит в общем случае? значит может быть и не в одном?

@DrOffset · 20.04.2014, 18:51

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

Добавлено через 1 минуту
танкист34, вот здесь есть несколько решений на разных языках. В том числе на С и С++.

@танкист34 · 20.04.2014, 18:59 **[ТС]**

DrOffset, спасибо, у меня решение имеется.
Да я то понимаю, что каждый философ (это как разная задача == процесс), НО это надо ещё преподователю доказать, что он не сможет это циклом решить. Особенно против довода, что если выполнять эту задачу на многопроцессорной системе с помощью семафоров, то один из философов может не поесть, а циклом все покушают. Хотя странно, что он не поест никогда, ведь он в очередь встанет.

@DrOffset · 20.04.2014, 19:01

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

Ведь эта задача ставилась в контексте того, что каждый философ - это отдельный, параллельный поток.
Преподаватель похоже тебя провоцирует просто.

@танкист34 · 20.04.2014, 19:07 **[ТС]**

DrOffset, а тогда получается, если мы как вы говорите организуем последовательную кормёжку, то в каждый момент будет кушать только один философ, или же можно по двое?
если по двое можно, то параллельность будет(блин я уже как препод стал рассуждать

), что скорее всего он мне так и скажет, если я ему про параллельность скажу.

@DrOffset · 20.04.2014, 19:11

Сообщение от танкист34

DrOffset, а тогда получается, если мы как вы говорите организуем последовательную кормёжку, то в каждый момент будет кушать только один философ, или же можно по двое?

Ну вот смотри, давай разберемся. Допустим у нас три философа. По условию задачи, вилки лежат между ними, получается вилки тоже три. Как ты сможешь без конкуренции за третью вилку запустить сразу двух обедать? Правильно, никак.
Именно проблему этой конкуренции и призвана решать данная задача.

@танкист34 · 20.04.2014, 19:16 **[ТС]**

DrOffset, дак при трёх философах так и так кушать сможет только один, циклом делаешь кормёжку по очереди и всё. Я про двух имел ввиду, если всего пять вилок.

@DrOffset · 20.04.2014, 19:24

Сообщение от танкист34

Я про двух имел ввиду, если всего пять вилок.

Если философов пять, то и вилок пять. Значит двое могут обедать. Однако, ведь время раздумья - разное. Следовательно синхронность, которую мы вносим последовательным перебором пар - не работает. Если просто завязать на последовательность, получается мы прерываем философа в середине его размышлений словами "жри, скотина"

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

@танкист34 · 20.04.2014, 19:34 **[ТС]**

DrOffset, спасибо большое, приведу ему все доводы, может докажу.

Добавлено через 2 минуты
DrOffset, кстати, на счёт прерывания философа посреди размышлений, то он сказал, что по теории вероятности для больших чисел выходит 50 на 50, следовательно, он расчитает время и получится циклом оптимальнее (я говорю, у него на всё отговорка).

@DrOffset · 20.04.2014, 19:44

Сообщение от танкист34

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

Если сможет рассчитать, то возможно. Однако для каждой задачи (размышления) придется считать по новой.
Давай представим, что еда - это некий набор данных, поев, философ начинает их обрабатывать (т.е. думать). От этих данных зависит длительность вычислений, но неизвестно как именно. Предложи ему решить эту задачу в общем случае.
Эта задача как раз хорошо иллюстрирует проблему перекладывания ответственности. Философ ведь точно знает когда он закончит вычисления. А циклу со стороны, чтобы скомпоновать примерно одинаково по времени вычисляющих философов, чтобы запустить их думать вместе, придется применить нехилый мат. аппарат. Если и будет найдено решение, то оно будет неточным (т.е. всегда останется вероятность ошибки). Так в чем же профит?

@танкист34 · 28.04.2014, 13:16 **[ТС]**

DrOffset, не получилось доказать про философов. Он говорит пока формулировку правильную не предоставлю, он в любом случае циклом сможет решить. Формулировки конкретной нет в книге Таненбаума. В той формулировке, которая там дана он сказал задача в любом случае решается конвеером. А в других источниках информация аналогична.

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 27.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 27.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 25.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

@танкист34 -23 / 0 / 2 Регистрация: 15.03.2013 Сообщений: 328

	Обедающие философы 20.04.2014, 15:10. Показов 9413. Ответов 22 Метки нет (Все метки) Добрый вечер! Возник такой вот вопрос: Есть стандартная задача с обедающими философами, описанная в книге Таненбаума. Но преподователь спрашивает, почему нельзя сделать всё циклом, он сказал что может сделать обыкновенным циклом и тоже все философы поедят. Что именно решает эта задача? И почему подход с циклом не верен? Заранее спасибо. 0

@Voivoid 710 / 283 / 16 Регистрация: 31.03.2013 Сообщений: 1,340
	20.04.2014, 17:07
	Эта задача актуальна для многопоточной среды 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	20.04.2014, 17:12
	Условие задачи Проблема обедающих философов 0

@танкист34 -23 / 0 / 2 Регистрация: 15.03.2013 Сообщений: 328
	20.04.2014, 17:22 [ТС]
	Voivoid, подробнее можно? просто он настаивает на том, что он циклом сможет решить эту задачу и никакой синхронизации не надо. Говорит: "докажи обратное". Зачем то ещё пример работы планировщика задач приводил в NT системе. Дословно не помню, но смысл заключался в том, что процессы работают с всокими приоритетами и работают и не дают возможности запустится процессу с низким приоритетом, а потомм планировщик берёт и повышает приоритет процесса, который ожидал и он выполняется.(что-то типо того). Это он дал в пример, когда сказал "давай, вот запустим на многопроцессорной системе". В итоге: надо ему объяснить, что именно решает данная задача, если накормить философов, то их накормить можно и циклом. Добавлено через 2 минуты IrineK, я с книги брал условие, там аналогичное 0

@танкист34 -23 / 0 / 2 Регистрация: 15.03.2013 Сообщений: 328
	20.04.2014, 18:17 [ТС]
	DrOffset, а если цклом, то его получится распараллелить? или же он будет выполнятся строго одним потоком (процессом) 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	20.04.2014, 18:23
	Здесь однопоточное решение на Java 0

@танкист34 -23 / 0 / 2 Регистрация: 15.03.2013 Сообщений: 328
	20.04.2014, 18:39 [ТС]
	я кажется понял, здесь подразумевается то, что каждый философ это отдельный процесс. Цикл в данном случае не подходит по тому, что мы не знаем какой из процессов обратится первым к разделяемому ресурсу, так как время раздумия надо рассматривать динамиччески(что в цикле не возможно, там мы зададим строго определенный интервал, а в реальности процесс может запросить ресурс в любое время т.е. цикл будет не оптимален). Забыл где, но где - то читал пример про принтеры на семафорах, там похожая ситуация. Но всё равно он завтра с циклом прикопается скорее всего, ладно, всем спасибо, как узнаю правильный ответ напишу, может кому пригодится. 0

@Voivoid 710 / 283 / 16 Регистрация: 31.03.2013 Сообщений: 1,340
	20.04.2014, 18:44
	Очевидно, что в общем случае цикл можно крутить только в одном потоке 0

@DrOffset 19500 / 10105 / 2461 Регистрация: 30.01.2014 Сообщений: 17,818
	20.04.2014, 18:51
	танкист34, для начала неплохо бы выяснить что конкретно предлагается решать циклом и как это будет выглядеть. Нужно исходить из того, что каждый философ обозначает параллельную задачу. Добавлено через 1 минуту танкист34, вот здесь есть несколько решений на разных языках. В том числе на С и С++. 0

@танкист34 -23 / 0 / 2 Регистрация: 15.03.2013 Сообщений: 328
	20.04.2014, 18:59 [ТС]
	DrOffset, спасибо, у меня решение имеется. Да я то понимаю, что каждый философ (это как разная задача == процесс), НО это надо ещё преподователю доказать, что он не сможет это циклом решить. Особенно против довода, что если выполнять эту задачу на многопроцессорной системе с помощью семафоров, то один из философов может не поесть, а циклом все покушают. Хотя странно, что он не поест никогда, ведь он в очередь встанет. 0

@DrOffset 19500 / 10105 / 2461 Регистрация: 30.01.2014 Сообщений: 17,818
	20.04.2014, 19:01
	Если под циклом подразумевается последовательная кормежка философов (т.е. по очереди), то да, можно так решать. Но это будет решение совсем другой задачи Ведь эта задача ставилась в контексте того, что каждый философ - это отдельный, параллельный поток. Преподаватель похоже тебя провоцирует просто. 0

@танкист34 -23 / 0 / 2 Регистрация: 15.03.2013 Сообщений: 328
	20.04.2014, 19:07 [ТС]
	DrOffset, а тогда получается, если мы как вы говорите организуем последовательную кормёжку, то в каждый момент будет кушать только один философ, или же можно по двое? если по двое можно, то параллельность будет(блин я уже как препод стал рассуждать), что скорее всего он мне так и скажет, если я ему про параллельность скажу. 0

@танкист34 -23 / 0 / 2 Регистрация: 15.03.2013 Сообщений: 328
	20.04.2014, 19:16 [ТС]
	DrOffset, дак при трёх философах так и так кушать сможет только один, циклом делаешь кормёжку по очереди и всё. Я про двух имел ввиду, если всего пять вилок. 0

@танкист34 -23 / 0 / 2 Регистрация: 15.03.2013 Сообщений: 328
	20.04.2014, 19:34 [ТС]
	DrOffset, спасибо большое, приведу ему все доводы, может докажу. Добавлено через 2 минуты DrOffset, кстати, на счёт прерывания философа посреди размышлений, то он сказал, что по теории вероятности для больших чисел выходит 50 на 50, следовательно, он расчитает время и получится циклом оптимальнее (я говорю, у него на всё отговорка). 0

@танкист34 -23 / 0 / 2 Регистрация: 15.03.2013 Сообщений: 328
	28.04.2014, 13:16 [ТС]
	DrOffset, не получилось доказать про философов. Он говорит пока формулировку правильную не предоставлю, он в любом случае циклом сможет решить. Формулировки конкретной нет в книге Таненбаума. В той формулировке, которая там дана он сказал задача в любом случае решается конвеером. А в других источниках информация аналогична. 0

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

Решение