Lock-freeとWait-freeアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/12/20 18:32 UTC 版)
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズムは Lock-free である。
- ^ Harris, Tim; Fraser, Keir (26 November 2003). “Language support for lightweight transactions”. ACM SIGPLAN Notices 38 (11): 388. doi:10.1145/949343.949340.
- ^ Harris, Tim; Marlow, S.; Peyton-Jones, S.; Herlihy, M. (June 15–17, 2005). “Composable memory transactions”. Proceedings of the 2005 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '05 : Chicago, Illinois. New York, NY: ACM Press. pp. 48–60. doi:10.1145/1065944.1065952. ISBN 978-1-59593-080-4
- ^ libcds - C++ library of lock-free containers and safe memory reclamation schema
- ^ liblfds - A library of lock-free data structures, written in C
- ^ Concurrency Kit - A C library for non-blocking system design and implementation
- ^ Herb Sutter. “Lock-Free Code: A False Sense of Security”. 2015年9月1日時点のオリジナルよりアーカイブ。2019年9月25日閲覧。
- ^ Herb Sutter. “Writing Lock-Free Code: A Corrected Queue”. 2008年12月5日時点のオリジナルよりアーカイブ。2019年9月25日閲覧。
- ^ Herb Sutter. "Writing a Generalized Concurrent Queue".
- ^ Herb Sutter. "The Trouble With Locks".
- ^ a b Anthony Williams. "Safety: off: How not to shoot yourself in the foot with C++ atomics". 2015. p. 20.
- ^ Herlihy, Maurice P. (1988). “Impossibility and universality results for wait-free synchronization”. Proc. 7th Annual ACM Symp. on Principles of Distributed Computing. pp. 276–290. doi:10.1145/62546.62593. ISBN 0-89791-277-2
- ^ Fich, Faith; Hendler, Danny; Shavit, Nir (2004). “On the inherent weakness of conditional synchronization primitives”. Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC). pp. 80–87. doi:10.1145/1011767.1011780. ISBN 1-58113-802-4
- ^ Kogan, Alex; Petrank, Erez (2011). “Wait-free queues with multiple enqueuers and dequeuers”. Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 223–234. doi:10.1145/1941553.1941585. ISBN 978-1-4503-0119-0
- ^ Michael, Maged; Scott, Michael (1996). “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”. Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC). pp. 267–275. doi:10.1145/248052.248106. ISBN 0-89791-800-2
[続きの解説]
「Lock-freeとWait-freeアルゴリズム」の続きの解説一覧
- 1 Lock-freeとWait-freeアルゴリズムとは
- 2 Lock-freeとWait-freeアルゴリズムの概要
- 3 ロックフリーダム（Lock-freedom）
- 4 オブストラクション・フリーダム（Obstruction-freedom）
- 5 コンペア・アンド・スワップ
- 6 関連項目
固有名詞の分類
| 並行性 | Lock-freeとWait-freeアルゴリズム Communicating Sequential Processes 銀行家のアルゴリズム 競合状態 居眠り床屋問題 |
- Lock-freeとWait-freeアルゴリズムのページへのリンク
