|
ランポートのパン屋のアルゴリズム（ランポートのパンやのアルゴリズム）とは、情報工学者レスリー・ランポートが考案したコンピュータ用の相互排他のためのアルゴリズムである。マルチスレッド処理の頑健性を相互排他（ミューテックス）によって強化することを目的としている。 コンピュータにおいて、マルチスレッドが同時に同じリソースにアクセスすることは普通に行われる。複数のスレッドが同じメモリ位置に同時に書き込みを行えば、データ破壊が発生する可能性があるし、あるスレッドが書き込み途中のメモリ領域を別のスレッドが読み込んでもデータ破壊が発生する可能性がある。ランポートのパン屋のアルゴリズムは数ある相互排他アルゴリズムのひとつで、並列スレッドが同時にクリティカルセクションに入ることを防いでデータ破壊の危険性を排除する。 == アルゴリズム == === 「パン屋」の由来 === ランポートは、番号札発行機が入り口にあるパン屋を想像した。それによって個々の客にユニークな番号を割り当てるのである。客が入店する度に番号が 1 ずつ増えていく。番号表示機があって、現在応対中の客の番号が表示される。他の客は列に並んで待ち、パン屋の店員が現在の客の応対を終えると、次の番号が表示される。買い物の際、客は番号札を返して欲しいものを得るが、新たな番号を得ずに買い物を続けることはできない。 コンピュータでは「客」がスレッドに対応し、広域変数で表される ''i'' で識別される。 コンピュータアーキテクチャには限界があるため、ランポートのアナロジーの一部は若干変更を加える必要がある。複数のスレッドが同時に要求すると、同じ番号を与えられる可能性があり、これを防ぐことはできない。従って、スレッド識別子である ''i'' が優先順位も表すものと見なす。''i'' の値が小さいスレッドは優先順位が高く、先にクリティカルセクションに入ることができる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ランポートのパン屋のアルゴリズム」の詳細全文を読む スポンサード リンク
|