/* Scheduling Simulation*/
 
#include <stdio.h>
#include <stdlib.h>
 
/* Process Data Structure */
struct process {
    int pid;                /* Process ID */
    int burst;              /* CPU Burst Time */
    int priority;           /* Priority */
    int working;            /* Working time, for round-robin scheduling */
    int waiting;            /* Waiting time, for round-robin scheduling */
    struct process *next;
};
 
/* Function Prototype Declarations */
struct process *init_process (int pid, int burst, int priority);
void fcfs (struct process *proc);
void listprocs (struct process *proc);
void priority (struct process *proc);
void rr (struct process *proc, int quantum);
void sjf (struct process *proc);
 
/* Main Program Segment */
int main (void) {
    /* Initialize process list */
    struct process *plist, *ptmp;
    plist       = init_process(1, 10, 3);
    plist->next = init_process(2,  1, 1); ptmp = plist->next;
    ptmp->next  = init_process(3,  2, 3); ptmp = ptmp->next;
    ptmp->next  = init_process(4,  1, 4); ptmp = ptmp->next;
    ptmp->next  = init_process(5,  5, 2);
 
    /* Perform simulations */
    listprocs(plist);
    fcfs(plist);
    sjf(plist);
    priority(plist);
    rr(plist, 1);
 
    /* Terminate cleanly */
    while (plist != NULL) {
        ptmp = plist;
        plist = plist->next;
        free(ptmp);
    };
    return(0);
};
 
 
/* Process list entry initialization routine */
struct process *init_process (int pid, int burst, int priority) {
    struct process *proc;
    proc = malloc(sizeof(struct process));
    if (proc == NULL) {
        printf("Fatal error: memory allocation failure.\nTerminating.\n");
        exit(1);
    };
    proc->pid = pid;
    proc->burst = burst;
    proc->priority = priority;
    proc->working = 0;
    proc->waiting = 0;
    proc->next = NULL;
    return(proc);
};
 
 
/* First-Come-First-Served scheduling simulation */
void fcfs (struct process *proc) {
    int time = 0, start, end;
    struct process *tmp = proc;
 
    printf("BEGIN:\tFirst-Come-First-Served scheduling simulation\n");
 
    while (tmp != NULL) {
        start = time;
        time += tmp->burst;
        end = time;
        printf("Process: %d\tEnd Time: %d\tWaiting: %d\tTurnaround: %d\n", tmp->pid, time, start, end);
        tmp = tmp->next;
    };
 
    printf("END:\tFirst-Come-First-served scheduling simulation\n\n");
};
 
 
/* Process listing */
void listprocs (struct process *proc) {
    struct process *tmp = proc;
 
    printf("BEGIN:\tProcess Listing\n");
 
    while (tmp != NULL) {
        printf("PID: %d\t\tPriority: %d\tBurst: %d\n", tmp->pid, tmp->priority, tmp->burst);
        tmp = tmp->next;
    };
 
    printf("END:\tProcess Listing\n\n");
};
 
 
/* Priority scheduling simulation
 * Note: lower priority value gets a higher priority
 */
void priority (struct process *proc) {
    int time, start, end, highest;
    struct process *copy, *tmpsrc, *tmp, *beforehighest;
 
    printf("BEGIN:\tPriority scheduling simulation\n");
 
    /* Duplicate process list */
    tmpsrc = proc;
    copy = tmp = NULL;
    while (tmpsrc != NULL) {
        if (copy == NULL) {
            copy = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
            tmp = copy;
        } else {
            tmp->next = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
            tmp = tmp->next;
        };
        tmpsrc = tmpsrc->next;
    };
 
    /* Main routine */
    time = 0;
    while (copy != NULL) {
        /* Find the next job */
        beforehighest = NULL;
        highest = copy->priority;
        tmp = copy->next;
        tmpsrc = copy;
        while (tmp != NULL) {
            if (tmp->priority < highest) {
                highest = tmp->priority;
                beforehighest = tmpsrc;
            };
            tmpsrc = tmp;
            tmp = tmp->next;
        };
 
        /* Process job and remove from copy of process list */
        if (beforehighest == NULL) {
            /* Handle first job is highest priority case */
            start = time;
            time += copy->burst;
            end = time;
            printf("Process: %d\tEnd Time: %d\tWaiting: %d\tTurnaround: %d\n", copy->pid, time, start, end);
            tmpsrc = copy->next;
            free(copy);
            copy = tmpsrc;
        } else {
            /* Handle first job is not highest priority case */
            tmp = beforehighest->next;
            start = time;
            time += tmp->burst;
            end = time;
            printf("Process: %d\tEnd Time: %d\tWaiting: %d\tTurnaround: %d\n", tmp->pid, time, start, end);
            beforehighest->next = tmp->next;
            free(tmp);
        };
    };
 
    printf("END:\tPriority scheduling simulation\n\n");
};
 
 
/* Round-Robin scheduling simulation */
void rr (struct process *proc, int quantum) {
    int jobsremain, passes;
    struct process *copy, *tmpsrc, *tmp, *slot;
 
    printf("BEGIN:\tRound-Robin scheduling simulation (Quantum: %d)\n", quantum);
    /* Duplicate process list */
    tmpsrc = proc;
    copy = tmp = NULL;
    while (tmpsrc != NULL) {
        if (copy == NULL) {
            copy = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
            tmp = copy;
        } else {
            tmp->next = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
            tmp = tmp->next;
        };
        tmpsrc = tmpsrc->next;
    };
 
    /* Main routine */
    jobsremain = 1;
    slot = NULL;
    while (jobsremain) {
        jobsremain = 0;
 
        /* Pick next working slot */
        if (slot == NULL) {
            slot = copy;
            jobsremain = 1;
        } else {
            passes = 0;
            do {
                if (slot->next == NULL) {
                    passes++;
                    slot = copy;
                } else {
                    slot = slot->next;
                };
            } while (passes <= 2 && slot->burst == slot->working);
            if (passes <= 2) {
                jobsremain = 1;
            };
        };
 
        /* Perform a cycle */
        tmp = copy;
        while (tmp != NULL) {
            if (tmp->burst > tmp->working) {
                if (tmp == slot) {
                    tmp->working += quantum;
                } else {
                    tmp->waiting += quantum;
                };
            };
            tmp = tmp->next;
        };
    };
 
    /* Display statistics and clean up copy */
    tmp = copy;
    while (tmp != NULL) {
        printf("Process: %d\tWorking: %d\tWaiting: %d\tTurnaround: %d\n", tmp->pid, tmp->working, tmp->waiting, tmp->working + tmp->waiting);
        tmpsrc = tmp;
        tmp = tmp->next;
        free(tmpsrc);
    };
 
    printf("END:\tRR scheduling simulation\n\n");
};
 
 
/* Shortest Job First scheduling simulation */
void sjf (struct process *proc) {
    int time, start, end, shortest;
    struct process *copy, *tmpsrc, *tmp, *beforeshortest;
 
    printf("BEGIN:\tShortest Job First scheduling simulation\n");
 
    /* Duplicate process list */
    tmpsrc = proc;
    copy = tmp = NULL;
    while (tmpsrc != NULL) {
        if (copy == NULL) {
            copy = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
            tmp = copy;
        } else {
            tmp->next = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
            tmp = tmp->next;
        };
        tmpsrc = tmpsrc->next;
    };
 
    /* Main routine */
    time = 0;
    while (copy != NULL) {
        /* Find the next job */
        beforeshortest = NULL;
        shortest = copy->burst;
        tmp = copy->next;
        tmpsrc = copy;
        while (tmp != NULL) {
            if (tmp->burst < shortest) {
                shortest = tmp->burst;
                beforeshortest = tmpsrc;
            };
            tmpsrc = tmp;
            tmp = tmp->next;
        };
 
        /* Process job and remove from copy of process list */
        if (beforeshortest == NULL) {
            /* Handle first job is shortest case */
            start = time;
            time += copy->burst;
            end = time;
            printf("Process: %d\tEnd Time: %d\tWaiting: %d\tTurnaround: %d\n", copy->pid, time, start, end);
            tmpsrc = copy;
            copy = copy->next;
            free(tmpsrc);
        } else {
            /* Handle first job is not shortest case */
            tmp = beforeshortest->next;
            start = time;
            time += tmp->burst;
            end = time;
            printf("Process: %d\tEnd Time: %d\tWaiting: %d\tTurnaround: %d\n", tmp->pid, time, start, end);
            beforeshortest->next = tmp->next;
            free(tmp);
        };
    };
 
    printf("END:\tShortest Job First scheduling simulation\n\n");
};