重み付きポーリングアルゴリズム

に質問
Q 1,Q 2,…,Qn n個のキューがあり、各キューには重み値W 1,W 2,…,Wnがあり、そのうちの1つのキューから1つの要素を取り出すたびに、異なるキューから取り出された要素の数の割合が重み値の割合に従うようにする必要がある.
説明する
これは,ネットワークトラフィックスケジューリングシーンにおける「重み付きポーリングスケジューリング」(Weighted Round-Robin Scheduling,WRR)であり,既存のアルゴリズムが利用できる.
簡単にするために、まず最も簡単な状況を考慮して、W 1=W 2=...=Wnでは,「重み付きポーリングスケジューリング」(Round-Robin Scheduling,RR)に劣化し,RR実装は簡単であり,重み値が異なる場合を考慮する.
実装(pythonコード)
RR

# count
N = 3

# Round-Robin Scheduling
def rr_select():
    last = N - 1
    while True:
        current = (last + 1) % N
        last = current
        yield current

rr_test = rr_select()
for i in range(1000):
    print(rr_test.__next__())

Nはキューの個数であり、0〜N−1の数字はこのN個のキューを表す.
RRは各キューから要素を順次取り出し,あまり述べる必要はない.
WRR

# count
N = 3

weight = (60, 30, 10)

#      
def gcd(nums):
    m = nums[0]
    for n in nums[1:]:
        while n != 0:
            m, n = n, m % n
    return m

# Weighted Round-Robin Scheduling
def wrr_select():
    current = N - 1
    current_weight = 0

    while True:
        current = (current + 1) % N
        if current == 0:
            current_weight -= gcd(weight)
            if current_weight <= 0:
                current_weight = max(weight)
        if weight[current] >= current_weight:
            yield current

wrr_test = wrr_select()
for i in range(1000):
    print(wrr_test.__next__())

このアルゴリズムは説明する必要がある.
最初の10要素を取った結果を見てみましょう.

current_weight               
60                 0
50                 0
40                 0
30                 0 1
20                 0 1
10                 0 1 2

すなわち、for i in (0, 1, 2)の小周期毎に、current_weight > weight[i]の場合、iが選択される.current_weightが0に等しい場合、最初から始めます.これは大きな周期です.1つの大きなサイクルは、max(weight)/gcd(weight)の小さなサイクルを含む.
では、このようにして重みの割合に合致していることをどのように証明しますか?
各小週期では,重み値が最も大きいキューから要素を取り出すことが見られ,重み値が最も大きいものを基準とし,重み値が小さいものを直接比較することができる.それは権利値が10であればいいだけで、10は60の1/6で、60分6分で、1部だけが10を与えるべきなので、60は10に下がってやっと10の条件を満たすことを知っています.重み30の同理.
実はmax(weight)とgcd(weight)は別のものを選択することができるが、それらの2つを選択すると最も細粒度の平均を満たすことができ、すなわち任意の10個の連続した中間結果を取り出すたびに、必然的に重み値の割合に従うことができ、最も優れていると考えられる.
ランダム性の考慮
WRRの実行結果は固定されており、ランダム性を考慮する必要がある場合は、追加の作業が必要です.簡単にはキューの順序をランダムにすることができますが、実際の順序は固定されています.実際の必要に応じて一定(ランダム)数の結果を頻繁に一時保存し、ランダムに処理して順次出力することができます.
リファレンス

ポーリングスケジューリングアルゴリズム(Round-Robin Scheduling)

重み付きポーリングアルゴリズム

IPVSのスケジューリングアルゴリズム

Weighted round robin

Windows、Linux、Shell、C、C++、AHK、Python、JavaScript、Luaなどの分野に関する問題を有料で解決し、柔軟に価格を設定し、コンサルティングを歓迎し、微信ly 50247.