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

Последовательная согласованность [ ] представляет собой более слабое условие корректности, в котором выполняется требование L1, но не L2: вызовы методов должны происходить по одному в некотором последовательном порядке, но неперекрываюмиеся вызовы могут быть переупорядочены. Любая линеаризуемая история является последовательно согласованной, однако обратное неверно. Последовательная согласованность допускает больший параллелизм, но это не локальное свойство: система, состоящая из множества последовательно согласованных объектов, вовсе не обязательно сама является последовательно согласованной.

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

Ни сериализуемость, ни строгая сериализуемость не являются локальными свойствами. Если разные объекты сериализуют транзакции в разном порядке, то не может быть порядка сериализации, общего для всех объектов. Сериализуемость и строгая сериализуемость являются блокирующими свойствами: при определенных обстоятельствах транзакция может быть не в состоянии завершить ожидающий метод, не нарушая сериализуемости. Если несколько транзакций блокируют друг друга, возникает ситуация взаимоблокировки. Для таких транзакций необходимо выполнить откат и перезапуск, что подразумевает наличие дополнительных механизмов для этой цели.

Понятие линеаризуемости было предложено Херлихи и Винг [3], последовательной согласованности – Лампортом [4], а сериализуемости Эсвараном и коллегами [1].