Class ClockPolicy

  • All Implemented Interfaces:
    ReplacementPolicy

    final class ClockPolicy
    extends java.lang.Object
    implements ReplacementPolicy
    Implementation of a replacement policy which uses the clock algorithm. All the cache entries are stored in a circular buffer, called the clock. There is also a clock hand which points to one of the entries in the clock. Each time an entry is accessed, it is marked as recently used. If a new entry is inserted into the cache and the cache is full, the clock hand is moved until it is over a not recently used entry, and that entry is evicted to make space for the new entry. Each time the clock hand sweeps over a recently used entry, it is marked as not recently used, and it will be a candidate for removal the next time the clock hand sweeps over it, unless it has been marked as recently used in the meantime.

    To allow concurrent access from multiple threads, the methods in this class need to synchronize on a number of different objects:

    • CacheEntry objects must be locked before they can be used
    • accesses to the clock structure (circular buffer + clock hand) should be synchronized on the ArrayList representing the circular buffer
    • accesses to individual Holder objects in the clock structure should be protected by synchronizing on the holder
    To avoid deadlocks, we need to ensure that all threads obtain synchronization locks in the same order. CacheEntry's class javadoc dictates the order when locking CacheEntry objects. Additionally, we require that no thread should obtain any other synchronization locks while it is holding a synchronization lock on the clock structure or on a Holder object. The threads are however allowed to obtain synchronization locks on the clock structure or on a holder while they are locking one or more CacheEntry objects.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private ConcurrentCache cacheManager
      The cache manager for which this replacement policy is used.
      private java.util.ArrayList<ClockPolicy.Holder> clock
      The circular clock buffer which holds all the entries in the cache.
      private java.util.concurrent.atomic.AtomicInteger freeEntries
      The number of free entries.
      private int hand
      The current position of the clock hand.
      private java.util.concurrent.atomic.AtomicBoolean isShrinking
      Tells whether there currently is a thread in the doShrink() method.
      private static float MAX_ROTATION
      How large part of the clock to look at before giving up in rotateClock().
      private int maxSize
      The maximum size of the cache.
      private static int MIN_ITEMS_TO_CHECK
      The minimum number of items to check before we decide to give up looking for evictable entries when rotating the clock.
      private static float PART_OF_CLOCK_FOR_SHRINK
      How large part of the clock to look at before giving up finding an evictable entry in shrinkMe().
    • Constructor Summary

      Constructors 
      Constructor Description
      ClockPolicy​(ConcurrentCache cacheManager, int initialSize, int maxSize)
      Create a new ClockPolicy instance.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void doShrink()
      Try to shrink the clock if it's larger than its maximum size.
      void insertEntry​(CacheEntry entry)
      Insert an entry into the cache.
      private boolean isEvictable​(CacheEntry e, ClockPolicy.Holder h, boolean clearRecentlyUsedFlag)
      Check if an entry can be evicted.
      private ClockPolicy.Holder moveHand()
      Get the holder under the clock hand, and move the hand to the next holder.
      private void removeHolder​(int pos, ClockPolicy.Holder h)
      Remove the holder at the given clock position.
      private ClockPolicy.Holder rotateClock​(CacheEntry entry, boolean allowEvictions)
      Rotate the clock in order to find a free space for a new entry.
      private void shrinkMe()
      Perform the shrinking of the clock.
      int size()
      Get the number of entries allocated in the data structure that holds cached objects.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • MIN_ITEMS_TO_CHECK

        private static final int MIN_ITEMS_TO_CHECK
        The minimum number of items to check before we decide to give up looking for evictable entries when rotating the clock.
        See Also:
        Constant Field Values
      • MAX_ROTATION

        private static final float MAX_ROTATION
        How large part of the clock to look at before giving up in rotateClock().
        See Also:
        Constant Field Values
      • PART_OF_CLOCK_FOR_SHRINK

        private static final float PART_OF_CLOCK_FOR_SHRINK
        How large part of the clock to look at before giving up finding an evictable entry in shrinkMe().
        See Also:
        Constant Field Values
      • cacheManager

        private final ConcurrentCache cacheManager
        The cache manager for which this replacement policy is used.
      • maxSize

        private final int maxSize
        The maximum size of the cache. When this size is exceeded, entries must be evicted before new ones are inserted.
      • clock

        private final java.util.ArrayList<ClockPolicy.Holder> clock
        The circular clock buffer which holds all the entries in the cache. Accesses to clock and hand must be synchronized on clock.
      • hand

        private int hand
        The current position of the clock hand.
      • freeEntries

        private final java.util.concurrent.atomic.AtomicInteger freeEntries
        The number of free entries. This is the number of objects that have been removed from the cache and whose entries are free to be reused without eviction.
      • isShrinking

        private final java.util.concurrent.atomic.AtomicBoolean isShrinking
        Tells whether there currently is a thread in the doShrink() method. If this variable is true a call to doShrink() will be a no-op.
    • Constructor Detail

      • ClockPolicy

        ClockPolicy​(ConcurrentCache cacheManager,
                    int initialSize,
                    int maxSize)
        Create a new ClockPolicy instance.
        Parameters:
        cacheManager - the cache manager that requests this policy
        initialSize - the initial capacity of the cache
        maxSize - the maximum size of the cache
    • Method Detail

      • size

        public int size()
        Description copied from interface: ReplacementPolicy
        Get the number of entries allocated in the data structure that holds cached objects. This number could include empty entries for objects that have been removed from the cache, if those entries are still kept in the data structure for reuse.
        Specified by:
        size in interface ReplacementPolicy
        Returns:
        the number of entries allocated in the cache
      • moveHand

        private ClockPolicy.Holder moveHand()
        Get the holder under the clock hand, and move the hand to the next holder.
        Returns:
        the holder under the clock hand, or null if the clock is empty
      • rotateClock

        private ClockPolicy.Holder rotateClock​(CacheEntry entry,
                                               boolean allowEvictions)
                                        throws StandardException
        Rotate the clock in order to find a free space for a new entry. If allowEvictions is true, an not recently used object might be evicted to make room for the new entry. Otherwise, only unused entries are searched for. When evictions are allowed, entries are marked as not recently used when the clock hand sweeps over them. The search stops when a reusable entry is found, or when more than a certain percentage of the entries have been visited. If there are free (unused) entries, the search will continue until a reusable entry is found, regardless of how many entries that need to be checked.
        Parameters:
        entry - the entry to insert
        allowEvictions - tells whether evictions are allowed (normally true if the cache is full and false otherwise)
        Returns:
        a holder that we can reuse, or null if we didn't find one
        Throws:
        StandardException
      • isEvictable

        private boolean isEvictable​(CacheEntry e,
                                    ClockPolicy.Holder h,
                                    boolean clearRecentlyUsedFlag)
        Check if an entry can be evicted. Only entries that still are present in the cache, are not kept and not recently used, can be evicted. This method does not check whether the Cacheable contained in the entry is dirty, so it may be necessary to clean it before an eviction can take place even if the method returns true. The caller must hold the lock on the entry before calling this method.
        Parameters:
        e - the entry to check
        h - the holder which holds the entry
        clearRecentlyUsedFlag - tells whether or not the recently used flag should be cleared on the entry (true only when called as part of a normal clock rotation)
        Returns:
        whether or not this entry can be evicted (provided that its Cacheable is cleaned first)
      • removeHolder

        private void removeHolder​(int pos,
                                  ClockPolicy.Holder h)
        Remove the holder at the given clock position.
        Parameters:
        pos - position of the holder
        h - the holder to remove
      • doShrink

        public void doShrink()
        Try to shrink the clock if it's larger than its maximum size.
        Specified by:
        doShrink in interface ReplacementPolicy
      • shrinkMe

        private void shrinkMe()
        Perform the shrinking of the clock. This method should only be called by a single thread at a time.