US 6,715,039 B1 · Cache slot promotion in a replacement queue cache using determinations of probabilities and costs

Abstract

Techniques and criteria are used in connection with promoting a slot within a cache in the form of a replacement queue. A cache slot may be promoted based on an inequality that considers the following criteria: probability of losing a cache hit, gaining a cache hit, and the price or cost associated with promoting a slot. The foregoing criteria may be used in accordance with a predetermined promotion policy when the replacement queue is in a locked state and an unlocked state, or only when the replacement queue is in a locked state. Different costs may be associated with the state of the replacement queue as locked or unlocked as the replacement queue may be locked in connection with operations that are performed on the replacement queue. The cost associated with a locked replacement queue may be different than the cost associated with an unlocked replacement queue. Different thresholds and values associated with the foregoing criteria may be specified as dynamic system parameters.

Claims48

Dependent claims

A method for determining whether to promote a cache slot within a cache comprising:

determining whether a probability of losing a cache hit is greater than a ratio of a cost associated with promoting said cache slot to the gain of a cache hit;
and
promoting said cache slot in response to determining that said probability is greater than said ratio, said promoting placing said cache slot at a different position within said cache to increase duration of said cache slot being included in said cache.

A method for determining whether to promote a cache slot within a cache comprising:

determining whether a probability of losing a cache hit is greater than a ratio of a cost associated with promoting said cache slot to the gain of a cache hit;
and
promoting said cache slot in response to determining that said probability is greater than said ratio, said promoting placing said cache slot at a different position within said cache to increase duration of said cache slot being included in said cache,
wherein said probability of losing a cache hit is a mathematical product of a first probability multiplied by a second probability, said first probability being a probability of a cache hit occurring after said cache slot is promoted, said second probability being a probability that a read to a portion of storage corresponding to said cache slot occurs after said cache slot is displaced from the cache is said cache slot if not promoted.

1 more element

A computer program product for determining whether to promote a cache slot within a cache comprising:

machine executable code that determines whether a probability of losing a cache hit is greater than a ratio of a cost associated with promoting said cache slot to the gain of a cache hit;
and
machine executable code that promotes said cache slot in response to determining that said probability is greater than said ratio, said promoting placing said cache slot at a different position within said cache to increase duration of said cache slot being included in said cache,
wherein said probability of losing a cache hit is a mathematical product of a first probability multiplied by a second probability, said first probability being a probability of a cache hit occurring after said cache slot is promoted, said second probability being a probability that a read to a portion of storage corresponding to said cache slot occurs after said cache slot is displaced from the cache is said cache slot if not promoted.

1 more element

Dependencies are inferred from the claim text.

Cache slot promotion in a replacement queue cache using determinations of probabilities and costs

Life of this patent

Cache slot promotion in a replacement queue cache using determinations of probabilities and costs

Life of this patent

Abstract

Claims48