Search

EP-4068094-B1 - LOCK-FREE RING BUFFER

EP4068094B1EP 4068094 B1EP4068094 B1EP 4068094B1EP-4068094-B1

Inventors

  • JEFFERY, KEITH

Dates

Publication Date
20260506
Application Date
20220330

Claims (12)

  1. A method (800) for writing, by a computing thread, data to a ring buffer, the method comprising: determining (802) whether the ring buffer is full; and in response to determining that the ring buffer is not full: reserving (804) an element of the ring buffer for writing the data, wherein reserving the element comprises incrementing a size variable corresponding to a number of stored elements in the ring buffer; reserving (806) a portion of the ring buffer at which the data is to be written, wherein the portion includes a plurality of elements of the ring buffer, and reserving the portion of the ring buffer comprises reserving each element of the plurality of elements to a different index of the ring buffer; determining (808) whether a state of the portion of the ring buffer is in change by at least one other computing thread; and in response to determining that the state of the portion of the ring buffer is not in change by the at least one other computing thread: marking (810) the state of the portion of the ring buffer as being in change by the computing thread; and writing (812) the data to the portion of the ring buffer.
  2. The method of Claim 1, wherein determining (802) whether the ring buffer is full is based on an atomic variable that represents the number of stored elements in the ring buffer.
  3. The method of Claim 1 or 2, wherein determining (808) whether the state of the portion of the ring buffer is in change by the at least one other computing thread comprises determining whether a state of each element of the plurality of elements is in change by at least one other computer thread.
  4. The method of any preceding claim, wherein determining (808) whether the state of the portion of the ring buffer is in change by the at least one other computing thread is based on a state variable having one of : a first value of the state variable corresponds to an unoccupied state; a second value of the state variable corresponds to an in-transition state; and a third value of the state variable corresponds to an occupied state.
  5. The method of Claim 4, wherein marking (810) the state of the portion of the ring buffer as being in change by the computing thread comprises marking (updating) the state variable to have the second value.
  6. The method of Claim 4, wherein: the portion of the ring buffer comprises a plurality of elements associated with the ring buffer; and marking (810) the state of the portion of the ring buffer as being in change by the computing thread comprises marking (updating) the state variable of a corresponding at least one element of the plurality of elements to have the second value.
  7. The method of Claim 6, wherein writing (812) the data to the portion of the ring buffer comprises writing a respective subset of the data to the corresponding at least one element of the plurality of elements.
  8. The method of any of Claims 4 to 7, further comprising: in response to writing the data to the portion of the ring buffer, marking (updating) (814) the state variable to have the third value.
  9. A machine-readable non-transitory medium having stored thereon machine-executable instructions for writing, by a computing thread, data to a ring buffer, the instructions comprising: determining (802) whether the ring buffer is full; and in response to determining that the ring buffer is not full: reserving (804) an element of the ring buffer for writing the data, wherein reserving the element comprises incrementing a size variable corresponding to a number of stored elements in the ring buffer; reserving (806) a portion of the ring buffer at which the data is to be written, wherein the portion includes a plurality of elements associated with the ring buffer, and reserving the portion of the ring buffer comprises reserving each element of the plurality of elements to a different index of the ring buffer; determining (808) whether a state of the portion of the ring buffer is in change by at least one other computing thread; and in response to determining that the state of the portion of the ring buffer is not in change by the at least one other computing thread: marking (810) the state of the portion of the ring buffer as being in change by the computing thread; and writing (812) the data to the portion of the ring buffer.
  10. The machine-readable non-transitory medium of Claim 9, wherein determining (802) whether the ring buffer is full is based on an atomic variable that represents the number of stored elements in the ring buffer.
  11. A method (900) for reading data from a ring buffer by a computing thread, the method comprising: determining (902) whether the ring buffer is empty; in response to determining that the ring buffer is not empty: clearing (904) an element of the ring buffer storing the data, wherein clearing (904) the element comprises decrementing a size variable corresponding to a number of stored elements in the ring buffer; identifying (906) a portion of the ring buffer from which the data is to be read; determining (908) whether a state of the portion of the ring buffer is in change by at least one other computing thread; and in response to determining that the state of the portion is not in change by the at least one other computing thread: marking (910) the state of the portion of the ring buffer as being in change by the computing thread; reading (912) the data from the portion of the ring buffer; and destroying (914) the data in the portion of the ring buffer.
  12. A machine-readable non-transitory medium having stored thereon machine-executable instructions for reading, by a computing thread, data from a ring buffer, the instructions comprising: determining (902) whether the ring buffer is empty; in response to determining that the ring buffer is not empty: clearing (904) an element of the ring buffer storing the data, wherein clearing (904) the element comprises decrementing a size variable corresponding to a number of stored elements in the ring buffer; identifying (906) a portion of the ring buffer from which the data is to be read; determining (908) whether a state of the portion of the ring buffer is in change by at least one other computing thread; and in response to determining that the state of the portion is not in change by the at least one other computing thread: marking (910) the state of the portion of the ring buffer as being in change by the computing thread; reading (912) the data from the portion of the ring buffer; and destroying (914) the data in the portion of the ring buffer.

Description

BACKGROUND A ring buffer, also known as a circular buffer, is a queue (e.g., a first-in-first-out queue) with fixed storage space characteristics. As long as the number of unconsumed elements in the ring buffer does not exceed the (fixed) storage space, the buffer acts as an infinite queue with no dynamic storage overhead. Depending on the implementation, consumers (e.g., an entity seeking to read data from the ring buffer) may encounter a fail or a block if the queue is empty, while producers (e.g., an entity seeking to write data into the ring buffer) may encounter a fail or a block if the queue is full. Document US2013/0246672 describes an adaptive multi-thread buffer supports multiple writer process and reader processes simultaneously without blocking. Writer processes are assigned a reserved write slot using a writer index that is incremented for each write request. When a reserved write slot is not null, the buffer is resized to make room for new data. Document US 2019/0236749 describes methods and devices for managing first-in first-out (FIFO) queues in graphics. A write operation can be executed by multiple write threads on a graphics processing unit (GPU) to write data to memory locations in the multiple pages of memory. SUMMARY With respect to various embodiments disclosed herein, techniques are described for writing data to (or reading data from) a ring buffer without requiring the use of locks. By way of example, a lock-free ring-buffer is implemented using single-variable atomic operations (e.g., 32-bit single-variable atomic operations). Extensions for two-variable compare-and-swap functions are not necessarily required. Such a buffer does not require dynamic storage management, except for potential initial allocation. Also, it may outperform a naive locking ring buffer. Also, it does not require knowledge of the number of producers or consumers that may use the buffer, which are numbers that can change dynamically at run-time. Also, such a buffer can be used for inter-device memory transactions, including between a central processing unit (CPU) (a first device) and a graphics processing unit (GPU) (a second device) of a computing device, including communication between the CPU and the GPU. With respect to GPU, a single-producer batch push function is constructed so as to require fewer memory transactions. Because GPU architectures may not support native locks, the appeal of lock-free queues may be further enhanced. According to at least one embodiment, a method for writing, by a computing thread, data to a ring buffer is disclosed. The method includes determining whether the ring buffer is full. In response to determining that the ring buffer is not full, the method further includes: reserving an element of the ring buffer for writing the data, wherein reserving the element includes incrementing a size variable corresponding to a number of stored elements in the ring buffer; reserving a portion of the ring buffer at which the data is to be written, wherein the portion includes a plurality of elements of the ring buffer, and reserving the portion of the ring buffer comprises reserving each element of the plurality of elements to a different index of the ring buffer; and determining whether a state of the portion of the ring buffer is in change by at least one other computing thread. In response to determining that the state of the portion of the ring buffer is not in change by the at least one other computing thread, the method further includes: marking the state of the portion of the ring buffer as being in change by the computing thread; and writing the data to the portion of the ring buffer. According to at least one embodiment, a machine-readable non-transitory medium has stored thereon machine-executable instructions for writing, by a computing thread, data to a ring buffer. The instructions include determining whether the ring buffer is full. In response to determining that the ring buffer is not full, the instructions further include: reserving an element of the ring buffer for writing the data, wherein reserving the element comprises incrementing a size variable corresponding to a number of stored elements in the ring buffer; reserving a portion of the ring buffer at which the data is to be written, wherein the portion includes a plurality of elements of the ring buffer, and reserving the portion of the ring buffer comprises reserving each element of the plurality of elements to a different index of the ring buffer; and determining whether a state of the portion of the ring buffer is in change by at least one other computing thread. In response to determining that the state of the portion of the ring buffer is not in change by the at least one other computing thread, the instructions further include: marking the state of the portion of the ring buffer as being in change by the computing thread; and writing the data to the portion of the ring buffer. According to at least one embodiment