Как я должен увеличить число для сценария с циклической нарезкой с наименьшим количеством конфликтов?

Question

Если много тем звонят GetNextNumber одновременно со следующим кодом, GetNextNumber вернет на 1 больше раз, чем любые другие числа.

private class RoundRobbinNumber
{
    private int _maxNumbers = 10;
    private int _lastNumber;

    private RoundRobbinNumber(int maxNumbers)
    {
        _maxNumbers = maxNumbers;
    }

    public int GetNextNumber()
    {
        int nextNumber = Interlocked.Increment(ref _lastNumber);
        if (_lastNumber > _maxNumbers)
        {
            Interlocked.CompareExchange(ref _lastNumber, 1, _maxNumbers);
            nextNumber = 1;
        }
        return nextNumber;
    }
}

Есть ли способ сбросить _lastNumber вернуться к одному и надежно вернуть увеличенный номер для каждого вызывающего потока GetNextNumber()без необходимости использовать замок?

Answer 1

Хитрость заключается в том, чтобы выполнять операцию в цикле, пока она не будет успешной. Я приведу общий шаблон для этого подхода в своем ответе здесь.

public int GetNextNumber()
{
  int initial, computed;
  do
  {
    initial = _lastNumber;
    computed = initial + 1;
    computed = computed > _maxNumbers ? computed = 1 : computed;
  } 
  while (Interlocked.CompareExchange(ref _lastNumber, computed, initial) != initial);
  return computed;
}

Answer 2

Ответ Андрея без условных утверждений:

using System;
namespace Utils
{
    public class RoundRobinCounter
    {
        private int _max;
        private int _currentNumber = 0;

        public RoundRobinCounter(int max)
        {
            _max = max;
        }

        public int GetNext()
        {
            uint nextNumber = unchecked((uint)System.Threading.Interlocked.Increment(ref _currentNumber));
            int result = (int)(nextNumber % _max);
            return result;
        }
    }
}

А вот скрипта.net запускает этот код.

Answer 3

Не уверен, что если кому-то поможет, но это может быть еще проще:

class RoundRobinNumber
{
    private int _maxNumbers = 10;
    private int _lastNumber = 0;

    public RoundRobinNumber(int maxNumbers)
    {
        _maxNumbers = maxNumbers;
    }

    public int GetNextNumber()
    {
        int nextNumber = Interlocked.Increment(ref _lastNumber);

        int result = nextNumber % _maxNumbers;  

        return result >= 0 ? result : -result;
    }
}

Answer 4

Обычно циклический перебор используется для выбора элемента из коллекции. Основываясь на ответе Алекса, я сделалRoundRobinCollectionвариант.

      public class RoundRobinCollection<T>
{
    private readonly ReadOnlyCollection<T> _collection;
    private int _currentNumber = -1;

    public RoundRobinCollection(IEnumerable<T> enumerable)
    {
        _collection = new List<T>(enumerable).AsReadOnly();

        if (!_collection.Any())
        {
            throw new InvalidOperationException("Cannot use empty collection for RoundRobinCollection.");
        }
    }

    public T GetNext()
    {
        var index = GetNextIndex();
        return _collection[index];
    }

    private int GetNextIndex()
    {
        // This increments the currentNumber in a Thread-safe way, and deals with exceeding int.MaxValue properly
        var nextNumber = unchecked((uint)Interlocked.Increment(ref _currentNumber));
        return (int)(nextNumber % _collection.Count);
    }
}

Пример использования:

      public class SomeClient
{
    private readonly RoundRobinCollection<ServerConfig> _serverConfigs;

    public SomeClient(List<ServerConfig> serverConfigs)
    {
        _serverConfigs = new RoundRobinCollection<ServerConfig>(serverConfigs);
    }

    public void DoSomething(){
       var serverConfig = _serverConfigs.GetNext();
       // Do something with current serverConfig
    }
}