Stackを使ってQueueを作る - くまメモ
有名な話かと思ったら意外と知られていなかったのでメモ。 FILOを使ってFIFOを作るとも言います。StackでQueue作れてもQueueでStackを作る方法が思いつかないので誰か教えて下さい。もしくはこういう学問があったら紹介して頂けると嬉しいです。 簡単な説明としては、2つのStackを用意して、enqueueするときには1つ目にpush()し、dequeueするときには2つ目からpop()するだけ。 ただし2つ目のStackが空の場合は1つ目のスタックが空になるまで2つ目のスタックに移し替える。 template<typename T> class MyQueue { std::stack<T> in, out; MyQueue(){} void enqueue(const T& v) { in.push(v); } T dequeue() { if (out.empty())
2010-12-27
Boostに以前からread-writeロックは実装されていたようですがバグがあったとかで最近の物ではupgrade_lock, upgrade_to_unique_lockにさし変わっています。 ただのロックと比べてパフォーマンスが出やすい上に素性の良い設計だと思うので紹介してみようと思います。 read lock read-lockをする場合はshared_mutexを引数にshared_lockをかけてやればいいです。 #include <boost/thread.hpp> using namespace boost; shared_mutex mutex; void reader(){ shared_lock<shared_mutex> read_lock(mutex); // ここでロック！ // クリティカルセクション } スコープを外れると同時にshared_lockのデスト
ノンブロッキングでマルチリーダーでserializableなSTM戦略 - くまメモ
前回ノンブロッキングなSTMに付いて説明したのですが、トランザクション中での読み出しに関してはあまりに適当な説明しかしていなかったです。 そこをもう少しまともに説明しようと思います。 読み出しトランザクション? 複数の箇所の読み出しをatomicに行う必要があります。 一番簡単な方法は「その値そのもので上書きしてやる」事で値を変えずに所有権を自分に移す事です。 transactional_object<int> *a,*b; const int *commited_a, *commited_b; status_t my_status = new status_t(ACTIVE); retry: transactional_object<int> *old_a = a, *old_b = b; // aを読む if(*(old_a->owner_) == COMMITTED){ commit
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言語の擬似コードで書くと以下のような
non-blockingの意味するところ - くまメモ
海外の文献を読み漁っていると気づくのですが 2003年を境にこの文脈で使われる言葉の定義が変わります。 ↑2003年ごろまでの構図 ↑現在の構図。*1 non-blocking = obstruction-free という理解でもおおよそ間違いではないとは思いますが 論文を読むに当たって non-blocking = ロックを使わないアルゴリズム全般 obstruction-free = 非lock-freeだけどロックだけはしない というニュアンスの違いを感じます。 以後、現在の構図の方を前提に話します。ご注意ください。 まずは3つの分類の違いから wait-free 操作が「他のスレッドの動向に関わらず有限ステップで完了できる」場合、そのアルゴリズムはwait-freeと呼ばれます。starvation-freeと呼んだりもします。 実際には初めからここに分類されるアルゴリズムは多くあ
RAM Cloudについて - くまメモ
RAMCloudというストレージシステムについて調べてみた 公式wiki http://fiz.stanford.edu:8081/display/ramcloud/Home 公式サイト http://www.stanford.edu/~ouster/cgi-bin/projects.php ソース[英語] http://www.stanford.edu/~ouster/cgi-bin/papers/ramcloud.pdf △全体要約 ･全てのデータをRAM上に納めた超低レイテンシ分散ストレージ ･数千台の計算機を10GbEで接続し、5-10μs程度の遅延を実現する"予定" ･データセンターや高負荷Webサーバで利用する前提 ･ギガバイト単価$60ほどで、1000000000ops/sの速度を実現する。(通信機器やラックの代金は含まない) 例として上がっている用途は空港の旅客管理システム
lock-free stackと並行アルゴリズムの区分 - くまメモ
この記事は カーネル／VM Advent Calendar http://atnd.org/events/10701 のために書かれました。 これまで複数回に渡ってlock-freeデータ構造を紹介して来ましたが そもそもの前提を話していなかったり目的も不明だったりと不備だった点があったので 根元から一度おさらいしてみたいと思います。 まずロックを用いる事の欠点から 上図のような構図でロックによる相互排他を行うと様々な問題が発生します。 具体的に言うと排他に成功したスレッドに様々な災難が降りかかります。 主な事例として ↑ロック確保できたのにOSによってプリエンプションされる。 ↑物理メモリに乗ってない仮想メモリにアクセスしてしまった。 ↑キャッシュミスヒットによるメモリ待ち。 そんなに気にするほどのパフォーマンス低下ではないと思うかも知れませんが マルチコアの方向へ舵を切った新世代CPU
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
