scheduling_algortihm.c

Scheduling algortihms..UNIX

#include <stdio.h>
#include <stdlib.h>


/*Process Data Structure */
struct process {
int pid; // Process ID 
int length; //length
int priority; //Priority 
int working; //Working time, for round-robin scheduling 
int waiting; //Waiting time, for round-robin scheduling 
struct process *next;
};



/* Function Prototypes */
struct process *init_process (int pid, int length, int priority);
void round_robin (struct process *proc, int quantum);
void priority (struct process *proc);
void multiple_queue (struct process *proc);
void shortest_job_first (struct process *proc);
void listprocs (struct process *proc);



int main (void) {
//i put the input.txt variables on here..
/* Initialize process list */
struct process *plist, *ptmp;
plist = init_process(1, 15, 2);
plist->next = init_process(2, 25, 2); ptmp = plist->next;
ptmp->next = init_process(3, 10, 4); ptmp = ptmp->next;
ptmp->next = init_process(4, 20, 1); ptmp = ptmp->next;
ptmp->next = init_process(5, 30, 3);
////////////////////////////////////////////////////////////////////////// 


//Perform simulations 
    listprocs(plist);
	round_robin(plist, 5); // 5 is quantum
	priority(plist);
    multiple_queue(plist);
    shortest_job_first(plist);
 
   
	
	
//Termination
while (plist != NULL) {
ptmp = plist;
plist = plist->next;
free(ptmp);
};
return(0);
};



// Process list entry initialization routine 
struct process *init_process (int pid, int length, int priority) {
struct process *proc;
proc = (struct process*)malloc(sizeof(struct process));

if (proc == NULL) {
printf(" Memory allocation failure.\n");
exit(1);
};

proc->pid = pid;
proc->length = length;
proc->priority = priority;
proc->working = 0;
proc->waiting = 0;
proc->next = NULL;
return(proc);
};




// Process listing 
void listprocs (struct process *proc) {
struct process *tmp = proc;

printf("\tProcess List\n");

while (tmp != NULL) {
printf("PID: %d\t\tPriority: %d\tlength: %d\n", tmp->pid, tmp->priority, tmp->length);
tmp = tmp->next;
};
}; 



//ROUND ROBIN SCHEDULING
void round_robin (struct process *proc, int quantum) {
    int jobsremain, passes;
    struct process *copy, *tmpsrc, *tmp, *slot;

    printf("\n\tRound Robin Scheduling  (Quantum: %d)\n", quantum);
    /* Duplicate process list */
    tmpsrc = proc;
    copy = tmp = NULL;
    while (tmpsrc != NULL) {
        if (copy == NULL) {
            copy = init_process(tmpsrc->pid, tmpsrc->length, tmpsrc->priority);
            tmp = copy;
        } else {
            tmp->next = init_process(tmpsrc->pid, tmpsrc->length, 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->length == slot->working);
            if (passes <= 2) {
                jobsremain = 1;
            };
        };

        /* Perform a cycle */
        tmp = copy;
        while (tmp != NULL) {
            if (tmp->length > 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\tProcess time: %d\tResponse time: %d\tThroughput: %d\n", tmp->pid, tmp->working, tmp->waiting, tmp->working + tmp->waiting);
        tmpsrc = tmp;
        tmp = tmp->next;
        free(tmpsrc);
    };

    printf("\t**** Round Robin Scheduling **** \n\n");
};

//PRIORITY SCHEDULING

void priority (struct process *proc) {
    int time, start, end, highest;
    struct process *copy, *tmpsrc, *tmp, *beforehighest;

    printf("\tPriority Scheduling \n");


    tmpsrc = proc;
    copy = tmp = NULL;
    while (tmpsrc != NULL) {
        if (copy == NULL) {
            copy = init_process(tmpsrc->pid, tmpsrc->length, tmpsrc->priority);
            tmp = copy;
        } else {
            tmp->next = init_process(tmpsrc->pid, tmpsrc->length, tmpsrc->priority);
            tmp = tmp->next;
        };
        tmpsrc = tmpsrc->next;
    };


    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->length;
            end = time;
            printf("Process: %d\tProcess time: %d\tResponse time: %d\tThroughput: %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->length;
            end = time;
            printf("Process: %d\tProcess time: %d\tResponse time: %d\tThroughput: %d\n", tmp->pid, time, start, end);
            beforehighest->next = tmp->next;
            free(tmp);
        };
    };

    printf("\t**** Priority Scheduling ****\n\n");
};




//MULTIPLE QUEUE SCHEDULING
void multiple_queue (struct process *proc) {
    int time = 0;
	int start;
	int	end;
    struct process *tmp = proc;

    printf("\tMultiple Queue Scheduling\n");

    while (tmp != NULL) {
        start = time;
        time += tmp->length;
        end = time;
        printf("Process: %d\tProcess time: %d\tResponse time: %d\tThroughput: %d\n", tmp->pid, time, start, end);
        tmp = tmp->next;
    };

    printf("\t**** Multiple Queue Scheduling ****\n\n");
};




//SHORTEST JOB FIRST SCHEDULING
void shortest_job_first (struct process *proc) {
    int time, start, end, shortest;
    struct process *copy, *tmpsrc, *tmp, *beforeshortest;

    printf("\tShortest Job First Scheduling \n");

    /* Duplicate process list */
    tmpsrc = proc;
    copy = tmp = NULL;
    while (tmpsrc != NULL) {
        if (copy == NULL) {
            copy = init_process(tmpsrc->pid, tmpsrc->length, tmpsrc->priority);
            tmp = copy;
        } else {
            tmp->next = init_process(tmpsrc->pid, tmpsrc->length, tmpsrc->priority);
            tmp = tmp->next;
        };
        tmpsrc = tmpsrc->next;
    };

    /* Main routine */
    time = 0;
    while (copy != NULL) {
        /* Find the next job */
        beforeshortest = NULL;
        shortest = copy->length;
        tmp = copy->next;
        tmpsrc = copy;
        while (tmp != NULL) {
            if (tmp->length < shortest) {
                shortest = tmp->length;
                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->length;
            end = time;
            printf("Process: %d\tProcess time: %d\tResponse time: %d\tThroughput: %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->length;
            end = time;
            printf("Process: %d\tProcess time: %d\tResponse time: %d\tThroughput: %d\n", tmp->pid, time, start, end);
            beforeshortest->next = tmp->next;
            free(tmp);
        };
    };

    printf("\t**** Shortest Job First Scheduling ****\n\n");
};