排他制御
このような連結リストからノードを削除するには、1つ前のノードにある、次のノードを指すポインタを、削除したいノードの、次のノードを指すように書き換える(例えば、ノード i を削除するには、ノード i-1 のnextポインタをノード i+1 を指すよう書き換える)。このとき、その連結リストを複数プロセスが共有しているなら、2つのプロセスがそれぞれ別のノードを削除しようとして次のような問題を生じる可能性がある。
2つのプロセスはそれぞれノード i と i+1 を同時に削除しようとする。どちらのノードも連結リストの途中にあり、先頭でも最後尾でもないとする。
ノード i-1 のnextポインタはノード i+1 を指すよう書き換えられ、ノード i のnextポインタはノード i+2 を指すよう書き換えられる。
両方の削除処理が完了した状態を見ると、ノード i-1 がノード i+1 を指すよう書き換えられたために、ノード i+1 は連結リストに残ってしまう。
この問題は排他制御を施して複数の状態更新処理が同時に行われないようにすれば解決する。
あるプロセスがロックを獲得したにもかかわらず、そのプロセスが現にCPU上で実行されていないため、実質的にどのプロセスやCPUもクリティカルセクション内の処理を実行していない状態。ロックの目的に照らし合わせると無駄な状態である。ロックの獲得からクリティカルセクション内の処理を開始するまでに遅延が発生したりコンテキストスイッチの回数が増加するため、システムの応答遅延増加や全体性能の劣化を招く。
ロックを解放したプロセスが、そのロックを待ってスリープしているプロセスのいずれかへロックの所有権を直接渡してしまう実装になっていると発生しやすくなる。対策として、ロックを獲得したいプロセスは必ず自分自身でロック獲得を試みる実装にすることにより問題が軽減される。典型例はスピンロックで、ロックを獲得したいプロセスは仕様上決してスリープしない。逆にロック待ちのプロセスがスリープする場合は、スリープ終了からロック獲得までの手順によってはコンボイに陥りやすくなる。
優先度上限プロトコルは優先度がサポートされている環境下にて、優先度継承はロック所有中のプロセスよりも優先度が高いプロセスがロックを獲得しようとした場合に、それぞれこの問題を優先度に依存した別々のアプローチで解決しようとする。ただし、コンボイの本質は「プロセスが現にCPU上で実行中ではないにもかかわらずロックを獲得してしまう」ことにあり、優先度の有無には関係ないため、両者とも問題を直接解決するものではない。スピンロックがコンボイの問題を逃れていることから明らかなように、「プロセスが自力でロックを獲得する」実装に制限することが本質的な解決となる。