Линеаризуемость: различия между версиями

Объект в таких языках, как Java и C++, представляет собой контейнер для данных. Каждый объект предоставляет набор методов, которые являются единственным способом манипулирования внутренним состоянием объекта. У каждого объекта есть класс, который определяет методы, которые он предоставляет, и то, что они делают.

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

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