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

@танкист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, не получилось доказать про философов. Он говорит пока формулировку правильную не предоставлю, он в любом случае циклом сможет решить. Формулировки конкретной нет в книге Таненбаума. В той формулировке, которая там дана он сказал задача в любом случае решается конвеером. А в других источниках информация аналогична.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

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

	Обедающие философы 20.04.2014, 15:10. Показов 9343. Ответов 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 19497 / 10102 / 2461 Регистрация: 30.01.2014 Сообщений: 17,808
	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 19497 / 10102 / 2461 Регистрация: 30.01.2014 Сообщений: 17,808
	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

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

Решение