# US 2014/0156959 A1 · Concurrent array-based queue > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0156959 A1 - Document ID: US20140156959A1 - Status: Published application - Kind: A1 - Application number: 13/690,028 - Filed: 2012-11-30 - Published: 2014-06-05 - Earliest claimed: 2012-11-30 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Philip Heidelberger; Burkhard Steinmacher-Burow - Web page: https://patentgrep.com/patent/US20140156959A1 ## CPC - G06F 5/065: {Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's} - G06F 12/145: {the protection being virtual, e.g. for virtual blocks or segments before a translation mechanism} - G06F 2205/066: User-programmable number or size of buffers, i.e. number of separate buffers or their size can be allocated freely - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract According to one embodiment, a method for implementing an array-based queue in memory of a memory system that includes a controller includes configuring, in the memory, metadata of the array-based queue. The configuring comprises defining, in metadata, an array start location in the memory for the array-based queue, defining, in the metadata, an array size for the array-based queue, defining, in the metadata, a queue top for the array-based queue and defining, in the metadata, a queue bottom for the array-based queue. The method also includes the controller serving a request for an operation on the queue, the request providing the location in the memory of the metadata of the queue. ## Claims ### Claim 1 A method for implementing an array-based queue in memory of a memory system that includes a controller, the method comprising: configuring, in the memory, metadata of the array-based queue, the configuring comprising: defining, in the metadata, an array start location in the memory for the array-based queue; defining, in the metadata, an array size for the array-based queue; defining, in the metadata, a queue top for the array-based queue; and defining, in the metadata, a queue bottom for the array-based queue; and serving, by the controller, a request for an operation on the queue, the request providing the location, in the memory, of the metadata of the queue. ### Claim 2 (depends on 1) The method of claim 1, wherein serving the request further comprises: receiving the request, the request comprising a pop top operation request or a pop bottom operation request; reading the metadata to determine a location in memory for a selected element in the array-based queue based on the request; updating the metadata based on the request, the updating comprising advancing the queue top or the queue bottom to remove the selected element from the array-based queue; reading the selected element based on the request; and replying to the request with a result of the read. ### Claim 3 (depends on 2) The method of claim 2, wherein the configuring the array-based queue further comprises defining, in the metadata, a failed pop parameter to be returned by the controller when receiving a pop request for the array-based queue when the array-based queue is empty. ### Claim 4 (depends on 2) The method of claim 2, wherein the configuring further comprises defining, in the metadata, a position and size of an instance field in each element of the array-based queue, the request comprises a pop instance request, and wherein the serving further comprises decrementing an instance field of the selected element and pushing the selected element with an updated instance field back onto the array-based queue based on the result being greater than zero. ### Claim 5 (depends on 1) The method of claim 1, wherein serving the request further comprises: receiving the request, the request comprising a push top or push bottom operation request on the queue, the request providing a value for a selected element in the array-based queue; reading the metadata to determine a location in memory for the selected element in the array-based queue based on the request; updating the metadata based on the request, the updating comprising advancing the queue top or the queue bottom to add the selected element to the queue; and writing the value provided by the request to the selected element. ### Claim 6 (depends on 1) The method of claim 1, wherein the request corresponds to a single load instruction or a single store instruction, wherein the single load or single store instruction comprises an atomic memory operation received and served by the controller and the single load or single store instruction supports concurrent requests. ### Claim 7 (depends on 1) The method of claim 1, the configuring further comprising defining, in the metadata, a token parameter that represents a number of free elements available for future pushes to the queue and wherein updating the metadata based on the request comprises updating the token parameter. ### Claim 8 (depends on 1) The method of claim 1, further comprising defining a kernel-protected field in the controller that specifies a page size and an alignment of a memory page, wherein the controller successfully serves the request only if the metadata and the array-based queue are located at a same page. ### Claim 9 (depends on 8) The method of claim 8, wherein the kernel-protected field specifying the page size and alignment is a kernel-protected operand in the request and the kernel-protected operand is provided by processor memory address translation hardware. ### Claim 10 (depends on 1) The method of claim 1, wherein the configuring further comprises defining, in the metadata, a configuration lock parameter to indicate if the array-based queue is being configured, wherein a request can acquire a configuration lock using the configuration lock parameter and acquiring the configuration lock prevents the controller from successfully serving subsequent requests to the queue. ### Claim 11 A system for implementing a queue, the system comprising: a memory and a controller, the system configured to perform a method comprising: configuring, in the memory, metadata of an array-based queue, the array-based queue located in the memory, wherein configuring comprises: defining, in the metadata, an array start location in the memory for the array-based queue; defining, in the metadata, an array size for the array-based queue; defining, in the metadata, a queue top for the array-based queue; and defining, in the metadata, a queue bottom for the array-based queue; and serving, by the controller, a request for an operation on the queue, the request providing the location, in the memory, of the metadata of the queue. ### Claim 12 (depends on 11) The system of claim 11, wherein serving the request further comprises: receiving the request, the request comprising a pop top operation request or a pop bottom operation request; reading the metadata to determine a location in memory for a selected element in the array-based queue based on the request; updating the metadata based on the request, the updating comprising advancing the queue top or the queue bottom to remove the selected element from the array-based queue; reading the selected element based on the request; and replying to the request with a result of the read. ### Claim 13 (depends on 11) The system of claim 11, wherein serving the request further comprises: receiving the request, the request comprising a push top or push bottom operation request on the queue, the request providing a value for a selected element in the array-based queue; reading the metadata to determine a location in memory for the selected element in the array-based queue based on the request; updating the metadata based on the request, the updating comprising advancing the queue top or the queue bottom to add the selected element to the queue; and writing the value provided by the request to the selected element. ### Claim 14 (depends on 11) The system of claim 11, wherein the request corresponds to a single load instruction or a single store instruction, wherein the single load or single store instruction comprises an atomic memory operation received and served by the controller and the single load or single store instruction supports concurrent requests. ### Claim 15 (depends on 11) The system of claim 11, further comprising defining a kernel-protected field in the controller that specifies a page size and an alignment of a memory page, wherein the controller successfully serves the request only if the metadata and the array-based queue are located at a same page. ### Claim 16 (depends on 15) The system of claim 15, wherein the kernel-protected field specifying the page size and alignment is a kernel-protected operand in the request and the kernel-protected operand is provided by processor memory address translation hardware. ### Claim 17 (depends on 11) The system of claim 11, wherein the configuring further comprises defining, in the metadata, a configuration lock parameter to indicate if the array-based queue is being configured, wherein a request can acquire a configuration lock using the configuration lock parameter and acquiring the configuration lock prevents the controller from successfully serving subsequent requests to the queue. ### Claim 18 A computer program product for implementing an array-based queue in memory of a memory system, the memory system including a controller, the computer program product comprising: a tangible storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising: configuring, in the memory, metadata of the array-based queue, wherein configuring comprises: defining, in the metadata, an array start location in the memory for the array-based queue; defining, in the metadata, an array size for the array-based queue; defining, in the metadata, a queue top for the array-based queue; and defining, in the metadata, a queue bottom for the array-based queue; and serving, by a controller, a request for an operation on the queue, the request providing the location, in the memory, of the metadata of the queue. ### Claim 19 (depends on 18) The computer program product of claim 18, wherein serving the request further comprises: receiving the request, the request comprising a pop top operation request or a pop bottom operation request; reading the metadata to determine a location in memory for a selected element in the array-based queue based on the request; updating the metadata based on the request, the updating comprising advancing the queue top or the queue bottom to remove the selected element from the array-based queue; reading the selected element based on the request; and replying to the request with a result of the read. ### Claim 20 (depends on 19) The computer program product of claim 19, wherein the configuring the array-based queue further comprises defining, in the metadata, a failed pop parameter to be returned by the controller when receiving a pop request for the array-based queue when the array-based queue is empty. ### Claim 21 (depends on 19) The computer program product of claim 19, wherein the configuring further comprises defining, in the metadata, a position and size of an instance field in each element of the array-based queue, the request comprises a pop instance request, and wherein the serving further comprises decrementing an instance field of the selected element and pushing the selected element with an updated instance field back onto the array-based queue based on the result being greater than zero. ### Claim 22 (depends on 18) The computer program product of claim 18, wherein serving the request further comprises: receiving the request, the request comprising a push top or push bottom operation request on the queue, the request providing a value for a selected element in the array-based queue; reading the metadata to determine a location in memory for the selected element in the array-based queue based on the request; updating the metadata based on the request, the updating comprising advancing the queue top or the queue bottom to add the selected element to the queue; and writing the value provided by the request to the selected element. ### Claim 23 (depends on 18) The computer program product of claim 18, the configuring further comprising defining, in the metadata, a token parameter that represents a number of free elements available for future pushes to the queue and wherein updating the metadata based on the request comprises updating the token parameter.