pomodoro/archive/round-robin.md

Циклический алгоритм распределения задач

Round-robin (круглая лента) — алгоритм балансировки нагрузки вычислительной системы, распределение задач по кругу между исполнителями. Есть ряд задач m, выполнение которых занимает равное время, и ряд исполнителей n, равных по своим возможностям. Реализация алгоритма на Java 7 с использованием одной карты TreeMap без внешних библиотек.

Класс CircularList<T>

Карта TreeMap
key	Integer — количество обращений.
value	List<T> — список исполнителей.

Конструктор
CircularList(List<T> list)	list — список исполнителей, обязательный параметр.

Доступные методы	Возвращаемое значение
getOne()	T, первый элемент с наименьшим количеством обращений.
getOne(List<T> filter)	T, первый элемент с наименьшим количеством обращений, которого нет в списке отбора.
getOne(T filterIn)	T, указанный элемент независимо от количества обращений.
status(), toString()	String, текущее состояние карты.

Закрытый метод
reset()	void, сбрасываем счётчики при достижении максимума Integer и обновляем карту.

---

CircularList.java

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

// распределение задач по кругу между исполнителями <T>
public class CircularList<T> {
  // ключ — количество обращений, значение — список исполнителей
  private final TreeMap<Integer, List<T>> elements = new TreeMap<>();

  // list — список исполнителей, обязательный параметр
  public CircularList(List<T> list) {
    if (list == null || list.size() == 0) return;
    this.elements.put(0, new ArrayList<>(list));
  }

  // возвращаем первый элемент с наименьшим количеством обращений
  public synchronized T getOne() {
    // вынимаем из карты первую запись с наименьшим количеством обращений
    Map.Entry<Integer, List<T>> entry = this.elements.pollFirstEntry();
    Integer key = entry.getKey();
    List<T> value = entry.getValue();
    // вынимаем из списка первый элемент
    T element = value.remove(0);
    // если в списке ещё что-то осталось — помещаем обратно в карту
    if (value.size() > 0) this.elements.put(key, value);
    // берём из карты следующий список с большим количеством обращений
    List<T> newValue = this.elements.get(key + 1);
    // если его нет — создаём новый список
    if (newValue == null) newValue = new ArrayList<>();
    // добавляем текущий элемент
    newValue.add(element);
    // помещаем обновлённый список в карту
    this.elements.put(key + 1, newValue);
    // если достигнут максимум — сбрасываем счётчики и обновляем карту
    if (Integer.MAX_VALUE - key < 10) this.reset();
    // возвращаем первый элемент с наименьшим количеством обращений
    return element;
  }

  // возвращаем первый элемент с наименьшим количеством
  // обращений, которого нет в списке отбора — filter
  public synchronized T getOne(List<T> filter) {
    // некорректно задан фильтр — отбор не применяется
    if (filter == null || filter.size() == 0) return getOne();
    Integer key = -1;
    List<T> value;
    T element = null;
    // обходим записи карты
    for (Map.Entry<Integer, List<T>> entry : this.elements.entrySet()) {
      key = entry.getKey();
      value = entry.getValue();
      // обходим элементы списка
      for (T el : value) {
        // если элемента нет в фильтре
        if (!filter.contains(el)) {
          // элемент найден
          element = el;
          // удаляем элемент из списка
          value.remove(el);
          // если в списке ничего не осталось — удаляем запись карты
          if (value.size() == 0) this.elements.remove(key);
          // выходим из цикла
          break;
        }
      }
      // если элемент найден — выходим из цикла
      if (element != null) break;
    }
    // если элемент не найден — фильтр не применяется
    if (element == null) return getOne();
    // берём из карты следующий список с большим количеством обращений
    List<T> newValue = this.elements.get(key + 1);
    // если его нет — создаём новый список
    if (newValue == null) newValue = new ArrayList<>();
    // добавляем текущий элемент
    newValue.add(element);
    // помещаем обновлённый список в карту
    this.elements.put(key + 1, newValue);
    // если достигнут максимум — сбрасываем счётчики и обновляем карту
    if (Integer.MAX_VALUE - key < 10) this.reset();
    // возвращаем первый элемент с наименьшим количеством обращений
    return element;
  }

  // возвращаем указанный элемент независимо от количества обращений
  public synchronized T getOne(T filterIn) {
    // некорректно задан фильтр — отбор не применяется
    if (filterIn == null) return getOne();
    // обходим записи карты
    for (Map.Entry<Integer, List<T>> entry : this.elements.entrySet()) {
      Integer key = entry.getKey();
      List<T> value = entry.getValue();
      // обходим элементы списка
      for (T element : value) {
        // если элемент найден
        if (filterIn.equals(element)) {
          // удаляем этот элемент из списка
          value.remove(element);
          // если в списке ничего не осталось — удаляем запись карты
          if (value.size() == 0) this.elements.remove(key);
          // берём из карты следующий список с большим количеством обращений
          List<T> newValue = this.elements.get(key + 1);
          // если его нет — создаём новый список
          if (newValue == null) newValue = new ArrayList<>();
          // добавляем текущий элемент
          newValue.add(element);
          // помещаем обновлённый список в карту
          this.elements.put(key + 1, newValue);
          // если достигнут максимум — сбрасываем счётчики и обновляем карту
          if (Integer.MAX_VALUE - key < 10) this.reset();
          // возвращаем отфильтрованный элемент
          return element;
        }
      }
    }
    // если элемент не найден — фильтр не применяется
    return getOne();
  }

  // возвращаем текущее состояние карты
  public synchronized String status() {
    return elements.toString();
  }

  @Override
  public synchronized String toString() {
    return elements.toString();
  }

  // сбрасываем счётчики и обновляем карту
  private synchronized void reset() {
    List<T> newList = new ArrayList<>();
    while (this.elements.size() > 0)
      newList.addAll(this.elements.pollFirstEntry().getValue());
    this.elements.put(0, newList);
  }
}

---

Test.java

import java.util.Arrays;
import java.util.List;

// быстрое тестирование — запускаем методы в одном потоке
class Test {
  public static void main(String[] args) {
    List<String> executors = Arrays.asList("A", "B", "C", "D");
    CircularList<String> list = new CircularList<>(executors);
    System.out.println(list);
    // {0=[A, B, C, D]}
    for (int i = 0; i < 10; i++)
      System.out.print(list.getOne(Arrays.asList("A")) + " ");
    // B C D B C D B C D B 
    System.out.println();
    System.out.println(list.status());
    // {0=[A], 3=[C, D], 4=[B]}
    for (int i = 0; i < 3; i++)
      System.out.print(list.getOne("D") + " ");
    // D D D 
    System.out.println();
    System.out.println(list.status());
    // {0=[A], 3=[C], 4=[B], 6=[D]}
    for (int i = 0; i < 14; i++)
      System.out.print(list.getOne() + " ");
    // A A A C A B C A B C A D B C 
    System.out.println();
    System.out.println(list.status());
    // {6=[A], 7=[D, B, C]}
  }
}

---

Test2.java

import java.util.Arrays;
import java.util.List;

// долгое тестирование — запускаем методы в многопоточном режиме
class Test2 {
  public static void main(String[] args) {
    final List<String> executors = Arrays.asList("A", "B", "C", "D");
    final CircularList<String> list = new CircularList<>(executors);
    Runnable r1 = new Runnable() {
      @Override
      public void run() {
        for (int i = 0; i < 1000; i++) {
          String test = list.getOne(Arrays.asList("A"));
          if (!executors.contains(test))
            System.out.println("Error!");
        }
      }
    };
    Runnable r2 = new Runnable() {
      @Override
      public void run() {
        for (int i = 0; i < 300; i++) {
          String test = list.getOne("D");
          if (!executors.contains(test))
            System.out.println("Error!");
        }
      }
    };
    Runnable r3 = new Runnable() {
      @Override
      public void run() {
        for (int i = 0; i < 1400; i++) {
          String test = list.getOne();
          if (!executors.contains(test))
            System.out.println("Error!");
        }
      }
    };
    long time = System.currentTimeMillis();
    for (int i = 0; i < 4000000; i++) {
      new Thread(r1).start();
      new Thread(r2).start();
      new Thread(r3).start();
      if (i % 1000000 == 0) {
        System.out.print(list.status() + " :: ");
        System.out.println(System.currentTimeMillis() - time);
      }
    }
    System.out.print(list.status() + " == ");
    System.out.println(System.currentTimeMillis() - time);
    // {0=[D], 1=[B, C, A]} :: 3
    // {674162345=[A], 674162346=[B, C], 674163331=[D]} :: 953920
    // {1348883478=[A], 1348883589=[C], 1348883590=[B], 1348884772=[D]} :: 1912645
    // {2024396005=[A], 2024396024=[B, C], 2024396481=[D]} :: 2878158
    // {551625032=[A], 551625033=[B, C], 551625061=[D]} == 3847930
  }
}

---

© Головин Г.Г., Код с комментариями, 2023