Как определить, возникнет ли тупик в этой системе? - PullRequest
0 голосов
/ 23 февраля 2011

N процессов совместно используют M единиц ресурса, которые можно зарезервировать и выпускать только по одной за раз.Максимальная потребность каждого процесса не превышает M, а сумма всех максимальных потребностей меньше, чем M + N.Может ли произойти тупик в системе?

Ответы [ 2 ]

1 голос
/ 23 февраля 2011

описываемая вами система выглядит как семафоры

о вашем последнем вопросе: ДА.Ты всегда мог зайти в тупик;если вы не понимаете, как, спросите молодого / позорного / мотивированного / девиантного разработчика.

Один хороший способ сделать хороший;иметь странные правила блокировки / освобождения ресурсов.Например, если процессу требуется М ресурсов для выполнения задачи, он может сразу заблокировать половину из них, а затем ждать, пока другая половина станет доступной, прежде чем что-либо делать.

Я предполагаю, что он никогда не сдастся, пока не получит свои М драгоценные ресурсы, и не отпустит их все, как только задача будет выполнена.

Один процесс не вызовет особых проблем, но некоторые вызовут это, поскольку они заблокируют более M общих ресурсов и потребуют больше из них для выхода из этого замороженного состояния.

0 голосов
/ 17 декабря 2014

Надеюсь, вы получили ответ.Отвечая на этот вопрос для других посетителей.

Ответ таков: в системе не возникнет тупика .

Доказательство приведено на рисунке ниже.

Изображение взято с http://alumni.cs.ucr.edu/~choua/school/cs153/Solution%20Manual.pdf на стр. 31

...