usersort.c

openPBS的开放源代码

     * Populate the arrays of pointers with the jobs
     */
    dedtimeI = normalI = otherI = runningI = 0;

    for (this = jobs; this != NULL; this = this->next) {
	if (this->state != 'R' && this->state != 'Q') {
	    otherQ[otherI++] = this;
	    continue;
	}

	if (this->state == 'R') {
	    runningJobs[runningI++] = this;
	    continue;
	}

	/* Does this job belong on the dedicated list? */
	if (this->flags & JFLAGS_DEDICATED) {
	    dedtimeQ[dedtimeI++] = this;
	    continue;
	}

	/* every other kind of job. */
	normalQ[normalI++] = this;
    }

    (void)sprintf(log_buffer,
	"run:%d norm:%d ded:%d othr: %d total:%d",
          runningI, normalI, dedtimeI, otherI,
	  runningI+ normalI+ dedtimeI+ otherI);
    log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER, id, log_buffer);
    DBPRT(("%s: %s\n", id, log_buffer));

    return (0);

malloc_failed:

    if (dedtimeQ) { free(dedtimeQ);	dedtimeQ = NULL; }
    if (normalQ)  { free(normalQ);	normalQ  = NULL; }
    if (otherQ)   { free(otherQ);	otherQ   = NULL; }
    nJRs = nJQs = 0;

    log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER, id, "malloc failed");
    return (-1);
}

/* 
 * Determine whether a queued job has waited so long that extra emphasis
 * should be placed on running this job.
 */
static int
is_outstanding(Job *job)
{
    /*
     * If it is currently primetime, consider an interactive job "waiting 
     * for a long time" if it has waited for more time than some constant
     * plus the time it requested.
     *
     * A batch job can wait for much longer than an interactive job.  Given
     * the ability to submit an interactive job, assume that if the user was
     * actually waiting for the job to start, they would submit it as inter-
     * active.
     * 
     * The lower-priority "background" jobs are not eligable for "long waiting
     * assistance".
     */
 
    if (!strcmp(job->oqueue, schd_BackgroundQueue))
	return(0);

    if (schd_INTERACTIVE_LONG_WAIT && job->flags & JFLAGS_INTERACTIVE) {
	if (job->eligible > (job->walltime + schd_INTERACTIVE_LONG_WAIT))
	    if (schd_prime_time(0))
		return (1);
    } else {
	if (schd_MAX_QUEUED_TIME && (job->eligible > schd_MAX_QUEUED_TIME))
	    return 1;
    }

#ifdef JAMES_DEBUG
    if (job->eligible > Min_Queued_Time)
	return job->walltime < schd_SMALL_QUEUED_TIME;
#endif /* JAMES_DEBUG */

    return 0;
}

/*
 * Construct a list of users who own one or more "normal" jobs, and count
 * the number of jobs they own.
 */
static void
get_users(void)
{
    char   *id = "get_users";
    Job    *job_ptr;
    char   *uname;
    char   *name;
    int     which;
    int     i;
    int     j;

    /*
     * Destroy any previously created list.
     */
    if (Users)
	free(Users);

    Users  = NULL;
    nUsers = 0;

    /* 
     * Walk the list of "normal" jobs, creating group/owner tuples for each
     * new user.
     */
    for (i = 0; i < nnormalQ; ++i) {

	job_ptr = normalQ[i];
	name = make_grp_usr_tuple(job_ptr);

	/* Is this a new entry in the list? */
	if (is_new_user(name, Users, nUsers, &which)) {

	    ++nUsers;

	    Users = realloc(Users, nUsers * sizeof *Users);
	    if (!Users) {
		log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER,
			   id, "realloc(Users)");
		return;
	    }
	    make_uinfo(name, &(Users[nUsers - 1]));
	} else {
	    Users[which].jobcount++;
	}
    }

    /* Now, walk the list of running jobs and record each user's count. */
    for (i = 0; i < nUsers; ++i) {
	uname = Users[i].name;
	for (j = 0; j < nJRs; ++j) {
	    job_ptr = runningJobs[j];
	    /* Create the name tuple for this user. */
	    name = make_grp_usr_tuple(job_ptr);

	    if (!strcmp(name, uname))
		Users[i].running_jobs++;
	    ++job_ptr;
	}
    }

    return;
}

/* Search the list of users, looking for 'user'. */
static int
is_new_user(char *user, struct Uinfo *list, int len, int *which)
{
    struct Uinfo *list_ptr = list;
    int     i;

    for (i = 0; i < len; ++i) {
	if (!strcmp(list_ptr->name, user)) {
	    *which = i;
	    return 0;
	}
	++list_ptr;
    }

    return 1;
}

/* Build a record of the pertinent data about a job owner. */
static int
make_uinfo(char *user, struct Uinfo *uinfo)
{
    strncpy(uinfo->name, user, sizeof(uinfo->name) - 1);
    uinfo->jobcount = 1;
    uinfo->running_jobs = 0;
    uinfo->nodehours = get_resource_usage(user);

    return 0;
}

/*
 * Retrieve this user's info from the past usage database.  If 'user' is
 * not found, create and install an appropriate entry in the usage database.
 */
double
get_resource_usage(char *user)
{
    char   *id = "get_resource_usage";
    struct past_usage *pusage_ptr;
    int     i;

    /* Search for 'user' in the existing database.  */
    pusage_ptr = Resource_usage;
    for (i = 0; i < n_Resource_usage; ++i) {
	if (!strcmp(pusage_ptr->user, user))
	    return (pusage_ptr->usage);
	++pusage_ptr;
    }

    /* No pre-existing entry.  Create a new one. */
    ++n_Resource_usage;

    pusage_ptr = realloc(Resource_usage, n_Resource_usage * sizeof *pusage_ptr);
    if (!pusage_ptr) {
	log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER,
		   id, "realloc(Resource_usage)");
	return -1;
    }

    Resource_usage = pusage_ptr;
    pusage_ptr += n_Resource_usage - 1;
    strcpy(pusage_ptr->user, user);
    pusage_ptr->usage = 0.0;

    return 0;
}

/*
 * Update past-usage database to account for a new job being run.
 */
void
schd_update_resource_usage(Job *job)
{
    char   *id = "schd_update_resource_usage";
    int     i;
    char   *name;
    double  node_hours;

    /* create the name tuple for this guy */
    name = make_grp_usr_tuple(job);

    /* We want to evaluate a new past-usage charge rate.
     * instead of use this old equation:
     *
    node_hours = (job->walltime / 3600.0) * job->nodes;
     *
     * lets just have a flat charge per job. but lets not
     * charge anything for very short jobs.
     */
     if (job->walltime > (20*60))	/* greater than 20 minutes */
	 node_hours = 10.0;
     else
	 node_hours = 1.0;

    /*
     * First, update the recent past-usage database.  Find the appropriate
     * user entry, and add the job's expected usage to that user's total.
     */
    for (i = 0; i < n_Resource_usage; ++i) {
	if (strcmp(Resource_usage[i].user, name))
	    continue;

	Resource_usage[i].usage += node_hours;

	if (debug) {
	    sprintf(log_buffer, "%s has %f node-hour recent usage",
		    Resource_usage[i].user, Resource_usage[i].usage);
	    log_record(PBSEVENT_DEBUG, PBS_EVENTCLASS_REQUEST, id, log_buffer);
	}
	break;
    }

    /* 
     * Next, update the FY-to-date usage database.  Same as above, but
     * operate on the per-group database.
     */

    for (i = 0; i < schd_NumAllocation; i++) {
	if (strcmp(schd_GroupTable[i].gname, job->group))
	    continue;

	schd_GroupTable[i].total_usage += node_hours;
	break;
    }

    /* 
     * Finally, update the user's running-job count.
     */
    for (i = 0; i < nUsers; ++i) {
	if (strcmp(Users[i].name, name))
	    continue;
	Users[i].running_jobs++;

	if (debug) {
	    sprintf(log_buffer, "%s has %d running jobs",
		    Users[i].name, Users[i].running_jobs);
	    log_record(PBSEVENT_DEBUG, PBS_EVENTCLASS_REQUEST, id, log_buffer);
	}
	break;
    }
    return;
}

/* 
 * Sort the list of users with jobs in the "normal" list in ascending order
 * by number of jobs queued.
 */
static void
sort_users(void)
{
    qsort(Users, nUsers, sizeof *Users, compare_users);
    return;
}

/*
 * qsort() comparison function.  Sort Uinfo records by increasing value of
 * the 'jobcount' fields.
 */
static int
compare_users(const void *e1, const void *e2)
{
    struct Uinfo *u1 = (struct Uinfo *)e1;
    struct Uinfo *u2 = (struct Uinfo *)e2;
    int     jc1;
    int     jc2;

    jc1 = u1->jobcount;
    jc2 = u2->jobcount;

    return ((jc1 > jc2) ? 1 : ((jc1 < jc2) ? -1 : 0));
}

/*
 * qsort() function to sort jobs from largest to smallest by priority
 */
static int
priority_ordering(const void *e1, const void *e2)
{
    Job    *job1 = *(Job **)e1;
    Job    *job2 = *(Job **)e2;

    if (job1->priority > job2->priority)
	return -1;
    if (job1->priority < job2->priority)
	return 1;
    return 0;
}
/*
 * Sort "normal" jobs by priority.
 */
static void
sort_jobs(void)
{
    int     (*criterion) (const void *, const void *);

    /* 
     * Depending upon the time of day, use a different ordering routine.
     * This is where most of the policy is implemented, as the rest of
     * the scheduler code attempts to run jobs in as close to this order
     * as possible, assuming available resources, time, etc.
     */
    criterion = priority_ordering;

    if (schd_ENFORCE_PRIME_TIME && schd_TimeNow >= schd_ENFORCE_PRIME_TIME) {
	if (schd_prime_time(0))
		/* for now use the same ordering all the time */
	    criterion = priority_ordering;
    }

    /* 
     * Sort the jobs based upon the proper criterion
     * for the current time of day.
     */
    qsort( normalQ,  nnormalQ, sizeof  *normalQ, criterion);

    /* 
     * Sort the list of running jobs, in ascending order by the expected
     * time to completion.
     */
    qsort(runningJobs, nJRs, sizeof *runningJobs, compare_running);

    return;
}

/*
 * 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;
}

/* 
 * 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, 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 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 (normalQ)
	free(normalQ);

    if (otherQ)
        free(otherQ);

    /* And reset all the values. */
    runningJobs = dedtimeQ = normalQ = otherQ = NULL;
    nJRs = nJQs = ndedtimeQ = 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 */