排他制御の基礎の基礎

はじめに

システムに存在するリソースには同時にアクセスしてはいけないものが多々あります。身近な例を挙げると、Ubuntuのパッケージ管理システムのデータベースがあります。aptコマンドの動作によってこのデータベースは更新されるのですが、同時に2つ以上のaptが動作できたとすると、データベースが破壊されてシステムが危機的状況に陥ります。

このような問題を避けるために、あるリソースに同時に1つの処理しかアクセスできなくする排他制御というしくみがあります。排他制御はOSが提供する重要な機能の一つです。

排他制御が必要なケース

排他制御は直感的ではなく非常に理解が難しいのですが、ここでは比較的理解が簡単なファイルロックというしくみを使って説明します。説明には、あるファイルの中身を読みだして、その中に書いてある数字に1を加えて終了するincというという単純なプログラムを使います。

inc

#!/bin/bash

TMP=$(cat count)
echo $((TMP + 1)) >count

初期状態として、countというファイルがあって、その中には"0"が書き込まれているものとします。

$ cat count
0

この状態でincプログラムを呼び出した後にcountファイルの中身を確認してみましょう。

$ ./inc
$ cat count
1
$ 

当たり前といえば当たり前なのですが、countファイルの中身は0から1つ増えて、1になりました。ではcountファイルの中身をもう一度0に戻してからincプログラムを10000回実行してみます。

$ echo 0 >count
$ for ((i=0;i<10000;i++)) ; do ./inc ; done
$ cat count
10000
$ 

期待通り、countファイルの中身は10000になりました。

ここからが本題です。incプログラムをinc &のように並列実行するとどうなるか、ためしてみましょう。

$ for ((i=0;i<10000;i++)) ; do ./inc & done
...
$ cat count
57
$ 

期待値は10000なのですが、結果は全然違って57になってしまいました。これは複数のincプログラムが並列実行しているために、次のようなことが起こりうるからです。

1. incプログラムAがcountファイルから0を読み出す
2. incプログラムBがcountファイルから0を読み出す
3. incプログラムAがcountファイルに1を書き込む
4. incプログラムBがcountファイルに1を書き込む

これは単なる実験プログラムだからびっくりするだけでいいのですが、これと似たような問題が銀行のシステムのみなさんの預金額を扱う処理で発生したらと思うと背筋が冷えますね。

このような問題を避けるために、countの値を読み出して1を足して、その値をcountファイルにまた書き戻すという一連の処理を、同時に1つのincプログラムからしか実行できないようにする必要あります。これを実現するのが排他制御です。

排他制御の直感的実装

排他制御の文脈では、前述の一連の処理のことをクリティカルセクションと呼びます。クリティカルセクションの中の処理を他の処理に割り込ませない形で一気に実行することをアトミック処理と呼びます。

incプログラムにおいて排他制御を実現するために、lockというファイルの存在有無によって、すでにいずれかの処理がクリティカルセクションに入っているか否かを表現してみるとどうでしょうか。これを実装したのがinc-wrong-lockプログラムです。

inc-wrong-lock

#!/bin/bash

while : ; do
  if [ ! -e lock ] ; then
    break
  fi
done
touch lock
TMP=$(cat count)
echo $((TMP + 1)) >count
rm -f lock

見ての通り、もともとincプログラムでやっていた処理の前にlockファイルの有無を確認して、存在していない場合のみlockファイルを作ってクリティカルセクションに入り、処理が終わったらlockファイルを消して終了します。なんとなくうまくいきそうに見えますね。

では実行してみます。

$ echo 0 >count
$ rm lock
$ for ((i=0;i<10000;i++)) ; do ./inc-wrong-lock & done
...
$ cat count
11
$ 

プログラムの名前からなんとなく想像はされていたとは思いますが、全然だめでした。なぜでしょうか。

inc-wrong-lockプログラムがうまく動作しなかった理由は、次のようなことが起きうるからです。

1. incプログラムAがlockファイルが無いことを確認して先に進む
2. incプログラムBがlockファイルがないことを確認して先に進む
3. incプログラムAがcountファイルから0を読み出す
4. incプログラムBがcountファイルから0を読み出す
5. 以下、incプログラムと同様

この問題を避けるためにはlockファイルの存在を確認して、存在しなかった場合はファイルを作って先に進むという一連の処理をアトミック処理にする必要があります。なんだか堂々巡りをしているようですが、まさにこれと同じようなことを実現するのがファイルロックです。

正しい排他制御

ファイルロックはflock()やfcntl()といったシステムコールを使って、あるファイルについてロック/アンロックという状態を変更します。具体的には以下の処理をアトミックに実行します。

1. ファイルがロックされているかどうかを確認する
2. ロックされていればシステムコールを失敗させる
3. ロックされていなければロックしてシステムコールを成功させる

ここではシステムコールの使い方については説明しませんが、気になる方はman 2 flockを見たり、man 2 fcntlのF_SETLK,F_GETLKの説明を見たりしてください。

ファイルロックのしくみはflockというコマンドによって、シェルスクリプトからも使えるようになっています。使い方は簡単で、以下inc-lockプログラムのように、第一引数に指定したファイルをロックした状態で、第二引数に指定したプログラムを実行してくれます。

inc-lock

#!/bin/bash

flock lock ./inc

ではinc-lockプログラムを並列に10000個実行してみましょう。

$ echo 0 >count
$ touch lock
$ for ((i=0;i<10000;i++)) ./inc-lock & done
...
$ cat count
10000
$ 

ついにうまくいきました。

排他制御は前述の通り非常に複雑なのですが、本記事のこれまでの内容を繰り返し読んだり、ご自身実行の流れを書いてみたりすれば、そのうち理解できるようになるはずです。

ファイルロックはどうやって実現しているのか

前節において、排他制御のしくみを実現する方法の一つにファイルロックがある話をしました。ではファイルロックはどのように実装されているのでしょうか。実はこれは通常C言語のような高級言語のレベルではなく、機械語のレイヤで実現します。

ロックを実装するために次のような仮想的なアセンブリ言語の命令列を書いたとします。

start:
  load r0 mem # (1) memというアドレスのメモリを読み出してr0というレジスタに保存。memの中身が1ならロックされていること、0ならされていないことを示す
  test r0     # (2) r0が0かそれ以外かを確認する
  jmpz enter  # (3) r0が0だった場合、つまりロックされていなければはenterというラベルにジャンプ
  jmp start   # (4) r0が0以外だった場合、つまりロック済みであればstartというラベルに戻る
enter:
  store mem 1 # (5) memに1を書き込む。これでロックをする
  ...
  <クリティカルセクション>
  ...
  store mem 0 # (6) memに0を書き込んでアンロック

ここまでやれば大丈夫かというとそうではありません。二つの処理が(1)を同時に実行した場合、どちらの処理もクリティカルセクションに入っていいと判断してしまいます。このようなことが発生する理由は、(1)~(5)の処理がアトミックになっていないからです。

この問題を解決するために、多くのCPUアーキテクチャにおいて、(1)~(5)に相当する処理をアトミックに実行する命令が用意されています。興味のあるかたは「compare and exchange」、「compare and swap」などのキーワードで検索してみてください。

最初に書いたときは以下の記述がなく、「排他制御を実現するためには上記CPU命令が必須」という書き方をしていましたが、kumagiさんのご指摘により修正しました。ありがとうございました。

高級言語のレベルで排他制御を実現する方法もありますが、上述のCPUの命令よりも時間効率、空間効率が悪いです。興味のあるかたは「ピーターソンのアルゴリズム」で検索してみてください。