# US 8,572,130 B2 · Replacement policy for resource container > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,572,130 B2 - Document ID: US8572130B2 - Status: Granted - Kind: B2 - Application number: 13/169,925 - Filed: 2011-06-27 - Published: 2012-12-27 - Granted: 2013-10-29 - Earliest claimed: 2011-06-27 - Assignees: Sap SE - Applicants: Ivan Schreter - Inventors: Ivan Schreter - Web page: https://patentgrep.com/patent/US8572130B2 ## CPC - G06F 16/22: Indexing; Data structures therefor; Storage structures - G06F 5/065: {Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's} - G06F 12/0866: for peripheral storage systems, e.g. disk cache - G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F 16/24552: {Database cache management} - G06F 9/3856: {Reordering of instructions, e.g. using queues or age tags} - G06F 2212/465: Structured object, e.g. database record - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A system includes creation of a first resource queue indicating an order of resources stored in a memory, the order based on respective timestamps associated with the stored resources, association of the first resource queue with a first queue timestamp, reception of a first command to deallocate a first amount of stored resources from the memory, determination that a first stored resource indicated by the first resource queue is associated with a timestamp earlier than the first queue timestamp, deallocation of the first stored resource from the memory, reception of a second command to deallocate a second amount of stored resources from the memory, determination that the first resource queue indicates no stored resources which are associated with a timestamp earlier than the first queue timestamp, and, in response to the determination that the first resource queue indicates no stored resources which are associated with a timestamp earlier than the first queue timestamp, creation of a second resource queue indicating a second order of second resources stored in the memory, the second order based on respective second timestamps associated with the stored second resources. ## Claims ### Claim 1 A method implemented on a machine having at least one processor for a database system, comprising: creating a first resource queue indicating an order of resources stored in a memory, the order based on respective timestamps associated with the stored resources; associating the first resource queue with a first queue timestamp; receiving a first command to deallocate a first amount of stored resources from the memory; determining that a first stored resource indicated by the first resource queue is associated with a timestamp earlier than the first queue timestamp; deallocating the first stored resource from the memory; receiving a second command to deallocate a second amount of stored resources from the memory; determining that the first resource queue indicates no stored resources which are associated with a timestamp earlier than the first queue timestamp; in response to the determination that the first resource queue indicates no stored resources which are associated with a timestamp earlier than the first queue timestamp, creating a second resource queue indicating a second order of second resources stored in the memory, the second order based on respective second timestamps associated with the stored second resources; creating a third resource queue indicating a third order of resources of a second disposition type stored in the memory, the third order based on respective timestamps associated with the stored resources of the second disposition type; and associating the third resource queue with a third queue timestamp; wherein determining that the first stored resource indicated by the first resource queue is associated with a timestamp earlier than the first queue timestamp comprises: determining a first not-in-use time for a stored resource indicated by the first resource queue based on a first timestamp associated with the stored resource; determining a first weighted not-in-use time for the stored resource based on the first not-in-use time and on a first weight associated with the first disposition type; determining a second not-in-use time for a stored resource indicated by the first resource queue based on a first timestamp associated with the stored resource; determining a second weighted not-in-use time for the stored second resource based on the second not-in-use time and on a second weight associated with the second disposition type; and determining that the first weighted not-in-use time is greater than the second weighted not-in-use time. ### Claim 2 (depends on 1) A method according to claim 1, further comprising: prior to receiving the second command, receiving a third command to deallocate a third amount of stored resources from the memory; determining that a third stored resource indicated by the first resource queue is associated with a timestamp earlier than the first queue timestamp; and deallocating the third stored resource from the memory. ### Claim 3 (depends on 1) A method according to claim 1, further comprising: associating the second resource queue with a second queue timestamp; determining that a second stored resource indicated by the second queue is associated with a timestamp earlier than the second queue timestamp; and deallocating the second stored resource from the memory. ### Claim 4 (depends on 1) A method according to claim 1, wherein the resource queue comprises a tree structure. ### Claim 5 (depends on 4) A method according to claim 4, wherein a stored resource is associated with a respective resource header comprising a left pointer member to indicate a first child resource of the stored resource within the tree structure and a right pointer member to indicate a second child resource of the stored resource within the tree structure. ### Claim 6 (depends on 1) A method according to claim 1, wherein determining that the first resource queue indicates no stored resources which are associated with a timestamp earlier than the first queue timestamp further comprises: determining that the memory stores resources of the first disposition type. ### Claim 7 A non-transitory computer-readable medium storing program code, the program code executable by a computer, the program code comprising: code to create a first resource queue indicating an order of resources stored in a memory, the order based on respective timestamps associated with the stored resources; code to associate the first resource queue with a first queue timestamp; code to receive a first command to deallocate a first amount of stored resources from the memory; code to determine that a first stored resource indicated by the first resource queue is associated with a timestamp earlier than the first queue timestamp; code to deallocate the first stored resource from the memory; code to receive a second command to deallocate a second amount of stored resources from the memory; code to determine that the first resource queue indicates no stored resources which are associated with a timestamp earlier than the first queue timestamp; code to create, in response to the determination that the first resource queue indicates no stored resources which are associated with a timestamp earlier than the first queue timestamp, a second resource queue indicating a second order of second resources stored in the memory, the second order based on respective second timestamps associated with the stored second resources; code to create a third resource queue indicating a third order of resources of a second disposition type stored in the memory, the third order based on respective timestamps associated with the stored resources of the second disposition type; and code to associate the third resource queue with a third queue timestamp; wherein the code to determine that the first stored resource indicated by the first resource queue is associated with a timestamp earlier than the first queue timestamp comprises: code to determine a first not-in-use time for a stored resource indicated by the first resource queue based on a first timestamp associated with the stored resource; code to determine a first weighted not-in-use time for the stored resource based on the first not-in-use time and on a first weight associated with the first disposition type; code to determine a second not-in-use time for a stored resource indicated by the first resource queue based on a first timestamp associated with the stored resource; code to determine a second weighted not-in-use time for the stored second resource based on the second not-in-use time and on a second weight associated with the second disposition type; and code to determine that the first weighted not-in-use time is greater than the second weighted not-in-use time. ### Claim 8 (depends on 7) A medium according to claim 7, the program code further comprising: code to receive, prior to receiving the second command, a third command to deallocate a third amount of stored resources from the memory; code to determine that a third stored resource indicated by the first resource queue is associated with a timestamp earlier than the first queue timestamp; and code to deallocate the third stored resource from the memory. ### Claim 9 (depends on 7) A medium according to claim 7, the program code further comprising: code to associate the second resource queue with a second queue timestamp; code to determine that a second stored resource indicated by the second queue is associated with a timestamp earlier than the second queue timestamp; and code to deallocate the second stored resource from the memory. ### Claim 10 (depends on 7) A medium according to claim 7, wherein the resource queue comprises a tree structure. ### Claim 11 (depends on 10) A medium according to claim 10, wherein a stored resource is associated with a respective resource header comprising a left pointer member to indicate a first child resource of the stored resource within the tree structure and a right pointer member to indicate a second child resource of the stored resource within the tree structure. ### Claim 12 (depends on 7) A medium according to claim 7, wherein the code to determine that the first resource queue indicates no stored resources which are associated with a timestamp earlier than the first queue timestamp further comprises: code to determine that the memory stores resources of the first disposition type. ### Claim 13 A system comprising: a database cache; a memory storing processor-executable process steps; and a processor to execute the processor-executable process steps to cause the system to: create a first resource queue indicating an order of resources stored in the database cache, the order based on respective timestamps associated with the stored resources; associate the first resource queue with a first queue timestamp; receive a first command to deallocate a first amount of stored resources from the database cache; determine that a first stored resource indicated by the first resource queue is associated with a timestamp earlier than the first queue timestamp; deallocate the first stored resource from the database cache; receive a second command to deallocate a second amount of stored resources from the database cache; determine that the first resource queue indicates no stored resources which are associated with a timestamp earlier than the first queue timestamp; create, in response to the determination that the first resource queue indicates no stored resources which are associated with a timestamp earlier than the first queue timestamp, a second resource queue indicating a second order of second resources stored in the database cache, the second order based on respective second timestamps associated with the stored second resources; create a third resource queue indicating a third order of resources of a second disposition type stored in the database cache, the third order based on respective timestamps associated with the stored resources of the second disposition type; and associate the third resource queue with a third queue timestamp; wherein the determination that the first stored resource indicated by the first resource queue is associated with a timestamp earlier than the first queue timestamp comprises: determination of a first not-in-use time for a stored resource indicated by the first resource queue based on a first timestamp associated with the stored resource; determination of a first weighted not-in-use time for the stored resource based on the first not-in-use time and on a first weight associated with the first disposition type; determination of a second not-in-use time for a stored resource indicated by the first resource queue based on a first timestamp associated with the stored resource; determination of a second weighted not-in-use time for the stored second resource based on the second not-in-use time and on a second weight associated with the second disposition type; and determination that the first weighted not-in-use time is greater than the second weighted not-in-use time. ### Claim 14 (depends on 13) A system according to claim 13, the processor to execute the processor-executable process steps to cause the system to: receive, prior to receiving the second command, a third command to deallocate a third amount of stored resources from the database cache; determine that a third stored resource indicated by the first resource queue is associated with a timestamp earlier than the first queue timestamp; and deallocate the third stored resource from the database cache. ### Claim 15 (depends on 13) A system according to claim 13, the processor to execute the processor-executable process steps to cause the system to: associate the second resource queue with a second queue timestamp; determine that a second stored resource indicated by the second queue is associated with a timestamp earlier than the second queue timestamp; and deallocate the second stored resource from the database cache. ### Claim 16 (depends on 13) A system according to claim 13, wherein the resource queue comprises a tree structure. ### Claim 17 (depends on 16) A system according to claim 16, wherein a stored resource is associated with a respective resource header comprising a left pointer member to indicate a first child resource of the stored resource within the tree structure and a right pointer member to indicate a second child resource of the stored resource within the tree structure.