# Implement Different Scheduling Algorithms Assignment Solution.

## Instructions

Objective
Write a program to implement different scheduling algorithms in C language.

## Requirements and Specifications

The first line in the file is the total number of processes.
• 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)
```#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; } ```