Computer system process scheduler determining and executing processes based upon changeable priorities

• US 6,668,269 B1
• Filed: 12/29/1999
• Issued: 12/23/2003
• Est. Priority Date: 08/11/1995
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Kamada, Jun, Ono, Etsuo, Yuhara, Masanobu
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US09/474,100
• Time in Patent Office: 1,455 Days
• Field of Search: 709/100, 709/101, 709/102, 709/103, 709/104, 709/105, 709/106, 709/108
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A computer-system fixed-priority process scheduler that is supported by an operating system (OS) and establishes fixed priorities respectively corresponding to a plurality of processes to be scheduled. Further, the priorities can be changed by designation from the user processes. The process scheduler allocates a central processing unit (CPU) to executable ones of the processes in the descending order of the priorities thereof. Moreover, a user-level process scheduler is provided in a fixed-priority process scheduler space, namely, in a real-time class process scheduler space. The user-level process scheduler has a first priority of a real time class. Furthermore, the user-level process scheduler performs the scheduling of a group of other user processes, which have priorities lower than the first priority, and causes the group of such user processes to operate or run. Namely, the user-level process scheduler determines the allocation of the CPU to such user processes and requests the OS to execute such user processes.

Claims

1. A computer-system process scheduler, which is supported by an operating system and establishes fixed priorities respectively corresponding to a plurality of processes to be scheduled, the priorities being able to be changed by designation sent from a user process, the computer process scheduler being adapted to allocate a CPU to executable ones of the processes in a descending order of the priorities thereof and to cause the process, to which the CPU is allocated, to operate, the computer-system process scheduler comprising:

a user-level process scheduler belonging to a user process and having a first priority and being operative to determine allocation of the CPU thereto and to request the operating system to execute the user process.

2. The computer-system process scheduler according to claim 1, wherein the user-level process scheduler is linked to each of a plurality of user processes having the first priority and is operative to schedule the user process corresponding thereto and to cause a corresponding one of the user processes to operate.

3. The computer-system process scheduler according to claim 1, wherein the user-level process scheduler having the first priority provides a user-level process scheduler having a second priority in a group of user processes scheduled by the user-level process scheduler having the first priority and is operative to hierarchically schedule other groups of user processes from those of high-order groups to those of low-order groups and cause the groups of the user processes to operate.

4. The computer-system process scheduler according to claim 1, which further comprises a plurality of user schedulers having the first priority, each of which individually schedules a corresponding group of user processes and-causes the corresponding group of user processes to operate.

5. The computer-system process scheduler according to claim 1, wherein the control portion of said user-level process scheduler comprises:

a process execution control portion requesting the operating system to execute, suspend or resume a designated user process, in accordance with an instruction issued from the class change instruction portion according to a demand made by a user process, or in accordance with an instruction issued from the process execution instructing portion by referring to the process management table;

a process priority control portion requesting the operating system to execute, suspend or resume a user process by changing a priority of a designated user process into the first priority and executing the user process and suspending another user process, whose priority is changed into a low priority, in accordance with an instruction issued from the class change instruction portion according to a demand made by a user process, or in accordance with an instruction issued from the process execution instructing portion by referring to the process management table; and

a class change control portion requesting the operating system to execute, suspend or resume a designated user process, in accordance with an instruction issued from the class change instruction portion according to a demand made by a user process, or in accordance with an instruction issued from the process execution instructing portion by referring to the process management table, in the case that the user-level process scheduler according to a process state, in addition to and differently from a real time class having a fixed priority of a high priority range.

6. The computer-system process scheduler according to claim 5, wherein the class change instructing portion refers to the process management table and obtains a total of CPU time required by a group of user processes, which are currently in an admitted state, in response to a demand for admission, which includes designation of CPU utilization time of a user process, wherein if a total of the required CPU time is equal to or less than a predetermined time, the class change instructing portion permits the user process to admit the group, wherein if the total of the required CPU time exceeds the predetermined time, the class change instructing portion rejects the demand for admission.

7. The computer-system process scheduler according to claim 5, wherein in case of permitting a user process to admit, the class change instructing portion instructs the process execution control portion to change a state of the user process, which has made the demand for admission, into a suspended state, and further instructs the class change control portion to change a class of the user process from a time sharing class, which has a dynamic priority of a low priority range, into a real time class having a fixed priority of a high priority range, and furthermore instructs the process priority control portion to change a priority of the user process into a second priority, wherein after the user process is registered in the process management table, the class change instructing portion posts permission for admission to the user process.

8. The computer-system process scheduler according to claim 5, wherein in case of permitting a user process to admit, the class change instructing portion instructs the class change control portion to change a class of the user process into a real time class, and further instructs the process priority control portion to change a priority of the user process into a priority which is lower than the first priority, wherein after the user process is registered in the process management table, the class change instructing portion posts permission for admission to the user process.

9. The computer-system process scheduler according to claim 5, wherein in case of permitting a user process to admit, the class change instructing portion instructs the class change control portion to change a class of the user process into a time sharing class, wherein after the user process is registered in the process management table, the class change instructing portion posts permission for admission to the user process.

10. The computer-system process scheduler according to claim 5, wherein in response to a demand for exit, which has been made by a user process, the class change instructing portion deletes the user process from the process management table and instructs the class change control portion to change a class of the user process, which has made the demand for exit, into a time sharing class.

11. The computer-system process scheduler according to claim 5, wherein in response to a notice from a user process, the class change instructing portion handles admission and exit of a new user process.

12. The computer-system process scheduler according to claim 5, wherein in response to a notice from the operating system, the class change instructing portion handles admission and exit of a new user process.

13. The computer-system process scheduler according to claim 5, wherein the user-level process scheduler receives information, which concerns a change request, to be given to the process execution control portion, the class change control portion and the process priority control portion, and further receives a request from an application program, through a library linked to the application program, and thereafter requests the operating system to perform a change in the user process.

14. The computer-system process scheduler according to claim 5, wherein scheduling specifications of a change request to be given to the process execution control portion, the class change control portion and the process priority control portion are established by a user process, wherein a change in the user process is requested to the operating system by posting a change request to the user-level process scheduler according to the scheduling specifications of the user process.

15. The computer-system process scheduler according to claim 1, wherein a user process to be scheduled by the user-level process scheduler consists of a plurality of threads, wherein the plurality of threads are scheduled by a thread scheduler which is a part of the user process.

16. The computer-system process scheduler according to claim 1, wherein when allocating CPU time to one or more user processes registered in a process management table, the user-level process scheduler corresponding to a process user requests the operating system to execute or suspend a user process, or change a priority of a user process or change a class, to which a user process belongs, in such a manner that only one user process is present in a period of time during which the CPU is allocated to a user process.

17. The computer-system process scheduler according to claim 1, wherein when allocating CPU time to one or more user processes registered in a process management table, the user-level process scheduler corresponding to a process user requests the operating system to execute or suspend a user process, or change a priority of a user process or change a class, to which a user process belongs, in such a manner that a plurality of user processes are present in a time sharing manner in a period of time during which the CPU is allocated to user processes.

18. The computer-system process scheduler according to claim 1, wherein the user-level process scheduler ensures operations of a plurality of user processes in a constant time by allocating CPU time to the plurality of user processes and the user-level process scheduler itself serially in the constant time.

19. The computer-system process scheduler according to claim 1, wherein the user-level process scheduler ensures operations of a plurality of user processes by setting a constant period and allocating CPU time to the plurality of user processes and the user-level process scheduler itself serially in each constant period.

20. The computer-system process scheduler according to claim 19, wherein in case that operating periods of a plurality of user processes are different from one another, the user-level process scheduler ensures operations of a plurality of user processes by determining a scheduling period from a combination of the different operating periods, and allocating CPU time to the plurality of user processes serially in the scheduling period.

21. The computer-system process scheduler according to claim 1, wherein when a ratio of total CPU time, which is allocated to a plurality of user processes, to a constant time or to a constant period is equal to or less than a predetermined value, the user-level process scheduler permits allocation of CPU time to another user process, wherein when the ratio exceeds the predetermined value, the user-level process scheduler rejects allocation of CPU time to another user process.

22. The computer-system process scheduler according to claim 1, wherein in case that CPU time is allocated to a user process in a constant time or a constant period, the user-level process scheduler allocates continuous CPU time to a user process.

23. The computer-system process scheduler according to claim 1, wherein in case that CPU time is allocated to a plurality of user processes in a constant time or a constant period, the user-level process scheduler allocates CPU time to the plurality of user processes, respectively, by dividing each CPU time to be allotted to corresponding one of the plurality of user processes.

24. The computer-system process scheduler according to claim 1, wherein in case that user processes registered in a process management table include a user process belonging to a real time class having a fixed priority of a high priority range and further include a user process belonging to a time sharing class, in which a priority of a low priority range is dynamically changed, the use-level process scheduler limits allocation of CPU time to the user process belonging to the real time class and allocates CPU time to the user process belonging to the time sharing class.

25. The computer-system process scheduler according to claim 1, wherein the user-level process scheduler detects suspension of a user process and then enables another user process to operate.

26. The computer-system process scheduler according to claim 1, wherein when allocating CPU time to a user process, the user-level process scheduler provides a blocking detection process, which can be executed at a same priority as of the user process, in addition to the user process, wherein when the user process is blocked, the user-level process scheduler allocates CPU time to the blocking detection process and causes the blocking detection process to send a notice representing an occurrence of blocking of the user process to the user-level process scheduler, wherein the user-level process scheduler recognizes from the notice that the user process is suspended, and enables another user process to be executed.

27. The computer-system process scheduler according to claim 1, wherein when allocating CPU time to a user process, the user-level process scheduler provides a blocking detection process, which can be executed at a low priority, in addition to the user process, wherein when the user process is blocked, the user-level process scheduler allocates CPU time to the blocking detection process and causes the blocking detection process to send a notice representing an occurrence of blocking of the user process to the user-level process scheduler, wherein the user-level process scheduler recognizes from the notice that the user process is suspended, and enables another user process to be executed.

28. The computer-system process scheduler according to claim 1, wherein the user-level process scheduler detects that a user process being blocked becomes put into a ready state, and causes the user process to operate.

29. The computer-system process scheduler according to claim 1, wherein the user-level process scheduler detects a notice, which is issued from the operating system and indicates an occurrence of blocking a user process, or a notice indicating resumption of the user process by recovering the blocked user process, and then executes or suspends another user process.