# US 11,442,871 B2 · Supporting concurrent remove operations and add-to-front operations on a Least Recently Used (LRU) queue

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,442,871 B2
- Document ID: US11442871B2
- Status: Granted
- Kind: B2
- Application number: 17/079,361
- Filed: 2020-10-23
- Published: 2021-02-11
- Granted: 2022-09-13
- Earliest claimed: 2018-04-05
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Yosef Lev; David Dice; Daniel McNaught Jordan
- Web page: https://patentgrep.com/patent/US11442871B2

## CPC

- G06F 9/526: {Mutual exclusion algorithms}
- G06F 12/122: of the least frequently used [LFU] type, e.g. with individual count value
- G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)}
- G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores
- G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
- G06F 12/127: using additional replacement algorithms
- G06F 16/1774: {Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 12/08: in hierarchically structured memory systems, e.g. virtual memory systems
- G06F 12/0857: {by multiple requestors}
- G06F 2212/1008: Correctness of operation, e.g. memory ordering
- G06F 2212/1024: Latency reduction
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A remove operation and an add-to-front operation may be currently performed with respect to nodes in an Least Recently Used (LRU) queue. A remove operation for a node may proceed if a lock can be obtained on the node to be removed and a predecessor node. During the remove operation, an add-to-front operation may proceed if a lock can be obtained on a dummy node that precedes the current front node of the LRU queue.

## Claims

### Claim 1

A system, comprising:
at least one processor
a memory, comprising a first least recently used (LRU) queue comprising a plurality of nodes, a second LRU queue, and program instructions that when executed by the at least one processor cause the at least one processor to:
move a node of the plurality of nodes from the first LRU queue to the front of the second LRU queue, wherein to move the node, the program instructions cause the at least one processor to:
remove the node from the first LRU queue, wherein the removal holds respective locks on the node and a predecessor node in the first LRU queue until the predecessor node points to a successor node of the node as a next node in the first LRU queue and the successor node points to the predecessor node as a node immediately prior to the successor node in the first LRU queue; and
add the node as front node to the second LRU queue, wherein the addition locks a dummy node that points to a current front node of the second LRU queue until:
a previous node pointer of the current front node points to the node;
a previous node pointer of the node points to the dummy node; and
a next node pointer of the node points to the current front node.

### Claim 2 (depends on 1)

The system of claim 1, wherein to hold the respective lock on the node in the first LRU queue, the program instructions cause the at least one processor to set a lock bit in the successor node to identify the node as locked in the first LRU queue.

### Claim 3 (depends on 2)

The system of claim 2, wherein to remove the node from the first LRU queue, the program instructions cause the at least one processor to unset the lock bit in the successor node to identify the node as unlocked.

### Claim 4 (depends on 3)

The system of claim 3, wherein the lock bit is unset without using a compare and swap (CAS) operation.

### Claim 5 (depends on 1)

The system of claim 1, wherein to hold the respective lock on the predecessor node in the first LRU queue, the program instructions cause the at least one processor to write a null value as a next node pointer of the predecessor node.

### Claim 6 (depends on 1)

The system of claim 1, wherein to lock the dummy node that points to the current front node of the second LRU queue, the program instructions cause the at least one processor to write a null value as a next node pointer of the dummy node.

### Claim 7 (depends on 6)

The system of claim 6, wherein to add the node as the front node to the second LRU queue, the program instructions cause the at least one processor to further perform a compare and swap (CAS) operation to replace a null value stored as the next node pointer of the dummy node with a pointer to the node in order to unlock the dummy node.

### Claim 8

A method, comprising:
performing, by one or more computing devices:
moving a node from a first Least Recently Used (LRU) queue to the front of a second LRU queue, comprising:
removing the node from the first LRU queue, wherein the removing comprises holding respective locks on the node and a predecessor node in the first LRU queue until the predecessor node points to a successor node of the node as a next node in the first LRU queue and the successor node points to the predecessor node as a node immediately prior to the successor node in the first LRU queue; and
adding the node as front node to the second LRU queue, wherein the adding comprises locking a dummy node that points to a current front node of the second LRU queue until:
a previous node pointer of the current front node points to the node;
a previous node pointer of the node points to the dummy node; and
a next node pointer of the node points to the current front node.

### Claim 9 (depends on 8)

The method of claim 8, wherein holding the respective lock on the node in the first LRU queue comprises setting a lock bit in the successor node to identify the node as locked in the first LRU queue.

### Claim 10 (depends on 9)

The method of claim 9, wherein removing the node from the first LRU queue further comprises unsetting the lock bit in the successor node to identify the node as unlocked.

### Claim 11 (depends on 10)

The method of claim 10, wherein the lock bit is unset without using a compare and swap (CAS) operation.

### Claim 12 (depends on 8)

The method of claim 8, wherein holding the respective lock on the predecessor node in the first LRU queue comprises writing a null value as a next node pointer of the predecessor node.

### Claim 13 (depends on 8)

The method of claim 8, wherein locking the dummy node that points to the current front node of the second LRU queue comprises writing a null value as a next node pointer of the dummy node.

### Claim 14 (depends on 13)

The method of claim 13, wherein adding the node to the front node to the second LRU queue further comprises performing a compare and swap (CAS) operation to replace a null value stored as the next node pointer of the dummy node with a pointer to the node in order to unlock the dummy node.

### Claim 15

One or more non-transitory, computer-readable storage media, storing program instructions that when executed on or across one or more computing devices cause the one or more computing devices to implement:
moving a node from a first Least Recently Used (LRU) queue to the front of a second LRU queue, wherein the program instructions cause the one or more computing devices to implement:
removing the node from the first LRU queue, wherein the removing comprises holding respective locks on the node and a predecessor node in the first LRU queue until the predecessor node points to a successor node of the node as a next node in the first LRU queue and the successor node points to the predecessor node as a node immediately prior to the successor node in the first LRU queue; and
adding the node as front node to the second LRU queue, wherein the adding comprises locking a dummy node that points to a current front node of the second LRU queue until:
a previous node pointer of the current front node points to the node;
a previous node pointer of the node points to the dummy node; and
a next node pointer of the node points to the current front node.

### Claim 16 (depends on 15)

The one or more non-transitory, computer-readable storage media of claim 15, wherein, in holding the respective lock on the node in the first LRU queue, the program instructions cause the one or more computing devices to implement setting a lock bit in the successor node to identify the node as locked in the first LRU queue.

### Claim 17 (depends on 16)

The one or more non-transitory, computer-readable storage media of claim 16, wherein, in removing the node from the first LRU queue, the program instructions cause the one or more computing devices to further implement unsetting the lock bit in the successor node to identify the node as unlocked.

### Claim 18 (depends on 17)

The one or more non-transitory, computer-readable storage media of claim 17, wherein the lock bit is unset without using a compare and swap (CAS) operation.

### Claim 19 (depends on 15)

The one or more non-transitory, computer-readable storage media of claim 15, wherein, in locking the dummy node that points to the current front node of the second LRU queue, the program instructions cause the one or more computing devices to further implement writing a null value as a next node pointer of the dummy node.

### Claim 20 (depends on 19)

The one or more non-transitory, computer-readable storage media of claim 19, wherein, in adding the node to the front node to the second LRU queue further, the program instructions cause the one or more computing devices to further implement performing a compare and swap (CAS) operation to replace a null value stored as the next node pointer of the dummy node with a pointer to the node in order to unlock the dummy node.