Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-12-29
2003-12-23
Banankhah, Majid A. (Department: 2127)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000
Reexamination Certificate
active
06668269
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a process scheduler for a computer system (hereunder sometimes referred to as a computer-system process scheduler), which uses a process scheduler supported by an operating system so as to cause a user-level process scheduler to function. More particularly, the present invention relates to a computer-system process scheduler that uses a process scheduler, which establishes fixed priorities respectively corresponding to a plurality of processes to be scheduled (namely, objects of scheduling) and next allocates a central processing unit (CPU) to a plurality of executable processes in the descending order of the priorities thereof and further causes the CPU to operate, so as to allow a user-level process scheduler to function.
2. Description of the Related Art
Generally, a plurality of programs are executed concurrently in a computer, so that a plurality of executable units (namely, run units) named as “processes” are permitted to be present therein. At that time, it is necessary to assign the CPU to each process according to an algorithm. Such assignment of the CPU to a process is referred to as “process scheduling”. Conventional process scheduling is-performed in a batch system or by a time-sharing system. Further, conventional process schedulers were created for the purpose of increasing the CPU utilization (efficiency) of the entire system. In the case of time-sharing systems, reduction in response time required to respond to a user's operation (namely, the improvement of response performance) was further taken into account. It, however, has been regarded as being inevitable that the response time becomes long under heavy load conditions of the systems. Thus, there is no guarantee on the utilization of the CPU by user processes. Additionally, in the case of controlling built-in equipment which requires real time processing, all processes to be executed can be known when designed. Consequently, a fixed-priority scheduler, by which fixed priorities are assigned to the processes and a process of a priority higher than the priorities of other processes is preferentially executed, is used.
Meanwhile, with the recent development of multi-media systems, process schedulers for computers have come to handle videos and audios. In order to reproduce videos and audios smoothly, certain processes should be carried out securely at predetermined time intervals. In the case of such a conventional multi-media system, the conventional scheduling has the following problems:
I. In the case of the scheduling performed in the conventional batch system or in the conventional time-sharing system, there is no guarantee concerning when and how a CPU can-be utilized therein. In the case of employing such scheduling, the CPU cannot be utilized when a multi-media application program becomes necessary. As a result, when reproducing video data, a moving object generated in reproduced images does not appear to move smoothly.
II. The multi-media application programs are different from programs for controlling the built-in equipment in that the multi-media application programs cannot predict what processes or programs will be executed. The multi-media application programs, therefore, cannot preliminarily establish the priorities of processes (namely, assign the priorities to the processes, respectively). The conventional scheduling, which uses fixed priorities, cannot achieve the purpose of the schedulers. This problem also arises in the case of employing a rate monotonic scheduling method by which, among periodic processes, a process having a period shorter than those of the other processes is preferentially executed.
III. The multi-media application programs are further different from programs for controlling the built-in equipment in that the reliability of a run of the multi-media application is low. For example, if a certain multi-media application program permanentally uses a CPU on purpose or by mistake, programs having priorities lower than that of the process occupying the CPU do not run at all in the case that the scheduling is performed by using the fixed priorities. An occurrence of such a situation is not allowed in a general-purpose multi-media system.
For the aforementioned reasons, there has now emerged a need for a new process scheduling method which is available in a multi-media system. The research and development of such a process scheduling method are currently pursued. Incidentally, there are two cases or manners of introducing a new process scheduler, which is suitable for a multi-media system, thereinto. Namely, in a first case, the process scheduling is performed in an operating system. Further, in a second case, the process scheduling is carried out by a user program which runs or operates on (namely, under the control of) an operating system. Hitherto, the following problems, however, have arisen in the case when such a process scheduler is introduced into a multi-media system.
(1) Problems caused when introducing such a new process scheduler into the operating system:
(i) Conventional operating systems do not permit any persons other than developers thereof to add a process scheduler thereto or modify the process scheduler thereof. A source code of the operating system and a development environment, in which the operating system is developed, are necessary for changing the scheduler thereof. In the case of commercial operating systems, generally, persons other than developers thereof cannot get the source codes thereof. Even if a person other than the developers could get the source code of a commercial operating system, he should pay a very expensive royalty fee. Actually, it is impossible for a developer of a multi-media system to modify the process scheduler of the commercial operating system.
(ii) In the case of non-commercial operating systems, persons other than developers thereof may be able to get the source codes of some of the non-commercial operating systems free of charge. However, if the source code of such a non-commercial operating system is obtained, this non-commercial operating system cannot allow a large number of application programs to run. Moreover, there is a problem in a system to support users or the persons who have got the source codes. The present conditions, therefore, do not permit non-experts of an operating system for a computer to utilize non-commercial operating systems.
(iii) Whether an operating system to be modified is a commercial one or a non-commercial one, general knowledge concerning an operating system and comprehension of an operating-system installing method peculiar to the operating system are required to modify the operating system.
(2) Problems caused when introducing the new process scheduler into the operating system by executing a user program:
(i) There has been a method for realizing a pseudo process (namely, a user-level thread) in a user own process by a user program or a library utilized by a user program and for scheduling of user-level threads. This method, however, can perform the scheduling only in the process. Therefore, in the case that there are other groups of processes which utilize a CPU required by a multi-media system, the utilization of the CPU required by the multi-media system cannot be ensured.
(ii) Further, there has been a method by which a user program becomes a scheduler and this scheduler gives a user process a priority used by a fixed-priority scheduler which is supported by an operating system. Namely, this method utilizes the scheduling (function) provided by the operating system. Consequently, the utilization of the CPU in the user process needed by the multi-media system cannot be ensured.
(iii) Generally, the modification of the user program becomes further necessary in the aforementioned cases of (2)(i) and (2)(ii).
As is understood from the foregoing description, in the case of the conventional process schedulers, it is very difficult to introduce a new (conventional) process scheduler, which is r
Kamada Jun
Ono Etsuo
Yuhara Masanobu
Banankhah Majid A.
Fujitsu Limited
Staas & Halsey , LLP
LandOfFree
Computer system process scheduler determining and executing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer system process scheduler determining and executing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer system process scheduler determining and executing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3179151