| dbpprop:abstract
|
- In computer science, non-blocking synchronization ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress; wait-free if there is also guaranteed per-thread progress. Literature up to the turn of the 21st century used "non-blocking" synonymously with lock-free. However, since 2003, the term has been weakened to only prevent progress-blocking interactions with a preemptive scheduler. In modern usage, therefore, an algorithm is non-blocking if the suspension of one or more threads will not stop the potential progress of the remaining threads. They are designed to avoid requiring a critical section. Often, these algorithms allow multiple processes to make progress on a problem without ever blocking each other. For some operations, these algorithms provide an alternative to locking mechanisms.
- Nicht-blockierende Synchronisation (engl. 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.
- Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけて保護するアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。通常ロックを所有するスレッドは、コンテキストスイッチが発生した時点で、全体の進行を阻止することがあるので、Lock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブが使われていないということになる。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。全てのアルゴリズムを Lock-free にすることが出来るが、一部しか Wait-free にできない。Wait-free なアルゴリズムは Lock-free である。
- W tradycyjnym podejściu do programowania wielowątkowego używa się blokad, które wspomagają synchroniczny dostęp do zasobów dzielonych. Elementy takie jak Mutex, semafory, czy sekcje krytyczne są mechanizmami, które pozwalają programiście zapewnić, że określone fragmenty kodu nie będą wykonywane jednocześnie, gdyż w takim wypadku mogłoby to naruszyć strukturę pamięci współdzielonej. Jeśli jeden wątek zamierza nałożyć blokadę, która aktualnie jest już założona przez inny wątek, będzie on zablokowany do momentu zwolnienia tej blokady. Blokowanie wątków jest niepożądane z wielu powodów. Oczywistym jest fakt, że gdy jakiś wątek jest zablokowany, wówczas nie może on wykonywać nic innego. Jeśli taki zablokowany wątek ma do wykonania zadania o wysokim priorytecie, wstrzymywanie go jest wysoce niepożądane. Inne problemy wynikające z blokowania wątków nie są już tak oczywiste. Niektóre interakcje pomiędzy blokadami mogą prowadzić do błędów, takich jak zakleszczenia, zagłodzenia procesów czy inwersje priorytetów. Algorytmy synchronizacji nieblokującej są również bezpieczne do stosowania w procedurach obsługi przerywań (ang. interrupt handlers): nawet gdy wywłaszczony wątek nie może być dokończony, przetwarzanie jest dalej możliwe bez niego. Inaczej jest w globalnych strukturach danych, chronionych przez wzajemne wykluczenie, które nie mogą zostać osiągnięte, ten wywłaszczony wątek może być tym trzymającym blokadę. Synchronizacja nieblokująca ma potencjał do przeciwdziałania inwersji priorytetów, gdyż żaden wątek nie jest zmuszany do czekania na inny, zawieszony wątek. Jeśli jednak może wystąpić livelock (rodzaj zakleszczenia), wątki muszą czekać na wystąpienie konfliktu, w związku z czym inwersja priorytetów jest ciągle możliwa w zależności od użytego systemu zarządzania konfliktami. Inwersji priorytetów zapobiegają algorytmy wolne od blokad.
|
| rdfs:comment
|
- In computer science, non-blocking synchronization ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress; wait-free if there is also guaranteed per-thread progress. Literature up to the turn of the 21st century used "non-blocking" synonymously with lock-free.
- Nicht-blockierende Synchronisation (engl. 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.
- W tradycyjnym podejściu do programowania wielowątkowego używa się blokad, które wspomagają synchroniczny dostęp do zasobów dzielonych. Elementy takie jak Mutex, semafory, czy sekcje krytyczne są mechanizmami, które pozwalają programiście zapewnić, że określone fragmenty kodu nie będą wykonywane jednocześnie, gdyż w takim wypadku mogłoby to naruszyć strukturę pamięci współdzielonej.
|
![[RDF Data]](/statics/sw-cube.png)
