Method and system for scheduling queued messages based on queue delay and queue priority

• US 6,182,120 B1
• Filed: 09/11/1998
• Issued: 01/30/2001
• Est. Priority Date: 09/30/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Beaulieu, Cesca, Dispensa, Jean-Claude
• Primary Examiner(s): Rinehart, Mark H.
• Assistant Examiner(s): Vaughn, Jr, William C.
• Application Number:
  US09/152,144
• Time in Patent Office: 872 Days
• Field of Search: 709/103, 709/200, 709/207, 709/107, 709/240, 709/243, 709/244, 709/232, 709/229, 710/60, 710/54, 710/29, 710/40, 710/263, 710/244
• US Class Current: 709/207
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Queue processing mechanism in which queued messages are processed based on combination of queue delay and queue priority. A scheduler dequeues the highest priority non-empty Microcode Input Queue (MIQ) to serve the queued messages. If there is no critical queue, meaning that the maximum aging of one or more queues has not been reached, the critical state is not entered. A static weight for each queue is then tested to determine if there is still a message to be processed from the corresponding MIQ. Messages are dequeued from the same MIQ until the static weight is reached. The next MIQ is then served etc., until the queue of the lowest priority level is served. If the critical phase is entered, the status of the normal state is stored for later return and the MIQs in critical state are dequeued according to their critical weights. If other MIQs appear to be critical, they are served in the order of their critical priorities (or weights). The critical queues are dequeued sequentially according to their critical weight. If no critical MIQ is left, the scheduler exits from this critical state and loops back to the normal state that it previously exited. Normal state processing continues until the next critical state occurs.

Claims

1. A method for controlling data transfer between a host data processing system and a communication network by processing queued messages in a plurality of queues saved in a data store, said method comprising the steps of:

(a) including in the data store a first service table (ACT_ST) containing a plurality of bits wherein each bit is associated with a corresponding queue so as to determine which queue has to be served, said first service table being stored before entering a critical state and updated according to the critical queues and being the result of an AND operation between two other service tables contained in the data store, specifically;

a second service table (HDW_ST) containing a plurality of bits, each bit corresponding to the status of a queue so as to determine if a new message has been enqueued in said queue; and

a third service table (WGH_ST) containing a plurality of bits, each bit associated with a corresponding queue so as to determine if said queue is to be served according to the associated predetermined number of allowed dequeue messages;

(b) dequeueing, in a normal state, successively queued messages from a plurality of queues according to their associated queue priorities;

(c) dequeueing in the normal state, in the order of queue priorities, queued messages from non-empty queues until their associated predetermined number of allowed dequeue messages are reached;

(d) interrupting the normal state to enter a critical state, by dequeueing successively queued messages from a plurality of critical queues according to their associated queue priorities, said critical queues having their corresponding aging times exceed predetermined values;

(e) dequeueing in the critical state, in the order of critical queue priorities, queued messages from non-empty critical queues until their associated predetermined critical number of allowed dequeue messages are reached; and

(f) returning to the previous normal state with its set of parameters to continue until the next critical state occurs or until the end of scheduling cycle is reached.

2. The method of claim 1 wherein step (a) comprises the steps of:

reading said service tables HDW_ST, WGH_ST and ACT_ST;

selecting a left most ‘

1’

in said first service table to dequeue messages from the corresponding queue until the associated predetermined number of allowed dequeue messages is reached;

computing the elapsed time since the previous processing of said selected queue in order to determine if its corresponding aging time exceeds a predetermined value; and

dequeueing a next non-empty queue in the normal state according to its corresponding status bit in said first service table.

3. The method of claim 1 wherein step (b) comprises the steps of:

saving a current normal state set of parameters;

setting in said third service table (WGH_ST) bits that correspond to queues in the critical state;

computing bits in a first critical service table (ACT_ST) corresponding to said critical state;

selecting a left most ‘

1’

in said first service table to dequeue message from the corresponding critical queue until the associated predetermined number of allowed dequeue messages is reached;

computing the elapsed time since the previous processing of said selected queue in order to determine if its corresponding aging time exceeds a predetermined value; and

dequeueing a next non-empty critical queue according to its corresponding status bit in said first service table (ACT_ST).

4. A system for controlling data transfer between a host data processing system and a communication network by processing queued messages in a plurality of queues saved in a data store, said system comprising:

a first service table (ACT_ST) saved in the data store and containing a plurality of bits wherein each bit is associated with a queue so as to determine which queue has to be served, said service table being stored before entering a critical state and updated according to the critical queues;

said first service table (ACT_ST) being the result of an AND operation between two other service tables contained in the data store, specifically;

a second service table (HDW_ST) containing a plurality of bits, each bit corresponding to the status of a queue so as to determine if a new message has been enqueued in said queue; and

a third service table (WGH_ST) containing a plurality of bits, each bit associated with a corresponding queue so as to determine if said queue is to be served according to the associated predetermined number of allowed dequeue messages;

a plurality of registers that are associated with each queue including;

a first register for a static weight corresponding to a number of messages which may be pulled out from said queue, said register being implemented in connection with a second register for a current weight corresponding to a number of messages allowed to be dequeued from said queue, for processing said queued messages in a normal state;

a third register for a maximum delay corresponding to a maximum waiting time of a non-empty queue to be dequeued, said register being implemented in connection with a fourth register for a dormant time corresponding to an elapsed time since said queue was last served, for processing queued messages in a critical state when the contents of said fourth register exceeds the contents of said third register; and

a fifth register processing queued message of a critical queue for critical weight corresponding to a number of messages allowed to be dequeued from said critical queue, in a critical state.