Adaptive multi-threaded buffer

• US 8,904,067 B2
• Filed: 03/13/2012
• Issued: 12/02/2014
• Est. Priority Date: 03/13/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Saputra, Erwien
• Primary Examiner(s): Tsai, Henry
• Assistant Examiner(s): Shyu, Jing-Yih
• Application Number:
  US13/419,306
• Publication Number:
  US 20130246672A1
• Time in Patent Office: 994 Days
• Field of Search: None
• US Class Current: 710/56
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

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. Reader processes are assigned a reserved read slot using a reader index that is incremented for each read request. When data is read out to the reader process, the read slot content is set to null. When a writer process attempts to write null data to a write slot, the buffer replaces the null write data with an empty value object so that content of the buffer is null only for empty slots. When an empty value object is read from a slot, the buffer replaces the content with null data to send to the reader process.

Claims

1. A method comprising:

receive a request from a writer process executing on a processor to write data to a buffer;

increment a writer index to a next slot in the buffer;

reserve a first write slot for the writer process; and

write data from the writer process to the first write slot;

receive a request from a reader process to read data from the buffer;

increment a reader index to reserve a read slot for the reader process;

read the content of the read slot and set the slot content to null in an atomic manner;

if the read slot content is null, then determine whether the buffer has been resized;

if the buffer has been resized, increment the reader index;

reserve a new read slot for the reader process; and

read the content of the new read slot and set the slot content to null in an atomic manner.

2. The method of claim 1, further comprising:

identify when the content of the first write slot is not null; and

resize the buffer if the first write slot content is not null.

3. The method of claim 1, further comprising:

identify when the data from the writer process is null data;

substitute the null data with an empty value object; and

write the empty value object to the first write slot.

4. The method of claim 1, further comprising:

receive a request from a second writer process to write data to the buffer;

increment the writer index to a second write slot in the buffer;

reserve the second write slot for the second writer process; and

write data from the second writer process to the second write slot.

5. The method of claim 1, wherein the buffer is an array or a circular linked list.

6. The method of claim 1, further comprising:

if the content of the read slot is an empty value object, replace the empty value object with null data; and

provide the null data to the reader process.

7. A method for resizing a buffer, comprising:

determine an original buffer is full when content of a slot that is reserved for a new writer process executing on a processor is not null;

create a new buffer;

move data from slots in the original buffer to slots in the new buffer;

set a reader index to point to last slot in new buffer;

set a writer index to point to last non-null element in new buffer;

receive a request from the writer process to write data to the buffer;

increment the writer index to a next slot in the buffer;

reserve a first write slot for the writer process; and

write data from the writer process to the first write slot.

8. The method of claim 7, wherein moving data from slots in the original buffer to slots in the new buffer compacts the data by skipping null slots in the original buffer and filling slots in the new buffer sequentially.

9. The method of claim 7, further comprising:

set slots in the original buffer to null as data is moved to slots in the new buffer; and

dispose of original buffer when all data has been moved.

10. The method of claim 7, further comprising:

block writer processes and reader processes from reserving slots in the original buffer; and

after all data has been moved to the new buffer, allow writer processes and reader processes to reserve slots in the new buffer.

11. The method of claim 7, further comprising:

set a buffer state to a resizing state; and

after all data has been moved to the new buffer, set the buffer state to a non-resizing state.

12. The method of claim 7, wherein the new buffer is larger than the original buffer by a preselected multiple or by a preselected number of slots.

13. The method of claim 7, wherein a new buffer size is selected based upon a frequency of buffer resizing.

14. A computer-readable storage device not comprising a propagated signal or wave storing computer-executable instructions that when executed by at least one processor cause the at least one processor to perform a method for writing and reading data to a buffer, the method comprising:

receiving a request from a reader process to read data from the buffer;

incrementing a reader index;

reserving a read slot for the reader process;

sending the content of the read slot to the reader process and set the slot content to null in an atomic manner;

if the read slot content is null, then determining whether the buffer has been resized;

if the buffer has been resized, incrementing the reader index;

reserving a new read slot for the reader process;

reading the content of the new read slot and set the slot content to null in an atomic manner;

receiving a request from a writer process to write data to the buffer;

incrementing a writer index to a next slot in the buffer;

reserving a first write slot for the writer process; and

writing data from the writer process to the first write slot.

15. The computer-readable storage device of claim 14, wherein the method further comprises:

identifying when the data from the writer process is null data;

substituting the null data with an empty value object;

writing the empty value object to the first write slot;

if the content of the read slot is the empty value object, replacing the empty value object with null data; and

providing the null data to the reader process.

16. The computer-readable storage device of claim 14, wherein the method further comprises:

identifying when the content of the first write slot is not null; and

resizing the buffer if the first write slot content is not null.