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)
– 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;
}