A cache to provide data caching in response to data access requests from at least one system device, and a method operating such a cache, are provided. Allocation control circuitry of the cache is responsive to a cache miss to allocate an entry of the multiple entries in the data caching storage circuitry in dependence on a cache allocation policy. Quality-of-service monitoring circuitry is responsive to a quality-of-service indication to modify the cache allocation policy with respect to allocation of the entry for the requested data item. The behaviour of the cache, in particular regarding allocation and eviction, can therefore be modified in order to seek to maintain a desired quality-of-service for the system in which the cache is found.