Disclosed is a circuit which selects one of the elements of a translation lookaside buffer for replacement while excluding all other elements that are eligible for replacement. The circuit divides the entries into major groups and further sub-divides each major group into minor groups of elements. Each element within each minor group examines the previous major group, the previous minor group, and the previous entry within the minor group to determine whether an element has already been selected. The circuit will select an entry only if no previous entry within the minor group has been selected, no previous minor group has been selected, and no previous major group has been selected.

A method and apparatus for replacing data in a list of buffers is provided. The list of buffers has a hot end and a cold end. The buffers at the hot end are maintained in a FIFO list and the buffers at the cold end are maintained in an LRU list. Requested data is located and, if the requested data is located in the LRU portion of the buffer list, the buffer containing the requested data is moved to the head of the FIFO list. If the data is located in a buffer in the FIFO portion of the buffer list, no rearrangement is required. If the requested data is not located in the buffer list, the data is stored into the buffer at the tail end of the LRU list, then the buffer is moved to the head of the FIFO list.

In a method and system for storing information within a set of a cache memory, the set has multiple locations. The information is stored at a selected one of the locations. The selected location satisfies one of the following conditions (a), (b) and (c): (a) the selected location is invalid; (b) each of the locations is valid, and the selected location is unmodified; (c) each of the locations is valid and modified, and the selected location is least recently used among the locations.

A Record Lock Processor is utilized in a multi-host data processing system to control the locking of Objects upon request of each of the multiple host data processors in non-conflicting manner. The Record Lock Processor has storage provisions which include a Lock List for storing bits that identify the Objects and bits that identify the requesting processor, a Queue List that stores entries that are formatted like the Lock List entry when a prior Lock List entry has been made for the same Object, and a Cache List for each processor that stores Cache List entries that identify each Object that is stored in the cache memories, each of which Cache List entries is associated with one of the requesting processors, wherein such Cache List entries include validity bits that identify whether each Object stored in a Cache List has a Valid or an Invalid status.

A block substitution method of a cache memory incudes the steps of storing data integrity information with a main memory for each block of the cache memory and calculating a non-reference period of each block. The non-reference periods of the blocks are compared to determine an order of the blocks based on the non-reference periods and a difference between the non-reference period of the block having a longest non-reference period and the non-reference period of other blocks is calculated. Data integrity in the block having the longest non-reference period is examined and when there is no data integrity in that block the data integrity in other blocks is examined in the order of the non-reference period. A block having a longest non-reference period among the blocks having the data integrity is determined and the determined block is selected as a block to be substituted by a new data block when the difference is smaller than a predetermined value. New data is loaded to the selected block.