Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-10-07
2004-01-06
Maung, Zarni (Department: 2126)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06675190
ABSTRACT:
BACKGROUND OF THE INVENTION
In digital communications networks, particularly in SDH networks (SDH: Synchronous Digital Hierarchy), a database containing data about the current network configuration is provided for each network element. To manage a network element, several scheduler tasks must be processed in parallel. To accomplish this, use is made of operating systems, such as UNIX or MACH, which control access to one or more processors using so-called threads. These operating systems are known per se and are described in many forms in the literature, for example in a book by A. Silberschatz et al, “Operating System Concepts”, 3
rd
Edition, 1991, Addison-Wesley Publishing Company, Reading, Mass., USA, Chapter 4.2.3, pages 96-97. With the aid of such operating systems, access by two or more scheduler tasks to one processor is controlled in such a way that for each task currently using the processor, a decision is made as to when the processor is freed for the next task. For this mode of operation, the term “cooperative multitasking” is used. The order in which the tasks are executed is determined by a control module, a so-called task scheduler.
Such a control module and a method for cooperative multitasking are disclosed in U.S. Pat. No. 5,437,032. There, two or more scheduler tasks are combined into jobs. Each job is assigned a weight in accordance with a priority. Its share of the total weight of all jobs corresponds to the actual level of multitasking activity. A desired level of multitasking activity is defined which corresponds to the maximum number of tasks that can be executed concurrently. The discrepancy between these two levels is used to determine the order in which the jobs are executed. Jobs whose actual level of multitasking activity differs greatly from the desired level are preferentially scheduled for execution. In the method disclosed in U.S. Pat. No. 5,437,032, it may happen that individual tasks are not executed because their lobs have only a very small discrepancy and are always dealt with after jobs with a large discrepancy.
In an article by M. P. Bosse et al, “Management von SDH-Netzelementen: eine Anwendung der lnformationsmodellierung”, Elektrisches Nachrichtenwesen, a journal published by the applicant, 4
th
Quarter 1993, pages 329-338, a method of and apparatus for managing network elements in digital communications networks are described. A task scheduler is not described there, however.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a method and apparatus for cooperative multitasking in a communications network which do not have the above disadvantages.
This object is attained by a method with the features according to claim
1
and by a network element with the features according to the independent claim.
Accordingly, each scheduler task is assigned a counter and a threshold value, 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 at least one of the counters exceeds the associated threshold value. If that is the case for a single task, this task will be executed and its counter will be reset. If that is the case for at least two tasks, one of the set of tasks will be selected by at least one selection criterion. This task will then be executed and its counter will be reset. The counters assigned to the remaining tasks, i.e., the tasks awaiting execution, are incremented by one count. The execute cycle will be repeated if it is determined that at least one more of the tasks is waiting to be processed.
The waiting times are thus monitored by means of the counters, and those tasks which have been waiting longer than a time determined by the threshold value are given priority. In addition, a selection criterion is taken into account to define the order if none of the tasks is to be given priority in view of the waiting times.
Further advantageous features of the invention are apparent from the subclaims.
Accordingly, it is particularly advantageous if the selection criterion is a priority criterion according to which a test is made to determine the order in which the tasks will be executed. Thus, of those tasks whose counts are greater than the associated threshold values, first the very important tasks and then the less important tasks are processed.
In another preferred embodiment of the invention, the selection criterion is a time period that indicates how long each task stays in a wait loop, and according to which it is determined which task will be executed next. The order of execution is thus determined by the positions of the tasks in a wait loop. Through this round-robin principle, a task can be incorporated into the process in a very simple manner.
Advantageously, each threshold value is a number less than the total number N of tasks to be executed by not more than one, and all threshold values are increased by at least one if another task is waiting to be executed. These measures ensure that all tasks that are waiting to be executed profit from the cooperative multitasking and are processed within as short a time as possible.
If the number N increases by one (N=N+1) because another task is waiting to be processed, it is particularly advantageous to increase only those threshold values by one which are less than or equal to N−1. This allows all tasks to be executed within as few execute cycles as possible.
Particularly advantageously, a single task is taken into account only on the occurrence of an event that necessitates processing this task. This means that specific tasks can be deferred until the occurrence of expected events that make it necessary to process these specific tasks. For instance, system alerts or emergency alarms may occur, for which special scheduler tasks are available. These tasks are suspended until the occurrence of the events. In this very simple manner, the method is extended to a larger set of tasks without these specific tasks having to be constantly managed and without the control module (“task scheduler”) being additionally loaded.
In another preferred embodiment of the invention, a task is taken into account as a task to be executed only when a predeterminable time interval has expired. This means that the task is deactivated until the expiration of the time interval. The event is, for example, the expiration of a predeterminable maintenance interval, and the task executes a maintenance routine.
REFERENCES:
patent: 5437032 (1995-07-01), Wolf et al.
patent: 6105048 (2000-08-01), He
patent: 0 658 841 (1995-06-01), None
A. Silberschatz et al, Operating System Concepts, 3rdEdition 1991, Chapter 4.2.3, pp. 96-97.
M. P. Bosse et al, “Management of SDH Network Elements: An Application of Information Modelling”, Alcatel Electrical Communication, 4thQuarter 1993; pp. 329-338.
H. M. Deitel, “An Introduction to Operating Systems”, 1990, Chapter 10,-Job and Processor Scheduling pp. 285-304.
Dr. Kocher Hartmut
Klamt Reimund
Schabernack Jörg
Alcatel
Maung Zarni
Opie G. Lawrence
LandOfFree
Method for cooperative multitasking in a communications... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for cooperative multitasking in a communications..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for cooperative multitasking in a communications... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3198334