RETAINING STATE INFORMATION OF AN ARRAY OF ELEMENTS BY SUBDIVIDING THE ARRAY INTO GROUPS OF ELEMENTS

Methods improve state information retention when selecting a not-recently-used element in an array of N elements. A first method comprises the steps of subdividing the array of N elements into K groups, selecting a group from among the K groups, selecting an element that is set to a not-recently-used state from the elements in the selected group, and marking the selected element as recently-used. If all the elements in the selected group are marked as recently-used, the method preferably marks all the elements in the selected group, except the selected element, as not-recently-used. Alternately, the method simply marks all the elements in the selected group when all the elements in the selected group are marked as recently-used. The method also preferably cycles through the groups so that a different group is selected each time. A second method comprises the steps of selecting an element that is marked as not-recently-used from the elements in the array, marking the selected element as recently-used and marking all the elements in the array except the selected element as not-recently-used when all the elements in the array are marked as recently-used. A program that comprises components that execute the above methods is embodied on a computer readable medium.