Maintaining a separate LRU linked list for each thread for multi-threaded access

A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations of minimizing contention among multiple threads for determining a least recently used cache entry, the operations comprising:

• maintaining a plurality of linked lists of elements corresponding to a plurality of threads accessing a plurality of cache entries, including a first linked list corresponding to a first thread and a second linked list corresponding to a second thread, each element of each linked list corresponding to one of the plurality of cache entries;
• in response to the first thread accessing a cache entry corresponding to an element of the second linked list of elements, inserting the element corresponding to the accessed cache entry to a head of the first linked list of elements;
• removing the element corresponding to the accessed cache entry from the second linked list;
• and
• re-linking one or more neighboring elements that were adjacent to the removed elements on the second linked list.

A data processing system, comprising:

• a processor;
• and
• a memory to store instructions, which when executed by the processor, cause the processor to perform operations, the operations including
• maintaining a plurality of linked lists of elements corresponding to a plurality of threads accessing a plurality of cache entries, including a first linked list corresponding to a first thread and a second linked list corresponding to a second thread, each element of each linked list corresponding to one of the plurality of cache entries,
• in response to the first thread accessing a cache entry corresponding to an element of the second linked list of elements, inserting the element corresponding to the accessed cache entry to a head of the first linked list of elements,
• removing the element corresponding to the accessed cache entry from the second linked list, and
• re-linking one or more neighboring elements that were adjacent to the removed elements on the second linked list.