Java Tips: かしこいロック

単純なロック: SimpleLock

public class SimpleLock implements ReadWriteLock {
    boolean working = false;

    public void beginRead() { lock(); }
    public void endRead() { unlock(); }

    public void beginWrite() { lock(); }
    public void endWrite() { unlock(); }

    protected synchronized void lock() {
        while (working) {
            try {
                wait();
            } catch (InterruptedException e) {
            }
        }
        working = true;
    }

    protected synchronized void unlock() {
        working = false;
        notifyAll();
    }
}

既に検討したように「かしこいロック」は synchronized ブロックのような単純な仕組みでは実装できないので、ウェイトセットを利用したロック機構を使用する。その準備として、「単純なロック」のウェイトセットを利用した実装 SimpleLock のソースコード(リスト4)を見てみよう。基本的なテクニックなのであらためて詳細は説明しないが、以下に簡単にその仕組みを説明する。

変数 working は誰かがデータにアクセス中かどうか(すなわちアクセス中のスレッドが存在するかどうか)を表すフラグであり、アクセス中なら true、そうでないなら false の値をとる。

ロックを利用するスレッドはこのフラグを見て、処理(読み込みまたは書き込みのデータアクセス)を続行するかウェイトセットに入って待つ(wait())かを決める。処理を続行する場合は、working フラグを立て、処理が終わればフラグを戻す。そしてウェイトセットで待っている他のスレッド達を起こす(notifyAll())。起されたスレッドのうち this のロックを獲得できたスレッドが処理を続行する。

working フラグが立っている間は、他のスレッドが処理を始めようとしても lock() の中で待たされるため、常に一つのスレッドだけがデータを処理する。このように、SimpleLock を使うことでデータにアクセスできるスレッドは一度に一つだけとなり、全てのデータアクセスが排他制御されることになる。

とりあえずの解: SmartLock

public class SmartLock implements ReadWriteLock {
    int readingReaders = 0;
    boolean writing = false;

    public synchronized void beginRead() {
        while (writing) {
            try {
                wait();
            } catch (InterruptedException e) {
            }
        }
        readingReaders++;
    }

    public synchronized void endRead() {
        readingReaders--;
        notifyAll();
    }

    public synchronized void beginWrite() {
        while (writing || readingReaders > 0) {
            try {
                wait();
            } catch (InterruptedException e) {
            }
        }
        writing = true;
    }

    public synchronized void endWrite() {
        writing = false;
        notifyAll();
    }
}

それでは「かしこいロック」の実装の一つ SmartLock のソースコード(リスト 5)を見てみよう。

SimpleLock にあった working フラグは、writing フラグと readingReaders になっている。SmartLock では SimpleLock における「アクセス中」という状態が、より細かく「書き込み中」と「読み込み中」の組合わせで表現されるわけだ。

writing フラグは誰かがデータに書き込み中かどうか(書き込み中のスレッドが存在するかどうか)を表すフラグであり、書き込み中なら true、そうでないなら false の値をとる。readingReaders はデータを読み込み中のスレッドの数を表し、0 または正の整数の値をとる。readingReaders が単純なフラグでないのは、SmartLock が読み込みの並列動作を許すためである。読み込み中のスレッドが全員処理を終えたことを確認するためにはそれらのスレッドの数を数えておかなくてはならない。

このロックがどのように動作するかを考える。

まず beginWrite() と endWrite() だけが使用される状況を考えよう。この時 readingReaders は常に 0 であるから、beginWrite() の while 文にある条件 readingReaders > 0 は無くても同じである。ということは、この状況では beginWrite() / endWrite() は、SimpleLock における lock() / unlock() と全く同じ構造を持つことになる(writing フラグは SimpleLock における working フラグに相当)。よって、書き込みアクセス同士は排他制御されることがわかる。

次に beginRead() と endRead() だけが使用される状況を考えよう。この時 writing フラグは常に false であるから、beginRead() の while ループ全体が無くても同じということになる。readingReaders のカウントは行われるが beginRead() も endRead() もこの変数を参照しないので、これも無くても同じである。endRead() の notifyAll() も、wait() するスレッドが存在しない以上無視できる。つまり、この状況では beginRead() / endRead() は何もしていないことになる。よって、読み込みアクセス同士は排他制御されず、無制限に同時実行されることがわかる。

それでは読み込みと書き込みのアクセスが衝突した場合はどうか。まず読み込み中に書き込みしようとした場合を考える。読み込み中のスレッドがあれば readingReaders は正値であるから、書き込もうとしたスレッドは beginWrite() の while ループの中でウェイトセットに入り、待たされることになる。次に、書き込み中に読み込みしようとした場合を考える。この時 writing フラグは true であるから、読み込もうとしたスレッドは beginRead() の while ループの中でウェイトセットに入り、待たされることになる。よって、読み込みアクセスと書き込みアクセスは排他制御され、決して同時には処理されない。

以上の考察から SmartLock は表 1の Read-Write ロックが満たすべき条件を備えてることがわかった。実際にデモプログラムをコマンドライン引数に SmartLock を与えて起動して、アクセス効率が向上していることを実感して欲しい。SimpleLock ではグラフ描画が一つづつ実行されていたのが、SmartLock では二つのグラフ描画が同時に実行されているのがわかるだろう。

これで「読み書き問題」は解決のはず…。しかしこの章のタイトルをもう一度よく見て欲しい。「とりあえずの解」と書いてある。随分不満げな書き方ではないか。一体何がまずいのだろう?

ロックアウトを防ぐ: SmarterLock

実は上の SmartLock に関する考察には重大な落とし穴がある。確かにデータが破壊されたり、不完全なデータが読み込まれることはない。しかし、例えば以下のようなことが起りうるのだ。

悪意のある攻撃者が電子掲示板の運営を妨害しようと考えた。ログデータは SmartLock で守られており破壊することは不可能だ。掲示板サーバには十分な処理能力があり、攻撃者の手持ちの資源(低速回線に繋がった2台の端末)でその能力を使い切ることは不可能だ。しかしこの攻撃者はまんまと攻撃に成功した。彼が攻撃している間、誰も掲示板に書き込みできなくなったのだ。一体彼は何をしたのだろうか?

種明かしをすると、彼は2台の端末に交互に掲示板をリロードさせたのだ。この場合リロードのタイミングが重要になる。片方の端末でのリロードが終わらないうちに、もう片方の端末のリロードを開始する、という操作を交互に繰り返す必要がある。これをシミュレートしたのがデモプログラム ReadAttackTest だ。起動方法は以下の通り。

java -classpath RWLockDemos.jar ReadAttackTest SmartLock

RWLockTest と同様の画面が出るが、ずっとフラットなグラフが表示され、グラフデータが更新されないのがわかるだろう*。ちなみに、この攻撃は SimpleLock には通用しない(コマンドライン引数に SmartLock のかわりに SimpleLock を指定して確かめることができる)。

* このデモは正確なタイミングを完全に維持するようにはなっていない。長時間放置しておくと、アクセスタイミングがだんだんずれてきて、片方のスレッドが休憩中にもう片方のスレッドによる読み込みが終わってしまうことがある。こうなると書き込み側のスレッドが動作できるようになり、グラフデータが更新される。

もう一度 SmartLock のソースコード(リスト5)をよく見て欲しい。beginWrite() の while ループの条件が問題だ。上に述べたような攻撃を受けている間は常に readingReaders > 0 が成り立つので、書き込みしようとしているスレッドは、いくら notifyAll() で起されてもすぐまた while ループの中で待たされてしまい、決して前には進めない。これはロックアウトと呼ばれる現象だ。ロックアウトはデッドロックと異なり計算機が停止してしまうわけではないが、特定の処理が全く実行されなくなる。

public class SmarterLock implements ReadWriteLock {
    int readingReaders = 0;
    int waitingWriters = 0;
    boolean writing = false;

    public synchronized void beginRead() {
        while (writing || waitingWriters > 0) {
            try {
                wait();
            } catch (InterruptedException e) {
            }
        }
        readingReaders++;
    }

    public synchronized void endRead() {
        readingReaders--;
        notifyAll();
    }

    public synchronized void beginWrite() {
        waitingWriters++;
        while (writing || readingReaders > 0) {
            try {
                wait();
            } catch (InterruptedException e) {
            }
        }
        waitingWriters--;
        writing = true;
    }

    public synchronized void endWrite() {
        writing = false;
        notifyAll();
    }
}

この問題を解決したのが、「もっとかしこいロック」 SmarterLock である(リスト6)。SmarterLock は SmartLock の改良型である(リスト中の太字の部分が SmartLock からの変更点である)。新たに waitingWriters という変数が追加されているが、beginWrite() のコードを見ればわかるように、これは書き込みを試みたが beginWrite() 内で待たされてしまったスレッドの数を表すようになっている。

そして beginRead() の while 文の条件に waitingWriters > 0 が追加されている。書き込みを待っているスレッドが存在すれば、読み込みを試みたスレッドもウェイトセットに入って待つのである。これは、待っている書き込みスレッドがあれば、読み込み中のスレッドはそれ以上増えずに減る一方であり、やがては readingReader == 0 になり、再び書き込みスレッドが実行可能になることを意味する。この時、待っている読み込みスレッドはまだ実行できない。waitingWriters > 0 がまだ成り立っているからだ。よって、待っているスレッドの中では、書き込みスレッドが優先的に実行されることになる。

先ほどの ReadAttackTest をコマンドライン引数に SmarterLock を与えて起動すると、もはやこの攻撃が通用しないことが確認できる。

ロックアウトを完全に防ぐ: SmartestLock

しかし、SmarterLock もまだ完全ではない。実は上で述べたリロード攻撃と同様の手順を書き込み操作に適用してロックアウト状態にできるのだ。これをシミュレートしたのがデモプログラム WriteAttackTest だ。起動方法は以下の通り。

java -classpath RWLockDemos.jar WriteAttackTest SmarterLock

このデモではいつまで経ってもグラフ描画が始まらない*。ちなみに、この攻撃は SmartLock や SimpleLock には通用しない。

* このデモもやはり正確なタイミングを完全に維持できないため、長時間放置しておくとグラフ描画が始まることがありうる。

public class SmartestLock implements ReadWriteLock {
    int readingReaders = 0;
    int waitingWriters = 0;
    boolean preferWriter = true;
    boolean writing = false;

    public synchronized void beginRead() {
        while (writing || (preferWriter && waitingWriters > 0)) {
            try {
                wait();
            } catch (InterruptedException e) {
            }
        }
        readingReaders++;
    }

    public synchronized void endRead() {
        readingReaders--;
        preferWriter = true;
        notifyAll();
    }

    public synchronized void beginWrite() {
        waitingWriters++;
        while (writing || readingReaders > 0) {
            try {
                wait();
            } catch (InterruptedException e) {
            }
        }
        waitingWriters--;
        writing = true;
    }

    public synchronized void endWrite() {
        writing = false;
        preferWriter = false;
        notifyAll();
    }
}

多くの文献(例えば [Wei02] や [Khan02])ではこの記事の SmarterLock 相当のものが Read-Write Lock として紹介されているが*、[結城02] では書き込み攻撃にも耐えられる改良版が紹介されている。ここではそれを「最もかしこいロック」 SmartestLock と呼ぼう。リスト7は、SmarterLock の進化形になるように [結城02] を若干改変したものである(太字部分は SmarterLock からの変更点)。

* 元々 Read-Write Lock が書き込みより読み込みが多い状況を想定していることを考えると、読み込み攻撃に似た状況はアクセスが集中したときに偶然発生する可能性が高いのが、書き込み攻撃に似た状況は偶然には起りにくいであろう。そういう意味で SmarterLock で十分とする見方もあるだろう。

SmartestLock では新たに preferWriter というフラグが導入されている。このフラグの役目を考えてみよう。

SmarterLock で書き込み攻撃が成立するのは、処理待ちスレッドの中から待っている書き込みスレッドが優先的に実行されるのが原因である。攻撃中は、そうやって優先的に実行された書き込みスレッドが処理を終える前に、新たな書き込みスレッドが待ち状態になり、そのスレッドが再び優先的に実行されるため、いつまでたっても読み込みスレッドが実行されないのだ。

しかし SmartestLock では preferWriter フラグが巧妙な働きをする。まず、待っている書き込みスレッドが存在し、そのスレッドを待たせていた読み込みスレッドが処理を終えたとする。この時 preferWriter は true であり、beginRead() の while 文の条件 preferWriter && waitingWriters > 0 は真となる。従ってここでは SmarterLock と同様、書き込みスレッドが優先的に実行される。

しかし、書き込みスレッドが処理を終えると、preferWriter は false になるため beginRead() の while 文の条件は逆転し、読み込みスレッドにも実行のチャンスが与えられる。運悪く書き込みスレッドが実行されても、preferWriter は false のままなのでまたチャンスがやってくる。運良く読み込みスレッドが実行されれば preferWriter は true になって再び書き込みスレッド優先になる。このように preferWriter フラグは互いに実行のチャンスを譲り合うように振る舞うため、読み込みが書き込みをロックアウトすることも、書き込みが読み込みをロックアウトすることもない。

最後に RWLockTest, ReadAttackTest, WriteAttackTest の各デモを、コマンドライン引数に SmartestLock を指定して実行してみて欲しい。SmartestLock は SmartLock と同様に効率的に動作し、読み込み・書き込み両方の攻撃にも耐えられるのが確認できるはずだ。