блокировка на ключе кеша

Question

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

У меня есть интерфейс:

public interface KeyLock<K extends Comparable<? super K>> {

  public void lock(K key);

  public void unock(K key);

}

с реализацией по умолчанию:

public class DefaultKeyLock<K extends Comparable<? super K>> implements KeyLock<K> {

  private final ConcurrentMap<K, Mutex> lockMap;

  public DefaultKeyLock() {
    lockMap = new ConcurrentSkipListMap<K, Mutex>();
  }

  @Override
  public void lock(K key) {
    Mutex mutex = new Mutex();
    Mutex existingMutex = lockMap.putIfAbsent(key, mutex);
    if (existingMutex != null) {
      mutex = existingMutex;
    }
    mutex.lock();
  }

  @Override
  public void unock(K key) {
    Mutex mutex = lockMap.get(key);
    mutex.unlock();
  }

}

Это хорошо работает, но карта никогда не очищается. То, что я пока имею для чистой реализации:

public class CleanKeyLock<K extends Comparable<? super K>> implements KeyLock<K> {

  private final ConcurrentMap<K, LockWrapper> lockMap;

  public CleanKeyLock() {
    lockMap = new ConcurrentSkipListMap<K, LockWrapper>();
  }

  @Override
  public void lock(K key) {
    LockWrapper wrapper = new LockWrapper(key);
    wrapper.addReference();
    LockWrapper existingWrapper = lockMap.putIfAbsent(key, wrapper);
    if (existingWrapper != null) {
      wrapper = existingWrapper;
      wrapper.addReference();
    }

    wrapper.addReference();
    wrapper.lock();
  }

  @Override
  public void unock(K key) {
    LockWrapper wrapper = lockMap.get(key);
    if (wrapper != null) {
      wrapper.unlock();
      wrapper.removeReference();
    }
  }

  private class LockWrapper {

    private final K key;

    private final ReentrantLock lock;

    private int referenceCount;

    public LockWrapper(K key) {
      this.key = key;
      lock = new ReentrantLock();
      referenceCount = 0;
    }

    public synchronized void addReference() {
      lockMap.put(key, this);
      referenceCount++;
    }

    public synchronized void removeReference() {
      referenceCount--;
      if (referenceCount == 0) {
        lockMap.remove(key);
      }
    }

    public void lock() {
      lock.lock();
    }

    public void unlock() {
      lock.unlock();
    }
  }

}

Это работает для двух потоков, получающих доступ к одной блокировке ключа, но после введения третьего потока целостность блокировки больше не гарантируется. Есть идеи?

Answer 1

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

Вы можете адаптировать мою реализацию, хотя я реализовал динамическую версию только для удовольствия.На практике это не показалось полезным, поэтому в производстве использовалось только фиксированное.Вы можете использовать функцию hash () из ConcurrentHashMap для обеспечения хорошего распространения.

ReentrantStripedLock in, http://code.google.com/p/concurrentlinkedhashmap/wiki/IndexableCache

Answer 2

Я не покупаю, что это работает для двух потоков. Учтите это:

• (поток A) вызывает блокировку (x), теперь удерживает блокировку x
• переключатель потока
• (Thread B) вызывает lock (x), putIfAbsent () возвращает текущую оболочку для x
• переключатель потока
• (Поток A) вызывает unlock (x), счетчик ссылок оболочки достигает 0 и удаляется с карты
• (поток A) вызывает lock (x), putIfAbsent () вставляет новую оболочку для x
• (резьба A) блокирует новую оболочку
• переключатель потока
• (резьба B) блокирует старую обертку

Как насчет:

• LockWrapper начинается со счетчика ссылок 1
• addReference () возвращает false, если счетчик ссылок равен 0
• в lock (), если существующиеWrapper! = Null, мы вызываем addReference () для него. Если это возвращает false, оно уже было удалено с карты, поэтому мы возвращаемся назад и пытаемся снова из putIfAbsent ()