NAKAMURA Minoru の日記 (2010年9月)

先月の日記(2010年08月) 今月の日記(2010年09月)
2002 | 10 | 11 | 12
2003 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2004 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2005 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2006 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2007 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2008 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2009 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2010 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2011 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2012 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2013 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2014 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2015 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2016 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2017 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
ホームページ | 最新のコメント50
インデックス: 食べ歩き | Java | プログラム | UNIX | 画像
最新の日記へのリンク | この日記ページをはてなアンテナに追加 この日記ページをはてなブックマークに追加
はてな ダイアリー アンテナ ブックマーク ブログ
Twitter | mixi | Facebook | Google+
slideshare | github | Qiita



9/18 (土)

アルナルド・ポモドーロの『球体をもった球体』

ニコニコ動画にアップロードされている MMD 動画には 空中庭園 がよく出てくるが、この周囲に浮かんでいる痕のついた球体はアルナルド・ポモドーロの『球体をもった球体』(Google画像)がモデルだと思われる。 この球体は漫画などの背景にも頻出する。

「球体をもった球体」をはじめて観たのは、高校2年の時に行った箱根彫刻の森美術館だった。光沢のある球体の中にサイバネスティックな内臓をのぞかせているというのはすごいインパクトのある彫刻で、強く印象に残っている。

その後、これとよく似たモチーフの「球体」が各地の美術館や博物館に置かれているのを発見する。 似ただけではなく上野の博物館の前にある奴はレプリカのようだ。 バチカン美術館の前にも「球体をもった球体」があるらしい。

どれがオリジナルだろうか気になる。 彫刻の森美術館のが製作期間が1978-1980年で、ぱっと調べる限りでは一番古そう。 「彫刻の森美術館」の図録の解説を見れば分かるのだろうが、部屋の中を探しても見つからない。 どこいったんだろう?

紹介ページ

「球体をもった球体」を紹介しているページ。

P.S.

よく考えるとスターウォーズの第一作が1977年公開なんだよね。 デス・スターの影響を受けたかどうかは気になる。


9/17 (金)

C 言語で precise GC をやるには

C 言語で GC をやるシステムとして Boehm GC があるが、 これはメモリ中のデータをスキャンして「ポインタぽいものはポインタとみなす」という判定を行なったあとに mark-and-sweep GC を行なう conservative GC だ。 C 言語で全てのポインタを正確にトレースする precise GC または exact GC をやるのは非常に難しいのだが、 果敢に挑戦する人がいるようだ(Coding Blog | 8cc Cコンパイラ)

上記のブログにコメントしたのだが、 別観点から問題点を適当に列挙してみる。

マルチスレッドの問題

シングルスレッドの場合 GC はメモリを確保する関数(malloc)のタイミングで発生するため、 GC が起きるポイントはソースコード上の特定の位置に絞られる。 コンパイラは malloc などの呼び出し前にレジスタの内容をメモリに退避するなどすればポインタを正確にトレースすることができる。

一方、マルチスレッドでは GC を起こしたスレッド以外は、 他のスレッドをいったん停止させる必要がある。 このスレッドサスペンドを実装するには Solaris のようなスレッドを一時停止させる関数(thr_suspend)を使うのがよい。 しかし Linux のような pthread ライブラリしか持たない関数では、 非同期シグナルを他スレッドに送信して 予め仕掛けられたシグナルハンドラ内で一時待機をさせることになる。

どちらの方法でも他のスレッドが停止する位置(PC アドレス)は、 GC にとって都合のよい位置とは限らない。 コンパイラが生成した全命令、ライブラリ、PLT の中などでほとんど任意の位置でスレッドが停止する可能性がある。

そして停止した命令アドレス位置では、 スタックの情報が完全には解析できないかもしれないし、 レジスタの情報の解析はさらに困難であろう。

これを防ぐには、以下の2つの方法のどちらかを採用する必要がある。

  1. どの命令アドレスで停止してもスタックとレジスタがポインタが可能なように、予め情報を網羅的に用意しておく。 おそらくコンパイラが DWARF や unwind 情報のような形でスタックマップ、レジスタマップをバイナリ中の特別なセクションに配置する形になるはず。 GC ルーチンは、停止命令アドレスをキーにしてスタック・レジスタマップを検索し、ポインタかどうかを判定する。

    この方法はコード量の数倍の附加情報が必要になってデータが大きくなるのが欠点。

  2. コンパイラはスタック・マップ、レジスタ・マップを用意した特別な命令アドレス位置を、適当な間隔で設ける。 これはセーフポイント(safe point)と呼ばれることが多い。通常は後方分岐命令や関数の呼び出し位置などをセーフポイントとする。
    最初に GC 起動スレッドが他のスレッドを停止させた時点では、 セーフポイントで止まらない可能性が高い。 この時は、 GC は他スレッドの停止状態を解除して、次のセーフポイントまで自分で走行させる。 セーフポイント位置で他スレッドを再び停止させる。

    セーフポイント位置で停止さえる方法もいくつかあるが、 命令の書き換えを使う方法を使うことが多い。 GC ルーチンは他スレッドの停止命令アドレスから次に通過するセーフポイント位置を割り出して、 次のセーフポイントの命令を x86 なら無限ループする jmp $pc - 2 へ書き換えてしまう。 他のスレッドの停止状態を解除すると、 (期待通りなら)すみやかにセーフポイントまで進むので、 GC ルーチンは他スレッドを GC 安全な位置で止めたことになる。

    ただしこの方法はいくつも欠点を抱えている。
    • 命令の書き換えには self-modified code や cross-modified code に特有の問題が発生する。 命令キャッシュの不整合問題や、 書き換えた命令が停止させらようとしているスレッド以外にも見えてしまう問題である。
    • 停止状態から再会させた時にセーフポイントまで辿り着くとは限らない。 最悪無限ループするかもしれない。

また GC 制御のために、 プログラムが意図しない位置でスレッドを停止させると、 デッドロックが発生する危険性がある。

非同期シグナル

シグナル、特に非同期シグナルはいろいろ問題を引き起こす。

  • セーフポイント方式をとった場合、セーフポイントに誘導中の非同期シグナルをどうやって抑止するか?
    GC のためのスレッド制御にリアルタイムシグナルを使うとすれば、 それはプログラムの他のコンポーネントが使わないようにする必要がある。 また GC 制御用のリアルタイムシグナルが、 ユーザプログラムから呼び出される sigprocmaskpthread_sigmask によってブロックされないようにする必要がある。

システムに深く関係するデータ構造

C 言語の場合、OS の機能がラッピングされずに直接的に見えてしまうので、 本来 GC を念頭におかれていないシステムコールとの整合性が問題になる。

  • setjmpgetcontext やシグナルハンドラなどに渡ってくる sigcontext_t 構造体には、レジスタが含まれている。 precise GC を行なう場合には、この中のポインタを保持しているレジスタを正確に判定してマーキングに加える必要がある。
    しかし本当にそんなことができるのか?
    シグナルハンドラの sigcontext_t 構造にどのようなレジスタが渡るのかはコンテキスト依存だ。 特に非同期シグナルは(マスクが空いている限り)どの位置でも発生しうるので、 疎な safe point がスタックマップを持つだけでは対応できない。

  • 同様に SIGSEGV シグナルの場合、si_addr はどのように扱うか? SIGSEGV シグナルの発生元アドレスにあるオブジェクトを GC が動かしてしまった場合 si_addr も一緒に移るべきだが、そんなことは可能なのだろうか?

  • GC が発生した時点で、 待機系のシステムコール(sigwait やセマフォや mutex)を呼び出しているスレッドがいた場合の対処は難しい。
    • いったん起きてもらう → GLIBC の書き換えが必要?
    • 寝ているスレッドは起こさないで GC を行なう。 → スタック・レジスタ情報が不完全になる。

9/13 (月)

[Food] 四季懐石 たらふく@武蔵中原 (公式食べログ)

8月23日付けで所属が異動になった我々とインターンの学生さんの歓迎会を 南武線沿線の懐石料理で。

たらふく:
通し
たらふく:
刺身
たらふく:
ウナギの蒲焼
たらふく:
里芋に煮っ転がし
たらふく:
天ぷら
たらふく:
揚げ出し豆腐
たらふく:
鯖寿司
たらふく:
海ぶどう
たらふく:
秋刀魚
たらふく:
天ぷら
たらふく:
お茶漬け

9/9 (木)

[Work] 職場のパソコンが新しくなる

職場のマイパソコンが、 Pentium3 1GHz x2 + memory 1GB + Windows 2000 から Core i5-660 3.33GHz + memory 4GB + Windows 7 に昇進した。


9/8 (水)

[時事] 東京・千葉が冠水

台風9号の影響で関東圏とくに東京と千葉の各所が冠水・水没して大変なことに。

そういえば私が大学受験をした年も東京に台風がヒットして、 御茶ノ水駅が水没したんだったよなぁ。


9/3 (金)

ブレードサーバ PRIMERGY BX900 をセットアップする

富士通製のブレードサーバ BX900のセットアップ作業。

過去に同種のブレードサーバーを触った時から比べると 性能が向上しているのは当然だが、 管理系が改善されて大変に楽になった。

  • 起動時の BIOS を含めたビデオ出力が IP ネットワーク越しに飛ばせるようになった。
  • リモートで仮想CD/DVDドライブをアタッチ可能。 手元のパソコンに OS のインストールイメージを用意すれば、 リモートインストール可能。
  • NIC カードが iSCSI ブート対応。

考えてみれば IPMI がそこらへんのパソコンに載るようになっている時代なのだから、 そのうち20〜30万円ぐらいのワークステーションにこのへんの機能も載るようになるんだろうなぁ。

P.S.

ところでこの手の機能脳は操作端末(パソコン)からブレードサーバのリモートマネージメントコントローラにコネクションを貼るのだけど、 仮想CD/DVDドライブ機能(富士通はリモートストレージと呼んでいる)だけは逆にリモートマネージメントコントローラから操作端末にコネクションを貼ろうとしている。

途中にファイヤーフォールのアクセス制限が掛かっていて、 インバウンドtcp接続を弾いているとなぜか仮想CD/DVDドライブ機能が動作せずに大いに悩んでしまった。


9/1 (水)

[Linux] wait queue に関するメモ

2月8日の日記に書いた、 Linux カーネルで wait queue を使う場合のメモ。

wait queue を使って待機するスレッド(タスク)は以下の処理を行なう。 この処理の中でスレッドを待機するのは L7 の schedule() の中だ。 schedule() がスレッドの CPU 時間を剥ぎ取るのは、 その直前の L5 で current->status を走行状態(TASK_RUNNING)から 待機状態(TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE)に更新しているため。

    /* 静的変数として定義 */
 1: static DECLARE_WAIT_QUEUE_HEAD(waitq);

    /* wait queue に入れる側 */
 2: DECLARE_WAITQUEUE(wait, current);

    /* 本当に待機するかどうか条件をチェックするためにスピンロックをかける */
 3: spin_lock_irqsave(&wait_lock);

    /* キューに wait を突っ込む。 */
 4: add_wait_queue(&waitq, &wait);

    /* current->status を TASK_INTERRUPTIBLE */
 5: set_current_state(TASK_INTERRUPTIBLE);

    /* 割り込みを禁止したまま schedule() は呼べないので解除 */
 6: spin_unlock_irqsave(&wait_lock);

 7: schedule();

 8: spin_lock_irqsave(&wait_lock);

    /* current->status を TASK_RUNNING */
 9: set_current_state(TASK_RUNNING);

10: spin_unlock_irqsave(&wait_lock);

    /* キューから wait を削除する。 */
11: remove_wait_queue(&waitq, &wait);

しかしこの L5 と L7 はスピンロックで守られた排他区間ではないので、 スレッドを起こす側が下のような処理だと、 待機側の CPU が L8 でスピンロックを解いた後 まだ L9 の間を実行する前に、 起動側の CPU が wake_up_all を実行してしまうことがある。

spin_lock_irqsave(&wait_lock);

wake_up_all(&waitq);

spin_unlock_irqsave(&wait_lock);

これを防ぐために wake_up 系は、 wait queue から起こしたいスレッドに対して schedule.c の中で default_wake_function を適用し、

  1. task->status を TASK_RUNNING に更新する。
  2. 起こしたいスレッドをスレッドスケジューリングの run queue に挿入する。
    待機しているスレッドが起動側の CPU とは異なる場合には、 プロセッサ間割り込みも使う。

という方法で current->status を TASK_RUNNING に変えてしまう。 そのため L6〜L7 の間で wake_up_all が掛かった場合、 CPU 実行権が残っている限り L7 の schedule() からは直帰することになり、待機側のスレッドが眠りっぱなしということはない。

ただ wait_lock を使ったスピンロックがない場合は、 どうなるのだろう?


先月の日記(2010年08月) 今月の日記(2010年09月)
2002 | 10 | 11 | 12
2003 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2004 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2005 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2006 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2007 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2008 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2009 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2010 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2011 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2012 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2013 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2014 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2015 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2016 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
2017 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
ホームページ | 最新のコメント50
インデックス: 食べ歩き | Java | プログラム | UNIX | 画像
最新の日記へのリンク | この日記ページをはてなアンテナに追加 この日記ページをはてなブックマークに追加
はてな ダイアリー アンテナ ブックマーク ブログ
Twitter | mixi | Facebook | Google+
slideshare | github | Qiita


Written by NAKAMURA Minoru, Email: nminoru atmark nminoru dot jp, Twitter:@nminoru_jp