задержанная ограничительная проверка

Один объект считается линеаризуемым, если

(a) каждый из его методов является атомарным. Представьте их как синхронизированные методы Java, но подробнее ниже.

(b) может быть не более одной ожидающей операции от любого заданного потока / процессора.

(c) операции должны вступить в силу до их возвращения. Недопустимо, чтобы объект ставил их в очередь, чтобы выполнять их лениво.

Теперь, (а) можно ослабить намного больше. Линеаризуемость требует, чтобы эффект этой операции был атомарным. Таким образом, операция добавления в связанном списке без блокировки будет иметь одну точку в своем исполнении («точку линеаризации»), до которой этот элемент не был добавлен, и после которого этот элемент определенно находится. Это лучше, чем получение блокировок. потому что замки могут блокировать бесконечно.

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

И поскольку они вынуждены оказывать влияние когда-то во время вызова метода (стеки должны быть push / pop, множества должны быть добавлены / удалены и т. Д.), Объект может быть рассмотрен с помощью известных методов последовательной спецификации (pre и post). условия и т.д.).

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