// qtime.cpp - ANALYSE QUEUEING TIMES
//
// MODULE INDEX
// NAME                 CONTENTS
// Simulate             Simulate processing of jobs, return total time
// main                 Main line
//
// MAINTENANCE HISTORY
// DATE         PROGRAMMER AND DETAILS
// 10-05-02     JS      Original
//
//-----------------------------------------------------------------------------

#include <stdio.h>              // Standard input/output
#include <stdlib.h>             // Standard library
#include <time.h>               // System time functions
#include <math.h>               // Mathematics library

//-----------------------------------------------------------------------------

// DEFINITIONS

#define MINREQTIME      4.0             // Minimum inter-request time
#define MAXREQTIME      7.0             // Maximum inter-request time
#define MINWIPTIME      3.9             // Minimum work-in-progress time
#define MAXWIPTIME      6.9             // Maximum work-in-progress time
#define NJOBS           200000          // Number of jobs

//-----------------------------------------------------------------------------

// JOB RECORD

struct JOB {
        struct JOB      *jobNxt;        // Next job in the list
        struct JOB      *jobPrv;        // Previous job in the list
        double          jobReqTime;     // Time the job was requested (days)
};

//-----------------------------------------------------------------------------

// QUEUEING MODE

enum MODE {
        MODEFIFO,                       // First in first out
        MODELIFO                        // Last in first out
};

//-----------------------------------------------------------------------------

// SIMULATE THE PROCESSING OF A NUMBER OF JOBS, RETURN TOTAL TIME

void
Simulate (
        MODE            mode,           // Queueing mode
        double          *avgTime,       // Average job processing time
        double          *sdTime)        // Standard deviation of proc time
{
        JOB             *job;           // Job structure pointer
        JOB             *fstJob;        // First job in the queue
        JOB             *lstJob;        // Last job in the queue
        JOB             *wipJob;        // Work-in-progress job
        int             reqRemaining;   // Requests remaining
        double          nextReqTime;    // Next request time
        int             jobInProg;      // Job in progress flag
        double          nextFinishTime; // Next job completion time
        double          totalTime;      // Total job processing time
        double          totalTime2;     // Total job proc time squared
        double          thisTime;       // Time for the current job

        // Initialise the number of requests remaining and
        // the next request time

        reqRemaining = NJOBS;
        nextReqTime = 0;

        // Initialise the queue

        fstJob = lstJob = NULL;

        // No job is in progress at the moment.  Initialise the next job
        // completion time to inhibit warning messages from 'average'
        // compilers.

        jobInProg = 0;
        nextFinishTime = 0;

        // Initialise the total job processing time

        totalTime = 0;
        totalTime2 = 0;

        // Process cycles until all jobs are finished

        while (reqRemaining != 0 || jobInProg) {

                // If the next thing to happen is a new request...

                if (
                        reqRemaining != 0 && (
                                ! jobInProg ||
                                nextReqTime < nextFinishTime
                        )
                ) {

                        // Create a new job record

                        job = new JOB;
                        job->jobReqTime = nextReqTime;

                        // Append the job to the queue depending on
                        // the queueing mode

                        if (mode == MODEFIFO) {
                                job->jobPrv = lstJob;
                                job->jobNxt = NULL;
                                if (lstJob == NULL)
                                        fstJob = job;
                                else
                                        lstJob->jobNxt = job;
                                lstJob = job;
                        } else {
                                job->jobPrv = NULL;
                                job->jobNxt = fstJob;
                                if (fstJob == NULL)
                                        lstJob = job;
                                else
                                        fstJob->jobPrv = job;
                                fstJob = job;
                        }

                        // If there is no job currently in progress
                        // start the job

                        if ( ! jobInProg) {
                                wipJob = fstJob;
                                fstJob = fstJob->jobNxt;
                                if (fstJob == NULL) lstJob = NULL;
                                nextFinishTime = nextReqTime + MINWIPTIME +
                                        ((double)rand() / 32768) *
                                        (MAXWIPTIME-MINWIPTIME);
                                jobInProg = 1;
                        }

                        // Update the number of requests remaining and
                        // the next request time

                        reqRemaining -- ;
                        nextReqTime += MINREQTIME + ((double)rand() / 32768) *
                                (MAXREQTIME-MINREQTIME);
                }

                // If the next thing to happen is completion of a job
                // process completion of the job

                else {
                        // Log the completion time of the job
                        // and release the job memory

                        thisTime = nextFinishTime - wipJob->jobReqTime;
                        totalTime += thisTime;
                        totalTime2 += thisTime * thisTime;
                        delete wipJob;

                        // If there is a job in the queue, start it

                        if (fstJob != NULL) {
                                wipJob = fstJob;
                                fstJob = fstJob->jobNxt;
                                if (fstJob == NULL) lstJob = NULL;
                                nextFinishTime = nextFinishTime + MINWIPTIME +
                                        ((double)rand() / 32768) *
                                        (MAXWIPTIME-MINWIPTIME);
                        }

                        // If there are no jobs in the queue, reset
                        // the job-in-progress flag

                        else {
                                jobInProg = 0;
                        }
                }
        }

        // Return the average processing time and its standard deviation

        *avgTime = totalTime / NJOBS;
        *sdTime = sqrt (totalTime2 / NJOBS - *avgTime * *avgTime);
}

//-----------------------------------------------------------------------------

// MAIN LINE

int
main ()
{
        unsigned int    randSeed;       // Random number seed
        double          avgFifoTime;    // Average FIFO time
        double          sdFifoTime;     // Standard deviation FIFO time
        double          avgLifoTime;    // Average LIFO time
        double          sdLifoTime;     // Standard deviation LIFO time

        // Generate a pseudo-random number seed

        randSeed = (unsigned int) time ((time_t*)0);

        // Execute the simulations

        srand (randSeed);
        Simulate (MODEFIFO, &avgFifoTime, &sdFifoTime);
        srand (randSeed);
        Simulate (MODELIFO, &avgLifoTime, &sdLifoTime);

        // Output the results

        printf ("Average FIFO time = %6.2f\n", avgFifoTime);
        printf ("Std dev FIFO time = %6.2f\n", sdFifoTime);
        printf ("Average LIFO time = %6.2f\n", avgLifoTime);
        printf ("Std dev LIFO time = %6.2f\n", sdLifoTime);
        printf ("Average ratio (%%) = %6.2f\n", avgLifoTime/avgFifoTime*100.0);
        printf ("Std dev ratio (%%) = %6.2f\n", sdLifoTime/sdFifoTime*100.0);

        return 0;
}