A cache may store critical cache lines and non-critical cache lines, and may attempt to retain critical cache lines in the cache by, for example, favoring the critical cache lines in replacement data updates. Multiple levels of criticality may be available for a given cache line and cache circuitry may adjust the criticality value of in response to a criticality event. One or more upper criticality levels may be masked when selecting a victim cache line for replacement.