Circular queue for microkernel operating system

Abstract

In one embodiment, a method includes receiving, by a kernel of an operating system executing on a computing device, a request to store a message to communicate from a first process to a second process using a circular buffer. The circular buffer includes a first number of memory segments. An ownership of a first memory segment of the circular buffer is determined, based on a corresponding first ownership segment of an ownership array for the circular buffer. The ownership array includes a second number of ownership segments, where the second number is the same as the first number. Responsive to determining that the first segment is available to the first process, the message is stored in the first memory segment. After the message is stored in the first memory segment, the first ownership segment is changed to indicate the first memory segment is owned by the second process.

What is claimed is: 
     
       1. A method comprising, by a kernel of an operating system executing on a computing device:
 receiving a request to store a message to communicate from a producer process to a consumer process using a circular buffer, wherein the circular buffer comprises memory segments; 
 determining an ownership of a first memory segment of the circular buffer, based on a corresponding first ownership segment of an ownership array for the circular buffer, wherein the ownership array comprises a corresponding ownership segment for each memory segment of the circular buffer; and 
 determining, based on the determined ownership of the first memory segment, that the first segment is available to the producer process; 
 determining that criteria are satisfied after a comparison of a current iteration around the circular buffer taken by the producer process to a number of messages previously stored in the first memory segment, wherein the satisfied criteria indicate that the messages previously stored in the first memory segment have been consumed; 
 responsive to determining that the first memory segment is available to the producer process and that the criteria are satisfied:
 storing the message in the first memory segment; and 
 
 after storing the message in the first memory segment, changing a value stored in the first ownership segment to indicate the first memory segment is owned by the consumer process to allow the consumer process to consume the stored message. 
 
     
     
       2. The method of  claim 1 , wherein each of the memory segments of the circular buffer is associated with a generation number; and
 the method further comprises, after storing the message in the first memory segment, incrementing the generation number associated with the first memory segment. 
 
     
     
       3. The method of  claim 1 , further comprising:
 consuming the message stored in the first memory segment by the consumer process; and 
 after consuming the message by the consumer process, changing the value stored in the first ownership segment to indicate the first memory segment is owned by the producer process to enable the producer process to write into the first memory segment. 
 
     
     
       4. The method of  claim 1 , further comprising:
 receiving a second request to store a second message in the first memory segment of the circular buffer; 
 responsive to the second request, determining the ownership of the first memory segment; and 
 responsive to determining the first memory segment is owned by the consumer process, denying storage of the second message in the first memory segment. 
 
     
     
       5. The method of  claim 1 , wherein the circular buffer is associated with a reservation counter; and
 the method further comprises:
 receiving a third request to reserve a third message for storing in the circular buffer; 
 determining whether a plurality of reservation criteria are satisfied; and 
 responsive to determining the reservation criteria are satisfied, incrementing the reservation counter. 
 
 
     
     
       6. The method of  claim 1 , wherein the memory segments are equally sized. 
     
     
       7. One or more computer-readable non-transitory storage media embodying software that is operable when executed to cause a kernel of an operating system executing on a computing device to:
 receive a request to store a message to communicate from a producer process to a consumer process using a circular buffer, wherein the circular buffer comprises memory segments; 
 determine an ownership of a first memory segment of the circular buffer, based on a corresponding first ownership segment of an ownership array for the circular buffer, wherein the ownership array comprises a corresponding ownership segment for each memory segment of the circular buffer; 
 determine, based on the determined ownership of the first memory segment, that the first segment is available to the producer process; 
 determine that criteria are satisfied after a comparison of a current iteration around the circular buffer taken by the producer process to a number of messages previously stored in the first memory segment, wherein the satisfied criteria indicate that the messages previously stored in the first memory segment have been consumed; and 
 responsive to determining that the first memory segment is available to the producer process and that the criteria are satisfied:
 store the message in the first memory segment; and 
 after storing the message in the first memory segment, change a value stored in the first ownership segment to indicate the first memory segment is owned by the consumer process to allow the consumer process to consume the stored message. 
 
 
     
     
       8. The media of  claim 7 , wherein each of the memory segments of the circular buffer is associated with a generation number; and
 wherein the software is further operable when executed to cause the kernel to, after storing the message in the first memory segment, increment the generation number associated with the first memory segment. 
 
     
     
       9. The media of  claim 7 , wherein the software is further operable when executed to cause the kernel to:
 consume the message stored in the first memory segment by the consumer process; and 
 after consuming the message by the consumer process, change the value stored in the first ownership segment to indicate the first memory segment is owned by the producer process to enable the producer process to write into the first memory segment. 
 
     
     
       10. The media of  claim 7 , wherein the software is further operable when executed to cause the kernel to:
 receive a second request to store a second message in the first memory segment of the circular buffer; 
 responsive to the second request, determine the ownership of the first memory segment; and 
 responsive to determining the first memory segment is owned by the consumer process, deny storage of the second message in the first memory segment. 
 
     
     
       11. The media of  claim 7 , wherein the circular buffer is associated with a reservation counter; and
 wherein the software is further operable when executed to cause the kernel to:
 receive a third request to reserve a third message for storing in the circular buffer; 
 determine whether a plurality of reservation criteria are satisfied; and 
 responsive to determining the reservation criteria are satisfied, increment the reservation counter. 
 
 
     
     
       12. The media of  claim 7 , wherein the memory segments are equally sized. 
     
     
       13. A system comprising:
 one or more processors; and 
 one or more computer-readable non-transitory storage media coupled to one or more of the processors and comprising instructions operable when executed by one or more of the processors to cause a kernel of an operating system executing on the system to:
 receive a request to store a message to communicate from a producer process to a consumer process using a circular buffer, wherein the circular buffer comprises memory segments; 
 determine an ownership of a first memory segment of the circular buffer, based on a corresponding first ownership segment of an ownership array for the circular buffer, wherein the ownership array comprises a corresponding ownership segment for each memory segment of the circular buffer; 
 determine, based on the determined ownership of the first memory segment, that the first segment is available to the producer process; 
 determine that criteria are satisfied after a comparison of a current iteration around the circular buffer taken by the producer process to a number of messages previously stored in the first memory segment, wherein the satisfied criteria indicate that the messages previously stored in the first memory segment have been consumed; and 
 responsive to determining that the first memory segment is available to the producer process and that the criteria are satisfied:
 store the message in the first memory segment; and 
 after storing the message in the first memory segment, change a value stored in the first ownership segment to indicate the first memory segment is owned by the consumer process to allow the consumer process to consume the stored message. 
 
 
 
     
     
       14. The system of  claim 13 , wherein each of the memory segments of the circular buffer is associated with a generation number; and
 wherein the processors are further operable when executing the instructions to cause the kernel of the operating system executing on the system to, after storing the message in the first memory segment, increment the generation number associated with the first memory segment. 
 
     
     
       15. The system of  claim 13 , wherein the processors are further operable when executing the instructions to cause the kernel of the operating system executing on the system to:
 consume the message stored in the first memory segment by the consumer process; and 
 after consuming the message by the consumer process, change the value stored in the first ownership segment to indicate the first memory segment is owned by the producer process to enable the producer process to write into the first memory segment. 
 
     
     
       16. The system of  claim 13 , wherein the processors are further operable when executing the instructions to cause the kernel of the operating system executing on the system to:
 receive a second request to store a second message in the first memory segment of the circular buffer; 
 responsive to the second request, determine the ownership of the first memory segment; and 
 responsive to determining the first memory segment is owned by the consumer process, deny storage of the second message in the first memory segment. 
 
     
     
       17. The system of  claim 13 , wherein the circular buffer is associated with a reservation counter; and
 wherein the processors are further operable when executing the instructions to cause the kernel of the operating system executing on the system to:
 receive a third request to reserve a third message for storing in the circular buffer; 
 determine whether a plurality of reservation criteria are satisfied and 
 responsive to determining the reservation criteria are satisfied, increment the reservation counter. 
 
 
     
     
       18. The system of  claim 13 , wherein the memory segments are equally sized.