Low-overhead threads in a high-concurrency system

• US 6,874,027 B1
• Filed: 06/09/2000
• Issued: 03/29/2005
• Est. Priority Date: 04/07/2000
• Status: Expired due to Fees

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: English, Robert M.
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): SALAD, ABDULLAHI ELMI
• Application Number:
  US09/590,491
• Time in Patent Office: 1,754 Days
• Field of Search: 709/226, 709/201, 709/107, 709/108, 709/205, 709/102, 709/104, 709/203, 718/102, 718/100, 718/106, 718/104, 718/107, 718/105, 718/101, 707/8
• US Class Current: 709/226
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

A method and system for providing the functionality of dynamically-allocated threads in a multithreaded system, in which the operating system provides only statically-allocated threads. With this functionality, a relatively large number of threads can be maintained without a relatively large amount of overhead (either in memory or processor time), and it remains possible to produce program code without undue complexity. A plurality of dynamically-allocated threads are simulated using a single statically-allocated thread, but with state information regarding each dynamically-allocated thread maintained within the single statically-allocated thread. The single statically-allocated thread includes, for each procedure call that would otherwise introduce a new simulated thread, a memory block including (1) a relatively small procedure call stack for the new simulated thread, and (2) a relatively small collection of local variables and other state information for the new simulated thread.

Claims

1. A method including

simulating a plurality of dynamically-allocated threads using a single statically-allocated thread;

and

maintaining state information used by each dynamically-allocated thread in variables maintained by said statically-allocated thread;

wherein said statically-allocated thread simulates said plurality of dynamically-allocated threads by using a scheduler to call thread blocks for said plurality of dynamically-allocated threads; and

wherein said thread blocks are stored in a linked list maintained by said statically-allocated thread.

2. A method as in claim 1, further including maintaining, for a routine capable of being suspended or interrupted, a set of entry points into which said routine is capable of being re-entered after said suspension or interruption.

3. A method as in claim 1, further including generating said set of entry points in response to one or more programming macros.

4. A method as in claim 1, further including maintaining high concurrency among threads without maintaining a substantial amount of state information regarding simulated threads.

5. A method as in claim 4, wherein an amount of state information that is maintained is less than an amount of state information that would be necessary for plural actual dynamically-allocated threads.

6. A method as in claim 1, wherein said state information includes a relatively small procedure call stack for the simulated threads.

7. A method as in claim 6, wherein said relatively small procedure call stack is smaller than a procedure call stack that would be necessary for plural actual dynamically-allocated threads.

8. A method as in claim 1, wherein said state information includes a relatively small collection of local variables and other state information for the simulated threads.

9. A method as in claim 1, wherein said plurality of dynamically-allocated threads are simulated using said statically-allocated thread under an operating system that is incapable of executing plural actual dynamically-allocated threads.

10. A method as in claim 1, wherein said thread blocks in said linked list are called in turn by said scheduler.

11. Apparatus including a file server system having a single statically-allocated thread including a plurality of simulated dynamically-allocated threads, said statically-allocated thread maintaining variables that maintain state information used by each of said simulated dynamically-allocated threads;

wherein said statically-allocated thread simulates said plurality of dynamically-allocated threads by using a scheduler to call thread blocks for said plurality of dynamically-allocated threads; and

wherein said thread blocks are stored in a linked list maintained by said statically-allocated thread.

12. Apparatus as in claim 11, further including a routine capable of being suspended or interrupted, said routing having a set of entry points into which said routine is capable of being re-entered after said suspension or interruption.

13. Apparatus as in claim 12, wherein said set of entry points are responsive to one or more programming macros.

14. Apparatus as in claim 11, wherein said state information includes a relatively small procedure call stack for the simulated threads.

15. Apparatus as in claim 14, wherein said relatively small procedure call stack is smaller than a procedure call stack that would be necessary for plural actual dynamically-allocated threads.

16. Apparatus as in claim 11, wherein said state information includes a relatively small collection of local variables and other state information for the simulated threads.

17. Apparatus as in claim 16, wherein said relatively small collection of local variables and other state information is smaller than a collection of local variables and other state information that would be necessary for plural actual dynamically-allocated threads.

18. Apparatus as in claim 11, wherein said file server system is incapable of executing plural actual dynamically-allocated threads.

19. Apparatus as in claim 11, wherein said thread blocks in said linked list are called in turn by said scheduler.

20. A method of implementing a plurality of simulated dynamically-allocated threads using a single statically-allocated thread, comprising:

using a scheduler implemented by said single statically-allocated thread to call thread blocks for said plurality of simulated dynamically-allocated threads; and

maintaining state information used by each of said plurality of simulated dynamically-allocated threads in variables maintained by said statically-allocated thread;

wherein said thread blocks are stored in a linked list maintained by said statically-allocated thread.

21. A method as in claim 20, wherein said thread blocks in said linked list are called in turn by said scheduler.

22. Apparatus including a server that implements a plurality of simulated dynamically-allocated threads using a single statically-allocated thread, comprising:

a processor that executes a scheduler implemented by said single statically-allocated thread to call thread blocks for said plurality of simulated dynamically-allocated threads; and

memory that stores state information used by each of said plurality of simulated dynamically-allocated threads in variables maintained by said statically-allocated thread;

wherein said thread blocks are stored in a linked list maintained in said memory by said statically-allocated thread.

23. Apparatus as in claim 22, wherein said thread blocks in said linked list are called in turn by said scheduler.