8/31 (土)
x86/x64最適化勉強会6
x86/x64最適化勉強会6に行ってきた。
Pthread mutex と他の同期オブジェクトの違い
Pthread mutex と他の同期オブジェクトには使い分けの作法があると自分は信じていたのだが、どうも一般の常識ではないらしい。
私の認識ではユーザランドでマルチスレッドプログラムを書く場合に使える同期オブジェクトにはざっくり3種類のカテゴリがある。
- スピンロック(spin lock)
- Pthread mutex
- その他の同期オブジェクト(POSIX セマフォ、Pthread reader-writer lock、Pthread 条件変数、IPC セマフォ)
1. と 2. & 3. の違いは簡単で、競合状態になった時に OS に CPU 実行権を渡して待機状態になるかどうかだ。 一方、2. と 3. は動作のセマンティクスが少し違うというだけで、例えば値が 1 のセマフォは pthread mutex と等価じゃないかと思える。
しかし pthread mutex を単なる同期オブジェクトと考えると痛い目にあう。 2. と 3. は以下のように使い分けるべし。
- 排他区間が長時間動くようなら pthread mutex は使わずに、3. の同期オブジェクトを使う。
- スレッドの競合が頻繁に起きるようなら pthread mutex は使わずに、3. の同期オブジェクトを使う。
- read/write や recv/send のようなシステムコールを呼び出すなら pthread mutex は使わずに、3. の同期オブジェクトを使う。
ようするにメモリを読んだり書いたりするだけで、極めて短時間で走行が完了し、排他区間といいつつスレッド競合は滅多に起きない箇所にしか pthread mutex は使えない。
printf や fprintf を挟むのはアウト。
malloc や sprintf はまあ許容する。
自分も Pthread ライブラリの教科書を読み漁ったという訳ではなくどうしてこういう作法に辿りついたのか思い出せないのだが、なんでそうしなくてはならないかつらつら書いておく。
以降、Pthread mutex をただの mutex と略す。
Pthread mutex は fairness の規定がない
Mutex は fairness の規定が全然ない同期オブジェクトである。 ロックの fairness は過去の日記に何度か書いているが(2004年4月13日、2007年9月10日)、ざっくり言えば同期オブジェクトの fairness は、待機状態のスレッドが出た後に「アンロック」された場合に、どのスレッドが同期オブジェクトの所有権と CPU 実行権を握るかというポリシーのこと。
- Fair なロックは、先にロックを試みたスレッドが後から来たスレッドよりも先にロック所有権を獲得できる。
- Unfair なロックは後からロックを試みたスレッドが先に待っているスレッドを追い越してロック所有権を獲得できる。つまり順番抜かしを許す。
Mutex 以外の同期オブジェクトは、アンロック時に待機状態のスレッドがどうなるかある程度記述されている。
例えば POSIX セマフォの場合は sema_post すると If the value of the semaphore resulting from this operation is zero, then one of the threads blocked waiting for the semaphore shall be allowed to return successfully from its call to sem_wait().
とある。
POSIX セマフォはアンロックした場合、sem_wait で待機状態のスレッドのいずれかにその同期オブジェクトの所有権が渡ると読める。
sem_wait の実行順を守ってないが一応ルールがある。
Pthread reader-writer ロックのpthread_rwlock_unlockや、IPC セマフォのsemopにも規定がある。
しかし pthread_mutex_unlock は If there are threads blocked on the mutex object referenced by mutex when pthread_mutex_unlock() is called, resulting in the mutex becoming available, the scheduling policy shall determine which thread shall acquire the mutex.
とある。
pthread_mutex_unlock は待機中のスレッドに所有権を渡すのではなく、ただ the mutex becoming available
、mutex を誰も所有していない状態にして、後に OS のスケジューラに任せるよ、と書いてある。
OS 依存、ライブラリ依存だ。
Pthread mutex が unfair だと問題か？
アンフェアな同期オブジェクトを使った排他処理を行うと思わぬ落とし穴に落ちることがある。
例えば mutex で排他処理する資源に、スレッド A、スレッド B、スレッド C アクセスし、同時に pthread_mutex_lock をとったとする。
スレッド A が打ち勝ち mutex の所有権を獲得し、排他処理に入り、排他区間から出て pthread_mutex_unlock する。
しかし pthread_mutex_unlock は待機中のスレッド B やスレッド C を起こすとは限らないので、スレッド A は再び排他区間に入り pthread_mutex_lock を実行する。
Mutex の所有権は自由なのでスレッド A は再度ロックを成功させ、pthread_mutex_unlock し、三度 pthread_mutex_lock を成功させ、、、というループをずっと繰り返すかも知れない。
スレッド B やスレッド C は何時までたっても起き上がれない。
もちろん mutex をどう実装するかは OS やライブラリに依存しているので fair な実装が選択されるかもしれない。 しかし同じプログラムを別の OS に持ってゆくと動かなくなることが考えられる。 あるいはもっと酷くて、同じ OS でバージョンによって mutex が fairness が変わって、過去に動いていたプログラムが動かなくなることがある。
実際に Solaris でそういうことが起きて、mutex の fairness の変更を補正するためにユーザランドプログラムの中に長時間走行しているスレッドはプライオリティを落とす仕組みを自前で入れたとか言う話も聞いたことがある。 南無三。
Pthread mutex は Cancellation Point じゃない
その他にも mutex は特別扱いを受けている傍証に、mutex は取り消しポイント(cancellation point)ではないというのもある。
停止させたいスレッドを指定して pthread_cancel を実行すると、ターゲットスレッドが cancellation point に到達すると停止する。
Cancellation point はまずプログラムの中に明示的に配置する pthread_testcancel だが、システム関数の中で特にスレッドをブロックしてしまうようなものが必須 cancellation point、あるいは cancellation point の可能性のあるものに選ばれている。
同期オブジェクトのほとんどはリストに載っているのだが、mutex 系の API は選ばれていない。
Mutex が cancellation point でないのは mutex はローレベルの同期オブジェクトで他の同期オブジェクトを作る部品として使われることが多いので排除されている可能性もあるが、mutex の排他区間は一気通貫で駆け抜けて停止しないものなのだ。
Linux の場合は…
Mutex の動作は実際は OS とライブラリによって変わる。
Linux は mutex も POSIX セマフォも pthread reader-writer ロックも内部では futex を使っているから、ほとんど同じ挙動をするようだ。
全般に同期オブジェクトは fair な方向に向かっているし、Linux だけを使っている分は気にしなくてもいいのかしらん。
もう Linux 以外使わないだろう。
Solaris とか、AIX とか、HP-UX とか。
8/29 (木)
中原区図書館
午前中いろいろ用事があったので会社は有休。 午後から暇になったので、武蔵小杉の駅ビルに移設した中原区図書館に初めて行ってみた。
まず設備が大変にモダンなのに驚く。 利用者がバーコードリーダーを通して無人で借り出しするシステムだとか、端末で座席の確保とか電子書籍化されている。
田舎の図書館というとハードカバーばかりだったが岩波文庫のような文庫本が大量にある。 自分が読みたい本があるかはボチボチ探したい。
ハリー・ポッター展＠森アーツセンターギャラリー
六本木ヒルズ内の森アーツセンターギャラリーでやっている「ハリー・ポッター展」(公式)を観てきた。
この展示会は日時指定のチケットの前売り制になっていて、当日券は前売り券の販売状況に応じて発売される。 当初は前売り券が完売の状況だったのだが、すでに2ヶ月以上経つ平日ということもあって当日券が購入できた。 とはいえゲキ混み状況。 前の客で展示物が見えない。
結局、私はハリー・ポッターをあまり知らんので、衣装とか見てもふ〜んという感じでした。 私はなんでこれを観にいこうと思ったのだろう。
8/27 (火)
C/C++ 言語のコメントを削除する正規表現
適当なスクリプト言語で C 言語のソースコードの中で使われているシンボルを抽出しようと試行錯誤する。
例えば send、recv が使われているとか、errno が参照されているかとかの情報が集めたい。
真面目にやるなら C 言語や C++ 言語のパーサーが必要なのだが、とりあえずソースコードからコメントと文字リテラルを除去した後に識別子に見えるものを拾ってゆけばいい。
しかし C 言語のコメントは /* */ と // の 2 種類があり、除去するのは少し面倒だ。
先人の知恵を拝借しようとネットを見ていると perlfaq6 の Regular Expressions の中にそのものずばりの項目があった。 日本語訳のページもある。
C ソースコードの行を改行を \n にして全てまとめて $contents に入れた場合、以下の正規表現一つでコメントを削除できるようだ。
$contents =~ s#/\*[^*]*\*+([^/*][^*]*\*+)*/|//([^\\]|[^\n][\n]?)*?\n|("(\\.|[^"\\])*"|'(\\.|[^'\\])*'|.[^/"'\\]*)#defined $3 ? $3 : " "#gse;
正規表現がどのように動いているのかはサパ〜リだが、期待通りに動作している。
追記：9/11
ちゃんと読んでみよう。
まず $contents =~ s#PATTERN#REPLACE#gse という形をしている。
これは $contents =~ s/PATTERN/REPLACE/gse の / を別の文字 # に置き換えただけ。
先頭の s は PATTERN を REPLACE に置換することを指示している。
最後の gse のオプションの意味は、
| オプション | 意味 |
|---|---|
| g | 繰り返してマッチするようになる |
| s | 複数行を1つの文字列に押し込めたものとして扱い . が改行(\n)にもマッチするようにする |
| e | 式の右側の評価を行う |
最後の e オプションによって、defined $3 ? $3 : " " が生きてくる。
defined は変数が定義されているかどうかを判断するので、$3 が定義されていれば(存在すれば)そのまま、定義されていなければ空白文字へ置換 " " になる。
/* 〜 */ 型のコメント部分が $1 にマッチし、// 型のコメント部分が $2 にマッチし、コメントでない部分が $3 マッチする。
その上で、$3 だけを残して出力するというものらしい。
追記：9/12
Python で記述。 re モジュールの sub 関数を使う。 Perl との
- sub 関数が
s/の置換に相当する。 - さらに sub 関数は g オプションの動作がデフォルトである。
- Perl で指定した e オプションは、Python では置換文字の代わりに自分で定義した
replace_funcで実現可能。replace_funcの引数mには MatchObject のインスタンスが渡すので必要な変換をして文字列を返す。 - Perl で指定した s オプションは、Python では (?s) で設定する DOTALL モードが等価な機能を提供する。
import os
import re
target_file ="foo.c"
def concat_all_lines(target_file):
contents = ""
for line in open(target_file, 'r'):
contents += line
return contents
def replace_func(m):
tuple = m.groups()
if (tuple[2] != None):
return tuple[2]
return " ";
contents = concat_all_lines(target_file)
print re.sub(r"(?s)/\*[^*]*\*+([^/*][^*]*\*+)*/|//([^\\]|[^\n][\n]?)*?\n|(\"(\\.|[^\"\\])*\"|'(\\.|[^'\\])*'|.[^/\"'\\]*)",
replace_func, contents)
8/17 (土)
川崎に帰還
新幹線で新山口から新横浜へ。 途中は新大阪まで立ちっぱなしだったが、新大阪で降りる人が少ないのに業を煮やして下車したら、運よく10分後に新大阪始発ののぞみが出ていて着座できた。
下車しなかったら凄い混雑の車両の中に巻き込まれていたわけだが、駅が「隣の電車は空いています」というアナウンスは出せないものなのだろうか？ アナウンスを出した時に何人降りるのか予想ができないので難しいかしらん。
8/13 (火)
景清洞
畔上氏と秋吉台にある三大鍾乳洞の一つ景清洞(秋吉台・秋芳洞観光サイト、Wikipedia)に。
景清洞の近くはキャンプ地になっていて、テントを張って野営や BBQ ができる。 35 ℃近い真夏日だというに、たくさんの家族連れが賑わっている。 みんな正気か？
 |
 |
 |
 |
景清洞は秋芳洞、大正洞と並ぶ、秋吉台の三大鍾乳洞だ。 大正洞は2008年1月5日に行ってみたけど上下に高低のある立体的な鍾乳洞だが、景清洞はずっと水平に横穴が続く。 観光コースとして公開されているものだけで700メートルに近い。
 |
 |
 |
鍾乳洞の中は中は外とはうって変わって涼しい。 20℃を下回るうえに霧まで出ているので、寒いくらいだ。
 |
 |
 |
 |
観光コースの終わりは鍾乳洞の天井がだいぶ下がってきて、飛び上がると頭を打つ高さだ。 探検コースだとヘルメットを貸してくれて、その先まで進むことが可能だ。
 |
 |
鍾乳洞からの帰還。 外の光が見える。 そして気温がどんどん上昇してゆく。
 |
 |
 |
[Food] パラタ＠防府
防府にあるインド料理パラタ(食べログ)。
 |
 |
 |
8/12 (月)
実家に帰省
実家の防府に帰る途中、徳山駅に途中下車してみた。 お盆ということもあるのだが、駅前銀座が軒並みシャッタがー閉まっていて寂しい限りだ。 昔、行った近鉄松下も今年の2月にも撤退したらしい。
 徳山の駅前商店街 |
8/11 (日)
[Movie] パシフィック・リム
川崎109シネマズで「パシフィック・リム」の IMAX 3D で字幕版を観てきた。 チネチッタの 3D は吹き替えなのだが、これは IMAX 3D は字幕なのね。
でっかい怪物は Kaiju だし、ロケットパンチでるし、無駄に長い発進シーケンスとかもろに特撮映画っぽいよね。
8/10 (土)
[Movie] ワールド・ウォーZ
川崎チネチッタでワールド・ウォーZの 2D 字幕版を鑑賞。
マックス ブルックスの「WORLD WAR Z」だが、この本はゾンビ・アウトブレイクというかゾンビー世界大戦が完結後に著者が書いた報告書を読み上げるような内容で特定の主人公はいない。 「山椒魚戦争」的なコラージュの手法だ。 映画版は大幅に改変して、ブラド・ピットが演じる国連捜査官がゾンビ・アウトブレイクの解決法をクエストするという内容になっている。
この映画を観ながらダニエル ドレズナーの「ゾンビー襲来：国際政治理論で、その日に備える」を思い出したのだが、この映画みたいなゾンビ・アウトブレイクが起きたらゾンビの抹殺に反対するリベラル組織が実際にできそうだよね。
[Food] 本場タイ屋台料理チャオタイ＠川崎
いつものチャオタイ。 前回は7月13日に来ている。 今回初めてカップサイズのトムヤムクンがあることに気づいた。
 プラー パッ ナムプリックパオ |
 パッタイ ジェー |
 トム ヤム クン(カップ) |
