VPF::Обедающие философы.. - Форум программистов

Crash512

Дата 8.1.2007, 15:40 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 61
Регистрация: 12.9.2006

Репутация: нет
Всего: нет

В универе нам задали написать данный алгоритм... Исходя лишь из описания, приведённого ниже. Может кто-нибудь сталкивался?.. Я не особо въехал...

Цитата

В 1965 году Дейкстра сформулировал и решил проблему синхронизации, назван¬ную им проблемой обедающих философов. С тех пор каждый, кто изобретал еще один новый примитив синхронизации, считал своим долгом продемонстрировать достоинства нового примитива на примере проблемы обедающих философов. Про¬блему можно сформулировать следующим образом: пять философов сидят за круг¬лым столом, и у каждого есть тарелка со спагетти. Спагетти настолько скользкие, что каждому философу нужно две вилки, чтобы с ними управиться. Между каж¬дыми двумя тарелками лежит одна вилка. Жизнь философа состоит из чередующихся периодов поглощения пищи и раз¬мышлений. (Разумеется, это абстракция.) Ког¬да философ голоден, он пытается получить две вилки, левую и правую, в любом порядке. Если ему удалось получить две вилки, он некоторое время ест, затем кладет вилки обратно и продолжает размышления. Вопрос состоит в следующем: можно ли написать алгоритм, который моделирует эти действия для каждого философа и никогда не застревает?
Можно изменить алгоритм так, чтобы после получения левой вилки прове¬рялась доступность правой. Если правая вилка недоступна, философ отдает левую вилку обратно, ждет некоторое время и повторяет весь процесс. Этот подход также не будет работать, хотя и по другой причине. Если не повезет, все пять философов могут начать процесс одновременно, взять левую вилку, обнаружить отсутствие правой, положить левую обратно на стол, одновременно взять левую вилку, и так до бесконечности. Ситуация, в которой все программы продолжают работать сколь угодно долго, но не могут добиться хоть какого-то прогресса, называется зависа¬нием процесса. Внести улучшение, исключающее взаимоблокировку и зависание процесса: защитить пять операторов, следующих за запросом think, бинарным семафором. Тогда философ должен будет выполнить операцию down на переменной mutex прежде, чем потянуться к вилкам. А после возврата вилок на место ему следует выполнить операцию up на переменной mutex. С теоретической точки зрения решение вполне подходит. С точки зрения практики возникают про¬блемы с эффективностью: в каждый момент времени может есть спагетти только один философ. Но вилок пять, поэтому необходимо разрешить есть в каждый мо¬мент времени двум философам. Решение, исключающее взаимоблокировку и по¬зволяет реализовать максимально возможный параллелизм для любого числа фи¬лософов. Здесь используется массив state для отслеживания душевного состояния каждого философа: он либо ест, либо размышляет, либо голодает (пытаясь полу¬чить вилки). Философ может начать есть, только если ни один из его соседей не ест.

Rodman

Дата 9.1.2007, 15:42 (ссылка)

(нет голосов)

Загрузка ...

CIO

Профиль
Группа: Участник
Сообщений: 6144
Регистрация: 7.5.2006
Где: Ukraine ⇛ Kyiv ci ty

Репутация: 7
Всего: 122

а так тебе понятней будет?!

--------------------

CRM с функцией АвтоОбзвона

Лотереи мира

Crash512

Дата 9.1.2007, 21:04 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 61
Регистрация: 12.9.2006

Репутация: нет
Всего: нет

Пасиб... Уже всё написал...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C++ Builder \| Следующая тема »