usersort.c

openPBS的开放源代码

	if (job1->walltime > job2->walltime)
	    return 1;
	if (job1->walltime < job2->walltime)
	    return -1;
    }

    /* Oldest to youngest. */
    if (job1->eligible > job2->eligible)
	return -1;

    if (job1->eligible < job2->eligible)
	return 1;

    /* Cannot decide based on the cpu or walltime requests. */
    return 0;
}
/*
 * old qsort() function to order jobs during non-primetime.
 *
 * Order non-interactive (batch) jobs before interactive jobs.  If both
 * jobs are batch or both are interactive, sort from biggest to smallest
 * CPU requested.
 */
static int
compare_nonprime_batch_old(const void *e1, const void *e2)
{
    Job    *job1 = (Job *)e1;
    Job    *job2 = (Job *)e2;

    /* Batch jobs before interactive. */
    if ((job1->flags & JFLAGS_INTERACTIVE) !=
	(job2->flags & JFLAGS_INTERACTIVE)) 
    {
	return (job1->flags & JFLAGS_INTERACTIVE) ? 1 : -1;
    }

    /* Biggest to smallest. */
    if (job1->nodes > job2->nodes)
	return -1;
    if (job1->nodes < job2->nodes)
	return 1;

    /* Oldest to youngest. */
    if (job1->eligible > job2->eligible)
	return -1;

    if (job1->eligible < job2->eligible)
	return 1;

    return 0;
}
#endif /* HISTORICAL_CODE */

/*
 * qsort() function to order running jobs.
 *
 * Order running jobs by remaining runtime from soonest-ending to latest-
 * ending.  Jobs end up in order of time of completion (first to complete
 * first).
 */
static int
compare_running(const void *e1, const void *e2)
{
    Job    *job1 = *(Job **)e1;
    Job    *job2 = *(Job **)e2;

    if (job1->time_left > job2->time_left)
	return 1;

    if (job1->time_left < job2->time_left)
	return -1;
	
    return 0;
}

/* 
 * Permutation of the "normal" jobs -- inputs are the sorted list of users
 * who own the jobs & the list of jobs as sorted by 'sort_jobs_1st()',
 * This function uses the position of the job's owner in the user list and
 * and the [decayed] past-usage information to rearrange the job list in a
 * _highly_ nontrivial manner [best understood by perusing the actual code]
 */
static void
sort_jobs_2nd(void)
{
    struct Uinfo *ulist;
    char   *id = "sort_jobs_2nd";
    char   *group, *name;
    char    tmp[MAX_TXT];
    Job   **jlist1;
    Job   **jlist2;
    int     ndxU = 0;
    int     ndxJ1 = 0;
    int     ndxJ2 = 0;
    int     chosen_one;
    double  bump_usage;
    size_t  nbytes;
    int     i;

    if (nUsers == 0 || nnormalQ == 0)
	return;			/* There's nothing to do. */

    /* Allocate space for and make a copy of the Users list. */
    ulist = malloc(nUsers * sizeof *ulist);
    if (!ulist) {
	log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER,
		   id, "malloc(ulist)");
	return;
    }
    for (i = 0; i < nUsers; ++i)
	ulist[ndxU++] = Users[i];

    /* Allocate space for two copies of the job list. */
    jlist1 = malloc(nnormalQ * sizeof *normalQ);
    if (!jlist1) {
	free(ulist);
	log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER,
		   id, "malloc(jlist1)");
	return;
    }
    jlist2 = malloc(nnormalQ * sizeof *normalQ);
    if (!jlist2) {
	free(ulist);
	free(jlist1);
	log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER,
		   id, "malloc(jlist2)");
	return;
    }

    /* 
     * Make a copy of the job list in jlist1.  The permuted list will be
     * built in jlist2, then nnormalQ will be pointed to the new list in
     * jlist2.  jlist1 is consumed during the permutation.
     */
    for (i = 0; i < nnormalQ; ++i)
	jlist1[ndxJ1++] = normalQ[i];

    chosen_one = 0;
    while (ndxJ1 > 0) {
	/* Find the user with the least usage [past & projected] */
	for (i = 0; i < ndxU; ++i)
	    if (ulist[i].nodehours < ulist[chosen_one].nodehours)
		chosen_one = i;

	/* Break the 'group:user' tuple into its constituents. */
	strcpy(tmp, ulist[chosen_one].name);
	group = strtok(tmp, ":");
	name  = strtok(NULL, " \t\n");

	/* Find the first job in the list owned by that user. */
	for (i = 0; i < ndxJ1; ++i) {

	    /* 
	     * Ignore jobs that do not belong to this group:user tuple.
	     */
	    if ((strcmp(jlist1[i]->group, group) != 0) || 
		(strcmp(jlist1[i]->owner, name) != 0))
	    {
		continue;
	    }

	    /* Compute new usage data, assuming this job will be run. */
	    /* commented out as we experiment with the new past usage
	     * charge algorithm

	       bump_usage = jlist1[i]->walltime / 3600.0;
	       if (bump_usage < 1.0)
		   bump_usage = 1.0;
	       bump_usage *= jlist1[i]->nodes;
	       ulist[chosen_one].nodehours += bump_usage;
	     */

     	    if (jlist1[i]->walltime > (20*60))	/* greater than 20 minutes */
	         bump_usage = 10.0;
            else
	         bump_usage = 1.0;
	    ulist[chosen_one].nodehours += bump_usage;

	    /* 
	     * Copy this job from jlist1 to the next slot in jlist2, then
	     * remove it from jlist1.
	     */
	    jlist2[ndxJ2] = jlist1[i];
	    if (i + 1 < ndxJ1) {
		nbytes = (ndxJ1 - (i + 1)) * sizeof *jlist1;
		memmove(jlist1 + i, jlist1 + (i + 1), nbytes);
	    }
	    --ndxJ1;
	    ++ndxJ2;

	    /*
	     * If no more jobs belong to this user, then remove the user's
	     * entry from the local copy of the user list.  Then go back
	     * and do the whole permutation again with the next user.
	     */
	    ulist[chosen_one].jobcount --;
	    if (ulist[chosen_one].jobcount == 0) {
		if (chosen_one + 1 < ndxU) {
		    nbytes = (ndxU - (chosen_one + 1)) * sizeof *ulist;
		    memmove(ulist + chosen_one,
			    ulist + (chosen_one + 1),
			    nbytes);
		}
		--ndxU;
		if (chosen_one >= ndxU)
		    chosen_one = 0;
	    } else if (++chosen_one >= ndxU)
		chosen_one = 0;
	    break;
	}
    }

    /* Free storage for the depleted original user and job lists. */
    free(ulist);
    free(jlist1);

    /* 
     * Free the original normal job list, and point it at the new permuted 
     * job list. 
     */
    if (normalQ)
	free(normalQ);
    normalQ = jlist2;

    return;
}

/*
 * Sort the list of waiting jobs in order from largest to smallest,
 * breaking ties with walltime form shortest to longest.
 */
static void
sort_waiting_jobs(void)
{
    qsort(waitingQ, nwaitingQ, sizeof *waitingQ, compare_waiting);
    return;
}

/*
 * qsort() comparison function for ordering waiting jobs.
 *
 * Job walltimes are compared against schd_SMALL_QUEUED_TIME.  If both are 
 * either longer or shorter, than the tie is resolved by sorting from
 * largest to smallest CPU request.
 */
static int
compare_waiting(const void *e1, const void *e2)
{
    Job    *job1 = *(Job **)e1;
    Job    *job2 = *(Job **)e2;
    int     cmp1;
    int     cmp2;

    cmp1 = job1->walltime - schd_SMALL_QUEUED_TIME;
    cmp2 = job2->walltime - schd_SMALL_QUEUED_TIME;

    /*
     * If both jobs are over or under the schd_SMALL_QUEUED_TIME, then
     * break the tie by sorting from largest to smallest CPU request.
     * Failing this, sort from oldest to youngest job.
     */
    if ((cmp1 >= 0 && cmp2 >= 0) || (cmp1 < 0 && cmp2 < 0)) {
	if (job1->nodes < job2->nodes)
	    return 1;
	if (job1->nodes > job2->nodes)
	    return -1;

	if (job1->eligible < job2->eligible)
	    return -1;
	if (job1->eligible > job2->eligible)
	    return 0;

	return 0;
    }

    /*
     * If the first job requests less than schd_SMALL_QUEUED_TIME (which
     * implies that the second requests more than schd_SMALL_QUEUED_TIME),
     * sort longest to shortest walltime, then by eligible time.
     */
    if (cmp1 < 0) {
	if (job1->walltime < job2->walltime)
	    return 1;
	if (job1->walltime > job2->walltime)
	    return -1;

	if (job1->eligible < job2->eligible)
	    return -1;
	if (job1->eligible > job2->eligible)
	    return 1;
	return 0;
    }

    return 1;
}

/*
 * Sort special jobs into descending order by number of nodes requested.
 */
static void
sort_special_jobs(void)
{
    qsort(specialQ, nspecialQ, sizeof *specialQ, special_ordering);
    return;
}

#ifdef SORT_DEDTIME_JOBS
/*
 * sort 'dedtime' jobs: descending order by number of nodes requested.
 */
static void
sort_dedtime_jobs(void)
{
    qsort(dedtimeQ, ndedtimeQ, sizeof *dedtimeQ, special_ordering);
    return;
}
#endif /* SORT_DEDTIME_JOBS */

/*
 * qsort() function to sort jobs from largest to smallest by number of
 * CPUs requested.
 */
static int
special_ordering(const void *e1, const void *e2)
{
    Job    *job1 = *(Job **)e1;
    Job    *job2 = *(Job **)e2;

    if (job1->nodes > job2->nodes)
	return -1;
    if (job1->nodes < job2->nodes)
	return 1;
    return 0;
}

/* 
 * This function creates a new linked list from the Job structs pointed to 
 * by the arrays of Job pointers.  Note that the reassembly is carried out
 * in place - only the links are modified, there is no allocation or freeing
 * other than at the end to free all the sublists.
 *
 * The final list will be reassembled and ordered as: 
 *
 *      running, outstanding waiting, special, normal, dedicated
 */
static Job *
make_job_list(void)
{
    Job    list_seed, *joblist, *jobtail;
    int    i;

    memset(&list_seed, 0, sizeof(list_seed));

    /*
     * "Seed" the linked list by pointing to a bogus initial element.
     * Since the jobtail->next pointer will always be valid (either it
     * hangs off the seed or a real job) this simplifies the following
     * list operations considerably.
     */
    joblist = &list_seed;
    jobtail = &list_seed;
    jobtail->next = NULL;

    /* Walk the running jobs and place them on the list. */
    for (i = 0; i < nJRs; i++)
	jobtail = jobtail->next = runningJobs[i];

    /* Walk the waiting jobs and place them on the list. */
    for (i = 0; i < nwaitingQ; i++)
	jobtail = jobtail->next = waitingQ[i];

    /* Walk the special queue jobs and place them on the list. */
    for (i = 0; i < nspecialQ; i++)
	jobtail = jobtail->next = specialQ[i];

    /* Walk the normal jobs and place them on the list. */
    for (i = 0; i < nnormalQ; i++)
	jobtail = jobtail->next = normalQ[i];

    /* Walk the dedicated queue jobs and place them on the list. */
    for (i = 0; i < ndedtimeQ; i++)
	jobtail = jobtail->next = dedtimeQ[i];

    /* Place any remaining jobs on the end of the list. */
    for (i = 0; i < notherQ; i++)
        jobtail = jobtail->next = otherQ[i];
 
    /* Terminate the last element on the list with a NULL next pointer. */
    jobtail->next = NULL;

    /* Free any storage allocated for the lists. */
    if (runningJobs)
	free(runningJobs); 

    if (dedtimeQ)
	free(dedtimeQ);

    if (specialQ)
	free(specialQ);

    if (waitingQ)
	free(waitingQ);

    if (normalQ)
	free(normalQ);

    if (otherQ)
	free(otherQ);

    /* And reset all the values. */
    runningJobs = specialQ = dedtimeQ = waitingQ = normalQ = otherQ = NULL;
    nJRs = nJQs = ndedtimeQ = nspecialQ = nwaitingQ = nnormalQ = notherQ = 0;

    /*
     * The first element on joblist is the pointer to the list_seed.  It's
     * next pointer points to the head of the real list - return that.
     */
    return (joblist->next);
}

static char *
make_grp_usr_tuple(Job *job)
{
    static char tuple[PBS_MAXUSER + MAX_GROUP_NAME_SIZE + 1 + 1];

    strncpy(tuple, job->group ? job->group : unknown, MAX_GROUP_NAME_SIZE);
    strcat(tuple, ":");
    strncat(tuple, job->owner ? job->owner : unknown, PBS_MAXUSER);

    return tuple;
}

#ifdef USERSORT_DEBUG
static int
print_jobs(Job *joblist)
{
    char   *id = "pntJ";
    Job    *job;

    if (joblist) {
	log_record(PBSEVENT_SCHED, PBS_EVENTCLASS_SERVER, id,
		   "Sorted/Ordered Job List:");
	for (job = joblist; job != NULL; job = job->next) {
	    sprintf(log_buffer, "%s %c owner=%s\tnodes=%d q=%s",
		 job->jobid, job->state, job->owner, job->nodes, job->qname);
	    log_record(PBSEVENT_SCHED, PBS_EVENTCLASS_SERVER, id, log_buffer);
	}
    }
    return 0;
}
#endif /* USERSORT_DEBUG */

#ifdef DEAD_CODE_MAY_19_1998
/*==========================================================*/
/* determine whether user already has too many jobs running */
/*==========================================================*/
static int
too_many_running_jobs(char *user, char *group)
{
    int     i;
    char    tuple[MAX_TXT + 1];

    sprintf(tuple, "%s:%s", group, user);
    for (i = 0; i < nUsers; ++i)
	if (!strcmp(Users[i].name, tuple)) {
	    return Users[i].running_jobs >= schd_MAX_USER_RUN_JOBS;
	}
    /* didn't find this user -- must not have any running... */
    return 0;
}
#endif /* DEAD_CODE_MAY_19_1998 */

#ifdef DEAD_CODE_MAY_19_1998
/*=========================================================*/
/* in PrimeTime, interactive jobs go ahead of batch jobs - */
/* within each of those subgroups, the jobs are ordered by */
/* time requested, so shorter jobs go first                */
/*=========================================================*/
static int
compare_old_prime(const void *e1, const void *e2)
{
    Job    *job1 = (Job *)e1;
    Job    *job2 = (Job *)e2;

    if ((job1->flags & JFLAGS_INTERACTIVE) ==
	(job2->flags & JFLAGS_INTERACTIVE)) {
	if (job1->walltime > job2->walltime)
	    return 1;
	else if (job1->walltime < job2->walltime)
	    return -1;
	else
	    return 0;
    } else
	return (job1->flags & JFLAGS_INTERACTIVE) ? -1 : 1;
}
#endif /* DEAD_CODE_MAY_19_1998 */

#ifdef DEAD_CODE_MAY_19_1998
/*======================================================================*/
/* during the Interactive phase of NonPrimeTime, interactive jobs move  */
/* to the head of the list and each sublist is ordered by the requested */
/* nodes, so that bigger jobs are given preference                      */
/*                                                                      */
/* THIS ROUTINE IS CURRENTLY NOT USED -- Retained for future use        */
/*======================================================================*/
static int
compare_nonprime_inter(const void *e1, const void *e2)
{
    Job    *job1 = (Job *)e1;
    Job    *job2 = (Job *)e2;

    if ((job1->flags & JFLAGS_INTERACTIVE) ==
	(job2->flags & JFLAGS_INTERACTIVE)) {
	if (job1->nodes > job2->nodes)
	    return -1;
	else if (job1->nodes < job2->nodes)
	    return 1;
	else
	    return 0;
    } else
	return (job1->flags & JFLAGS_INTERACTIVE) ? -1 : 1;
}
#endif /* DEAD_CODE_MAY_19_1998 */