Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
1998-09-16
2004-12-07
Banankhah, Majid A. (Department: 2127)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S100000, C718S102000
Reexamination Certificate
active
06829766
ABSTRACT:
BACKGROUND OF THE INVNETION
1. Field of the Invention
The present invention relates to a data processing method and, more particularly, to a schedule managing mechanism implemented by an operating system. The present invention also relates to a recording medium storing such an operating system, as well as to a data processing apparatus employing such a recording medium. Details of certain features of the present invention are described in European Patent Application No. 0.753,811 A1 entitled “Data processing method and device” and filed by the same assignee on Jul. 12, 1996 claiming a Convention Priority on JP 178625/95, filed 1997 Jul. 7, the complete disclosure of which is hereby incorporated herein by reference.
2. Description of the Related Art
Operating systems can be sorted into the following three types: operating systems using so-called fat kernels, operating systems employing so-called micro-kernels and operating systems adopting so-called nano-kernels.
In a fat-kernel-type operating system, all the functions of the system are packaged in a fat kernel. Referring to
FIG. 12
, when an application program requests the operating system to provide a service that is accompanied by a change in thread status, a system call is made to invoke from the kernel a module corresponding to the requested service, such as “Mailer” or “Synchronization”. Subsequently, in order to enable such a module to change the statuses of threads, a so-called function call is performed to invoke a “Scheduler” which controls the sequence of execution of the threads to manage the schedule of these threads, whereby the processing involving a change in the thread status is performed.
In order to package various functions in the operating system using a fat kernel, a programmer is required to have sufficient knowledge about the kernel because all the functions have to be packaged in the kernel. Further, alteration of functions cannot easily be effected since these functions are packaged in the kernel. Thus, the operating systems employing fat kernels generally have limited versatility.
Referring now to micro-kernel type operating system, the micro-kernel accommodates only basic functions such as hardware control functions, while other functions of the operating system are implemented externally of the micro-kernel. This type of operating system, therefore, is free from the problem of limited versatility that is inherent in the operating systems of fat-kernel type, because only selected functions are packaged in the kernel.
As shown in
FIG. 13
, the micro-kernel-type operating system permits not only application programs but also modules which provide operating system functions, e.g., “Synchronization”, “Mailer” and “Schedule” shown in
FIG. 13
, to run on the micro-kernel. Therefore, these modules providing the operating system functions are under the schedule control of the Scheduler loaded in the micro-kernel.
In the micro-kernel-type operating system, interactions between application programs and modules are conducted by means of a communication mechanism “Mailer” which is provided by the micro-kernel. At the same time, the modules that provide the operating system functions control the execution of application programs, by indirectly invoking the “Scheduler” in the micro-kernel via an interface which also is provided by the micro-kernel.
Referring now to
FIG. 14
, in a nano-kernel-type operating system, only a context switch mechanism that undertakes switching of contexts is extracted from the contents of a micro-kernel. The extracted context switch mechanism forms a nano-kernel.
Thus, in the nano-kernel-type operating system, the context switch mechanism that has dependency on the type of CPU and so forth is extracted and abstracted. This offers greater ease of programming, as well as higher kernel mobility.
In order to obtain enhanced versatility of operating systems, as well as higher kernel mobility and greater ease of programming, a micro-kernel-type operating system is preferred to a fat-kernel-type operating system, and a nano-kernel-type operating system is preferred to a micro-kernel-type operating system.
A micro- or nano-kernel-type operating system, however, requires a large number of context switches. This is because the communication mechanism and the scheduler of the micro-kernel have to be invoked each time of execution of any of execution entities such as the application programs which are operated on the operating system, objects which provide functions of the operating system, and so forth. Consequently, overall performance of the micro- or nano-kernel-type operating system is inferior to that of fat-kernel-type operating system.
The operating system employing a nano-kernel system requires a context switch even for the purpose of calling the communication mechanism or the scheduler. This type of operating system, therefore, further increases overheads of cost due to the use of greater number of context switches beyond the cost incurred in the micro-kernel-type operating system.
Thus, the use of a nano-kernel undesirably impairs the performance of the entire system due to increase in the number of the context switches. A solution to this problem might be to suppress invocation of the scheduler when context switch is performed. A mere suppression of invocation of the scheduler, however, hampers the schedule management and, hence, the system operation.
More specifically, omission of a scheduler invocation causes the scheduler to fail to receive information necessary for schedule management, resulting in discordance between the actual system status and the status understood by the scheduler. Consequently, the scheduler is disabled to perform appropriate schedule management. Omission of a scheduler invocation also poses the following problem. In general, when the queue in a thread under the schedule control by a scheduler is changed, the scheduler performs rescheduling such that processings of higher priorities are executed preferentially. Such rescheduling is not performed when the invocation the scheduler is omitted. Processings of higher priorities, therefore, may be delayed undesirably.
SUMMARY OF THE INVENTION
Accordingly, an object of the present invention is to provide a data processing method employing a nano-kernel, wherein the number of calls for a scheduler is minimized without impairing operation of a system which adopts this method. It is also an object of the present invention to provide a recording medium containing a program that implements the data processing method, as well as a data processing apparatus employing such a recording medium.
To these ends, according to one aspect of the present invention, there is provided a data processing method in which, when a context switch has occurred to switch the thread to be executed, the history of the context switch is recorded. Then, when a scheduler for controlling the execution sequence of threads is invoked, a queue managed by the scheduler is updated tracing back the recorded history of the context switch.
Thus, in the data processing method of the present invention, a queue is updated tracing back the record of context switch history when a scheduler is invoked. The scheduler, therefore, can correctly manage the schedule even if any context switch has been performed without invoking the scheduler.
The updating may be performed by setting a predetermined flag on a thread that causes a context switch which requires alteration of sequence in the queue, and invoking, in response to an occurrence of a new context switch, the scheduler to alter the sequence in the queue when the thread that has caused the new context switch bears the flag. This ensures that sequence in the queue is re-scheduled at appropriate timings, thus eliminating inconvenience such as delaying of a processing having a high priority.
The setting of the flag may be conducted such that the thread on which the flag is set differs according to the type of the invocation of the scheduler. This ensures that re-scheduling in the queue is executed at timings th
Banankhah Majid A.
Frommer William S.
Frommer & Lawrence & Haug LLP
Sony Corporation
LandOfFree
Data processing method and apparatus and recording medium,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processing method and apparatus and recording medium,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing method and apparatus and recording medium,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3277637