ChA MasterZiv есть системы, где порядок доступа к ресурсам не определен вообще
Дидлок - следствие конкуренции процессов за ресурсы. Нет конкуренции, нет дидлоков.
P.S. "В очередь, сукины дети !" ©


Правильно.
Поэтому, чтобы покупатели не подрались у полки в магазине за последнюю модель самолёта с серийным номером 321 и одну из баночек краски защитного цвета (без которой обычно эту модель никто не покупает), мы будем сукиных детей в магазин запускать по очереди :).
Хотя нам, продавцам, совершенно всё равно, если два покупателя подерутся за эту модельку прямо у полки .

softwarermikronпропущено...

Разрешаю разгласить тайну: показывайте эту строчку.
Подсказываю: для того, чтобы дедлок имел шанс возникнуть, должны быть выполнены некоторые условия. Существует техническая возможность сравнительно просто перестроить работу любой произвольной ИС таким способом, чтобы одно из этих условий заведомо не выполнялось.

1. softwarer, непонятно что такое "произвольной ИС".
2. mikron, непонятно что такое "система полностью подконтрольна".
3. mikron, непонятно что такое "внешних источников помех нет".

4. mikron, любой путь ухода от дедлока потребует дополнительных затрат со стороны системы:
1) дополнительные ресурсы памяти;
2) дополнительные вычисления;
3) дополнительное время на обработку;

или может "упереться" в нефункциональные требований (при имеющихся ограничениях в вычислительных ресурсах):

1) максимальное время обработки пакета не должно превышать ...;
2) количество повторных попыток обработки пакета не должно превышать ...;
3) время ожидания пакета до обработки не должно превышать ...;

Какая-то тонкость кроется в твоём ограничении "Не изменяемы только функциональные требования к системе"...

Если нет нефункциональных требований ("быстрая" обработка множества ресурсов) и архитектурных требований ("должно" быть множество потоков/процессов/процессоров), то чисто архитектурные решения для ухода от риска дедлока найдутся: здесь уже озвучено "В очередь!" и ещё пара-тройка найдётся даже на википедии...
Озвучь, в чём твой риск дедлока состоит? :).

Привожу теоретический пример:

1. Среда:
1.1. В системе есть множество ресурсов;
1.2. Есть внешняя среда, из которой хаотично в систему поступают "пакеты";
1.3. Содержимое пакета: критерий (условие отбора подмножества ресурсов) и задача для обработки ресурсов из этого подмножества;
1.4. подмножества, отобранные по критериям пакетов, могут пересекаться.

2. Задача системы:
"обрабатывать" пакеты: находить ресурсы по критериям и выполнять над каждым из ресурсов поставленную задачу.

3. Функциональные требования (как следствие свойств ресурса и характера задач)
3.1. Над конкретным ресурсом в один момент времени может выполняться только одна задача;
3.2. Ресурсы, отобранные по критерию одного пакета, должны обрабатываться "как единое целое":
3.2.1. чтобы пакет считался обработанным, должен быть обработан каждый ресурс, указанный в пакете;
3.2.2. пока в пакете есть необработанные ресурсы, уже обработанные ресурсы пакета не должны быть доступны для выполнения задач других пакетов;

Если есть архитектурное решение/требование "Многопроцессная среда обработки" (чтобы не было желающих устроить одну и только одну очередь :), получаем потенциальный риск дедлока...

А устранить можно всегда, если "нам всё подконтрольно" (с) mikron, и если не упрёмся в нефункциональные требования при ограничениях вычислительных ресурсов...

vromanovАнатоЛойПоэтому, чтобы покупатели не подрались у полки в магазине за последнюю модель самолёта с серийным номером 321 и одну из баночек краски защитного цвета (без которой обычно эту модель никто не покупает), мы будем сукиных детей в магазин запускать по очереди :).
Хотя нам, продавцам, совершенно всё равно, если два покупателя подерутся за эту модельку прямо у полки .
Не обязательно.. Надо просто модель продавать тому, кто схватит ее первым, а краску только обладетелю модели. Точнее организовать конвеер. Т.е. продавать товары в порядке артикула.
Артикулы А, Б, В. 1-му покупателю нужно А и В, второму Б и В. Продай в порядке артикулов, если В в 1-ом экземпляре... Всё равно за В передерутся.

Dimitry SibiryakovАнатоЛойВсё равно за В передерутся.
Да, но дедлока не будет. Второй просто подождёт пока не подвезут.

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

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

Dimitry SibiryakovАнатоЛойТеперь допускаем, что...
....система построена без использования естественного интеллекта. Ну и кто при этом ССЗБ?..

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

vromanovДедлки возникают по следующей причне. У вакс есть два объекта A и Б. Предположим, это количество средств на счету покупателя и количество товара Х.
Дедлок возникнет если одна часть вашего приложения, сначала залочит объект А, вторая объект Б. А потом первая попытается получить доступ к Б а вторая к А. Вот они и будут ждать друг-друга.

Я вас понял, вы меня - нет. Ваше описание дедлока мне понятно. Она - суть простейшей модели дедлока. Я привёл пример из жизни, работающий именно по этой модели, только, похоже, вы за множеством дедлоков в моём примере этот самый дедлок то и не заметили.

Мой пример работает по вашей модели:
Вместо объекта А - компот, вместо объекта Б - пирожное.
Два чувака (две части нашего приложения) покупают подружкам пирожное с компотом , но один сначала пошёл налево за пирожным, второй направо за компотом (лочат объекты А и Б).
Когда каждый из них пришёл за вторым блюдом (попытались получить доступ к Б и А), оказалось что второго блюда для них нет. Каждому вернуться к барышням без второго блюда гордость не позволяет, новые компоты с пирожными не приносят.
"Вот они и будут ждать друг-друга", ожидая, кто вернёт своё блюдо на полку первым :).

vromanovАнатоЛой поскольку мы не столовая, а кафе, в которой 99% заказов - из одного блюда). Что дальше?
не вижу тут причны для дедлока.

Конкретно данная фраза - про неэффективность организации потока с подносами.
Причина для дедлока надеюсь внятно описана выше на ваших объектах А и Б.

vromanovОтсутвие таких проблем решается дизайном.
Также для уменшения врероятности любых - уменьшение зацепления.
Т.е. если у вас етсь транзакции делайте их короткими.
Например, если кто-то выбрал товар, то не надо лочить эту строчку, а просто зарезервируйте его на некоторое количество времени и осводите транзакцию.
По-моему, никто из участников не сомневается, что проблема дедлока решается - если нет требований/ограничений для реализации того или иного алгоритма. Мы с первом поста говорим о том, есть ли такие функциональные требований (читай "требования из среды") , что дедлоки таки будут случаться (читай "нельзя организовать обработку ресурсов таким образом, что мы полностью избежим ситуаций с возникновением дедлока, и не придётся придумывать тайм-ауты или "внешних наблюдателей" или доп. обработку, прежде чем заблокировать ресурс")). Я привёл пример, когда упорядочивание ресурсов (последовательность блюд на вдоль реек с подносами) и упорядочивание потребителей ресурсов (посетителей кафе в очереди с подносами) не удовлетворяет функциональным требованиям (посетители вправе в произвольном порядке подходить к блюдам).

П.С.: В топике не хватает топик-стартера для оценки достигнутых результатов :)

Dimitry SibiryakovАнатоЛойТеперь таки представьте, что возможность чуваков хаотично метаться между
ресурсами дана нам как требование, то есть свыше (см. стартовый топик).

Тогда достаточно устранить второе условие дедлока и отпускать занятый ресурс прежде чем
вставать в очередь к следующему.

К сожалению, я не понял, что это будет обозначать в моём примере...
Отдавать компот/пирожное барышням, прежде чем идти за пирожным/компотом?
Или возвращать компот/пирожное на полку?
Поясните, пожалуйста.

vadiminfoАнатоЛойП.С.: В топике не хватает топик-стартера для оценки достигнутых результатов :)
Ну, возможно, следует достигнуть еще больших результатов, и чтобы там было именно теоретическое что-то (вопрос то теоретический по мнению ТС). Например, теорема с формальным доказательством. Возможно, нескольких примеров ему все еще недостаочно.
Согласен, все дружно без целей постебались. Разрешите сворачиваться ? .

Dimitry SibiryakovАнатоЛойК сожалению, я не понял, что это будет обозначать в моём примере...

Взял компот, перелил себе на поднос, вернул на полку. Взял пирожное, скопировал себе на
поднос, вернул на полку. Теперь у тебя есть обои, можешь идти к барышням.

В моём примере я не могу "скопировать" пирожное или компот. Выше предложение по реализации нереализуемо.

Dimitry SibiryakovАнатоЛойВ моём примере я не могу "скопировать" пирожное или компот.

Совесть не даёт? Ню-ню...

В таком случае твоё доказательство неизбежности дедлоков звучит как "я не могу иначе". К
счастью, не все люди так религиозны.


У меня впечатление, что мы все о разном.

Dimitry SibiryakovДеадлоки это артефакт реализации конкретной СУБД. Никакой общей теории для них нет.

Дмитрий, в каких известных вам СУБД такого артефакта нет?

Dimitry SibiryakovPS: Как я уже сказал? NumbusDB существует. Она многопользовательская и в ней нет дедлоков.
Но как они этого добились, я рассказать не смогу: при попытке вкурить её архитектуру у
меня срывает крышу.

Дай, плиз, ссылку, на основании которой пытаешься вкурить архитектуру...