マルチコアと同期
ロックフリー(lock-free)のアルゴリズムの性質として正しいものはどれか。
- Aどれかのスレッドが途中で止まっても、ほかのスレッドのうち少なくとも1つは処理を進められる
- Bすべてのスレッドが、必ず決まった回数の手順で処理を終える
- Cアトミック命令を一切使わずに、共有データを更新する
答えと解説を見る
正解：A. どれかのスレッドが途中で止まっても、ほかのスレッドのうち少なくとも1つは処理を進められる
ロックを使うと、ロックを持ったスレッドが割り込みや優先度の低さで止まると、ほかの全員が待たされます。ロックフリーのアルゴリズムはCASなどで共有データを直接更新し、あるスレッドが失敗してやり直すのは、ほかの誰かが成功したときだけ、という形にします。そのため、全体としては常にどれかのスレッドが進みます。ただし正しく作るのは難しく、ABA問題などにも注意が必要です。
- A. 正しい。ロックを持ったまま止まるスレッドの問題がありません。
- B. それはより強いウェイトフリーの性質です。
- C. CASなどのアトミック命令を使って作ります。