A cache shared by multiple clients implements a client specific policy for replacing entries in the event of a cache miss. A request from any client can hit any entry in the cache. For purposes of replacing entries, at least of the clients is restricted, and when a cache miss results from a request by the restricted client, the entry to be replaced is selected from a fixed subset of the cache entries. When a cache misses results from a request by any client other than the restricted client, any cache entry, including a restricted entry, can be selected to be replaced.