Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-04-23
2003-05-06
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
06560628
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a scheduling apparatus for an operating system which is capable of time-sharing processing a plurality of executable subjects, a method for the scheduling, and a recording medium in which an operating system capable of time-sharing processing a plurality of executable subjects is stored.
BACKGROUND OF THE INVENTION
In a system which can run a number of executable subjects concurrently in time-sharing mode, the executable subjects are scheduled in order of priority levels attributed to the executable subjects respectively. More particularly, the executable subjects are queued in a wait queue depending on their priority levels so that the executable subject of the highest priority is executed first, and can thus be handled by a CPU (central processing unit) in the order of their priority levels. The executable subject may be a process, a task, a thread, or the like and in this specification, is illustrated as a thread. The system in which the executable subject is a thread is hence called a multi-thread system.
In such a multi-thread system, the order of importance of threads is defined by their priority levels which have been determined, e.g. when the threads were produced. The order is not limited to precedence for execution of a thread but, for example in time-slice scheduling, may be priority for a time slice of the processing time of a CPU imparted to a thread. In another case, the priority of a thread may be dynamically weighted with relation to the time consumption in the system and the processing time required for the thread.
With the use of an algorithm for scheduling in order of the priority, a drawback known as priority inversion may arise in the exclusive controlling of access to common resources. Such priority inversion is now explained referring to FIG.
1
.
FIG. 1
is a diagram showing a typical attitude of the priority inversion. The priority inversion commonly occurs when a higher priority thread A enters a critical section CS
1
. It is noted that the critical section CS
1
contains a resource commonly used by the thread A and a thread C.
It is assumed, as shown in
FIG. 1
, that when the thread C has entered the critical section CS
1
, the higher priority thread A is turned to its ready state. The execution of the thread C is thus interrupted and the execution of the thread A is started. However, because the thread C is present in the critical section CS
1
, the thread A has to wait until the thread C leaves from the critical section CS
1
. Accordingly, the thread A is in its wait state and, then, the execution of the thread C is started.
Under this condition, when a thread B of which the priority is between those of the thread A and the thread C is turned to its ready state before the thread C leaves from the critical section A, the priority inversion occurs. More specifically, even while the higher priority thread A is in its wait state, the execution of the thread B which is lower in the priority than the thread A is started. As the middle priority thread B has been turned to its ready state, the execution of the thread C is interrupted and the execution of the middle priority thread B is started. At the time, the thread A is still in its wait state. Since the relation between the thread A and the thread B is not defined except their priorities, the thread A will hardly presume how long its wait state lasts before its execution is resumed.
With the algorithm for scheduling in order of priority, such priority inversion may substantially occur causing a higher priority thread to wait for the completion of the execution of a lower priority thread. Also, when the priority inversion has once occurred, the duration of interruption of the execution of the higher priority thread will hardly be estimated. Failure of estimating the interruption time for a higher priority thread is critical for a real-time system (that is irresponsible if a process is not finished within a specific length of time).
For eliminating the drawback of priority inversion, priority inheritance schemes have been introduced (such as “Priority Inheritance Protocols: An Approach to Real-time Synchronization” by Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky, Technical Report CMU-CS-87-181, the Computer Science Department of Carnegie Mellon University, November 1987). The priority inheritance scheme is designed in which when a higher priority thread is turned to its wait state due to the presence of a lower priority thread, the lower priority thread inherits the priority level of the higher priority thread.
FIG. 2
illustrates a scenario, similar to that of
FIG. 1
, except for a priority inheritance scheme is employed. With the priority inheritance scheme, when the execution of a thread C is started with a thread A being in the wait state, the priority level of the thread C is changed to a level equal to the priority level of the thread A. As a result, interruption of the execution of the thread C by the execution of a thread (for example, the thread B) of which the priority level is lower than that of the thread A will be prevented before the thread C leaves from a critical section CS
1
.
The priority inheritance scheme allows the thread C to be scheduled at the priority level of the thread A before it leaves from the critical section CS
1
. Accordingly, the waiting time before the thread A is allowed to enter the critical section CS
1
is bounded within a period required for the thread C occupying the critical section CS
1
. This permits an estimation of the interruption period during which the execution of the higher priority thread A is suspended.
To implement the above described priority inheritance scheme, the following procedure has to be performed. It is noted that this procedure is explained for a case that the execution of the higher priority thread A is interrupted until the lower priority thread C explicitly leaves from the critical section CS
1
.
First, as it has been judged that the thread A has to wait before the thread C leaves from the critical section CS
1
, i.e. the thread A is turned to its wait state, the thread A is dequeued from a wait queue. Then, the priority level of the thread C is temporarily changed to a level equal to the priority level of the thread A and the thread C is queued in the wait queue according to its priority level. The threads queued in the wait queue are performed by a CPU in order of the priority levels. When the thread C is called, its execution is started. In case that the processing time imparted to the thread C ends up during the execution, the thread C is queued again in the wait queue according to its changed priority level (equal to the priority level of the thread A).
When the wait state of the thread A is resolved (i.e. the thread C has left from the critical section CS
1
), the priority level of the thread C is turned back to its original lower level and the thread C is queued in the wait queue according to its original lower priority level. Simultaneously, the execution of the thread A becomes ready and queued back in the wait queue.
By following the foregoing procedure, the priority inheritance scheme shown in
FIG. 2
is implemented where the interruption of the execution of the thread C by a thread (for example, the thread B) of which the priority level is lower than that of the thread A can be avoided before the thread C leaves out from the critical section CS
1
.
In a conventional scheduling system, the location in the wait queue of a thread to be queued is determined by its priority level at the time. Because the priority level is changed dynamically and frequently in the priority inheritance scheme, it is necessary to modify the wait queue at short intervals of time. Therefore, the use of the priority inheritance scheme requires modification or rescheduling of the wait queue to respond to the dynamic change of the priority level, hence resulting in increase of the overhead.
More particularly, the priority inheritance scheme is effective to eliminate the drawback of priority
Banankhah Majid A.
Frommer William S.
Frommer & Lawrence & Haug LLP
Mahr Hans R.
Sony Corporation
LandOfFree
Apparatus, method, and recording medium for scheduling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus, method, and recording medium for scheduling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus, method, and recording medium for scheduling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3042495