Determining a job group status based on a relationship between a generation counter value and a ticket value for scheduling the job group for execution
A job scheduler system includes one or more hardware processors, a memory including a job group queue stored in the memory, and a job scheduler engine configured to create a first job group in the job group queue, the first job group includes a generation counter having an initial value, receive a first request to steal the first job group, determine a state of the first job group based at least in part on the generation counter, the state indicating that the first job group is available to steal, based on the determining the state of the first job group, atomically increment the generation counter, thereby making the first job group unavailable for stealing, and alter an execution order of the first job group ahead of at least one other job group in the job group queue.
1. A system comprising:
one or more computer processors;
one or more computer memories;
one or more modules incorporated into the one or more computer memories, the one or more modules configuring the one or more computer processors to perform operations for scheduling computer jobs without using waiting locks for reading and writing to a set of data structures, the operations comprising:
atomically removing a plurality of jobs corresponding to a first job group from a job group queue, putting the job group on a job list stack, and leaving a first empty container on the job group queue, the first empty container corresponding to the first job group;
based on a determination that the first job group depends on a second job group, performing additional operations comprising:
based on a determination that the second job group is in a finished state, atomically pushing the plurality of jobs associated with the first job group onto an execution stack and pulling the plurality of jobs corresponding to the first job group from the execution stack in any order for execution;
based on a determination that the second job group is in a pushed state, atomically putting the plurality of jobs associated with the first job group into a second empty container on the job group queue, the second empty container corresponding to the second job group;
based on a determination that the second job group is in a queued state, performing a steal operation on the second job group and atomically putting the plurality of jobs corresponding to the first job group into the second empty container.
2. The system of claim 1 , the operations further comprising setting a finished generation count for the second job group equal to a starting generation count plus two increment counts, and wherein the second job group is considered to be in the queued state when a generation counter is equal to the finished generation count minus two increment count, the job group is considered to be in the pushed state when the generation counter is equal to the finished generation count minus the increment count, and the job group is considered to be in the finished state when the generation counter is equal to the finished generation count.
3. The system of claim 1 , wherein the putting of the plurality of jobs corresponding to the first job group into the second empty container includes reusing memory allocated for the second empty container such that an operating system call for allocation of additional memory is avoided.
4. The system of claim 1 , wherein memory associated with the second empty container is not deallocated when the second job group is in the finished state and when the second empty container is removed from the end of the queue.
5. The system of claim 1 , the operations further comprising, based on the determination that the second job group is in the finished state, finding the plurality of jobs corresponding to the first job group in the second empty container and atomically placing the plurality of jobs corresponding to the first job group on the execution stack.
6. The system of claim 4 , further comprising receiving a new set of jobs and creating a new job group that includes a plurality of individual jobs from the new set of jobs wherein the plurality of jobs do not depend on each other for execution and can be executed in any order, and placing the new job group within the second empty container, placing the second empty container at the beginning of the queue, and persisting a generation counter used for the second job group such that the generation counter is not reset.
7. The system of claim 2 , further comprising initializing a job counter to a count of the plurality of jobs of the first job group when the first job group is pushed onto the execution stack and incrementing the generation counter when the job counter is zero.
8. A method comprising:
performing operations for scheduling computer jobs without using waiting locks for reading and writing to a set of data structures, the operations comprising:
atomically removing a plurality of jobs corresponding to a first job group from a job group queue, putting the job group on a job list stack, and leaving a first empty container on the job group queue, the first empty container corresponding to the first job group;
based on a determination that the first job group depends on a second job group, performing additional operations comprising:
based on a determination that the second job group is in a finished state, atomically pushing the plurality of jobs associated with the first job group onto an execution stack and pulling the plurality of jobs corresponding to the first job group from the execution stack in any order for execution;
based on a determination that the second job group is in a pushed state, atomically putting the plurality of jobs associated with the first job group into a second empty container on the job group queue, the second empty container corresponding to the second job group;
based on a determination that the second job group is in a queued state, performing a steal operation on the second job group and atomically putting the plurality of jobs corresponding to the first job group into the second empty container, one or more modules incorporated into one or more computer memories, the one or more modules configuring one or more processors to implement the performing of the operations for schedule the computer jobs.
9. The method of claim 8 , the operations further comprising setting a finished generation count for the second job group equal to a starting generation count plus two increment counts, and wherein the second job group is considered to be in the queued state when a generation counter is equal to the finished generation count minus two increment count, the job group is considered to be in the pushed state when the generation counter is equal to the finished generation count minus the increment count, and the job group is considered to be in the finished state when the generation counter is equal to the finished generation count.
10. The method of claim 8 , wherein the putting of the plurality of jobs corresponding to the first job group into the second empty container includes reusing memory allocated for the second empty container such that an operating system call for allocation of additional memory is avoided.
11. The method of claim 8 , wherein memory associated with the second empty container is not deallocated when the second job group is in the finished state and when the second empty container is removed from the end of the queue.
12. The method of claim 8 , the operations further comprising, based on the determination that the second job group is in the finished state, finding the plurality of jobs corresponding to the first job group in the second empty container and atomically placing the plurality of jobs corresponding to the first job group on the execution stack.
13. The method of claim 11 , further comprising receiving a new set of jobs and creating a new job group that includes a plurality of individual jobs from the new set of jobs wherein the plurality of jobs do not depend on each other for execution and can be executed in any order, and placing the new job group within the second empty container, placing the second empty container at the beginning of the queue, and persisting a generation counter used for the second job group such that the generation counter is not reset.
14. The method of claim 9 , further comprising initializing a job counter to a count of the plurality of jobs of the first job group when the first job group is pushed onto the execution stack and incrementing the generation counter when the job counter is zero.
15. A non-transitory machine-readable medium storing a set of instructions that, when executed by one or more processors, causes the one or more processors to perform operations for scheduling computer jobs without using waiting locks for reading and writing to a set of data structures, the operations comprising:
atomically removing a plurality of jobs corresponding to a first job group from a job group queue, putting the job group on a job list stack, and leaving a first empty container on the job group queue, the first empty container corresponding to the first job group;
based on a determination that the first job group depends on a second job group, performing additional operations comprising:
based on a determination that the second job group is in a finished state, atomically pushing the plurality of jobs associated with the first job group onto an execution stack and pulling the plurality of jobs corresponding to the first job group from the execution stack in any order for execution;
based on a determination that the second job group is in a pushed state, atomically putting the plurality of jobs associated with the first job group into a second empty container on the job group queue, the second empty container corresponding to the second job group;
based on a determination that the second job group is in a queued state; performing a steal operation on the second job group and atomically putting the plurality of jabs corresponding to the first job group into the second empty container.
16. The non-transitory machine-readable medium of claim 15 , the operations further comprising setting a finished generation count for the second job group equal to a starting generation count plus two increment counts, and wherein the second job group is considered to be in the queued state when a generation counter is equal to the finished generation count minus two increment count; the job group is considered to be in the pushed state when the generation counter is equal to the finished generation count minus the increment count, and the job group is considered to be in the finished state when the generation counter is equal to the finished generation count.
17. The non-transitory machine-readable medium of claim 15 , wherein the putting of the plurality of jobs corresponding to the first job group into the second empty container includes reusing memory allocated for the second empty container such that an operating system call for allocation of additional memory is avoided.
18. The non-transitory machine-readable medium of claim 15 , wherein memory associated with the second empty container is not deallocated when the second job group is in the finished state and when the second empty container is removed from the end of the queue.
19. The non-transitory machine-readable medium of claim 15 , the operations further comprising, based on the determination that the second job group is in the finished state, finding the plurality of jobs corresponding to the first job group in the second empty container and atomically placing the plurality of jobs corresponding to the first job group on the execution stack.
20. The non-transitory machine-readable medium of claim 18 , the operations further comprising receiving a new set of jobs and creating a new job group that includes a plurality of individual jobs from the new set of jobs wherein the plurality of jobs do not depend on each other for execution and can be executed in any order, and placing the new job group within the second empty container, placing the second empty container at the beginning of the queue, and persisting a generation counter used for the second job group such that the generation counter is not reset.