ロックフリー性の証明について - くまメモ
http://www.slideshare.net/kumagi/lock-free-safe?next_slideshow=1 とか過去に自分で書いておきながら、その当時の自分の認識が甘かった事もあるのでここに一度書き出しておく。 Lock-Freeは「ロックを使わない事」ではない STMの事をもってしてLock-Freeと呼んでる文脈はいっぱいあるけれど、STMの実装にロックを使う事は一般的だし、それは正しい専門用語で言う所のLock-Freeとは呼ばない。 Lock-Freeとは「どんなスケジューリングが為されようともどれかの操作が進行する」という進行保証(Progress Guarantee)を表している。 スケジューリング？ マルチコアCPUでもシングルコアCPUでも、OSは実行中のプログラムを任意のタイミングで強制的に一時停止させて他のプログラムにCPUリソースを割り当てる事が
Non-blocking STMについて頑張って説明してみる - くまメモ
STMはソフトウェアトランザクショナルメモリの略です。 ↓とりあえずwikipedia http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%95%E3%83%88%E3%82%A6%E3%82%A7%E3%82%A2%E3%83%88%E3%83%A9%E3%83%B3%E3%82%B6%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%83%A1%E3%83%A2%E3%83%AA 日本でSTMの話題を検索すると「楽観的ロックでしょ？」といった発言を見かける事が多く、確かに実用的な手法の多くはロックベースだったりしていますが、正直なところロックベースな手法のSTMはデータベースでのトランザクションと似ているフシがあったりしてデータベースに詳しい人からするとそれほど驚くような手法ではない事が多いのです。その
Lock-free Stack - くまメモ
ではLock-free Stackについて図とプログラムを交えながら説明します。C++ではなくCを使います。 これは複数スレッドからロックによる排他無しで共有できるスタックで、外部には node* top; void push(const T*, node** top); bool pop(T*, node** top); を提供します。*1 このスタックはbottomへと繋がる線形リストをベースとして動作するため、配列ベースのスタックにパフォーマンスで劣ることもあります。*2 その線形リストを構成するノードのデータ構造から見てみましょう。 struct node{ T data; node* next; }; ごく典型的な線形リストのノードと同じです。 道具の紹介 lock-freeデータ構造を構成する場合に頻出のCompare And Swap。 C言語の擬似コードで書くと以下のような
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
