Dynamic multilevel task management method and apparatus

• US 6,920,632 B2
• Filed: 08/23/2002
• Issued: 07/19/2005
• Est. Priority Date: 08/23/2002
• Status: Expired due to Fees

• Current Assignee: Xyron (ACCO Brands Incorporated)
• Original Assignee: Xyron (ACCO Brands Incorporated)
• Inventors: Donovan, Brian, Dress, William B., McKaig, Ray S.
• Primary Examiner(s): Knight, Anthony
• Assistant Examiner(s): BARNES-BULLOCK, CRYSTAL JOY
• Application Number:
  US10/227,050
• Publication Number:
  US 20040039455A1
• Time in Patent Office: 1,061 Days
• Field of Search: 718/100, 718102-104, 710 40- 48, 710/1, 710/260, 710/240, 710/244, 710/264, 710/265, 709102-104
• US Class Current: 718/103
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A method for the orderly execution of multiple tasks in a data processing system and a circuit for implementing that method include a plurality of task modules which construct bids based upon the order of the task and its priority. The highest priority highest order number tasks are switched to available system execution resources. The system permits the orderly execution of round-robin task sets in an environment of dynamically changing priorities. When a round-robin task set is interrupted, the system is able to return to the round-robin task set after execution of the higher priority task at the exact point the interruption occurred.

Claims

1. In a data processing system, a method of selecting tasks for execution by one or more system resources comprising the steps of:

(a) placing a task set into circuit modules arranged in a predetermined order determined by a task ID code, each of said circuit modules comprising a bid constructor circuit for constructing a bid for each task, said bid comprising at least a priority code and said task ID code, the bid comprising an integral portion and a fractional portion, the integral portion being determined by the priority code and the fractional portion indicating whether the task has been previously executed;

(b) establishing in each of said circuit modules a single priority code for each task in the task set thereby rendering the task set as a round-robin task set;

(c) initiating the execution of the round-robin task set in the order established by the task ID code;

(d) interrupting the execution of the round-robin task set for a new task comprising a second round-robin task set having a higher priority code than the priority code established for the round-robin task set, wherein said priority codes vary dynamically over time; and

(e) after the execution of the new task, resuming the execution of the round-robin set while maintaining the order of said round-robin task set as established in step (a).

2. The method of claim 1 wherein tasks having the same priority code are executed in the order represented by the task ID code.

3. The method of claim 1 wherein said bid comprises an integral portion and a fractional portion, the integral portion being determined by said priority code and the fractional portion being determined, at least in part, by said task ID code.

4. The method of claim 1 wherein the operation of said bid constructor circuit is controlled by a multiplicity flag, said flag indicating that a plurality of tasks each have the same priority code, wherein all of said tasks having the same priority code are compared with other tasks in a single priority comparison circuit.

5. The method of claim 1 wherein the operation of said bid constructor circuit is controlled by a blocking bit flag wherein all bids from said bid constructor circuits are compared in a dual priority comparison circuit, one comparison being made for bids having an active blocking bit flag and a second comparison being made for bids having an inactive blocking bit flag, whereby a larger result of the two comparison steps is selected for execution.

6. In a data processing system, a method of selecting tasks for execution by one or more system resources comprising the steps of:

(a) establishing a task set in circuit modules, said circuit modules arranged in a predetermined order determined by a task ID code;

(b) establishing in each of said circuit modules a priority code for each task in the task set;

(c) creating a bid for each task in the task set, the bid comprising a priority code and the task ID code;

(i) determining if the task ID code of the next task to run matches or is greater than the task ID code of any task in the task set, and

(ii) determining if the priority code of the next task to run matches the priority code of any task in the task set;

(d) selecting the highest valued bid for execution by a system resource and designating said task as the next task to run;

(e) executing the next task to run, and after the execution of said task, comparing the priority code and task ID code of said task with each of the other tasks in the task set.

7. The method of claim 6 wherein the bid of step (c) includes an integral portion and a fractional portion, the integral portion being determined by the priority code and the fractional portion being determined at least in part by the outcome of steps (i) and (ii).

8. The method of claim 7 wherein the bid is a binary number and the fractional portion of said number is its least significant bit.

9. The method of claim 7 wherein the priority code is allowed to vary dynamically over time.