## 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)

– 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**

**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.

C

C

C

C

C

C

C

C

C

C

C

C

C

C

C

C

C

C

C

C