UPS

2009/07/26

気がついたら、オーディオ機器に接続するUPSが著しく増殖していた。



別にだからなんだということでもないが。

ついでに言うと、左に見えている黒い板はPioneerのKUROの背面である。でもって、這い回っているケーブルの大部分は電源とLANである。

出火しなければいいのだが。

同期

2009/07/20

主筆」の、テキストデータを保持し、編集する部分の実装を進めてはいるのだが、やはり難しい。とりあえず、文字列の追加と削除を行う処理だけを先に作って、その部分だけでもとりあえず動くようにしようと考えているのだが、それだけでも難しい。

今現時点では、追加・削除の処理を行う部分のコーディングが終わり、少しずつ動かし始めてはいるのだが、どうにも思うように動いてくれない。一つ課題が解決すれば、また次の問題が生じるという状態で、苦しいことこの上ない。いかんせん、アルゴリズムそのものが複雑なのだから仕方がない。

ところで、今頑張って作っているロジックは、ウインドウ幅での行折り返しを実現するということと共に、複数の処理を並列で走らせて、処理効率を向上するという目的もある。とすると、何らかの方法で、スレッド間の排他制御を行い、矛盾が生じないようにしてやらなければならないはずである。しかも、処理効率向上を目的としているのだから、ごく単純に、あるスレッドがデータ構造にアクセスしようとする都度、データ全体に対して排他ロックを掛けると言うような方式を採用するわけには行かない。複数スレッドが矛盾が生じない限り、複数のスレッドが同時にアクセスできるような方式を考えなければならない。

しかしこれはこれで非常に難しい問題である。

直感的に言って、ツリー構造全体にロックをかけてしまうのが野蛮だというのであれば、ツリーの個々のノードに対してロックをかけるようにすればいいような気がし無くもない。そうすれば、少なくとも矛盾が生じることなく、かつ、複数スレッドで同時にデータ構造にアクセスすることができるようになるはずである。

しかし、その方式には大きな問題点がある。まず、各ノード間には複雑なデータの依存性があるという事だ。つまり、親ノードは子ノードに対するインデックスであるため、子ノードの情報を変更した場合はその変更が親ノードに反映されなければならない場合がある。そのため、単純に一つのノードをロックすると言っても、実際に排他をかけなければいけない範囲は、単一のノードよりもはもう少し広いということになる。そのため、ロックをかける範囲がはっきりせず、実装が困難だと思われる。

さらに、個々のスレッドがどのような順番でノードにアクセスするかが決められないため、場合によってはデッドロックに陥る危険性があるという問題がある。各スレッドの処理をACID特性に従ったトランザクションとして実装するのであれば、デッドロックが生じた場合には、それを検出して一方をロールバックするという方法も考えられる。だが、そこまでやるのは明らかに大仰過ぎる上に、処理速度的にも不利になる。だから、処理が途中で失敗したら元に戻せるような実装にすることはできない。すなわち、デッドロックから回復する術がないということであるため、そもそも、デッドロックが発生しないような、何らかの方法を考えなければならない。

デッドロックを防ぐためには、各リソースに対して、ロックをかける順番をあらかじめ決めておいてしまえばいい。そうすれば、理論上デッドロックは発生し得なくなる。しかし、今回はその方式を採用することはできない。

ツリー構造である都合上、同一の高さのノードを左右に移動するようなアクセスはあまり起こらないと考えられる。そうすると、ロックをかける順番を「上から」と「下から」のどちらかに限定しさえすれば、デッドロックを防ぐことができるような気がする。しかし、必ず上(ルート側)から順番にロックをかけるようにする、というルールを決めた場合、それは、アクセスする都度必ずツリー全体にロックをかけるという方式と同じになってしまう。なぜならば、ツリー構造である都合上、アクセスそのものが必ずルートから行われることになるためである。また、下(葉)から順番にロックをかけるというのも、同じ理由で成立し得ない。いきなり葉からアクセスすることはできないからだ。

また、この考えを延長して行くと、二層ロックを採用することも不可能という事になる。ツリー構造にアクセスするためには、まずルートにアクセスする必要があり、そのためにルートのノードに対してロックをかけることになる。その後、自分が一通りの処理を終えるまでずっとルートのノードを押さえ続けていたら、その間ずっと他のスレッドはツリー構造にアクセスすることができなくなってしまう。だから、どうしても処理途中であっても使わなくなったノードは解放してやるようにしてあげなければならない。

そう考えていくと、どうにも八方塞がりの様な気がしてくる。しかし、あまり汎用性のない、アプリケーション依存な方法を使うのであれば、全くやりようがないという事でもないようだ。まず、データ構造にアクセスするスレッドの種類・数・アクセスパターンは、あらかじめはっきりと判っている(何せ自分で作るのだから)。そこから、起こりうる競合を全て洗い出して、各競合に対してどのように対処すればいいかを一つずつ決めていけばいい。そうすれば、高い効率を維持したまま、矛盾やデッドロックを生じさせないようにすることが可能である。

とりあえず、考えた結果については、また今度気が向いたら書くことにしよう。

時間

2009/07/10

「主筆」の文字列を保持するデータ構造の実装を始めてからかなり時間が経つが、まだコーディングも終わっていない。そもそも、テキストファイルの読み込み/文字コードの変換/マルチバイト-ワイドバイトの変換/データ構造への格納/構文強調表示処理/文字の描画位置の確定/画面への文字列の描画という7種類の処理を全て並列に処理させようと言う野心的な目標なのだから、そう簡単に終わるものとは考えていない。その上、ウインドウ幅での行折り返しに対応させるために、いくつかの余分なデータも保持させなければならないのだから、ますます事態は複雑化し混迷を極めている。

しかし、「主筆」の開発を進める一方で技術士の受験勉強もしなければならない。気がついてみれば、試験日まであと一ヶ月を切っている。論文を書く練習なども、このところ少しさぼり気味だったから、また復活させなければならない。時間は限りなく無いと言える。

どうやらこれは、エロ画像の収集に精を出している場合ではなさそうだ。