usersort.c

openPBS的开放源代码

/*
*         OpenPBS (Portable Batch System) v2.3 Software License
* 
* Copyright (c) 1999-2000 Veridian Information Solutions, Inc.
* All rights reserved.
* 
* ---------------------------------------------------------------------------
* For a license to use or redistribute the OpenPBS software under conditions
* other than those described below, or to purchase support for this software,
* please contact Veridian Systems, PBS Products Department ("Licensor") at:
* 
*    www.OpenPBS.org  [phone]                  [e-mail]
*                        877 902-4PBS (US toll-free)
* ---------------------------------------------------------------------------
* 
* This license covers use of the OpenPBS v2.3 software (the "Software") at
* your site or location, and, for certain users, redistribution of the
* Software to other sites and locations.  Use and redistribution of
* OpenPBS v2.3 in source and binary forms, with or without modification,
* are permitted provided that all of the following conditions are met.
* After December 31, 2001, only conditions 3-6 must be met:
* 
* 1. Commercial and/or non-commercial use of the Software is permitted
*    provided a current software registration is on file at www.OpenPBS.org.
*    If use of this software contributes to a publication, product, or
*    service, proper attribution must be given; see www.OpenPBS.org/credit.html
* 
* 2. Redistribution in any form is only permitted for non-commercial,
*    non-profit purposes.  There can be no charge for the Software or any
*    software incorporating the Software.  Further, there can be no
*    expectation of revenue generated as a consequence of redistributing
*    the Software.
* 
* 3. Any Redistribution of source code must retain the above copyright notice
*    and the acknowledgment contained in paragraph 6, this list of conditions
*    and the disclaimer contained in paragraph 7.
* 
* 4. Any Redistribution in binary form must reproduce the above copyright
*    notice and the acknowledgment contained in paragraph 6, this list of
*    conditions and the disclaimer contained in paragraph 7 in the
*    documentation and/or other materials provided with the distribution.
* 
* 5. Redistributions in any form must be accompanied by information on how to
*    obtain complete source code for the OpenPBS software and any
*    modifications and/or additions to the OpenPBS software.  The source code
*    must either be included in the distribution or be available for no more
*    than the cost of distribution plus a nominal fee, and all modifications
*    and additions to the Software must be freely redistributable by any party
*    (including Licensor) without restriction.
* 
* 6. All advertising materials mentioning features or use of the Software must
*    display the following acknowledgment:
* 
*     "This product includes software developed by NASA Ames Research Center,
*     Lawrence Livermore National Laboratory, and Veridian Information 
*     Solutions, Inc.
*     Visit www.OpenPBS.org for OpenPBS software support,
*     products, and information."
* 
* 7. DISCLAIMER OF WARRANTY
* 
* THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND. ANY EXPRESS
* OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT
* ARE EXPRESSLY DISCLAIMED.
* 
* IN NO EVENT SHALL VERIDIAN CORPORATION, ITS AFFILIATED COMPANIES, OR THE
* U.S. GOVERNMENT OR ANY OF ITS AGENCIES BE LIABLE FOR ANY DIRECT OR INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
* OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
* EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
* 
* This license will be governed by the laws of the Commonwealth of Virginia,
* without reference to its choice of law rules.
*/
/* $Id: usersort.c,v 1.2.4.4 2000/08/09 00:19:21 hender Exp $ */

#include <sys/types.h>
#include <sys/stat.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "pbs_error.h"
#include "pbs_ifl.h"
#include "log.h"

#include "toolkit.h"
#include "gblxvars.h"

/*
 * Conditional compilation flags:
 *
 * USERSORT_DEBUG:      Enable additional debugging of queue and job structs.
 * SORT_DEDTIME_JOBS:   Enable sorting of jobs in dedicated queue.
 */

/* #define USERSORT_DEBUG */
/* #define SORT_DEDTIME_JOBS */

extern int connector;
int     schd_NeedToGetDecayInfo;

/* User information. */
struct Uinfo {
    char name[MAX_TXT+1];
    int jobcount;
    int running_jobs;
    double nodehours;
};

/* Decayed usage statistics. */
struct past_usage {
    char user[MAX_TXT+1];
    double usage;
};

static time_t when_decay_saved;
static time_t when_decay_done;

static int debug = 1;
static int n_Resource_usage;
static struct past_usage *Resource_usage;

/* Per-user usage information. */
static struct Uinfo *Users = NULL;
static int nUsers;

/* Per-class job lists.  Point to a set of jobs in the input list. */
static Job **normalQ  = NULL;
static int nnormalQ;
static Job **waitingQ = NULL;
static int nwaitingQ;
static Job **specialQ = NULL;
static int nspecialQ;
static Job **dedtimeQ = NULL;
static int ndedtimeQ;
static Job **otherQ = NULL;
static int notherQ;
static Job **runningJobs   = NULL;
static int nJQs, nJRs;

static char *unknown = "???";

static int split_jobs (Job *jobs);
static void get_users (void);
static int make_uinfo (char *user, struct Uinfo *info);
static Job *make_job_list (void);
static int is_new_user (char *user, struct Uinfo *list, int len, int *which);
static void sort_users (void);
static void sort_special_jobs (void);
static void sort_waiting_jobs (void);
static void sort_jobs_1st (void);
static void sort_jobs_2nd (void);
static int is_outstanding (Job *job);
static double get_resource_usage (char *user);
static int compare_users (const void *e1, const void *e2);
static int compare_prime_batch (const void *e1, const void *e2);
static int compare_nonprime_batch (const void *e1, const void *e2);
#ifdef HISTORICAL_CODE
static int compare_prime (const void *e1, const void *e2);
static int compare_nonprime_batch_old (const void *e1, const void *e2);
#endif /* HISTORICAL_CODE */
static int compare_running (const void *e1, const void *e2);
static int compare_waiting (const void *e1, const void *e2);
static int special_ordering (const void *e1, const void *e2);
static char *make_grp_usr_tuple(Job *job);

#ifdef USERSORT_DEBUG
static int print_jobs (Job *joblist);
#endif /* USERSORT_DEBUG */

#ifdef SORT_DEDTIME_JOBS
static void sort_dedtime_jobs(void);
#endif /* SORT_DEDTIME_JOBS */

#ifdef DEAD_CODE_MAY_19_1998
static int too_many_running_jobs(char *user, char *group);
static int compare_old_prime(const void *e1, const void *e2);
static int compare_nonprime_inter(const void *e1, const void *e2);
#endif /* DEAD_CODE_MAY_19_1998 */

/* 
 * Take a list of jobs, break it into sublists, sort those lists, and
 * return a pointer to a new list of jobs in the order in which they
 * should be run.
 */
Job *
schd_sort_jobs(Job *jobs)
{
    Job *newjobs = NULL;

    if (split_jobs(jobs))
	return (NULL);

    /*
     * Create a list of the users with jobs queued. 
     */
    get_users();

    /*
     * Sort user list in order of ascending past-usage.
     */
    sort_users();

    /*
     * Sort the list of waiting/outstanding jobs in order from largest to
     * smallest, shortest first.
     */
    sort_waiting_jobs();

    /*
     * Sort jobs in the special queue from largest to smallest.
     */
    sort_special_jobs();

    /*
     * Sort the jobs in normalQ.  Order depends on time of day (primetime).
     */
    sort_jobs_1st();

    if (schd_SORT_BY_PAST_USAGE) {
	/*
	 * Permute the queued jobs based on past usage.
	 */
	sort_jobs_2nd();
    }

    /* 
     * Convert arrays of jobs into a linked list.
     */
    newjobs = make_job_list();

#ifdef USERSORT_DEBUG
    /* Print the newly-created ordered job list. */
    print_jobs(newjobs);		
#endif /* USERSORT_DEBUG */

    return (newjobs);
}

/* 
 * Determine if it is necessary to save the past usage information to the
 * disk.
 */
int
schd_save_decay(void)
{
    if (schd_TimeNow >= (when_decay_saved + 3600))
	return 1;
    return 0;
}

/* 
 * Read or write the past usage data to the disk file.
 */
void
schd_decay_info(char *mode)
{
    char   *id = "schd_decay_info";
    FILE   *decay;
    char    buffer[MAX_TXT + 1 + 1]; /* size =  MAX_TXT + a newline + a NULL */
    char    gname[50];
    char   *group_ptr;
    struct past_usage *pusage_ptr;
    int     next = 0;
    int     last = -1;
    size_t  temp = 0;
    int     do_decay = 0;
    int     i;

    /*
     * If there is no pre-existing file, bootstrap it with a single record 
     * for root:root.
     */

    if ((decay = fopen(DECAY_INFO_FILE, mode)) == NULL) {
	sprintf(log_buffer, "fopen(%s,%s) failed (%d)",
		DECAY_INFO_FILE, mode, errno);
	log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER, id, log_buffer);

	if ((decay = fopen(DECAY_INFO_FILE, "w")) == NULL) {
	    /*
	     * Could not open the file for writing.  Possibly the path is
	     * invalid?
	     */
	    sprintf(log_buffer, "fopen(%s,%s) failed (%d)",
		    DECAY_INFO_FILE, mode, errno);
	    log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER, id, log_buffer);

	    return;
	}

	/* 
	 * The file pointed to by DECAY_INFO_FILE is writable.  Create the
	 * bootstrap record.
	 */

	strftime(buffer, sizeof buffer, "%a\n", &schd_TmNow);
	fputs(buffer, decay);
	fprintf(decay, "root:root 1.0\n");
	fclose(decay);

	sprintf(log_buffer, "wrote bootstrap record");
	log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER, id, log_buffer);

	/* 
	 * Attempt to reopen the file.  If it fails, then the bootstrap
	 * failed as well.  This leaves the open stream pointer in 'decay'
	 * as if it were opened successfully above.
	 */
	if ((decay = fopen(DECAY_INFO_FILE, mode)) == NULL) {
	    sprintf(log_buffer, "bootstrap:fopen(%s,%s) failed",
		    DECAY_INFO_FILE, mode);
	    log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER, id, log_buffer);
	    return;
	}
    }

    /* Read or write based on mode. */
    if (mode[0] == 'r') {

	pusage_ptr = Resource_usage;
	pusage_ptr = realloc(pusage_ptr, ALLOC_1ST * sizeof *pusage_ptr);
	if (pusage_ptr == NULL) {
	    temp = ALLOC_1ST * (sizeof *pusage_ptr);
	    sprintf(log_buffer, "realloc(%ld) failed", temp);
	    log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER, id, log_buffer);
	    return;
	}
	last = ALLOC_1ST - 1;

	/* XXX No error checking. */
	fgets(buffer, sizeof buffer, decay);	/* skip day_of_week */

	while (fgets(buffer, sizeof buffer, decay)) {
	    if (next > last) {
		last += ALLOC_INC;
		pusage_ptr = realloc(pusage_ptr, 
		    (last + 1) * sizeof *pusage_ptr);
		if (pusage_ptr == NULL) {
		    temp = last * (sizeof *pusage_ptr);
		    sprintf(log_buffer, "realloc(%ld) failed", temp);
		    log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER,
			       id, log_buffer);
		    return;
		}
	    }
	    /* XXX No error checking. */
	    strcpy(pusage_ptr[next].user, strtok(buffer, " \n"));
	    pusage_ptr[next].usage = atof(strtok(NULL, " \n"));

	    if (debug) {
		sprintf(log_buffer, "Read: %-8s\t%.02f", pusage_ptr[next].user,
			pusage_ptr[next].usage);
		log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER,
			   id, log_buffer);
	    }
	    ++next;
	}
	fclose(decay);

	pusage_ptr = realloc(pusage_ptr, next * sizeof *pusage_ptr);
	if (pusage_ptr == NULL) {
	    temp = next * (sizeof *pusage_ptr);
	    sprintf(log_buffer, "realloc(%ld) failed", temp);
	    log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER, id, log_buffer);
	    return;
	}
	Resource_usage = pusage_ptr;
	n_Resource_usage = next;

	schd_NeedToGetDecayInfo = 0;
	when_decay_done = schd_TimeNow;

    } else if (mode[0] == 'w') {

	/* XXX 23 hours hardcoded */
	do_decay = schd_TimeNow > when_decay_done + 82800;

	strftime(buffer, sizeof buffer, "%a\n", &schd_TmNow);
	fputs(buffer, decay);

	pusage_ptr = Resource_usage;
	for (i = 0; i < n_Resource_usage; ++i) {

	    if (do_decay) {
		/* extract group id from group:user tuple */
		strcpy(gname, pusage_ptr->user);
		group_ptr = strtok(gname, ":");
		if (schd_ENFORCE_ALLOCATION && 
		    schd_TimeNow >= schd_ENFORCE_ALLOCATION && 
		    schd_is_over_alloc(group_ptr))
		{
		    pusage_ptr->usage= pusage_ptr->usage * schd_OA_DECAY_FACTOR;
		} else {
		    pusage_ptr->usage = pusage_ptr->usage * schd_DECAY_FACTOR;
		}
	    }
	    if (pusage_ptr->usage > 0) {
		fprintf(decay, "%s %0.3f\n", 
		    pusage_ptr->user, pusage_ptr->usage);
	        if (debug) {
		    sprintf(log_buffer, "Wrote: %-8s\t%0.3f",
			    pusage_ptr->user, pusage_ptr->usage);
		    log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER,
			   id, log_buffer);
		}
	    }
	    ++pusage_ptr;
	}
	fclose(decay);
	if (do_decay)
	    when_decay_done = schd_TimeNow;

	when_decay_saved = schd_TimeNow;

    } else {
	sprintf(log_buffer, "unknown mode [%s]", mode);
	log_record(PBSEVENT_SYSTEM, PBS_EVENTCLASS_SERVER, id, log_buffer);
    }

    return;
}

/*
 * Split the supplied list of Job's into separate arrays based on various
 * characteristics of the jobs (queued vs. running, waiting, special, etc)
 */
static int
split_jobs(Job *jobs)
{
    char   *id = "split_jobs";
    Job    *this;
    QueueList *qptr;
    int     dedtimeI, specialI, waitingI, normalI, otherI, runningI;

    /* Number of elements in the queue arrays. */
    nJRs = nJQs = 0;
    ndedtimeQ = nspecialQ = nwaitingQ = nnormalQ = notherQ = 0;

    runningJobs = NULL;
    normalQ = NULL;
    waitingQ = NULL;
    specialQ = NULL;
    dedtimeQ = NULL;
    otherQ   = NULL;

    /*
     * Count the number of jobs that belong to each class, and allocate
     * an array of pointers to Job's for each non-empty class.  Note that
     * only jobs that are either 'R'unning or 'Q'ueued are of interest.
     * Place "other" jobs on the "other" list for completeness.
     */
    for (this = jobs; this != NULL; this = this->next) {
	if (this->state == 'R') {
	    nJRs ++;
	    continue;
	}

	if (this->state == 'Q') {
	    nJQs ++;

	    /* Does this job belong on the dedicated list? */
	    if ((schd_DedQueues != NULL)) {
		for (qptr = schd_DedQueues; qptr != NULL; qptr = qptr->next) {
		    if (!strcmp(this->qname, qptr->queue->qname)) {
			ndedtimeQ ++;
			break;
		    }
		}
		if (qptr != NULL) {	/* Match found with dedicated queue. */
		    this->flags |= JFLAGS_DEDICATED;
		    continue;
		}
	    }

	    /* Does this job belong on the special queue list? */
	    if ((schd_SpecialQueue != NULL) && 
		(!strcmp(this->qname, schd_SpecialQueue->queue->qname))) 
	    {
		nspecialQ ++;
		continue;
	    }

	    /* Is the job in an outstanding condition? */
	    if (is_outstanding(this)) {
		this->flags |= JFLAGS_WAITING; /* Note the waiting condition. */
		nwaitingQ ++;
		continue;
	    }

	    /* Just a boring old everyday job. */
	    nnormalQ ++;

	    continue;
	}
 
	/* Some other state.  Keep track of it so the memory isn't lost. */
	notherQ ++;
	continue;
    }

    /* No running or queued jobs.  Just exit. */
    if (!nJRs && !nJQs)
	return (-1);

    /* 
     * Now allocate arrays of pointers large enough to hold a pointer to
     * each job in the class.  These arrays will be sorted, and the job
     * lists reordered to match the sorted values.
     */
    if (nJRs) {
	if ((runningJobs = (Job **)malloc(nJRs * sizeof (Job *))) == NULL) {
	    DBPRT(("%s: malloc failed for %d Job *'s (%s)\n", id, 
		nJRs, "runningJobs"));
	    goto malloc_failed;
	}
    }