1. A fully associative cache memory, comprising: an array of storage elements; an allocation unit that allocates the storage elements of the array in response to memory accesses that miss in the cache memory; wherein each of the memory accesses has an associated memory access type (MAT) of a plurality of predetermined MATs, wherein the MAT is received by the cache memory; wherein each valid storage element of the array has an associated MAT of the plurality of predetermined MATs; wherein for each MAT of the plurality of predetermined MATs, the allocation unit maintains: a counter that counts of a number of valid storage elements of the array associated with the MAT; and a corresponding threshold; and wherein the allocation unit allocates into any of the storage elements of the array in response to a memory access that misses in the cache memory, unless the counter of the MAT of the memory access has reached the corresponding threshold, in which case the allocation unit replaces one of the valid storage elements associated with the MAT of the memory access.