Starvation-avoiding unbounded transactional memory

1. A method for facilitating efficient transactional execution, comprising:

executing a starvation-avoiding transaction for a thread, and at least one non-starvation-avoiding transaction for another thread;

wherein executing each of the starvation-avoiding transaction and the non-starvation-avoiding transaction involves placing load-marks on cache lines which are loaded during the corresponding transaction, and placing store-marks on cache lines which are stored to during the corresponding transaction;

wherein executing the starvation-avoiding transaction involves writing a timestamp value into metadata for load-marked and store-marked cache lines; and

wherein executing the non-starvation-avoiding transaction involves storing the addresses of load-marked or store-marked cache lines in a private buffer for the other thread;

preventing other threads from executing other starvation-avoiding transactions while the thread is executing the starvation-avoiding transaction; and

if a load-mark or store-mark placed during a non-starvation-avoiding transaction is encountered on a cache line read from or written to during the starvation-avoiding transaction, aborting the non-starvation-avoiding transaction, wherein aborting the non-starvation-avoiding transaction involves using the addresses stored in the private buffer to identify cache lines load-marked or store-marked during the non-starvation-avoiding transaction.

2. The method of claim 1 , wherein the method further comprises obtaining a token before commencing execution of the starvation-avoiding transaction and releasing the token when the starvation-avoiding transaction completes.

3. The method of claim 1 , wherein when a cache line is load-marked, no other thread may store a value in the cache line and when a cache line is store-marked, no other thread may load or store a value in the cache line.

4. The method of claim 3 , further comprising:

storing the addresses of load-marked or store-marked cache lines in a private buffer corresponding to the other thread.

5. The method of claim 4 , wherein if a load-mark or store-mark placed during a non-starvation-avoiding transaction is encountered on a cache line read from or written to during the starvation-avoiding transaction, the method further comprises:

releasing the load-marks and store-marks from the identified cache lines;

placing a load-mark or store-mark associated with the starvation-avoiding transaction on the cache line and writing a timestamp value into metadata for the cache line; and

continuing the starvation-avoiding transaction.

6. The method of claim 4 , wherein the method further comprises, if a load-mark or store-mark placed during a non-starvation-avoiding transaction is encountered on a cache line read from or written to during the starvation-avoiding transaction:

setting a starvation-avoiding transaction requested (SA-requested) flag for the cache line, wherein when the SA-requested flag is set, no other thread can place a subsequent load-mark or store-mark on the cache line;

delaying the starvation-avoiding transaction; and

continuing the starvation-avoiding transaction when the marking thread has cleared the load-mark or store-mark from the cache line, wherein continuing the starvation-avoiding transaction involves clearing the SA-requested flag, placing a load-mark or a store-mark on the cache line, and writing the timestamp value into metadata for the cache line.

7. The method of claim 1 , wherein the method further comprises performing IO accesses during the starvation-avoiding transaction as corresponding IO access instructions are executed.

8. An apparatus for facilitating efficient transactional execution, comprising:

a processor;

an execution mechanism on the processor;

wherein the execution mechanism is configured to execute a starvation-avoiding transaction for a thread, and at least one non-starvation-avoiding transaction for another thread;

wherein executing each of the starvation-avoiding transaction and the non-starvation-avoiding transaction involves placing load-marks on cache lines which are loaded during the corresponding transaction, and placing store-marks on cache lines which are stored to during the corresponding transaction;

wherein executing the starvation-avoiding transaction involves writing a timestamp value into metadata for load-marked and store-marked cache lines; and

wherein executing the non-starvation-avoiding transaction involves storing the addresses of load-marked or store-marked cache lines in a private buffer for the other thread;

wherein while executing the starvation-avoiding transaction, the execution mechanism is configured to prevent other threads from executing starvation-avoiding transactions; and

wherein if the execution mechanism encounters a load-mark or store-mark placed during a non-starvation-avoiding transaction on a cache line read from or written to during the starvation-avoiding transaction, the execution mechanism is configured to abort the non-starvation-avoiding transaction, wherein aborting the non-starvation-avoiding transaction involves using the addresses stored in the private buffer to identify cache lines load-marked or store-marked during the non-starvation-avoiding transaction.

9. The apparatus of claim 8 , wherein the execution mechanism is configured to obtain a token before commencing execution of the starvation-avoiding transaction and release the token when the starvation-avoiding transaction completes.

10. The apparatus of claim 8 , wherein when a cache line is load-marked, no other thread may store a value in the cache line and when a cache line is store-marked, no other thread may load or store a value in the cache line.

11. The apparatus of claim 10 , wherein the execution mechanism is further configured to:

store the addresses of load-marked or store-marked cache lines in a private buffer corresponding to the other thread.

12. The apparatus of claim 11 , wherein if the execution mechanism encounters a load-mark or store-mark placed during a non-starvation-avoiding transaction on a cache line read from or written to during the starvation-avoiding transaction, the execution mechanism is configured to:

to release the load-marks and store-marks from the identified cache lines;

place a load-mark or store-mark associated with the starvation-avoiding transaction on the cache line and write a timestamp value into metadata for the cache line; and to

continue the starvation-avoiding transaction.

13. The apparatus of claim 11 , wherein if the execution mechanism encounters a load-mark or store-mark placed during a non-starvation-avoiding transaction on a cache line read from or written to during the starvation-avoiding transaction, the execution mechanism is configured to:

set a starvation-avoiding transaction requested (SA-requested) flag for the cache line, wherein when the SA-requested flag is set, no other thread can place a subsequent load-mark or store-mark on the cache line;

delay the starvation-avoiding transaction; and to

continue the starvation-avoiding transaction when the marking thread has cleared the load-mark or store-mark from the cache line, wherein continuing the starvation-avoiding transaction involves clearing the SA-requested flag, placing a load-mark or a store-mark on the cache line, and writing the timestamp value into metadata for the cache line.

14. The apparatus of claim 8 , wherein the execution mechanism is configured to perform IO accesses during the starvation-avoiding transaction as corresponding IO access instructions are executed.

15. A computer system for facilitating efficient transactional execution, comprising:

a processor;

a memory coupled to the processor, wherein the memory is configured to store data and instructions for the processor;

an execution mechanism on the processor;

wherein the execution mechanism is configured to execute a starvation-avoiding transaction for a thread, and at least one non-starvation-avoiding transaction for another thread;

wherein executing each of the starvation-avoiding transaction and the non-starvation-avoiding transaction involves placing load-marks on cache lines which are loaded during the corresponding transaction, and placing store-marks on cache lines which are stored to during the corresponding transaction;

wherein executing the starvation-avoiding transaction involves writing a timestamp value into metadata for load-marked and store-marked cache lines; and

wherein executing the non-starvation-avoiding transaction involves storing the addresses of load-marked or store-marked cache lines in a private buffer for the other thread;

wherein while executing the starvation-avoiding transaction, the execution mechanism is configured to prevent other threads from executing starvation-avoiding transactions; and

wherein if the execution mechanism encounters a load-mark or store-mark placed during a non-starvation-avoiding transaction on a cache line read from or written to during the starvation-avoiding transaction, the execution mechanism is configured to abort the non-starvation-avoiding transaction, wherein aborting the non-starvation-avoiding transaction involves using the addresses stored in the private buffer to identify cache lines load-marked or store-marked during the non-starvation-avoiding transaction.

16. The computer system of claim 15 , wherein the execution mechanism is configured to obtain a token before commencing execution of the starvation-avoiding transaction and release the token when the starvation-avoiding transaction completes.

17. The computer system of claim 15 , wherein when a cache line is load-marked, no other thread may store a value in the cache line and when a cache line is store-marked, no other thread may load or store a value in the cache line.

18. The computer system of claim 17 , wherein the execution mechanism is further configured to:

store the addresses of load-marked or store-marked cache lines in a private buffer corresponding to the other thread.

19. The computer system of claim 18 , wherein if the execution mechanism encounters a load-mark or store-mark placed during a non-starvation-avoiding transaction on a cache line read from or written to during the starvation-avoiding transaction, the execution mechanism is configured to:

release the load-marks and store-marks from the identified cache lines;

place a load-mark or store-mark associated with the starvation-avoiding transaction on the cache line and write a timestamp value into metadata for the cache line; and to

continue the starvation-avoiding transaction.

20. The computer system of claim 18 , wherein if the execution mechanism encounters a load-mark or store-mark placed during a non-starvation-avoiding transaction on a cache line read from or written to during the starvation-avoiding transaction, the execution mechanism is configured to:

set a starvation-avoiding transaction requested (SA-requested) flag for the cache line, wherein when the SA-requested flag is set, no other thread can place a subsequent load-mark or store-mark on the cache line;

delay the starvation-avoiding transaction; and to

continue the starvation-avoiding transaction when the marking thread has cleared the load-mark or store-mark from the cache line, wherein continuing the starvation-avoiding transaction involves clearing the SA-requested flag, placing a load-mark or a store-mark on the cache line, and writing the timestamp value into metadata for the cache line.

21. The computer system of claim 15 , wherein the execution mechanism is configured to perform IO accesses during the starvation-avoiding transaction as corresponding IO access instructions are executed.