ブログトップ 記事一覧 ログイン 無料ブログ開設

理想未来はどうなった? このページをアンテナに追加 RSSフィード Twitter

2010-10-22

Mac OS X 10.7 Lionよりも有名なライオン

Mac OS X 10.7のコードネームはLionと発表がありましたが、
ライオンといえば、こいつの事を忘れていました。





それは・・・!?






みんな大好き、ミスドポン・デ・ライオン


f:id:pcmaster:20091223221818j:image


・・・お呼びでない?



一度思ってしまうと中々忘れられないもので、こんなものまで・・・


f:id:pcmaster:20101023155938j:image



ポン・デ・ライオンに見えてくる・・・


f:id:pcmaster:20101023154134j:image


Back to the Misdo
最近ミスド行っていますか?



ちなみに最近報告してないですが、現在のミスドポイント数は1024ポイント。
1000ポイント超えているので、もう一体ポン・デ・ライオン特殊召喚できます。

関連記事

[ミスタードーナツ]吠えるポン・デ・ライオン(大)降臨!
[ミスタードーナツ]ミスドカードのポイントが1000ポイント貯まった。
[Apple][MacBook Air][Mac OS X][iLife]Back to the Macイベント
[Apple][Mac OS X]Mac OS X 10.7はLion? Appleが10月20日(水)に次期OS発表イベントを開催
[Mac][Mac OS X][思うこと]私がMacを使う理由と、他の人に奨められない理由

コンペア・アンド・スワップ

当たり前だろうと思う事でも、世の中当たり前じゃなかったり、当たり前という基準は各々の判断でしかない。
コンペア・アンド・スワップもそんな当たり前なことの一つです。


お題

預金口座で残高を更新するシステムを作る。
預金口座は複数のATMから同時に振込や引落が行われる可能性がある。

方法

口座の更新は複数のATMから同時に行われる可能性があり、残高を正しく保つには、次のいずれかの方法をとる事になる。

  1. 預入要求、払出要求という操作をキューで管理し、残高の更新は1つのスレッドが行う。
  2. コンペアアンドスワップを使う。

1の方法はシステムが大きくなりますが、考え方としてはシンプルです。
2のコンペア・アンド・スワップが今回説明したい内容で、覚えておくと色々なところで応用がきくかもしれません。

アルゴリズム

コンペア・アンド・スワップを使った更新アルゴリズムは次の通り。

  1. 値を読み出す。
  2. 加算、減算等の計算の処理を行う
  3. コンペアアンドスワップ(もう一度値を読み出し古い値のままであれば2で更新した新しい値に置き換え)を行う。
  4. 3の処理が失敗した場合は、1に戻ってやり直す。

ある意味当たり前の話ですが、古い値と同じときに、新しい値に置き換えるというのが重要です。
古い値と同じということは、他から更新されていないということを示しているからです。


コンペア・アンド・スワップは、アトミックに(=分解できない一つの操作として)行う必要があり、また成功したかどうかの結果を返すことが出来る必要があります。

なぜアトミックに操作できないと不味いかというと、例えば古い値と比較して置き換えれると判断した後に、別のスレッドが値を置き換えたりすると比較の結果が無意味となった上、置き換えられた値を更に上書きすることになり一貫性が保証できないからです。
その為、比較と交換の操作は分解できない1命令として操作する必要があります。

ちなみにコンペア・アンド・スワップをアトミックに操作する命令ですが、マシン語レベルですとx86系の場合、i486以降でcmpxchgという便利な命令があったりします。
SQLならばUPDATEで更新を行う際に、WHERE句でプライマリーキーと古い値で比較して更新を行い、更新された行数が1であれば成功、更新された行数が0であれば失敗と見なすのが良いでしょう。

参考

Lock-freeとWait-freeアルゴリズム - Wikipedia
コンペア・アンド・スワップ - Wikipedia

関連記事

[Linux][bash]bash 履歴の管理
[Linux]メモリオーバーコミット
[Linux][MeCab][PHP]PHPで都道府県、市区町村、町域名以降の住所分割を高速に行う方法
[postfix][php]メールを高速に配信する方法
[postfix]postfixでキューに溜まった特定の送信元、送信先のメールを一括削除する方法