round robin scheduling java iterators

Question

I have a list of hosts in an array which represnt the servers available to do a particular job. Currently I simply iterate thru the list looking and establish comms with a host to check its not busy. If not I will send a job to it. This approach tends to mean that the first host in the list tends to get hot constanly with the load not balanced properly with the rest of the available hosts.

in pseudocode ..

for (Host h : hosts) {

    //checkstatus
    if status == job accepted break;

}

I'd like to balance this load properly between the hosts i.e first time host one is used 2nd time the method is used host 2. Just wondering that the most elegant solution to this is ??

Thanks W

Organelle

I think probably im after is. Probably implementing a custom iterator for my array list of hosts. Just not that sure how to do this. I have a feeling I need to extend the ArrayList class and implement the ListIterator class does this sound reasonable? – Organelle

Answer 1

You can create a new kind of Iterable that provides round-robin iteration:

public class RoundRobin<T> implements Iterable<T> {
      private List<T> coll;

      public RoundRobin(List<T> coll) { this.coll = coll; }

      public Iterator<T> iterator() { 
         return new Iterator<T>() {
            private int index = 0;

            @Override
            public boolean hasNext() {
                return true;
            }

            @Override
            public T next() {
                T res = coll.get(index);
                index = (index + 1) % coll.size();
                return res;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }

        };
    }
}

You need to define your hosts as RoundRobin<Host>.

[FIXED based on Mirko's comment]

Babbage

Good solution. One small issue though: Performing coll.get(index) is expensive for some lists. I'd say maintaining an iterator and doing next on it, and getting a fresh iterator when you run out of elements is better. – Flightless

Your implementation is buggy, because the first call of next() delivers a null! See: https://mcmap.net/q/756584/-round-robin-scheduling-java-iterators – Thora

Answer 2

Google collections has a utility method Iterators.cycle(Iterable<T> iterable) that does what you want.

Flightless

Perfect pick. Please note this cyclic iterator is not thread-safe (#4494143). – Lutenist

Answer 3

If the list is mutable and the cost of editing it is negligible compared to I/O with the hosts, you can just rotate it:

List<String> list = Arrays.asList("one", "two", "three");
Collections.rotate(list, -1);
System.out.println(list);

Compose

Answer 4

IMHO the standard Java API already provides an easy way to accomplish this, without resorting to external libraries or even the need to implement a custom Iterator. Simply use a Deque where you'd pull the first server, use or discard it, then append it back to the end of the Deque. Here's some sample code:

// Initialize the Deque. This might be at your class constructor. 
Deque<Host> dq = new ArrayDeque<Host>();
dq.addAll(Arrays.asList(hosts)); 

void sendJob(Job myJob) {
    boolean jobInProcess = false;
    do {
        Host host = dq.removeFirst(); // Remove the host from the top
        if(!host.isBusy()) {
            host.sendJob(myJob);
            jobInProcess = true;
        }
        dq.addLast(host); // Put the host back at the end
    } 
    while(!jobInProcess); // Might add another condition to prevent an infinite loop...    
}

This is just a sample where you always ping hosts in round robin order in a loop that only ends when one of them is available and takes the job. You could tinker with it easily to go only around the queue once (use a counter with a max set to the queue's size) or a number of times beofre throwing an exception, or sleeping in between rounds to avoid banging the hosts when all are busy.

Gabby

Answer 5

My RoundRobin implementation, based upon the implementation of https://mcmap.net/q/756584/-round-robin-scheduling-java-iterators

/**
 * 
 * @author Mirko Schulze
 *
 * @param <T>
 */
public class RoundRobin<T> implements Iterable<T> {

    private final List<T>   coll;

    public RoundRobin(final List<T> coll) {
        this.coll = NullCheck.throwExceptionIfNull(coll, "collection is null");
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {

            private int index;

            @Override
            public boolean hasNext() {
                return true;
            }

            @Override
            public T next() {
                this.index = this.index % RoundRobin.this.coll.size();
                final T t = RoundRobin.this.coll.get(this.index);
                this.index++;
                return t;
            }

            @Override
            public void remove() {
                throw new IllegalArgumentException("remove not allowd");
            }
        };
    }
}

And the Junit TestCase

/**
 * 
 * @author Mirko Schulze
 *
 */
@RunWith(JUnit4.class)
public class RoundRobinTest extends TestCase {

    private List<Integer> getCollection() {
        final List<Integer> retval = new Vector<Integer>();
        retval.add(Integer.valueOf(1));
        retval.add(Integer.valueOf(2));
        retval.add(Integer.valueOf(3));
        retval.add(Integer.valueOf(4));
        retval.add(Integer.valueOf(5));
        return retval;
    }

    @Test
    public void testIteration() {
        final List<Integer> l = this.getCollection();
        final Integer frst = l.get(0);
        final Integer scnd = l.get(1);
        final Integer thrd = l.get(2);
        final Integer frth = l.get(3);
        final Integer last = l.get(4);
        Assert.assertEquals("die Collection hat für diesen Test nicht die passende Größe!", 5, l.size());
        final RoundRobin<Integer> rr = new RoundRobin<Integer>(l);
        final Iterator<Integer> i = rr.iterator();
        for (int collectionIterations = 0; collectionIterations < 4; collectionIterations++) {
            final Integer i1 = i.next();
            Assert.assertEquals("nicht das erste Element", frst, i1);
            final Integer i2 = i.next();
            Assert.assertEquals("nicht das zweite Element", scnd, i2);
            final Integer i3 = i.next();
            Assert.assertEquals("nicht das dritte Element", thrd, i3);
            final Integer i4 = i.next();
            Assert.assertEquals("nicht das vierte Element", frth, i4);
            final Integer i5 = i.next();
            Assert.assertEquals("nicht das letzte Element", last, i5);
        }
    }
}

Thora

Answer 6

The implementations provided are buggy and might fail in case of parallelism , the easiest way i did it was to use a circular linked list whose pointer is maintained by an atomic integer.

Aggrieved

Answer 7

If you are creating an Iterator, best to create a defensive copy first and have the iterator work on that.

return new MyIterator(ImmutableList.<T>copyOf(list));

Geum

of should be copyOf; otherwise you have a list that contains as its sole element a reference to the original list. – Interstellar

Yes. Sorry, rather a bad typo there – Geum

Answer 8

    public class RoundRobinIterator<T> implements Serializable {

        private static final long serialVersionUID = -2472203060894189676L;
        //
        private List<T> list;
        private Iterator<T> it;
        private AtomicInteger index = new AtomicInteger(0);

        public RoundRobinIterator(List<T> list) throws NullPointerException {
            super();
            if (list==null) {
                throw new NullPointerException("List is null");
            }
            this.list=Collections.unmodifiableList(list);
        }
        public RoundRobinIterator(Collection<T> values) {
            this(new ArrayList<T>(values));
        }
        public RoundRobinIterator(Iterator<T> values) {
            this(copyIterator(values));
        }
        public RoundRobinIterator(Enumeration<T> values) {
            this(Collections.list(values));
        }



        private final List<T> getList() {
            return list;
        }
        private final Iterator<T> getIt() {
            return it;
        }
        public final int size() {
            return list.size();
        }
        public final synchronized T getNext(Filter<T> filter) {
            int start = index.get();
            T t = getNext();
            T result = null;
            while ((result==null) && (start!=getIndex())) {
                if (filter.accept(t)) {
                    result=t;
                } else {
                    t = getNext();
                }
            }
            return result;
        }

        public final synchronized T getNext() {
            if (getIt()==null) {
                if (getList().size()==0) {
                    index.set(0);
                    return null;
                } else {
                    it = getList().iterator();
                    index.set(0);
                    return it.next();
                }
            } else if (it.hasNext()) {
                index.incrementAndGet();
                return it.next();
            } else {
                if (list.size()==0) {
                    index.set(0);
                    return null;
                } else {
                    index.set(0);
                    it = list.iterator();               
                    return it.next();
                }
            } 
        }

        public final synchronized int getIndex() {
            return index.get();
        }


        private static <T> List<T> copyIterator(Iterator<T> iter) {
            List<T> copy = new ArrayList<T>();
            while (iter.hasNext()) {
                copy.add(iter.next());
            }
            return copy;
        }
    }

Where Filter is

    public interface Filter<T> {

        public boolean accept(T t);

    }

Herat