Dynamic rank ordered scheduling mechanism

• US 4,358,829 A
• Filed: 04/14/1980
• Issued: 11/09/1982
• Est. Priority Date: 04/14/1980
• Status: Expired due to Term

• Current Assignee: Sperry Corporation (Unisys Corporation)
• Original Assignee: Sperry Corporation (Unisys Corporation)
• Inventors: Branigin, Michael H., Knebel, Francis P., McClellan, Gerald V.
• Primary Examiner(s): Atkinson, Charles E.
• Assistant Examiner(s): Heckler, Thomas M.
• Application Number:
  US06/140,367
• Time in Patent Office: 939 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 718/103
• CPC Class Codes: G06F 13/18 based on priority control G06F13/1605 takes precedence

Abstract

A mechanism is provided which permits the insertion of elements into a list of positions determined by the rank of the elements and allows deletion of elements only from the top of the list. The arrangement provides dynamic aging of the priorities of the elements entered into the list.

Claims

1. In a dynamic rank ordered scheduling mechanism for enqueuing data elements on and dequeuing data elements from lists, the improvement comprising:

storage means for storing a queue control block and a list head table having a plurality of ranks with each rank representing a priority level and controlling an associated list comprising a plurality of data elements which are stored in said storage means;

said queue control block including a value B representing a pointer to the table rank from which a dequeue last occurred, a value N representing a count of the priority levels which have enqueued data elements, a value K representing the base address of the table, and a bit map having a binary bit position corresponding to each of said ranks;

means for applying a data element to said storage means;

means providing an indication of the priority (P) of a data element applied to said storage means;

means for summing K, N, B and P to produce an enqueue address representing a rank in said list head table;

means for applying said enqueue address to said table to enqueue a data element applied thereto; and

,

means connected to said storage means for setting the corresponding bit position in said bit map and incrementing said value N when a data element is first enqueued on a given rank of said table.

2. In a dynamic rank ordered scheduling mechanism for enqueuing elements received from a source external to said mechanism in ranks in a table, or dequeuing elements from said table, the improvement comprising:

means for storing a table of elements; and

,

means for enqueuing elements in said table at insertion points I defined by the equation I=B+N+P where B is a value representing a pointer to a table rank from which a dequeue last occurred, N is a value representing the number of ranks of the table that have at least one element enqueued therein, and P is a priority value assigned to the element being enqueued.

3. The improvement as claimed in claim 2 and further comprising:

means for dequeuing elements from said table at a deletion point D where D is the highest order rank in the table that contains an element.

4. The improvement as claimed in claim 3 wherein the means for dequeuing elements comprises:

means for storing a bit map word having a bit position corresponding to each rank of said table;

means for scanning said bit map word to produce a signal indicating the highest order bit position of said bit map word which is set;

means responsive to said scanning means for producing encoded signals representing said value D;

means responsive to said value D for addressing said table at the rank corresponding to the value D; and

,

means for storing said encoded signals for subsequent use as said value B.

5. The improvement as claimed in claim 4 and further comprising:

means for sensing when a dequeued element is the last element of its rank in the table;

storage means for storing the value N;

means responsive to said sensing means and said means storing the value N for decrementing the value N when a dequeued element is the last element of its rank in the table; and

,

means for storing said decremented value N in said storage means.

6. The improvement as claimed in claim 5 and further comprising means responsive to said sensing means and said means storing said bit map word for resetting the bit position of the bit map word corresponding to the rank of a dequeued element when said sensing means senses that the dequeued element is the last element of its rank in the table.

7. The improvement as claimed in claim 4, 5 or 6 wherein said means for scanning said bit map word comprises:

a counter having an individual output for each possible count;

means for incrementing said counter;

a masking circuit including a plurality of logical AND circuits, one for each bit in said bit map word; and

,

means for applying said bit map word and the outputs from said counter to said masking circuit whereby said masking circuit produces said signal when the count in said counter is equal to the highest order bit position which is set in said bit map word.

8. The improvement as claimed in claim 6 and further comprising:

second sensing means for sensing that an element being enqueued is the first element of its rank to be currently queued;

means responsive to said second sensing means and said means storing the value N for incrementing the value N when an enqueued element is the first element of its rank to be currently queued; and

,

means for storing said incremented value N in said storage means for storing the value N.

9. The improvement as claimed in claim 8 and further comprising means responsive to said second sensing means and said means storing said bit map word for setting the bit position of the bit map word corresponding to the rank of the element being enqueued when said second sensing means senses that the element being enqueued is the first element of its rank in the table.

10. The improvement as claimed in claim 9 wherein the means for setting and means for resetting a bit position of the bit map word comprises:

means for selectively summing N, B and P to produce a binary code value representing the bit position to be set or reset;

means for decoding the binary coded value to produce an output signal on one of a plurality of output lines, there being one line corresponding to each bit of said bit map word;

a first plurality of Exclusive OR circuits each connected to receive a bit of said bit map word;

a plurality of OR circuits each having a first input connected to receive the output from a corresponding Exclusive OR circuit of said first plurality and a second input connected to one of the output lines of the means for decoding the binary coded value;

a second plurality of Exclusive OR circuits each responsive to a corresponding one of said OR circuits;

means responsive to said first sensing means for selectively applying a control signal to each of the Exclusive OR circuits in both said first and said second plurality of Exclusive OR circuits to thereby complement the inputs thereto when said first sensing means senses that an element being dequeued is the last element of its rank in the table;

said first and said second plurality of Exclusive OR circuits passing the inputs thereto without complementing in the absence of said control signal; and

,

gating means responsive to said first and second sensing means and said second plurality of Exclusive OR circuits for applying a modified bit map word to the means for storing a bit map word.

11. The method of enqueuing and dequeuing elements in a table having a number of ranks each rank representing a priority level, said method comprising:

inserting elements in the table at an insertion point I=B+N+P; and

,

dequeuing elements from the table at a deletion point D where,

D is a value representing the highest order rank in the table that contains an element,

N is a value representing the number of ranks of the table having at least one element enqueued therein,

P is a priority value assigned to an element being enqueued, and,

B is a value representing a pointer to the table position from which the last dequeue occurred.