Data processing system having multiple processors, a task scheduler for a data processing system having multiple processors and a corresponding method for task scheduling

• US 20050081200A1
• Filed: 12/05/2002
• Published: 04/14/2005
• Est. Priority Date: 12/14/2001
• Status: Abandoned Application

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Van Eijndhoven, Josephus Theodorus Johannes, Rutten, Martijn Johan, Pol, Evert-Jan Daniel
• Application Number:
  US10/498,298
• Publication Number:
  US 20050081200A1
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/485 Resource constraint
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

The invention is based on the idea to provide distributed task scheduling in a data processing system having multiple processors. Therefore, a data processing system comprising a first and at least one second processor for processing a stream of data objects, wherein said first processor passes data objects from a stream of data objects to the second processor, and a communication network and a memory is provided. Said second processors are multi-tasking processors, capable of interleaved processing of a first and second task, wherein said first and second tasks process a first and second stream of data objects, respectively. Said data processing system further comprises a task scheduling means for each of said second processors, wherein said task scheduling means is operatively arranged between said second processor and said communication network, and controls the task scheduling of said second processor.

Claims

1. A data processing system, comprising:

a first and at least one second processor for processing a stream of data objects, said first processor being arranged to pass data objects from a stream of data objects to the second processor, said second processors being multi-tasking processors, capable of interleaved processing of a first and second task, wherein said first and second tasks process a first and second stream of data objects, respectively;

a communication network; and

a task scheduling means for each of said second processors, said task scheduling means being operatively arranged between said second processor and said communication network;

wherein the task scheduling means of each of said second processors controls the task scheduling of said second processor.

2. Data processing system according to claim 1, wherein

said second processors are arranged to handle multiple inbound and outbound streams and/or multiple streams per task.

3. Data processing system according to claim 1, wherein

said task scheduling means are adapted to determine the next task to be processed by said second processor upon receiving a request from said second processor and to forward an identification of said next task to said second processor,

wherein said second processor requests a next task at successive intervals;

said intervals representing the processing steps of said second processor.

4. Data processing system according to claim 1, wherein

the communication between said second processors and their associated task scheduling means is a master/slave communication, said second processors acting as masters.

5. Data processing system according to claim 1, wherein

said second processors being function-specific dedicated processors performing a set of parameterised stream processing functions.

6. Data processing system according to claim 1, wherein said task scheduling means comprises:

a stream table for storing parameters of each stream associated with the tasks mapped on the associated processor, said stream table containing various administrative data per stream, and/or

a task table for administrating the different tasks associated to said second processor, said task table containing an index to the stream table indicating which streams are associated to said task, an enable flag for each task indicating whether the task is allowed to run, and/or a budget counter indicating an available processing budget for each task.

7. Data processing system according to claim 6, wherein

said stream table contains an amount of valid data for reading, an amount of available room for writing, information on whether the running task is blocked on reading or writing to said stream, and/or configuration information relating said stream to a task.

8. Data processing system according to claim 6, wherein

said task scheduling means is adapted to check all streams in said stream table and to determine which of said streams allow task progress,

wherein a stream allows progress if a) the stream has valid data for reading or available room for writing, b) the task did not request more valid data or room than is available in the stream, and/or c) option a), b) are configured as irrelevant for task progress.

9. Data processing system according to claim 6, wherein

said task scheduling means is adapted to check all tasks in said task table and to determine which of said tasks are allowed to run,

wherein a task is allowed to run if all the streams associated to said task allow task progress and the task is configured to be runnable.

10. Data processing system according to claim 6, wherein

said task scheduling means is adapted to select one task from a plurality of configured tasks as the task to be processed next.

11. Data processing system according to claim 1, wherein

said task scheduling means comprises a budget counter means for controlling the resource budget of the current task.

12. Data processing system according to claim 1, wherein

said task scheduling means is adapted to utilize a resource budget parameter per task, wherein said resource budget parameter limits the time in which a processor is continuously occupied with the related task.

13. Data processing system according to claim 12, wherein

said task scheduling means is adapted to select a task which is to be processed next after the current task, upon receiving a request from said second processor

wherein the current task is allowed to continue if the current task is still allowed to run and its resource budget is not depleted;

wherein otherwise a next task as determined by said task scheduling means is selected as new current task.

14. Data processing system according to claim 13, wherein

said task scheduling means is adapted to select the next task that is allowed to run in round-robin order.

15. Data processing system according to claim 1, wherein

said task scheduling means is adapted to select a task which is to be processed next before said second processor request a next task, so that the identification of the selected next task can be immediately returned to said second processor.

16. Data processing system according to claim 12, wherein

said budget counter is updated by events based upon a real-time clock.

17. Data processing system according to claim 12, wherein

said task scheduling means is adapted to replenish the budget of a next task when it is selected to become the current task.

18. Data processing system according to claim 1, wherein

said second processors being a programmable processors performing a set of programmable parameterised stream processing functions.

47. A method for task scheduling according to claim 1, further comprising the step of:

implementing the task scheduler on a programmable second processor.

19. A task scheduler for a data processing system, said system comprising a first and at least one second processor for processing a stream of data objects, said first processor being arranged to pass data objects from a stream of data objects to the second processor, a communication network and a memory, wherein

the task scheduler is adapted to be associated to one of said second processors,

the task scheduler is being adapted to be operatively arranged between said second processor and said communication network;

and

the task scheduler is adapted to control the task scheduling of said associated second processor.

20. A task scheduler according to claim 19, wherein

said task scheduler is adapted to determine the next task to be processed by said second processor upon receiving a request from said second processor and to forward an identification of said next task to said second processor,

wherein said second processor requests a next task at predetermined intervals;

said intervals representing the processing steps of said second processor.

21. A task scheduler according to claim 19, further comprising:

a stream table for storing parameters of each stream associated with the tasks mapped on the associated processor, said stream table containing various administrative data per stream, and/or

a task table for administrating the different tasks associated to said second processor, said task table containing an index to the stream table indicating which streams are associated to said task, an enable flag for each task indicating whether the task is allowed to run, and/or a budget counter indicating an available processing budget for each task.

22. A task scheduler according to claim 19, wherein

said stream table contains an amount of valid data for reading, an amount of available room for writing, information on whether the running task is blocked on reading or writing to said stream, and/or configuration information relating said stream to a task

23. A task scheduler according to claim 21, being

adapted to check all streams in said stream table and to determine which of said streams allow task progress,

wherein a stream allows progress if a) the stream has valid data for reading or available room for writing, b) the task did not request more valid data or room than is available in the stream, and/or c) option a), b) are configured as irrelevant for task progress.

24. A task scheduler according to claim 21, being

adapted to check all tasks in said task table and to determine which of said tasks are allowed to run,

wherein a task is allowed to run if all the streams associated to said task allow task progress and the task is configured to be runnable.

25. A task scheduler according to claim 24, being

adapted to select a task which is to be processed next after the current task, upon receiving a request from said second processor;

wherein the current task is allowed to continue if the current task is still allowed to run and the budget counter in said task table is nonzero,

wherein otherwise the next task as determined by said task scheduling means is selected as current task and the budget counter is reset.

26. A task scheduler according to claim 21, being

adapted to select one task from a plurality of configured tasks as the task to be processed next.

27. A task scheduler according to claim 19, comprising

a budget counter means for controlling the resource budget of the current task.

28. A task scheduler according to claim 19, being

adapted to utilize a resource budget parameter per task, wherein said resource budget parameter limits the time in which a processor is continuously occupied with the related task.

29. A task scheduler according to claim 28, being adapted to select a task which is to be processed next after the current task, upon receiving a request from said second processor

wherein the current task is allowed to continue if the current task is still allowed to run and its resource budget is not depleted;

wherein otherwise a next task as determined by said task scheduling means is selected as new current task.

30. A task scheduler according to claim 29, being

said task scheduling means is adapted to select the next task that is allowed to run in round-robin order.

31. A task scheduler according to claim 28, being

adapted to replenish the budget of a next task when it is selected to become the current task.

32. A method for task scheduling in a data processing system, said system comprising a first and at least one second processor for processing a stream of data objects, said first processor being arranged to pass data objects from a stream of data objects to the second processor, a communication network, said system having a task scheduler for each of said second processors;

whereby

the task scheduler controls the task scheduling of said second processor

33. A method for task scheduling according to claim 32, further comprising the steps of:

determining the next task to be processed by said second processor upon receiving a request from said second processor, and

forwarding an identification of said next task to said second processor,

wherein said second processor requests a next task at successive intervals;

said intervals representing the processing steps of said second processor.

34. A method for task scheduling according to claim 32, wherein

the communication between said second processors and their associated task scheduling means is a master/slave communication, said second processors acting as masters.

35. A method for task scheduling according to claim 32, further comprising the steps of:

storing parameters of each stream associated with the tasks mapped on the associated processor a stream table, said stream table containing various administrative data per stream, and/or

administrating the different tasks associated to said second processor a task table, said task table containing an index to the stream table indicating which streams are associated to said task, an enable flag for each task indicating whether the task is allowed to run, and/or a budget counter indicating an available processing budget for each task.

36. A method for task scheduling according to claim 35, wherein

said stream table contains an amount of valid data for reading, an amount of available room for writing, information on whether the running task is blocked on reading or writing to said stream, and/or configuration information relating said stream to a task

37. A method for task scheduling according to claim 35, further comprising the steps of:

checking all streams in said stream table and to determine which of said streams allow task progress, wherein

a stream allows progress if a) the stream has valid data for reading or available room for writing, b) the task did not request more valid data or room than is available in the stream, and/or c) option a), b) are configured as irrelevant for task progress.

38. A method for task scheduling according to claim 35, further comprising the steps of:

checking all tasks in said task table and determining which of said tasks are allowed to run,

wherein a task is allowed to run if all the streams associated to said task allow task progress and the task is configured to be runnable.

39. A method for task scheduling according to claim 35, 36, 37 or 38, further comprising the step of:

selecting one task from a plurality of configured tasks as the task to be processed next.

40. A method for task scheduling according to claim 32, further comprising the step of:

for controlling the resource budget of the current task.

41. A method for task scheduling according to claim 32, further comprising the step of:

utilizing a resource budget parameter per task, wherein said resource budget parameter limits the time in which a processor is continuously occupied with the related task.

42. A method for task scheduling according to claim 41, further comprising the steps of:

selecting a task which is to be processed next after the current task, upon receiving a request from said second processor

wherein the current task is allowed to continue if the current task is still allowed to run and its resource budget is not depleted;

wherein otherwise a next task as determined by said task scheduling means is selected as new current task.

43. A method for task scheduling according to claim 42, further comprising the step of:

selecting the next task that is allowed to run in round-robin order.

44. A method for task scheduling according to claim 32, further comprising the step of:

selecting a task which is to be processed next before said second processor request a next task, so that the identification of the selected next task can be immediately returned to said second processor.

45. A method for task scheduling according to claim 41, further comprising the step of:

updating said budget counter by events based upon a real-time clock.

46. A method for task scheduling according to claim 41, further comprising the steps of:

replenishing the budget of a next task when it is selected to become the current task.