+1 (315) 557-6473 

Implement Different Scheduling Algorithms Assignment Solution.


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 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)
– Queue of ready processes
– 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
Implement different scheduling algorithms in C
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;
}