パンツ排他処理
2008年07月14日01:40
最近僕のなかで「排他処理」がマイブームになっている。 僕が今取り組んでいる『並列処理』というプログラムの形態では絶対に必要な処理だ。
並列処理というのは、複数の事を同時に実行するプログラムの形態のことだけど、並列処理じゃない普通のプログラムがどうなのかしらないと、並列処理のありがたさがわからないと思う。 たとえば、今、こうしてmixiをやっているあなたのコンピューターでせっせと働いているウェブブラウザは、基本的に並列処理ではない、普通の処理（直列処理）のプログラムだ。
これは、要するに、小さいラーメン屋の親父の様なものだ。 こういうラーメン屋では、お客さんが１０人居ようが２０人居ようが、ラーメンを作るのは、親父一人だ。 お客さんが同時にラーメンを頼んでも、親父はテーブルの片端から器を並べていき、端から順番にラーメンを作っていく。 これが直列処理だ。 これだと、お客さんがたくさんになってくると、お客さんが注文してからラーメンにありつくまでの時間がたくさんかかるようになってしまう。
そこで、ラーメン屋の親父は、アルバイトを何人か雇う。 すると、麺をゆでる人、スープを入れる人、具を入れる人と、手分けしてラーメンを作る事もできる。 こういう風に複数の手順を平行して実行することを、並列処理と呼ぶ。 手分けの仕方によって状況に合わせた柔軟な対応ができるのも、この並列処理の強みだ。 例えば、充分人手がある場合では、２つ以上のラーメンを同時に作る事ができるようにもなるだろう。
これが並列処理で、僕は、この並列処理というものを使って、新しいプログラムを組んでいる。
並列処理っていうのは、効率がとてもよい反面、とても難しい問題も持っている。 例えばラーメン屋の厨房にモタモタしているタイミングの悪いヤツが居ると、ラーメン屋全体で、ラーメン提供速度が落ちてしまったり ...なんていう、一人では絶対に起こらなかった問題が起こってくるのだ。
例えば、作業の前後関係がおかしくなるのなどは、多人数で仕事をしている時に起こる代表的な問題だ。
ラーメンというのは、汁を入れて、油を入れて、麺を入れて、そこに具を入れて出来上がりだが、汁入れ担当がグズグズして居るうちに、麺が入ってしまい、具が入ってしまい、そこに汁入れ担当が、ようやく汁を入れる、というような事が起こると、折角のパリパリ海苔がグチャグチャになってしまう。 これでは作り直しである。 並列処理もこれと同じで、そういうことがないように、処理の前後関係をキチンと守る仕掛けが必要だ。
これのことを、並列処理の世界では「排他処理」と呼ぶのだけど、排他処理には色々な種類がある。
例えば、餃子焼きナベにＡさんが来て、餃子を焼き始めた... ところが、後からＢさんがやってきて、更に餃子を入れて焼き始めた... これでＡさんが焼き始めた餃子とＢさんが焼き始めた餃子が混ざってしまって、焼き加減がおかしくなってしまう、という事が起こる。こういうことがないように、Ａさんが餃子を焼いている間、Ｂさんは待つ必要がある。
このように、ある道具を使う人が常に一人であることを保障する事を「ミューテックス」を取得すると呼んだりする。 ミューテックスというのは、相互排除という意味のコンピューター用語で、非常に有名な処理だ。
なんでたかがそれだけのことなのに、ミューテックスなんて名前をつけて特殊扱いするのかというと、ミューテックスはプログラマが自分自身の手で作るのが極めて難しく、ほとんどの場合、WindowsなどのＯＳが提供しているような物を流用する必要があるからだ。
先ほどのラーメン屋の例で行くと「... 餃子焼きナベを使っている間は、上にフダを乗せて置くように。」とかいうルールを作ったとしても、ある日、昼の忙しい時、二人同時にナベを見て、二人同時に札を置いてしまうということが起こることがあるかもしれない。 現実の世界では、二人が目を合わせればそういうことは起こらないかもしれないが、コンピューターの世界は、店の電気を消して真っ暗の中で声も出さずに仕事をしている、とでもいうような極めて特殊な状況下なので、現実の世界では起こりそうもないことでも、コンピューターの中では本当に起こってしまうのだ。
このような問題が起こらないようにするのは、簡単そうに思えるが、実際にやってみるとことのほか難しい。 声も聞こえない真っ暗のラーメン屋の中で「フダを置く」とか「肩をたたく」とかいった限られたコミュニケーション法だけで衝突しないようにラーメンを作るところを想像して欲しい。 手順がひとつでも狂うと誰がどこに居るかもわからなくなってしまうだろう。 「ミューテックス」というのは、実に特殊な仕掛けなのだ。
キューという処理もある。これは「待ち行列」の事だ。 店員がトイレに行きたくなる。 しかし、トイレはひとつしかないというような場合、もしもトイレが使用中だったら後ろで待っている必要がある。 そうやって、トイレを使いたい人が行列を作って待っているような状態は、コンピューターの世界でもよく見られる。 これはトイレに限らず、あらゆる場面で発生する。 例えばさきほどの餃子焼きナベの利用順なども、こういう例に当たる。 きちんと早い者順の順番を守らないと、いつまでたっても餃子を作れない料理人が出てしまうため、きちんと待ち行列を作る必要がある。 こういう処理のことをコンピューターの世界では「キュー処理」「キューイング」などと呼ぶ。
◇
今日、僕は、「読み込み書き込みロック」というものを作ろうと思った。これは Windowsでファイルの更新をする時、非常によくつかう機能だが、これを自分で作ろうとすると、もの凄く難しいのだ。
これは、例えばファイルを開いて読んでいるとき、誰か知らない人がそのファイルを開いていつの間にか書き換えてしまった、なんてことが起こらないようにするための機能なのだ。 開いていた人はファイルが書き換わるなんていうことは予想していない事なので、書き換わっていない心積もりで仕事を進めてしまう。 こうやって、データを壊してしまったり、プログラムが誤動作してしまったりすると、とても困った事になる。
そういうことがないように、自分だけがファイルを操作できるように制限する必要がある。これをロックなどと呼ぶ。 これもミューテックスの一種だ。
しかし、普通ファイルというのは読むことの方が多いものだ。 書き込むことは稀だということも珍しくない。 すると、ファイルを読むだけのためにいちいち自分専用にロックをかけるのは、とてもムダが多いということになる。 読むだけなら、みんなで仲良く読んだってかまわないのだ。 しかし、時々書き込む人だけ制限したい。 そんな都合のよいロックがあるのだろうか。
あるのだ。 こういう読み込み様のロック処理のことを「共有ロック」というらしいことがわかった。それに対して書き込みロックは「排他ロック」だ。 その「共有ロック」と「排他ロック」が同時に起こると、どういう干渉が起きるのか、想像も出来なかった。
ずっと悩んだ。 二つの性質の違うロックが重なるとどういうことになるのか、ひたすらタイミングチャートを描いて考えた... しかし条件分岐のパターンが多く複雑で非常に難航した。
ある瞬間ひらめいた。 ここ数日で一番のヒラメキだった。
これは「男女兼用トイレ」の様なものなのだ。 ひとつのトイレがある。 ところが、このトイレは男女兼用だった。 このトイレはいつも込んでいて行列が出来ている。 ここの男性・女性がそれぞれたくさん並んでいる。
男性は、別に見られても恥ずかしくないので、２～３人で同時にトイレに入って用を足しても全く構わない。 だから、男性がトイレに居る時、次の人が男性であれば次の人も入ることが出来る。 これが共有ロックだ。
しかし、次の人が女性だったとする。 女性は男性女性に限らず２人以上でトイレを使うのはいやなので、この男性二人がトイレから出るまで待つことになる。 そして、女性がトイレに入ると、次の人が男性であろうと、女性であろうと、そのトイレの中の女性が外に出るまでは中に入れない。 これが排他ロックだ。
考えてみれば、コンピューターサイエンスの初歩の初歩でもあるわけなのだけど、初歩だろうがへったくれだろうが、知らないものは知らないので、仕方がない...。 とにかく必要な事を全て知り尽くす時が来るまで地道にコツコツと頑張ろうと思う。
今、僕は、省機能の軽量データベースの様なものを作っている。 非階層型ファイルシステムを作るに当たって、最初はリレーショナルデータベースを使ってインデックスを管理していたのだけど、使う機能は限られているのに、性能が高すぎるためとても遅いし、今計画している機能を追加すると、とても複雑になるということも判明したので、この際専用のデータベースを自分の手で作ってしまおうと考えたのだ。
作成に当たってネックになるのが排他処理というわけだった。
だけど、こういうコンピューターの基礎について勉強すると、色々アイデアがわいてくる。 あぁこんな事もできる、あんな事もできる、ととても自由な気持ちになれる。 まだ知識が足りなさ過ぎるのだけど、全部知り尽くすことが出来たら、すごく面白いプログラムがサクサク作れるようになると思う。
並列処理というのは、複数の事を同時に実行するプログラムの形態のことだけど、並列処理じゃない普通のプログラムがどうなのかしらないと、並列処理のありがたさがわからないと思う。 たとえば、今、こうしてmixiをやっているあなたのコンピューターでせっせと働いているウェブブラウザは、基本的に並列処理ではない、普通の処理（直列処理）のプログラムだ。
これは、要するに、小さいラーメン屋の親父の様なものだ。 こういうラーメン屋では、お客さんが１０人居ようが２０人居ようが、ラーメンを作るのは、親父一人だ。 お客さんが同時にラーメンを頼んでも、親父はテーブルの片端から器を並べていき、端から順番にラーメンを作っていく。 これが直列処理だ。 これだと、お客さんがたくさんになってくると、お客さんが注文してからラーメンにありつくまでの時間がたくさんかかるようになってしまう。
そこで、ラーメン屋の親父は、アルバイトを何人か雇う。 すると、麺をゆでる人、スープを入れる人、具を入れる人と、手分けしてラーメンを作る事もできる。 こういう風に複数の手順を平行して実行することを、並列処理と呼ぶ。 手分けの仕方によって状況に合わせた柔軟な対応ができるのも、この並列処理の強みだ。 例えば、充分人手がある場合では、２つ以上のラーメンを同時に作る事ができるようにもなるだろう。
これが並列処理で、僕は、この並列処理というものを使って、新しいプログラムを組んでいる。
並列処理っていうのは、効率がとてもよい反面、とても難しい問題も持っている。 例えばラーメン屋の厨房にモタモタしているタイミングの悪いヤツが居ると、ラーメン屋全体で、ラーメン提供速度が落ちてしまったり ...なんていう、一人では絶対に起こらなかった問題が起こってくるのだ。
例えば、作業の前後関係がおかしくなるのなどは、多人数で仕事をしている時に起こる代表的な問題だ。
ラーメンというのは、汁を入れて、油を入れて、麺を入れて、そこに具を入れて出来上がりだが、汁入れ担当がグズグズして居るうちに、麺が入ってしまい、具が入ってしまい、そこに汁入れ担当が、ようやく汁を入れる、というような事が起こると、折角のパリパリ海苔がグチャグチャになってしまう。 これでは作り直しである。 並列処理もこれと同じで、そういうことがないように、処理の前後関係をキチンと守る仕掛けが必要だ。
これのことを、並列処理の世界では「排他処理」と呼ぶのだけど、排他処理には色々な種類がある。
例えば、餃子焼きナベにＡさんが来て、餃子を焼き始めた... ところが、後からＢさんがやってきて、更に餃子を入れて焼き始めた... これでＡさんが焼き始めた餃子とＢさんが焼き始めた餃子が混ざってしまって、焼き加減がおかしくなってしまう、という事が起こる。こういうことがないように、Ａさんが餃子を焼いている間、Ｂさんは待つ必要がある。
このように、ある道具を使う人が常に一人であることを保障する事を「ミューテックス」を取得すると呼んだりする。 ミューテックスというのは、相互排除という意味のコンピューター用語で、非常に有名な処理だ。
なんでたかがそれだけのことなのに、ミューテックスなんて名前をつけて特殊扱いするのかというと、ミューテックスはプログラマが自分自身の手で作るのが極めて難しく、ほとんどの場合、WindowsなどのＯＳが提供しているような物を流用する必要があるからだ。
先ほどのラーメン屋の例で行くと「... 餃子焼きナベを使っている間は、上にフダを乗せて置くように。」とかいうルールを作ったとしても、ある日、昼の忙しい時、二人同時にナベを見て、二人同時に札を置いてしまうということが起こることがあるかもしれない。 現実の世界では、二人が目を合わせればそういうことは起こらないかもしれないが、コンピューターの世界は、店の電気を消して真っ暗の中で声も出さずに仕事をしている、とでもいうような極めて特殊な状況下なので、現実の世界では起こりそうもないことでも、コンピューターの中では本当に起こってしまうのだ。
このような問題が起こらないようにするのは、簡単そうに思えるが、実際にやってみるとことのほか難しい。 声も聞こえない真っ暗のラーメン屋の中で「フダを置く」とか「肩をたたく」とかいった限られたコミュニケーション法だけで衝突しないようにラーメンを作るところを想像して欲しい。 手順がひとつでも狂うと誰がどこに居るかもわからなくなってしまうだろう。 「ミューテックス」というのは、実に特殊な仕掛けなのだ。
キューという処理もある。これは「待ち行列」の事だ。 店員がトイレに行きたくなる。 しかし、トイレはひとつしかないというような場合、もしもトイレが使用中だったら後ろで待っている必要がある。 そうやって、トイレを使いたい人が行列を作って待っているような状態は、コンピューターの世界でもよく見られる。 これはトイレに限らず、あらゆる場面で発生する。 例えばさきほどの餃子焼きナベの利用順なども、こういう例に当たる。 きちんと早い者順の順番を守らないと、いつまでたっても餃子を作れない料理人が出てしまうため、きちんと待ち行列を作る必要がある。 こういう処理のことをコンピューターの世界では「キュー処理」「キューイング」などと呼ぶ。
◇
今日、僕は、「読み込み書き込みロック」というものを作ろうと思った。これは Windowsでファイルの更新をする時、非常によくつかう機能だが、これを自分で作ろうとすると、もの凄く難しいのだ。
これは、例えばファイルを開いて読んでいるとき、誰か知らない人がそのファイルを開いていつの間にか書き換えてしまった、なんてことが起こらないようにするための機能なのだ。 開いていた人はファイルが書き換わるなんていうことは予想していない事なので、書き換わっていない心積もりで仕事を進めてしまう。 こうやって、データを壊してしまったり、プログラムが誤動作してしまったりすると、とても困った事になる。
そういうことがないように、自分だけがファイルを操作できるように制限する必要がある。これをロックなどと呼ぶ。 これもミューテックスの一種だ。
しかし、普通ファイルというのは読むことの方が多いものだ。 書き込むことは稀だということも珍しくない。 すると、ファイルを読むだけのためにいちいち自分専用にロックをかけるのは、とてもムダが多いということになる。 読むだけなら、みんなで仲良く読んだってかまわないのだ。 しかし、時々書き込む人だけ制限したい。 そんな都合のよいロックがあるのだろうか。
あるのだ。 こういう読み込み様のロック処理のことを「共有ロック」というらしいことがわかった。それに対して書き込みロックは「排他ロック」だ。 その「共有ロック」と「排他ロック」が同時に起こると、どういう干渉が起きるのか、想像も出来なかった。
ずっと悩んだ。 二つの性質の違うロックが重なるとどういうことになるのか、ひたすらタイミングチャートを描いて考えた... しかし条件分岐のパターンが多く複雑で非常に難航した。
ある瞬間ひらめいた。 ここ数日で一番のヒラメキだった。
これは「男女兼用トイレ」の様なものなのだ。 ひとつのトイレがある。 ところが、このトイレは男女兼用だった。 このトイレはいつも込んでいて行列が出来ている。 ここの男性・女性がそれぞれたくさん並んでいる。
男性は、別に見られても恥ずかしくないので、２～３人で同時にトイレに入って用を足しても全く構わない。 だから、男性がトイレに居る時、次の人が男性であれば次の人も入ることが出来る。 これが共有ロックだ。
しかし、次の人が女性だったとする。 女性は男性女性に限らず２人以上でトイレを使うのはいやなので、この男性二人がトイレから出るまで待つことになる。 そして、女性がトイレに入ると、次の人が男性であろうと、女性であろうと、そのトイレの中の女性が外に出るまでは中に入れない。 これが排他ロックだ。
考えてみれば、コンピューターサイエンスの初歩の初歩でもあるわけなのだけど、初歩だろうがへったくれだろうが、知らないものは知らないので、仕方がない...。 とにかく必要な事を全て知り尽くす時が来るまで地道にコツコツと頑張ろうと思う。
今、僕は、省機能の軽量データベースの様なものを作っている。 非階層型ファイルシステムを作るに当たって、最初はリレーショナルデータベースを使ってインデックスを管理していたのだけど、使う機能は限られているのに、性能が高すぎるためとても遅いし、今計画している機能を追加すると、とても複雑になるということも判明したので、この際専用のデータベースを自分の手で作ってしまおうと考えたのだ。
作成に当たってネックになるのが排他処理というわけだった。
だけど、こういうコンピューターの基礎について勉強すると、色々アイデアがわいてくる。 あぁこんな事もできる、あんな事もできる、ととても自由な気持ちになれる。 まだ知識が足りなさ過ぎるのだけど、全部知り尽くすことが出来たら、すごく面白いプログラムがサクサク作れるようになると思う。
コメント一覧
zannin 2008年07月14日 18:52
説明すごくわかり易いですね！
待ち行列とかは銀行の窓口で説明を受けた記憶が微かにあります。。。
プログラマの方が素晴らしいものを作ってくださっても
私のような未熟構築屋が機器選定(というかRAIDカードだったりですが)をショボってパフォーマンス落とすんですよねorz
過去にそれでストレージを変えたことがります。
あと、RAID5 は大嫌いです(笑)
#ブラックボックスをいじるのは本当に難しいですね
本物のエンジニアの方には本当に頭が下がります。
ハード、ソフト問わず。
待ち行列とかは銀行の窓口で説明を受けた記憶が微かにあります。。。
プログラマの方が素晴らしいものを作ってくださっても
私のような未熟構築屋が機器選定(というかRAIDカードだったりですが)をショボってパフォーマンス落とすんですよねorz
過去にそれでストレージを変えたことがります。
あと、RAID5 は大嫌いです(笑)
#ブラックボックスをいじるのは本当に難しいですね
本物のエンジニアの方には本当に頭が下がります。
ハード、ソフト問わず。
おかあつ 2008年07月14日 19:00
＞ プログラマの方が素晴らしいものを作ってくださっても 私のような未熟構築屋が機器選定(というかRAIDカードだったりですが)をショボってパフォーマンス落とすんですよねorz
実は、プログラマがすごい間違ったものを作っているんだけど、それをいえないので、使っている人に「そんな使い方するからパフォーマンスが悪化するんだ」とか、人のせいにしているだけだったりして...。
（＾－＾；
あと、ブラックボックスをいじるのは難しいなあ... と思って、思い切ってふたを開けたら、実は中身が空っぽだったとか...。
（＾－＾；；；
ブラックボックスを作った人を捕まえようと思ったら、作った人が外注さんで、とうに退社していなかったりとか
（＾－＾；；；；；
その外注さんって、僕だったりして！
！！！（￣ロ￣ ；；；；
笑えるようで結構笑えないくらいよくあるんですよね...。
実は、プログラマがすごい間違ったものを作っているんだけど、それをいえないので、使っている人に「そんな使い方するからパフォーマンスが悪化するんだ」とか、人のせいにしているだけだったりして...。
（＾－＾；
あと、ブラックボックスをいじるのは難しいなあ... と思って、思い切ってふたを開けたら、実は中身が空っぽだったとか...。
（＾－＾；；；
ブラックボックスを作った人を捕まえようと思ったら、作った人が外注さんで、とうに退社していなかったりとか
（＾－＾；；；；；
その外注さんって、僕だったりして！
！！！（￣ロ￣ ；；；；
笑えるようで結構笑えないくらいよくあるんですよね...。
