I am programming CPU cache simulator and I am supposed to implement removing of entries. I will not use LRU but just random.

I am not really clear, when should I call the removing function? When cache (2 or 4 caches) are full and CPU wants to write into cache where all (data and tag) of specific indexes are same? Are there some other possible situations, or maybe I am completely wrong?

Hope you understand my question, if no, please tell me and I will edit my question. Thank you in advance.


Cache lines are evicted :

  • When the OS requests it, it may occur for example in non cache-coherent systems when a peripheral does a DMA transfer (direct transfer from a peripheral to main memory), or if the CPU is shut down to save its state to RAM...

  • When all the ways of the cache are already used for the requested line.

In a write-through cache, new data can be directly loaded, overwriting previous contents. In a write-back cache, if the cache line was modified, it must be written back before loading new data.

There could be other exceptional cases, for example if a parity error is detected and new data must be loaded... But, generally, caches are filled but never emptied.

  • 3
    $\begingroup$ You forgot about coherence invalidations (remote writes), but I think the question was asking about when the replacement policy is applied (which, of course, happens on a insertion/cache miss). $\endgroup$ – Paul A. Clayton Jan 22 '16 at 3:11
  • $\begingroup$ @paul-a-clayton : Oh, yes indeed ! Forgot that. S,E->I in a MESI cache... $\endgroup$ – TEMLIB Jan 22 '16 at 20:36

The simple (possibly, overly simplified) answer is that you need to remove entries whenever a new entry is to be written to the cache, but the cache is full.

That is, if there is a memory access which is a miss and the record is brought to the cache from the main memory, but there is no place to put the new record (all possible places for that record are full), you need to make some room by removing one of the records.

Of course, you should write the record(-to-be-removed) back to the main memory before removing it form the cache, and obviously, you should remove a record that resides in the cache in a place that can be used to place the new record. Note that the cache needs not be completely full -- whatever happens in entries where the new record cannot be mapped to is irrelevant.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.