Techniques for an interrupt free operating system

• US 6,314,471 B1
• Filed: 11/13/1998
• Issued: 11/06/2001
• Est. Priority Date: 11/13/1998
• Status: Expired due to Term

• Current Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Korry, Richard D., Coatney, Susan L., Alverson, Gail A., Callahan, Charles David II, Kaplan, Laurence S.
• Primary Examiner(s): Etienne, Ario
• Application Number:
  US09/191,942
• Time in Patent Office: 1,089 Days
• Field of Search: 710/8, 710/5, 710/6, 710/20, 710/18, 710/21, 712/9, 712/203, 712/206, 712/215, 712/241, 712/20, 712/21, 712/22, 712/32
• US Class Current: 710/5
• CPC Class Codes: G06F 9/4812 by interrupt, e.g. masked
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications

Abstract

A method and system in a multithreaded processor for processing events without interrupt notifications. In one aspect of the present invention, an operating system creates a thread to execute on a stream of the processor. During execution of the thread, the thread executes a loop that determines whether an event has occurred and, in response to determining whether an event has occurred, assigns a different thread to process the event so that multiple events can be processed in parallel and so that interrupts are not needed to signal that the event has occurred. Another aspect of the present invention provides a method and system for processing asynchronously occurring events without interrupt notifications. To achieve this processing, a first thread is executed to generate a notification that the event has occurred upon receipt of the asynchronously occurring event. A second thread is also executed that loops determining whether a notification has been generated and, in response to determining that a notification has been generated, performing the processing necessary for the event.

Claims

1. A method in a multithreaded processor for processing events without interrupt notifications, the method comprising:

creating a thread to execute on a stream of the processor; and

during execution of the thread,

executing a loop that

determines whether an event has occurred; and

in response to determining whether an event has occurred, assigns a different thread to process the event so that multiple events can be processed in parallel.

2. The method of claim 1 wherein the created thread is a listener thread.

3. The method of claim 1 wherein the assigning of a different thread includes the creating of a thread.

4. The method of claim 1 wherein an event is the unblocking of a thread of a user program.

5. The method of claim 1 wherein an event is the unblocking of a thread of an operating system.

6. The method of claim 1 wherein the event is the expiration of a timer.

7. The method of claim 6 wherein the assigning of a different thread includes sending a message to another thread.

8. The method of claim 7 wherein the other thread creates a thread to process the timer expiration.

9. The method of claim 1 wherein determining includes checking a data structure to determine if any thread are unblocked.

10. A method in a multithreaded processor for processing asynchronously occurring events without interrupt notifications, the method comprising:

upon receipt of the asynchronously occurring event, executing a first thread to generate a notification that the event has occurred; and

executing a second thread with a loop that

determines whether a notification has been generated;

in response to determining that a notification has been generated, performs the processing necessary for the event.

11. The method of claim 10 wherein the second thread is a virtual processor thread.

12. The method of claim 10 wherein the generated notification is placing an indication of a unit of work on a queue.

13. The method of claim 10 wherein the first thread is a device driver.

14. The method of claim 13 wherein the device driver invokes a callback routine to process the event.

15. The method of claim 10 including executing a stream of an input/output processor to indicate the occurrence of the event.

16. A computer system for processing events without interrupt notifications, the computer system having a multithreaded architecture with streams, comprising:

a team structure that references unblocked threads for each team associated with the computer system;

a daemon data structure that references unblocked operating system daemons associated with the computer system; and

a listener daemon that loops checking the data structures for unblocked threads of the teams and unblocked operating system daemons and starting the execution of the unblocked threads of the teams and the unblocked operating system daemons in streams.

17. The computer system of claim 16 wherein the team data structure and the daemon data structure comprise a single data structure.

18. The computer system of claim 16 wherein the computer system has multiple processors and a team represents the threads for a user program that is assigned to a processor.

19. The computer system of claim 16 wherein the listener daemon also checks for time out events when it loops.

20. The computer system of claim 16 wherein the operating system includes kernel daemons.

21. The computer system of claim 20 wherein a kernel daemon controls scheduling of user programs.

22. The computer system of claim 16 wherein the operating system includes supervisor daemons.

23. The computer system of claim 22 wherein a supervisor daemon controls executing device drivers.

24. The computer system of claim 16 wherein when execution of a thread of a team is started, the thread switch from a current protection domain to a protection domain associated with the thread.

25. The computer system of claim 16 including:

a continuation data structure that references unblocked continuations associated with the computer system, each continuation representing work to be performed by an operating system; and

virtual processor daemons that loop checking the continuation data structure and starting execution of any unblocked continuation.

26. The computer system of claim 25 wherein the continuation data structure also references continuations that have not yet been started and the virtual processor daemons start execution of the continuations that have not yet been started.

27. The computer system of claim 26 wherein the virtual processor daemons give preference to starting execution of unblocked continuations.

28. The computer system of claim 25 wherein the number of virtual processor daemons is modified dynamically.

29. The computer system of claim 25 wherein a continuation represents a request by a user program to perform work.

30. The computer system of claim 25 wherein a continuation represents a request by an operating system daemon to perform work.

31. The computer system of claim 25 wherein a continuation represents a request by a device driver to perform work.

32. The computer system of claim 31 wherein device drivers execute in supervisor daemons that block waiting for input or output.

33. A computer system for processing events without interrupt notifications, the computer system having a multithreaded architecture with streams, comprising:

a continuation data structure that references unblocked continuations associated with the computer system, each continuation representing work to be performed by an operating system; and

virtual processor daemons that loop checking the continuation data structure and starting execution of any unblocked continuation in a stream.

34. The computer system of claim 33 wherein the continuation data structure also references continuations that have not yet been started and the virtual processor daemons start execution of the continuations that have not yet been started.

35. The computer system of claim 34 wherein the virtual processor daemons give preference to starting execution of unblocked continuations.

36. The computer system of claim 33 wherein the number of virtual processor daemons is modified dynamically.

37. The computer system of claim 33 wherein a continuation represents a request by a user program to perform work.

38. The computer system of claim 33 wherein a continuation represents a request by an operating system daemon to perform work.

39. The computer system of claim 33 wherein a continuation represents a request by a device driver to perform work.

40. The computer system of claim 39 wherein device drivers execute in supervisor daemons that block waiting for input or output.

41. The computer system of claim 39 wherein device drivers invoke callback routines registered on behalf of user programs.

42. A method in a computer system for processing events without interrupts, the computer system having streams for execution of threads, the method comprising repeatedly:

determining whether there are any unblocked threads of execution for user programs that are currently not executing; and

when it is determined that there is an unblocked thread of execution for a user program that is not currently executing, staring execution of that unblocked thread of execution in a stream of the computer system.

43. The method of claim 42 wherein when an unblocked thread of execution is started, it switches protection domains to a protection domain of the user program.

44. The method of claim 42 including:

determining whether there are any unblocked operating system daemons that are currently not executing; and

when it is determined that there is an operating system daemon that is not currently executing, starting execution of the unblocked operating system daemon in a stream of the computer system.

45. The method of claim 44 wherein an unblocked operating system daemon represents processing for a device driver.

46. The method of claim 42 wherein virtual processors loop determining whether there are any unblocked continuations and when it is determined that there is an unblocked continuation, starting execution of the unblocked continuation in a stream of the computer system.

47. The method of claim 46 wherein the virtual processors also determine whether there are any not-yet-started continuations and when it is determined that there is a not-yet-started continuation, starting execution of the not-yet-started continuation.

48. The method of claim 47 wherein starting execution of unblocked continuations has priority over starting execution of not-yet-started continuations.

49. A method in a computer system for processing events without interrupts, the computer system having streams for execution of threads, the method comprising:

for each of a plurality of virtual processors,

repeatedly determining whether there are any unblocked continuations; and

when it is determined that there is an unblocked continuation, starting execution of the unblocked continuation in a stream of the computer system.

50. The method of claim 49 wherein the virtual processors also determine whether there are any not-yet-started continuations and when it is determined that there is a not-yet-started continuation, starting execution of the not-yet-started continuation.

51. The method of claim 50 wherein starting execution of unblocked continuations has priority over starting execution of not-yet-started continuations.

52. The method of claim 49 wherein a continuation represents processing on behalf of a device driver.

53. The method of claim 49 wherein a continuation represents processing on behalf of a user program.

54. A computer system for processing events without interrupt notifications in a multithreaded processor, comprising:

means for creating a thread to execute on a stream of the processor; and

means for executing a loop that, during execution of the thread, determines whether an event has occurred and, in response to determining whether an event has occurred, assigns a different thread to process the event so that multiple events can be processed in parallel.

55. The computer system of claim 54 wherein the created thread is a listener thread.

56. The computer system of claim 54 wherein the assigning of a different thread includes the creating of a thread.

57. The computer system of claim 54 wherein an event is the unblocking of a thread of a user program.

58. The computer system of claim 54 wherein an event is the unblocking of a thread of an operating system.

59. The computer system of claim 54 wherein the event is the expiration of a timer.

60. The computer system of claim 59 wherein the assigning of a different thread includes sending a message to another thread.

61. The computer system of claim 60 wherein the other thread creates a thread to process the timer expiration.

62. The computer system of claim 54 wherein determining includes checking a data structure to determine if any threads are unblocked.

63. A computer-readable medium containing instructions for controlling in a multithreaded processor to process asynchronously occurring events without interrupt notifications, by a method comprising:

upon receipt of the asynchronously occurring event, executing a first thread to generate a notification that the event has occurred; and

executing a second thread with a loop that determines whether a notification has been generated and, in response to determining that a notification has been generated, performs the processing necessary for the event.

64. The computer-readable medium of claim 63 wherein the second thread is a virtual processor thread.

65. The computer-readable medium of claim 63 wherein the generated notification is placing an indication of a unit of work on a queue.

66. The computer-readable medium of claim 63 wherein the first thread is a device driver.

67. The computer-readable medium of claim 66 wherein the device driver invokes a callback routine to process the event.

68. The computer-readable medium of claim 63 including executing a stream of an input/output processor to indicate the occurrence of the event.

69. A computer-readable medium containing instructions for controlling a computer system to process events without interrupts, the computer system having streams for execution of threads, by a method comprising repeatedly:

determining whether there are any unblocked threads of execution for user programs that are currently not executing; and

when it is determined that there is an unblocked thread of execution for a user program that is not currently executing, starting execution of that unblocked thread of execution in a stream of the computer system.

70. A computer-readable medium containing instructions for controlling a computer system to process events without interrupts, the computer system having streams for execution of threads, by a method comprising:

for each of a plurality of virtual processors,

repeatedly determining whether there are any unblocked continuations; and

when it is determined that there is an unblocked continuation, starting execution of the unblocked continuation in a stream of the computer system.