このテキストは、運営している韓国のブログを日本語に翻訳したものです。
韓国のブログ：https://yunsuu.notion.site/e379eccd32c545419f0651f743c12c13?v=35310b282de24cc5a292fe45cc498a32&pvs=74
この記事は「Operating Systems: Three Easy Pieces」を読んでまとめた本です。
著者が無料で公開しているので、興味のある方はぜひ読んでみてください。
本にある良い問題は解いてgithubにアップロードしています。
github：https://github.com/yunsuu/ostep-homework-solution
本のリンク：https://pages.cs.wisc.edu/~remzi/OSTEP/
唯一の並行性解決策はロック
ロックは、スレッドがクリティカルセクションを実行するときに他のスレッドがクリティカルセクションに侵入するのを防ぐためのもので、
ロックの実装
単にグローバル変数を設定するようにするとクリティカルセクションが侵入される問題が生じるので、
ハードウェアの援助を得て、アトミックな演算を実装し、この演算を利用してロックを実装する。それがテストアンドセットの演算である。
コンペアアンドスワップはええと…はあ。
この前の実装方法はスピンロックで、単一コアでは大きな欠点がある。
CPUのリソースを無駄にするからです。この問題を改善するロックの実装方法もあります。
この方法はキューにスレッドを入れて、必要な瞬間まで休ませ、必要な瞬間にだけ起こして使う方法で、
ロックの評価
相互排他
クリティカルセクションへのアクセスを適切にブロックしているか
公正性
スターベーションがどれだけ発生していないか
パフォーマンス
- 単一CPU上のロック競争
- マルチCPUでのロック競争
実装方法を調査しましょう。
割り込み制御
void lock() {
DisableInterrupts();
}
void unlock() {
EnableInterrupts();
}
相互排他
クリティカルセクションに進入するとき、現在実行中のスレッド以外のすべての割り込みを制限するため、相互排他が実装されている。
公平性
すべての割り込みを制限するため、他のスレッドへの応答時間を短縮することはできず、公平性が悪い。
特権演算をスレッド内で実行するため、オペレーティングシステムはスレッドを信頼できなければならない。
意図せずにスレッドで無限ループがかかると、オペレーティングシステムは再び制御を取り戻すことができない。
そのため、重要な割り込みを見逃すことがあります。
Only load/store
これはかつてのエンジニアたちが失敗した試みです。load/store方式にはどのような限界があり、その後の方式はどのようにこれを補完したのか見てみましょう。
実装コード
typedef struct __lock_t {
int flag;
} lock_t;
void init(lock_t *mutex) {
// 0 -> lock is available, 1 -> held
mutex->flag = 0;
}
void lock(lock_t *mutex) {
while (mutex->flag == 1) // TEST the flag
; // spin-wait (do nothing)
mutex->flag = 1; // now SET it!
}
void unlock(lock_t *mutex) {
mutex->flag = 0;
}
このコードには2つの問題があります。
問題点1.相互排他が守られないときがある。
2つのスレッドを実行しているときに、スレッド1がロックコードを実行している途中でスレッド2に切り替えられると、運が悪いと次の図のように2つのスレッドが両方ともロックを取得する場合があります。
問題点2. spin-wait方式は性能的に非効率的(特に単一CPUの場合)
spint waitの特性上、無限反復を通じてロックが解除されるまで待つため、単一CPUの場合、ロックが解除されるまで何もできません。
Test-And-set
ロックを実装するためには、必ずアトミックな処理が必要です。つまり、誰もが介入できないタイミングが必要であるという意味です。しかし、これはソフトウェアの協力だけでは難しく、ハードウェアの援助が必要です。
Test-And-setの実装ロジック(c言語ですが、実際にはハードウェアで実装されています)
// Atomic operation. This code can never be executed concurrently.
int TestAndSet(int *old_ptr, int new) {
int old = *old_ptr; // fetch old value at old_ptr
*old_ptr = new; // store 'new' into old_ptr
return old; // return the old value
}
ロックの実装ロジック
typedef struct __lock_t {
int flag;
} lock_t;
void init(lock_t *lock) {
// 0: lock is available, 1: lock is held
lock->flag = 0;
}
void lock(lock_t *lock) {
//Previous value has to be 0 for the lock to be released ->
//The previous thread must have finished using the lock and set flag = 0 for the current thread to escape the infinite loop and be able to execute
while (TestAndSet(&lock->flag, 1) == 1)
; // spin-wait (do nothing)
}
void unlock(lock_t *lock) {
lock->flag = 0;
}
この方式を単一プロセスで正しく使用するためには、プリエンプティブスケジューラが必要です。プリエンプティブスケジューラは、残り時間が最も少ないプロセスやスレッドを優先的に実行します。スピンウェイトは当然、最も低い優先度となるでしょう。そうでなければ、他のプロセス/スレッドがスピンロックを行うことでCPUを永遠に占有してしまうからです。
Compare and Swap
Compare and Swapは基本的にTest and setと同じですが、実装方法が一つ違います。
Test and setは必ず交換するのに対して、Compare and Swapは検査した後、元のものとexpectedが同じであれば交換します。
int CompareAndSwap(int *ptr, int expected, int new) {
int original = *ptr;
if (original == expected)
*ptr = new;
return original;
}
ロックの実装
void lock(lock_t *lock) {
while (CompareAndSwap(&lock->flag, 0, 1) == 1)
; // spin
}
その他のコードはTest and setと同じです。 Test and setよりも強力ですが、その理由はlock-free synchronizationの章で詳しく説明します。
Load-linked and store-conditional
変更しなければ、アドレスはそのままです。
ptrが更新されていなければ、ptrを交換して1を返す。
そうでなければ、0を返す。
int LoadLinked(int *ptr) {
return *ptr;
}
int StoreConditional(int *ptr, int value) {
if (no update to *ptr since LoadLinked to this address) {
*ptr = value;
return 1; // success!
} else {
return 0; // failed to update
}
}
void lock(lock_t *lock) {
while (1) {
while (LoadLinked(&lock->flag) == 1)
; // spin until it’s zero
if (StoreConditional(&lock->flag, 1) == 1)
return; // if set-it-to-1 was a success: all done
// otherwise: try it all over again
}
}
void unlock(lock_t *lock) {
lock->flag = 0;
}