Electrical computers and digital processing systems: multicomput – Computer conferencing – Priority based messaging
Reexamination Certificate
1998-09-11
2001-01-30
Rinehart, Mark H. (Department: 2756)
Electrical computers and digital processing systems: multicomput
Computer conferencing
Priority based messaging
C709S241000, C709S241000, C709S200000, C709S229000, C709S232000, C709S240000, C710S029000, C710S040000, C710S054000, C710S060000, C710S244000, C710S263000
Reexamination Certificate
active
06182120
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to data processing in a multitasking operating computer system and more particularly to a method and a system for controlling data transfer between a host data processing system and communication networks by processing queued messages according to a combination of time and weight criteria.
BACKGROUND OF THE INVENTION
Operating systems that use single tasking have existed on host data processing systems for many years. In such systems, the operating system executes computer programs, subroutines or tasks serially. Before beginning a new task, the previous one must be completed. The waiting delay may last for a certain period and the throughput of the operating system may be impacted. Thus, the system may break down.
This problem has led to the advent of the multitasking or multi thread operating systems in which each computer program or task is divided into a plurality of tasks or streams of execution. Furthermore, multitasking operating systems have also been extended to multiprocessor environments where tasks of the same or different programs can be executed in parallel on different computer processors. While such multitasking operating systems optimize the use of one or more processors, they do not permit the application program developer to adequately influence the scheduling of the task executions.
There are different mechanisms for processing the set of queues in which the tasks are queued. Such mechanisms are based on three main basic principles:
the principle based on priority: wherein a set of priorities is assigned to the different queues and the queue with highest priority is served as long as it is not empty. In such case, the queues with lower priorities might never be served because of the important traffic on higher priority queues;
the principle based on a predefined processing sequence: wherein an order for processing of queues is defined according to a priority that is defined by repetition of a queue in the sequence. Whatever the status of the queues are, the sequence is executed (high priority is defined by a high number of occurrences of a given queue in the sequence); and
the principle based on time: wherein each queue is assigned a processing time. The queue is to be processed when the corresponding processing time has elapsed. In this case, the queue priority is defined according to the value of the corresponding processing time (the higher the priority of the queue is, the lower the relevant processing time should be).
In any one of these mechanisms which are to some extent static, the queue evolution and aging are not taken into consideration. In order to cope with the data traffic and not to impact on the throughput of the queue processing, it is required to implement a mechanism that is based on criteria which may have static requirements but which may also evolve in real time so as to process within acceptable delays all the messages in the queues, even the ones with the lowest priorities.
In U.S. Pat. No. 5,630,128, a controlled scheduling of program threads in a multitasking operating system is disclosed. In this technique, a multitasking operating system permits application programs to influence a schedule of execution of programs to which are assigned priority levels and dispatch classes in which the threads reside. According to these parameters, the operating system queues the highest priority thread which is available for execution from each dispatch class onto a run list for execution by a processor. The highest priority thread on the run list is executed first. But in this kind of implementation, there is no guarantee that the lowest priority thread can be processed within an acceptable delay unless no higher priority thread remains on the run list.
In another U.S. Pat. No. 5,437,032, a task scheduler for a multiprocessor system, each containing one or more processors, concurrently execute tasks into which jobs as database queries are divided. Each job is assigned a weight in accordance with the external priority of the job. A desired level of concurrent task activity is defined for each of the jobs. The actual level of concurrent task activity for each of the jobs is also determined. The jobs are prioritized for execution of awaiting tasks in accordance with the discrepancy between the desired level of concurrent task activity and the actual level of concurrent task activity for each of the jobs. This technique is based on the definitions of desired and actual levels and does take into account the time constraint wherein a task or a set of tasks are to be executed within a certain delay.
In U.S. Pat. No. 5,247,671, scalable schedules for a serial communications controller in a data processing system is disclosed. In this document, the tasks are scheduled at different priority level so that time-critical tasks are performed quickly enough to prevent data loss. The notion of time-critical in this patent came directly from the notion of priority. Both notions are not independent, meaning that the tasks are arranged according to certain priority and in this arrangement, some or all the tasks might have time-critical values.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a method and a system for use in data processing in a computer system where the tasks or messages that are queued might have both an associated priority and a time-critical delay.
It is also an object of the invention to have an implementation wherein the prioritizing of queues and messages should not deteriorate the time responses of messages of the lowest priorities.
It is another object of the present invention to be applicable to any software managed system where the users share a single resource.
Accordingly, the queues are processed according to two criteria that are the static priority requirements of the queues and its acceptable aging. The queue processing is then based on a time and weight dependent mechanism.
Therefore, according to the present invention, a method for controlling data transfer between a host data processing system and communication networks by processing queued messages of a plurality of queues (MIQ) saved in a data store comprises the steps of:
(a) dequeueing, in normal state, successively queued messages from a plurality of queues (MIQ) according to their queue priorities;
(b) interrupting this normal state to enter a critical state, by dequeueing successively queued messages from a plurality of critical queues (MIQ) according to their queue priorities, the critical queues having aging times that exceed predetermined values (Delay.Maxi); and
(c) returning to the previous normal state with its set of parameters to continue until the next critical state occurs or until the end of the scheduling cycle.
According to the present invention, a system is provided for controlling data transfer between a host data processing system and communication networks by processing queued messages of a plurality of queues (MIQ) saved in a data store, wherein each MIQ is associated with at least four registers:
a first register for static weight (Stat.Ni) corresponding to the number of messages which may be pulled out from the queue, the first register being implemented in connection with a second register for current weight (Cur.Ni) corresponding to the number of messages left that are allowed to be dequeued from the queue, for processing queued messages in normal state; and
a third register for maximum delay (Delay.Maxi) corresponding to the maximum waiting time of a non-empty MIQ to be dequeued, the third register being implemented in connection with a fourth register for dormant time (Dorm.i) corresponding to the elapsed time since the MIQ was last served, for processing queued messages in critical state when the fourth register exceeds the third register.
REFERENCES:
patent: 4084228 (1978-04-01), Dufond et al.
patent: 5012409 (1991-04-01), Fletcher et al.
patent: 5469571 (1995-11-01), Bunnell
patent: 5544318 (1996-08-01), Schmitz et al.
patent: 5892900 (1999-04-01), Gint
Beaulieu Cesca
Dispensa Jean-Claude
International Business Machines - Corporation
McConnell Daniel E.
Rinehart Mark H.
Vaughn, Jr William C.
LandOfFree
Method and system for scheduling queued messages based on... 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 and system for scheduling queued messages based on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for scheduling queued messages based on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2525639