Preemptive multitasking employing software emulation of directed exceptions in a multithreading processor

• US 9,032,404 B2
• Filed: 12/20/2005
• Issued: 05/12/2015
• Est. Priority Date: 08/28/2003
• Status: Active Grant

• Current Assignee: MIPS Tech, LLC
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Kissell, Kevin D.
• Primary Examiner(s): ZHE, MENG YAO
• Application Number:
  US11/313,296
• Publication Number:
  US 20060161921A1
• Time in Patent Office: 3,430 Days
• Field of Search: None
• US Class Current: 718/100
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/30032 Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
• CPC Class Codes: G06F 9/30123 according to context, e.g. thread buffers
• CPC Class Codes: G06F 9/3017 Runtime instruction translation, e.g. macros
• CPC Class Codes: G06F 9/30174 for non-native instruction set, e.g. Javabyte, legacy code
• CPC Class Codes: G06F 9/30181 Instruction operation extension or modification
• CPC Class Codes: G06F 9/30185 according to one or more bits in the instruction, e.g. prefix, sub-opcode
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/4812 by interrupt, e.g. masked
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A multiprocessor computer system includes an exception domain having multiple thread contexts (TCs) each having a restart address register, and a timer that generates a periodic interrupt request to the exception domain. The exception domain selects an eligible TC to service the interrupt request, which is non-specific regarding which TC to select. A first interrupt handler executes on the selected TC to service the interrupt request to schedule a set of processes assigned by the SMP OS for execution on the selected TC, and write an address of a second interrupt handler to the restart address register of each TC other than the selected TC. The second interrupt handler schedules a plurality of sets of processes assigned by the SMP OS for execution on respective ones of the TCs other than the selected TC.

Claims

1. A method for performing preemptive scheduling of a plurality of processes managed by a symmetric multiprocessor operating system on a multithreading microprocessor, the method comprising:

receiving, by an exception domain, a periodic interrupt request from a timer, the exception domain comprising a plurality of thread contexts of the microprocessor;

determining a subset of eligible threads from the plurality of thread contexts of the microprocessor;

selecting one of the plurality of thread contexts from the subset of eligible threads;

executing a first interrupt handler on the one of the plurality of thread contexts to service the interrupt request, said executing comprising;

scheduling a new process to execute on the one thread context;

writing an address of a second interrupt handler to a restart address register of each thread context other than the one of the plurality of thread contexts; and

scheduling, by the second interrupt handler, a respective new process to execute on each thread context other than the one of the plurality of thread contexts.

2. The method as recited in claim 1, wherein said executing the first interrupt handler further comprises:

for each thread context other than the one of the plurality of thread contexts, writing to a control register of the thread context to commence execution of the second interrupt handler thereon, prior to said scheduling by the second interrupt handler the respective new process to execute on the thread context.

3. The method as recited in claim 2, wherein said executing the first interrupt handler further comprises:

for each thread context other than the one of the plurality of thread contexts, writing to the control register of the thread context to halt execution of a thread executing thereon, prior to said writing the address of the second interrupt handler to the restart address register.

4. The method as recited in claim 3, wherein said executing the first interrupt handler further comprises:

for each thread context other than the one of the plurality of thread contexts, reading a restart address of the thread from the restart address register, prior to said writing the address of the second interrupt handler to the restart address register.

5. The method as recited in claim 4, wherein said executing the first interrupt handler further comprises:

for each thread context other than the one of the plurality of thread contexts, saving the restart address to a memory coupled to the microprocessor, after said reading the restart address of the thread from the restart address register.

6. The method as recited in claim 3, wherein said executing the first interrupt handler further comprises:

for each thread context other than the one of the plurality of thread contexts, reading an execution privilege level of the thread context and saving the execution privilege level to a memory coupled to the microprocessor, after said writing to the control register of the thread context to halt execution of the thread executing thereon, and prior to said writing to the control register of the thread context to commence execution of the second interrupt handler thereon.

7. The method as recited in claim 1, further comprising:

selecting the one thread context to service the timer interrupt request, in response to said receiving the timer interrupt request, and prior to said executing the first interrupt handler on the one thread context.

8. The method as recited in claim 7, wherein said selecting the one thread context to service the interrupt request comprises selecting an eligible one of the plurality of thread contexts, wherein one of the plurality of thread contexts is eligible if it is enabled to service exceptions.

9. The method as recited in claim 8, wherein said selecting the one thread context to service the interrupt request comprises selecting an eligible one of the plurality of thread contexts in a pseudo-random fashion.

10. The method as recited in claim 8, wherein said selecting the one thread context to service the interrupt request comprises selecting an eligible one of the plurality of thread contexts in a round-robin fashion.

11. The method as recited in claim 8, wherein said selecting the one thread context to service the interrupt request comprises selecting an eligible one of the plurality of thread contexts based on relative priorities of the plurality of thread contexts.

12. The method as recited in claim 7, further comprising:

suspending execution of the plurality of thread contexts other than the selected one thread context, after said selecting the one thread context.

13. The method as recited in claim 1, wherein the timer interrupt request is non-specific about which of the plurality of thread contexts is to be interrupted to execute the first interrupt handler to service the request.

14. The method as recited in claim 1, wherein the timer interrupt request is non-directable specifically to any of the plurality of thread contexts.

15. The method as recited in claim 1, wherein the plurality of thread contexts are bound to the exception domain.

16. The method as recited in claim 1, wherein the microprocessor comprises a second exception domain comprising a second plurality of thread contexts each bound to the second exception domain, wherein said executing the first interrupt handler further comprises:

for each of the second plurality of thread contexts, placing a message on a message queue to request the thread context to service the request.

17. The method as recited in claim 16, wherein said executing the first interrupt handler further comprises:

interrupting the second exception domain, after said placing the messages.

18. The method as recited in claim 17, wherein said interrupting the second exception domain comprises:

writing to a control register of the second exception domain to cause a software interrupt.

19. The method as recited in claim 1, wherein said executing the first interrupt handler further comprises:

for each thread context other than the one of the plurality of thread contexts;

reading a status register of the thread context to determine whether the thread context is exempted from servicing exceptions; and

placing a message on a message queue to request the thread context to service the request, if the status register indicates the thread context is exempted from servicing exceptions, rather than said writing the address of the second interrupt handler to the restart address register of the thread context.

20. The method as recited in claim 1, wherein said executing the first interrupt handler further comprises:

for each thread context other than the one of the plurality of thread contexts, saving a current state of the thread context, prior to said writing to the restart address register.

21. A multiprocessor computer system for performing preemptive scheduling of a plurality of processes managed by a symmetric multiprocessor operating system (SMP OS) running on the system, the system comprising:

a multithreading microprocessor, comprising;

an exception domain, comprising a plurality of thread contexts each comprising a restart address register; and

a timer, configured to generate a periodic interrupt request to said exception domain, wherein said exception domain is configured to;

determine a subset of eligible threads from the plurality of thread contexts, and

select one of the plurality of thread contexts from the subset of eligible threads to service said interrupt request, wherein said timer interrupt request is nonspecific regarding which of said plurality of thread contexts to select to service said request; and

a memory, coupled to said microprocessor, for storing a first interrupt handler of the SMP OS for execution on said selected thread context to service said interrupt request, wherein said first interrupt handler is configured to;

schedule a set of processes assigned by the SMP OS for execution on said selected thread context; and

write an address of a second interrupt handler to said restart address register of each of said plurality of thread contexts other than said selected thread context, wherein said second interrupt handler is configured to schedule a plurality of sets of processes assigned by the SMP OS for execution on respective ones of said plurality of thread contexts other than said selected thread context.

22. The system as recited in claim 21, wherein said first interrupt handler is further configured to, for each thread context other than said selected thread context, write to a control register of said thread context to commence execution of said second interrupt handler thereon, prior to said second interrupt handler scheduling said plurality of sets of processes.

23. The system as recited in claim 22, wherein said first interrupt handler is further configured to, for each thread context other than said selected thread context, write to said control register of said thread context to halt execution of a thread executing thereon, prior to writing said address of said second interrupt handler to said restart address register.

24. The system as recited in claim 23, wherein said first interrupt handler is further configured to, for each thread context other than said selected thread context, read a restart address of said thread from said restart address register, prior to writing said address of said second interrupt handler to said restart address register.

25. The system as recited in claim 24, wherein said first interrupt handler is further configured to, for each thread context other than said selected thread context, save said restart address to a memory coupled to said microprocessor, prior to reading said restart address of said thread from said restart address register.

26. The system as recited in claim 23, wherein said first interrupt handler is further configured to, for each thread context other than said selected thread context, read an execution privilege level of said thread context and save said execution privilege level to a memory coupled to said microprocessor, subsequent to writing to said control register of said thread context to halt execution of said thread executing thereon, and prior to writing to said control register of said thread context to commence execution of said second interrupt handler thereon.

27. The system as recited in claim 22, wherein said control register comprises a MIPS Multithreading Application Specific Extension (MT ASE) TCHalt register.

28. The system as recited in claim 21, wherein said exception domain is further configured to suspend execution of said plurality of thread contexts other than said selected thread context, in response to receiving said timer interrupt request.

29. The system as recited in claim 21, wherein said microprocessor further comprises:

a second exception domain, comprising a second plurality of thread contexts, wherein said first interrupt handler is further configured to, for each of said second plurality of thread contexts, place a message on a message queue to request said thread context to service said request.

30. The system as recited in claim 29, wherein said first interrupt handler is further configured to interrupt said second exception domain, after placing said messages.

31. The system as recited in claim 30, wherein said first interrupt handler writes to a control register of said second exception domain to cause a software interrupt.

32. The system as recited in claim 31, wherein said control register comprises a MIPS Privileged Resource Architecture (MT PRA) Cause register.

33. The system as recited in claim 21, wherein said first interrupt handler is further configured to, for each thread context other than said selected thread context, read a status register of said thread context to determine whether said thread context is exempted from servicing exceptions, and place a message on a message queue to request said thread context to service said request, if said status register indicates said thread context is exempted from servicing exception, rather than writing said address of said second interrupt handler to said restart address register of said thread context.

34. The system as recited in claim 33, wherein said status register comprises a MIPS Multithreading Application Specific Extension (MT ASE) TCStatus register.

35. The system as recited in claim 21, wherein said first interrupt handler is further configured to, for each thread context other than said selected thread context, save a current state of said thread context, prior to writing to said restart address register.

36. The system as recited in claim 21, wherein said restart address register comprises a MIPS Multithreading Application Specific Extension (MT ASE) TCRestart register.

37. The system as recited in claim 21, wherein said plurality of thread contexts comprise MIPS Application Specific Extension (MT ASE) thread contexts.

38. A computer program product for use with a computing device, the computer program product comprising:

a non-transitory computer readable storage medium, having computer readable program code embodied in said medium, wherein the computer readable program code is configured to cause a computer executing the computer readable program code to perform a method of preemptive scheduling of a plurality of processes managed by a symmetric multiprocessor operating system on a multithreading microprocessor, wherein the method comprises;

receiving, by an exception domain, a periodic interrupt request from a timer, the exception domain comprising a plurality of thread contexts of the microprocessor;

determining a subset of eligible threads from the plurality of thread contexts of the microprocessor;

selecting one of the plurality of thread contexts from the subset of eligible threads;

executing a first interrupt handler on the one of the plurality of thread contexts to service the interrupt request, said executing comprising;

scheduling a new process to execute on the one thread context; and

writing an address of a second interrupt handler to a restart address register of each thread context other than the one of the plurality of thread contexts; and

scheduling, by the second interrupt handler, a respective new process to execute on each thread context other than the one of the plurality of thread contexts.

39. The computer program product of claim 38, wherein the computer readable program code is configured to cause a computer executing the computer readable program code to perform the method, further comprising:

providing a step of for each thread context other than the one of the plurality of thread contexts, writing to a control register of the thread context to commence execution of the second interrupt handler thereon, prior to said scheduling by the second interrupt handler the respective new process to execute on the thread context.

40. The computer program product of claim 39, wherein the computer readable program code is configured to cause a computer executing the computer readable program code to perform the method, further comprising:

providing a step of for each thread context other than the one of the plurality of thread contexts, writing to the control register of the thread context to halt execution of a thread executing thereon, prior to said writing the address of the second interrupt handler to the restart address register.