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; wherein the fully associative cache memory further comprises: for each MAT of the plurality of MATs, a pointer that points to a most recently replaced one of the valid storage elements associated with the MAT; and wherein when the counter of the MAT of the memory access has not reached the corresponding threshold, the allocation unit finds a next entry after the one pointed to by the pointer that is either invalid or that does not have the MAT of the memory access. 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 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; wherein the fully associative cache memory further comprises: for each MAT of the plurality of MATs, a pointer that points to a most recently replaced one of the valid storage elements associated with the MAT; and wherein when the counter of the MAT of the memory access has not reached the corresponding threshold, the allocation unit finds a next entry after the one pointed to by the pointer that is either invalid or that does not have the MAT of the memory access. for each MAT of the plurality of MATs, a pointer that points to a most recently replaced one of the valid storage elements associated with the MAT; and wherein when the counter of the MAT of the memory access has not reached the corresponding threshold, the allocation unit finds a next entry after the one pointed to by the pointer that is either invalid or that does not have the MAT of the memory access.