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&#39;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.

Description:
FIELD OF THE INVENTION 
       [0001]    Embodiments of the present invention comprise methods and systems for protecting multi-threaded access to shared memory that provide higher data concurrency than other methods. 
       BACKGROUND 
       [0002]    In multithreaded environments where memory is shared, there is the potential for one thread to read data that is being written by another, resulting in incomplete or corrupt data. There is therefore a need to protect shared resources and assure that updates to the resource are atomic with respect to other threads. 
       SUMMARY 
       [0003]    Some embodiments of the present invention comprise methods and systems for protecting multi-threaded access to shared memory that provide higher data concurrency than other methods. Some embodiments comprise methods and systems that provide access to data for all threads during the first phases of one thread&#39;s write operation. In some embodiments, all threads are allowed access to a particular data unit until one thread enters the commit phase of the write operation. In some embodiments, 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. 
         [0004]    This invention provides improved concurrency by performing reduced cross-thread interference. Embodiments can be implemented at any level from hardware to high-level languages. Some embodiments, protect readers from accessing partial write results which avoids retry semantics and data corruption. 
         [0005]    The foregoing and other objectives, features, and advantages of the invention will be more readily understood upon consideration of the following detailed description of the invention taken in conjunction with the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL DRAWINGS 
         [0006]      FIG. 1  is a diagram showing the phases and the blocking period of a traditional prior art write operation; 
           [0007]      FIG. 2  is a diagram showing the phases and the blocking period of an exemplary embodiment of the present invention; 
           [0008]      FIG. 3  is a diagram showing steps of an exemplary data management process comprising a mutual write process; 
           [0009]      FIG. 4  is a diagram showing steps of an exemplary data management process comprising a mutual write process from the perspective of a participating thread; and 
           [0010]      FIG. 5  is a diagram showing steps of an exemplary data management process comprising an exclusive write process. 
       
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
       [0011]    Embodiments of the present invention will be best understood by reference to the drawings, wherein like parts are designated by like numerals throughout. The figures listed above are expressly incorporated as part of this detailed description. 
         [0012]    It will be readily understood that the components of the present invention, as generally described and illustrated in the figures herein, could be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the methods and systems of the present invention is not intended to limit the scope of the invention but it is merely representative of the presently preferred embodiments of the invention. 
         [0013]    Elements of embodiments of the present invention may be embodied in hardware, firmware and/or software. While exemplary embodiments revealed herein may only describe one of these forms, it is to be understood that one skilled in the art would be able to effectuate these elements in any of these forms while resting within the scope of the present invention. 
         [0014]    Some embodiments of the present invention provide an improvement to current methods of protecting shared memory in multithreaded systems. One benefit of these embodiments is to improve thread concurrency by reducing interference between threads. Another benefit of some embodiments is to provide a mechanism that is implementable in legacy systems without additional hardware or software system requirements. 
         [0015]    Some embodiments of the present invention comprise an improved lock mechanism by incorporating an explicit memory access pattern. The core strategy is to postpone write-based blocking until the commission of write operations. The underlying assumption is that committing writes to memory takes less time than an entire write operation. 
         [0016]    To further illustrate, consider the process of updating a particle in a physics based system. The particle state may include position, velocity, and several forces. A typical update may involve numerous read, update, and write operations, all of which would be encapsulated by a mutual-exclusion lock so that the state appears updated atomically (so that all members of state are consistent). 
         [0017]    Using traditional locking mechanisms, as illustrate in  FIG. 1 , the duration of a traditional lock  16  may include at least a read operation  10  consuming time to read the state, a compute operation  12  consuming time to perform one or more computations based on the state, and a commit operation  14  consuming time to return new values to the state members. 
         [0018]    In contrast, using embodiments of the present invention, as illustrated in  FIG. 2 , a mutual exclusion lock  26  may only be necessary during the commit phase  24  thereby allowing access during any read operation  20  or compute operation  22 . This is because embodiments of the present invention effect a separation between a readable copy and a writable copy of the state. So, in the illustrative example, a memory copy of the state can be made, via hardware registers (copy is retained in the registers), cache (CPU cache), main memory (via software), hardware backing-store or by other methods. Thus, the original state is blocked  26  only when the updated copy is written back, reducing the block time to only a memory write or commit operation  24  and eliminating the time delay of reading  20  and computations  22 . Note that, in some embodiments, the term “copy” may mean only that the write operations are storing to a different location than that which the read operations are reading from. An implementation of this invention can be realized via any mechanism that implements such an algorithm, such as by swapping memory pointers (ping-ponging memory images), stalling writes, cache flushes or other methods. 
         [0019]    In some embodiments, each resource may be associated with a lock state. The lock state may be any of the following: 
         [0020]    1) None 
         [0021]    2) Read 
         [0022]    3) Write 
         [0023]    4) Read+Write 
         [0024]    5) Commit 
         [0000]    The physical embodiment of a state may vary with each implementation. 
         [0025]    As threads try to access the resource, they may declare their intent (read or write) by executing either an EnterRead or EnterWrite algorithm. When they finish an operation, they may indicate such by executing either the ExitRead or ExitWrite algorithm. The following state table, Table 1, shows exemplary state transitions for the lock state, where the current state is shown across the top and the algorithm to be executed is shown at left. For example, when the state is None, executing EnterWrite will cause the state to become Write. 
         [0000]    
       
         
               
               
               
               
               
               
             
               
               
               
               
               
               
             
           
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                   
                   
                   
                 Read + 
                   
               
               
                   
                 None 
                 Read 
                 Write 
                 Write 
                 Commit 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                 EnterRead 
                 Read 
                 Read 1   
                 Read + 
                 Read + 
                 BLOCK 3   
               
               
                   
                   
                   
                 Write 
                 Write 
               
               
                 ExitRead 
                 ERROR 
                 None 2   
                 ERROR 
                 Write 2   
                 UNBLOCK 4   
               
               
                 EnterWrite 
                 Write 
                 Read + 
                 Write 1   
                 Read + Write 
                 BLOCK 3   
               
               
                   
                   
                 Write 
               
               
                 ExitWrite 
                 ERROR 
                 ERROR 
                 Commit 
                 Commit 
                 BLOCK 3   
               
               
                   
               
               
                   1 A counter will be incremented. 
               
               
                   2 The state may not actually change; a counter is decremented, and only if 0 does the state change. 
               
               
                   3 No state change occurs; the thread is blocked before returning from the algorithm. 
               
               
                   4 The read or write counters are decremented. If they are both zero, the write results are committed, the state is changed to None, and all blocked threads are released in order and their algorithms re-executed. 
               
             
          
         
       
     
         [0026]    In these exemplary embodiments, readers and writers proceed unhindered. All readers share a common copy of the resource; each writer acquires a unique copy. 
         [0027]    In these exemplary embodiments, when an ExitWrite occurs: 
         [0028]    the Commit state is entered 
         [0029]    the ExitWrite operation blocks until all outstanding readers and writers have retired 
         [0030]    All new Readers and writers are blocked until the Commit is completed 
         [0031]    In some known methods, all readers and writers are blocked for the entirety of the EnterWrite→ExitWrite sequence. However, in these embodiments, the blockages are restricted only to the ExitWrite operation. In some embodiments, serialization of resource accesses may not be guaranteed. For example, given two threads executing EnterWrite and EnterRead, in that literal order, the reading thread cannot know whether it will receive the version of the resource before the write operation began or after it finished. The following might occur: 
       Example 1 
       [0032]    Thread A: BeginWrite 
         [0033]    Thread B: BeginRead 
         [0034]    [End . . . operations occur in either order] 
       Example 2 
       [0035]    Thread A: BeginWrite 
         [0036]    Thread A: EndWrite 
         [0037]    Thread B: BeginRead 
         [0038]    Thread B: EndRead 
         [0039]    Clearly, thread B will see different versions in these examples; in Example 1, thread B will see the version before the write, and in Example 2 it will see the version after the right. In some applications, this is acceptable or desired. Each reader will see a self-consistent, complete version of the resource, although it may change immediately when the thread finishes reading it. 
       3-D Modeling Software Embodiment 
       [0040]    In 3-D modeling software, such as video games, a virtual world (or some portion thereof) may be modeled in PC memory in the form of [n] objects, each containing attributes that determine an object&#39;s location, appearance or other game characteristics. A typical game may have thousands of such objects; some being static parts of the environment, and many being dynamic, representing live entities such as other players. 
         [0041]    On current and future hardware, there is a need for wide, threaded execution, whereby objects can be accessed by many threads simultaneously. 
         [0042]    Now, consider the situation where [n] objects are interacted with by [m] threads. Some threads are responsible for rendering (read only access), while others are responsible for model updates (moving characters, etc; write operations). Each model update may be a lengthy operation including but not limited to: 
         [0043]    1) Considering the “presumed update” such as position, and 
         [0044]    a. Checking (reading) many other model objects to perform collision detection 
         [0045]    b. Sending and receiving network data to verify against other models 
         [0046]    Hence, each update operation may encapsulate significant processing, as well as many bracketed read operations to the same resource, or other resources, even in cases where only a few bytes will ultimately be written. 
         [0047]    Using traditional concurrency mechanisms, a write to some number of objects may stall rendering or other program features due to the mutual exclusion nature of the mechanism. Moreover, since writers block all readers, it would be difficult to ensure that race conditions don&#39;t occur when reads are bracketed by writes to objects being read by other writers. 
         [0048]    Accordingly, embodiments of the present invention may introduce some additional memory overhead but [in some cases] may also dramatically reduce resource contention, freeing threads to get more work done in less time. 
       Real-Time Measurements 
       [0049]    Experimental results show a much higher level of concurrency using an exemplary embodiment of the present invention. Total program throughput ranged from 0.98 (just slightly slower than simple reader+writer locking) to 3.4 (more than three times faster), depending upon specific software design and hardware capability. 
         [0050]    For further clarification, two logical and two physical embodiments will be discussed. 
       Logical Embodiments 
     1. Mutual Write Embodiments 
       [0051]    In these embodiments, any number of readers and writers can proceed concurrently, with threads being blocked only during the commission of any write. The side-effect of this logic is a lack of serialization. For example, if the protected resource is an integer, and the operation is the simple addition of 1, the result of approximately simultaneous writers is ambiguous. If the starting value is 1 and three writes occur, the result could be 2, 3, or 4, depending upon how much concurrency there was between the writers (whether they began with the same start value, or were executed somewhat more serially such that one or more began with the resulting value from the other). 
         [0052]    In some exemplary embodiments, the following process, illustrated in  FIG. 3  may be executed. In these embodiments, described from the perspective of a memory or resource manager, a manager receives a call  30  from Thread “A” as Thread “A” executes an EnterWrite or similar process directed to updating data referred to as “Data  1 .” In response to receiving the call  30 , the manager makes  31  a copy of Data  1 , which we will refer to as “Copy  1 A.” Copy  1 A is a copy of the data represented by Data  1  one, but stored at a different address so it can be modified without affecting Data  1 . This copy process may take place immediately after the call  30  is received or at any time up until Thread A enters the commit phase. The manager grants  32  write access of Copy  1 A to Thread A only and continues to grant  33  read access of Data  1  to Thread A. Thread A has no need of read access of Copy  1 A as read access of Data  1  is preserved at this time. The manager also continues to provide  34  read access of Data  1  to any other threads that request read access. 
         [0053]    Steps  30  to  33  may be repeated  35  for any other threads that seek write access to Data  1 , thereby causing the creation of additional copies of Data  1  (e.g., Copy  1 B), for which exclusive write access is granted to the treads that have requested them. At some point, Thread A will complete any reading and computing phases of its operation by writing an updated value to Copy  1 A and will execute  36  an ExitWrite or similar operation that will signal to the manager that the thread is ready to enter a commit phase. Upon receipt of this ExitWrite or similar call  36 , the manager may then block  37  Thread A until: a) any pending read requests are fulfilled and b) any pending write requests have followed similar procedures to Thread A&#39;s write request and are also blocked. At this point, for the commit phase, any new read requests and write requests for Data  1  are blocked  38  briefly. During the read/write blockage  38 , updated Copy  1  data, which was written to Copy  1  by Thread A, is written  39  to Data  1 . Following this write operation, all readers are unblocked  40 . If any write requests have been blocked, each write request may then be unblocked, in turn, and allowed to follow a process similar to that explained for Thread A. This process may repeat for each blocked write request. In these embodiments, blocked write requests may be unblocked in any order or randomly and no specific queue or order need be maintained. However, in some embodiments, write requests may be unblocked in the order in which their respective threads requested write privileges. 
         [0054]    Some of these embodiments may be described from the perspective of a thread that is attempting to write or update data. In these embodiments, illustrated in  FIG. 4 , Thread A may execute  50  an EnterWrite operation or a similar operation that sends a request to a memory or resource manager indicating that Thread A wants to write a value to Data  1 . In response, the manager may grant and Thread A may receive  51  write access to a copy of Data  1 , referred to as Copy  1 A. In some embodiments, Copy  1 A may be created in response the request received from Thread A. Thread A may then proceed to read from Data  1 , if desired, and may compute, if desired, any values based on Data  1 . In some embodiments, Thread  1  may not need to read from Data  1  or compute any values, however, using these embodiments, access to Data  1  is preserved to any threads that desire read or write access during a read or computation process executed by Thread A. 
         [0055]    Thread A may then update or write  52  a value to Copy  1 A, wherein this value is intended for Data  1 . At this point, Thread A may execute an ExitWrite operation or a similar operation that indicates  53  to the manager that it wishes to enter the commit phase to update Data  1 . When this occurs, Thread A is blocked until any pending read requests are fulfilled and until any other write requests for Data  1  are also blocked. Any new read or write requests for Data  1  are also blocked while the manager copies data from Copy  1 A to Data  1  so as to update Data  1  with data originating from Thread A. After new data is written to Data  1 , all read requests may be unblocked and any write requests may be unblocked, however, these operations will have no impact on Thread A unless it has requested further read and/or write operations. 
       2. Exclusive Write 
       [0056]    This embodiment also comprises the advantage that blocking is only performed during the commit operation, but further imposes a restriction that writes are serialized, such that when any writer uses EnterWrite, other writers are blocked until the first write operation completes. This embodiment would resolve the integer ambiguity, requiring that for any [n] writers, writer [m] sees the results of writer [m−1] as the resource&#39;s initial value. Table 2 represents a state table for these embodiments. 
         [0000]    
       
         
               
               
               
               
               
               
             
               
               
               
               
               
               
             
           
               
                   
                 TABLE 2 
               
               
                   
                   
               
               
                   
                   
                   
                   
                 Read + 
                   
               
               
                   
                 None 
                 Read 
                 Write 
                 Write 
                 Commit 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                 EnterRead 
                 Read 
                 Read 1   
                 Read + 
                 Read + 
                 BLOCK 3   
               
               
                   
                   
                   
                 Write 
                 Write 
               
               
                 ExitRead 
                 ERROR 
                 None 2   
                 ERROR 
                 Write 2   
                 UNBLOCK 4   
               
               
                 EnterWrite 
                 Write 
                 Read + 
                 BLOCK 3   
                 Read + 
                 BLOCK 3   
               
               
                   
                   
                 Write 
                   
                 Write 
               
               
                 ExitWrite 
                 ERROR 
                 ERROR 
                 Commit 
                 Commit 
                 ERROR 
               
               
                   
               
               
                   1 A counter will be incremented. 
               
               
                   2 The state may not actually change; a counter is decremented, and only if 0 does the state change. 
               
               
                   3 No state change occurs; the thread is blocked before returning from the algorithm. 
               
               
                   4 The read or write counters are decremented. If they are both zero, the write results are committed, the state is changed to None, and all blocked threads are released in order and their algorithms re-executed. 
               
             
          
         
       
     
         [0057]    In some exemplary embodiments, the following process, illustrated in  FIG. 5  may be executed. In these embodiments, described from the perspective of a memory or resource manager, a manager receives a call  60  from Thread “A” as Thread “A” executes an EnterWrite or similar process directed to updating data referred to as “Data  1 .” In response to receiving the call  60 , the manager makes  61  a copy of Data  1 , which we will refer to as “Copy  1 A.” Copy  1 A is a copy of the data represented by Data  1  one, but stored at a different address so it can be modified without affecting Data  1 . This copy process may take place immediately after the call  60  is received or at any time up until Thread A is ready to enter the commit phase. The manager grants  62  write access of Copy  1 A to Thread A only and continues to grant  63  read access of Data  1  to Thread A. Thread A has no need of read access of Copy  1 A as read access of Data  1  is preserved at this time. The manager also continues to provide  64  read access of Data  1  to any other threads that request read access. 
         [0058]    Steps  60  to  63  may be repeated  65  for any other threads that seek write access to Data  1 , thereby causing the creation of additional copies of Data  1  (e.g., Copy  1 B for Thread B), for which exclusive write access is granted to the treads that have requested them. At some point, Thread A will complete any reading and computing phases of its operation by writing an updated value to Copy  1 A and will execute  66  an ExitWrite or similar operation that will signal to the manager that the thread is ready to enter a commit phase. Upon receipt of this ExitWrite or similar call  66 , the manager may then block  67  Thread A until: a) any pending read requests are fulfilled and b) any pending write requests have followed similar procedures to Thread A&#39;s write request and are also blocked and managed. Management of blocked write requests may be handled in several ways. In some embodiments, a queue may be constructed to maintain an order of release for the blocked write requests. This order may be the order in which the write requests are received by the manager or some other order. In some embodiments, the blocked write requests may be maintained in a pool and later released in the order in which they execute an ExitWrite operation. In other embodiments, locked write requests may later be released in other orders or randomly at appropriate times. 
         [0059]    At this point, any new read requests and write requests for Data  1  are blocked  68  briefly. These blocked read and write requests may also be managed with queues or by other methods such as those described for the already-executing write requests above. During the read/write blockage  68 , updated Copy  1  data that was written to Copy  1  by Thread A is written  69  to Data  1 . Following this write operation, all readers are unblocked  70 . If any write requests have been blocked and queued  67 , the next write request in the queue may then be unblocked and allowed to follow a process similar to that explained for Thread A. This process may repeat for each blocked and queued write request. 
         [0060]    Performance of these embodiments from the perspective of Thread A will be essentially the same as that described above in relation to  FIG. 4 . However, other threads, which have requested write access to Data  1  after Thread A may be treated differently based on management of blocked write requests as explained above. 
       Physical Embodiments 
     1. Software Embodiments 
       [0061]    These embodiments may be easily implemented in nearly any programming language in use today. They can be built from scratch, or built using a current synchronization mechanisms as a basis. Furthermore, some embodiments may be added to a language compiler in such a way as to be realized at runtime without explicit coding on the part of the programmer. 
       2. Hardware Embodiment 
       [0062]    These embodiments may be implemented in hardware by, for example, adding a “backing store” of memory that is used for write operations and a trivial set of instructions that can be used to commit writes to shared memory. 
         [0063]    The terms and expressions which have been employed in the foregoing specification are used therein as terms of description and not of limitation, and there is no intention in the use of such terms and expressions of excluding equivalence of the features shown and described or portions thereof, it being recognized that the scope of the invention is defined and limited only by the claims which follow.