zedchance/Makefile

## README.md

      
    Raw
  

              README.md
            
          
    simulator

CPU scheduling simulator
How to compile

Compile using the provided Makefile.
So, run make to build everything.
How to test

There are 3 example input files provided.

To test the first input file using all 3 algorithms, run: make test.
To test the second input file using all 3 algorithms, run: make test2.
To test the third input file using all 3 algorithms, run: make test3.

Otherwise, the usage is as follows:
./simulator input_file FCFS|RR|SRTF [quantum if RR]


## input.1
1 0 10
2 0 9
3 3 5
4 7 4
5 10 6
6 10 7

## input.2
1 0 2
2 5 2
3 10 2
4 15 2

## input.3
1 0 10
5 5 10
25 6 12
30 20 10
100 16 20
90 4 4
77 70 20

## Makefile
all: simulator

simulator: simulator.o queue.o
	clang simulator.o queue.o -o simulator

simulator.o: simulator.c simulator.h
	clang -g -c simulator.c -Wall

queue.o: queue.c simulator.h
	clang -g -c queue.c -Wall

clean:
	rm -rf simulator *.o

test: simulator input.1
	./simulator input.1 FCFS
	./simulator input.1 RR 2
	./simulator input.1 SRTF

test2: simulator input.2
	./simulator input.2 FCFS
	./simulator input.2 RR 2
	./simulator input.2 SRTF

test3: simulator input.3
	./simulator input.3 FCFS
	./simulator input.3 RR 2
	./simulator input.3 SRTF


## queue.c
// run queue for scheduling simulator

#include <stdio.h>
#include <stdlib.h>

#include "simulator.h"

node * head = NULL;
node * tail = NULL;

int is_empty()
{
    if (head == NULL && tail == NULL)
    {
        return 1;
    }
    return 0;
}

int length()
{
    if (is_empty())
    {
        return 0;
    }
    node * walker = head;
    int length = 1;
    while (walker != tail)
    {
        walker = walker->next;
        length++;
    }
    return length;
}

void push_tail(pcb * data)
{
    node * new = malloc(sizeof(node));
    new->data = data;

    if (is_empty())
    {
        head = new;
        tail = new;
    }
    else
    {
        tail->next = new;
        tail = new;
    }
}

pcb * pop_head()
{
    if (is_empty())
    {
        return NULL;
    }

    node * ret = head;

    if (head == tail)
    {
        head = NULL;
        tail = NULL;
    }
    else
    {
        head = ret->next;
    }

    return ret->data;
}


## simulator.c
// CPU scheduling simulator - CS139 assignment 2
// Zed Chance

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "simulator.h"

// from assignment: assume the maximum queue length is 20.
#define SIZE 20

// stats variables
int pcount = 0;
int time = 0;
int idle_time = 0;
int * pid_index;          // array of pids, used for indexes for arrays below
int * computational_time; // time on CPU
int * response_time;      // first wait time
int * turnaround_time;    // finish - arrival

void print_stats()
{
    // cpu usage
    double avg_cpu = ((double)(time - idle_time) / time) * 100;

    // response time
    double avg_response = 0;
    for (int i = 0; i < pcount; i++)
    {
        avg_response = avg_response + response_time[i];
    }
    avg_response = avg_response / pcount;

    // turnaround time
    double avg_turnaround = 0;
    for (int i = 0; i < pcount; i++)
    {
        avg_turnaround = avg_turnaround + turnaround_time[i];
    }
    avg_turnaround = avg_turnaround / pcount;

    // wait time
    double avg_wait = 0;
    for (int i = 0; i < pcount; i++)
    {
        avg_wait = avg_wait + (turnaround_time[i] - computational_time[i]);
    }
    avg_wait = avg_wait / pcount;

    printf("\n== STATS ===========================\n");
    printf(" Average CPU usage       : %6.2f %%\n", avg_cpu);
    printf(" Average wait time       : %6.2f\n", avg_wait);
    printf(" Average response time   : %6.2f\n", avg_response);
    printf(" Average turnaround time : %6.2f\n", avg_turnaround);
    printf("====================================\n\n");
}

int get_index_of_pid(int pid)
{
    for (int i = 0; i < pcount; i++)
    {
        if (pid_index[i] == pid)
        {
            return i;
        }
    }
    return -1;
}

int sort_by_arrival_time(const void * a, const void * b)
{
    pcb * aa = (pcb *)a;
    pcb * bb = (pcb *)b;
    return aa->arrival - bb->arrival;
}

int sort_by_burst(const void * a, const void * b)
{
    pcb * aa = (pcb *)a;
    pcb * bb = (pcb *)b;
    return aa->burst - bb->burst;
}

// first come first served
void fcfs(pcb * processes, int pcount)
{
    // sort by arrival time
    qsort(processes, pcount, sizeof(pcb), sort_by_arrival_time);

    // run in order
    int running = 0;
    int local_pcount = pcount;
    while(local_pcount--)
    {
        // get current process
        pcb current = processes[running];

        // wait until arrival
        while (current.arrival > time)
        {
            printf("<system time %4d> CPU IS IDLE\n", time++);
            idle_time++;
        }

        // "run" process
        response_time[get_index_of_pid(current.pid)] = time - current.arrival;
        for (int i = 0; i < current.burst; i++)
        {
            printf("<system time %4d> process %4d is running\n", time++, current.pid);
            computational_time[get_index_of_pid(current.pid)]++;
        }
        turnaround_time[get_index_of_pid(current.pid)] = time - current.arrival;
        printf("<system time %4d> process %4d is finished...\n", time, current.pid);
        running++;
    }
    printf("<system time %4d> all processes finished...\n", time);
    print_stats();
}

// round robin
void rr(pcb * processes, int pcount, int quantum)
{
    pcb * running = NULL;

    // loop thru time
    int runtime = 0;
    for (int total_process = pcount; ; time++)
    {
        // check if new arrivals
        for (int i = 0; i < pcount; i++)
        {
            if (time == processes[i].arrival)
            {
                // add to queue
                push_tail(processes + i);
            }
        }

        // check if switching processes
        if (runtime <= 0)
        {
            // currently running process goes to queue
            if (running != NULL)
            {
                // push back on queue if remaining burst
                if (running->burst > 0)
                {
                    push_tail(running);
                }
                else
                {
                    printf("<system time %4d> process %4d is finished...\n", time, running->pid);
                    total_process--;
                    turnaround_time[get_index_of_pid(running->pid)] = time - running->arrival;

                     // check if we're done
                    if (total_process == 0)
                    {
                        break;
                    }
                }
            }

            // head of queue is new running process
            running = pop_head();

            // determine runtime
            if (running == NULL)
            {
                runtime = -1;
            }
            else
            {
                // min(burst, quantum)
                runtime = (running->burst < quantum) ? running->burst : quantum;
            }
        }

        // "run" process
        if (runtime > 0)
        {
            // run for 1 unit of burst
            printf("<system time %4d> process %4d is running\n", time, running->pid);
            running->burst--;
            runtime--;
            computational_time[get_index_of_pid(running->pid)]++;

            // calc response if first time running
            if (response_time[get_index_of_pid(running->pid)] == -1)
            {
                response_time[get_index_of_pid(running->pid)] = time - running->arrival;
            }
        }
        else if (runtime == -1)
        {
            printf("<system time %4d> CPU IS IDLE\n", time);
            idle_time++;
        }
    }
    printf("<system time %4d> all processes finished...\n", time);
    print_stats();
}

// shortest run time first
void srtf(pcb * processes, int pcount)
{
    pcb * queue = malloc(sizeof(pcb) * SIZE);
    int qcount = 0;

    // loop thru time
    int currently_running = 0;
    for (int total_process = pcount; ; time++)
    {
        // check if new arrivals
        for (int i = 0; i < pcount; i++)
        {
            if (time == processes[i].arrival)
            {
                queue[qcount++] = processes[i];
            }
        }

        // sort by burst time
        qsort(queue, qcount, sizeof(pcb), sort_by_burst);

        // "run" process
        pcb * running = queue + currently_running;
        if (running->burst == 0 && qcount > currently_running)
        {
            printf("<system time %4d> process %4d is finished...\n", time, running->pid);
            total_process--;
            turnaround_time[currently_running] = time - running->arrival;

            // check if we're done
            if (total_process == 0)
            {
                break;
            }
            else
            {
                // bump to next process
                running = queue + ++currently_running;
            }
        }
        if (total_process > 0 && running->burst > 0)
        {
            printf("<system time %4d> process %4d is running\n", time, running->pid);
            running->burst--;
            computational_time[currently_running]++;

            // calc response if first time running
            if (response_time[get_index_of_pid(running->pid)] == -1)
            {
                response_time[get_index_of_pid(running->pid)] = time - running->arrival;
            }
        }
        else if (currently_running >= qcount)
        {
            printf("<system time %4d> CPU IS IDLE\n", time);
            idle_time++;
        }
    }
    printf("<system time %4d> all processes finished...\n", time);
    print_stats();

    free(queue);
}

int main(int argc, char ** argv)
{
    // check args
    if (argc < 3)
    {
        fprintf(stderr, "Not enough arguments\n");
        fprintf(stderr, "Usage: %s input_file FCFS|RR|SRTF [time quantum]\n", argv[0]);
        exit(1);
    }

    // open input file
    FILE * input = fopen(argv[1], "r");
    if (!input)
    {
        fprintf(stderr, "Can't open %s for reading.\n", argv[1]);
        exit(1);
    }

    // read into processes array
    pcb * processes = malloc(sizeof(pcb) * SIZE);
    pid_index = malloc(sizeof(int) * SIZE);
    char line[1000];
    while (fgets(line, 1000, input) != NULL)
    {
        int p, a, b;
        sscanf(line, "%d %d %d", &p, &a, &b);
        processes[pcount].pid = p;
        processes[pcount].arrival = a;
        processes[pcount].burst = b;
        pid_index[pcount] = p;
        pcount++;
    }
    printf("Total %d tasks are read from %s\n", pcount, argv[1]);
    fclose(input);

    // allocate stat variables
    computational_time = malloc(sizeof(int) * SIZE);
    response_time = malloc(sizeof(int) * SIZE);
    turnaround_time = malloc(sizeof(int) * SIZE);
    for (int i = 0; i < pcount; i++)
    {
        // -1 indicates process has not yet been responded to
        response_time[i] = -1;
    }

    // get schedule mode, and call sim function
    if (strcmp(argv[2], "FCFS") == 0)
    {
        printf("Scheduling algorithm: FCFS.\n");
        fcfs(processes, pcount);
    }
    else if (strcmp(argv[2], "RR") == 0)
    {
        // get quantum
        if (argc < 4)
        {
            fprintf(stderr, "Not enough arguments, missing time quantum\n");
            fprintf(stderr, "Usage: %s input_file RR time_quantum\n", argv[0]);
            exit(1);
        }
        int quantum = 0;
        sscanf(argv[3], "%d", &quantum);

        printf("Scheduling algorithm: RR with quantum = %d.\n", quantum);
        rr(processes, pcount, quantum);
    }
    else if (strcmp(argv[2], "SRTF") == 0)
    {
        printf("Scheduling algorithm: SRTF.\n");
        srtf(processes, pcount);
    }
    else
    {
        printf("I don't know the '%s' scheduling algorithm.\n", argv[2]);
    }

    free(processes);
    free(pid_index);
    free(computational_time);
    free(response_time);
    free(turnaround_time);
}

## simulator.h
// simulator header file

// struct representing a process
typedef struct pcb
{
    int pid;     // process id
    int arrival; // when the process arrives
    int burst;   // cpu cycles left
} pcb;

// queue to implement scheduling algorithms
typedef struct node
{
    pcb * data;
    struct node * next;
} node;

void push_tail(pcb * data);
pcb * pop_head();
	all: simulator

	simulator: simulator.o queue.o
	clang simulator.o queue.o -o simulator

	simulator.o: simulator.c simulator.h
	clang -g -c simulator.c -Wall

	queue.o: queue.c simulator.h
	clang -g -c queue.c -Wall

	clean:
	rm -rf simulator *.o

	test: simulator input.1
	./simulator input.1 FCFS
	./simulator input.1 RR 2
	./simulator input.1 SRTF

	test2: simulator input.2
	./simulator input.2 FCFS
	./simulator input.2 RR 2
	./simulator input.2 SRTF

	test3: simulator input.3
	./simulator input.3 FCFS
	./simulator input.3 RR 2
	./simulator input.3 SRTF
	// run queue for scheduling simulator

	#include <stdio.h>
	#include <stdlib.h>

	#include "simulator.h"

	node * head = NULL;
	node * tail = NULL;

	int is_empty()
	{
	if (head == NULL && tail == NULL)
	{
	return 1;
	}
	return 0;
	}

	int length()
	{
	if (is_empty())
	{
	return 0;
	}
	node * walker = head;
	int length = 1;
	while (walker != tail)
	{
	walker = walker->next;
	length++;
	}
	return length;
	}

	void push_tail(pcb * data)
	{
	node * new = malloc(sizeof(node));
	new->data = data;

	if (is_empty())
	{
	head = new;
	tail = new;
	}
	else
	{
	tail->next = new;
	tail = new;
	}
	}

	pcb * pop_head()
	{
	if (is_empty())
	{
	return NULL;
	}

	node * ret = head;

	if (head == tail)
	{
	head = NULL;
	tail = NULL;
	}
	else
	{
	head = ret->next;
	}

	return ret->data;
	}
	// CPU scheduling simulator - CS139 assignment 2
	// Zed Chance

	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>

	#include "simulator.h"

	// from assignment: assume the maximum queue length is 20.
	#define SIZE 20

	// stats variables
	int pcount = 0;
	int time = 0;
	int idle_time = 0;
	int * pid_index; // array of pids, used for indexes for arrays below
	int * computational_time; // time on CPU
	int * response_time; // first wait time
	int * turnaround_time; // finish - arrival

	void print_stats()
	{
	// cpu usage
	double avg_cpu = ((double)(time - idle_time) / time) * 100;

	// response time
	double avg_response = 0;
	for (int i = 0; i < pcount; i++)
	{
	avg_response = avg_response + response_time[i];
	}
	avg_response = avg_response / pcount;

	// turnaround time
	double avg_turnaround = 0;
	for (int i = 0; i < pcount; i++)
	{
	avg_turnaround = avg_turnaround + turnaround_time[i];
	}
	avg_turnaround = avg_turnaround / pcount;

	// wait time
	double avg_wait = 0;
	for (int i = 0; i < pcount; i++)
	{
	avg_wait = avg_wait + (turnaround_time[i] - computational_time[i]);
	}
	avg_wait = avg_wait / pcount;

	printf("\n== STATS ===========================\n");
	printf(" Average CPU usage : %6.2f %%\n", avg_cpu);
	printf(" Average wait time : %6.2f\n", avg_wait);
	printf(" Average response time : %6.2f\n", avg_response);
	printf(" Average turnaround time : %6.2f\n", avg_turnaround);
	printf("====================================\n\n");
	}

	int get_index_of_pid(int pid)
	{
	for (int i = 0; i < pcount; i++)
	{
	if (pid_index[i] == pid)
	{
	return i;
	}
	}
	return -1;
	}

	int sort_by_arrival_time(const void * a, const void * b)
	{
	pcb * aa = (pcb *)a;
	pcb * bb = (pcb *)b;
	return aa->arrival - bb->arrival;
	}

	int sort_by_burst(const void * a, const void * b)
	{
	pcb * aa = (pcb *)a;
	pcb * bb = (pcb *)b;
	return aa->burst - bb->burst;
	}

	// first come first served
	void fcfs(pcb * processes, int pcount)
	{
	// sort by arrival time
	qsort(processes, pcount, sizeof(pcb), sort_by_arrival_time);

	// run in order
	int running = 0;
	int local_pcount = pcount;
	while(local_pcount--)
	{
	// get current process
	pcb current = processes[running];

	// wait until arrival
	while (current.arrival > time)
	{
	printf("<system time %4d> CPU IS IDLE\n", time++);
	idle_time++;
	}

	// "run" process
	response_time[get_index_of_pid(current.pid)] = time - current.arrival;
	for (int i = 0; i < current.burst; i++)
	{
	printf("<system time %4d> process %4d is running\n", time++, current.pid);
	computational_time[get_index_of_pid(current.pid)]++;
	}
	turnaround_time[get_index_of_pid(current.pid)] = time - current.arrival;
	printf("<system time %4d> process %4d is finished...\n", time, current.pid);
	running++;
	}
	printf("<system time %4d> all processes finished...\n", time);
	print_stats();
	}

	// round robin
	void rr(pcb * processes, int pcount, int quantum)
	{
	pcb * running = NULL;

	// loop thru time
	int runtime = 0;
	for (int total_process = pcount; ; time++)
	{
	// check if new arrivals
	for (int i = 0; i < pcount; i++)
	{
	if (time == processes[i].arrival)
	{
	// add to queue
	push_tail(processes + i);
	}
	}

	// check if switching processes
	if (runtime <= 0)
	{
	// currently running process goes to queue
	if (running != NULL)
	{
	// push back on queue if remaining burst
	if (running->burst > 0)
	{
	push_tail(running);
	}
	else
	{
	printf("<system time %4d> process %4d is finished...\n", time, running->pid);
	total_process--;
	turnaround_time[get_index_of_pid(running->pid)] = time - running->arrival;

	// check if we're done
	if (total_process == 0)
	{
	break;
	}
	}
	}

	// head of queue is new running process
	running = pop_head();

	// determine runtime
	if (running == NULL)
	{
	runtime = -1;
	}
	else
	{
	// min(burst, quantum)
	runtime = (running->burst < quantum) ? running->burst : quantum;
	}
	}

	// "run" process
	if (runtime > 0)
	{
	// run for 1 unit of burst
	printf("<system time %4d> process %4d is running\n", time, running->pid);
	running->burst--;
	runtime--;
	computational_time[get_index_of_pid(running->pid)]++;

	// calc response if first time running
	if (response_time[get_index_of_pid(running->pid)] == -1)
	{
	response_time[get_index_of_pid(running->pid)] = time - running->arrival;
	}
	}
	else if (runtime == -1)
	{
	printf("<system time %4d> CPU IS IDLE\n", time);
	idle_time++;
	}
	}
	printf("<system time %4d> all processes finished...\n", time);
	print_stats();
	}

	// shortest run time first
	void srtf(pcb * processes, int pcount)
	{
	pcb * queue = malloc(sizeof(pcb) * SIZE);
	int qcount = 0;

	// loop thru time
	int currently_running = 0;
	for (int total_process = pcount; ; time++)
	{
	// check if new arrivals
	for (int i = 0; i < pcount; i++)
	{
	if (time == processes[i].arrival)
	{
	queue[qcount++] = processes[i];
	}
	}

	// sort by burst time
	qsort(queue, qcount, sizeof(pcb), sort_by_burst);

	// "run" process
	pcb * running = queue + currently_running;
	if (running->burst == 0 && qcount > currently_running)
	{
	printf("<system time %4d> process %4d is finished...\n", time, running->pid);
	total_process--;
	turnaround_time[currently_running] = time - running->arrival;

	// check if we're done
	if (total_process == 0)
	{
	break;
	}
	else
	{
	// bump to next process
	running = queue + ++currently_running;
	}
	}
	if (total_process > 0 && running->burst > 0)
	{
	printf("<system time %4d> process %4d is running\n", time, running->pid);
	running->burst--;
	computational_time[currently_running]++;

	// calc response if first time running
	if (response_time[get_index_of_pid(running->pid)] == -1)
	{
	response_time[get_index_of_pid(running->pid)] = time - running->arrival;
	}
	}
	else if (currently_running >= qcount)
	{
	printf("<system time %4d> CPU IS IDLE\n", time);
	idle_time++;
	}
	}
	printf("<system time %4d> all processes finished...\n", time);
	print_stats();

	free(queue);
	}

	int main(int argc, char ** argv)
	{
	// check args
	if (argc < 3)
	{
	fprintf(stderr, "Not enough arguments\n");
	fprintf(stderr, "Usage: %s input_file FCFS\|RR\|SRTF [time quantum]\n", argv[0]);
	exit(1);
	}

	// open input file
	FILE * input = fopen(argv[1], "r");
	if (!input)
	{
	fprintf(stderr, "Can't open %s for reading.\n", argv[1]);
	exit(1);
	}

	// read into processes array
	pcb * processes = malloc(sizeof(pcb) * SIZE);
	pid_index = malloc(sizeof(int) * SIZE);
	char line[1000];
	while (fgets(line, 1000, input) != NULL)
	{
	int p, a, b;
	sscanf(line, "%d %d %d", &p, &a, &b);
	processes[pcount].pid = p;
	processes[pcount].arrival = a;
	processes[pcount].burst = b;
	pid_index[pcount] = p;
	pcount++;
	}
	printf("Total %d tasks are read from %s\n", pcount, argv[1]);
	fclose(input);

	// allocate stat variables
	computational_time = malloc(sizeof(int) * SIZE);
	response_time = malloc(sizeof(int) * SIZE);
	turnaround_time = malloc(sizeof(int) * SIZE);
	for (int i = 0; i < pcount; i++)
	{
	// -1 indicates process has not yet been responded to
	response_time[i] = -1;
	}

	// get schedule mode, and call sim function
	if (strcmp(argv[2], "FCFS") == 0)
	{
	printf("Scheduling algorithm: FCFS.\n");
	fcfs(processes, pcount);
	}
	else if (strcmp(argv[2], "RR") == 0)
	{
	// get quantum
	if (argc < 4)
	{
	fprintf(stderr, "Not enough arguments, missing time quantum\n");
	fprintf(stderr, "Usage: %s input_file RR time_quantum\n", argv[0]);
	exit(1);
	}
	int quantum = 0;
	sscanf(argv[3], "%d", &quantum);

	printf("Scheduling algorithm: RR with quantum = %d.\n", quantum);
	rr(processes, pcount, quantum);
	}
	else if (strcmp(argv[2], "SRTF") == 0)
	{
	printf("Scheduling algorithm: SRTF.\n");
	srtf(processes, pcount);
	}
	else
	{
	printf("I don't know the '%s' scheduling algorithm.\n", argv[2]);
	}

	free(processes);
	free(pid_index);
	free(computational_time);
	free(response_time);
	free(turnaround_time);
	}
	// simulator header file

	// struct representing a process
	typedef struct pcb
	{
	int pid; // process id
	int arrival; // when the process arrives
	int burst; // cpu cycles left
	} pcb;

	// queue to implement scheduling algorithms
	typedef struct node
	{
	pcb * data;
	struct node * next;
	} node;

	void push_tail(pcb * data);
	pcb * pop_head();