Supporting concurrent remove operations and add-to-front operations on a Least Recently Used (LRU) queue
AssigneeOracle International Corporation
InventorsYosef Lev, David Dice, Daniel McNaught Jordan
Life of this patent
Estimating the term…
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.
Claims20
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.
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.
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.
Dependencies are inferred from the claim text.