тупик бесплатно против голодания бесплатно - PullRequest
2 голосов
/ 03 декабря 2011

Может ли случиться так, что алгоритм взаимного исключения не поддерживает свойство free-lock free, но поддерживает свободу голодания?

Спасибо

Ответы [ 2 ]

10 голосов
/ 30 сентября 2015

Голодная свобода может быть определена как: Независимо от процесса p , каждый вызов acquire_mutex(), выданный p , в конечном итоге завершается.ИЛИ Любой процесс, пытающийся войти в критическую секцию, в конечном итоге попадет в критическую секцию.

Тупиковая свобода : независимо от времени T , если раньше T один или несколько процессов вызвали операцию acquire_mutex(), и ни один из них не завершил свой вызов во время T , затем наступает время T '> T , в которое процесс, которыйвызвал acquire_mutex(), завершает свой вызов. [Raynal, Параллельное программирование: алгоритмы, принципы и основания] ИЛИ Если процесс пытается войти в критическую секцию, то какой-то процесс, не обязательно такой же, в конечном итоге попадет в критическую секцию.ИЛИ По крайней мере один, всегда побеждает.

Обратите внимание, что тупиковая свобода говорит о том, что некоторые процессы будут прогрессировать, но другие могут застрять (голодать), пытаясь попасть вкритический раздел.Поначалу это звучит странно, но это так: не все потоки застряли, поэтому нет тупика, то есть тупиковой свободы.

С другой стороны, голодная свобода говорит, что каждые процесс, пытающийся попасть в критическую секцию, в конечном итоге сделает это.Не будет никаких процессов, которые когда-либо будут голодать.

Это делает свободу голода гораздо более сильным свойством, чем свобода тупика.

Ответ на ваш вопрос НЕТ.

4 голосов
/ 03 декабря 2011

Нет - каждое разумное определение голода включает тупик.

...