マルチスレッドプログラミングでは、共有リソース上で演算を行う場合、データの競合問題から保護するために同期が必要になります。残念ながら、同期操作のオーバーヘッドは非常に大きく、例えば整数変数に対して加算操作を行った場合、同期操作のオーバーヘッドは加算操作の100倍以上になります。
この同期操作のオーバーヘッドを減らす方法はありますか？より高速なロックや、より高速なアトミック演算が設計できれば、このオーバーヘッドは当然減るでしょう。現在の技術では、最速のアトミック演算は通常の加算演算の何百倍も時間がかかるので、そこから始めるのは非常に困難です。
それでは、ソフトウェアアルゴリズムの観点から同期操作のオーバーヘッドを減らすことができますか？答えはもちろんですが、基本的な考え方は、同期の使用回数を減らすことです、そのような同期0010回の元の使用として、今だけ10回、同期を使用する前に、特定の条件を満たすために変更され、その後、オーバーヘッドの同期は、001回の削減に広がって、効率が大幅に改善されています。共有キューの例では、次の最初の外観。
一般的な共有キューは通常ロックを使用して実装されますが、もちろんCASアトミック操作を使用して実装されることもあります。
ロック保護と共有キューでは、キューのキューにキュー操作のうち、通常、ロックを保護するために使用され、キュー操作の擬似コードのうち、ロック保護の典型的な使用は次のとおりです：
template class <T>
Locked_DeQueue(T &data)
{
Lock();
DeQueue(data); //シリアル・アウト・オブ・キュー操作を呼び出す
Unlock();
}
上記のLocked_DeQueue()関数を使用すると、それが呼び出されるたびに、ロック操作が発生します。実際には、キューが空であるなど、操作をロックする必要があるたびに、実際にはキューの操作を実行する必要はありませんが、ロック操作を回避するために特定のメソッドを取ることができますが、Locked_DeQueue()関数の使用は、ロック操作を回避することはできません上記の関数を改善する必要があります。
キュー操作のロック保護を使用する前に、まずキューが空かどうかを判断し、空でない場合は空とすることは、最も考えやすい点の1つです。コードは以下の通りです：
template class <T>
Locked_DeQueue_a(T &data)
{
If ( !IsEmpty() )
{
Lock();
DeQueue(data); //シリアル・アウト・オブ・キュー操作を呼び出す
Unlock();
}
}
上記のLocked_DeQueue_a()関数の重要な点は、IsEmpty()関数がロック操作を使用してはいけないということです。
IsEmtpy（）関数は、リングキューの配列実装にロック操作を使用しないようにする方法は、例えば、キューが空であるかどうかを判断する際に、基本的な方法は、チームのヘッドポインタがポインタの末尾に等しいかどうかを判断することです。擬似コードは次のとおりです：
INT IsEmpty()
{
Lock()
if ( チーム・ヘッド・ポインタ == 队尾指针 )
{
Unlock();
return 1; //
}
else
{
Unlock();
return 0; //
}
}
チーム先頭ポインタとチーム末尾ポインタは、キューに入ったり出たりする操作中に変更されるので、上記のIsEmpty()関数でロック保護を使用する必要があります。
基本的な方法は、フラグ変数EmptyFlagを設定し、キューインとキューアウトの操作において、キューが空のときはフラグ変数の値を1に、キューが空でないときはフラグ変数の値を0に設定します。このように、キューが空かどうかの判定はEmptyFlagの単一変数で行うことができ、単一変数の読み書きはアトミック操作で実現できるため、読み出し操作は通常の操作と同じです。同期操作はありません。
以下は、EmptyFlag変数を使用して実装されたout-of-queue操作です。
template class <T>
Locked_DeQueue_b(T &data)
{
if ( EmptyFlag )
{
return;
}
Lock();
if ( !EmptyFlag ) //Lock()前, 其他线程可能修改了标志
{
DeQueue(data); //シリアル・アウト・オブ・キュー操作を呼び出す
if ( チーム・ヘッド・ポインタ == 队尾指针 )
{
//キューが出た後、キューは空になり、アトミック操作によってEmptyFlagが1にセットされる。
AtomicIncrement(&EmptyFlag);
}
}
Unlock();
}
キューのis-or-isn't-empty関数は、同期を全く必要としない以下の実装を使用して実装することができます。
INT IsEmpty()
{
return EmptyFlag;
}
Locked_DeQueue_b()関数の実装から、キューが空であったであろう場合、それだけで戻り値のEmptyFlagを判断し、同期が使用される回数を削減し、ロック操作を呼び出すことはありません、そしてIsEmpty()関数では、同期を使用する必要は全くありません、これは頻繁にキューが空であるかどうかを判断する必要がある人のためのものですシナリオの使用、。これは、キューが空かどうかを頻繁に判断する必要があるようなシナリオに向いています。
例えば、動的なタスク・スケジューリングでは、ロック付きの通常の共有キューを使用するとします。あるスレッドのプライベートキューが空になったとき、他のスレッドの共有キューからタスクを盗む必要があります。 盗んだキューが空であればロック操作が発生し、別のキューから別のタスクを盗む必要があり、それでもキューが空であればまたロック操作が必要になり、1回のタスク獲得操作で複数のロック操作とアンロック操作が発生する可能性があります。上記の条件付き同期方式を用いることで、1回のロック操作でタスクを盗むことができます。
上記の条件付き同期パターンは、ステートマシンのような状況に適しており、同期が使用されるのはステートの切り替えが発生したときだけで、他の非ステート変数に対する操作をステート変数に対する操作（EmptyFlagなど）に置き換えることで同期の使用を削減します。
