java - AtomicBoolean を使用した Java のラウンドロビンスケジューリングアルゴリズム

Question

外部システムにリクエストを送信するときに、厳密なラウンドロビンスケジューリングを実装したいと考えています。2 つの外部システムサーバーがあります。最初のリクエストは「System1」に送信され、2 番目のリクエストは「System2」に送信され、次のリクエストは「System1」に送信される必要があります。

リクエストを送信するサーバーが 2 つしかないため、ブロッキングやコンテキストスイッチを使用せずに最大のパフォーマンスが必要なため、CAS 操作を利用するため、AtomicBoolean を選択しました。

私の実装クラス

1. RoundRobinTest.java

package com.concurrency;

import java.util.Iterator;

public class RoundRobinTest 
{
    public static void main(String[] args) 
    {
        for (int i = 0; i < 500; i++) 
        {
            new Thread(new RoundRobinLogic()).start();
        }
        try 
        {
            // Giving a few seconds for the threads to complete
            Thread.currentThread().sleep(2000);
            Iterator<String> output = RoundRobinLogic.output.iterator();
            int i=0;
            while (output.hasNext()) 
            {
                System.out.println(i+++":"+output.next());
                // Sleeping after each out.print 
                Thread.currentThread().sleep(20);
            }
        } 
        catch (Exception ex) 
        {
            // do nothing
        }
    }

}

2.RoundRobinLogic.java (静的 AtomicBoolean オブジェクトを持つクラス)

package com.concurrency;

import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.atomic.AtomicBoolean;

public class RoundRobinLogic implements Runnable 
{
    private static AtomicBoolean bool = new AtomicBoolean(true);

    public static Queue<String> output = new ConcurrentLinkedDeque<>();

    @Override
    public void run() 
    {
        if(bool.getAndSet(false))
        {
            // Sending the request to first system
            output.add("Request to System1");
        }
        else if(!bool.getAndSet(true))
        {
            // Sending the request to first system
            output.add("Request to System2");
        }       
    }

}

出力：

......................
314:Request to System1
315:Request to System2
316:Request to System1
317:Request to System2
318:Request to System1
319:Request to System1
320:Request to System2
321:Request to System2
322:Request to System1
323:Request to System2
324:Request to System1
325:Request to System2
......................

リクエスト 318 と 319 は同じサーバーに送信されており、このシナリオでは AtomicBoolean が失敗します。私のアプリケーションでは、一度に 1000 ～ 2000 のスレッドが共有オブジェクトにアクセスしている可能性があります。実際のJava並行性から、私は以下を見てきました。

競合レベルが高い場合、ロックはアトミック変数よりもパフォーマンスが優れている傾向がありますが、より現実的な競合レベルでは、アトミック変数がロックよりもパフォーマンスが優れています。これは、ロックが競合に反応してスレッドを一時停止し、共有メモリバス上の CPU 使用率と同期トラフィックを削減するためです。低から中程度の競合で、アトミックはより優れたスケーラビリティを提供します。競合が多い場合、ロックはより優れた競合回避を提供します。(単一 CPU システムでは、CAS ベースのアルゴリズムはロックベースのアルゴリズムよりもパフォーマンスが優れています。これは、読み取り変更書き込み操作の途中でスレッドが横取りされるというまれなケースを除いて、CAS は常に単一 CPU システムで成功するためです。)

今、私は以下の質問があります。

ラウンドロビン要求の送信を実現するために、他の効率的なノンブロッキングの方法はありますか。
競合が激しい場合、AtomicBoolean が失敗する可能性はありますか? 私が理解しているのは、競合が激しいためにパフォーマンス/スループットが低下する可能性があるということです。しかし、上記の例では AtomicBoolean は失敗します。なんで？

score 11 · Accepted Answer

ジョンの答えはさておき、よりクリーンでおそらくわずかに効率的な実装はorRoundRobinLogicを使用します。これにより、の現在の値を新しい値と比較する必要がなくなります。AtomicIntegerAtomicLongAtomicBoolean

class RoundRobinLogic implements Runnable
{
    private static final AtomicInteger systemIndex = new AtomicInteger(1);

    public static final Queue<String> output = new ConcurrentLinkedDeque<>();

    @Override
    public void run()
    {
        if (systemIndex.incrementAndGet() % 2 == 0) {
            // Sending the request to first system
            output.add("Request to System1");
        } else {
            // Sending the request to second system
            output.add("Request to System2");
        }
    }
}

これにより、これを追加のシステムにかなり簡単に拡張できます。

class RemoteSystem
{
    private final String name;

    RemoteSystem(String name)
    {
        this.name = name;
    }

    public String name()
    {
        return name;
    }
}

class RoundRobinLogic implements Runnable
{
    private static final AtomicInteger systemIndex = new AtomicInteger(1);

    private static final RemoteSystem[] systems = new RemoteSystem[] {
        new RemoteSystem("System1"),
        new RemoteSystem("System2"),
        new RemoteSystem("System3"),
        new RemoteSystem("System4"),
    };

    public static final Queue<String> output = new ConcurrentLinkedDeque<>();

    @Override
    public void run()
    {
        RemoteSystem system = systems[systemIndex.incrementAndGet() % systems.length];

        // Sending the request to right system
        output.add("Request to " + system.name());
    }
}

score 4 · Accepted Answer

Queueではなく、実際のシステムへの API を使用していると仮定しましょう。私が見ている問題は次のものに関連しています。

    if(bool.getAndSet(false))
    {
        // Sending the request to first system
        output.add("Request to System1");
    }
    else if(!bool.getAndSet(true))
    {
        // Sending the request to second system
        output.add("Request to System2");
    }

両方の条件が失敗した場合はどうなりますか? そんなことがあるものか？最初に入ると想像してくださいifbool ですtrue。次に、それをfalseに設定しようとしますが、別のスレッドがあなたを打ち負かしたので、false. 次に、を試しますelse if。たどり着いたelse ifときがfalseで、trueに設定されている場合はどうなりますか?別のスレッドを購入しますか? その場合、両方の試行が失敗します。

これを次のようにリファクタリングします。

while(true){
  boolean current = bool.get();
  if(bool.compareAndSet(current, !current){
     if(current){ 
        //send request to first system
     } else {
        //send request to second system
     }
     return;
  }
}

Sean Bright が述べたように、キューに追加しているため、上記のように実装しても、キュー自体は AtomicBoolean との同期の一部ではないため、いくつかの値が正しく表示されない場合があります。

score 1 · Accepted Answer

あなたの要件は基本的に次のとおりです。アトミック操作を実装する

ブール値を評価して反転します (または、モジュロを評価して、一般的なnサーバーの場合はカウンターをインクリメントします) 、および
ステップ 1 の結果に基づいてキューにエントリを挿入します。

手順 1 と 2 を個別にスレッドセーフにすることで、実際にそれを達成することはできません。ステップ 1 と 2 を一緒に同期する必要があります。

動作するはずの簡単な実装を次に示します。

import java.util.LinkedList;
import java.util.Queue;

public class RoundRobinLogic implements Runnable 
{
    private static boolean bool = true;
    public static final Queue<String> OUTPUT = new LinkedList<String>();
    private static final Object LOCK = new Object();

    @Override
    public void run() {
        synchronized (LOCK) {
            OUTPUT.add(bool ? "Request to System1" : "Request to System2");
            bool = !bool;
        }
    }
}

ご質問について：

プロセッサレベルよりも高い 2 つの操作を一緒に同期する必要がある場合、ブロックを回避することはできません。クラスjava.util.concurrent.atomicはマシンレベルのアトミック命令を採用しているため、これらのクラスを使用するコード (通常はプラットフォームによって異なります) をブロックする必要はありません。
あなたの実装でAtomicBooleanは、失敗しませんでした。代わりに、ブール値の読み取りと要素のキューへの追加との間に競合状態が発生しました。

java - AtomicBoolean を使用した Java のラウンド ロビン スケジューリング アルゴリズム

3 に答える 3

Related

Reference

java - AtomicBoolean を使用した Java のラウンドロビンスケジューリングアルゴリズム