Non-blocking algorithm (original) (raw)
Nicht-blockierende Synchronisation (englisch non-blocking oder auch lock-free synchronization) ist eine Technik in der Informatik, um parallele Prozesse zu synchronisieren, ohne dabei bestimmte Programmabschnitte sperren zu müssen. Insbesondere dient sie zur Implementierung von nicht-blockierenden Datenstrukturen in parallelen Systemen.
| Property | Value |
|---|---|
| dbo:abstract | الخورزميات غير المسدودة (non-blocking algorithm) في مجال الحوسبة المتوازية هو نوع من الخوارزمية تضمن للخيوط التي تتنافس على مورد مشترك عدم الدخول في حالة استبعاد التشارك. الخوارزمية غير المسدودة تعتمد إقفال-تحرير إذا ضمن تقدم النظام بكامله، وتعتمد انتظار-تحرير إذا ضمن لكل خيط التقدم. استعملت أدبيات الحوسبة المتوازية في مطلع القرن 21 تسمية «غير المسدودة» كمرادف لـ إقفال-تحرير. ومع ذلك، ومنذ عام 2003، انحصر هذا المصطلح لوصف فقط لتفادي التفاعلات الموصلة للانسداد مع جدولة وقائية. في الاستعمال الحديث، تكون خوارزمية غير المسدودة إذا كان تعليق خيط واحد أو أكثر لن يوقف التقدم المحتمل للخيوط المتبقية. فهي مصممة لتجنب طلب مقطع حرج. في كثير من الأحيان، هذه الخوارزميات تسمح لمهام متعددة بإحراز تقدم بشأن مشكل ما بدون عرقلة فيما بينها. بالنسبة لبعض العمليات، وهذه الخوارزميات توفر بديل لآليات الاقفال. (ar) Nicht-blockierende Synchronisation (englisch non-blocking oder auch lock-free synchronization) ist eine Technik in der Informatik, um parallele Prozesse zu synchronisieren, ohne dabei bestimmte Programmabschnitte sperren zu müssen. Insbesondere dient sie zur Implementierung von nicht-blockierenden Datenstrukturen in parallelen Systemen. (de) In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003. The word "non-blocking" was traditionally used to describe telecommunications networks that could route a connection through a set of relays "without having to re-arrange existing calls" (see Clos network). Also, if the telephone exchange "is not defective, it can always make the connection" (see nonblocking minimal spanning switch). (en) Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズムは Lock-free である。 (ja) Synchronizacja nieblokująca - jedna z metod synchronizacji procesów wielowątkowych, która zapewnia, że w każdej chwili co najmniej jeden z działających wątków postępuje z pracą. (pl) Неблокирующая синхронизация — подход в параллельном программировании на симметрично-многопроцессорных системах, в котором отходят от традиционных примитивов блокировки, таких, как семафоры, мьютексы и события. Разделение доступа между потоками идёт за счёт атомарных операций и специальных, разработанных под конкретную задачу, механизмов блокировки. Преимущество неблокирующих алгоритмов — в лучшей масштабируемости по количеству процессоров. К тому же, если ОС прервёт один из потоков фоновой задачей, остальные выполнят свою работу, не простаивая, а то и возьмут невыполненную работу на себя. (ru) Алгоритм без блокування (англ. Non-blocking algorithm) — підхід в паралельному програмуванні на симетрично-багатопроцесорних системах, що проповідує відмову від традиційних примітивів блокування, таких, як семафори, м'ютекси і події. Розподіл доступів між потоками відбувається за рахунок атомарних операцій і спеціально розроблених під конкретну задачу механізмів блокування. Перевага алгоритмів без блокування в кращій масштабованості за кількістю процесорів. До того ж, якщо ОС перерве один з потоків фонового процесу, інші, як мінімум, виконають свою роботу без простою. Як максимум — візьмуть невиконану роботу на себе. (uk) |
| dbo:wikiPageExternalLink | http://preshing.com/20120612/an-introduction-to-lock-free-programming/ http://tutorials.jenkov.com/java-concurrency/non-blocking-algorithms.html |
| dbo:wikiPageID | 554867 (xsd:integer) |
| dbo:wikiPageLength | 18683 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1089089074 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Pre-emptive_multitasking dbr:Producer–consumer_problem dbr:Memory_barrier dbr:Algorithm dbc:Synchronization dbr:Deadlock dbr:Interrupt_handler dbr:Priority_inversion dbr:Telecommunications_network dbr:Consistency_model dbr:Critical_section dbr:Erez_Petrank dbc:Concurrency_control_algorithms dbr:Livelock dbr:Clos_network dbr:Compare-and-swap dbr:Computer_science dbr:Parallel_computing dbr:Semaphore_(programming) dbr:Mutual_exclusion dbr:C++11 dbr:Data_structure dbr:Linearizability dbr:Load-link/store-conditional dbr:Lock_(computer_science) dbr:Multi-core_processor dbr:Read-copy-update dbr:Real-time_computing dbr:Hash_table dbc:Concurrency_control dbr:Java_ConcurrentMap dbr:Thread_(computing) dbr:Stack_(data_structure) dbr:C11_(C_standard_revision) dbr:Circular_buffer dbr:Software_transactional_memory dbr:FIFO_(computing_and_electronics) dbr:Scheduling_(computing) dbr:Liveness dbr:Nonblocking_minimal_spanning_switch dbr:Read-modify-write dbr:Resource_(computer_science) dbr:Resource_starvation dbr:Set_(computer_science) dbr:Queue_(data_structure) |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Distinguish dbt:Main dbt:Reflist dbt:Short_description dbt:Var |
| dcterms:subject | dbc:Synchronization dbc:Concurrency_control_algorithms dbc:Concurrency_control |
| rdf:type | owl:Thing yago:WikicatConcurrencyControlAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | Nicht-blockierende Synchronisation (englisch non-blocking oder auch lock-free synchronization) ist eine Technik in der Informatik, um parallele Prozesse zu synchronisieren, ohne dabei bestimmte Programmabschnitte sperren zu müssen. Insbesondere dient sie zur Implementierung von nicht-blockierenden Datenstrukturen in parallelen Systemen. (de) Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズムは Lock-free である。 (ja) Synchronizacja nieblokująca - jedna z metod synchronizacji procesów wielowątkowych, która zapewnia, że w każdej chwili co najmniej jeden z działających wątków postępuje z pracą. (pl) Неблокирующая синхронизация — подход в параллельном программировании на симметрично-многопроцессорных системах, в котором отходят от традиционных примитивов блокировки, таких, как семафоры, мьютексы и события. Разделение доступа между потоками идёт за счёт атомарных операций и специальных, разработанных под конкретную задачу, механизмов блокировки. Преимущество неблокирующих алгоритмов — в лучшей масштабируемости по количеству процессоров. К тому же, если ОС прервёт один из потоков фоновой задачей, остальные выполнят свою работу, не простаивая, а то и возьмут невыполненную работу на себя. (ru) الخورزميات غير المسدودة (non-blocking algorithm) في مجال الحوسبة المتوازية هو نوع من الخوارزمية تضمن للخيوط التي تتنافس على مورد مشترك عدم الدخول في حالة استبعاد التشارك. الخوارزمية غير المسدودة تعتمد إقفال-تحرير إذا ضمن تقدم النظام بكامله، وتعتمد انتظار-تحرير إذا ضمن لكل خيط التقدم. (ar) In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003. (en) Алгоритм без блокування (англ. Non-blocking algorithm) — підхід в паралельному програмуванні на симетрично-багатопроцесорних системах, що проповідує відмову від традиційних примітивів блокування, таких, як семафори, м'ютекси і події. Розподіл доступів між потоками відбувається за рахунок атомарних операцій і спеціально розроблених під конкретну задачу механізмів блокування. (uk) |
| rdfs:label | خوارزمية غير مسدودة (ar) Nicht-blockierende Synchronisation (de) Lock-freeとWait-freeアルゴリズム (ja) Non-blocking algorithm (en) Synchronizacja nieblokująca (pl) Неблокирующая синхронизация (ru) Неблокуючий алгоритм (uk) |
| owl:differentFrom | dbr:O dbr:Non-blocking_I |
| owl:sameAs | freebase:Non-blocking algorithm yago-res:Non-blocking algorithm wikidata:Non-blocking algorithm dbpedia-ar:Non-blocking algorithm dbpedia-de:Non-blocking algorithm dbpedia-fa:Non-blocking algorithm dbpedia-he:Non-blocking algorithm dbpedia-ja:Non-blocking algorithm dbpedia-pl:Non-blocking algorithm dbpedia-ru:Non-blocking algorithm dbpedia-uk:Non-blocking algorithm https://global.dbpedia.org/id/uJzQ |
| prov:wasDerivedFrom | wikipedia-en:Non-blocking_algorithm?oldid=1089089074&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Non-blocking_algorithm |
| is dbo:wikiPageRedirects of | dbr:Non-blocking_data_structure dbr:Non-blocking_data_structures dbr:Non-blocking_synchronisation dbr:Non-blocking_synchronization dbr:Lock-free_and_wait-free_algorithms dbr:Wait-free dbr:Wait-free_algorithm dbr:Wait-free_algorithms dbr:Wait_free dbr:Wait_free_algorithm dbr:Wait_free_algorithms dbr:Lock-Free_Programming dbr:Lock-free dbr:Lock-free_algorithm dbr:Lock-free_algorithms dbr:Lock-free_data_structures dbr:Lock_free dbr:Lock_free_algorithm dbr:Lock_free_algorithms |
| is dbo:wikiPageWikiLink of | dbr:Non-blocking_data_structure dbr:Non-blocking_data_structures dbr:Non-blocking_synchronisation dbr:Relativistic_programming dbr:Priority_inversion dbr:Concurrent_computing dbr:Non-blocking_synchronization dbr:Shared_snapshot_objects dbr:Monte_Carlo_tree_search dbr:Concurrency_control dbr:Concurrent_data_structure dbr:Consensus_(computer_science) dbr:Work_stealing dbr:Linux_kernel dbr:Lock-free_and_wait-free_algorithms dbr:Communicating_sequential_processes dbr:Webcron dbr:Hazard_pointer dbr:Dijkstra_Prize dbr:Discrete-event_simulation dbr:Read-copy-update dbr:Blocking_(computing) dbr:Thread_(computing) dbr:X10_(programming_language) dbr:Panagiota_Fatourou dbr:Skip_list dbr:Wait-free dbr:Wait-free_algorithm dbr:Wait-free_algorithms dbr:Wait_free dbr:Wait_free_algorithm dbr:Wait_free_algorithms dbr:Lock-Free_Programming dbr:Lock-free dbr:Lock-free_algorithm dbr:Lock-free_algorithms dbr:Lock-free_data_structures dbr:Lock_free dbr:Lock_free_algorithm dbr:Lock_free_algorithms |
| is foaf:primaryTopic of | wikipedia-en:Non-blocking_algorithm |