Low-contention update buffer queuing for large systems

摘要

A method for queuing thread update buffers to enhance garbage collection. The method includes providing a global update buffer queue and a global array with slots for storing pointers to filled update buffers. The method includes with an application thread writing to the update buffer and, when filled, attempting to write the pointer for the update buffer to the global array. The array slot may be selected randomly or by use of a hash function. When the writing fails due to a non-null slot, the method includes operating the application thread to add the filled update buffer to the global update buffer queue. The method includes, with a garbage collector thread, inspecting the global array for non-null entries and, upon locating a pointer, claiming the filled update buffer. The method includes using the garbage collector thread to claim and process buffers added to the global update buffer queue.

主权项

1. A method of queuing buffers for garbage collection in a computer system, comprising:
in a memory of the computer system, providing a global update buffer queue and a global array with slots for storing pointers to update buffers filled by application threads; running an application thread in the memory of the computer system; providing, for the application thread, an update buffer in the memory and a data structure including a current update buffer slot with a pointer to the update buffer; with the application thread, writing to the update buffer; after the writing fills the update buffer, attempting with the application thread to write the pointer for the filled update buffer to one of the slots of the global array for storing pointers; when the attempting fails, operating the application thread to add the filled update buffer to the global update buffer queue; with a garbage collector thread, inspecting the global array for non-null entries in the slots and, upon locating the pointer, claiming the filled update buffer for processing; and with the garbage collector thread when the slots all have null entries, obtaining the filled update buffer from the global update buffer queue; wherein the claiming is performed with an atomic operation; and wherein the claiming further comprises changing the one of the slots of the global array for storing pointers to null.