US 2002/0120821 A1 · Excessive spin detection and avoidance for systems using a least recently used page replacement algorithm

Abstract

A system and method for eliminating excessive spin conditions on systems implementing a LRU algorithm. This is achieved by limiting the amount of time a LRU task is allowed to run in any one invocation. If this time limit is exceeded before the LRU task has completed its processing, the LRU task will reschedule itself to run after a short time interval, record which frames have been processed so far, release its serialization resources, and exit to open a window of enablement. During this window, other processes that were spinning for the serialization resources can have a chance to run. When the LRU task runs again it will re-obtain the serialization resources and continue processing frames that were not previously processed. The above process will be repeated until all the appropriate frames in the system are in LRU order.

Claims12

Dependent claims

In a computing system implementing a virtual memory system having real memory storage frames for storing virtual pages of data and an auxiliary storage system comprising auxiliary storage slots for storing copies of corresponding virtual pages provided in real storage frames, wherein a page frame table queue comprising frames is traversed in Least Recently Used (LRU) order to determine real frame candidates for storage in said auxiliary storage system, a method for eliminating excessive spin conditions on systems implementing an LRU order queue traversal algorithm, said method comprising:

a) establishing time limit representing an amount of time a LRU task is allowed to run in a queue traversal invocation, wherein processor spin locks are held for serialization purposes during said LRU task invocation;
b) determining whether said time limit has been exceeded before said LRU task has completed its processing;
and, if the time limit has been exceeded,
c) terminating the LRU task and, re-scheduling the LRU task to run after a predetermined time interval, whereby during said time interval, opening up a window of enablement so other processes spinning for the serialization resources may run.

1 more element

In a computing system implementing a virtual memory system having real memory storage frames for storing virtual pages of data and an auxiliary storage system comprising auxiliary storage slots for storing copies of corresponding virtual pages provided in real storage frames, wherein a page frame table queue comprising frames is traversed in Least Recently Used (LRU) order to determine real frame candidates for storage in said auxiliary storage system, a system for eliminating excessive spin conditions on systems implementing an LRU order queue traversal algorithm, said system comprising the steps of:

a system resource manager for establishing time limit representing an amount of time a LRU task is allowed to run in a queue traversal invocation, wherein processor spin locks are held for serialization purposes during said LRU task invocation;
real storage manager for determining whether said time limit has been exceeded before said LRU task has completed its processing;
and, if the time limit has been exceeded, terminating the LRU task and, re-scheduling the LRU task to run after a pre-determined time interval, whereby during said time interval, other processes spinning for the serialization resources may run.

Dependencies are inferred from the claim text.

Excessive spin detection and avoidance for systems using a least recently used page replacement algorithm

Life of this patent

Excessive spin detection and avoidance for systems using a least recently used page replacement algorithm

Life of this patent

Abstract

Claims12