Linearizability (original) (raw)
선형화가능성(Linearizability)은 병행 프로그래밍에서 어떤 연산이 즉시 효과가 나타나는 것처럼 보이는 성질을 가리킨다. 사용자는 구현 세부 사항을 무시해도 좋지만, 성능에는 영향이 있다. 반대로 어떤 연산이 원자적이지 않으면, 병행 연산(들)이 끼치는 추가적이고 돌발적인 영향을 이해하고 대처해야 한다. 그리고 당연히 이런 문제는 재현하기 힘들고 디버그하기 힘들다. 데이터베이스의 ACID 속성에 익숙한 경우에 병행 프로그래밍에서 원자성은 에 관련된 것이며, 직렬화보다 더 강력하다는 점에 주의하자. 데이터베이스에서는 원자성에 관해 다른 정의를 가진다.
| Property | Value |
|---|---|
| dbo:abstract | In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events (event), that may be extended by adding response events such that: 1. * The extended list can be re-expressed as a sequential history (is serializable). 2. * That sequential history is a subset of the original unextended list. Informally, this means that the unmodified list of events is linearizable if and only if its invocations were serializable, but some of the responses of the serial schedule have yet to return. In a concurrent system, processes can access a shared object at the same time. Because multiple processes are accessing a single object, there may arise a situation in which while one process is accessing the object, another process changes its contents. Making a system linearizable is one solution to this problem. In a linearizable system, although operations overlap on a shared object, each operation appears to take place instantaneously. Linearizability is a strong correctness condition, which constrains what outputs are possible when an object is accessed by multiple processes concurrently. It is a safety property which ensures that operations do not complete in an unexpected or unpredictable manner. If a system is linearizable it allows a programmer to reason about the system. (en) 선형화가능성(Linearizability)은 병행 프로그래밍에서 어떤 연산이 즉시 효과가 나타나는 것처럼 보이는 성질을 가리킨다. 사용자는 구현 세부 사항을 무시해도 좋지만, 성능에는 영향이 있다. 반대로 어떤 연산이 원자적이지 않으면, 병행 연산(들)이 끼치는 추가적이고 돌발적인 영향을 이해하고 대처해야 한다. 그리고 당연히 이런 문제는 재현하기 힘들고 디버그하기 힘들다. 데이터베이스의 ACID 속성에 익숙한 경우에 병행 프로그래밍에서 원자성은 에 관련된 것이며, 직렬화보다 더 강력하다는 점에 주의하자. 데이터베이스에서는 원자성에 관해 다른 정의를 가진다. (ko) 並行プログラミングにおいて操作（または操作の集合）は、呼び出しイベントと応答イベント（コールバック）の順序付きリストで構成されており、応答イベントを追加することで以下のように拡張できる場合、線形化可能である。 1. * 拡張されたリストは逐次履歴として再表現することができる（直列化可能である）。 2. * その逐次履歴は元の拡張されていないリストの部分集合である。 これは、非公式には、変更されていないイベントのリストは、その呼び出しが直列化可能であるが、直列スケジュールの応答の一部がまだ戻ってきていない場合に限り、線形化可能であることを意味する。 並行システムではプロセスが同時に共有オブジェクトにアクセスできる。複数のプロセスが1つのオブジェクトにアクセスしているため、あるプロセスがオブジェクトにアクセスしている間に、別のプロセスがオブジェクトの内容を変更するという事態が発生することがある。 この例では線形化可能性の必要性を示している。線形化可能なシステムでは、共有されたオブジェクトに対する操作が重なっても、それぞれの操作は瞬時に行われているように見える。線形化可能性は強力な正当性条件であり、複数のプロセスが同時にオブジェクトにアクセスした場合に、どのような出力が可能であるかを制約する。線形化可能性は、操作が予期せぬ方法で完了しないことを保証する安全特性でもある。システムが線形化可能であれば、プログラマーはシステムについて推論することができる。 (ja) 线性一致性（Linearizability），或称原子一致性或严格一致性指的是程序在执行的历史中在存在可线性化点P的执行模型，这意味着一个操作将在程序的调用和返回之间的某个点P起作用。这里“起作用”的意思是被系统中并发运行的所有其他线程所感知。 (zh) Линеаризу́емость (англ. linearizability) — свойство программной системы, при котором результат любого параллельного выполнения (операций) эквивалентен некоторому последовательному выполнению. Для любого другого потока выполнение линеаризуемой операции является мгновенным: операция либо не начата, либо завершена. Применяется как в многопоточном программировании, так и в распределённых системах. Как было показано, линеаризуемость является локальным и неблокируемым свойством.Локальность означает, что если доказана линеаризуемость операций для нескольких программ в отдельности(или для операций работающих с разными объектами одной программы),то программы вместе (операции вместе) также будут линеаризуемы.В линеаризуемой программе запущенные операции не требуют для своего завершения запуска других операций.Это свойство неблокируемости.Кроме того, линеаризуемость упрощает доказательство свойств программ, которые используют линеаризуемые операции,так как поведение линеаризуемой программы сводится к последовательным выполнениям. Свойство линеаризуемости во многом сходно с такими свойствами как (англ. serializability), атомарность, последовательная согласованность (англ. sequential consistency).В отличие от них, линеаризуемость предполагает наличие спецификации, тогда как эти свойства накладывают ограничения только на саму программу.В некоторых источниках термин атомарность используется как синоним линеаризуемости, в других же означает . Часто под неформальным понятием потоковой безопасности (англ. thread-safety) понимают именно линеаризуемость. Понятие линеаризуемости впервые появилось в статье Херлихи и 1987 года как для систем с объектной организацией общей памяти. В отличие от всех остальных систем, здесь программы не могут напрямую использовать общие переменные, а только через специальные функции-методы (операции). Для этих систем линеаризуемость совпадает со . Задача проверки линеаризуемости — это частный случай задачи функционального тестирования, в которой проверяется, удовлетворяет ли программа функциональным требованиям к ней, заданным в виде спецификации. Но в отличие от общего случая, здесь спецификация требуется только для последовательных выполнений. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Linearlizable_Process.svg?width=300 |
| dbo:wikiPageExternalLink | https://aphyr.com/posts/313-strong-consistency-models%7Cwebsite=aphyr.com%7Cpublisher=Aphyr%7Caccess-date=13 http://repository.cmu.edu/cgi/viewcontent.cgi%3Farticle=2597&context=compsci |
| dbo:wikiPageID | 1204310 (xsd:integer) |
| dbo:wikiPageLength | 24456 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122023445 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:64-bit dbr:Monitor_(synchronization) dbr:SUSv3 dbr:Cyrix_coma_bug dbr:Deadlock dbr:Infinite_loop dbr:Invariant_(computer_science) dbr:Non-blocking_synchronization dbr:Concurrent_programming dbr:Consistency_model dbr:Context_switch dbr:Critical_section dbr:Lock-free_and_wait-free_algorithms dbr:Compare-and-swap dbr:Debug dbr:Burroughs_large_systems dbr:Database_transaction dbr:Load-link/store-conditional dbr:Lock_(computer_science) dbr:32-bit dbr:ACID dbr:ARM_architecture dbr:Fetch-and-add dbr:Central_processing_unit dbr:Process_(computing) dbr:Read-copy-update dbr:Atomicity_(database_systems) dbc:Consistency_models dbr:Interrupt dbr:Jeannette_Wing dbc:Concurrency_control dbc:Transaction_processing dbr:C11_(C_standard_revision) dbr:Spring_Framework dbr:If_and_only_if dbr:Instruction_(computer_science) dbr:Instruction_pipeline dbr:Sequence dbr:CPU_design dbr:C_programming_language dbr:X86_instruction_listings dbr:Maurice_Herlihy dbr:Transactional_memory dbr:Serializability dbr:Time_of_check_to_time_of_use dbr:Test-and-set dbr:Event_(computing) dbr:Read-modify-write dbr:Shared_register dbr:Thread_(computer_science) dbr:Uniprocessor dbr:Denial_of_service_attack dbr:File:Linearlizable_Process.svg |
| dbp:date | November 2018 (en) |
| dbp:dupe | atomicity (en) serializability (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:Cite_web dbt:Main dbt:More_footnotes dbt:Reflist dbt:Relevance_inline dbt:Duplication |
| dct:subject | dbc:Consistency_models dbc:Concurrency_control dbc:Transaction_processing |
| rdf:type | yago:WikicatConsistencyModels yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| rdfs:comment | 선형화가능성(Linearizability)은 병행 프로그래밍에서 어떤 연산이 즉시 효과가 나타나는 것처럼 보이는 성질을 가리킨다. 사용자는 구현 세부 사항을 무시해도 좋지만, 성능에는 영향이 있다. 반대로 어떤 연산이 원자적이지 않으면, 병행 연산(들)이 끼치는 추가적이고 돌발적인 영향을 이해하고 대처해야 한다. 그리고 당연히 이런 문제는 재현하기 힘들고 디버그하기 힘들다. 데이터베이스의 ACID 속성에 익숙한 경우에 병행 프로그래밍에서 원자성은 에 관련된 것이며, 직렬화보다 더 강력하다는 점에 주의하자. 데이터베이스에서는 원자성에 관해 다른 정의를 가진다. (ko) 线性一致性（Linearizability），或称原子一致性或严格一致性指的是程序在执行的历史中在存在可线性化点P的执行模型，这意味着一个操作将在程序的调用和返回之间的某个点P起作用。这里“起作用”的意思是被系统中并发运行的所有其他线程所感知。 (zh) In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events (event), that may be extended by adding response events such that: 1. * The extended list can be re-expressed as a sequential history (is serializable). 2. * That sequential history is a subset of the original unextended list. Informally, this means that the unmodified list of events is linearizable if and only if its invocations were serializable, but some of the responses of the serial schedule have yet to return. (en) 並行プログラミングにおいて操作（または操作の集合）は、呼び出しイベントと応答イベント（コールバック）の順序付きリストで構成されており、応答イベントを追加することで以下のように拡張できる場合、線形化可能である。 1. * 拡張されたリストは逐次履歴として再表現することができる（直列化可能である）。 2. * その逐次履歴は元の拡張されていないリストの部分集合である。 これは、非公式には、変更されていないイベントのリストは、その呼び出しが直列化可能であるが、直列スケジュールの応答の一部がまだ戻ってきていない場合に限り、線形化可能であることを意味する。 並行システムではプロセスが同時に共有オブジェクトにアクセスできる。複数のプロセスが1つのオブジェクトにアクセスしているため、あるプロセスがオブジェクトにアクセスしている間に、別のプロセスがオブジェクトの内容を変更するという事態が発生することがある。 (ja) Линеаризу́емость (англ. linearizability) — свойство программной системы, при котором результат любого параллельного выполнения (операций) эквивалентен некоторому последовательному выполнению. Для любого другого потока выполнение линеаризуемой операции является мгновенным: операция либо не начата, либо завершена. Применяется как в многопоточном программировании, так и в распределённых системах. Часто под неформальным понятием потоковой безопасности (англ. thread-safety) понимают именно линеаризуемость. (ru) |
| rdfs:label | Linearizability (en) 선형화가능성 (ko) 線形化可能性 (ja) Линеаризуемость (ru) 线性一致性 (zh) |
| owl:sameAs | freebase:Linearizability yago-res:Linearizability wikidata:Linearizability dbpedia-fi:Linearizability dbpedia-ja:Linearizability dbpedia-ko:Linearizability dbpedia-ru:Linearizability dbpedia-zh:Linearizability https://global.dbpedia.org/id/4hr9F |
| prov:wasDerivedFrom | wikipedia-en:Linearizability?oldid=1122023445&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Linearlizable_Process.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Linearizability |
| is dbo:wikiPageRedirects of | dbr:Indivisibility_(programming) dbr:Atomic_operation dbr:Atomicity_(programming) dbr:Immediate_consistency dbr:Uninterruptibility_(programming) dbr:Linearizable dbr:Indivisible_operation dbr:Atomic_(computer_science) dbr:Atomic_action dbr:Atomic_actions dbr:Atomic_instruction dbr:Atomic_operations dbr:Atomic_operations_(computing) dbr:Atomic_primitive |
| is dbo:wikiPageWikiLink of | dbr:Atomics dbr:Deadlock dbr:Indivisibility_(programming) dbr:Thread_safety dbr:Processor_consistency dbr:Time-of-check_to_time-of-use dbr:Cosmos_DB dbr:Optimistic_concurrency_control dbr:Shared_snapshot_objects dbr:Concurrent_data_structure dbr:Consistency_model dbr:Linux_kernel dbr:Load_balancing_(computing) dbr:Atomic_operation dbr:Sequential_consistency dbr:Mutual_exclusion dbr:Hash_array_mapped_trie dbr:Load-link/store-conditional dbr:ARM_architecture_family dbr:ECMAScript dbr:Amo dbr:Causal_consistency dbr:Atomicity_(database_systems) dbr:Atomicity_(programming) dbr:Tagged_pointer dbr:Array_Based_Queuing_Locks dbr:Atom_(programming_language) dbr:ANSI_C dbr:APL_syntax_and_symbols dbr:Java_concurrency dbr:Immediate_consistency dbr:Read–modify–write dbr:Regular_semantics dbr:C_standard_library dbr:OpenGL dbr:OpenMP dbr:Race_condition dbr:Wide-area_damping_control dbr:Transactional_memory dbr:Serializability dbr:Eventual_consistency dbr:Uninterruptibility_(programming) dbr:Non-blocking_algorithm dbr:Shared_register dbr:Linearizable dbr:Indivisible_operation dbr:Atomic_(computer_science) dbr:Atomic_action dbr:Atomic_actions dbr:Atomic_instruction dbr:Atomic_operations dbr:Atomic_operations_(computing) dbr:Atomic_primitive |
| is foaf:primaryTopic of | wikipedia-en:Linearizability |
