Enumeration of a concurrent data structure
AssigneeMicrosoft Corporation
InventorsEmad Omara, John J. Duffy
Life of this patent
Estimating the term…
Abstract
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.
Claims20
A computer readable storage medium storing computer-executable instructions that, when executed in a computer system, perform a method comprising:
- acquiring a global lock on a data structure that is accessible by a plurality of threads, the data structure including a set of local lists configured as a first linked list and a dictionary that identifies a location of each local list, and each of the set of local lists including a respective second linked list of data elements;
- preventing the plurality of threads from accessing the set of local lists without synchronization;
- and
- subsequent to any unsynchronized operations on the set of local lists completing, performing an enumeration of each of the respective second linked lists of data elements of the local lists using the dictionary.
A method performed in a process executing on a computer system, the method comprising:
- creating a data structure that is accessible to first and second threads concurrently, the data structure including a dictionary;
- adding first and second local lists from the first and the second threads, respectively, to the data structure and first and second identifiers of the first and the second local lists, respectively, to the dictionary;
- storing an identifier in the first local list that identifies a location of the second local list;
- adding a first plurality of data elements from the first thread to the first local list as a first linked list;
- accessing a first one of the first plurality of data elements from a first end of the first linked list with the first thread;
- and
- stealing a second one of the first plurality of data elements from a second end of the first linked list with the second thread.
A method performed by a computer system executing a process, the method comprising:
- acquiring a global lock on a data structure that is accessible by a first and second threads, the data structure including a first and a second local lists and a dictionary with first and second entries that identify first and second locations, respectively, of the first and the second local lists, respectively, the first and the second local lists including a first and second linked lists of data elements, respectively, and the first local list including a list identifier the second location of the second local list;
- preventing the first and the second threads from accessing the first and the second local lists without synchronization;
- and
- subsequent to any unsynchronized operations on the first and the second local lists completing, performing an enumeration of the first and the second linked lists of data elements of the first and the second local lists using the first entry and the list identifier.
Dependencies are inferred from the claim text.