Tell me about the rules of cache operation.

Cache stores copies of data to speed up access to them. Main rules:

Locality of Reference:
- Temporal Locality: If a data element was used recently, it is likely to be used again soon.
- Spatial Locality: If a data element was used, neighboring elements are also likely to be used soon.
Cache Replacement Policies: Define which data block to remove from the cache when it is full and space is needed for new data. Common policies:
- FIFO (First-In, First-Out): The "oldest" block is removed.
- LRU (Least Recently Used): The block that was least recently accessed is removed.
- LFU (Least Frequently Used): The block that was used least often is removed.
Cache Writing Policies: Define when changes in the cache are synchronized with main memory.
- Write-Through: Data is written simultaneously to the cache and main memory. Ensures consistency but is slower.
- Write-Back: Data is initially written only to the cache. Main memory is updated later when the block is removed from the cache or explicitly marked as "dirty" (modified). Faster but requires change tracking mechanisms.
Cache Miss Handling: Define how the system reacts when requested data is absent in the cache.
- The system fetches data from the next level of memory (e.g., main memory).
- Data is placed into the cache (possibly replacing an existing block), and then provided to the requesting process.
Cache Coherence Rules: Important in multiprocessor systems where multiple processors may have copies of the same data in their local caches. They ensure data consistency across all caches. Examples of protocols: MSI, MESI.
Cache Invalidation/Update Rules: When data is changed in one place (e.g., in a processor's cache), it is necessary to either invalidate (make invalid) the copies in other caches or update them to avoid using stale data.