Method and apparatus for serving a request queue

• US 20030177164A1
• Filed: 03/15/2002
• Published: 09/18/2003
• Est. Priority Date: 03/15/2002
• Status: Active Grant

• Current Assignee: Toshiba Tec Corporation (Toshiba Corporation)
• Original Assignee: Toshiba Tec Corporation (Toshiba Corporation)
• Inventors: Savov, Andrey I., Garg, Man M.
• Granted Patent: US 6,983,462 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/548 Queue
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A system and method is provided for implementing a thread safe request queue. The request queue is preferably implemented using a circular array and atomic operations are preferably used for non-blocking functionality. In a preferred embodiment of the present invention, the request queue is capable of simultaneous thread release so that threads dequeue only when they are ready to be processed.

Claims

1. A method for serving a request queue in a system comprising a plurality of channels, the method comprising the steps of:

a) acquiring a blocking semaphore to determine the number of channels to acquire;

b) decrementing a blocking semaphore count;

c) acquiring at least one channel from which an incoming request is received;

d) receiving a request;

e) enqueueing the received request;

f) incrementing a dequeueing semaphore count;

g) acquiring the dequeueing semaphore to determine the number of requests to dequeue;

h) decrementing the dequeuing semaphore count;

i) dequeueing an enqueued request;

j) processing the dequeued request; and

k) incrementing a blocking semaphore count.

2. The method of claim 1, wherein the request queue is a circular array.

3. The method of claim 1, wherein enqueueing a received request of step e) comprises the steps of:

a) determining if the queue is full; and

b) increasing the size of the queue upon a positive determination in step a); and

c) storing the request in an empty element of the queue.

4. The method of claim 3, wherein determining if the queue is full of step a) comprises the step of performing an atomic add operation on a first element index and returning a second element index.

5. The method of claim 3, wherein increasing the size of the queue of step b) comprises the steps of:

a) acquiring the blocking semaphore and the dequeueing semaphore; and

b) suspending all enqueueing and dequeueing operations.

6. The method of claim 1, wherein dequeueing a received request of step i) comprises the steps of:

a) determining if the queue is empty; and

b) returning an array element for processing upon a negative determination in step a).

7. The method of claim 6, wherein determining if the queue is empty of step a) comprises the step of performing an atomic compare exhange operation on first and second element indices and returning a third element index.

8. A circular queue for serving requests in a system having a maximum integer number that can be stored in a machine word, the circular queue comprising:

a) an integral number of array elements, S, defined such that the maximum possible integer number stored in a machine word, MAX_INT, is divisible by S as shown in the following equation;

MAX_—

INT=0(mod S); and

b) each array element having an index that is a multiple of quotient, q, wherein q is defined by the following equation;

q=(MAX_—

INT+1)/S.

9. The circular queue of claim 8 wherein the queue is a print request queue.

10. The circular queue of claim 8 wherein MAX_INT is 2³², or 4,294,967,296.

11. A method for choosing and serving a circular array request queue comprising the steps of:

a) selecting an integral number of array elements, S1, such that the maximum possible integer number stored in a machine word, MAX_INT, is divisible by S1 as shown in the following equation;

MAX_—

INT=0(mod S1);

b) indexing each array element such that the element index is a multiple of quotient, q, wherein q is defined by the following equation;

q1=(MAX_—

INT+1)/S1;

c) acquiring a blocking semaphore to determine the number of channels to acquire;

d) decrementing a blocking semaphore count;

e) acquiring at least one channel from which an incoming request is received;

f) receiving a request;

g) enqueueing the received request;

h) incrementing a dequeueing semaphore count;

i) acquiring the dequeueing semaphore to determine the number of requests to dequeue;

j) decrementing the dequeuing semaphore count;

k) dequeueing an enqueued request;

l) processing the dequeued request; and

m) incrementing a blocking semaphore count.

12. The method of claim 11, wherein enqueueing a received request of step g) comprises the steps of:

a) determining if the queue is full; and

b) increasing the size of the queue upon a positive determination in step a); and

c) storing the request in an empty element of the queue.

13. The method of claim 12, wherein increasing the size of the queue of step b) comprises the steps of:

a) acquiring the blocking semaphore and the dequeueing semaphore; and

b) suspending all enqueueing and dequeueing operations c) selecting an integral number of array elements, S2, such that S2 is greater than S1 and such that the maximum possible integer number stored in a machine word, MAX_INT, is divisible by S2 as shown in the following equation;

MAX_—

INT=0(mod S2); and

d) indexing each array element such that the element index is a multiple of quotient, q, wherein q is defined by the following equation;

q2=(MAX_—

INT+1)/S2.

14. The method of claim 13, wherein S2 is twice S1.