スーパーマリオブラザーズで学ぶ「スレッド」

コンピュータープログラムにおける「スレッド」という概念を、ジョシュア氏が横スクロールアクションゲームの代名詞であるスーパーマリオブラザーズを使って解説しています。

What Threads Are, Part 2 - by Joshua - Pretty Good Blog
https://prettygoodblog.com/p/what-threads-are-part-2

ジョシュア氏はスーパーマリオブラザーズをスレッドとして使ったマルチスレッドエミュレーションを構築しました。このマルチスレッドエミュレーションでは3つのスレッド(3つの異なるスーパーマリオブラザーズ)が実行されており、それぞれが異なるインスタンスとして実行されています。

エミュレーターは定期的にスレッドを切り替えており、その様子はゲームのインスタンスの切り替わりとして表現されます。なお、各スレッドの違いがわかるように、スーパーマリオブラザーズのゲーム画面は異なるカラー(紫・青・緑)で補正されているため、動画を再生すると画面の色味が絶えず変化します。

スーパーマリオブラザーズをスレッドとして使ったマルチスレッドエミュレーションその1 - YouTube

動画の再生が始めるとマルチスレッドがスタート。具体的には、スクリプトが3つのセーブステートを作成し、それぞれがゲームの現在の状態を表しています。次に3つのスレッドを作成し、それぞれに保持する保存状態を与えます。

続いて、スレッドスケジューラが起動。スレッドスケジューラの仕事は単純にスレッドの切り替えを行うのみ。ただし、以下の条件に従ってスレッドの切り替えが行われます。

◆160フレームごとに新しいスレッドに切り替える
・次のスレッドは、理想的には順番通り(1、2、3、1、2、3……)。
・ただし、KILLED、BLOCKED(ブロック解除できない場合)、SLEEPING(ウェイクアップする時間でない場合)のスレッドはスキップ。

◆新しいスレッドに切り替える際の条件
1：スレッドのセーブ状態を現在のゲーム状態で更新
2：新しいスレッドの保存状態をロード
3：どのスレッドにいるかを反映してゲームのカラーパレットを更新

これは動画の最初の部分で見られる内容です。各スレッドが同時に開始され(World 1-1の読み込み画面)、各スレッドが定期的に入れ替わる様子が「画面の色の変化」および「場面の変化」でよくわかります。基本的に3つのスーパーマリオブラザーズが同時にプレイされているだけなのですが、実際にアクティブなのは1つのみです。

特定の領域または機能が同期プリミティブをアクティブ化するように設定することで、スレッド境界と物理的に対話することが可能になったとジョシュア氏は説明。具体的には、以下の3つを設定したそうです。

・スレッドアクティブ時、マリオが3つのブロックの上に立っている場合、そのマリオが立ち去るまで他のスレッドへの切り替えは実行されません。(割り込み無効)
・土管には一度に1人のマリオしか入れません。(ミューテックス)
・マリオがゴールフラッグに触れると、他のすべてのマリオがゴールフラッグに触れるまでゲームが一時停止します。(条件変数)

World 1-1の場合、赤い網掛け部分が「割り込み無効」が適用されるエリア、黄色い網掛け部分(中に入れる土管)が「ミューテックス」が適用されるエリア、緑の網かけ部分が「条件変数」が適用されるエリアです。

なお、マリオが敵を倒すとスレッドは300フレームの間スリープ状態になります。動画ではわかりづらいですが、スリープ状態のスレッドは必ずしも時間通りに復帰するわけではなく、スレッドスケジューラが次に実行を決定するまで待機する必要があります。

ジョシュア氏によると、このエミュレーターには通常のCPUにスレッドを追加するのと同じ方法でスレッドを追加しているそうです。つまり、「(A)マシンの現在の状態を保存」、「(B)必要に応じて将来的にそれをロードできるメカニズムを巧みに活用」します。なお、エミュレーター自体はスレッド向けに設計されておらず、スレッドという概念も存在しません。

ジョシュア氏のマルチスレッドエミュレーションでは、実際のデッドロック(AがXを保持、BがYを保持、AがYを取得しようとする一方でBがXを取得しようとする)が発生する可能性がある状況を設定していませんが、実際に起きた場合はスレッドスケジューラによって処理されます。

実行できるスレッドがない場合(デッドロックの場合、すべてのスレッドが停止していたり、すべてのスレッドがスリープしていたりするなど)、スレッドスケジューラはゲームを停止し、エラーメッセージを表示します。

デッドロック的な状況が発生する例としては、ミューテックス(すべてのマリオが土管に入るのを待っている状態)で、土管内のマリオが死んでしまうケースが挙げられます。

以下が擬似的にデッドロックを再現した際の動画。土管の中でマリオが死ぬことはないため、ゲーム時間を高速化し、タイムアップすることでデッドロックに陥っています。

スーパーマリオブラザーズをスレッドとして使ったマルチスレッドエミュレーションその2 - YouTube

そして、スレッドスケジューラがより頻繁に実行されるとどうなるかを示したのが以下の動画。なお、以下の動画はてんかん発作を起こす可能性があるため、再生は自己責任でお願いします。

【てんかん発作を起こす可能性があるため閲覧注意】スーパーマリオブラザーズをスレッドとして使ったマルチスレッドエミュレーションその3 - YouTube

ジョシュア氏がスーパーマリオブラザーズをスレッドとして使ったマルチスレッドエミュレーションをどのように実現したのかは、以下の通り。

最初、ジョシュア氏はオープンソースのNES(海外版ファミリーコンピュータ)エミュレーターを探し、ソースコードにマルチスレッドエミュレーション要素を直接追加するつもりだったそうです。そんな中で発見したのが、NESエミュレーターのFCEUXです。FCEUXに数百行のLuaを追加することで、「ミューテックス」「条件変数」「割り込みマスク」「スリープ」などをサポートする正当なスレッドスケジューラが完成しました。

なお、ジョシュア氏が自作したスクリプトは以下のリンクからチェックできます。

pastebin.com/raw/vrDVjqHb
https://pastebin.com/raw/vrDVjqHb

ジョシュア氏は自作したマルチスレッドエミュレーションについて、「スレッド優先順位やアイドルタスク、セマフォ、公平性アルゴリズム、動的スレッド生成、ミューテックスの待機リストの追跡、収益化といった機能をサポートしていないため、優れたスレッドスケジューラではありません。ひどく非効率で、非常に面倒ですが、気に入っています」と記しています。