Enumeration of a concurrent data structure

An enumerable concurrent data structure referred to as a concurrent bag is provided. The concurrent bag is accessible by concurrent threads and includes a set of local lists configured as a linked list and a dictionary. The dictionary includes an entry for each local list that identifies the thread that created the local list and the location of the local list. Each local list includes a set of data elements configured as a linked list. A global lock on the concurrent bag and local locks on each local list allow operations that involve enumeration to be performed on the concurrent bag.

BACKGROUND

Processes executed in a computer system may be configured to execute different parts of the process concurrently. Where these different parts of the process may access the same data concurrently, the accesses to the data are typically synchronized. For example, when a thread of a process accesses data, it generally invokes a lock or other synchronization technique to ensure that no other thread of the process performs a conflicting access to the data. The synchronization prevents data from being corrupted but adds processing overhead to each data access and may serialize the access to the data by different threads. This serialization may inhibit the performance and scalability of a process, particularly where there are many independent processing resources that execute threads.

A process may wish to perform concurrent operations on a collective set of data. In doing so, different threads of the process may add data to or remove data from the collective set of data in an arbitrary order. The process may wish to enumerate the collective set of data at some point in the execution. While various synchronization mechanisms may be used to allow the collective set of data to be enumerated, the synchronization mechanisms may inhibit the performance and scalability of the process.

SUMMARY

An enumerable concurrent data structure referred to as a concurrent bag is provided. The concurrent bag is accessible by concurrent threads and includes a set of local lists configured as a linked list and a dictionary. The dictionary includes an entry for each local list that identifies the thread that created the local list and the location of the local list. Each local list includes a set of data elements configured as a linked list. A global lock on the concurrent bag and local locks on each local list allow operations that involve enumeration to be performed on the concurrent bag.

DETAILED DESCRIPTION

FIG. 1is a block diagram illustrating an embodiment of a runtime environment10with a process12that is executing multiple concurrent threads22(1)-22(M) where M is greater than or equal to two and may vary during the execution of process12.

Runtime environment10represents a runtime mode of operation in a computer system, such as a computer system100shown inFIG. 6and described in additional detail below, where the computer system is executing instructions. The computer system generates runtime environment10from a kernel14, processing resources16(1)-16(N) where N is greater than or equal to one and may vary during the execution of process12, a resource management layer18, and a runtime platform20. Runtime environment10allows process12to be executed by the computer system along any other processes that co-exist with process12(not shown) using kernel14, processing resources16(1)-16(N), resource management layer18, and runtime platform20. Runtime environment10operates in conjunction with kernel14and/or resource management layer18to allow process12to obtain processor and other resources of the computer system (e.g., processing resources16(1)-16(N)).

Process12may be configured to operate in a computer system based on any suitable execution model, such as a stack model or an interpreter model, and may represent any suitable type of code, such as an application, a library function, or an operating system service. Process12has a program state and machine state associated with a set of allocated resources that include a defined memory address space of the computer system. Process12executes autonomously or substantially autonomously from any co-existing processes in runtime environment10. Accordingly, process12does not adversely alter the program state of co-existing processes or the machine state of any resources allocated to co-existing processes. Similarly, co-existing processes do not adversely alter the program state of process12or the machine state of any resources allocated to process12.

Process12includes an allocation of processing and other resources that execute threads22. Process12obtains access to the processing and other resources in the computer system from kernel14, resource management layer18, and runtime platform20. Process12includes a sequence of instructions that perform work when executed by threads22in the computer system. Each thread22includes program state and machine state information that allows blocking and unblocking of threads22. The blocking may include preemptive and/or cooperative blocking. Threads22may be created or terminated as specified by process12and/or kernel14.

Kernel14manages processing and other resources of the computer system and provides a set of functions that allow process12and other processes in the computer system to access and use the components. In addition, kernel14offers threads22to process12and allocates memory of the computer system to process12. Kernel14may allocate the memory in any suitable fixed or variable sizes (e.g., pages of 4 kilobytes (KB) to 64 KB).

Processing resources16reside in execution cores of a set or one or more processor packages (e.g., one or more processor packages102shown inFIG. 6and described in additional detail below) of the computer system. Each processing resource16is configured to execute instructions independently or substantially independently from the other execution cores and includes a machine state. Processing resources16may be included in a single processor package or may be distributed across multiple processor packages. Each execution core in a processor package may include one or more processing resources16.

Resource management layer18allocates processing resources16to process12to cause process12and threads22to be executed by the allocated processing resources16. Resource management layer18exists separately from kernel14in the embodiment ofFIG. 1. In other embodiments, resource management layer18or some or all of the functions thereof may be included in kernel14.

Runtime platform20includes instructions that are executable in conjunction with kernel14and resource management layer18to generate runtime environment10and provide runtime functions to process12and other processes. These runtime functions include a concurrent bag function that creates concurrent bag24as will be described below. The runtime functions may be included in computer system100as a library of functions or other suitable programming construct that makes the functions available to process12and other processes in runtime environment10. In other embodiments, some or all of the runtime functions may be as an integrated part of kernel14and/or resource management layer18.

Process12causes concurrent bag24to be created via the concurrent bag function provided by runtime platform20. Concurrent bag24is a data structure that forms a concurrent collection of data elements46(shown inFIG. 2) that is accessible by multiple threads22. The concurrent bag function may be implemented as an application programming interface (API) or other suitable programming construct in runtime platform20.

Concurrent bag24includes a concurrent dictionary26and a linked list of local lists30of data elements46. Dictionary26includes an entry28for each local list30where each entry28includes a thread identifier28A that identifies a thread22that created the corresponding local list30as the key and a list identifier28B that identifies a location of the corresponding local list30as the value. The set of local lists30are configured as a linked list by including a next list identifier32with each local list30that identifies the head of a next local list30.

The linked list of local lists30may be locked using a global lock34or other suitable synchronization mechanism. A thread22that acquires global lock34prevents all other threads22from adding or deleting local lists30from the linked list until the thread22releases global lock34. Global lock34, however, does not prevent threads22from adding, removing, or stealing data elements46from local lists30.

Concurrent bag24also includes a synchronization indicator36. Synchronize indicator36indicates whether synchronization (e.g., a local lock60) is to be used when a thread22performs an add operation or a remove operation to the linked list or steals a data element46from the linked list. If synchronization is to be used, then the thread22acquires the local lock60of the local list30prior to performing a synchronized add operation or a synchronized remove operation or stealing a data element46without regard to the number of data elements46in the linked list of data elements46. If not, then the thread22performs the add operation or remove operation without synchronization if the linked list of data elements46includes two or more data elements46.

As shown inFIG. 2, each local list30includes a next list identifier32, a thread identifier42, a head identifier44, a set of data elements46configured as a linked list, a tail identifier48, a count50, a steal count52, a current operation indicator54, and a lock taken indicator56. Each local list30may be locked using a corresponding local lock60or other suitable synchronization mechanism.

Thread identifier42identifies the thread22that created the corresponding local list30.

Head identifier44and tail identifier48identifies the head and the tail of a linked list, respectively, formed by the set of data elements46(1)-46(P) of the corresponding local list30, where P represents the Pth data element46at any point in the execution of process12. The set of data elements46is configured as a linked list to allow the thread22that created the corresponding local list30and one other thread22to concurrently access the linked list where the linked list includes two or more data elements46. For example, the thread22that created the corresponding local list30may access (i.e., add or remove) the data element46(1) at the head of the linked list while another thread22concurrently steals (i.e., removes) the data element46(P) at the tail of the linked list if P is greater than or equal to two.

Count50identifies the number data elements46that have been added to and removed from in the linked list by the thread22that created the corresponding local list30(i.e., the thread22identified in thread identifier42). Count50is incremented each time that a data element46is added to the linked list by the thread22that created the corresponding local list30and decremented each time that a data element46is removed from the linked list by the thread22that created the corresponding local list30in one embodiment.

Steal count52identifies the number data elements46that have been stolen (i.e., removed) from in the linked list by a threads22other than the thread22that created the corresponding local list30. Steal count52is incremented each time that a data element46is stolen from the linked list by a threads22other than the thread22that created the corresponding local list30.

Current operation indicator54is set by the thread22that created the corresponding local list30to indicate whether an unsynchronized add operation, an unsynchronized remove operation, or no operation is being performed on the linked list of data elements46. The thread22performs an add operation to add a data element46to the linked list and performs a remove operation to remove a data element46from the linked list. Current operation indicator54indicates that no operation is being performed any time that no unsynchronized add or remove operation is being performed by the thread22.

Lock taken indicator56indicates whether the local lock60is currently taken or is currently available. A thread22that acquires the local lock60prevents all other threads22from performing synchronized add and remove operations on the corresponding local list30and stealing from the corresponding local list30until the thread22releases the local lock60.

Concurrent bag24attempts to minimize the use of synchronization (e.g., minimize the use of global lock34and local locks60) in accessing data elements46in concurrent bag24from multiple threads22while preserving thread safety between threads22as described below with reference toFIGS. 3 and 4A-4B. In addition, concurrent bag24provides for enumeration to support various operations for concurrent bag24as described below with reference toFIG. 5. The synchronization policies described with reference toFIGS. 3 and 4A-4Ballow concurrent bag24to be frozen for enumeration as described with reference toFIG. 5.

FIG. 3is a flow chart illustrating an embodiment of a method for adding local lists30to concurrent bag24. The embodiment ofFIG. 3will now be described with reference to the embodiments ofFIGS. 1 and 2where a concurrent bag24has been created. In one embodiment, thread22creates concurrent bag24by calling a function in runtime platform20. In other embodiments, thread22creates concurrent bag24using other suitable programming constructs or one or more functions located outside of runtime platform20but otherwise in or accessible to the computer system.

InFIG. 3, any time that an arbitrary thread22seeks to add a data element to a local list30in concurrent bag24, the thread22determines whether a local list30for the thread22is present in concurrent bag24, as indicated in a block61, by locating an entry28for the thread22in dictionary26. If an entry28for the thread22is located, then the thread22adds the data element46to the local list30as described in the method ofFIG. 4Abelow. If not, then the thread22determines whether global lock34of concurrent bag24is available as indicated in a block62. If not, then the thread22waits until global lock34is available before acquiring global lock34as indicated in a block63, adding a local list30to the linked list of local lists30in concurrent bag24as indicated in a block64, and adding the data element46to the local list30as indicated in a block65. The thread22subsequently releases global lock34as indicated in a block66. Using global lock34, runtime platform20synchronizes the addition of local lists30to concurrent bag24by threads22.

In one embodiment, thread22calls a function in runtime platform20that causes the local list30to be added to concurrent bag24. The function creates an entry28in dictionary26that identifies the thread22in thread identifier28A and the location of the local list30in list identifier28B. The function also sets the next list identifier32of the previous local list30(if present), which is identified using the previous entry28in dictionary26, to identify the newly added local list30. The function further sets the next list identifier32of the newly added local list30to null. In other embodiments, thread22adds the local list30to concurrent bag24using other suitable programming constructs or one or more functions located outside of runtime platform20but in or accessible to the computer system.

Local lists30may continue to be added to concurrent bag24by arbitrary threads22until concurrent bag24is deleted. In one embodiment, a thread22deletes concurrent bag24by calling a function in runtime platform20. In other embodiments, thread22deletes concurrent bag24using other suitable programming constructs or one or more functions located outside of runtime platform20but in or accessible to the computer system. In embodiments with garbage collection, runtime platform20may mark the concurrent bag24and local lists30for collection by a garbage collector (not shown). In other embodiments, runtime platform20may delete the concurrent bag24and local lists30in other suitable ways.

In some embodiments, a local list30of a thread22that is aborted may be reassigned to a thread22that attempts to add a new local list30to concurrent bag24. In these embodiments, the thread identifier28A in the dictionary26and the thread identifier42of a local list30of a thread22that is aborted are set to identify the thread22attempting to add a new local list30. The existing local list30is then used by the thread22instead of creating a new local list30.

FIG. 4Ais a flow chart illustrating an embodiment of a method for using a local list30in concurrent bag24by a thread22that created the corresponding local list30. The embodiment ofFIG. 4Awill now be described with reference to the embodiments ofFIGS. 1 and 2.

InFIG. 4A, any time that a thread22that created a local list30seeks to perform an add operation or a remove operation on the corresponding local list30as indicated in a block70, the thread22sets the current operation indicator54of the corresponding local list30to identify the add operation or the remove operation as indicated in a block71. The thread22then accesses the synchronize indicator36to determine whether synchronization is to be used while performing the add operation or the remove operation as indicated in a block72. If the synchronize indicator36does not indicate that synchronization is to be used, then the thread22determines whether the local list30includes less than two data elements46by subtracting steal count52from count50as indicated in a block73.

If the synchronize indicator36does not indicate that synchronization is to be used and the local list30includes two or more data elements46, then the thread22performs the add operation or the remove operation on the local list30without synchronization as indicated in a block74. For an add operation, thread22adds a data element46to a designated end of the linked list and increments count50. For a remove operation, thread22removes a data element46from the designated end of the linked list and decrements count50. The designated end of the linked list is the end of the linked list that is not used by other threads22that may steal data elements46from the linked list. For example, a thread22may perform add and remove operations to the head of the linked list of data elements46where other threads22may steal from the tail of the linked list of data elements46. After completing the unsynchronized add or remove operation, the thread22clears the current operation indicator54as indicated in a block75.

If the synchronize indicator36indicates that synchronization is to be used or the local list30includes less than two data elements46, then the thread22clears the current operation indicator54as indicated in a block76. The thread22determines whether the local lock60of the corresponding local list30is available using lock taken indicator56as indicated in a block77. If not, then the thread22waits until the local lock60is available before acquiring the local lock60as indicated in a block78, performing the add operation or the remove operation (described above) with synchronization as indicated in a block79, and subsequently releasing the local lock60as indicated in a block80.

Depending on the actual use of concurrent bag24, accesses to a local list30by the thread22that created the local list30may be largely unsynchronized. Synchronization may be performed under designated circumstances (e.g., enumeration as described below) that are indicated by the synchronize indicator36and to ensure thread safety (e.g., when the linked list includes less than two data elements46).

FIG. 4Bis a flow chart illustrating an embodiment of a method for using a local list30in concurrent bag24by a thread22other than the thread22that created the corresponding local list30. The embodiment ofFIG. 4Bwill now be described with reference to the embodiments ofFIGS. 1 and 2.

InFIG. 4B, a thread22may access a local list30other than a local list30created by the thread22using dictionary26as indicated in a block81. When a local list30created by the thread22does not include any data elements46(i.e., the count50minus the steal count52is zero), the thread22may attempt to steal a data element46from another local list30. The thread22accesses one or more entries28in dictionary26until the thread22identifies local list30with a data element46that may be stolen as indicated in a block82. A local list30includes a data element46that may be stolen if the head indicator44of the local list30is not equal to null. The thread22may access the entries28in the order that the entries appear in dictionary28or other suitable order until a local list30with a data element46that may be stolen is identified.

Once a thread22identifies a local list30with a data element46that may be stolen, the thread22determines whether the corresponding local lock60of the local list30is available using lock taken indicator56as indicated in a block83. If not, then the thread22waits until the local lock60is available before acquiring the local lock60as indicated in a block84. The thread22then waits until any unsynchronized remove operations complete by waiting until the current operation indicator54is not set to indicate a remove operation as indicated in a block85. After all unsynchronized remove operations complete, the thread22again ensures that a data element46to steal is present as indicated in a block86. If not, then the thread22releases the local lock60as indicated in a block87and repeats the function of block81. If so, then the thread22steals a data element46from the local list30and incrementing the steal count52of the local list as indicated in a block88, and subsequently releases the local lock60as indicated in a block89. Stealing, as just described, is performed with synchronization because more than one thread22may attempt to steal from the same local list30.

FIG. 5is a flow chart illustrating an embodiment of a method for performing an operation involving enumeration of concurrent bag24. The embodiment ofFIG. 5will now be described with reference to the embodiments ofFIGS. 1 and 2where a thread22calls an operation that involves enumeration of concurrent bag24. The embodiment ofFIG. 5will be described as being performed by runtime platform20. In other embodiments, some or all of the functions ofFIG. 5, or portions thereof, may be performed by process12, kernel14, and/or other components of the computer system (not shown).

InFIG. 5, runtime platform20determines whether global lock34of concurrent bag24is available as indicated in a block90. If not, then the runtime platform20waits until global lock34is available before acquiring global lock34to prevent any new local lists30from being added to concurrent bag24as indicated in a block91. Runtime platform20sets the local lists30to synchronize using the synchronize indicator36to cause any subsequent operations on the local lists30to be synchronized as indicated in a block92and begins acquiring local locks60of each local list30as indicated in a block93.

Runtime platform20waits until all local locks are acquired as indicated in a block94and all unsynchronized operations are complete as indicated in a block95before performing the operation that involves enumeration. For each local list30, runtime platform20waits until both the local lock60is acquired and the current operation indicator54indicates that no operation is being performed. After the local lock60is acquired, no unsynchronized operations (e.g., add or remove operations) may be started by a thread22until the local lock60is released. The thread22may, however, have started an unsynchronized add or remove operation prior to the local lock60being acquired by runtime platform20. Accordingly, runtime platform20waits until the current operation indicator54of the local list30indicates that no operation is being performed to ensure that any unsynchronized add or remove operation completes before beginning the enumeration.

After all local locks are acquired and all unsynchronized operations on all local lists30are complete, runtime platform20performs the operation that involves the enumeration as indicated in a block96. By acquiring the global lock34and all local locks60in blocks90-95, runtime platform20effectively freezes concurrent bag24to prevent any new local lists30from being added and any data elements from being added to, removed from, or stolen from any local lists30. With the concurrent bag24frozen, runtime platform20proceeds with enumerating the concurrent bag24by accessing and enumerating the data elements46in each local list30. Runtime platform20locates the first local list30using the list identifier28B in the first entry28in dictionary26. Upon locating the first local list30, runtime platform20accesses each data element46in the linked list from the data element46(1) identified by the head indicator44through the data element46(1) identified by the tail indicator48. When the tail indicator48is reached, runtime platform20accesses the next list identifier32to identify the next local list30and repeats the process of enumerating the data elements46in this next local list30. Runtime platform20continues identifying and enumerating local lists30until the local list30with the next list identifier32that is null is reached. At this point, runtime platform20has completed the enumeration part of the operation and may proceed to complete the overall operation.

The overall operation may be one or more of a Count operation, a CopyTo operation, a ToArray operation, or other suitable operation that involves enumeration. In a Count operation, runtime platform20uses the enumeration to count the number of data elements46in all local lists30in the concurrent bag24and returns the count to the thread22that called the Count operation. For a CopyTo operation, runtime platform20enumerates the concurrent bag24to allow the concurrent bag24to be copied to a specified location. Runtime platform20copies the concurrent bag24to the specified location and returns a confirmation indicator to the thread22that called the CopyTo operation. For a ToArray operation, runtime platform20enumerates the concurrent bag24to allow the concurrent bag24to be copied to a specified array. Runtime platform20copies the concurrent bag24to the specified array and returns a confirmation indicator to the thread22that called the ToArray operation.

Subsequent to performing the operation, runtime platform20releases local locks60of each local list30as indicated in a block97, sets the local lists30to not synchronize using the synchronize indicator36as indicated in a block98, and releases global lock34as indicated in a block99. By doing so, runtime platform20unfreezes the concurrent bag24to allow processing of the data elements46by threads22to resume.

FIG. 6is a block diagram illustrating an embodiment of a computer system100configured to implement runtime environment10(shown inFIG. 1) that allows process12to execute with multiple concurrent threads22.

Computer system100includes one or more processor packages102, a memory system104, zero or more input/output devices106, zero or more display devices108, zero or more peripheral devices110, and zero or more network devices112. Processor packages102, memory system104, input/output devices106, display devices108, peripheral devices110, and network devices112communicate using a set of interconnections114that includes any suitable type, number, and configuration of controllers, buses, interfaces, and/or other wired or wireless connections.

Computer system100represents any suitable processing device configured for a general purpose or a specific purpose. Examples of computer system100include a server, a personal computer, a laptop computer, a tablet computer, a personal digital assistant (PDA), a mobile telephone, and an audio/video device. The components of computer system100(i.e., processor packages102, memory system104, input/output devices106, display devices108, peripheral devices110, network devices112, and interconnections114) may be contained in a common housing (not shown) or in any suitable number of separate housings (not shown).

Processor packages102include processing resources16(1)-16(N). Each processing resource16in processor packages102is configured to access and execute instructions stored in memory system104. The instructions may include a basic input output system (BIOS) or firmware (not shown), process12, kernel14, resource management layer18, and runtime platform20. Each processing resource16may execute the instructions in conjunction with or in response to information received from input/output devices106, display devices108, peripheral devices110, and/or network devices112.

Memory system104includes any suitable type, number, and configuration of volatile or non-volatile storage devices configured to store instructions and data. The storage devices of memory system104represent computer readable storage media that store computer-executable instructions including process12, kernel14, resource management layer18, runtime platform20, and other processes.

Memory system104stores instructions and data received from processor packages102, input/output devices106, display devices108, peripheral devices110, and network devices112. Memory system104provides stored instructions and data to processor packages102, input/output devices106, display devices108, peripheral devices110, and network devices112. The instructions are executable by a computer system to perform the functions and methods of process12, kernel14, resource management layer18, and runtime platform20described herein. Examples of storage devices in memory system104include hard disk drives, random access memory (RAM), read only memory (ROM), flash memory drives and cards, and magnetic and optical disks.

Process12includes instructions that are executable in conjunction with kernel14, resource management layer18, and/or runtime platform20to cause desired operations to be performed by computer system100as described above with reference toFIG. 1.

Computer system100boots and executes kernel14. Kernel14includes instructions executable by processing resources16to manage the components of computer system100and provide a set of functions that allow process12and other processes to access and use the components. In one embodiment, kernel14is a Windows operating system. In other embodiments, kernel14is another operating system suitable for use with computer system100.

Resource management layer18includes instructions that are executable in conjunction with kernel14to allocate resources of computer system100including processing resources16as described above with reference toFIG. 1. Resource management layer18may be included in computer system100as a library of functions available to process12and other processes or as an integrated part of kernel14.

Runtime platform20includes instructions that are executable in conjunction with kernel14and resource management layer18to generate runtime environment10and provide runtime functions to process12and other processes as described above with reference toFIG. 1.

Input/output devices106include any suitable type, number, and configuration of input/output devices configured to input instructions or data from a user to computer system100and output instructions or data from computer system100to the user. Examples of input/output devices106include a keyboard, a mouse, a touchpad, a touchscreen, buttons, dials, knobs, and switches.

Display devices108include any suitable type, number, and configuration of display devices configured to output textual and/or graphical information to a user of computer system100. Examples of display devices108include a monitor, a display screen, and a projector.

Peripheral devices110include any suitable type, number, and configuration of peripheral devices configured to operate with one or more other components in computer system100to perform general or specific processing functions.

Network devices112include any suitable type, number, and configuration of network devices configured to allow computer system100to communicate across one or more networks (not shown). Network devices112may operate according to any suitable networking protocol and/or configuration to allow information to be transmitted by computer system100to a network or received by computer system100from a network.