Method and system for performing fair-share preemption
A method and apparatus for performing fair-share preemption in a distributed computing environment is disclosed. The invention allows the suspension of jobs in a preempt-able set and the transfer of their respective resources, e.g. either hardware or software resources, to jobs in a preempting set. These activities are performed, all while assuring fairness among jobs scheduled to be executed and optimizing the use of available resources. In a preferred embodiment, the preempt-able and the preempting sets may include jobs characterized by, for example, job priorities, job ownership, or combinations thereof.
1. A method for performing fair-share job preemption for a plurality of jobs in a distributed computing environment, comprising the steps of:
maintaining a set of preempt-able jobs and a set of preempting jobs, wherein use of at least a resource in the distributed computing environment by a preempt-able job is revokable, and wherein a preempting job is allowed to start using said at least a resource in the distributed computing environment if said resource is being currently used by at least one preempt-able job;
determining for each preempt-able job of the plurality of jobs a historical share respective of total preemption time of said each job in a fair-share window, wherein a fair-share window is a configurable time period value in which said each job was preempted;
determining for each user a current actual share respective of total preemption time of each user's jobs being preempted at the end of said fair-share window; and
prioritizing preempt-able jobs based on said historical share of said each job and said current actual share of said each user.
2. The method of claim 1 , wherein said at least a resource comprises any of: a central processing unit, a memory, and a software license.
3. The method of claim 1 , said steps of determining said historical share further comprising the steps of:
computing, for each job, a total preemption time (TPT) in said fair-share window, wherein said TPT corresponds to an accumulative time in which said each job was suspended due to preemption; and
computing a suffer time for a user, wherein said suffer time is respective of a total preemption time for a group of jobs owned by a specific user.
4. The method of claim 3 , said steps of computing said suffer time for a user further comprising the steps of:
summing TPTs of jobs that belong to said user; and
dividing said suffer time of said user by suffer times of all users.
5. The method of claim 1 , wherein said fair-share window comprises a predetermined time-interval.
6. The method of claim 1 , said steps of wherein computing said current share further comprising the steps of:
dividing a number of preempted jobs of a said user that are preempted by a total number of jobs that are preempted in the distributed computing environment.
7. The method of claim 1 , wherein said prioritizing comprises computation of a Δ share is computed using the following equation:
Δ share user-α =(target-share− Sw user-α )+(target-share− Sc user-α )
wherein said target-share comprises a pre-configurable parameter that defines a percentage of time slots to allocate for each user, said Sw user-α is said historical share of a user, and said Sc user-α is said current share of the user.
8. The method of claim 7 , said step of prioritizing said preempt-able jobs further comprising the step of:
assigning a priority ranking to a preempt-able job according to the Δ share computed for a user that owns said job.
9. The method of claim 1 , wherein said fair-share preemption comprises any of: a priority-based preemption or an ownership-based preemption.
10. A computer program product for enabling operation of a method for performing fair-share job preemption for a plurality of jobs in a distributed computing environment, the computer program product having computer instructions on a memory, the instructions comprising the steps of:
maintaining a set of preempt-able jobs and a set of preempting jobs, wherein use of at least a resource in the distributed computing environment by a preempt-able job is revokable, and wherein a preempting job is allowed to start using said at least a resource in the distributed computing environment if said resource is being currently used by at least one preempt-able job;
determining for each preempt-able job of the plurality of jobs a historical share respective of total preemption time of said each job in a fair-share window, wherein a fair-share window is a configurable time period value in which said each job was preempted;
determining for each user a current actual share respective of total preemption time of each user's jobs being preempted at the end of said fair-share window; and
prioritizing preempt-able jobs based on said historical share of said each job and said current actual share of said each user.
11. The computer program product of claim 10 , wherein said at least a resource comprises any of: a central processing unit (CPU), a memory, and a software license.
12. The computer program product of claim 10 , said steps of determining said historical share further comprising the steps of:
computing, for each job, a total preemption time (TPT) in said fair-share window, wherein said TPT corresponds to an accumulative time in which said each job was suspended due to preemption; and
computing a suffer time for a user, wherein said suffer time is respective of a total preemption time for a group of jobs owned by a specific user.
13. The computer program product of claim 12 , said steps of computing said suffer time for said user comprising the steps of:
summing TPTs of jobs that belong to said user; and
dividing said suffer time for said user by the suffer times of all users.
14. The computer program product of claim 10 , wherein said fair-share window comprises a predetermined time-interval.
15. The computer program product of claim 10 , said steps of wherein computing said current share further comprising the steps of:
dividing a number of preempted jobs of a said user that are preempted by a total number of jobs that are preempted in the distributed computing environment.
16. The computer program product of claim 10 , wherein said prioritizing comprises computation of a Δ share is computed using the following equation:
Δ share user-α =(target-share− Sw user-α )+(target-share− Sc user-α )
wherein said target-share comprises a pre-configurable parameter that defines a percentage of time slots to allocate for each user, said Sw user-α is said historical share of a user, and said Sc user-α is said current share of the user.
17. The computer program product of claim 16 , said steps of prioritizing said preempt-able jobs further comprising the steps of:
assigning a priority ranking to a preempt-able job according to the Δ share computed for a user that owns said job.
18. The computer program product of claim 16 , wherein said fair-share preemption comprises any of: a priority-based preemption and an ownership-based preemption.
19. A computer system for performing job fair-share preemption for a plurality of jobs in a distributed computing environment, the computer system comprising a processor and a memory that is under control of said processor, said system comprising:
means for maintaining a set of preempt-able jobs and a set of preempting jobs, wherein use of at least a resource in the distributed computing environment by a preempt-able job is revokable, and wherein a preempting job is allowed to start using said at least a resource in the distributed computing environment if said resource is being currently used by at least one preempt-able job;
means for determining for each preempt-able job of the plurality of jobs a historical share respective of total preemption time of said each job in a fair-share window, wherein a fair-share window is a configurable time period value in which said each job was preempted;
means for determining for each user a current actual share respective of total preemption time of each user's jobs being preempted at the end of said fair-share window; and
means for prioritizing preempt-able jobs based on said historical share of said each job and said current actual share of said each user.
20. The system of claim 19 , wherein said at least a resource comprises any of: a central processing unit (CPU), a memory, and a software license.
21. The system of claim 19 , said means for determining said historical share further comprising:
means for computing, for each job, a total preemption time (TPT) in said fair-share window, wherein said TPT corresponds to an accumulative time in which said each job was suspended due to preemption; and
means for computing a suffer time for a user, wherein said suffer time is respective of a total preemption time for a group of jobs owned by a specific user.
22. The system of claim 21 , said means for computing said suffer time for said user comprising:
means for summing TPTs of jobs belong to said user; and
means for dividing said suffer time for said user by the suffer times for all users.
23. The system of claim 19 , said fair-share window comprising a predetermined time-interval.
24. The system of claim 19 , said means for computing said current share further comprising:
means for dividing a number of preempted jobs of a said user that are preempted by a total number of jobs that are preempted in the distributed computing environment.
25. The system of claim 19 , wherein said means for prioritizing comprises compute of a Δ share is computed using the following equation:
Δ share user-α =(target-share− Sw user-α )+(target-share− Sc user-α )
wherein said target-share comprises a pre-configurable parameter that defines a percentage of time slots to allocate for each user, said Sw user-α is said historical share of a user, and said Sc user-α is said current share of the user.
26. The system of claim 25 , said means for prioritizing said preempt-able jobs further comprising:
means for assigning a priority ranking to a preempt-able job according to a Δ share computed for a user that owns said job.
27. The system of claim 19 , said means for fair-share preemption comprises any of: a priority-based preemption and an ownership-based preemption.
28. The system of claim 19 , wherein said system is coupled between a plurality of workstations and a plurality of remote computers.
29. The system of claim 28 , wherein said remote computers are coupled to a scheduler.
30. The system of claim 29 , wherein said scheduler comprises any of: a batch scheduler and an event driven scheduler.
31. The system of claim 19 , further comprising:
a job queue for maintaining said set of preempt-able jobs and said set of preempting jobs.