Apparatus, method, and recording medium for scheduling execution using time slot data

• US 6,560,628 B1
• Filed: 04/23/1999
• Issued: 05/06/2003
• Est. Priority Date: 04/27/1998
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Sony Corporation (Sony Group Corp.)
• Inventors: Murata, Seiji
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US09/298,246
• Time in Patent Office: 1,474 Days
• Field of Search: 709/100, 709/101, 709/102, 709/103, 709/104, 709/105, 709/106, 709/107, 709/108
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A scheduling method for use with a multi-thread system which is capable of time-sharing processing a plurality of threads is provided which can avoid the drawback of priority inversion, minimize the modification of a wait queue, and ensure the optimum use of the processing time of a CPU.

According to the present invention, a time slot data is assigned to each thread and the scheduling is carried out on the basis of the time slot data. As a processing time is imparted to the time slot data, the execution of the thread to which the time slot data is assigned is started. In case that a higher priority thread has to wait for the completion of the execution of a lower priority thread, the time slot data assigned to the higher priority thread is handled as a time slot data of the lower priority thread, hence allowing the execution of the lower priority thread to be started upon a processing time imparted to the time slot data.

Claims

1. A scheduling apparatus for an operating system capable of time-sharing processing a plurality of executable subjects, comprising:

means for storing a time slot data assigned to each of the executable subjects as an object to be scheduled;

a scheduler for imparting a processing time to the time slot data and conducting time-sharing scheduling;

means for executing the executable subject specified by the time slot data to which the processing time is imparted;

means for assigning the time slot data specifying a first executable subject to a second executable subject when said first executable subject has a higher priority level than said second executable subject and said first executable subject has to wait for completion of the execution of said second executable subject; and

means for re-assigning the time slot data specifying the first executable subject to said first executable subject when the execution of said second executable subject is completed.

2. A scheduling apparatus according to claim 1, wherein the time slot data includes link data which represents the executable subject to which the time slot data is assigned and wherein said scheduling apparatus further comprises:

means for shifting the executable subject specified by the link data of the time slot data from the higher priority executable subject to the lower priority executable subject when the time slot data specifying the higher priority executable subject is handled as a time slot data assigned to the lower priority executable subject.

3. A scheduling apparatus for an operating system capable of time-sharing processing a plurality of executable subjects having respective priority levels, comprising:

means for storing a time slot data assigned to each of the executable subjects as an object to be scheduled;

a scheduler for imparting a processing time to the time slot data and conducting time-sharing scheduling;

a ring buffer comprised of a plurality of wait queues, each having at least one time slot data allocatable thereto;

means for executing the executable subject specified by the time slot data to which the processing time is imparted;

positioning means for determining one of the wait queues in the ring buffer to which the time slot data is allocated as a function of the priority level of the executable subject specified by the time slot data;

means operable, when a time slot data is to be allocated to the determined wait queue in the ring buffer, to allocate the time slot data to the last of the wait queues in the ring buffer; and

means for imparting the processing time to the time slot data located at the top of the wait queue in the ring buffer.

4. A scheduling apparatus according to claim 3, wherein the time slot data includes data representing the priority level of the executable subject specified by the time slot data, and

the positioning means is operable, when the time slot data of the executable subject which has consumed the processing time imparted to it is allocatable to the wait queue in the ring buffer, to allocate the time slot data to a wait queue in the ring buffer which is distanced from the wait queue where the time slot data currently is saved, by a difference between one less than the number of wait queues in the ring buffer and the priority level of the allocatable time slot data.

5. A scheduling method for use with an operating system capable of time-sharing processing a plurality of executable subjects, comprising the steps of:

imparting a processing time to a time slot data which is assigned to each of the executable subjects as an object to be scheduled and conducting time-sharing scheduling;

executing the executable subject specified by the time slot data to which the processing time is imparted;

assigning the time slot data specifying a first executable subject to a second executable subject when said first executable subject has a higher priority level than said second executable subject and said first executable subject has to wait for completion of the execution of said second executable subject; and

re-assigning the time slot data specifying the first executable subject to said first executable subject when the execution of said second executable subject is completed.

6. A scheduling method according to claim 5, wherein the time slot data includes link data which represents the executable subject to which the time slot data is assigned, and shifting the executable subject specified by the link data from the higher priority executable subject to the lower priority executable subject when the time slot data for the higher priority executable subject is handled as a time slot data assigned to the lower priority executable subject.

7. A scheduling method for use with an operating system capable of time-sharing processing a plurality of executable subjects having respective priority levels, comprising the steps of:

imparting a processing time to a time slot data which is assigned to each of the executable subjects as an object to be scheduled and conducting time-sharing scheduling;

executing the executable subject specified by the time slot data to which the processing time is imparted;

determining one of wait queues provided in a ring buffer to which the time slot data is allocated, as a function of the priority level of the executable subject specified by the time slot data;

allocating the time slot data to the last of the wait queues in the ring buffer when a time slot data is to be allocated to the determined wait queue in the ring buffer; and

imparting the processing time to the time slot data located at the top of the wait queue in the ring buffer.

8. A scheduling method according to claim 7, wherein the time slot data includes data representing the priority level of the executable subject, and when the time slot data of the executable subject which has consumed the processing time imparted to it is allocatable to the wait queue in the ring buffer, allocating the time slot data to a wait queue in the ring buffer which is distanced from the wait queue where the time slot data currently is saved, by a difference between one less than the number of wait queues in the ring buffer and the priority level of the allocatable time slot data.

9. A recording medium on which is recorded a data processing program for a computer operating system capable of time-sharing processing a plurality of executable subjects, said data processing program controlling the computer operating system to:

impart a processing time to a time slot data which is assigned to each of the executable subjects as an object to be scheduled and conducting time-sharing scheduling;

execute the executable subject specified by the time slot data to which the processing time is imparted;

assign the time slot data specifying a first executable subject to a second executable subject when said first executable subject has a higher priority level than said second executable subject and said first executable subject has to wait for completion of the execution of said second executable subject; and

re-assign the time slot data specifying the first executable subject to said first executable subject when the execution of said executable subject is completed.

10. A recording medium according to claim 9, wherein the time slot data includes link data which represents the executable subject to which the time slot data is assigned, and wherein the data processing program shifts the executable subject specified by the link data from the higher priority executable subject to the lower priority executable subject when the time slot data specifying the higher priority executable subject is handled as a time slot data assigned to the lower priority executable subject.

11. A recording medium on which is recorded a data processing program for a computer operating system capable of time-sharing processing a plurality of executable subjects, said data processing program controlling the computer operating system to:

impart a processing time to a time slot data which is assigned to each of the executable subjects as an object to be scheduled and conducting time-sharing scheduling;

execute the executable subject specified by the time slot data to which the processing time is imparted;

determine one of wait queues provided in a ring buffer to which the time slot data is allocated, as a function of the priority level of the executable subject specified by the time slot data;

allocate the time slot data to the last of the wait queues in the ring buffer when a time slot data is to be allocated to the determined wait queue in the ring buffer; and

impart the processing time to the time slot data located at the top of the wait queue in the ring buffer.

12. A recording medium according to claim 11, wherein the time slot data includes data representing the priority level of the executable subject, and when the time slot data of the executable subject which has consumed the processing time imparted to it is allocatable to the wait queue in the ring buffer, allocating the time slot data to a wait queue in the ring buffer which is distanced from the wait queue where the time slot data currently is saved, by a difference between one less than the number of wait queues in the ring buffer and the priority level of the allocatable time slot data.