Applying limited-size hardware transactional memory to arbitrarily large data structure

Patent metadata

Field	Value
Publication number	US-9529839-B2
Application number	US-63226009-A
Country	US
Kind code	B2
Filing date	Dec 7, 2009
Priority date	Dec 7, 2009
Publication date	Dec 27, 2016
Grant date	Dec 27, 2016

Abstract

A technique for applying hardware transaction memory to an arbitrarily large data structure is disclosed. A data updater traverses the data structure to locate an update point using a lockless synchronization technique that synchronizes the data updater with other updaters that may be concurrently updating the data structure. At the update point, the updater performs an update on the data structure using a hardware transactional memory transaction that operates at the update point.

First claim

What is claimed is:

1. In a data processing system having at least one CPU, a memory operatively coupled to said CPU, said memory including a storage medium tangibly embodying a program of instructions that are executable on said at least one CPU to perform machine-implemented operations, said operations implementing a method for using hardware transactional memory to update a data structure, comprising:
a data updater traversing said data structure to locate an update point using a lockless synchronization technique that synchronizes said data updater with other updaters that may be concurrently updating said data structure;
said lockless synchronization being selected from the group consisting of (1) a synchronization technique that uses volatile variables and garbage collection, (2) a synchronization technique that uses plural list traversal transactions, or (3) a synchronization technique that uses watch primitives; and
upon reaching said update point, said updater performing an update on said data structure using a hardware transactional memory transaction that operates at said update point.

2. A system, comprising:
a CPU;
a memory operatively coupled to said CPU, said memory tangibly embodying a program of instructions executable by said CPU to perform operations that implement a method for using hardware transactional memory to update a data structure, comprising:
a data updater traversing said data structure to locate an update point using a lockless synchronization technique that synchronizes said data updater with other updaters that may be concurrently updating said data structure;
said lockless synchronization being selected from the group consisting of (1) a synchronization technique that uses volatile variables and garbage collection, (2) a synchronization technique that uses plural list traversal transactions, or (3) a synchronization technique that uses watch primitives; and
upon reaching said update point, said updater performing an update on said data structure using a hardware transactional memory transaction that operates at said update point.

3. A computer program product, comprising:
one or more non-transitory computer-readable storage media:
program instructions stored on said one or more media for programming a CPU to perform operations that implement a method for using hardware transactional memory to update a data structure, comprising:
a data updater traversing said data structure to locate an update point using a lockless synchronization technique that synchronizes said data updater with other updaters that may be concurrently updating said data structure;
said lockless synchronization being selected from the group consisting of (1) a synchronization technique that uses volatile variables and garbage collection, (2) a synchronization technique that uses plural list traversal transactions, or (3) a synchronization technique that uses watch primitives: and
upon reaching said update point, said updater performing an update on said data structure using a hardware transactional memory transaction that operates at said update point.

4. A machine implemented method for using hardware transactional memory to update a data structure, comprising:
a data updater traversing said data structure to locate an update point using a lockless synchronization technique that synchronizes said data updater with other updaters that may be concurrently updating said data structure;
upon reaching said update point, said updater performing an update on said data structure using a hardware transactional memory transaction that operates at said update point; and
said lockless synchronization uses one or more of (1) volatile variables and garbage collection, (2) plural list traversal transactions, or (3) watch primitives.

5. The method of claim 4 wherein said data structure comprises a linked list and said update comprises inserting, deleting or modifying a list element.

Assignees

• Mckenney Paul E
• Michael Maged M
• IBM

Inventors

• Mckenney Paul E
• Michael Maged M

Classifications

• G06F16/2308

  Concurrency control (transaction processing G06F9/466) · CPC title

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F17/30371 Primary

  Physics · mapped topic

• G06F17/30348

  Physics · mapped topic