Batch-wise handling of signals in a processing system

• US 6,662,203 B1
• Filed: 11/12/1999
• Issued: 12/09/2003
• Est. Priority Date: 11/16/1998
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Johnson, Sten Edvard, Kling, Lars-Örjan, Holmberg, Per Anders, Egeland, Terje
• Primary Examiner(s): Patel, Ramesh
• Assistant Examiner(s): PHAM, THOMAS K
• Application Number:
  US09/438,922
• Time in Patent Office: 1,488 Days
• Field of Search: 709/102, 709/103, 709/101, 709/207
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

The present invention relates to multiprocessing systems in which signals or processes are scheduled in order of their priority level. The invention is based on batch-wise acceptance and scheduling of job signals, and utilizes at least one delay queue for temporarily storing job signals to the processing system before they are accepted for scheduling. The processing system further comprises circuitry for batch-wise insertion of the temporarily stored job signals into the job scheduler of the multiprocessing system. In this way, the utilization of the parallel processing units is increased and the number of changes between different priority levels in the multiprocessing system is minimized.

Claims

1. A processing system comprising:

multiple processing units for parallel processing of job signals of different priority levels;

a job scheduler for scheduling the job signals for processing by the processing units in order of the priority level of the job signals, said job scheduler including a plurality of job buffers that store the job signals before the job scheduler passes the job signals to the processing units, each of the job buffers storing job signals of a different priority level;

at least one delay queue for temporarily delaying the job signals before the job signals reach the job buffers in the job scheduler, said delay queue temporarily storing the job signals until a batch of job signals accumulates in the delay queue; and

means for extracting the temporarily stored job signals as a batch from the delay queue and inserting the batched job signals into the job scheduler,

whereby, due to the insertion of job signals in batches, the multiple processing units are enabled to operate at a higher load level, and the number of changes between different priority levels of job signals in the processing units is minimized.

2. The processing system according to claim 1, further comprising a counter that controls the extracting means to extract the batch of temporarily stored job signals from the delay queue and insert the batched job signals into the job scheduler whenever the counter expires, wherein batches of temporarily stored job signals are periodically inserted into the job scheduler.

3. The processing system according to claim 1, further comprising a memory that stores the job signals until needed by the processing units, and wherein the delay queue is a queue of pointers that point to the job signals in the memory, and the means for extracting the batch of temporarily stored job signals from the delay queue and inserting the batched job signals into the job scheduler moves pointers from the delay queue to the job scheduler.

4. The processing system according to claim 1, wherein the batched job signals is inserted into the job scheduler when the delay quences becomes full.

5. The processing system according to claim 1, further comprising a number plurality of delay queues, each one of the delay queues being associated with a predetermined priority level for temporarily delaying job signals of the associated priority level.

6. The processing system according to claim 1, wherein the processing units are operable for processing job signals to independently execute different jobs in parallel, one of the parallel jobs being executed non-speculatively, and the remaining jobs being executed speculatively.

7. The processing system according to claim 5, wherein the means for extracting the batch of temporarily stored job signals from the delay queue and inserting the batched job signals into the job scheduler is operable for inserting the batched job signals of a selected one of the delay queues into a selected one of the job buffers in the job scheduler.

8. The processing system according to claim 5, wherein the means for extracting the batch of temporarily stored job signals from the delay queue and inserting the batched job signals into the job scheduler is operable for inserting the batched job signals of a selected one of the delay queues into a selected one of the job buffers in the job scheduler having a priority level corresponding to the priority level of the selected delay queue.

9. The processing system according to claim 5, wherein the delay queues and the job buffers in the job scheduler are built based on linked lists or queue segments in a memory, and the means for extracting the batch of temporarily stored job signals from the delay queue and inserting the batched job signals into the job scheduler is operable for inserting the batched job signals of a predetermined one of the delay queues into the job scheduler by linking a head element of the delay queue to a tail of a corresponding job buffer.

10. The processing system according to claim 6, wherein the job scheduler is operable for initiating an interrupt of the non-speculatively executed job and initiating flush of the speculatively executed jobs, upon reception of a job signal having a priority level that is higher than that of the jobs in the processing units.

11. The processing system according to claim 8, wherein if the processing units complete the processing of a batch of job signals having a high priority level prior to receiving another batch of job signals having the high priority level, the processing units process batches of lower priority job signals until another batch of job signals having the high priority level is received.

12. A method of handling job signals of different priority levels in a processing system having multiple processing units for parallel processing of job signals, and a job scheduler comprising a plurality of job buffers that store the job signals and insert the job signals into the processing units in descending order of priority level, said method comprising the steps of:

delaying the job signals prior to the scheduler in a plurality of delay queues until a batch of job signals is received in each delay queue, wherein the step of delaying the job signals is performed on a priority basis such that job signals of different priority levels are input into different delay queues;

extracting the job signals from each delay queue as a batch, and inserting the batched job signals into a job buffer in the job scheduler having a corresponding priority level; and

scheduling the job signals for processing by the processing units in order of the priority level of the job signals, said scheduling step including;

storing each received batch of job signals in a job buffer in the job scheduler having a priority level corresponding to the priority level of the received batch of job signals; and

passing the batches of job signals to the processing units in descending order of the priority levels;

whereby the multiple processing units are enabled to operate at a higher load level, and the number of changes between different priority levels of job signals in the processing units is minimized.

13. The method according to claim 12, wherein each delay queue is associated with a corresponding job buffer in the scheduler, the delay queues and the job buffers being based on linked list segments, and the step of extracting the job signals from each delay queue as a batch, and inserting the batched job signals into the job scheduler includes the step of linking the head of each delay queue to the tail of the corresponding job buffer.

14. The method according to claim 12, further comprising, if the processing units complete the processing of a batch of job signals having a high priority level prior to receiving another batch of job signals having the high priority level, processing batches of lower priority job signals until another batch of job signals having the high priority level is received.

15. A scheduler for scheduling process signals for processing in a processing system having multiple processes that execute the process signals in order of descending priority level, said scheduler comprising:

a process handler for directing the process signals to corresponding processes and for scheduling the processes to execute the process signals in descending order of priority level;

at least one delay queue for temporarily delaying the process signals prior to the process handler until a batch of process signals is accumulated in the delay queue; and

means for inserting the temporarily delayed process signals into the process handler as a batch,

whereby the multiple processing units are enabled to operate at a higher load level, and the number of changes between different priority levels of process signals in the processes is minimized.

16. The scheduler according to claim 15, wherein the process signals are stored in a memory, the delay queue is a queue of pointers to the process signals in the memory, and the means for inserting the temporarily delayed process signals into the process handler as a batch moves pointers from the delay queue to the process handler.

17. The scheduler according to claim 15, further comprising a counter that periodically controls the inserting means to insert the batch of temporarily delayed process signals into the process handler when the counter expires.

18. The scheduler according to claim 15, wherein the inserting means inserts the batch of temporarily delayed process signals into the process handler whenever the delay queue becomes full.

19. The scheduler according to claim 17, wherein the inserting means inserts the batch of temporarily delayed process signals into the process handler when the delay queue becomes full, if the delay queue becomes full prior to the counter expiring.