Data processing system and scheduling method

• US 6,349,321 B1
• Filed: 04/29/1998
• Issued: 02/19/2002
• Est. Priority Date: 04/30/1997
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Katayama, Isao
• Primary Examiner(s): Courtenay, III, St. John
• Assistant Examiner(s): Nguyen, Van Hoa
• Application Number:
  US09/067,900
• Time in Patent Office: 1,392 Days
• Field of Search: 709/100-108, 700/95
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A central processing unit schedules the start time of a following special process based on the progress status of a preceding special process being executed in an auxiliary processing unit and the processing time and the end time of the following special process.

Claims

1. A data processing system comprising:

a central processing unit; and

an auxiliary processing unit which runs in parallel with said central processing unit and which executes a special process according to a schedule made by said central processing unit,

wherein said auxiliary processing unit comprises;

a progress status indicating unit for indicating a progress status of the special process being executed therein; and

an operation status indicating unit for indicating an operation status thereof, and

wherein said central processing unit comprises;

a database which stores a predetermined execution processing time of each special process; and

a scheduling unit, responsive to a new process request received when said operation status indicating unit indicates that a preceding special process is being executed in said auxiliary processing unit and the new special process is higher in priority than the preceding special process, for selecting any one of ending the preceding special process, interrupting the preceding special process and saving a processing status, and interrupting the preceding special process and discarding the processing status, based on first to fourth times, thereby to schedule a time at which the new special process is to start, the first time being time from the moment the new process request is received to the moment the new special process must be ended, the second time being the processing time of the new special process, the processing time being stored in said database, the third time being time required for the preceding special process to end and obtained by referencing the progress status indicating unit of said auxiliary processing unit, and the fourth time being time required to interrupt the preceding special process being executed in said auxiliary processing unit and to save or discard the processing status thereof.

3. A data processing system according to claim 1, wherein said progress status indicating unit is initialized to 0 when the special process is started and comprises a counter which is incremented by the number of instructions executed as the special process progresses.

5. A data processing system according to claim 1, wherein said progress status indicating unit is set to the time required to execute the special process when the auxiliary processing unit starts the special process and comprises a counter which is decremented by the number of instructions executed as the special process progresses.

7. A data processing system according to claim 5, wherein the value of said counter is reset according to the content of processing at any time during the special processing.

2. A data processing system comprising:

a central processing unit; and

an auxiliary processing unit which runs in parallel with said central processing unit and which executes a special process according to a schedule made by said central processing unit,

wherein said auxiliary processing unit comprises;

a progress status indicating unit for indicating a progress status of the special process being executed therein; and

an operation status indicating unit for indicating an operation status thereof, and

wherein said central processing unit comprises;

a database which stores a predetermined execution processing time of each special process; and

a scheduling unit, responsive to a request received when said operation status indicating unit indicates that a preceding special process is being executed in said auxiliary processing unit and the new special process is higher in priority than the preceding special process, for calculating a limit time, Ta, from the moment the new process request is received to the moment the new special process must be ended, retrieving the processing time, Tb, of the new special process from said database, calculating a latest start time, Tc, before which the new special process must be started to complete within the limit time by subtracting the processing time Tb from the limit time Ta, and calculating a time, Td, when the preceding special process is to end by referencing the progress status indicating unit of said auxiliary processing unit,

wherein the new special process is scheduled to start after the preceding special process is ended if Tc≧

Td,

wherein the preceding special process is interrupted, the processing status is saved, and then the new special process is scheduled to start if Tc<

Td and Tc≧

Te, and

wherein the preceding special process is interrupted, the processing status is discarded, and then the new special process is scheduled to start if Tc<

Td, Tc<

Te, and Tc≧

Tf,

Te being a time at which the processing status of the interrupted preceding special process in said auxiliary processing unit is saved, Tf being a time at which the processing status of the interrupted preceding special process in said auxiliary processing unit is discarded.

4. A data processing system according to claim 2, wherein said progress status indicating unit is initialized to 0 when the special process is started and comprises a counter which is incremented by the number of instructions executed as the special process progresses.

6. A data processing system according to claim 2, wherein said progress status indicating unit is set to the time required to execute the special process when the auxiliary processing unit starts the special process and comprises a counter which is decremented by the number of instructions executed as the special process progresses.

8. A data processing system according to claim 6, wherein the value of said counter is reset according to the content of processing at any time during the special processing.

9. A scheduling method for allowing a central processing unit to schedule special processes to be executed in an auxiliary processing unit, in response to a new special process request received by said central processing unit when a preceding special process is being executed in said auxiliary processing unit and the new special process is higher in priority than the preceding special process, comprising the steps of:

selecting any one of ending the preceding special process, interrupting the preceding special process and saving a processing status thereof, and interrupting the preceding special process and discarding the processing status, based on first to fourth times, the first time being time from the moment the new process request is received to the moment the new special process must be ended, the second time being a processing time of the new special process, the third time being time from the moment the request is received to the moment the preceding special process is to end, and the fourth time being time required to interrupt the preceding special process being executed in said auxiliary processing unit and to save or discard the processing status thereof; and

scheduling a time at which the new special process is to start.

10. A scheduling method for allowing a central processing unit to schedule special processes to be executed in an auxiliary processing unit, in response to a new special process request received by said central processing unit when a preceding special process is being executed in said auxiliary processing unit and the new special process is higher in priority than the preceding special process, comprising the steps of:

calculating a limit time, Ta, from the moment the new process request is received to the moment the new special process must be ended;

retrieving a processing time, Tb, of the new special process and calculating a latest start time, Tc, before which the new special process must be started to complete within the limit time by subtracting the processing time Tb from the limit time Ta;

calculating a time, Td, when the preceding special process is to end;

starting the new special process after the preceding special process is ended if Tc≧

Td;

interrupting the preceding special process, saving the processing status, and then starting the new special process if Tc<

Td and Tc≧

Te, Te being a time at which the processing status of the interrupted preceding special process in said auxiliary processing unit is saved; and

interrupting the preceding special process, discarding the processing status, and then starting the new special process if Tc<

Td, Tc<

Te, and Tc≧

Tf, Tf being a time at which the processing status of the interrupted preceding special process in said auxiliary processing unit is discarded.

11. A data processing system comprising:

a central processing unit; and

an auxiliary processing unit which runs in parallel with said central processing unit and which executes a special process according to a schedule made by said central processing unit,

wherein said auxiliary processing unit comprises;

a number-of-instructions counter that indicates a progress status of the special process being executed therein; and

an operation status register that indicates an operation status thereof, and

wherein said central processing unit comprises;

a database which stores a predetermined execution processing time of each special process; and

a scheduling unit, responsive to a new process request received when said operation status register indicates that a preceding special process is being executed in said auxiliary processing unit and the new special process is higher in priority than the preceding special process, for selecting any one of (i) ending the preceding special process, (ii) interrupting the preceding special process and saving a processing status, and (iii) interrupting the preceding special process and discarding the processing status, and scheduling a time at which the new special process is to start, wherein the scheduling unit selects based on (a) a limit time from the moment the new process request is received to the moment the new special process must be ended, (b) a processing time of the new special process, said processing time being stored in said database, (c) a time required for the preceding special process to end, said time being obtained by referencing the number-of-instructions counter, and (d) a time required to interrupt the preceding special process being executed in said auxiliary processing unit, and to save or discard the processing status.