System and method for implementing reader-writer locks using hardware transactional memory
First Claim
1. A method, comprising:
- performing by a computer;
receiving, by a compiler executing on a processor of the computer, a multithreaded application that comprises code comprising one or more requests to acquire a shared reader-writer lock, wherein the shared reader-writer lock comprises a tail pointer and an ordered list of zero or more nodes, wherein the shared reader-writer lock controls access to a critical section of code or a shared resource by concurrently executing threads of the application; and
compiling the code by the compiler to produce executable code, compiling including modifying the code responsive to determining that the code includes at least one of;
a conditional branch on a local variable within a transaction,accesses to multiple shared variables within a transaction,a transaction that accesses only a single variable,one or more conditional branches within a transaction, oran indication that multiple threads wish to acquire a reader-writer lock on a single shared variable,wherein after the code is compiled to produce the executable code, execution of the executable code when performed results in;
a given thread of the application inserting a node in the ordered list of nodes, wherein each node in the ordered list of nodes is owned by a respective thread that holds the shared reader-writer lock or that desires access to the critical section of code or shared resource in a read-only mode or in a write mode, and wherein only one thread can hold the shared reader-writer lock in a write mode at a time;
subsequent to said inserting, the given thread acquiring the shared reader-writer lock in a read-only mode or in a write mode; and
subsequent to said acquiring, the given thread releasing the shared reader-writer lock, wherein said releasing comprises removing the inserted node from the ordered list of nodes;
wherein at least one of said inserting or said releasing comprises updating a value of the tail pointer within a hardware transaction or modifying a field of at least one node in the ordered list of nodes within a hardware transaction.
0 Assignments
0 Petitions
Accused Products
Abstract
Transactional reader-writer locks may leverage available hardware transactional memory (HTM) to simplify the procedures of the reader-writer lock algorithm and to eliminate a requirement for type stable memory An HTM-based reader-writer lock may include an ordered list of client-provided nodes, each of which represents a thread that holds (or desires to acquire) the lock, and a tail pointer. The locking and unlocking procedures invoked by readers and writers may access the tail pointer or particular ones of the nodes in the list using various combinations of transactions and non-transactional accesses to insert nodes into the list or to remove nodes from the list. A reader or writer that owns a node at the head of the list (or a reader whose node is preceded in the list only by other readers'"'"' nodes) may access a critical section of code or shared resource.
-
Citations
20 Claims
-
1. A method, comprising:
performing by a computer; receiving, by a compiler executing on a processor of the computer, a multithreaded application that comprises code comprising one or more requests to acquire a shared reader-writer lock, wherein the shared reader-writer lock comprises a tail pointer and an ordered list of zero or more nodes, wherein the shared reader-writer lock controls access to a critical section of code or a shared resource by concurrently executing threads of the application; and compiling the code by the compiler to produce executable code, compiling including modifying the code responsive to determining that the code includes at least one of; a conditional branch on a local variable within a transaction, accesses to multiple shared variables within a transaction, a transaction that accesses only a single variable, one or more conditional branches within a transaction, or an indication that multiple threads wish to acquire a reader-writer lock on a single shared variable, wherein after the code is compiled to produce the executable code, execution of the executable code when performed results in; a given thread of the application inserting a node in the ordered list of nodes, wherein each node in the ordered list of nodes is owned by a respective thread that holds the shared reader-writer lock or that desires access to the critical section of code or shared resource in a read-only mode or in a write mode, and wherein only one thread can hold the shared reader-writer lock in a write mode at a time; subsequent to said inserting, the given thread acquiring the shared reader-writer lock in a read-only mode or in a write mode; and subsequent to said acquiring, the given thread releasing the shared reader-writer lock, wherein said releasing comprises removing the inserted node from the ordered list of nodes; wherein at least one of said inserting or said releasing comprises updating a value of the tail pointer within a hardware transaction or modifying a field of at least one node in the ordered list of nodes within a hardware transaction. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
10. A system, comprising:
-
one or more processor cores; and a memory coupled to the one or more processor cores and storing program instructions that when executed on the one or more processor cores cause the one or more processor cores to perform; receiving, by a compiler executing on one or more processor cores, a multithreaded application comprising code that comprises one or more requests to acquire a shared reader-writer lock, wherein the shared reader-writer lock comprises a tail pointer and an ordered list of zero or more nodes, wherein the shared reader-writer lock controls access to a critical section of code or a shared resource by concurrently executing threads of the application; and compiling the code by the compiler to produce executable code, compiling including modifying the code and compiling the modified code responsive to determining that the code includes at least one of; a conditional branch on a local variable within a transaction, accesses to multiple shared variables within a transaction, a transaction that accesses only a single variable, one or more conditional branches within a transaction, or an indication that multiple threads wish to acquire a reader-writer lock on a single shared variable, wherein after the code is compiled to produce the executable code, execution of the executable code when performed results in; a given thread of the application inserting a node in the ordered list of nodes, wherein each node in the ordered list of nodes is owned by a respective thread that holds the shared reader-writer lock or that desires access to the critical section of code or shared resource in a read-only mode or in a write mode, and wherein only one thread can hold the shared reader-writer lock in a write mode at a time; subsequent to said inserting, the given thread acquiring the shared reader-writer lock in a read-only mode or in a write mode; and subsequent to said acquiring, the given thread releasing the shared reader-writer lock, wherein said releasing comprises removing the inserted node from the ordered list of nodes; wherein at least one of said inserting or said releasing comprises updating a value of the tail pointer within a hardware transaction or modifying a field of at least one node in the ordered list of nodes within a hardware transaction. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:
-
receiving, by a compiler executing on the one or more computers, code comprising a multithreaded application that comprises one or more requests to acquire a shared reader-writer lock, wherein the shared reader-writer lock comprises a tail pointer and an ordered list of zero or more nodes, wherein the shared reader-writer lock controls access to a critical section of code or a shared resource by concurrently executing threads of the application; and compiling the code by the compiler to produce executable code, compiling including modifying the code and compiling the modified code responsive to determining that the code includes at least one of; a conditional branch on a local variable within a transaction, accesses to multiple shared variables within a transaction, a transaction that accesses only a single variable, one or more conditional branches within a transaction, or an indication that multiple threads wish to acquire a reader-writer lock on a single shared variable, wherein after the code is compiled to produce the executable code, execution of the executable code when performed results in; a given thread of the application inserting a node in the ordered list of nodes, wherein each node in the ordered list of nodes is owned by a respective thread that holds the shared reader-writer lock or that desires access to the critical section of code or shared resource in a read-only mode or in a write mode, and wherein only one thread can hold the shared reader-writer lock in a write mode at a time; subsequent to said inserting, the given thread acquiring the shared reader-writer lock in a read-only mode or in a write mode; subsequent to said acquiring, the given thread releasing the shared reader-writer lock, wherein said releasing comprises removing the inserted node from the ordered list of nodes, wherein at least one of said inserting or said releasing comprises updating a value of the tail pointer within a hardware transaction or modifying a field of at least one node in the ordered list of nodes within a hardware transaction. - View Dependent Claims (17, 18, 19, 20)
-
Specification