Queue object for controlling concurrency in a computer system

Claim 2

A computer system executing an operating system for controlling the execution of a plurality of threads provided by said operating system, each of said plurality of threads in one of a plurality of states when said thread is currently active processing a work entry, said computer comprising: a microprocessor; a memory device, coupled to said microprocessor and accessible by said operating system, including a data structure stored in said memory device, said data structure including: a first section containing an entry list of work entries to be distributed to said plurality of threads; and a second section containing the number of threads that are currently in one of said plurality of states, said microprocessor responsive to said operating system to assign a selected one of said plurality of threads if the number of threads that are currently in one of said plurality of states is less than a predetermined number.

Claim 3

The computer system of claim 1, wherein said predetermined number is contained in a third section of said data structure.

Claim 4

The computer system of claim 2, wherein said data structure further includes a fourth section containing a wait list of waiting threads.

Claim 5

The computer system of claim 3, wherein said data structure further includes: a fifth section containing the size of said data structure; a sixth section containing the name of said data structure; and a seventh section including the number of said work entries in said entry list.

Claim 6

The computer system of claim 1, wherein said predetermined number defines a target concurrency level; and wherein said number of threads that are currently active processing one of said work entries defines a current concurrency level.

Claim 7

The computer system of claim 5, wherein said operating system is operative to reduce the current concurrency level in the event that said current concurrency level is greater than said target concurrency level.

Claim 8

The computer system of claim 5, wherein said operating system is operative to increase said current concurrency level in the event said current concurrency level is less than said target concurrency level.

Claim 9

In a computer system including a microprocessor, an operating system running on said computer system, a memory device coupled to said microprocessor and accessible by said operating system, said memory device storing a plurality of queue objects, each queue object including an entry list of work entries, a plurality of waiting threads, a current concurrency level and a target concurrency level, a method of controlling the current concurrency level, comprising the steps of: (a) comparing the current concurrency level with the target concurrency level, (b) if the current concurrency level is less than the target concurrency level, then: (i) giving a selected one of said plurality of work entries to a selected one of said plurality of waiting threads; (ii) executing said selected one of said plurality of waiting threads on said microprocessor; (iii) incrementing the current concurrency level; (c) otherwise, inserting said selected one of said plurality of work entries in said entry list.

Claim 10

In a computer system including a microprocessor, an operating system running on said computer system, a memory device coupled to said microprocessor and accessible by said operating system, said memory device storing a plurality of queue objects, each queue object including an entry list of work entries, a plurality of waiting threads, a current concurrency level and a target concurrency level, a method of controlling the current concurrency level, comprising the steps of: (a) comparing the current concurrency level with the target concurrency level, (b) if the current concurrency level is less than the target concurrency level, then: (i) giving a selected one of said plurality of work entries to a selected one of said plurality of waiting threads; (ii) executing said selected one of said plurality of waiting threads on said microprocessor; (iii) incrementing the current concurrency level; (c) otherwise, inserting said selected one of said plurality of work entries in said entry list.

Claim 11

The method of claim 8, further comprising the step of associating said selected waiting thread with a selected one of said plurality of queue objects.

Claim 12

In a computer system including a microprocessor, an operating system running on said computer system, a memory device coupled to said microprocessor and accessible by said operating system, said memory device storing a plurality of queue objects, each queue object including an entry list of work entries, a plurality of waiting threads, a current concurrency level and a target concurrency level, a method of controlling the current concurrency level, comprising the steps of: (a) detecting a calling thread that has completed executing one of said work entries on said microprocessor and is ready to execute another one of said work entries; (b) if the current concurrency level is less than the target concurrency level, then determining whether any of said plurality of work entries can be removed from said entry list; (b1) if there is not a work entry in the entry list that can be removed, then instructing said calling thread to enter a waiting state; (b2) otherwise: (i) removing a selected one of the plurality of work entries from the entry list; (ii) decrementing the number of work entries in the entry list; (iii) incrementing the current concurrency level; and (iv) executing said selected work entry on said microprocessor; (c) if the current concurrency level is not less than the target concurrency level, then instructing said calling thread to enter a waiting state.

Claim 13

In a computer system including a microprocessor, an operating system running on said computer system, a memory device coupled to said microprocessor and accessible by said operating system, said memory device storing a plurality of queue objects, each queue object including an entry list of work entries, a plurality of waiting threads, a current concurrency level and a target concurrency level, a method of controlling the current concurrency level, comprising the steps of: (a) detecting a calling thread that has completed executing one of said work entries on said microprocessor and is ready to execute another one of said work entries; (b) if the current concurrency level is less than the target concurrency level, then determining whether any of said plurality of work entries can be removed from said entry list; (b1) if there is not a work entry in the entry list that can be removed, then instructing said calling thread to enter a waiting state; (b2) otherwise: (i) removing a selected one of the plurality of work entries from the entry list; (ii) decrementing the number of work entries in the entry list; (iii) incrementing the current concurrency level; and (iv) executing said selected work entry on said microprocessor; (c) if the current concurrency level is not less than the target concurrency level, then instructing said calling thread to enter a waiting state.

Claim 14

The method of claim 10, further comprising the steps of: determining whether said calling thread is associated with one of said plurality of queue objects; if the associated queue object is the queue object from which said calling thread is attempting to remove a selected work entry, then decrementing the concurrency level corresponding to that queue object; if the associated queue object is not the queue object from which said calling thread is attempting to remove a selected work entry, then removing a selected work entry for a different thread.

Claim 15

The method of claim 10, wherein said selected one of the plurality of work entries is the first entry in the entry list.

Claim 16

A computer system executing a program module for controlling the execution of a plurality of threads provided by said program module, each of said plurality of threads in one of a plurality of states when said thread is currently active processing a work entry, said computer comprising: a microprocessor; a memory device, coupled to said microprocessor and accessible by said operating system, including a data structure stored in said memory device, said data structure including: a first section containing an entry list of work entries to be distributed to said plurality of threads; and a second section containing the number of threads that are currently in one of said plurality of states, said microprocessor responsive to said operating system to assign a selected one of said plurality of threads if the number of threads that are currently in one of said plurality of states is less than a predetermined number.

Claim 17

A computer system executing a program module for controlling the execution of a plurality of threads provided by said program module, each of said plurality of threads in one of a plurality of states when said thread is currently active processing a work entry, said computer comprising: a microprocessor; a memory device, coupled to said microprocessor and accessible by said operating system, including a data structure stored in said memory device, said data structure including: a first section containing an entry list of work entries to be distributed to said plurality of threads; and a second section containing the number of threads that are currently in one of said plurality of states, said microprocessor responsive to said operating system to assign a selected one of said plurality of threads if the number of threads that are currently in one of said plurality of states is less than a predetermined number.

Claim 18

The computer system of claim 13, wherein said predetermined number is contained in a third section of said data structure.

Claim 19

The computer system of claim 14, wherein said data structure further includes a fourth section containing a wait list of waiting threads.

Claim 20

The computer system of claim 15, wherein said data structure further includes: a fifth section containing the size of said data structure; a sixth section containing the name of said data structure; and a seventh section including the number of said work entries in said entry list.

Claim 21

The computer system of claim 13, wherein said predetermined number defines a target concurrency level; and wherein said number of threads that are currently active processing one of said work entries defines a current concurrency level.

Claim 22

In a computer system including a microprocessor, a program module running on said computer system, a memory device coupled to said microprocessor and accessible by said program module, said memory device storing a plurality of queue objects, each queue object including an entry list of work entries, a plurality of waiting threads, a current concurrency level and a target concurrency level, a method of controlling the current concurrency level, comprising the steps of: (a) comparing the current concurrency level with the target concurrency level, (b) if the current concurrency level is less than the target concurrency level, then: (i) giving a selected one of said plurality of work entries to a selected one of said plurality of waiting threads; (ii) executing said selected one of said plurality of waiting threads on said microprocessor; (iii) incrementing the current concurrency level; (c) otherwise, inserting said selected one of said plurality of work entries in said entry list.

Claim 23

In a computer system including a microprocessor, a program module running on said computer system, a memory device coupled to said microprocessor and accessible by said program module, said memory device storing a plurality of queue objects, each queue object including an entry list of work entries, a plurality of waiting threads, a current concurrency level and a target concurrency level, a method of controlling the current concurrency level, comprising the steps of: (a) comparing the current concurrency level with the target concurrency level, (b) if the current concurrency level is less than the target concurrency level, then: (i) giving a selected one of said plurality of work entries to a selected one of said plurality of waiting threads; (ii) executing said selected one of said plurality of waiting threads on said microprocessor; (iii) incrementing the current concurrency level; (c) otherwise, inserting said selected one of said plurality of work entries in said entry list.

Claim 24

The method of claim 18, further comprising the step of associating said selected waiting thread with a selected one of said plurality of queue objects.

Claim 25

In a computer system including a microprocessor, a program module running on said computer system, a memory device coupled to said microprocessor and accessible by said program module, said memory device storing a plurality of queue objects, each queue object including an entry list of work entries, a plurality of waiting threads, a current concurrency level and a target concurrency level, a method of controlling the current concurrency level, comprising the steps of: (a) detecting a calling thread that has completed executing one of said work entries on said microprocessor and is ready to execute another one of said work entries; (b) if the current concurrency level is less than the target concurrency level, then determining whether any of said plurality of work entries can be removed from said entry list; (b1) if there is not a work entry in the entry list that can be removed, then instructing said calling thread to enter a waiting state; (b2) otherwise: (i) removing a selected one of the plurality of work entries from the entry list; (ii) decrementing the number of work entries in the entry list; (iii) incrementing the current concurrency level; and (iv) executing said selected work entry on said microprocessor; (c) if the current concurrency level is not less than the target concurrency level, then instructing said calling thread to enter a waiting state.

Claim 26

In a computer system including a microprocessor, a program module running on said computer system, a memory device coupled to said microprocessor and accessible by said program module, said memory device storing a plurality of queue objects, each queue object including an entry list of work entries, a plurality of waiting threads, a current concurrency level and a target concurrency level, a method of controlling the current concurrency level, comprising the steps of: (a) detecting a calling thread that has completed executing one of said work entries on said microprocessor and is ready to execute another one of said work entries; (b) if the current concurrency level is less than the target concurrency level, then determining whether any of said plurality of work entries can be removed from said entry list; (b1) if there is not a work entry in the entry list that can be removed, then instructing said calling thread to enter a waiting state; (b2) otherwise: (i) removing a selected one of the plurality of work entries from the entry list; (ii) decrementing the number of work entries in the entry list; (iii) incrementing the current concurrency level; and (iv) executing said selected work entry on said microprocessor; (c) if the current concurrency level is not less than the target concurrency level, then instructing said calling thread to enter a waiting state.

Claim 27

The method of claim 20, further comprising the steps of: determining whether said calling thread is associated with one of said plurality of queue objects; if the associated queue object is the queue object from which said calling thread is attempting to remove a selected work entry, then decrementing the concurrency level corresponding to that queue object; if the associated queue object is not the queue object from which said calling thread is attempting to remove a selected work entry, then removing a selected work entry for a different thread.

Claim 28

The method of claim 21, wherein said selected one of the plurality of work entries is the first entry in the entry list.

Claim 29

A computer readable medium having stored therein instructions for causing a computer system to execute the method of claim 8.

Claim 30

A computer readable medium having stored therein instructions for causing a computer system to execute the method of claim 10.

Claim 31

A computer readable medium having stored therein instructions for causing a computer system to execute the method of claim 18.

Claim 32

A computer readable medium having stored therein instructions for causing a computer system to execute the method of claim 20.