その他の問題: Livelock と Starvation

1. はじめに

Livelock はマルチスレッドアプリケーションで、2つ以上のスレッドが Deadlock を避けようとするあまりお互いの動きに延々と反応して進まなくなる状況です。 Deadlock の場合はスレッドが固まって何もできないのに対して、Livelock は「生きている」ように見えます：スレッドは動いているけど、誰も有益な仕事をしていません。

狭い廊下で同僚とすれ違おうとしてお互いに何度も下がり合って結局進めない、みたいなイメージです。第三者から見ると面白いけど、プログラムでは最悪です。

例 — Livelock：ドアでのプログラマー

すごく礼儀正しい2人のプログラマーが狭い廊下で向かい合っていて、同時にドアの前に立ちます。どちらも相手に譲ろうとして横に避ける。両方とも「状況が変わってない」と判断してまた譲る――これが無限ループ。誰も止まってはないけど、ドアは誰も通れない。

マルチスレッドだと、あるスレッドがリソースが取れないと判断して後退し、再チェックしてまた後退する…という無限のやり取りになります。

2. 実践での Livelock

同じような状況をコードで作ってみます。例えば2つのリソース（銀行口座など）があって、2つのスレッドが同時にお互いに送金しようとして「もめないように」動いた結果、処理が進まなくなるケースです。

class Account
{
    public int Balance { get; set; }
    public object LockObj { get; } = new object();
}

public class Program
{
    static void Transfer(Account from, Account to, int amount)
    {
        while (true)
        {
            bool lockedFrom = false;
            bool lockedTo = false;
            try
            {
                Monitor.TryEnter(from.LockObj, 100, ref lockedFrom); 
                Monitor.TryEnter(to.LockObj, 100, ref lockedTo);

                if (lockedFrom && lockedTo)
                {
                    from.Balance -= amount;
                    to.Balance += amount;
                    break; // 送金完了！
                }
            }
            finally
            {
                if (lockedFrom) Monitor.Exit(from.LockObj);
                if (lockedTo) Monitor.Exit(to.LockObj);
            }
            // 取れなかった？一歩引いてもう一回試す — 丁寧に！
            Thread.Sleep(1);
        }
    }
    // ... Transfer(A, B, ...); Transfer(B, A, ...); を使って2つのスレッドを起動する
}

この例では、両方のスレッドが何度もロックを取ろうとします。もし両方が常に「ロックが取れない」と見て譲り合いを続けると、永遠に送金が行われません。スケジューラのランダム性に頼るのは堅牢な戦略ではありません。ランダムな待機や backoff を入れて、短い空回しループを Monitor.TryEnter や Thread.Sleep でぐるぐる回さないようにしましょう。

Livelock と Deadlock の比較

3. Starvation（飢餓）：リソースにたどり着けない順番

Starvation（直訳すると「飢餓」）は、あるスレッドや複数のスレッドが常に後回しにされて必要なリソースにアクセスできない状況です。ほかのスレッドが常に先に行ってしまうためです。

Deadlock や Livelock と違い、ここでは誰も永久にブロックされているわけでも永遠に譲っているわけでもありません。ただ単に、あるスレッドだけがずっと「ケーキの一切れ」をもらえない、という状況です。

実例イメージ

社員用レーン（VIP）と一般レーンがある食堂を想像してみてください。VIP レーンは短いけど常に誰かが先に入る。一方の一般客は30分も待って、VIP がまた先に行くのを見ているだけ。これが Starvation です。

4. C# での Starvation：実践とデバッグ

例えば lock を使った場合に、優先度が高いスレッドが常にクリティカルセクションに入り、もう一方が全然入れないケースを考えます。

private static readonly object _locker = new object();

static void Greedy()
{
    while (true)
    {
        lock (_locker)
        {
            Console.WriteLine("貪欲なスレッドがリソースを取得した...");
            Thread.Sleep(10); // ロックを長めに保持する
        }
        Thread.Sleep(1);
    }
}

static void Poor()
{
    while (true)
    {
        lock (_locker)
        {
            Console.WriteLine("貧しいスレッドが入ろうとした...");
        }
    }
}

両方を起動すると、"Greedy"（貪欲）が長くロックを持ってすぐに再取得するので、"Poor"（貧しい）はほとんど中に入れず、事実上リソースを「飢えている」状態になります。実際のシステムでは、優先度が低い、あるいは OS によって頻繁に割り込まれるスレッドが同様の飢餓に陥ることがあります。

どこで Starvation に遭遇するか？

• 低優先度スレッド。
• タスクキューの構成が不適切（公平な FIFO ポリシーがない）。
• ReaderWriterLockSlim のデフォルト設定：writer が稀で reader が途切れず来ると、writer はずっと飢える（reader が Read Lock を取っていて Write Lock を取れない）。

5. Starvation は必ずしもバグじゃないが問題になる

Starvation は Deadlock のようにプログラム全体を止めはしませんが、結果が不公平で予測不能になります：データ処理が偏り、いくつかのタスクが永遠に待たされ、全体のスループットが落ちる。サーバー系では全員に均等なチャンスを与えることが重要なので致命的になり得ます。

Livelock と Starvation を見つけて診断する方法

• CPU 使用率が強く上がっているのに処理が進まない：Livelock の疑い。
• スレッドは動いているが一部のタスクが全く終わらない：Starvation の疑い。
• ログ：特定のスレッドやタスクがリソースを全然取得していないとログに出ていれば、ほぼ間違いなく飢餓。

Livelock を避ける方法

• Monitor.TryEnter のような「譲歩する」non-blocking メソッドだけに頼らない。失敗したらランダムな待機（Thread.Sleep(Random.Next(1, 10)))) を入れてスレッドのタイミングをずらす。
• 短い busy-loop を回し続けないこと。そうすると「引いては試す」ループが無限に続く。
• 設計を変えることも有効：例えば「年長権」みたいなルールを入れて、どちらか一方だけが譲るようにする。

Starvation を避ける方法

• スレッド優先度を監視する：バックグラウンドや高優先度のタスクが常に他を邪魔しないようにする。
• ConcurrentQueue<T> やチャネル、タスクキューなどで公平な FIFO ポリシーを使い、順番に処理する。
• ReaderWriterLockSlim では新しい reader を一時停止して writer を優先させる設定にするなどして、writer がいつか Write Lock を取れるようにする。
• タイムアウトとログを使う：スレッドが長時間ロックを待っているときは警告を出す。
• ロック保持時間を短くし、クリティカルセクションを分散させる。

Deadlock、Livelock、Starvation の比較