Lock-free job scheduler for multi-processor systems
US9104500B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 29, 2011 |
| Grant date | Aug 11, 2015 |
| Priority date | — |
| Expiry date | Feb 28, 2034 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2209/486
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.