Patent ID: 8615636

Claim:
A method for replacing an entry in a cache, the method comprising the steps of: receiving a first request for information, and in response, searching for the information within the cache, wherein the cache is configured to utilize a priority based first in first out approach for addition of and removal of cache entries, the entries of the cache being included as part of either a first class of entries that are designated low priority or a second class of entries that are designated high priority, the second class of entries having a second class maximum number of entries such that, when the second class has reached the second class maximum number of entries, the addition of a new entry to the second class results in the removal of an old entry already included in the second class, a priority of the old entry being degraded such that the old entry is re-classified as part of the first class of entries, wherein a low priority entry, included the first class is evicted to allow for the addition of the old entry when the first class has reached a first class maximum number of entries; in response to a cache miss: locating the requested information outside of the cache; selecting an entry, from the first class of entries in the cache, to be evicted from the cache; replacing, into the first class of entries, the entry to be evicted with the requested information; receiving a second request for the information; in response to a cache hit: classifying the entry containing the requested information as belonging to the second class of entries, wherein the second class comprises a plurality of entries that have a higher priority than the entries included in the first class of entries, and are not selectable for eviction during the addition of a low priority entry; re-classifying, as belonging to the first class of entries, another entry from the second class of entries; wherein the entry re-classified as belonging to the first class of entries and the entry classified as belonging to the second class of entries respectively have a priority indicated by at least one bit; and wherein the priority of an entry included in the second class of entries is degraded when an entry included in the first class of entries is selected for eviction.