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

Answer 2

Let's assume you are not using a Queue but an api to an actual system. The issue I see is related to:

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

What if both conditionals fail? How is that possible? Imagine upon entering the first if the bool is true. Then you try to set it to false, but another thread beat you to it so you see false. You then try the else if. Now what if the else if when you get there is false, but set to true buy another thread? In that case both tries will fail.

I would refactor this to look like:

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

---

As Sean Bright mentioned, because your are adding to a queue, even if you implement it like I have above, you may still see some values out of order because the Queue itself is not part of the synchronization with the AtomicBoolean.

Answer 3

Since your requirement is basically: implement an atomic operation that

1. evaluates and flips a boolean (or evaluates a modulo and increments a counter in the generic n servers case) and
2. inserts an entry into a queue based on the result of step 1,

you cannot really accomplish that by making steps 1 and 2 individually thread-safe; you have to synchronize steps 1 and 2 together.

Here's a simple implementation that should work:

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

Regarding your questions:

1. You cannot avoid blocking if you need to synchronize two higher-than-processor-level operations together. Classes in java.util.concurrent.atomic employ machine-level atomic instructions, which is why code that uses these classes (usually, depending on platform) does not need to block.
2. In your implementation, AtomicBoolean did not fail. Instead, there was a race condition between reading the boolean and adding an element into the queue.