allocate.c

/*
 * this is allocate.c
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include "llist.c"
#include "llist.h"

#define INT_MAX __INT_MAX__

typedef struct {
    int timeArrived;
    int timeCompleted; //instant of time completed
    char processID[16];
    int executionTime;
    char parallelisable;
    int timeRemaining;
    int subProcsRunning;
    int justStarted;
    int deltaTime;
} process;

typedef struct {
    //int CPUi;
    int totalExecutionTimeRemaining; //add all the times of the process
    llist *processQueue;
    int numPorc;
} CPU;

void initializeProcess(char data[], process *newProcess);

process *headData(llist *q);

process *parallelParent(llist *processQueue, char *parentPid);

void advanceProcessQueue(llist *processQueue, int currentTime, int deltaTime, llist *processesComplete,
                         llist *parallelProcesses, int *numProcessesLeft, int *numProcessComplete, int cpuID);

void printQEntry(process *p);

int leastTimeRemaining(process *p, process *q);

int leastExecutionTime(process *p, process *q);

void calStats(llist *completedProcesses, int *currentTime, float *aveTurnaroundTime,
              float *maxOverhead, float *averageOverhead);

void addProcessToQueue(llist *processQueue, process *newProcess, int currentTime, int cpuID);

process *getNextProcess(FILE *f, llist *arrivals, process *readAhead);
process *getNextProcessB(FILE *f, llist *arrivals, process *readAhead);

int main(int argc, char *argv[]) {

    int numCPU;
    char file[255];
    strcpy(file, "testcases/");

    int deltaTime;
    int currentTime = 0;
    int numProcessesLeft = 0; //total number of processes over all CPUs
    int numberProcessesFinished = 0;
    float averageTurnaroundTime = 0;
    llist *completedProcesses, paralellizedProcesses, arrivalLounge;
    completedProcesses = llist_create(NULL);// is making list
    paralellizedProcesses = llist_create(NULL);

    process *newProcess;
    float maxOverhead = 0.0;
    float averageOverhead = 0.0;

    // Parse command line
    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i], "-f") == 0) {  //assigning the process file
            char temp[255];
            strcpy(temp, argv[i + 1]);
            strcat(file, temp);
        }
        if (strcmp(argv[i], "-p") == 0) {  //assigning the number of CPUs
            numCPU = atoi(argv[i + 1]);
        }
    }

    //  Initialize input file and arrival queue
    char line[36];
    arrivalLounge = llist_create(NULL);
    FILE *f = fopen(file, "r");
    process *headProcess;
    process *readAhead = malloc(sizeof(process));
    //  read the first process in
    if (fgets(line, sizeof line, f) != NULL) {
        //initialize the first process just read
        initializeProcess(line, readAhead);
    } else readAhead->timeArrived = -1;  // use -1 arrival to flag EOF

    //initialize CPUs
    CPU *CPUs = malloc(numCPU * sizeof(CPU));
    for (int i = 0; i < numCPU; i++) {
        CPUs[i].totalExecutionTimeRemaining = 0;
        CPUs[i].processQueue = llist_create(NULL);// is making list
    }

    //main loop
    if (f != NULL) {

        //iterate over arriving processes


        //while (fgets(line, sizeof line, f) != NULL) {
        while (newProcess = getNextProcessB(f, arrivalLounge, readAhead)) {

            //printf("process id:%s  process arrival time: %d\n", newProcess->processID, newProcess->timeArrived);

            deltaTime = newProcess->timeArrived - currentTime;

            //update currentTime
            currentTime += deltaTime;

            //update time CPU totalExecutionTimeRemaining and advance process queues
            for (int j = 0; j < numCPU; j++) {
                advanceProcessQueue(CPUs[j].processQueue, currentTime, deltaTime, completedProcesses,
                                    paralellizedProcesses,
                                    &numProcessesLeft,
                                    &numberProcessesFinished, j);
                if (CPUs[j].totalExecutionTimeRemaining - deltaTime < 0) {
                    CPUs[j].totalExecutionTimeRemaining = 0;
                } else {
                    CPUs[j].totalExecutionTimeRemaining -= deltaTime;
                }
            }
            //allocate process to cpu(s)
            if (newProcess->parallelisable == 'n') {  // If its not parallelizable just allocate it to queue
                int shortestTimeRemaining = 0; //this is the index for the CPU with the shortest time remaining
                for (int j = 1; j < numCPU; j++) {
                    // this is choosing a cpu queue scheduling
                    if (CPUs[j].totalExecutionTimeRemaining < CPUs[shortestTimeRemaining].totalExecutionTimeRemaining) {
                        shortestTimeRemaining = j;
                    }
                }
                //position the new process in the queue
                addProcessToQueue(CPUs[shortestTimeRemaining].processQueue, newProcess,
                                  currentTime, shortestTimeRemaining);
                numProcessesLeft += 1;
                CPUs[shortestTimeRemaining].totalExecutionTimeRemaining += newProcess->executionTime;
            } else if (newProcess->parallelisable == 'p') { // Parallelizable processes need to be split up
                // calculate number of sub processes and execution times for sub processes
                int quot = newProcess->executionTime / numCPU;
                int rem = newProcess->executionTime % numCPU;
                int nSubProc = numCPU;
                if (quot == 0) nSubProc = rem;
                newProcess->subProcsRunning = nSubProc;
                // create the sub processes
                process *parableProcess = malloc(nSubProc * (sizeof(process)));
                for (int i = 0; i < nSubProc; i++) {
                    parableProcess[i].timeArrived = newProcess->timeArrived;
                    sprintf(parableProcess[i].processID, "%s.%d", newProcess->processID, i);
                    // subprocess execution time = overhead (1) + integer-share-of-original-execution-time (quot) +
                    // one-more-if-there-is-some-remaining (i<rem)
                    parableProcess[i].executionTime = 1 + quot + (i < rem);
                    parableProcess[i].parallelisable = newProcess->parallelisable;
                    parableProcess[i].timeCompleted = -1;
                    parableProcess[i].timeRemaining = parableProcess[i].executionTime;
                    addProcessToQueue(CPUs[i].processQueue, &parableProcess[i], currentTime, i);
                }
                numProcessesLeft += 1;
                llist_push(paralellizedProcesses, newProcess);
            } else {
                printf("Error in test file ");
                exit(1);
            }
            //  Log started processes.
            for (int j = 0; j < numCPU; j++) {
                headProcess = headData(CPUs[j].processQueue);
                //next process in queue started
                if (headProcess != NULL && headProcess->justStarted) {
                    // printf("current time: %d\n", currentTime);
                    headProcess->justStarted = 0;
                    printf("%d,RUNNING,pid=%s,remaining_time=%d,cpu=%d - AAAA line 184\n",
                           deltaTime+1, headProcess->processID, headProcess->timeRemaining, j);
                }
            }

        }
        fclose(f);
    } else {
        perror(file); //print the error message on stderr
    }

    //  No more processes to be read in, just need to finish the ones in the queues
    //printf("No more processes to be read in\n");
    int tr;
    while (numProcessesLeft) {
        //  find how big the next time step is - its the smallest of the times remaining on each queue's head process
        deltaTime = INT_MAX;
        for (int i = 0; i < numCPU; i++) {
            if (headData(CPUs[i].processQueue) != NULL) {
                tr = headData(CPUs[i].processQueue)->timeRemaining;
                if (tr < deltaTime) {
                    deltaTime = tr;

                }
            }
        }

        currentTime += deltaTime;
        // update time CPU totalExecutionTimeRemaining and advance processes
        for (int j = 0; j < numCPU; j++) {
            advanceProcessQueue(CPUs[j].processQueue, currentTime, deltaTime, completedProcesses, paralellizedProcesses,
                                &numProcessesLeft,
                                &numberProcessesFinished, j);
            if (CPUs[j].totalExecutionTimeRemaining - deltaTime < 0) {
                CPUs[j].totalExecutionTimeRemaining = 0;
            } else {
                CPUs[j].totalExecutionTimeRemaining -= deltaTime;
            }
        }
        // Log process starts
        for (int j = 0; j < numCPU; j++) {
            headProcess = headData(CPUs[j].processQueue);
            //next process in queue started
            if (headProcess != NULL && headProcess->justStarted) {
                // printf("current time: %d\n", currentTime);
                headProcess->justStarted = 0;
                printf("%d,RUNNING,pid=%s,remaining_time=%d,cpu=%d\n",
                       currentTime, headProcess->processID, headProcess->timeRemaining, j);
            }
        }

//        currentTime += deltaTime;
    }
//    printf("Completed Queue:");
//    llist_print(completedProcesses, (void (*)(void *)) &printQEntry);

    calStats(completedProcesses, &currentTime, &averageTurnaroundTime, &maxOverhead, &averageOverhead);

    printf("Turnaround time %d\n", (int) (averageTurnaroundTime + 0.5));
    printf("Time overhead %2.2f %2.2f\n", maxOverhead, averageOverhead);
    printf("Makespan %d\n", currentTime);
//    printf("Completed Queue:");
//    llist_print(completedProcesses, (void (*)(void *)) &printQEntry);
    llist_free(completedProcesses);
    llist_free(paralellizedProcesses);

    return 0;
}  // main

void printQEntry(process *p) {
    if (p)
        printf("{arriv:%d, compl:%d, id:%s, exec:%d, para:%c, remain:%d}",
               p->timeArrived,
               p->timeCompleted,
               p->processID,
               p->executionTime,
               p->parallelisable,
               p->timeRemaining
        );
    else printf("EMPTY LIST\n");
}

int leastTimeRemaining(process *p, process *q) {
    if (p->timeRemaining < q->timeRemaining)
        return -1;
    else return 0;
}

int leastExecutionTime(process *p, process *q) {
    if (p->executionTime < q->executionTime || p->executionTime == q->executionTime &&
        strcmp(p->processID, q->processID ))
        return -1; //true
    else return 0; //false
}

void initializeProcess(char data[], process *newProcess) {
    const char s[2] = " ";
    char *token;

    token = strtok(data, s);
    if (token != NULL) {
        newProcess->timeArrived = atoi(token);
    }
    token = strtok(NULL, s);
    if (token != NULL) {
        strcpy(newProcess->processID, token);
    }
    token = strtok(NULL, s);
    if (token != NULL) {
        newProcess->executionTime = atoi(token);
    }
    token = strtok(NULL, s);
    if (token != NULL) {
        newProcess->parallelisable = token[0];
    }
    newProcess->deltaTime =0;
    newProcess->timeCompleted = -1;
    newProcess->timeRemaining = newProcess->executionTime;
}

process *headData(llist *q) {
    struct node *head = *q;
    if (head) {
        return head->data;
    } else {
        return NULL;
    }
}

process *parallelParent(llist *q, char *parentPid) {
    struct node *head = *q;
    process *p;

    if (head) p = head->data;
    while (head && !strncmp(p->processID, parentPid, strlen(parentPid))) {
        head = head->next;
        p = head->data;
    }
    return p;
}

// Advance the given process queue by delta time.  If one or more processes finish during the delta time
// period then pop them off the queue and add them to a completed processes list.
void advanceProcessQueue(llist *processQueue, int currentTime, int deltaTime, llist *processesComplete,
                         llist *paralellProcesses,
                         int *numProcessesLeft, int *numProcessComplete, int cpuID) {
    process *headProcess;
    process *paralizedProcess;
    char parentPid[11];

    headProcess = headData(processQueue);

    while (headProcess != NULL && deltaTime != 0) {
        if (deltaTime >= headProcess->timeRemaining) {  //  Process has finished
            deltaTime -= headProcess->timeRemaining;
            headProcess->timeCompleted = currentTime - deltaTime; //+ headProcess->timeRemaining;
//            int t = headProcess->timeRemaining;
            headProcess->timeRemaining = 0;
            if (headProcess->parallelisable == 'p') {
                //printf("process had finished, and was a paralized subprocess\n");
                parentPid[0] = strtok(headProcess->processID, ".");//todo to get rid of warning strncopy
                paralizedProcess = parallelParent(paralellProcesses, parentPid);
                paralizedProcess->subProcsRunning -= 1;
                if (paralizedProcess->subProcsRunning == 0) {
                    //printf("all subprocess from %s have finished \n", paralizedProcess->processID);
                    // parallelized process has completed.
                    *numProcessesLeft -= 1;
                    *numProcessComplete += 1;
                    paralizedProcess->timeCompleted = currentTime - deltaTime;//todo error on calculation here
                    paralizedProcess->timeRemaining = 0;
                    headProcess->timeRemaining = 0;
                    //printf("process had finished: Current time: %d, deltaTime: %d\n", currentTime, deltaTime);
                    printf("%d,FINISHED,pid=%s,proc_remaining=%d\n",
                           paralizedProcess->timeCompleted, paralizedProcess->processID, *numProcessesLeft);
                    //  Could accumulate statistics here instead of keeping list of completed processes
                    llist_push(processesComplete, paralizedProcess);
                }
                llist_pop(processQueue);
                headProcess = headData(processQueue);
                if (headProcess){
                    headProcess->justStarted = -1;
                    headProcess->deltaTime = deltaTime;
                }

            } else { // finishedprocess is not parallelisable
                *numProcessesLeft -= 1;
                *numProcessComplete += 1;
                printf("%d,FINISHED,pid=%s,proc_remaining=%d\n",
                       headProcess->timeCompleted, headProcess->processID, *numProcessesLeft);
                //  Could accumulate statistics here instead of keeping list of completed processes
                llist_push(processesComplete, headProcess);
                llist_pop(processQueue);
                headProcess = headData(processQueue);
                if (headProcess){
                    headProcess->justStarted = -1;
                    headProcess->deltaTime = deltaTime;
                }
            }

        } else { // head process not finished
            headProcess->timeRemaining -= deltaTime;
            headProcess->deltaTime = deltaTime;
            deltaTime = 0;
            // llist_print( processQueue, (void (*)(void *)) &printQEntry );
        }
    }
}

void calStats(llist *completedProcesses, int *currentTime, float *aveTurnaroundTime,
              float *maxOver, float *averageOverhead) {

    int turnaround, totTurnaround, maxTurnaround, count;
    float overhead, totOverhead, maxOverhead;

    process *p = headData(completedProcesses);
    *currentTime = p->timeCompleted;

    count = 0;
    maxOverhead = 0;
    totTurnaround = 0;
    totOverhead = 0;
    while (p != NULL) {
        count++;
        turnaround = p->timeCompleted - p->timeArrived;
        overhead = (float) turnaround / p->executionTime;
        totTurnaround += turnaround;
        totOverhead += overhead;
        if (overhead > maxOverhead) maxOverhead = overhead;
        llist_pop(completedProcesses);
        p = headData(completedProcesses);
    }
    *aveTurnaroundTime = (float) totTurnaround / (float) count;
    *maxOver = maxOverhead;
    *averageOverhead = totOverhead / (float) count;
}

void addProcessToQueue(llist *processQueue, process *newProcess, int currentTime, int cpuID) {
    process *oldProcess;
    oldProcess = headData(processQueue);
    process *headProcess;
    llist_add_inorder(newProcess, processQueue, (int (*)(void *, void *)) &leastTimeRemaining);
    headProcess = headData(processQueue);
    if (strncmp(headProcess->processID, newProcess->processID, sizeof (newProcess->processID)))
        headProcess->justStarted=-1;

}

process *getNextProcessB(FILE *f, llist *arrivals, process *readAhead) {
    char line[36];

    process *newProcess;
    int batchEnd=0;

    if (arrivals != NULL) {
        if (headData(arrivals) == NULL && readAhead->timeArrived != -1) {// no buffered processes so...{
            // queue the next batch of arrivals - starting with the read ahead.
            newProcess = malloc(sizeof(process));
            memcpy(newProcess, readAhead, sizeof(process));
            llist_add_inorder(newProcess, arrivals, (int (*)(void *, void *)) &leastExecutionTime);
            //llist_print();
            while (readAhead->timeArrived != -1 && !batchEnd) {
                if (fgets(line, sizeof line, f) != NULL) {
                    newProcess = malloc(sizeof(process));
                    initializeProcess(line, newProcess);
                    if (newProcess->timeArrived == readAhead->timeArrived) {
                        llist_add_inorder(newProcess, arrivals, (int (*)(void *, void *)) &leastExecutionTime);
                    } else {
                        batchEnd = -1;
                        memcpy(readAhead, newProcess, sizeof(process));
                        free(newProcess);
                    }
                } else {
                    readAhead->timeArrived = -1;
                }
            }
        }
        // now there's stuff in the arrivals lounge or there are no more to arrive
    }
//    llist_print(arrivals, (void (*)(void *)) &printQEntry);
    return llist_pop(arrivals);
}