Ответ 1
Центральное различие между ними состоит в том, что сериализуемость является глобальным свойством; свойство всей истории операций/транзакций. Линеаризуемость является локальным свойством; свойство одной операции/транзакции. Другое различие заключается в том, что линеаризуемость включает понятие реального времени, которое сериализуемость не имеет: точка линеаризации операции должна лежать между ее запросами и временем отклика. (См. Тим Харрис: Транзакционная память, 2ед. См. Слайды Херлихи из "Искусство многопроцессорного программирования", раздел "Линеаризуемость", которые доступны здесь, для некоторые примеры и доказательства.
Оба свойства нацелены на одну и ту же цель: последовательная согласованность. Из документа Герлихи:
Большая работа по базам данных и распределенным системам использует сериализуемость как основное условие корректности для параллельных вычислений. В этой модели транзакция представляет собой поток управления, который применяет конечную последовательность примитивных операций к набору объектов, совместно используемым другими транзакциями. История сериализуема, если она эквивалентна той, в которой транзакции появляются последовательно, т.е. Без чередования. Очередность (частичный) приоритета может быть определена на неперекрывающихся парах транзакций очевидным образом. История строго сериализуема, если порядок транзакций в последовательной истории совместим с порядком их приоритета...
... Линеаризуемость можно рассматривать как частный случай строгой сериализации, когда транзакции ограничены состоянием из одной операции, применяемой к одному объекту. Тем не менее, это однооперационное ограничение имеет далеко идущие практические и формальные последствия, давая линеаризуемым вычислениям другой вкус от их сериализуемых аналогов. Непосредственным практическим следствием является то, что механизмы управления concurrency, подходящие для сериализации, как правило, неприемлемы для линеаризуемости, поскольку они вводят ненужные служебные данные и помещают ненужные ограничения на concurrency.
Литература:
-
Харрис, Тим, Джеймс Ларус и Рави Раджвар: Transactional Memory, 2ed. Синтез лекций по компьютерной архитектуре. Morgn and Claypool, 2010. ISBN 9781608452354. URL: http://www.morganclaypool.com/doi/abs/10.2200/S00272ED1V01Y201006CAC011?journalCode=cac
-
Herlihy, Maurice и Jeanette Wing: Линеаризуемость: условие правильности для параллельных объектов. ACM Trans. Prog. Lang. и Sys. Том 12, № 3, июль 1990 г., стр. 463-492. URL http://www.cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
-
Papadimitriou, Christos: Сериализуемость одновременных обновлений баз данных. Journal of ACM Vol 26. No 4. October 1979, pp. 631-653. URL http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-210.pdf
-
Херлихи, Морис и Нир Шавит: Искусство многопроцессорного программирования. Elsevier, 2008. ISBN 978-0-12-370591-4. URL: http://www.elsevier.com/wps/find/bookdescription.cws_home/714091/description#description Пленки PPT для линеаризуемости находятся здесь: http://pub.ist.ac.at/courses/ppc10/slides/Linearizability.pptx
-
Аттия, Хагит и Дженнифер Уэлч: Последовательная последовательность против линеаризуемости. ACM-транзакции на компьютерных системах. 12, № 2, май 1994 г., стр. 91-122. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4969&rep=rep1&type=pdf
Подробнее:
Если вам это действительно интересно, прочитайте статью, в которой были введены определения. Для линеаризуемости Линеаризуемость: условие правильности для параллельных объектов, Herlihy и Wing. Это плотно, но стоит внимания. Обратите внимание, что в сообществе транзакционной памяти программного обеспечения остается открытым вопрос, является ли линеаризуемость правильной целью/свойством.
Сериализуемость относится к результату совокупности операций/ "система", выражаемых как конкретный порядок ( "как если бы выполнение выполнялось в определенном порядке..." ) всех операции. Линеаризуемость - это свойство одного подмножества операций в системе... операция/набор операций линеаризуема, если они отображаются в других операциях, как если бы они происходили в определенный момент времени (в логическом) по отношению к другим. Каноническая статья здесь Papadimitriou, Сериализуемость одновременных обновлений базы данных.
Подумайте о "атомной операции", когда вы думаете о "линеаризуемости". Операции A (множество) линеаризуются, когда они (кажутся) происходят атомарно по отношению к другим частям системы. Общая формулировка "обеспечивает иллюзию, что каждая операция вступает в действие мгновенно между ее вызовом и ответом". Формулировка линеаризуемости обусловлена Herlihy, в которой подчеркивается, что это локальное свойство по сравнению с другими видами свойств последовательной консистенции, таких как "сериализуемость", которые являются глобальными.