Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
20.04.2014, 15:10     Обедающие философы #1
Добрый вечер! Возник такой вот вопрос:
Есть стандартная задача с обедающими философами, описанная в книге Таненбаума.
Но преподователь спрашивает, почему нельзя сделать всё циклом, он сказал что может сделать обыкновенным циклом и тоже все философы поедят.
Что именно решает эта задача? И почему подход с циклом не верен?
Заранее спасибо.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2014, 15:10     Обедающие философы
Посмотрите здесь:

C# Обедающие философы
C++ Обедающие философы
C++ Процессы, Обедающие философы
C# Обедающие философы, перевод с Delphi
C# .NET 4.x Обедающие философы. Решение методом монитора

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
20.04.2014, 17:07     Обедающие философы #2
Эта задача актуальна для многопоточной среды
IrineK
Заблокирован
20.04.2014, 17:12     Обедающие философы #3
Условие задачи

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

Добавлено через 2 минуты
IrineK, я с книги брал условие, там аналогичное
DrOffset
6450 / 3824 / 885
Регистрация: 30.01.2014
Сообщений: 6,620
20.04.2014, 18:04     Обедающие философы #5
Цитата Сообщение от танкист34 Посмотреть сообщение
что именно решает данная задача
Задача решает проблему взаимных блокировок. Задача ставится именно в контексте параллельных вычислений.
Цитата Сообщение от танкист34 Посмотреть сообщение
никакой синхронизации не надо
Синхронизация нужна, ибо вилки, по условию, разделяемый ресурс.
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
20.04.2014, 18:17  [ТС]     Обедающие философы #6
DrOffset, а если цклом, то его получится распараллелить? или же он будет выполнятся строго одним потоком (процессом)
IrineK
Заблокирован
20.04.2014, 18:23     Обедающие философы #7
Здесь однопоточное решение на Java
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
20.04.2014, 18:39  [ТС]     Обедающие философы #8
я кажется понял, здесь подразумевается то, что каждый философ это отдельный процесс.
Цикл в данном случае не подходит по тому, что мы не знаем какой из процессов обратится первым к разделяемому ресурсу, так как время раздумия надо рассматривать динамиччески(что в цикле не возможно, там мы зададим строго определенный интервал, а в реальности процесс может запросить ресурс в любое время т.е. цикл будет не оптимален).
Забыл где, но где - то читал пример про принтеры на семафорах, там похожая ситуация.
Но всё равно он завтра с циклом прикопается скорее всего, ладно, всем спасибо, как узнаю правильный ответ напишу, может кому пригодится.
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
20.04.2014, 18:44     Обедающие философы #9
Очевидно, что в общем случае цикл можно крутить только в одном потоке
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
20.04.2014, 18:47  [ТС]     Обедающие философы #10
Цитата Сообщение от Voivoid Посмотреть сообщение
Очевидно, что в общем случае цикл можно крутить только в одном потоке
что значит в общем случае? значит может быть и не в одном?
DrOffset
6450 / 3824 / 885
Регистрация: 30.01.2014
Сообщений: 6,620
20.04.2014, 18:51     Обедающие философы #11
танкист34, для начала неплохо бы выяснить что конкретно предлагается решать циклом и как это будет выглядеть.
Нужно исходить из того, что каждый философ обозначает параллельную задачу.

Добавлено через 1 минуту
танкист34, вот здесь есть несколько решений на разных языках. В том числе на С и С++.
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
20.04.2014, 18:59  [ТС]     Обедающие философы #12
DrOffset, спасибо, у меня решение имеется.
Да я то понимаю, что каждый философ (это как разная задача == процесс), НО это надо ещё преподователю доказать, что он не сможет это циклом решить. Особенно против довода, что если выполнять эту задачу на многопроцессорной системе с помощью семафоров, то один из философов может не поесть, а циклом все покушают. Хотя странно, что он не поест никогда, ведь он в очередь встанет.
DrOffset
6450 / 3824 / 885
Регистрация: 30.01.2014
Сообщений: 6,620
20.04.2014, 19:01     Обедающие философы #13
Если под циклом подразумевается последовательная кормежка философов (т.е. по очереди), то да, можно так решать. Но это будет решение совсем другой задачи Ведь эта задача ставилась в контексте того, что каждый философ - это отдельный, параллельный поток.
Преподаватель похоже тебя провоцирует просто.
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
20.04.2014, 19:07  [ТС]     Обедающие философы #14
DrOffset, а тогда получается, если мы как вы говорите организуем последовательную кормёжку, то в каждый момент будет кушать только один философ, или же можно по двое?
если по двое можно, то параллельность будет(блин я уже как препод стал рассуждать), что скорее всего он мне так и скажет, если я ему про параллельность скажу.
DrOffset
6450 / 3824 / 885
Регистрация: 30.01.2014
Сообщений: 6,620
20.04.2014, 19:11     Обедающие философы #15
Цитата Сообщение от танкист34 Посмотреть сообщение
DrOffset, а тогда получается, если мы как вы говорите организуем последовательную кормёжку, то в каждый момент будет кушать только один философ, или же можно по двое?
Ну вот смотри, давай разберемся. Допустим у нас три философа. По условию задачи, вилки лежат между ними, получается вилки тоже три. Как ты сможешь без конкуренции за третью вилку запустить сразу двух обедать? Правильно, никак.
Именно проблему этой конкуренции и призвана решать данная задача.
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
20.04.2014, 19:16  [ТС]     Обедающие философы #16
DrOffset, дак при трёх философах так и так кушать сможет только один, циклом делаешь кормёжку по очереди и всё. Я про двух имел ввиду, если всего пять вилок.
DrOffset
6450 / 3824 / 885
Регистрация: 30.01.2014
Сообщений: 6,620
20.04.2014, 19:24     Обедающие философы #17
Цитата Сообщение от танкист34 Посмотреть сообщение
Я про двух имел ввиду, если всего пять вилок.
Если философов пять, то и вилок пять. Значит двое могут обедать. Однако, ведь время раздумья - разное. Следовательно синхронность, которую мы вносим последовательным перебором пар - не работает. Если просто завязать на последовательность, получается мы прерываем философа в середине его размышлений словами "жри, скотина" Это опять решение не той задачи, которая была поставлена. По условию философ начинает есть, когда закончил думать. Т.е. он пытается инициировать этот процесс, и ожидает только если нет доступных вилок.
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
20.04.2014, 19:34  [ТС]     Обедающие философы #18
DrOffset, спасибо большое, приведу ему все доводы, может докажу.

Добавлено через 2 минуты
DrOffset, кстати, на счёт прерывания философа посреди размышлений, то он сказал, что по теории вероятности для больших чисел выходит 50 на 50, следовательно, он расчитает время и получится циклом оптимальнее (я говорю, у него на всё отговорка).
DrOffset
6450 / 3824 / 885
Регистрация: 30.01.2014
Сообщений: 6,620
20.04.2014, 19:44     Обедающие философы #19
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от танкист34 Посмотреть сообщение
кстати, на счёт прерывания философа посреди размышлений, то он сказал, что по теории вероятности для больших чисел выходит 50 на 50, следовательно
Если сможет рассчитать, то возможно. Однако для каждой задачи (размышления) придется считать по новой.
Давай представим, что еда - это некий набор данных, поев, философ начинает их обрабатывать (т.е. думать). От этих данных зависит длительность вычислений, но неизвестно как именно. Предложи ему решить эту задачу в общем случае.
Эта задача как раз хорошо иллюстрирует проблему перекладывания ответственности. Философ ведь точно знает когда он закончит вычисления. А циклу со стороны, чтобы скомпоновать примерно одинаково по времени вычисляющих философов, чтобы запустить их думать вместе, придется применить нехилый мат. аппарат. Если и будет найдено решение, то оно будет неточным (т.е. всегда останется вероятность ошибки). Так в чем же профит?
танкист34
-62 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 328
28.04.2014, 13:16  [ТС]     Обедающие философы #20
DrOffset, не получилось доказать про философов. Он говорит пока формулировку правильную не предоставлю, он в любом случае циклом сможет решить. Формулировки конкретной нет в книге Таненбаума. В той формулировке, которая там дана он сказал задача в любом случае решается конвеером. А в других источниках информация аналогична.
Yandex
Объявления
28.04.2014, 13:16     Обедающие философы
Ответ Создать тему
Опции темы

Текущее время: 09:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru