Re: [Condor-users] Scheduling algorithm of condor?

[Erik Paulson <epaulson@xxxxxxxxxxx>]

On Tue, Jun 14, 2005 at 04:29:28PM -0400, Alex wrote:
> Hi all,
> 
> I want to build a event-driven simulator simulating the job queue of
> Condor. More exactly, the queue is used by jobs submitted GRAM of
> Globus Toolkit 4 only.
> 

That's not relevant to a model of the Condor queue. 

> Where can I find information about the scheduling algorithm that
> Condor is using? Is it using backfill?

No, Condor does not use backfill.

> Is it using wall clock time to
> determine the job length for backfill? Thanks.
> 

Condor doesn't know the job length time, so we don't specifically take it
into account. It's possible to include the wallclock time in the 
matchmaking system, but we won't compute a pool-wide schedule using it.

Condor schedules in different ways. First, it takes all users who have 
submitted jobs and calculates their priority. Then it totals the number of
resources available at the moment and using the ratios of the user priorities
it calculates the number of machines each user could get (what we call
their "pie slice". Then the Condor Matchmaker goes in user priority order 
and contacts each user, and asks for job information. 

The schedd(user) tells the matchmaker about a job, and the matchmaker
looks at available resources and creates a list of resources that "match"
the requirements expressions. Once it has a list of resources that match,
it sorts them according to the "rank" expressions of classads. If a
machine prefers a job, we assign the job to that machine, potentially
preempting a job that might already be running on that machine.
Otherwise, we give the job the machine it "ranks" highest. If the machine
it ranks highest is already running a job, we may preempt running job
for the new job - the default policy for preemption says that user has
to have a 20% better priority in order for preemption to succeed. If
the job has no preferences as to what sort of machine it gets, we give
it the first idle resource that meet its requirements.

This matchmaking cycle continues until the user has recieved all of the
machines in their "slice of pie", and then we contact the next highest
priority user (well, lowest priority, condor priorities are like golf)
and offer them their pie slice worth of machine. After we contacted 
users, we take any resources that might still be available, and recompute
the pie slice size, and repeat the cycle. We contiune "spinning the pie" 
until we run out of machines or all schedds say they're out of jobs. 

We do another sort of scheduling inside the condor_schedd - the schedd 
maintains its job queue listing in "job priority" order, which is on a 
per-user basis inside the schedd. So a user can say "when you try and matchmake
for resources on my behalf schedd, first try and find a resource for job A,
then try for job B."


See http://www.cs.wisc.edu/condor/manual/v6.7.8/2_7Priorities_Preemption.html#SECTION00372000000000000000
and
http://www.cs.wisc.edu/condor/manual/v6.7.8/3_5User_Priorities.html

You might want to read some of the earlier HPDC papers on Matchmaking too.

http://www.cs.wisc.edu/condor/publications.html

(I can't think of a paper where we specifically go into details on the
user priority calculations in details though) 

-Erik

> Regards,
> Alex
> 
> _______________________________________________
> Condor-users mailing list
> Condor-users@xxxxxxxxxxx
> https://lists.cs.wisc.edu/mailman/listinfo/condor-users