Round robin scheduling algorithm in Java using AtomicBoolean

Question

I want to implement a strict round robin scheduling when i send requests to an external system. There are two external system servers. The first request should go to 'System1' and the second request must go to 'System2' and next one to 'System1' and so on.

Since i have only two servers to send the request to, and since i want maximum performance without any blocking and context switch, i have gone for AtomicBoolean since it makes use of CAS operation.

My implementation classes

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(Class with static AtomicBoolean object)

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");
        }       
    }

}

Output:

---

......................
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
......................

---

The requests 318 and 319 had been sent to the same server and AtomicBoolean fails in this scenario. For my application 1000-2000 threads might be accessing the shared object at a time. From Java concurrency in practice, i have seen the below.

at high contention levels locking tends to outperform atomic variables, but at more realistic contention levels atomic variables outperform locks. This is because a lock reacts to contention by suspending threads, reducing CPU usage and synchronization traffic on the shared memory bus. With low to moderate contention, atomics offer better scalability; with high contention, locks offer better contention avoidance. (CAS based algorithms also outperform lock based ones on single CPU systems, since a CAS always succeeds on a single CPU system except in the unlikely case that a thread is preempted in the middle of the read modify write operation.)

Now i have the below questions.

1. Is there any other efficient non-blocking way, to achieve the round-robin request sending.
2. Under heavy contention, is it possible for the AtomicBoolean to fail ? What i understand is that performance/throughput might go down due to heavy contention. But in the above example AtomicBoolean fails . Why ?

Answer 1

As an aside to John's answer, a cleaner and perhaps slightly more efficient implementation of RoundRobinLogic would use AtomicInteger or AtomicLong. This removes the need to compare the current value of the AtomicBoolean with the new value:

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");
        }
    }
}

And this would allow you to extend this to additional systems fairly easily:

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());
    }
}