* 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");
};