определение без ожидания (имеется в виду параллельное программирование)

Question

В статье Мориса Херлихи "Синхронизация без ожидания" он определяет без ожидания:

"Реализация параллельного объекта данных без ожидания - это та, которая гарантирует что любой процесс может завершить любую операцию за конечное число шагов, независимо скорость выполнения на других процессах. " www.cs.brown.edu / ~ миль / ч / Herlihy91 / P124-herlihy.pdf

Давайте возьмем одну операцию из вселенной.

(1) Означает ли определение: «Каждый процесс завершает определенную операцию, выполняющуюся за одно и то же конечное число n шагов».?

(2) Или это означает: «Каждый процесс завершает определенную операцию op за любое конечное число шагов. Чтобы процесс мог завершить операцию за k шагов, другой процесс за j шагов, где k! = J.»?

Просто прочитав определение, я понял бы значение (2). Однако это не имеет смысла для меня, так как процесс, выполняющий op за k шагов, а другой раз за k + m шагов, соответствует определению, но m шагов может быть циклом ожидания. Если значение (2) верно, кто-нибудь может объяснить мне, почему это описывает без ожидания?

В отличие от (2) значение (1) будет гарантировать, что операция выполняется за то же количество шагов k. Таким образом, не может быть никаких дополнительных шагов m, которые необходимы, например, в цикле ожидания.

Какое значение правильно и почему?

Большое спасибо,

сема

Answer 1

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

Я понимаю, что «без ожидания» означает, что для достижения прогресса не требуется, чтобы какой-либо участник ждал завершения другого участника. Если такое ожидание было необходимо, если один участник зависает или работает медленно, другие участники страдают аналогичным образом.

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

Вместо того, чтобы сосредоточиться на «ожидании своей очереди, чтобы действовать», подход без ожидания поощряет «пытаться помочь», признавая, что другие могут также пытаться помочь одновременно. Каждый участник должен знать, как определить успех, когда повторить попытку и когда сдаться, будучи уверенным, что попытка не удалась только потому, что кто-то другой вошел туда первым. Пока работа выполнена, не имеет значения, какой поток ее выполнил.

Answer 2

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

Я не уверен, что означает «op» в этом контексте, но обычно, когда у вас многопоточная программа, потоки могут ждать, пока что-то сделают друг друга.

Пример: поток имеет блокировку, и другие потоки ожидают освобождения этой блокировки, пока они не смогут работать.

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

Другой пример: есть несколько потоков, каждый из которых пытается CAS по одному и тому же адресу

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

Answer 3

Ответ означает определение (2). Учтите, что цикл ожидания может никогда не завершиться, если ожидающий процесс выполняется бесконечно: « независимо от скорости выполнения других процессов ».

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

Answer 4

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