Method and apparatus for sharing a time quantum

• US 6,272,517 B1
• Filed: 06/30/1998
• Issued: 08/07/2001
• Est. Priority Date: 10/31/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Yue, Kelvin K., Stein, Daniel A., Sebrée, Michael A.
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US09/107,690
• Time in Patent Office: 1,134 Days
• Field of Search: 709/100, 709/101, 709/102, 709/103, 709/104, 709/106, 709/107, 709/108, 709/328, 709/315, 709/317, 709/332, 710/260, 703/26, 703/27
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A method and apparatus for allowing a first thread to “share” its remaining time quantum with a second thread when the first thread is blocked. A thread may be blocked, for example, if it is waiting for a resource such as a data file or a lock. A thread may also be blocked if it is waiting for an event, such as a user keystroke. If there is a thread on the run queue that “owns” the resource needed by the consumer thread, the blocked consumer thread transfers its right to execute for a remaining time quantum to the owner thread, and the owner thread executes next. If the threads are in a same process, this transfer means that no process context switch is required, since the consumer thread and the owner thread are threads of the same process. In addition, this transfer means that the time before the resource becomes available to the blocked consumer thread will be short. Similarly, if a consumer thread is blocked to await an event, such as a user keystroke, the blocked consumer thread'"'"'s remaining time quantum are transferred to another thread in that is waiting on the run queue for its turn to execute. Again, if the threads are in a same process, this transfer avoids having to perform a context switch between processes.

Claims

1. A method of sharing a time quantum between threads, comprising the steps, performed by the data processing system, of:

determining that a first thread, which is currently being executed by a processor and which has an associated time quantum, is blocked;

determining a next thread to be executed by the processor; and

transferring unused time in the time quantum of the first thread to the next thread to be executed.

2. The method of claim 1, wherein the determining step includes the step of determining a next thread to be executed that is from the same process as the first thread.

3. The method of claim 1, wherein the determining step includes the step of determining a next thread to be executed that is from a different process than the first thread.

4. The method of claim 1, wherein the determining step includes the step of determining a next thread to be executed that is from a different process of a different user than the first thread.

5. The method of claim 1, wherein the transferring step includes the step of adding the unused time in the time quantum of the first thread to a time quantum of the next thread to execute.

6. The method of claim 1, wherein the transferring step includes the step of transferring the unused time in the time quantum of the first thread to a time quantum of the next thread to execute, in place of an original time quantum for the next thread to execute.

7. The method of claim 1,

wherein the first thread in the determining step is being executed by a first processor of a plurality of processors,

wherein the determining step determines a next thread to be executed by the first processor, and

wherein the transferring step transfers unused time in the time quantum of the first thread to the next thread to be executed by the first processor.

23. The method of claim 1, further comprising:

after transferring the unused time, causing the next thread to use at least a portion of the unused time when the next thread is being executed by the processor.

24. The method of claim 23, further comprising:

after causing the next thread to use at least a portion of the unused time, restarting the first thread and enabling the first thread to use any remaining unused time that was not used by the next thread.

8. A method of sharing a time quantum between a plurality of threads in a data processing system, comprising the steps, performed by the data processing system, of:

initially assigning a number of tickets to the plurality of threads;

assigning an initial priority to a thread of each of the plurality of processes in accordance with the number of tickets assigned to the threads; and

executing the respective threads of the plurality of processes in an order indicated by the tickets assigned to the plurality of threads, so that the proportion of execution time between any two of the threads is the same as the proportion between the number of tickets of the two processes associated with the threads, the execution step including the substeps of;

determining that a first thread, which is currently being executed and which has an associated time quantum, is blocked;

determining a next thread to execute; and

transferring unused time in the time quantum of the first thread to the next thread to execute.

9. The method of claim 8, wherein the data processing system includes a plurality of processors, and the data processing system has a plurality of processor slots;

wherein the executing step includes the step of determining whether there is an available processor slot; and

further including the step of placing a thread associated with a one of the plurality of processes on a ticket queue of the process, when there is no available processor slot, so that the thread waits on the ticket queue for an available processor slot.

10. The method of claim 8, wherein the data processing system includes a plurality of processors, and the data processing system has a plurality of processor slots;

wherein the executing step includes the step of determining whether there is an available processor slot; and

further including the step of placing a thread associated with a one of the plurality of processes onto a processor run queue when there is an available processor slot.

11. The method of claim 10, further including the step of calculating a priority of the thread in accordance with the number of tickets currently held by the thread'"'"'s process before the thread is placed on the run queue.

12. The method of claim 11, wherein the executing step includes the steps of:

decrementing a number of tickets of a one of the plurality of processes whose thread has just finished executing for a predetermined time period; and

if the number of tickets for the one process is equal to zero after the decrementing step, setting the number of tickets for the one process to the initially determined number of tickets for the one process.

13. The method of claim 11, wherein the executing step includes the steps of recalculating the number of tickets held by the process;

after the thread of the process has executed for the predetermined period of time.

14. The method of claim 11, wherein the executing step includes the steps of checking whether there is another thread with a higher priority;

after the thread has finished executing for the predetermined period of time.

15. The method of claim 8, wherein at least one of the plurality of processes is a multi-threaded application.

25. The method of claim 8, further comprising:

after transferring the unused time, causing the next thread to use at least a portion of the unused time when the next thread is being executed.

26. The method of claim 25, further comprising:

after casing the next thread to use at least a portion of the unused time, restarting the first thread and enabling he first thread to use any remaining unused that was not used by the next thread.

16. An apparatus to allow sharing a time quantum between threads in a process, comprising:

a portion configured to determine that a first thread, which is currently being executed by a processor and which has an associated time quantum, is blocked;

a portion configured to determine a next thread to be executed by the processor; and

a portion configured to transfer unused time in the time quantum of the first thread to the next thread to be executed.

17. The apparatus of claim 16, wherein the determining portion includes a portion configured to determine a next thread to be executed that is from the same process as the first thread.

18. The apparatus of claim 16, wherein the determining portion includes a portion configured to determine a next thread to be executed that is from a different process than the first thread.

19. The apparatus of claim 16, wherein the transferring portion includes a portion configured to add the unused time in the time quantum of the first thread to a time quantum of the next thread to execute.

20. The apparatus of claim 16, wherein the transferring portion includes a portion configured to transfer the unused time in the time quantum of the first thread to a time quantum of the next thread to execute, in place of an original time quantum for the next thread to execute.

27. The apparatus of claim 16, further comprising:

a portion configured to cause the next thread to use at least a portion of the unused time when next thread is being executed by the processor.

28. The apparatus of claim 27, further comprising:

a portion configured to restart the first thread and enable the first thread to use any remaining unused time that was not used by the next thread.

21. A computer program product, comprising:

a computer usable medium having computer readable code embodied therein for sharing a time quantum between threads in a process, the computer program product including;

computer readable program code devices configured to cause a computer to effect determining that a first thread, which is currently being executed by a processor and which has an associated time quantum, is blocked;

computer readable program code devices configured to cause a computer to effect determining a next thread to be executed by the processor; and

computer readable program code devices configured to cause a computer to effect transferring unused time in the time quantum of the first thread to the next thread to be executed.

29. The computer program product of claim 21, further comprising:

computer readable program code devices configured to cause a computer to effect causing the next thread to use at least a portion of the unused time when the next thread is being executed by the processor.

30. The computer program product of claim 21, further comprising:

computer readable program code devices configured to cause a computer to effect restarting the first thread and enabling the first thread to use any remaining unused time that was not used b the next thread.

22. A computer data signal embodied in a carrier wave and representing sequences of instructions which, when executed by a processor, cause the processor to share a time quantum between threads in a process by performing the steps of:

determining that a first thread, which is currently being executed by a processor and which has an associated time quantum, is blocked;

determining a next thread to be executed by the processor; and

transferring unused time in the time quantum of the first thread to the next thread to be executed.

31. The computer data signal of claim 22, where the process further comprises:

after transferring the unused time, causing the next thread to use at least a portion of the unused time when the next thread is being executed by the processor.

32. The computer data signal of claim 31, wherein the process further comprises:

after causing the next thread to use at least a portion of the unused time, restarting the first thread and enabling the first thread to use any remaining unused time that was not used by the next thread.