|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.derby.impl.services.cache.ClockPolicy
final class ClockPolicy
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
usedArrayList
representing the circular
bufferHolder
objects in the clock
structure should be protected by synchronizing on the holderCacheEntry
'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 | |
---|---|
private class |
ClockPolicy.Holder
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 | |
---|---|
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 | |
---|---|
ClockPolicy(ConcurrentCache cacheManager,
int initialSize,
int maxSize)
Create a new ClockPolicy instance. |
Method Summary | |
---|---|
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. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
private static final int MIN_ITEMS_TO_CHECK
private static final float MAX_ROTATION
rotateClock()
.
private static final float PART_OF_CLOCK_FOR_SHRINK
shrinkMe()
.
private final ConcurrentCache cacheManager
private final int maxSize
private final java.util.ArrayList<ClockPolicy.Holder> clock
clock
and hand
must be
synchronized on clock
.
private int hand
private final java.util.concurrent.atomic.AtomicInteger freeEntries
private final java.util.concurrent.atomic.AtomicBoolean isShrinking
doShrink()
method. If this variable is true
a call to doShrink()
will be a no-op.
Constructor Detail |
---|
ClockPolicy(ConcurrentCache cacheManager, int initialSize, int maxSize)
ClockPolicy
instance.
cacheManager
- the cache manager that requests this policyinitialSize
- the initial capacity of the cachemaxSize
- the maximum size of the cacheMethod Detail |
---|
public void insertEntry(CacheEntry entry) throws StandardException
insertEntry
in interface ReplacementPolicy
entry
- the entry to insert (must be locked)
StandardException
- if an error occurs when inserting the entryCacheEntry.setCallback(ReplacementPolicy.Callback)
private ClockPolicy.Holder moveHand()
null
if the clock is
emptyprivate ClockPolicy.Holder rotateClock(CacheEntry entry, boolean allowEvictions) throws StandardException
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.
entry
- the entry to insertallowEvictions
- tells whether evictions are allowed (normally
true
if the cache is full and false
otherwise)
null
if we didn't
find one
StandardException
private boolean isEvictable(CacheEntry e, ClockPolicy.Holder h, boolean clearRecentlyUsedFlag)
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.
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)
Cacheable
is cleaned first)private void removeHolder(int pos, ClockPolicy.Holder h)
pos
- position of the holderh
- the holder to removepublic void doShrink()
doShrink
in interface ReplacementPolicy
private void shrinkMe()
|
Built on Thu 2011-03-10 11:54:14+0000, from revision ??? | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |