FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://sites.google.com/site/fpgadevelopindex/

MITのxv6を読もう - 第4章 ロック獲得の仕組み -

http://pdos.csail.mit.edu/6.828/2014/xv6/book-rev8.pdf

第4章では、ロックについての説明がなされている。ロックをどのように実装するかということについて、モデルとしては、

21 void
22 acquire(struct spinlock *lk)
23 {
24     for(;;) {
25         if(!lk->locked) {
26             lk->locked = 1;
27             break;
28         }
29     }
30 }

なのだが、そうは行っても、25行目を複数のプロセッサが同時に実行して、26行目を同時に実行してしまうと複数のCPUがロックを獲得してしまう。 これを防ぐためには、25行目と26行目が同時に実行できるようにすれば良い。 これはx86のアトミック操作命令を利用するのが良い、というかハードウェアに頼らないとこれを根本的に解決することはできない。

  • xchg命令

softwaretechnique.jp

第1オペランド(格納先)を第2オペランド(読み込み元)と交換します
オペランドには、2個の汎用レジスタまたは1つのレジスタとメモリアドレスが使用できます
メモリオペランドが参照されていると、LOCKプリフィクスの有無、あるいはIOPLの値に関係なく
プロセッサのロッキングプロトコルが効果操作が持続している間自動的に実行されます(ロッキングプロトコルについてはLOCKプリフィクスを参照してください)。 

つまり、アトミックにメモリに対して読み込みと書き込みを行う。 xchgにより、メモリに対して1を書き込もうとするのだが、交換された値(つまり、元のメモリの値)が1であれば、それは既にロックが取られている、という意味。 一方で、交換された値が0であれば、もともとメモリには0が書き込まれており、ロックは誰も取得していない、また、xchgの効果により、メモリには1が書き込まれたため、自分がロックを獲得したことになる、という仕組み。

一方で、プログラムのモジュール性という所で言うと、ロックは呼び出し元と呼び出し先に依存が発生するため、モジュール性は落ちる。 例えば、あるプログラムがロックを獲得して、さらに同一のロックを獲得しようとしても、獲得できないためデッドロックか永遠にスピンすることになってしまう。

これを回避するために「再帰ロック(recursive lock)」というものを説明している。 再帰ロックは、同一のプロセスが同一のロックを複数回獲得することを許すというものである。 これによりロックは、既にロックを獲得してクリティカルなデータを編集中にでさえ、ロックをさらに獲得し直すことが可能になってしまう。

これはこれで便利点もあるし不便な点もある。もはや、この状態では、ロックは呼び出し側と呼び出し元を保護することのみでしか、存在価値が無くなってしまう(これは意味が合っているかな?)