Lock-free job scheduler for multi-processor systems

A method of scheduling and synchronizing job execution in a multi-core, multi-thread CPU comprising:

• maintaining a list of jobs awaiting execution and active jobs counters respectively indicating numbers of executing jobs and suspended jobs;
• assigning jobs on the list of jobs to available threads among a plurality of threads for execution, and updating said list and the active jobs counters;
• upon an executing parent job spawning one or more child jobs, updating said list of jobs with said child jobs, suspending execution of the parent job, incrementing a child jobs counter associated with the parent job and said active jobs counters according to the number of child jobs spawned;
• in response to the execution of each of said one or more child jobs completing, decrementing said child jobs counter, and upon said child jobs counter becoming zero, resuming execution of said suspended parent job, updating said list to remove said completed child jobs and to add said resuming parent job, updating said active jobs counters, and retrieving said resuming parent job from said list for execution by a thread;
• and
• wherein said foregoing maintaining, assigning, updating of said list, and updating of said child jobs counter and said active jobs counters are performed using atomic operations without use of processing locks.

Computer readable non-transitory storage medium for storing instructions for controlling the operation of a computer to schedule and synchronize a plurality of jobs for execution by a plurality of threads in a multi-processor system, comprising instructions for:

• maintaining a list of jobs awaiting execution and counts of current numbers of the jobs on the list, of suspended jobs and of executing jobs;
• assigning jobs on the list of jobs to available threads among the plurality of threads for execution;
• upon an executing parent job having dependencies, spawning one or more child jobs corresponding to said dependencies, suspending execution of said parent job, updating said list with said child jobs, and incrementing a child jobs count associated with said parent job with a number of the child jobs spawned, said suspending, said incrementing and said updating said list with said child jobs being performed by atomic operations without use of locks;
• decrementing said child jobs count upon each child job completing execution, said decrementing being performed by atomic operations without the use of locks, and resuming execution of said suspended parent job in response to said child jobs count associated with said parent job becoming zero, wherein said resuming execution of said parent job comprises adding said parent job to the list of jobs, and retrieving said parent job from said list for execution by a thread;
• and
• updating said list and said counts in response to jobs on the list being assigned, suspended jobs resuming execution and executing jobs being completed, said assigning, maintaining and updating being performed by atomic operations without the use of locks.