Multi-processor scheduling kernel

• US 6,269,391 B1
• Filed: 06/19/1997
• Issued: 07/31/2001
• Est. Priority Date: 02/24/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Gillespie, Bruce K.
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US08/878,632
• Time in Patent Office: 1,503 Days
• Field of Search: 709/100, 709/101, 709/102, 709/103, 709/104, 709/108, 709/105, 709/203, 709/207, 709/223, 709/218, 709/249
• US Class Current: 718/100
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A scheduling kernel provides fair share scheduling of several virtual machines by a multi-processor scheduling module scheduling the virtual machines across the several processors of the multi-processor. A virtual machine scheduling module schedules threads of a virtual machine, and provides an independent scheduling policy for a virtual machine. Execution exclusion sets may be created and enforced by an execution exclusion set module to limit execution to a single thread at a time out of any particular execution exclusion set of threads.

Claims

1. A multi-processor comprising:

a memory device storing data structures for supporting execution of a multi-processor, the data structures including;

a multi-processor scheduling kernel executable by the multi-processor, and

a plurality of virtual machines, each virtual machine comprising a group of threads to be executed by a processor of the multi-processor; and

a plurality of processors, operably connected to the memory device, each processor being programmed to execute a selected thread and to execute an instance of the scheduling kernel to schedule the execution of the selected thread, the instance of the scheduling kernel comprising;

a multi-processor scheduling module for providing to the processor an order of execution for the each virtual machine, and

a virtual machine scheduling module for providing to the multi-processor scheduling module, an order of execution for each thread of the group of threads.

2. The apparatus of claim 1, wherein the scheduling kernel is programmed to make a second scheduling decision corresponding to a second thread, logically noncontiguous with a first thread, which second scheduling decision depends upon a first scheduling decision previously made by the scheduling kernel and corresponding to the first thread.

3. The apparatus of claim 2, wherein the first thread and second thread are members of an aversion group for which scheduling the first thread for execution decreases the possibility of execution of the second thread simultaneously therewith.

4. The apparatus of claim 2, wherein the first thread and second thread are members of an aversion group for which scheduling the first thread for execution precludes execution of the second thread simultaneously therewith.

5. The apparatus of claim 2, wherein the first thread and second thread are members of an aversion group for which scheduling the first thread for execution on a processor decreases the possibility of a subsequent execution of the second thread on the same processor.

6. The apparatus of claim 2, wherein the first thread and second thread are members of an affinity group for which scheduling the first thread for execution increases the possibility of execution of the second thread simultaneously therewith.

7. The apparatus of claim 2, wherein the first thread and second thread are members of an affinity group for which scheduling the first thread for execution on a processor increases the probability of a subsequent execution of the second thread on the same processor.

8. The apparatus of claim 2, wherein the first thread and second thread are members of an aversion group constituting an exclusion group for which scheduling the first thread for execution precludes execution of the second thread simultaneously therewith.

9. The apparatus of claim 2, wherein the first thread and second thread are members of an aversion group constituting an exclusion group for which scheduling the first thread for execution on a processor precludes a subsequent execution of the second thread on the same processor.

10. The apparatus of claim 1, wherein the data structures further comprise execution groups for which a second scheduling decision made by the scheduling kernel and corresponding to one thread in a one execution group depends upon another scheduling decision made by the scheduling kernel and corresponding to another thread in the same execution group.

11. The apparatus of claim 1, wherein:

the data structures further comprise execution groups comprising group threads for which a second scheduling decision made by the scheduling kernel and corresponding to a second execution group depends upon a first scheduling decision made by the scheduling kernel and corresponding to a thread in the first execution group.

12. The apparatus of claim 1, wherein the scheduling kernel is programmed to make a second scheduling decision controlling scheduling of an execution of a second thread, which second scheduling decision depends upon a first scheduling decision made by the scheduling kernel and controlling scheduling of an execution of a first thread.

13. The apparatus of claim 12, wherein:

the scheduling kernel further comprises an execution set module, executable by the multi-processor to make the first and second scheduling decisions; and

the data structures further comprise an execution set for defining the first and second scheduling decisions with respect to the first and second threads.

14. The apparatus of claim 13, wherein the first thread is included in the execution set.

15. The apparatus of claim 14, wherein the second thread is included in the execution set.

16. The apparatus of claim 13, further comprising a plurality of execution sets.

17. The apparatus of claim 1, wherein the multi-processor scheduling module further comprises a scheduling executable for providing a fair-share scheduling process between a plurality of virtual machines.

18. The apparatus of claim 17, wherein the fair-share scheduling process comprises an executable for comparing one time corresponding to all threads of one virtual machine to another time corresponding to all threads of another virtual machine.

19. The apparatus of claim 18, wherein the one time and the other time correspond to latency data reflecting respective wait times corresponding to respective ready threads in the respective one and another virtual machines.

20. The apparatus of claim 17, wherein the fair-share scheduling process further comprises an executable for comparing one progress of execution of a first thread with another progress of execution of another thread.

21. The apparatus of claim 20, wherein the one and the other progress reflect execution times and comparative importance of the respective one and another threads.

22. The apparatus of claim 17, wherein the fair-share scheduling process comprises an executable for comparing one time corresponding to one processor to another time corresponding to another processor.

23. The apparatus of claim 22, wherein the one time and the other time correspond to latency data corresponding to the respective one and another processors.

24. The apparatus of claim 1, wherein the data structures further comprise global data, corresponding to a virtual machine of the plurality of virtual machines, and CPU-specific data corresponding to a processor of the multi-processor.

25. The apparatus of claim 1, wherein the multi-processor scheduling module further comprises:

latency data corresponding to a latency of execution of a ready thread;

a latency executable for acquiring the latency data; and

a loading executable for using the latency data to adjust the scheduling of processors in the multi-processor.

26. The apparatus of claim 1, wherein the data structures further comprise an independent scheduling policy and the virtual machine scheduling module is programmed to execute in accordance therewith to schedule the virtual machines.

27. A method for fair-share scheduling of a multi-processor, the method comprising:

providing a multi-processor;

providing a multi-processor scheduling module, executable by the multi-processor for scheduling execution, by the multi-processor, of threads;

providing fair-share scheduling information for controlling scheduling of the threads; and

executing the multi-processor scheduling module to schedule the threads according to the fair-share scheduling information.

28. A method for scheduling virtual machines on a multi-processor, the method comprising:

providing a multi-processor;

providing a plurality of virtual machines, each comprising threads executable by the multi-processor;

providing a virtual machine scheduling module, executable by the multi-processor for scheduling the plurality of virtual machines for execution;

providing a multi-processor scheduling module, executable by the multi-processor for scheduling execution, by the multi-processor, of the threads;

executing the virtual machine scheduling module to schedule the plurality of virtual machines; and

executing the multi-processor scheduling module to schedule the threads within each of the virtual machines.

29. The method of claim 28, wherein scheduling the plurality of virtual machines further comprises selecting a selected virtual machine from the plurality of virtual machines.

30. The method of claim 29, wherein scheduling the threads further comprises controlling a context switch between a rising thread and a falling thread selected from the threads of the selected virtual machine.

31. The method of claim 28, wherein scheduling the plurality of virtual machines further comprises ordering the plurality of virtual machines according to a fair-share scheduling policy.

32. The method of claim 28, further comprising providing, prior to executing the multi-processor scheduling module, an independent scheduling policy corresponding to a virtual machine of the plurality of virtual machines for controlling the multi-processor scheduling module in accordance therewith during execution of the threads corresponding to the virtual machine.

33. The method of claim 32, further comprising providing a plurality of independent scheduling policies corresponding, respectively, to the plurality of virtual machines.

34. The method of claim 28, further comprising:

providing an execution set comprising group threads;

providing an execution set module for controlling execution of the threads of the virtual machines in accordance with a relationship between the threads and the group threads.

35. The method of claim 34, wherein the execution set comprises an execution exclusion set.

36. The method of claim 35, wherein the execution set comprises an affinity group of threads.

37. The method of claim 34, wherein the execution set comprises an aversion group of threads.

38. The method of claim 34, wherein a selected thread, selected for execution from a selected virtual machine, is selected from within the execution group due to a status of the selected thread as a group thread.

39. The method of claim 34, wherein a selected thread of a selected virtual machine is selected from outside the execution group due to a status of the selected thread as not a group thread.