Patent Document

BACKGROUND 
       [0001]    Concurrent computing environments use ever more powerful and complex multicore and/or multi-CPU platforms, with highly multithreaded operations. Especially where multiple and simultaneous producers (e.g., writers) and consumers (e.g., readers) operate on a given memory structure, this heightens the risk of process and/or thread contention, latency, and inefficient memory usage. As a result, concurrent computing can be associated with significant performance constraints. Such constraints can slow current processes and impose an opportunity cost of foregone added ones. 
         [0002]    Mechanisms have been designed to address these constraints. These include locking mechanisms that can selectively brake producers so that consumers can “catch up.” Disadvantages of locking mechanisms are known and can include significant wait times, thread stalls or thread death, and limited scalability. A lock-free mechanism, however, presents challenges as well, including the A-B-A problem, where state can appear identical from a first read to a second read, but in fact a separate process has “secretly” modified shared memory before changing it back again. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0003]      FIG. 1  illustrates an example computing environment in accord with embodiments. 
           [0004]      FIG. 2  illustrates an example ring buffer in accord with various embodiments. 
           [0005]      FIG. 3  illustrates an example queue and three example ring buffers in accord with various embodiments. 
           [0006]      FIGS. 4A-4E  illustrate an example scenario whereby the size of a ring buffer is adjusted. 
           [0007]      FIGS. 5A and 5B  are example flowcharts related to an enqueuing operation providing writing functionality in connection with a ring buffer. 
           [0008]      FIGS. 6A and 6B  are example flowcharts related to a dequeuing operation providing reading functionality in connection with a ring buffer. 
           [0009]      FIG. 6C  is an alternate embodiment relating to a dequeuing operation. 
       
    
    
     DETAILED DESCRIPTION 
       [0010]    In the following description, reference is made to the accompanying drawings which illustrate several embodiments of the present invention. It is understood that other embodiments may be utilized, and mechanical, compositional, structural, electrical and other operational changes may be made without departing from the spirit and scope of the present disclosure. The following detailed description is not to be taken in a limiting sense, and the scope of the embodiments of the present invention is defined only by the claims of the issued patent. 
         [0011]      FIG. 1  depicts an example architecture in accord with embodiments. System  100  comprises computing functionality, both local and distributed. System  100  may have a unit  102  comprising one, two or more central processing units  104 , 106 , which can be considered processors. Unit  102  can be a server or servers. A processor can be single-core  104 , or have multiple cores  108 ,  110  where more than one processor can be placed on a “chip”. The processor  104 ,  106  can execute instructions by many techniques, in concurrent processes and threads. Many variations of multiprocessor and/or multicore systems can be used. There may be multiple memory components. Certain memory components can be considered main memory  120 , which may be shared among one or more processors  104 ,  106 . Other memory components can be considered cache memory  112 ,  114 ,  116 ,  118 , which may be more closely associated with a specific processor  104 ,  106 . Caches can be divided into levels, e.g., L1 cache  112 ,  114 , L2 cache  116 ,  118 , and more. A bus  130  or other interconnection functionality can permit communication within and beyond a system. An additional unit  124  with comparable functionality can be in operative communication with a first unit  102 . There can be display and input/output functionality  122 . Also, a network or networks  126  can be present. Additionally, outside memory  128  or memories can be utilized. It will be readily appreciated that many interoperative variations, configurations, and architectures can be employed in accord with embodiments disclosed herein. 
         [0012]    In  FIG. 2 , an example ring buffer  200  is depicted in accord with embodiments. A ring buffer can be a data structure associated with and/or stored by one or more memory components. Ring buffer  200  can have attributes including a header  210  associated with at least one or more buckets  212 ,  214 ,  216 ,  218 ,  220  in an array. Each bucket can be considered an element of such array. By way of non-limiting example, ring buffer  200  can have a capacity of 32 buckets. Buckets  214 ,  216  and  218  represent single buckets. Buckets  212  and  220  represent multiple buckets. Header  210  contains fields that among other functions can manage reading and writing. Such fields can include next  240 , front  241 , padding1  242 , back  243 , end  244 , padding2  248 , capacity  250 , and mask  252 . 
         [0013]    An item  230  can be placed in ring buffer  200 . The item can be a pointer to a memory structure; it can also be the item itself rather than a pointer. In addition, a position variable  232  can track the logical position of such item. Main variables that are modified by enqueue and dequeue operations in the header  210  can be defined such that they will occur in separate cache lines, helping to minimize contention among threads and allow operations to occur in parallel without cache lines being invalidated by updates in another thread. Counts can be used to track logical positions in queue operations and to know if the ring in question is empty. 
         [0014]    The struct configuration can be defined to facilitate implementing various embodiments. However, added configurations can be used such as classes, or other method of allocating compound structures. 
         [0015]    As seen in  FIG. 2 , in ring buffer  200  a front  241  field references the position at which the last item was written, while the back  243  field references the next field that can be read. When front and back are equal, the buffer can be considered empty. As front  241  field reaches the end of the ring buffer it continues to be incremented, but a power of 2 modulo operation can be performed on the incremented front value before accessing the ring so that the ring logically wraps. A modulo for a size that is a power of 2 can be performed by an AND operation with a mask that is produced by subtracting 1 from the size; however, other multiples or powers can be used in connection with performing a modulo operation. 
         [0016]    In other words, the position value stored in each bucket can represent a logical position based on continued wrapping of the ring. When front  241  logically wraps to the point that it collides with back  243 , a new and larger ring can be created. New writes to the queue can occur in the new ring while reading can continue in the original ring. This can continue until the ring is empty, at which point the reads can advance to the new ring also. 
         [0017]    In embodiments, as depicted in  FIG. 3 , queue  310  can be utilized. Queue  310  can have a reader portion and writer portion aligned to be in separate cache lines. The reader portion can have two pointers to ring structures and a reader_count  316  that acts as a reference count of reader processes. Head  312  pointer can point to the first ring in a linked list of rings  330 ,  332 ,  334 , and drain pointer  314  can point to the ring currently being drained of items. The writer portion of the queue can have a fill  320  pointer to the ring currently being filled and a writer count that is a reference count of active writer processes. The writer count  322  and reader count  316  variables can act as reference counts of accessing processes and allow the system safely to release memory of rings that are no longer referenced. In addition, padding  318  can be used to reduce the possibility of conflict due to cache line sharing. Next field pointers  336  and  338  are depicted. 
         [0018]    Initial queue initialization and ring allocation can be performed. Initializing can comprise zeroing reader and writer counts, allocating the initial ring (with an example length of 32), and setting the end  244  field to an obviously invalid value that will not be matched by the back  243  field until it is reset. The number of buckets in the ring can be an integer that is a power of two and can be obtained by doubling the previous ring size to allow for efficient modulo operations that map the logical position to the actual array index. 
         [0019]      FIGS. 4A-4E  depicts a sequence of state changes illustrating a relationship between a queue and associated ring buffer(s), and more specifically how added ring buffers can be declared and utilized upon detection of a potential overflow condition and how pointers in a queue can adjust accordingly.  FIG. 4A  depicts an example state upon initialization. By way of non-limiting example, capacity in ring  1  is set to 4.  FIG. 4B  depicts an example state upon detection of a first overflow. It will be noted that capacity of ring  1  is 4, and ring  2  is 8, in accord with embodiments where the newly allocated ring has double the capacity.  FIG. 4C  depicts an example state where the first overflow buffer is draining and a second overflow buffer is filling. It will be noted that capacity of ring  1  is 4, ring  2  is 8, and ring  3  is 16.  FIG. 4D  depicts an example where a second overflow buffer is filling, and draining.  FIG. 4E  depicts an example state where a second overflow buffer is filling and draining, and previous ring buffers have been released. 
         [0020]    An enqueue operation can be performed, which employs previously discussed data structures. Conceptually, the buffer can be treated as if it were infinitely long, and the system can use a modulo operation to map onto actual ring size. To make the modulo operation even more efficient, ring size can be a value of the power of two, so that an AND operation with a mask can produce an index within range of the ring size. The enqueue operation can use three atomic non-blocking operations: atomic_fetch_and_add (AFA), atomic_fetch_and_subtract (AFS), and compare_and_swap (CAS). The AFA and AFS operations can return the value of the integer field before the update occurs. An atomic increment of the writer reference count and atomic decrement can be performed. A modulo operation can map the logical position to the actual index into the ring using the mask to point to the current bucket in the ring. The CAS operation can advance the ring front  241  value. 
         [0021]    The enqueue operation can declare certain variables including index, prey, and success. These variables can comprise local fields that hold fixed copies of their respectively named fields, which can change at any moment due to other writers&#39; changing them. The local fields are used to “fix” a value in time that will not change in order to compare against another changing field. Also, an INTEGER_MAX can be declared which is the maximum integral value for the size of an integer field. 
         [0022]    In accord with embodiments,  FIGS. 5A and 5B  show how the current fill ring can be added to, and how the system can dynamically adjust utilizing a logical perspective if the ring buffer—which has a finite number of buckets from a physical perspective—becomes full. A result can be set equal to SUCCESS  504 . The writer_count is atomically incremented  506 . A pointer to the current ring buffer being filled is loaded  508 . The fill buffer front value is read into prey  510 . It is clear that if buckets become progressively filled then, given the circular nature of the data structure, physical overflow is possible unless measures are taken. Accordingly, a determination can be performed  512  to establish whether the prey front value has wrapped the buffer by exceeding the value of back plus capacity, i.e., the buffer is full. In other words, a check is made whether it is acceptable to keep writing to the current ring buffer. 
         [0023]    If the result of this determination  512  is negative, the index can be set equal to prey+1 at  514 , which advances index to the next position. The bucket pointer is set to the bucket at the physical index equal to index modulo ring buffer capacity  516 . The modulo operation can be done via use of a mask (using an AND operation if the size of the ring buffer is a power of 2). It is then tested whether the bucket is empty  518 . If the bucket is not empty, control passes back to step  508  where a pointer is loaded to the current ring buffer being filled. If the bucket is empty, then a CAS swap front from prey to index is done and a determination is made whether this operation is successful  520 . If successful, the bucket is updated with the item and position is set equal to index  522 , and the writer_counter is atomically decremented  524  such as by an AFS; if unsuccessful, control passes back to step  508  where a pointer is loaded to the current ring buffer being filled. In this way items can be added to the ring buffer. 
         [0024]    However, the determination in step  512  can return a positive result. This will be so where the logical position of the ring has been advanced to such an extent as to comprise a potential overflow condition. Put simply, the ring has “wrapped.” Accordingly, measures are taken to permit continued efficient non-locked operations, including by declaring a second, expanded ring buffer. 
         [0025]    Accordingly, once it has been detected that the buffer has wrapped  512 , it is determined whether prey ring buffer front is less than INTEGER_MAX  528 , indicating that it is blocked from further writing. A rationale is to attempt to block processes from adding to the ring (though it is still possible). If the answer at step  528  is yes, an attempt is made to CAS ring buffer front with prey  530 . This check attempts to block further writing to the ring buffer by other processes. If the attempt in  530  is not successful, control returns to step  508 ; if it is successful, the end value is set for ring buffer to prey front  532  (setting this value lets dequeue processes know when the ring buffer is empty). Now, a new ring buffer is allocated twice the size (or any size that is larger than the current size) of the current ring buffer  534 . And, if the answer is no at step  528 , control passes such that a new ring buffer is allocated twice the size (or any size that is larger than the current size) of the current ring buffer  534 . 
         [0026]    A second, expanded ring has now been allocated. This functionality can be extended upon further iterations through the procedure such that multiple rings can be dynamically allocated as needed, each double the size of the prior one (or any size that is larger than the prior one). 
         [0027]    It is tested whether the ring buffer allocation was successful  536 . If yes, next is set equal to current ring buffer next pointer  538 , and it is determined if next pointer in the ring buffer is empty  540 . If no, an attempt is made to advance queue fill pointer to next ring buffer to fill with a CAS  546 , and the allocated ring buffer can be freed  548 . If the answer in step  540  is yes, however, it is determined whether a CAS with the last ring buffer in the list is successful  542 . If no, the allocated ring buffer can be freed  548 ; if yes, the queue fill pointer can be pointed to the new ring buffer with a CAS. 
         [0028]    Returning to step  536 , where it was determined if the ring buffer allocation  536  was successful, if the answer is no, the result can be set to NOMEM indicating out of memory, and writer_count can be atomically decremented  524 . It should be appreciated that some operating systems will simply kill the process if memory allocation cannot be fulfilled, rendering this step moot. 
         [0029]    Accordingly, a new ring can be allocated with capacity larger than and/or a multiple of the current ring, and the new ring can be added to the end of a linked list. 
         [0030]    Besides enqueue operations disclosed above, reading functionality can be performed via a dequeue operation disclosed in embodiments below. 
         [0031]    In  FIG. 6A , a result can be set equal to SUCCESS  604 . The reader count can be atomically incremented  606 . A pointer can then be loaded to the current ring buffer being drained  608 . 
         [0032]    The drain buffer back value is read into prey  610 , and an index set equal to prey+1 at step  612 . The bucket pointer is set to a bucket at physical index equal to index modulo ring buffer capacity  614 . Again, this can be accomplished by a modulo operation using a mask and ANDing as appropriate. At this point, it can be determined whether the logical index matches bucket logical position  616 . In other words, it can be determined if the logical position of the item in the current bucket matches the current back of the ring counter—again, put simply, it is determined whether the ring has wrapped. 
         [0033]    If the answer at step  616  is yes, it is then determined whether the bucket is empty  618 . If the bucket is empty, control passes to step  608 . If the bucket is not empty, it is determined whether the CAS back from prey to index was successful. If no, control passes to step  608 ; if yes, item pointer is set equal to bucket item empty bucket  622 . For context, it is possible for a writer to be in the actual process of writing to a bucket while a reader is attempting to access the very same bucket. By checking that both the position matches and that the item is present, the reader knows that the writer has completed the full write operation. On some systems, with a conservative memory update policy, the position check only might be appropriate; however, on other systems with a more relaxed memory update policy, updates can be seen to occur out of order. For these reasons, both can be checked. Then, reader_count is atomically decremented  624 . If the answer at step  616  is no, as seen in  FIG. 6B . it is determined whether the current drain ring buffer is the same as the current fill ring buffer  628 . 
         [0034]    If the answer at step  628  is no, it is determined whether the ring buffer is blocked for writes and at end of buffer  644 , and if the answer is no, control passes back to step  608 . If the answer is yes, then next is set to the ring buffer following the current ring buffer  646 , an attempt is made to move the current queue draining buffer to next  648 , and control passes back to step  608 . It will be appreciated that one purpose of step  644  is to use values in enqueue operations to establish if it is acceptable to start draining the next ring buffer. 
         [0035]    If the answer at step  628  is yes, then result is set to EMPTY  630 , and head is set to head of queue ring buffer list  632 . It is then determined whether head is the same as current draining ring buffer  634 . If yes, reader_count is atomically decremented  624 . If no, next is set to ring buffer following head of list  636 . It will be appreciated that one purpose of step  628  is to check whether the ring buffer is empty before attempting to advance. 
         [0036]    It is then determined if there is only one reader, and no writers  638 . If no, control passes to step  624  and reader_count is atomically decremented. 
         [0037]    If, however, it is determined that there is only one reader and no writers at step  638 , this is a condition that can indicate it may be permissible to free memory safely. Put another way, the check can establish that the head ring buffer can be released as no other process references the memory. 
         [0038]    Accordingly, if there is only one reader and no writers  638 , it is determined whether a CAS of queue head pointer to next is successful  640 . If successful, the head ring buffer can be freed  642 , and control again can pass to step  624  where reader_count is atomically decremented. 
         [0039]    Certain programming languages, such as Java or C#, can support memory deallocation on a largely routine basis. Thus, to the extent deallocation operations are carried out on a systematic basis such as with Java, C#, or other language, in embodiments it is possible that specific calculation of the quantity of readers and/or writers may be adjusted to account for this type of “garbage collection”, potentially rendering this step unneeded. In addition, for the above reasons, freeing the buffer in step  548  may not be needed in embodiments. Certain other languages, such as C, C++, or other language may not currently support this functionality on a largely routine basis, and may require manual memory management to a lesser or greater degree. 
         [0040]      FIG. 6C  discloses an added embodiment relating to dequeue operations. In this embodiment it is determined whether the ring buffer is empty by checking fields in the parent queue structure only without having directly to access the next logical bucket in ring buffer memory. It permits determination of whether a ring is not blocked and not wrapped, or not at an end. The process in in  FIG. 6C  is considered to continue from  FIG. 6A , as illustrated. In step  650 , it is determined whether the ring is not blocked and not prey not wrapped front, or ring is blocked and prey is not at end. If the answer is yes, it is determined whether the logical index matches the bucket logical position  652 : if no, control returns to step  608 , and if yes, control passes to step  618 . If, however, the answer at step  650  is no, control passes to step  628 . Subject to the foregoing, and the steps depicted in  FIG. 6C , the remainder of steps in  FIGS. 6A and 6B  are considered to apply. 
         [0041]    While the invention has been described in terms of particular embodiments and illustrative figures, those of ordinary skill in the art will recognize that the invention is not limited to the embodiments or figures described. 
         [0042]    Some portions of the detailed description are presented in terms of procedures, steps, logic blocks, processing other symbolic representations of operations on data bits that can be performed on computer memory. Certain steps may be performed by some or all of hardware, software, firmware, or combinations thereof. 
         [0043]    The program logic described indicates certain events occurring in a certain order. Those of ordinary skill in the art will recognize that the ordering of certain programming steps or program flow may be modified without affecting the overall operation performed by the preferred embodiment logic, and such modifications are in accordance with the various embodiments of the invention. Additionally, certain of the steps may be performed concurrently in a parallel process, as well as performed sequentially. 
         [0044]    Therefore, it should be understood that the invention can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is not intended to be exhaustive or to limit the invention to the precise form disclosed. It should be understood that the invention can be practiced with modification and alteration and that the invention be limited only by the claims and the equivalents thereof.

Technology Category: 3