Прежде всего, обратите внимание, что последовательные истории --- в соответствии с заданной моделью последовательности, такие как линеаризуемость или сериализуемость --- определяются как те, которые удовлетворяют последовательных спецификации объектов по отношению к точкам операции (или метода) [1, 2].
Более конкретно:
последовательная спецификация для объекта представляет собой набор последовательных историй для объекта
где история определяется как:
конечной последовательности события вызова и реагирования методов
, где пара событий вызова и ответа формирует вызов метода, т.е.:
вызова метода в истории H является пара, состоящая из вызова и ответа следующего соответствия в H
Таким образом, в самом деле, линеаризуемость определяется для отдельных операций на отдельных объектах, но определение может также охватывать истории по нескольким объектам [1, 2]. С другой стороны, сериализуемость охватывает истории с несколькими операциями по нескольким объектам по своей сути, поскольку она (обычно) определена в контексте транзакционной обработки, где каждая транзакция может включать несколько операций над несколькими объектами.
Эти две операции, а именно отдельные операции над отдельными объектами и несколько операций над несколькими объектами, могут быть эквивалентны путем определения методов объектов (которые потенциально объединяют несколько объектов), которые определяют соответствующую последовательную спецификацию , в которой все транзакции рассматриваются как методы на некоторых объектах (например, простой пример - очередь очереди/dequeue очереди [1]). Это, в свою очередь, определяет последовательную спецификацию таких объектов и, следовательно, достоверные истории в соответствии с заданными моделями согласованности.
Теперь, если T1 и T2 интерпретируются как потоки, то, действительно, последовательность 1 вызывает операции над одним объектом, тогда как последовательность 2 явно вызывает несколько операций и несколько объектов. Обратите внимание, что в обоих случаях истории могут быть проверены как на линеаризуемость, так и на сериализуемость, тогда как операции чтения и записи могут быть сгруппированы в «семантически» атомные методы, как обсуждалось ранее.
Взаимосвязь между линеаризуемостью и сериализуемостью, сериализуемость - это строго слабая модель согласованности, в которой допустимые истории могут быть эквивалентны исполнению методов в произвольных последовательностях, тогда как линеаризуемость можно рассматривать как эквивалентную строгой сериализуемости (если мы рассматриваем транзакции как методы одного объекта). Обратите внимание, что некоторые авторы начали использовать линеаризуемость в контексте транзакций [3].
[1] The Art of Multiprocessor Programming. Нир Шавит и М. П. Херлихи
[2] Linearizability: A Correctness Condition for Concurrent Objects. М. П. Херлихи и Дж. М. Винг. ACM-транзакции на языках программирования и системах, Vol. 12, № 3, июль 1990 года.
[3] Software Transactional Memory. Нир Шавит и Дэн Туиту. Distrib. Вычи. (1997) 10: 99-116.