Method for cooperative multitasking in a communications network, and a network element for carrying out the method

• US 6,675,190 B1
• Filed: 10/07/1999
• Issued: 01/06/2004
• Est. Priority Date: 10/08/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Schabernack, Jorg, Dr. Kocher, Hartmut, Klamt, Reimund
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): OPIE, GEORGE L
• Application Number:
  US09/414,311
• Time in Patent Office: 1,552 Days
• Field of Search: 709/102, 709/103, 709/104, 709/107, 709/100
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Instead of a conventional task scheduler in which tasks having a high priority are preferentially scheduled, so that the execution of tasks with very low priorities is blocked, a “fair scheduler” is proposed in which each task (TA to TE) is assigned a counter (CNT) and a threshold value (THD), with the threshold value specifying a maximum number of execute cycles within which the task need not be executed immediately, and the counter counting those execute cycles within which the task is not executed. At the beginning of each execute cycle, a test is made to determine whether one of the counters exceeds the associated threshold value. If that is the case, one (TD) of the corresponding tasks (TC, TD) is selected by a selection criterion and executed, and its counter is reset. The counters assigned to the remaining tasks are incremented by one, and the execute cycle is repeated if it is found that at least one more of the tasks (TC) is waiting to be processed.

Claims

1. A method for cooperative multitasking in a computer-controlled network element of a digital communications network wherein scheduler tasks are executed in a determined order, the method comprising the steps of:

(a) assigning a counter and a threshold value to each scheduler task, the threshold value specifying a maximum number of execute cycles within which the scheduler task need not be executed immediately, and the counter counting those execute cycles within which the scheduler task is not executed;

(b) determining at the beginning of each execute cycle whether at least one of the counters exceeds the associated threshold value;

(c) if it is determined that at least one of the counters exceeds the associated threshold value, selecting one of the corresponding scheduler tasks having the counter which exceeds the associated threshold value according to at least one selection criterion, executing the selected scheduler task, and resetting the counter of the selected scheduler task;

(d) incrementing by one the counters assigned to the remaining scheduler tasks which were not executed; and

(e) repeating steps (a) through (d) if it is determined that at least one of the scheduler tasks is waiting to be executed.

2. A method as claimed in claim 1 wherein the selection criterion is a priority criterion according to which a test is made to determine the order in which the scheduler tasks will be executed.

3. A method as claimed in claim 1 wherein the selection criterion is the time period that indicates how long each scheduler task stays in a wait loop, and on the basis of which it is determined which scheduler task will be executed next.

4. A method as claimed in claim 1 wherein each threshold value is a number less than the total number of scheduler tasks to be executed by not more than one, and wherein all threshold values are increased by one if another scheduler task is added.

5. A method as claimed in claim 1 wherein the number of scheduler tasks is increased by one if another scheduler task is waiting to be executed, and wherein only those threshold values are then increased by one which are less than or equal to the increased number.

6. A method as claimed in claim 1 wherein all threshold values are increased only on the occurrence of an event that requires the execution of the additional scheduler task.

7. A method as claimed in claim 1 wherein a single scheduler task is taken into account only on the occurrence of an event that requires the execution of this scheduler task.

8. A method as claimed in claim 1 wherein a scheduler task is taken into account as a task to be executed only when a predetermined time interval has expired.

9. A network element for a digital communications network, comprising at least one processor and a control module for implementing cooperative multitasking, wherein the processor executes scheduler tasks in an order determined by the control module, wherein for the determination of the order, the control module assigns a counter and a threshold value to each scheduler task, the threshold value specifying a maximum number of execute cycles within which the scheduler task need not be executed immediately, and the counter counting the execute cycles within which the scheduler task is not executed, wherein the control module determines at the beginning of the execute cycle whether at least one of the counters exceeds the associated threshold value, wherein, if it is determined that at least one of the counters exceeds the associated threshold value, the processor selects one of the corresponding scheduler tasks by at least one selection criterion and executes the selected scheduler task, the control module resets the counter of said the selected scheduler task which is executed, wherein at the end of the execute cycle, the counters assigned to the other scheduler tasks which were not executed are incremented by one, and wherein the control module controls a repetition of the execute cycle if it determines that at least one of the scheduler tasks is waiting to be executed.

10. A network element as claimed in claim 9 wherein at least two interconnected processors access at least two databases to execute the scheduler tasks using cooperative multitasking, and wherein one of the processors accesses the control module to determine the order in which the scheduler tasks will be executed.