Process VM - Code Cache

Code Cache differs from a conventional cache memory in at least 3 ways:
(1) The cache blocks do not have a fixed size. The size depends on the size of translated target block.
(2) The presence and locations of the blocks are dependent on one another because of chaining. If a block is removed, the links must be updated
(3) there is no backing store. When a block is remove, it must be regenerated.

Replacement strategies include:
(1) LRU - Because of temporal locality, this is often a good strategy for conventional caches. Unfortunately, because of the specific properties of code cache, it is relatively difficult to implement. Firstly, there is overhead to implement structure to track access. Secondly, back points are need to perform delink. Thirdly, blocks are of different size and this results in fragmentation. Because of these, LRU is not typically used for code cache.
(2 Flush when full - most basic algorithm is simply to let the code cache fill and then to flush it completely and start over with an empty cache. There are advantages in this approach. Overtime, the frequently followed paths may change and flishing provides an opportunity to elimnate control paths that have become stale and no longer refelct the common paths through the code. Secondly, flushing may remove orphans and reclaim space. The disadvantage is block must be retranslated from scratch, leading to a high performance overhead immediately after the flush.
(3) Preemptive flush - Many programs operate in phases. A phase change is usually associated with an working set change. When phase change, a new region of source code is being entered and a larger percentage of time is spent in block translations. The code cache can be preemptively flished tomake room for the translation.
(4) Fine grained FIFO - a nonfragmenting algorithm that exploits temporal locality and is not a brite force approach. The code cache is managed as a circular buffers. The oldest n-blocks are replaced to make room large enough for the new block. This scheme overcomes a number of disadvantages of LRU (albiet at a slightly reduced hit rate). It still needs to keep track of chaining via back pointers.
(5) Coarse grain FIFO - partition the cache into large blocks (e.g. a block may be 1/8 of cahce size). with this, backpointer problem can be simplified or eliminated by only maintianing backpointer in block level.