【OS】Lost Wake Up問題と不可分更新命令について復習

やかんです。

何やら難しそうなタイトルをしてますが、名前がゴツいだけで概念自体はシンプル。

正確に言うと、「僕がシンプルな部分しか理解していない」です。

Lost Wake Up問題について。

この話題については、前回の記事で扱った条件変数の理解が必須となります。悪しからず。

一言で述べると、「『起きなきゃいけない』スレッドが『寝てしまう』という問題」です。

は？

すみません。意味がわからなかったと思うので、下に僕にしかわからない図みたいなものを置いときます。

お前にしかわからんのかい。

Lost Wake Up問題は、「条件変数のapiにおいて、pthread_cond_waitが担う機能（CPUの解放とスレッドのブロック）が分割されている世界線」を考えるとわかりやすいです。

そもそも、pthread_cond_waitはこの2つの機能を不可分に行うから優秀。

この2つ（CPUの解放とスレッドのブロック）が分割されている、つまり、「CPUの解放」と「スレッドのブロック」が一度のCPUの占領で終わらない場合、この2つの処理の間に他のスレッドがCPUを使用することとなります。

具体的に、条件変数的な機能を用いたスレッドAとスレッドBで考えましょう。

スレッドAが条件変数に基づいてCPUを解放する（pthread_mutex_unlock）。
CPUが解放され、スレッドBにCPUリソースが回ってくる。
スレッドBが条件変数に基づいて、ブロックされているスレッドを起こす（blocked -> runnable、すなわちpthread_cond_broadcastなど）。
スレッドBがCPUを解放する。
CPUが解放され、スレッドAにCPUリソースが回ってくる。
スレッドAが条件変数に基づいてスレッドをブロックする。

このケースを考えると、「スレッドBによって、条件変数に基づいて寝ているスレッドが起こされているにもかかわらず、スレッドAが寝てしまう」という問題が生じていることがわかるんじゃないでしょうか。。

述べるの難しい。

まあなんか、そんな感じでLost Wake Up問題については終わろうと思います笑

CPUはプログラムカウンタに従って、命令を1つずつfetchして実行します。

CPUについては理解が浅いので間違っているかもしれないです。。

で、この「1つずつ命令を実行」というところが、不可分更新命令の理解においてまず重要です。「命令の最小単位は何か」という話ですね。

~~不可分更新命令は、「CPUが1度に実行可能な命令の単位以下」の命令です。~~

↑この部分、僕の友達が訂正してくれました。改正バージョンとしては、「不可分更新命令は、OSによって他のスレッドからの割り込みを禁止している命令」となります。プログラムカウンタの1クロックで実行されている命令ではないということですね。

友達は東大電情の子。バチくそ優秀。

まじで訂正ありがたい。。本当にありがとう。

はい、ということで話を不可分更新命令に戻しましょう。

不可分更新命令は、排他制御なしでも不可分に実行可能ということ。

不可分更新命令の例としては、

Test and Set
- あるメモリの値が所望の値かをチェックし、所望な値なら何もせず、所望の値と異なる場合は所望の値に書き換えるという命令。
Compare and Swap
- あるメモリの値が所望の値かをチェックし、所望の値なら何もせず、所望の値と異なる場合は、「所望の値とは異なる新しい任意の値」とメモリの値を交換するという命令。
Fetch and Add
- あるメモリの値を取得し、特定の値を加算するという命令。

などがあります。

ということで、唐突に終わりが来た感ありますが、今回の復習はこれにて終了。次はデッドロックについて簡単に触れたあと、話は変わってページフォルト周辺に取り組もうと思います。

最後まで読みいただき、ありがとうございます。