Class ClockPolicy
java.lang.Object
org.apache.derby.impl.services.cache.ClockPolicy
- All Implemented Interfaces:
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
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.-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
Holder class which represents an entry in the cache.Nested classes/interfaces inherited from interface org.apache.derby.impl.services.cache.ReplacementPolicy
ReplacementPolicy.Callback
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final ConcurrentCache
The cache manager for which this replacement policy is used.private final ArrayList
<ClockPolicy.Holder> The circular clock buffer which holds all the entries in the cache.private final AtomicInteger
The number of free entries.private int
The current position of the clock hand.private final AtomicBoolean
Tells whether there currently is a thread in thedoShrink()
method.private static final float
How large part of the clock to look at before giving up inrotateClock()
.private final int
The maximum size of the cache.private static final int
The minimum number of items to check before we decide to give up looking for evictable entries when rotating the clock.private static final float
How large part of the clock to look at before giving up finding an evictable entry inshrinkMe()
. -
Constructor Summary
ConstructorsConstructorDescriptionClockPolicy
(ConcurrentCache cacheManager, int initialSize, int maxSize) Create a newClockPolicy
instance. -
Method Summary
Modifier and TypeMethodDescriptionvoid
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.
-
Field Details
-
MIN_ITEMS_TO_CHECK
private static final int MIN_ITEMS_TO_CHECKThe minimum number of items to check before we decide to give up looking for evictable entries when rotating the clock.- See Also:
-
MAX_ROTATION
private static final float MAX_ROTATIONHow large part of the clock to look at before giving up inrotateClock()
.- See Also:
-
PART_OF_CLOCK_FOR_SHRINK
private static final float PART_OF_CLOCK_FOR_SHRINKHow large part of the clock to look at before giving up finding an evictable entry inshrinkMe()
.- See Also:
-
cacheManager
The cache manager for which this replacement policy is used. -
maxSize
private final int maxSizeThe maximum size of the cache. When this size is exceeded, entries must be evicted before new ones are inserted. -
clock
The circular clock buffer which holds all the entries in the cache. Accesses toclock
andhand
must be synchronized onclock
. -
hand
private int handThe current position of the clock hand. -
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
Tells whether there currently is a thread in thedoShrink()
method. If this variable istrue
a call todoShrink()
will be a no-op.
-
-
Constructor Details
-
ClockPolicy
ClockPolicy(ConcurrentCache cacheManager, int initialSize, int maxSize) Create a newClockPolicy
instance.- Parameters:
cacheManager
- the cache manager that requests this policyinitialSize
- the initial capacity of the cachemaxSize
- the maximum size of the cache
-
-
Method Details
-
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 interfaceReplacementPolicy
- Returns:
- the number of entries allocated in the cache
-
insertEntry
Insert an entry into the cache. If the maximum size is exceeded, evict a not recently used object from the cache. If there are no entries available for reuse, increase the size of the cache.- Specified by:
insertEntry
in interfaceReplacementPolicy
- Parameters:
entry
- the entry to insert (must be locked)- Throws:
StandardException
- if an error occurs when inserting the entry- See Also:
-
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. IfallowEvictions
istrue
, 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 insertallowEvictions
- tells whether evictions are allowed (normallytrue
if the cache is full andfalse
otherwise)- Returns:
- a holder that we can reuse, or
null
if we didn't find one - Throws:
StandardException
-
isEvictable
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 theCacheable
contained in the entry is dirty, so it may be necessary to clean it before an eviction can take place even if the method returnstrue
. The caller must hold the lock on the entry before calling this method.- Parameters:
e
- the entry to checkh
- the holder which holds the entryclearRecentlyUsedFlag
- 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
Remove the holder at the given clock position.- Parameters:
pos
- position of the holderh
- 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 interfaceReplacementPolicy
-
shrinkMe
private void shrinkMe()Perform the shrinking of the clock. This method should only be called by a single thread at a time.
-