Available frame queue processing

Patent metadata

Field	Value
Publication number	US-9898198-B2
Application number	US-201514738227-A
Country	US
Kind code	B2
Filing date	Jun 12, 2015
Priority date	Jun 12, 2015
Publication date	Feb 20, 2018
Grant date	Feb 20, 2018

Abstract

In one embodiment, a computer-implemented method includes building an available frame header queue (AFHQ). The AFHQ includes one or more headers, each header including one or more frame references being no more than a maximum count of frame references. Each of the one or more frame references of each of the one or more headers refers to an available frame. A frame request is received for one or more requested frames. One or more frame references are extracted, by a computer processor, from the AFHQ in response to the frame request. The extracting includes extracting from the AFHQ one or more requested headers including the one or more frame references referring to at least a portion of the one or more requested frames.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
building an available frame header queue (AFHQ) comprising a first-level queue of a plurality of headers, each header comprising a second-level queue of a plurality of frame references being no more than a maximum count of frame references, wherein each of the one or more frame references of each of the plurality of headers refers to an available frame;
receiving a frame request for one or more requested frames, wherein the frame request specifies a requested quantity for the one or more requested frames;
extracting, by a computer processor, one or more frame references from the first-level queue of the plurality of headers of the AFHQ in response to the frame request, wherein the extracting comprises extracting from the AFHQ one or more requested headers comprising the one or more frame references referring to at least a portion of the one or more requested frames;
wherein extracting from the AFHQ the one or more requested headers comprises:
calculating a header quantity by taking the floor of dividing the requested quantity by the maximum count; and
counting for extraction a quantity of headers equal to the header quantity;

calculating a remainder quantity by taking the remainder of dividing the requested quantity by the maximum count;
determining that the reminder quantity is greater than a size of a last header in the first-level queue of the plurality of headers of the AFHQ;
recalculating the remainder quantity as the remainder quantity less the size of the last header in the first-level queue of the plurality of headers of the AFHQ;
identifying for extraction, in a second-to-last header in the first-level queue of the plurality of headers of the AFHQ, one or more requested frame references having a quantity equal to the recalculated remainder quantity; and
returning in response to the frame request the one or more requested frame references, the one or more requested headers, and the last header in the first-level queue of the plurality of headers of the AFHQ.

2. The method of claim 1 , further comprising:
calculating a remainder quantity by taking the remainder of dividing the requested quantity by the maximum count;
identifying for extraction, in a last header in the first-level queue of the plurality of headers of the AFHQ, one or more requested frame references having a quantity equal to the remainder quantity; and
returning in response to the frame request the one or more requested frame references and the one or more requested headers.

3. The method of claim 2 , wherein each header in the first-level queue of the plurality of headers, except the last header, includes a count of frame references equal to the maximum count.

4. The method of claim 2 , wherein identifying for extraction, in the last header in the first-level queue of the plurality of headers of the AFHQ, the one or more requested frame references comprises:
determining a minimum of the remainder quantity and a size of the last header less the remainder quantity; and
counting for extraction, in the last header in the first-level queue of the plurality of headers of the AFHQ, the one or more requested frame references having a quantity equal to the minimum.

5. The method of claim 1 , wherein the maximum count is modifiable by a user.

6. The method of claim 1 , wherein the frame request specifies a requested quantity for the one or more requested frames, and wherein extracting from the AFHQ the one or more requested headers comprises:
calculating a header quantity by taking the floor of dividing the requested quantity by the maximum count; and
counting for extraction a quantity of headers equal to the header quantity.

7. A system comprising:
a memory; and
one or more computer processors, communicatively coupled to the memory, the one or more computer processors to:
build an available frame header queue (AFHQ) comprising a first-level queue of a plurality of headers, each header comprising a second-level queue of a plurality of frame references being no more than a maximum count of frame references, wherein each of the one or more frame references of each of the plurality of headers refers to an available frame;
receive a frame request for one or more requested frames, wherein the frame request specifies a requested quantity for the one or more requested frames;
extract one or more frame references from the first-level queue of the plurality of headers of the AFHQ in response to the frame request, wherein the extracting comprises extracting from the AFHQ one or more requested headers comprising the one or more frame references referring to at least a portion of the one or more requested frames;
wherein, to extract from the AFHQ the one or more requested headers, the one or more computer processors are further to:
calculate a header quantity by taking the floor of dividing the requested quantity by the maximum count; and
count for extraction a quantity of headers equal to the header quantity;

calculate a remainder quantity by taking the remainder of dividing the requested quantity by the maximum count;
determine that the reminder quantity is greater than a size of a last header in the first-level queue of the plurality of headers of the AFHQ;
recalculate the remainder quantity as the remainder quantity less the size of the last header in the first-level queue of the plurality of headers of the AFHQ;
identify for extraction, in a second-to-last header in the first-level queue of the plurality of headers of the AFHQ, one or more requested frame references having a quantity equal to the recalculated remainder quantity; and
return in response to the frame request the one or more requested frame references, the one or more requested headers, and the last header in the first-level queue of the plurality of headers of the AFHQ.

8. The system of claim 7 , wherein the one or more computer processors are further configured to:
calculate a remainder quantity by taking the remainder of dividing the requested quantity by the maximum count;
identify for extraction, in a last header in the first-level queue of the plurality of headers of the AFHQ, one or more requested frame references having a quantity equal to the remainder quantity; and
return in response to the frame request the one or more requested frame references and the one or more requested headers.

9. The system of claim 8 , wherein each header in the first-level queue of the plurality of headers, except the last header, includes a count of frame references equal to the maximum count.

10. The system of claim 8 , wherein, to identify for extraction in the last header in the first-level queue of the plurality of headers of the AFHQ the one or more requested frame references, the one or more computer processors are further configured to:
determine a minimum of the remainder quantity and a size of the last header less the remainder quantity; and
count for extraction, in the last header in the first-level queue of the plurality of headers of the AFHQ, the one or more requested frame references having a quantity equal to the minimum.

11. The system of claim 7 , wherein the maximum count is modifiable by a user.

12. The system of claim 7 , wherein the frame request specifies a requested quantity for the one or more requested frames, and wherein, to extract from the AFHQ the one or more requested headers, the one or more computer processors are further configured to:
calculate a header quantity by taking the floor of dividing the requested quantity by the maximum count; and
count for extraction a quantity of headers equal to the header quantity.

Assignees

• IBM

Inventors

• Hom David
• Morgenstern Harris M
• Partlow Steven M
• Tuttle Scott B
• Tzortzatos Elpida

Classifications

• G06F3/0683

  Plurality of storage devices · CPC title

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title

• G06F3/061 Primary

  Improving I/O performance · CPC title