Methods and systems for partially-transacted data concurrency

• US 8,161,250 B2
• Filed: 05/20/2009
• Issued: 04/17/2012
• Est. Priority Date: 05/20/2009
• Status: Active Grant

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.), III Holdings 10, LLC (Intellectual Ventures LLC)
• Original Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Hooper, Harold Scott
• Primary Examiner(s): TRAN, MICHAEL THANH
• Application Number:
  US12/469,039
• Publication Number:
  US 20100299487A1
• Time in Patent Office: 1,063 Days
• Field of Search: 711/152, 711/147
• US Class Current: 711/152
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Aspects of the present invention comprise systems and methods for protecting multi-threaded access to shared memory. Some aspects provide higher data concurrency than other methods. Some aspects relate to methods and systems that provide access to data for all threads during the first phases of one thread'"'"'s write operation. Some aspects provide all threads access to a particular data unit until one thread enters the commit phase of the write operation. Some aspects manage a computing data resource such that, when a thread enters the commit phase, all pending read requests are fulfilled, all pending write requests are allowed to proceed to commit phase at which point they are blocked, all new read and write requests are blocked and the commit phase is completed by updating the target data and releasing the blocked requests.

Some aspects provide improved concurrency by performing reduced cross-thread interference. Some aspects may be implemented at any level from hardware to high-level languages. Some aspects protect readers from accessing partial write results which avoids retry semantics and data corruption.

Claims

1. A method for protecting multi-threaded access to shared memory, said method comprising:

a) providing, via a computing device comprising a processor and a memory, limited access to a shared memory resource, wherein said limited access is provided when one or more threads are entering a read operation on said shared memory resource, exiting a read operation on said shared memory resource and during at least a portion of a write operation on said shared memory resource;

b) blocking, via said computing device, said access to said shared memory resource when one or more threads is exiting a write operation on said shared memory resource, wherein said exiting a write operation causes execution of a commit operation wherein data is written to said shared memory resource; and

wherein said providing limited access to a shared memory resource comprises making a copy of at least a portion of said shared memory resource and granting exclusive write access to a thread requesting said copy when said thread requests a write operation.

2. A method as described in claim 1 further comprising unblocking said access to said shared memory resource after said commit operation, wherein said unblocking comprises unblocking write requests that were pending when exiting said write operation before unblocking newer write requests.

3. A method as described in claim 2 wherein said unblocking write requests that were pending when exiting said write operation comprises unblocking in the order in which said write requests exited the write operation.

4. A method as described in claim 2 wherein said unblocking write requests that were pending when exiting said write operation comprises unblocking in the order in which said write requests entered the write operation.

5. A method as described in claim 2 wherein said unblocking newer write requests comprises unblocking in the order in which said newer write requests entered the write operation.

6. A method for protecting multi-threaded access to shared memory, said method comprising:

a) providing read access to a data element, Data 1, of a shared memory resource for a plurality of threads, said providing being performed by a computing device comprising a processor and memory;

b) receiving, at said computing device, a write request for said data element, Data 1, from Thread A, which is one of said plurality of threads;

c) creating, with said computing device, a new data element, Copy 1A, with an initial value copied from Data 1;

d) granting exclusive write access for Copy 1A to Thread A, wherein said granting is performed by said computing device;

e) maintaining read access to said plurality of threads, including Thread A, for Data 1 after receiving said write request from Thread A, wherein said maintaining is performed by said computing device;

f) receiving a commit request from Thread A to exit a write process initiated by said write request by entering a commit phase wherein the value in Copy 1A will be written to Data 1 and made accessible to all threads by said computing device;

g) blocking Thread A, with said computing device, until

i) all pending read requests from 5 other threads are fulfilled, and

ii) all pending write requests from other threads have progressed to blocking;

h) blocking any new read requests and write requests for Data 1 with said computing device;

i) writing the value in Copy 1A to Data 1, with said computing device;

j) unblocking all read requests after said writing with said computing device; and

k) unblocking each write request in succession with said computing device.

7. A method as described in claim 6 further comprising updating Copy 1A with a value determined by Thread A before said writing the value of Copy 1A to Data 1.

8. A method as described in claim 7 wherein said value determined by Thread A is determined based on a current value of Data 1.

9. A method as described in claim 6 further comprising continuing to receive write requests for Data 1 during said maintaining read access to said plurality of threads after receiving said write request from Thread A.

10. A method as described in claim 6 wherein said unblocking each write request in succession comprises unblocking said pending write requests before said new write requests.

11. A method as described in claim 6 wherein said unblocking each write request in succession comprises unblocking said pending write requests in the order in which they request a commit operation.

12. A method as described in claim 6 wherein said unblocking each write request in succession comprises unblocking said new write requests in the order in which said new write requests are received.

13. A method as described in claim 6 wherein said unblocking each write request in succession comprises unblocking said pending write requests in the order in which they request a commit operation and unblocking said new write requests, after unblocking said pending write requests, in the order in which said new write requests are received.

14. An apparatus for protecting multi-threaded access to shared memory, said apparatus comprising:

a) a data manager comprising a processor and a shared memory resource, said data manager comprising;

i) an access manager for providing read access to a data element, Data 1, of said shared memory resource to a plurality of threads;

ii) a receiver for receiving a write request for said data element, Data 1, from Thread A, which is one of said plurality of threads;

(1) wherein said data manager creates a new data element, Copy 1A, with an initial value copied from Data 1 in response to said receiving a write request;

(2) wherein said data manager grants exclusive write access for Copy 1A to Thread A;

(3) wherein said data manager maintains read access to said plurality of threads, including Thread A, for Data 1 after receiving said write request from Thread A;

iii) a second receiver for receiving a commit request from Thread A,

(1) wherein said data manager exits a write process initiated by said write request by entering a commit phase wherein the value in Copy 1A will be written to Data 1 and made accessible to all threads in response to said receiving a commit request;

iv) a first blocker for blocking Thread A until

(1) all pending read requests from other threads are fulfilled, and

(2) all pending write requests from other threads have progressed to blocking;

v) a second blocker or blocking any new read requests and write requests for Data 1;

vi) a memory writer for writing the value in Copy 1A to Data 1;

(1) wherein said first blocker and said second blocker unblock all read requests after said writing; and

(2) wherein said first blocker and said second blocker unblock each write request in succession.

15. An apparatus as described in claim 14 further comprising an updater for updating Copy 1A with a value determined by Thread A before said writing the value of Copy 1A to Data 1.

16. An apparatus as described in claim 14 wherein said data manager continues to receive write requests for Data 1 while maintaining read access to said plurality of threads after receiving said write request from Thread A.

17. An apparatus as described in claim 14 wherein said unblocking each write request in succession comprises unblocking said pending write requests before said new write requests.

18. An apparatus as described in claim 14 wherein said unblocking each write request in succession comprises unblocking said pending write requests in the order in which they request a commit operation.

19. An apparatus as described in claim 14 wherein said unblocking each write request in succession comprises unblocking said new requests in the order in which said new write requests are received.