Work-stealing queues for parallel garbage collection

  • US 6,823,351 B1
  • Filed: 10/26/2000
  • Issued: 11/23/2004
  • Est. Priority Date: 05/15/2000
  • Status: Expired due to Term
First Claim
Patent Images

1. For employing a number of execution threads to perform garbage-collection work tasks of which the performance of at least some includes identifying further work tasks, a computer-implemented method that includes:

  • providing a double-ended work queue for each thread, each work queue having first and second ends, dividing the garbage-collection work tasks into identifiable task groups, assigning task groups to threads, and executing each thread by;

    pushing onto the first end of that thread'"'"'s work queue identifiers of garbage-collection work tasks identified by that thread, popping identifiers of garbage-collection work tasks from the first end of the thread'"'"'s work queue and performing the tasks that the thus-popped identifiers identify; and

    when that thread'"'"'s queue is empty, popping identifiers of garbage-collection work tasks from the second end of the work queue provided for another of the threads and performing the garbage-collection work task thereby identified.

View all claims

    Thank you for your feedback