Implement Different Scheduling Algorithms Assignment Solution

Source Code

#include #include #include // Algorithms #define FCFS 0 #define ROUNDROBIN 1 #define SRJF 2 // states #define NOT_ARRIVED -1 // added for processes that haven't arrived yet #define READY 0 #define RUNNING 1 #define BLOCKED 2 #define TERMINATED 3 // added for processes that have terminated // process stages #define CPU1 0 #define IO 1 #define CPU2 2 // default time quantum for Round-Robin algorithm #define QUANTUM 2 // name of the process states char *states[] = { "ready", "running", "blocked"}; // definition of a process typedef struct { int pid; // process id int n_cpu; // number of cycles of cpu int n_io; // number of io cycles int n_arrival; // time of arrival int state; // current state int stage; // current stage (cpu1, io, cpu2) int t_ready; // last time this process was ready int t_rem[3]; // remaining time in all stages int t_end; // time at which the process ended }process; // definition of a node for the queue typedef struct node_t { process *proc; struct node_t *next; }node; // definition of a queue typedef struct { node *head; node *tail; }queue; // enqueue a process in a given queue, if the queue is for ready processes, // updates the ready time. For Round-robin and shortest remaining job time // algorithms it enqueues at end of queue, for FCFS it enqueues sorting by pid void enqueue(queue *q, process *p, int algo, int cycle, int state) { node *tmp, *prev, *cur; tmp = (node *) malloc(sizeof(node)); p->state = state; if (state == READY) p->t_ready = cycle; tmp->proc = p; tmp->next = NULL; if (q->head == NULL) // new queue q->head = q->tail = tmp; else { cur = q->head; prev = NULL; switch (algo) { case FCFS: // sort by pid while (cur != NULL && (p->pid > cur->proc->pid)) { prev = cur; cur = cur->next; } if (prev == NULL) // add at start { tmp->next = q->head; q->head = tmp; } else // before cur { tmp->next = cur; prev->next = tmp; if (tmp->next == NULL) q->tail = tmp; } break; case ROUNDROBIN: case SRJF: q->tail->next = tmp; // enqueue at end q->tail = tmp; break; } } } // dequeues (removes) a process from the given queue. For FCFS removes the first // element (smallest pid), for round robin removes either the first in the list // or if there are elements that were ready at the same time, take the smallest // pid. For SRJF it removes the process with the smallest remaining cpu time process* dequeue(queue *q, int algo) { process *p; node *tmp, *prev, *cur, *sel; int currj, selrj; if (q->head == NULL) return NULL; tmp = q->head; p = tmp->proc; if (q->head == q->tail) // if single node { q->head = q->tail = NULL; } else { switch (algo) { case FCFS: q->head = q->head->next; break; case ROUNDROBIN: prev = NULL; cur = q->head; sel = cur; while (cur->next != NULL) { if (cur->next->proc->t_ready == sel->proc->t_ready && cur->next->proc->pid < sel->proc->pid) { prev = cur; sel = cur->next; } cur = cur->next; } if (sel == q->head) q->head = q->head->next; else { prev->next = sel->next; tmp = sel; p = tmp->proc; if (sel == q->tail) q->tail = prev; } break; case SRJF: prev = NULL; cur = q->head; sel = cur; // get remaining cpu time selrj = sel->proc->t_rem[0] + sel->proc->t_rem[2]; while (cur->next != NULL) { // calculate remaining time currj = cur->next->proc->t_rem[0] + cur->next->proc->t_rem[2]; // select smaller job or equal remaining job but smaller pid if (currj < selrj || (currj == selrj && cur->next->proc->pid < sel->proc->pid)) { prev = cur; sel = cur->next; } cur = cur->next; } if (sel == q->head) q->head = q->head->next; else { prev->next = sel->next; tmp = sel; p = tmp->proc; if (sel == q->tail) q->tail = prev; } break; } } free(tmp); return p; } // copy processes to an array and sort them by pid process* sort_processes(process *p, int n) { process *parr, tmp; int i, j, min; parr = calloc(n, sizeof(process)); // copy processes for (i = 0; i < n; i++) parr[i] = p[i]; // sort by pid for (i = 0; i < n - 1; i++) { min = i; for (j = i + 1; j < n; j++) { if (parr[j].pid < parr[min].pid) min = j; } if (min != i) { tmp = parr[min]; parr[min] = parr[i]; parr[i] = tmp; } } return parr; } // output the process information on the given output file void print_processes(FILE *output, process *p, int n) { int i; process *parr; parr = sort_processes(p, n); for (i = 0; i < n; i++) { if (parr[i].state != NOT_ARRIVED && parr[i].state != TERMINATED) fprintf(output, " %d:%s", parr[i].pid, states[parr[i].state]); } fprintf(output, "\n"); free(parr); } // Updates the queue of blocked processs, all blocked processes are advanced by // one cycle of I/O, if a process has elapsed its I/O time, its removed from the // blocked queue and enqueued in the ready queue void update_blocked(queue *bqueue, queue *rqueue, int algo, int cycle) { node *tmp, *prev; prev = NULL; tmp = bqueue->head; while (tmp) { tmp->proc->t_rem[1]--; if (tmp->proc->t_rem[1] == 0) // if blocked time is elapsed { tmp->proc->stage++; // advance to cpu2 // add to ready queue enqueue(rqueue, tmp->proc, algo, cycle, READY); // remove from this queue if (prev == NULL) { bqueue->head = tmp->next; free(tmp); tmp = bqueue->head; } else { prev->next = tmp->next; free(tmp); tmp = tmp->next; } } else { prev = tmp; tmp = tmp->next; } } if (bqueue->head == NULL) bqueue->tail = NULL; else { if (prev == NULL) bqueue->tail = bqueue->head; else bqueue->tail = prev; } } // select the next process to be run process *next_process(queue *rqueue, int algo) { process *p; p = dequeue(rqueue, algo); if (p != NULL) p->state = RUNNING; return p; } // create the output filename from the input filename void get_output_filename(char *ifname, char *ofname, int algo) { char temp[100]; int len = strlen(ifname); int i; strcpy(temp, ifname); // find dot for (i = len - 1; i >= 0 && temp[i] != '.'; i--); if (i > 0) { temp[i] = 0; } sprintf(ofname, "%d-%s.txt", algo, temp); } int main(int argc, char **argv) { FILE *input, *output; char ofname[100]; int algo; int i, j, m; int nprocs, arriving_proc; process *processes, tmp, *current_proc, *parr; queue rqueue, bqueue; int cycle, cpu_used; int quantum; if (argc < 3) { printf("Usage:\n"); printf(" %s algorithm inputfile\n", argv[0]); printf("\nalgorithm: 0 = FCFS, 1 = RR, 2 = SRJF\n"); return 0; } algo = atoi(argv[1]); if (algo < 0 || algo > 2) { printf("Invalid algorithm, must be a number between 0 and 2\n"); return 1; } // open input file input = fopen(argv[2], "rt"); if (input == NULL) { printf("Unable to open input file\n"); return 1; } // read number of processes if (fscanf(input, "%d", &nprocs) != 1) { printf("Unable to read number of processes from input file\n"); fclose(input); return 1; } if (nprocs <= 0) { printf("Invalid number of processes\n"); fclose(input); return 1; } // allocate space for all processes processes = calloc(nprocs, sizeof(process)); for (i = 0; i < nprocs; i++) { if (fscanf(input, "%d %d %d %d", &processes[i].pid, &processes[i].n_cpu, &processes[i].n_io, &processes[i].n_arrival) != 4) { printf("Invalid data in input file\n"); free(processes); fclose(input); return 1; } else // fill initial values for process { processes[i].state = NOT_ARRIVED; processes[i].stage = CPU1; // start in first stage processes[i].t_rem[0] = (processes[i].n_cpu/2) + (processes[i].n_cpu & 1); processes[i].t_rem[1] = processes[i].n_io; processes[i].t_rem[2] = processes[i].n_cpu - processes[i].t_rem[0]; } } fclose(input); // sort processes by arrival time for (i = 0; i < nprocs - 1; i++) { m = i; for (j = i + 1; j < nprocs; j++) { if (processes[j].n_arrival < processes[m].n_arrival || ((processes[j].n_arrival == processes[m].n_arrival) && (processes[j].pid < processes[m].pid))) m = j; } if (m != i) { tmp = processes[m]; processes[m] = processes[i]; processes[i] = tmp; } } // get output file name get_output_filename(argv[2], ofname, algo); // open output filename output = fopen(ofname, "wt"); // simulate scheduling cycle = 0; cpu_used = 0; arriving_proc = 0; rqueue.head = NULL; rqueue.tail = NULL; bqueue.head = NULL; bqueue.tail = NULL; current_proc = NULL; quantum = QUANTUM; while (current_proc != NULL || rqueue.head != NULL || bqueue.head != NULL || arriving_proc < nprocs) { while (arriving_proc < nprocs && cycle == processes[arriving_proc].n_arrival) { enqueue(&rqueue, &processes[arriving_proc], algo, cycle, READY); arriving_proc++; } // update blocked processes update_blocked(&bqueue, &rqueue, algo, cycle); // select process to run if (current_proc == NULL) { current_proc = next_process(&rqueue, algo); if (current_proc != NULL) quantum = QUANTUM; // start quantum for round-robin } else // if there is a process running { cpu_used++; quantum--; current_proc->t_rem[current_proc->stage]--; if (current_proc->t_rem[current_proc->stage] == 0) // if time is elapsed { current_proc->stage++; // advance to next stage switch (current_proc->stage) { case IO: // changing to io (blocked) if (current_proc->n_io > 0) { // put as blocked enqueue(&bqueue, current_proc, algo, cycle, BLOCKED); current_proc = NULL; // switch process } else // continue running if no blocking time { current_proc->stage++; // change to cpu2 // if no remaining time for cpu2 if (current_proc->t_rem[current_proc->stage] == 0) { // put as terminated current_proc->t_end = cycle; current_proc->state = TERMINATED; current_proc = NULL; // switch process } } break; case CPU2: // running the second cpu stage break; case TERMINATED: // terminated // put as terminated current_proc->t_end = cycle; current_proc->state = TERMINATED; current_proc = NULL; // switch process break; } } if (current_proc != NULL) { switch(algo) { case ROUNDROBIN: if(quantum == 0) // quantum is elapsed for RR { enqueue(&rqueue, current_proc, algo, cycle, READY); // add to ready queue current_proc = NULL; // switch process } break; case SRJF: // if shortest, switch every time enqueue(&rqueue, current_proc, algo, cycle, READY); // add to ready queue current_proc = NULL; // switch process break; } } // if we must switch process if (current_proc == NULL) { current_proc = next_process(&rqueue, algo); if (current_proc != NULL) quantum = QUANTUM; // start quantum for round-robin } } if (rqueue.head != NULL || bqueue.head != NULL || current_proc != NULL) { fprintf(output, "%d", cycle); print_processes(output, processes, nprocs); cycle++; } } fprintf(output, "\nFinishing time: %d\n", cycle - 1); fprintf(output, "CPU utilization: %.2f\n", 1.0 * cpu_used / cycle); parr = sort_processes(processes, nprocs); for (i = 0; i < nprocs; i++) { fprintf(output, "Turnaround process %d: %d\n", i, parr[i].t_end - parr[i].n_arrival); } fclose(output); free(parr); free(processes); return 0; }