# Implement Different Scheduling Algorithms Assignment Solution

July 05, 2024
Doreen McQueen
🇬🇧 United Kingdom
C
Doreen, with a Master's degree in Software Engineering, brings a wealth of knowledge in cross-platform Makefile development and integration of external libraries. With 600 assignments under her belt, her expertise ensures students receive high-quality solutions tailored to their needs.
Key Topics
• Instructions
• Requirements and Specifications
Tip of the day
News

## Instructions

Objective

Write a C assignment program to implement different scheduling algorithms.

## Requirements and Specifications

The first line in the file is the total number of

Each process will be represented by 4 integers:

A B C D:

– A: process ID

– B: CPU time

– C: I/O time

– Arrival time

How time is distributed for a process ?

Note: We will use integers, not floating point. In case (0.5 * CPU Time) is float, round to following.

Note: If more than one process cycle (e.g. if cpu time is 7 then 7/2 = 3.5 -> 4).

arrives at the same time, give preference to the one with lower ID.

All times are in cyclesScheduling Algorithms.

0: First-Come-First-Served (nonpreemptive)

– Newly arriving processes are added to the end of

– When a process is blocked, due to I/O, and then becomes ready, it is added to the end of the queue.

– If two processes happen to be ready at the same time, give preference to the one with lower ID.

Screenshots of output

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; } ```

## Related Samples

At ProgrammingHomeworkHelp.com, we offer tailored assignment support for students, including a valuable resource for C programming. Our platform provides a selection of related C programming samples that demonstrate effective coding practices and problem-solving techniques. These samples serve as a helpful guide, offering insights and examples to enhance your understanding and execution of C assignments. Whether you're tackling basic concepts or complex projects, our expertly crafted samples are designed to support your learning journey and boost your programming skills. Visit us for comprehensive assistance and top-notch C programming resources.