いきなりですが、皆さんは排他制御をご存知でしょうか。排他制御は並列コンピューティングにおける概念であり、複数のプロセスが資源を共有して使用する際に、複数のプロセスが同時に資源を使用している状況（競合）が発生しないように制御する手法です。（この分野にはあまり詳しくないのでまさかり等は歓迎します）。
排他制御の一手法としてロックが知られています。この手法では、ある資源を使用するためにはまずその資源のロックを取得する必要があります。そして、資源を使い終わったらロックを解放します。あるプロセスがロックを取得している間は、別のプロセスは同じロックを取得することができません。よって、ロックを取得できたときのみ資源を使用するようにプログラムを書くことによって、資源に対する競合を防ぐことができます。
典型的には、使用したい資源が他のプロセスに使用されている場合、その資源のロックが解放されるまで待つことになります。そうなると、デッドロックの問題が発生します。デッドロックは、簡単に言えば全員が待っていて先に進まない状態です。
食事する哲学者の問題
デッドロックの例として有名なのが食事する哲学者の問題です。Wikipediaの記事が参考になるかもしれません。
この問題の図を作ってみました。下の図では、哲学者たちが円を作っています。そして、哲学者たちの間にフォーク（Font Awesomeのフリーのアイコンから選んだのでナイフとフォークになっていますが）が置いてあります
哲学者は自分の左右にあるフォークを両方使って食事をしようとします。この場合、フォークが資源にあたるわけですね。1つのフォークを2人が同時に使うことはできません。そして、哲学者がフォークを手に取ることがロックの取得にあたります。
哲学者がどのような行動を取るかはバリエーションがありますが、「まず自分の左のフォークを手に取る（左のフォークのロックを取得）→次に右のフォークを手に取る（右のフォークのロックを取得）」という行動を取る場合はデッドロックが起こりうることが知られています。実際、全員が一斉に左のフォークのロックを取得したら下の図のようになります。
フォークに色が付いているのは、同じ色の哲学者によりロックが取得されていることを示しています。哲学者たちは、まず左のフォークのロックを取得することに成功したので、次は右のフォークのロックを取得しようとします。しかし、右のフォークはすでにロックされていますから、解除されるまで待つことになります。全員がこの状態で待機しているため、誰も食事をすることができません。この状態がデッドロックです。
Web Locks API
さて、ここからが本題です。最近の（ブラウザ向け）JavaScriptでは、ロックを制御することができるAPIが提供されています。それがWeb Locks APIです。このAPIの特徴は、同オリジンならば複数のタブ間でロックの制御を行うことができるということです。言い換えると、オリジンレベルでグローバルな排他制御が行えます。つまり、今別のタブがロックを取得しているから自分のタブはロックを取得できないというような状況が起こりえるのです。
もしかしたらWeb Locks APIを知らないという方がいらっしゃるかも知れませんが、心配ありません。この記事ではWeb Locks APIの使い方も後で紹介します。
さて、ロックが使えるということは当然デッドロックも起こせるということです。ということで、 Web Locks APIを使ってデッドロックを実際にやってみました。具体的には、先ほど紹介した食事する哲学者の問題をJavaScriptで実装してみました。
デモ
こちらがデモページです。なお、記事執筆時点ではWeb Locks APIに対応しているのはGoogle Chromeだけなので、Google Chromeで開いてください。（もちろんiOSのChromeはだめです。）
ページを開くと5人の哲学者と5個のフォークがあります。とりあえず左上の「開始」ボタンを押すと5人の哲学者たちが食事を開始します。戦略が「左→右」が選択されていますが、とりあえずそのまま開始するとすぐにデッドロックになると思います。
実装が適当なので、初期化したい場合はページを更新してください。Web Locks APIはページが閉じられたらそのページが持っているロックは全部解放されるという安心安全な仕様なので、ページを更新したらロック状態が初期化できるのがありがたいですね。
戦略を変えてから開始ボタンを押すことで哲学者たちの行動を変えることができます。2つ目の「左→右（開始時に少し待つ）」を選択した場合は、哲学者たちは同時に食事を開始するのではなく開始時間をずらします。これで必ずデッドロックが防げるわけではないはずですが、大抵の場合は動き続けます。
3つ目の「順序付け」は先ほど紹介したWikipediaの記事で「リソース階層による解法」として紹介されている方法で、フォークを取る順番を左→右とするのではなく、フォークにIDをふっておいてIDが小さい方→IDが大きい方とすることでデッドロックが防げるというものです。これは哲学者が同時に動き始めますが、先ほどとは異なりデッドロックとはならないはずです。
なお、先ほども説明したとおり、Web Locks APIのロック機構はオリジン内でグローバルです。なので、先ほどのデモページを複数開いて実行すると、同じフォークを複数タブ間で取り合う挙動になります。この場合でも、全部「順序付け」戦略で動かすとちゃんと止まらずに動き続けます。すごいですね。（他の戦略が混ざるとほとんど一瞬で止まります。）
Web Locks APIの使い方
以降は、まずWeb Locks APIの使い方を説明し、その後先ほどのデモの実装について説明します。
Web Locks APIの基本的な機能は、もちろんロックを取得することです。そのためにはnavigator.locks.requestメソッドを用います。
navigator.locks.request('ロック名', async lock => {
// ロックが取得できたときの処理をここで行う
// Lockオブジェクトからは名前を取得できたりする
console.log(lock.name);
});
このように、最初の引数でロックの名前を文字列で指定します。ロックは文字列で識別され、同じ名前のロックがすでに取得されている場合は待たされることになります。第2引数は、ロックが取得できたときに呼ばれるコールバック関数です。つまり、この関数の中ではロックを取得して資源が占有できていることになります。
この例では、コールバック関数が終了すると取得したロックが自動的に解放されます。正確には、ロックが解放されるのはコールバック関数が返したPromiseが解決されたときです。よく見ると、コールバック関数がasync関数になっており、コールバック関数の返り値がPromiseを返すことが分かります。この例ではコールバック関数はすぐ終了するのでロックはすぐに解放されますが、async関数の中でawait等を使うことで、非同期処理の間ロックを占有し続けることができます。
また、以下のように自分でPromiseを作ることでロックの占有期間を制御できます。
navigator.locks.request('ロック名', () => {
return new Promise(resolve => {
setTimeout(resolve, 3000);
});
});
以下の例はこれを3つ並べてログ出力を付けたものです。実行すると、前のロックが解放されてから次のロックが取得されるという流れが確認できます。
navigator.locks.request('ロック名', () => {
console.log('ロックを取得しました (1)');
return sleep(3000);
});
navigator.locks.request('ロック名', () => {
console.log('ロックを取得しました (2)');
return sleep(3000);
});
navigator.locks.request('ロック名', () => {
console.log('ロックを取得しました (3)');
return sleep(3000);
});
function sleep(time) {
return new Promise(resolve => {
setTimeout(resolve, time);
});
}
以上がWeb Locks APIの基本的な使い方です。先ほどのデモはロック周りはこれだけを使って実装されていますが、他にもロックが取得できなかったら待たずにやめる機能（ifAvailable）や、排他ロックではなく共有ロックにできる機能（mode）、ロック取得待ちの状態をキャンセルできる機能（signal）があります。あと、ロックが取得されていても強制的に奪取できるエスケープハッチ（steal）もあります。詳しくはMDNを参照してください。
デモの解説
先ほどのデモのコードはGitHubを参照してください。解説といっても、基本的には先ほど紹介したWeb Locks APIを使って哲学者たちを実装しているだけですが。
哲学者たちそれぞれiframeを使って設置された異なるページに置かれています。他の哲学者たちのことは見えず、フォークの取得・解放はWeb Locks APIに任せています。ロック名は各フォークごとに異なるものとなっており、例えばフォークID1のロック名はweb_locks_api_sample_fork_1のようにしています。
ページには哲学者だけでなくフォークも設置されていますが、フォークはメインのページ（iframeの外）で描画されています。iframeのページの中の各哲学者は、フォークのロックを取得することに成功したらpostMessageを用いてメインページ（iframeの外）にその旨を伝えます。受け取ったメインページはフォークに色を付けます。また、フォークを解放したときに同様にメッセージを送ります。
ロック取得部分は先ほどのAPIそのままだと少しやりにくいので、ラッパークラスを作成しました（MDNでAdvanced Useとして紹介されている手法です）。具体的には、以下のように使えるLockクラスを作りました（コードはこの辺）。
// ロックを取得（取得できたらPromiseが解決されて新しいLockインスタンスが返る）。
const lock = await Lock.acquire('ロック名');
// ここで処理を行う
// ロックを解放するときはreleaseメソッドを呼ぶ
lock.release();
このLockクラスを使って、例えば左→右の順にフォークのロックを取得する哲学者のコードは以下のように書けます（コード）。this.getForkとthis.releaseForkはLockクラスを使用する処理をさらにラップした関数です。
ポイントは、leftForkLockを取得した後、そのロックを保持したままrightForkLockの取得を待っている点です。デッドロックが発生した場合はここで待ち続けることになります。このコードは全体がwhileループになっており、フォークを使用したら少し休憩したあと再びフォークを取りに行くようになっています。
while (true) {
// First, acquire left fork.
const leftForkLock = await this.getFork(left);
// Then, acquire right fork.
const rightForkLock = await this.getFork(right);
// Use forks for some time.
await randomSleep();
// release forks.
this.releaseFork(right, rightForkLock);
this.releaseFork(left, leftForkLock);
// have interval.
await randomSleep();
}
本質的な部分はこれくらいです。後は画面の表示周りの諸々です（適当に書いたのでコードが汚くてすみません）。
まとめ
この記事では、Web Locks APIを使用して食事する哲学者の問題を実装し、デッドロックを再現してみました。また、ラッパークラス的なものを作りWeb Locks APIを便利に使う例を紹介しました。Web Locks APIを使用するときの参考になれば幸いです。
記事執筆時点ではWeb Locks APIが使用できるのはGoogle Chromeのみなので実戦投入は難しいかもしれませんが、そのうちいい感じに使えるようになるといいですね。
※ Web Locks APIの仕様はまだ確定しておらず、記事で紹介した内容から今後変化する可能性があります。
