負荷分散アルゴリズムの分類の詳細な説明

負荷分散により、ネットワーク パフォーマンスとネットワーク動作環境を効果的に改善できます。では、負荷分散とは正確には何であり、どのように分類するのでしょうか。以下の紹介を見てみましょう。以下の紹介を通じて、負荷分散アルゴリズムの基本的な概念の分類と関連内容を理解できます。

負荷分散

システムのパフォーマンスを向上させるために、負荷は複数のコンピュータ間で合理的に分散され、各コンピュータの負荷が基本的に均衡化されます。この形式のコンピューティング パワー共有は、通常、負荷分散または負荷共有と呼ばれます。一般的に言えば、「負荷分散」の目的は、各コンピュータ間の負荷を基本的に均衡化することであり、「負荷共有」は単に負荷を再分配することを意味します。

負荷分散には、静的負荷分散と動的負荷分散の 2 種類があります。システム負荷の平均情報のみを使用し、システムの現在の負荷状態を無視する方法は、静的負荷分散と呼ばれます。システムの現在の負荷状態に応じてタスクの分割を調整する方法は、動的負荷分散と呼ばれます。

負荷の不均衡は主に次の原因で発生します。

一部のアルゴリズムの反復サイズは固定されていませんが、反復サイズはコンパイル時に取得できます。
一部のアルゴリズムの反復サイズは固定されておらず、反復サイズは処理されるデータに依存し、コンパイル時に取得することはできません。
反復サイズが固定されている場合でも、計算速度に違いを生じさせる変数は多数存在します。

これら 3 つの理由を考慮すると、最初のケースでは、コンパイル時に各反復の作業負荷を推定し、処理ノードの処理能力に応じて反復を分散することができます。これが静的負荷分散の方法です。2 番目と 3 番目のケースでは、動的負荷分散を採用する必要があります。操作中、各処理ノードによるタスクの完了に応じてタスクが動的に移行され、動的負荷分散が実現されます。動的負荷分散では、処理ノードの処理能力を調べる必要があります。その基本的な基礎は、処理ノードの以前の処理速度に基づいて将来の処理速度を予測することです。

負荷分散アルゴリズム

負荷分散アルゴリズムは、次の 3 つのコンポーネントで構成されます。

情報戦略: タスク配置戦略作成者が使用する負荷とタスク量、および情報の配布方法。
転送戦略: タスクとコンピューターの負荷に基づいて、タスクを他のコンピューターに転送して処理するかどうかを決定します。
配置戦略: 処理のために他のコンピュータに転送するのに適したタスクの場合は、タスクを転送する宛先コンピュータを選択します。

負荷分散の 3 つの部分は、それぞれ異なる方法で相互に作用します。配置戦略は、情報戦略によって提供される負荷情報を使用し、タスクが配信戦略によって配信に適していると判断された場合にのみアクションを実行します。

要約すると、負荷分散の目標は、平均タスク応答時間を最短にすること、変化する負荷に適応できること、信頼性の高い負荷分散メカニズムであることです。

負荷分散アルゴリズム: 情報戦略

負荷情報を記述するために使用されるパラメータは次のとおりです。

実行キュー内のタスクの数。
システムコールのレート。
CPU コンテキスト スイッチ レート。
アイドル CPU 時間の割合。
空きメモリのサイズ（K バイト）。

1 分以内の平均負荷。これらの単一の負荷記述パラメータの場合、実行中のキュー内のタスク数を負荷記述パラメータとして使用するのが最も効果的であることが証明されており、つまり、平均タスク応答時間が最も短く、広く使用されています。ただし、システム情報をより包括的にするためにさらに多くのパラメータを収集すると、追加のオーバーヘッドの増加により、望ましいパフォーマンスの向上が達成されないことがよくあります。たとえば、6 つのパラメータのうち 2 つを「AND」または「OR」で組み合わせて得られる平均応答時間は、実際には単一のパラメータの平均応答時間よりも悪くなります。

負荷分散アルゴリズム: 配信戦略

簡単のため、送信戦略を選択する場合、しきい値戦略がよく使用されます。たとえば、Eager らの方法は、タスクをローカルで処理するかどうかを決定するときに、コンピューター間でステータス情報を交換する必要はありません。サービス キューまたは待機中のサービス キューの長さがしきい値を超えると、タスクが送信され、受信したばかりのタスクが送信されます。プロセス移行は、実行中のタスクを移行できるため、受信したばかりのタスクしか送信できない方法を改善したものです。

7 つの負荷分散アルゴリズムをシミュレートして調査すると、その転送戦略はすべてしきい値戦略を採用しています。しきい値戦略は、コンピューター負荷しきい値 Load とタスク実行時間しきい値 TCPU の 2 つのしきい値に基づいています。コンピューター負荷が Load を超え、タスク実行時間が TCPU を超えると、タスクは他のコンピューターに転送されて実行されます。

負荷分散アルゴリズム: 配置戦略

まとめると、配置戦略は以下の4つになります。

◆集中戦略

P 秒ごとに、コンピューターの 1 つが「負荷情報センター」(LIC) として指定され、他のすべての負荷の変化を受信して​​「負荷ベクトル」に集約し、他のすべてのコンピューターにブロードキャストします。コンピューターは、タスクを別のコンピューターに転送して実行するのに適切であると判断した場合、LIC に要求を送信し、現在の負荷値を通知します。LIC は、実行キューの長さが最も短いコンピューターを選択し、タスクが配置されているコンピューターにタスクを送信するように通知します。同時に、宛先ホストの負荷値を 1 増加します。

◆閾値戦略

ランダムにコンピューターを選択し、タスクがそのコンピューターに送信された後、そのコンピューターのタスク キューの長さがしきい値を超えるかどうかを判断します。しきい値を超えていない場合は、タスクを送信します。しきい値を超える場合は、別のコンピューターをランダムに選択して、同じ方法で判断します。適切な送信先コンピューターが見つかるまで、または検出数が静的な値制限 LP を超えるまで、これを続けます。タスクが実際にコンピューターに到着すると、その状態に関係なく処理する必要があります。

◆最短タスクキュー戦略

異なる LP コンピュータをランダムに選択し、各コンピュータのタスク キューの長さをチェックして、タスクはタスク キューの長さが最も短いコンピュータに送信されます。タスクが実際にコンピュータに到着すると、状態に関係なく、宛先コンピュータはタスクを処理する必要があります。この戦略の簡単な改善点は、キューの長さが 0 のコンピュータに遭遇した場合は、このコンピュータが許容可能な宛先コンピュータであると判断できるため、それ以上の検出は実行されないことです。

◆リテンション戦略

タスクがコンピュータを離れる際、コンピュータはローカル負荷をチェックします。負荷がしきい値 T1 未満の場合、他のコンピュータを検出し、負荷が T1 を超える R 台のコンピュータにコンピュータ名を登録し、登録内容をスタックに保存します。タスクが過負荷のコンピュータに到着すると、タスクはスタックの先頭のコンピュータに転送されます。コンピュータの負荷が T1 未満の場合、スタックに保存されているすべてのコンピュータ名がクリアされます。