Примеры / Иллюстрация алгоритмов без ожидания и без блокировки

Question

Я читал, что ожидание приводит к тому, что все потоки завершаются независимо, а отсутствие блокировки гарантирует завершение программы в целом.Я не мог понять это.Кто-нибудь может привести пример (java), иллюстрирующий это.

РЕДАКТИРОВАТЬ: означает ли без блокировки программу без тупика?

Answer 1

Нет.Lock-free означает программу без блокировок;Кстати, алгоритм wait-free тоже lock-free, но не наоборот.Следовательно, оба являются неблокирующими алгоритмами .

Эта вики запись отлично подходит для понимания механизма без блокировки и без ожидания.

* 1011Пакет java.util.concurrent.atomic является примером программирования lock-free для отдельных переменных.А в Java 7 ConcurrentLinkedQueue является примером реализации wait-free.

Для дальнейшего понимания я хотел бы, чтобы вы прочитали эту статью, Going atomic Брайан Гетц - парень, который написал Параллелизм Java на практике .

Answer 2

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

Ожидание без ожидания является более сильным условием, которое означает, что каждый поток гарантировандобиваться прогресса в течение произвольного периода времени, независимо от времени / порядка выполнения потока;и поэтому мы можем сказать, что потоки заканчиваются независимо.Все программы без ожидания - без блокировок.

Я не знаю ничего из примеров Java, иллюстрирующих это, но могу сказать, что программы без блокировок / без ожидания обычно реализуются без блокировок, используянизкоуровневые примитивы, такие как инструкции CAS.

Answer 3

От более слабого к более сильному условию:

Метод без блокировки , если он гарантирует, что бесконечно часто вызов некоторых методов завершается за конечное числошаги.

Метод является без ожидания , если он гарантирует, что каждый вызов завершает свое выполнение за конечное число шагов.

Очевидно,любая реализация метода без ожидания также не блокируется, но не наоборот.Алгоритмы без блокировки допускают возможность того, что некоторые потоки могут голодать.

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

ПРИМЕЧАНИЕ: Еще более сильное свойство, которое называется " ограниченное ожидание без "что означает: ограничено числом шагов , которое может выполнить вызов метода.