Periodic process scheduling method

• US 5,944,778 A
• Filed: 03/26/1997
• Issued: 08/31/1999
• Est. Priority Date: 03/28/1996
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Nakano, Takahiro, Iwasaki, Masaaki, Takeuchi, Tadashi, Nakahara, Masahiko
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US08/824,338
• Time in Patent Office: 888 Days
• Field of Search: 709/100, 709/102, 709/103, 709/106
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/484 Precedence
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: H04L 69/32 Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A scheduling method of a periodic process of a computer system for keeping the execution interval of each process group constant as far as possible in the case where a plurality of process groups including periodically executed processes are executed in parallel. If a group master process of each process group specifies a wakeup interval period and a required CPU time per period and requests allocation of a CPU time, then a CPU allocation time of a specified process group is secured so as not to collide with a CPU allocation time of another process group, and a scheduling table is created so as to maintain the specified wakeup interval period. In response to arrival of time when one of the process groups should be waked up, a kernel process or a scheduler conducts wakeup by changing execution priority of a process belonging to this process group to highest priority ("raised") in the system, and thereafter maintains the highest priority for CPU allocation time consecutively allocated.

Claims

1. A periodic process scheduling method of a computer system, said computer system including a plurality of process groups, each of said process groups including at least one periodically executed process, said plurality of process groups being executed in parallel, said periodic process scheduling method comprising the steps of:

specifying a wakeup interval period and a required CPU time per period for each of said process groups;

securing a CPU allocation time so as to prevent collision between a CPU allocation time of a specified process group and a CPU allocation time of another specified process group, and adjusting said CPU allocation time and said wakeup period so as to maintain the wakeup interval period of each of said specified process groups;

creating a table for registering therein an order of said process groups to which CPU time is allocated by utilizing a time slot as a unit;

selecting a process group so as to allocate time slots to process groups in order starting from a process group having a shorter wakeup period;

extracting adjacent empty time slots within the wakeup interval period of the selected process group;

responding to the existence of adjacent empty time slots having a size of at least a required CPU time, obtaining, from adjacent empty time slots corresponding to at least the required CPU time and having a minimum size, adjacent empty time slots corresponding to the required CPU time beginning from the head thereof, and allocating the obtained adjacent empty time slots to the selected process group; and

responding to the nonexistence of adjacent empty time slots having a size of at least a required CPU time, allocating all time slots belonging to adjacent empty time slots having a maximum size to the selected process group, and allocating a remaining time equivalent to the required CPU time minus the allocated time slots to said process group by using the previous responding step and the present responding step.

2. A method for waking up a process scheduled according to the periodic scheduling method according to claim 1, further comprising the steps of:

responding to the arrival of the wakeup time of one of said process groups;

performing wakeup by changing the execution priority of a process belonging to said process group to a highest priority in a system; and

maintaining the highest priority for CPU allocation time consecutively allocated.

3. A process wakeup method according to claim 2, further comprising the steps of:

changing execution priority of said process to a lowest priority ("depressed") in the system upon lapse of the CPU allocation time consecutively allocated;

responding to an order for giving priority of a first process to a second process belonging to same process as the first process before lapse of said CPU allocation time consecutively allocated; and

performing wakeup by changing the execution priority of the first process from the highest priority ("raised") in the system to lowest priority and changing execution priority of the second process to the highest priority.

4. A process wakeup method according to claim 2, further comprising the steps of:

responding to the lapse of the CPU allocation time consecutively allocated and consumption of said required CPU time;

changing execution priority of a process waked up from the highest priority to reference priority; and

notifying said process of timeout.

5. A process wakeup method according to claim 2, further comprising the steps of:

responding to the lapse of the CPU allocation time consecutively allocated;

waking up a single control process;

waking up said process group; and

waking up a process belonging to a process group supplied with next consecutive CPU allocation time by using said control process.

6. A process wakeup method according to claim 2, wherein processing to be conducted between detection of a time for waking up one of said process groups and waking up a process belonging to said process group is executed by a single process.

7. A process wakeup method according to claim 2, further comprising the steps of:

responding to an occurrence of an asynchronous event requiring reception of information including arrival of a network packet during execution of a process having the highest priority in a system;

immediately suspending execution of the process running with the highest priority;

securing an information receiving buffer;

preparing for reception of the information;

resuming the execution of the process suspended in execution thereof; and

referring to received information and performing processing by using a periodically waked up process.

8. A computer-readable recording medium for storing a program for ordering periodic process scheduling of a computer system, said computer system including a plurality of process groups, each of said process groups including at least one periodically executed process, said plurality of process groups being executed in parallel, said program comprising:

program means for specifying a wakeup interval period and a required CPU time per period for each of the process groups;

program means for securing a CPU allocation time so as to prevent collision between a CPU allocation time of a specified process group and a CPU allocation time of another process group, and adjusting said CPU allocation time and said wakeup period so as to maintain the wakeup interval period of each of specified process groups;

registering means for creating a table to register therein an order of said process groups to which CPU time is allocated by utilizing a time slot as a unit;

selecting means for selecting a process group so as to allocate time slots to process groups in order starting from a process group having a shorter wakeup period;

extracting means for extracting adjacent empty time slots within the wakeup interval period of the selected process group;

means for responding to the existence of adjacent empty time slots having a size of at least a required CPU time, obtaining, from adjacent empty time slots corresponding to at least the required CPU time and having a minimum size, adjacent empty time slots corresponding to the required CPU time beginning from head thereof, and allocating the obtained adjacent empty time slots to the selected process group; and

means for responding to the nonexistence of adjacent empty time slots having a size of at least a required CPU time, allocating all time slots belonging to adjacent empty time slots having a maximum size to the selected process group, and allocating a remaining time equivalent to the required CPU time minus the allocated time slots to said process group by using the previous responding means and the present responding means.

9. A recording medium according to claim 8, wherein said recording medium further comprises:

program means responsive to arrival of the wakeup time for one of said process groups, to perform wakeup by changing the execution priority of a process belonging to said process group to a highest priority ("raised") in a system;

program means for maintaining the highest priority for CPU allocation time consecutively allocated, and changing the execution priority of said process to a lowest priority ("depressed") in the system upon lapse of the CPU allocation time consecutively allocated;

program means responsive to the lapse of the CPU allocation time consecutively allocated, to wakeup a single control process waking up said process group, and wakeup a process belonging to a process group supplied with next consecutive CPU allocation time by using said control process;

means for responding to an order for giving priority of a first process to a second process belonging to same process as the first process before lapse of said CPU allocation time consecutively allocated; and

means for performing wakeup by changing the execution priority of the first process from the highest priority ("raised") in the system to lowest priority and changing execution priority of the second process to the highest priority.