Multi-threaded garbage collector employing cascaded memory arrays of task identifiers to implement work stealing queues for task identification and processing
US7016923B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 5, 2002 |
| Grant date | Mar 21, 2006 |
| Priority date | — |
| Expiry date | Mar 12, 2024 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99957
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A computer system employing a plurality of concurrent threads to perform tasks that dynamically identify further similar tasks employs a double-ended queue (“deque”) to list the dynamically identified tasks. If a thread's deque runs out of tasks while other threads' deques have tasks remaining, the thread whose deque has become empty will remove one or more entries from another thread's deque and perform the tasks thereby identified. When a thread's deque becomes too full, it may allocate space for another deque, transfer entries from its existing deque, place an identifier of the existing deque into the new deque, and adopt the new deque as the one that it uses for storing and retrieving task identifiers. Alternatively, it may transfer some of the existing deque's entries into a newly allocated array and place an identifier of that array into the existing deque. The thread thereby deals with deque overflows without introducing additional synchronization requirements or restricting the deque's range of use.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.