Lock-free job scheduler for multi-processor systems

Abstract

A scalable job scheduler for a multi-thread, multi-processor system synchronizes and schedules jobs for execution by using lists and jobs counters for the numbers of active jobs. It minimizes synchronization overhead by using atomic operations for incrementing and decrementing the counters. The scheduler assigns jobs for execution, and can awake up an available thread to pick up work. A parent job spawns child jobs and maintains a job counter. Spawned jobs are added to the list for execution and the counter of waiting jobs is incremented. When execution of a job begins, the parent's counter of outstanding child jobs is decremented. A parent job is suspended until its counter of uncompleted spawned child jobs reaches zero. As a job is completed, the scheduler decrements the counter of active jobs, and assigns the next job in the queue to an available thread.