Round Robin and AtomicInteger in Java

1. Introduction

Multithreading has been a part of Java since its inception. However, managing concurrent tasks in multithreaded environments remains challenging, especially when multiple threads compete for shared resources. This competition often causes blocking, performance bottlenecks, and inefficient resource usage.

In this tutorial, we’ll build a Round Robin Load Balancer in Java using the powerful AtomicInteger class to ensure thread-safe, non-blocking operations. Along the way, we’ll explore key concepts like round-robin scheduling, context switching, and atomic operations—all crucial for efficient multithreading.

2. Round Robin and Context Switching

Understanding round-robin scheduling and context switching is important before we move forward to implement the same with the AtomicInteger class.

2.1. Round Robin Scheduling Mechanism

Before jumping into the implementation, let’s explore the core concept behind the load balancer: Round Robin Scheduling. This preemptive thread scheduling mechanism allows a single CPU architecture to manage multiple threads using a scheduler that executes each thread for a given time quantum. The time quantum defines the fixed amount of CPU time each thread receives before moving to the back of the queue.

For example, if we have five servers in the pool, the first request goes to server one, the second to server two, and so on. Once server five handles a request, the cycle starts over with server one. This simple mechanism ensures an even distribution of workload.

2.2. Context Switching

Context switching occurs when the system pauses a thread, saves its state, and loads another thread for execution. Although necessary for multitasking, frequent context switching can introduce overhead and reduce system efficiency. The process involves three steps:

• Saving State: The system saves the thread’s state (program counter, registers, stack, and references) in the Process Control Block (PCB) or Thread Control Block (TCB).
• Loading State: The scheduler retrieves the state of the next thread from the PCB or TCB.
• Resuming Execution: The thread resumes execution from where it left off.

Using a non-blocking mechanism like AtomicInteger in our load balancer helps minimize context switching. This way, multiple threads can handle requests simultaneously without creating performance bottlenecks.

3. Concurrency

Concurrency refers to a program’s ability to manage and execute multiple tasks by interleaving their execution in a seemingly non-blocking way. Tasks in a concurrent system aren’t necessarily executed simultaneously, but they appear to be because their execution is structured to run independently and efficiently.

In a single CPU architecture, context switching allows multiple tasks to share CPU time through a time quantum. In a multi-core CPU architecture, threads are distributed across CPU cores and can run truly parallel as well as concurrently. Therefore, concurrency can be broadly defined as a way for a single CPU to execute multiple threads or tasks seemingly at the same time.

4. Introduction to Concurrent Utilities

Java’s concurrency model improved with the introduction of concurrent utilities in Java 5. These utilities provide high-level concurrency frameworks that simplify thread management, synchronization, and task execution.

With features like thread pools, locks, and atomic operations, they help developers manage shared resources more efficiently in multithreaded environments. Let’s explore why and how Java introduced concurrent utilities.

4.1. An Overview of Concurrent Utilities

Despite Java’s robust multithreading capabilities, managing tasks by breaking them into smaller atomic units that can be executed concurrently posed challenges. Subsequently, this gap led to the development of concurrent utilities in Java to better utilize system resources. Java introduced concurrent utilities in JDK 5, offering a range of synchronizers, thread pools, execution managers, locks, and concurrent collections. This API was further expanded with the Fork/Join framework in JDK 7. These utilities are part of the following key packages:

4.2. Common Synchronizers & Thread Pools

The Java Concurrency API offers a set of common synchronizers like Semaphore, CyclicBarrier, Phaser, and many more as a replacement for the legacy way of implementing these synchronizers. Moreover, it provides thread pools inside of ExecutorService to manage a collection of worker threads. This has proved efficient for resource-intensive platforms.

The thread pool is a software design pattern that manages a collection of worker threads. It also provides thread reusability and can dynamically adjust the number of active threads to save resources. Using this design pattern at the base of ExecutorService, Java ensures that every task/thread can be queued when none of the threads are available and can execute the thread once a worker thread is freed.

5. What Is AtomicInteger?

AtomicInteger allows atomic operations on an integer value, enabling multiple threads to update the integer safely without explicit synchronization.

5.1. AtomicInteger vs Synchronized Blocks

Using synchronized blocks locks the shared variable for explicit access, leading to context-switching overhead. In contrast, AtomicInteger provides a lock-free mechanism, boosting throughput in multithreaded applications.

5.2. Non-Blocking Operations and the Compare-And-Swap Algorithm

At the base of AtomicInteger lies a mechanism called Compare-And-Swap (CAS), which is why operations in AtomicInteger are non-blocking.

Unlike traditional synchronization, which uses locks to ensure thread safety, CAS leverages hardware-level atomic instructions to achieve the same goal without locking the entire resource.

5.3. The CAS Mechanism

The CAS algorithm is an atomic operation that checks whether a variable holds a specific value (the expected value). If it does, the value updates with a new one. This process happens atomically—without interruption by other threads. Here’s how it works:

1. Comparison: The algorithm compares the current value in the variable to the expected value
2. Swap: If the value matches, the current value is swapped with the new value
3. Retry on Failure: If the value doesn’t match, the operation retries in a loop until successful

6. Implementing Round Robin Using AtomicInteger

It’s time to put the concepts into practice. Let’s build a Round Robin Load Balancer that assigns incoming requests to servers. To do this, we’ll use AtomicInteger to track the current server index, ensuring that requests are routed correctly even when multiple threads handle them concurrently:

private List<String> serverList; 
private AtomicInteger counter = new AtomicInteger(0);

We have a list of five servers and an AtomicInteger initialized to zero. Additionally, the counter will be responsible for allocating incoming requests to the appropriate server:

public AtomicLoadBalancer(List<String> serverList) {
   this.serverList = serverList;
}

public String getServer() {
    int index = counter.getAndIncrement() % serverList.size();
    return serverList.get(index);
}

The getServer() method actively distributes incoming requests to servers in a round-robin manner while ensuring thread safety. First, it calculates the next server by using getAndIncrement() in the current counter value and applying the modulus operation with the server list size to wrap around when reaching the end. Incrementing the counter atomically like this ensures efficient, non-blocking updates. The order of execution might vary as every thread runs parallelly.

Now, let’s also create an IncomingRequest class that extends the Thread class, directing the request to the correct server:

class IncomingRequest extends Thread {
    private final AtomicLoadBalancer balancer;
    private final int requestId;

    private Logger logger = Logger.getLogger(IncomingRequest.class.getName());
    public IncomingRequest(AtomicLoadBalancer balancer, int requestId) {
        this.balancer = balancer;
        this.requestId = requestId;
    }

    @Override
    public void run() {
        String assignedServer = balancer.getServer();
        logger.log(Level.INFO, String.format("Dispatched request %d to %s", requestId, assignedServer));
    }
}

Since the threads execute concurrently, the output order might vary.

7. Verifying the Implementation

Now we want to verify the AtomicLoadBalancer is distributing requests evenly across a list of servers. So, we start by creating a list of five servers and initialize the load balancer with it. Then, we simulate ten requests using IncomingRequest threads, which represent clients asking for a server:

@Test
public void givenBalancer_whenDispatchingRequests_thenServersAreSelectedExactlyTwice() throws InterruptedException {
    List<String> serverList = List.of("Server 1", "Server 2", "Server 3", "Server 4", "Server 5");
    AtomicLoadBalancer balancer = new AtomicLoadBalancer(serverList);
    int numberOfRequests = 10;
    Map<String, Integer> serverCounts = new HashMap<>();
    List<IncomingRequest> requestThreads = new ArrayList<>();
    
    for (int i = 1; i <= numberOfRequests; i++) {
       IncomingRequest request = new IncomingRequest(balancer, i);
       requestThreads.add(request);
       request.start();
    }
    for (IncomingRequest request : requestThreads) {
        request.join();
        String assignedServer = balancer.getServer();
        serverCounts.put(assignedServer, serverCounts.getOrDefault(assignedServer, 0) + 1);
    }
    for (String server : serverList) {
        assertEquals(2, serverCounts.get(server), server + " should be selected exactly twice.");
    }
}

Once the requests are processed, we collect how many times each server gets assigned. The goal is to ensure that the load balancer distributes the load evenly, so we expect each server to be assigned exactly twice. Finally, we verify this by checking the counts for each server. If the counts match, it confirms that the load balancer is working as expected and distributing requests evenly.

8. Conclusion

By using AtomicInteger and the Round Robin algorithm, we’ve built a thread-safe, non-blocking load balancer that efficiently distributes requests across multiple servers. AtomicInteger’s lock-free operations ensure that our load balancer avoids the pitfalls of context switching and thread contention, making it ideal for high-performance, multithreaded applications.

Through this implementation, we’ve seen how Java’s concurrent utilities can simplify the management of threads and improve overall system performance. Whether we’re building a load balancer, managing tasks in a web server, or developing any multithreaded system, the concepts explored here will help us design more efficient and scalable applications.