Implementation of a multiple writer single reader queue in a lock free and a contention free manner

A computer program product stored on a non-transitory computer-readable medium that when executed by a processor, performs a method of implementing a multiple writer single reader queue in a lock free and a contention free manner, 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.

A system implementing a multiple writer single reader queue in a lock free and a contention free manner, the system comprising:

• an electronic device for displaying a plurality of payloads;
• a memory that stores instructions;
• a processor;
• and
• a communication interface in electronic communication with the electronic device and the processor, the processor responsive to the instructions to receive a plurality of payloads from a plurality of users;
• assign a first payload of the plurality of payloads to a first writer thread of a plurality of writer threads, and assign a second payload of the plurality of payloads to a second writer thread of the plurality of writer threads;
• create a first writer queue by the first writer thread exclusively owned by the first writer thread, and create a second writer queue by the second writer thread exclusively owned by the second writer thread;
• enqueue 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 enqueue 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, and 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;
• dequeue 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;
• identify a queue entry in the sorted queue having the lowest queue entry number;
• enqueue another queue entry into the sorted queue from the writer queue from which the queue entry having the lowest queue entry number was obtained;
• dequeue from the sorted queue the queue entry having the lowest queue entry number for processing by the reader thread;
• and
• process the dequeued queue entry from the sorted queue.