Computer Laboratory – Systems Research Group – NetOS: Practical lock-free data structures
Introduction Through careful design and implementation it's possible to build data structures that are safe for concurrent use without needing to manage locks or block threads. These non-blocking data structures can increase performance by allowing extra concurrency and can improve robustness by avoiding some of the problems caused by priority inversion in local settings, or machine and link failu
革命の日々！ シーケンスロック その５ volatileがダメな理由
どもども。またまた間隔があいてしまいましたがシーケンスロックな話しの続きです。 前回の記事で坩堝さんから面白い指摘をうけたので今回は予定を変更してvolatileの話をしたいと思います。 retをvolatileにするだけではうまくいかないんですよね？ どういう風になるんだろ． なるほど、たしかに世のＣ言語の参考書を見るとvolatileはある種の最適化を妨げる効果を持つと されています。 これだけ見ると、volatileとつけるだけすべての最適化が無効になってうまく動きそうですね。 しかし、その理屈は微妙におかしいのである 多くの人が「ある種の」という言葉を拡大解釈しているがvolatileは本来スレッド同期に使えるようなシロモノではないのである。 つづきは、続きを読むからご覧ください。 あと、お願い。 今回の話は前提知識がいろいろとあるので、末尾のご参考にあげたURLを読んでから 読ん
Fast reader/writer locks [LWN.net]
The Linux kernel contains a number of primitives for controlling mutual exclusion. Semaphores and spinlocks (in several varieties) have been around for a while, and the read-copy-update mechanism was added in the 2.5 series. Yet another mechanism, called "fast reader/writer locks," has found its way into Andrew Morton's -mm patch set, and appears likely to be forwarded on to Linus soon for inclusi
Scalable Reader-Writer Locks
Scalable Reader-Writer Synchronization for Shared-Memory Multiprocessors Pseudocode from article of the above name, PPoPP '91. John M. Mellor-Crummey and Michael L. Scott. The queue-based locks below perform well in tests on machines with scores of processors. Simple, non-scalable reader-preference lock. For maximum throughput on small machines. Starves writers under continuous reader load. Starva
Scalable Synchronization
Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors Pseudocode from article of the above name, ACM TOCS, February 1991. John M. Mellor-Crummey and Michael L. Scott, with later additions due to (a) Craig, Landin, and Hagersten, and (b) Auslander, Edelsohn, Krieger, Rosenburg, and Wisniewski. All of these algorithms (except for the non-scalable centralized barrier) perform well
Scheduler-Conscious Synchronization
Preemption-Safe and Scheduler-Conscious Busy-Wait Synchronization Algorithms Pseudo-code from article of the above name, ACM TOCS, February 1997. Leonidas I. Kontothanassis, Robert W. Wisniewski, and Michael L. Scott. Preemption-Safe "Handshaking" Queue Lock (Queue-HS) Scheduler-Conscious "Smart Queue" Lock (Smart-Q) Preemption-Safe Ticket Lock (Ticket-PS) Scheduler-Conscious Fair Reader-Writer Lo
Lock-freeとWait-freeアルゴリズム - Wikipedia
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズム
Seqlock - Wikipedia
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (August 2011) (Learn how and when to remove this message) A seqlock (short for sequence lock) is a special locking mechanism used in Linux for supporting fast writes of shared variab
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.rdrop.com/users/paulmck/rclock/
High Performance Synchronization