Patent ID: 9069566
Filing Date: 2015-06-30
Classification: G06F

Abstract:
1. A method of implementing a multiple writer single reader queue in a lock free and a contention free manner, the method comprising: receiving a plurality of payloads from a plurality of users; assigning a first payload of the plurality of payloads to a first writer thread of a plurality of writer threads, and assigning a second payload of the plurality of payloads to a second writer thread of the plurality of writer threads; creating a first writer queue by the first writer thread exclusively owned by the first writer thread, and creating a second writer queue by the second writer thread exclusively owned by the second writer thread; enqueuing the first payload as a first queue entry, said first queue entry including a first queue entry number, a first writer queue identifier, a first entry type, a first writer reference, wherein the first payload is enqueued into the first writer queue identified by the first writer queue identifier by the first writer thread identified by the first writer reference, and enqueuing the second payload as a second queue entry, said second queue entry including at least one of a second queue entry number, a second writer queue identifier, a second entry type, a second writer reference, wherein the second payload is enqueued into the second writer queue identified by the second writer queue identifier by the second writer thread identified by the second writer reference; wherein the first and second queue entry numbers are generated by a queue entry counter which generates queue entry numbers in unique and increasing order in atomic fashion; dequeuing the first queue entry from the first writer queue and the second queue entry from the second writer queue in order of their respective queue entry numbers, and inserting the retrieved first and second queue entries into a sorted queue maintained by a reader thread, the dequeuing and inserting being done by the reader thread and whereby the first and second queue entries are inserted into the sorted queue in order of their respective queue entry numbers; identifying a queue entry in the sorted queue having the lowest queue entry number; enqueuing another queue entry into the sorted queue from the writer queue from which the queue entry having the lowest queue entry number was obtained; dequeuing from the sorted queue the queue entry having the lowest queue entry number for processing by the reader thread; and processing the dequeued queue entry from the sorted queue.