Using Queue Data Structures to Simulate Processes
* Program to test several scheduling algorithms
*/
#include
#include
#include
#define MAX_NAME 20 /* maximum length of filenames */
#define MAX_LINE 100 /* maximum length of line in input file */
#define COLUMNS 3 /* number of columns in input dataset files */
/* struct used to save scheduling information for every process */
typedef struct
{
int PID; /* process ID */
int AT; /* arrival time */
int BT; /* burst time */
int TaT; /* turn around time */
int WT; /* wait time */
int T; /* current elapsed time for process */
}scheduling_data_t;
/* struct of a node used to create a process queue */
typedef struct node
{
scheduling_data_t *data;
struct node *next;
}node_t;
/* structure to represent a queue */
typedef struct
{
node_t *head;
node_t *tail;
int size;
}queue_t;
/*
* Purpose: Creates a new queue
* Explanation: allocates memory for a queue structure, initialize elements
* Parameters: None
* Returns: pointer to new queue structure
*/
queue_t *new_queue()
{
queue_t *queue;
queue = (queue_t *) malloc(sizeof(queue_t));
queue->head = NULL;
queue->tail = NULL;
queue->size = 0;
return queue;
}
/*
* Purpose: Creates a new node with the given process data
* Explanation: allocates memory for a node structure, initialize elements
* Parameters: data = process scheduling data
* Returns: pointer to new node structure
*/
node_t *new_node(scheduling_data_t *data)
{
node_t *node;
node = (node_t *) malloc(sizeof(node_t));
node->data = data;
node->next = NULL;
return node;
}
/*
* Purpose: insert process data to the queue
* Explanation: inserts a new process scheduling data at the queue tail
* Parameters: data = process scheduling data to be inserted, queue = queue to use
* Returns: None
*/
void enqueue_process(scheduling_data_t *data, queue_t *queue)
{
node_t *node;
node = new_node(data); /* create a new node */
if (queue->size == 0)
queue->head = node; /* set node as queue head */
else
queue->tail->next = node; /* attach at queue tail */
queue->tail = node; /* set tail as the new node */
queue->size++; /* increment queue size */
}
/*
* Purpose: removes the process with the shortest BT from the queue and returns
* the scheduling data for it
* Explanation: searches for the process with the minimum BT in the queue and
* removes it from the queue, returns the scheduling data for the process found
* Parameters: queue = queue to use for searching the minimum
* Returns: pointer to the scheduling data for the process
*/
scheduling_data_t *get_shortest_process(queue_t *queue)
{
node_t *node, *prev;
node_t *min, *minprev;
scheduling_data_t *proc;
min = node = queue->head;
minprev = prev = NULL;
while (node!=NULL) /* find the node with the minimum BT */
{
if (node->data->BT < min->data->BT)
{
minprev = prev;
min = node;
}
prev = node;
node = node->next;
}
if (minprev == NULL) /* if it's the first node */
queue->head = min->next;
else
minprev->next = min->next; /* remove node */
proc = min->data;
free(min);
queue->size--; /* we removed a node, decrement size */
return proc;
}
/*
* Purpose: removes the process at the start of the queue and returns
* the scheduling data for it
* Explanation: removes the head node from the queue and returns the scheduling
* data for the process in the head node
* Parameters: queue = queue to use
* Returns: pointer to the scheduling data for the process
*/
scheduling_data_t *dequeue_process(queue_t *queue)
{
node_t *node;
scheduling_data_t *proc;
if (queue->head==NULL)
return NULL;
node = queue->head; /* dequeue head */
queue->head = node->next;
proc = node->data;
free(node);
queue->size--; /* we removed a node, decrement size */
return proc;
}
/*
* Purpose: Print an option menu on the screen
* Explanation: Prints menu
* Parameters: None
* Returns: None
*/
void show_menu()
{
/* Print the menu options */
printf("1 - First Come First Served (FCFS) Scheduler\n");
printf("2 - Shortest Job First (SJF) Scheduler\n");
printf("3 - Round Robin (RR) Scheduler\n");
printf("4 - Quit\n");
printf("Enter a selection: ");
fflush(stdout); /* flush the output to display immediatly the previous printf */
}
/*
* Purpose: Read a string from the user
* Explanation: Read string in the provided buffer and removes trailing newline
* Parameters: string = buffer to save read string
* Returns: None
*/
void read_string(char *string)
{
int length;
fgets(string, MAX_NAME, stdin); /* read string from stdin */
length = strlen(string);
if (string[length - 1] == '\n') /* remove the trailing newline */
string[length - 1] = '\0';
}
/*
* Purpose: Splits a given line using spaces, returns the split parts
* Explanation: tokenizes the line using strtok and saves all parts in the
* provided array, returns the number of parts found
* Parameters: line = line to split, parts = provided array of pointers to save
* the found parts, max_parts = maximum number of parts to split line
* Returns: Number of parts found in line and saved in the parts array
*/
int split_line(char *line, char **parts, int max_parts)
{
char *token;
int n_parts;
n_parts = 0;
token = strtok(line, " \t"); /* separate line by spaces */
/* keep separating line while there are more parts and we haven't reached the max*/
while (token != NULL &&n_partsdata[j + 1].AT) /* if the value is out of order */
{
/* swap values */
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
}
}
}
}
/*
* Purpose: read the input and output filenames from the user
* Explanation: prints prompts and reads the filenames in the provided variables
* Parameters: input_filename = place to save input filename, output_filename =
* place to save output filename
* Returns: None
*/
void get_filenames(char *input_filename, char *output_filename)
{
printf("Input file?: ");
read_string(input_filename);
printf("Output file?: ");
read_string(output_filename);
}
/*
* Purpose: prints the scheduling data on the screen and saves it to a file
* Explanation: prints the result of the simulation by showing the contents of
* the scheduling data array, also calculates the averages and shows them on the
* screen and saves all the same data to a file
* Parameters: data = array of scheduling data, n_data = number of entries in array,
* output_filename = file to use for saving the output
* Returns: None
*/
void print_scheduling_data(scheduling_data_t *data, int n_data, char *output_filename)
{
scheduling_data_tproc;
int n_proc;
double totalTaT = 0.0;
double totalWT = 0.0;
FILE *file_ptr;
file_ptr = fopen(output_filename, "wt"); /* open file for writing */
printf("%3s %4s %4s %4s\n","AT","BT","TaT","WT");
fprintf(file_ptr, "%3s %4s %4s %4s\n","AT","BT","TaT","WT");
for (n_proc = 0; n_proc= data[next_process].AT)
{
proc = &data[next_process++]; /* load next process */
proc->WT = time - proc->AT; /* calculate how much time it waited */
proc->TaT = proc->WT + proc->BT; /* calculate turn around time */
time += proc->BT; /* increment time by the burst time */
}
else
time++;
}
print_scheduling_data(data, n_data, output_filename);
}
/*
* Purpose: simulates the Shortest Job First scheduling
* Explanation: it creates a queue of processes depending on the arrival time,
* it selects the process with the minimum BT from this queue and it executes
* it, when the process has terminated it executes the next minimum BT process
* Parameters: data = array of scheduling data, n_data = number of entries in array
* output_filename = name of the file to use to save output
* Returns: None
* Advantages: short processes execute first, throughput is increased
* Disadvantages: execution time is not known in all cases, longer processes have
* longer waiting times
*/
void simulate_SJF(scheduling_data_t *data, int n_data, char *output_filename)
{
queue_t *ready_queue;
scheduling_data_t *proc;
int next_process;
int time;
ready_queue = new_queue(); /* create new queue */
printf("SJF CPU scheduling algorithm\n");
next_process = 0; /* next process to arrive */
time = 0; /* start at time 0 */
/* repeat while there are more processes arriving or there are waiting processes */
while(next_processsize !=0)
{
/* if one or more new processes have arrived */
while (next_process= data[next_process].AT)
enqueue_process(&data[next_process++], ready_queue); /* enqueue it */
if (ready_queue->size > 0)
{
proc = get_shortest_process(ready_queue); /* find shortest process */
proc->WT = time - proc->AT; /* calculate how much time it waited */
proc->TaT = proc->WT + proc->BT; /* calculate turn around time */
time += proc->BT; /* increment time by the burst time */
}
else
time++;
}
print_scheduling_data(data, n_data, output_filename);
free(ready_queue); /* free queue */
}
/*
* Purpose: simulates the Round-Robin scheduling
* Explanation: it creates a queue of processes depending on the arrival time,
* it selects the process in a FIFO manner and it executes it, when the quantum
* has elapsed it enqueues it again and it takes another process from the queue
* Parameters: data = array of scheduling data, n_data = number of entries in array
* output_filename = name of the file to use to save output
* Returns: None
* Advantages: every process has the chance to execute, no starvation occurs,
* all processes have the same priority
* Disadvantages: if the quantum is very short there are many process switchings
* so the efficiency is reduced
*/
void simulate_RR(scheduling_data_t *data, int n_data, char *output_filename)
{
queue_t *ready_queue;
scheduling_data_t *proc;
int next_process;
int time, tquant;
int quantum;
char c;
ready_queue = new_queue(); /* create new queue */
printf("Time Quantum?: ");
scanf("%d", &quantum);
while((c = getchar()) != '\n' && c != EOF); /* flush all input to get rid of newline */
printf("RR CPU scheduling algorithm\n");
next_process = 0; /* next process to arrive */
time = 0; /* start at time 0 */
tquant = 0; /* quantum time */
proc = NULL;
/* repeat while there are more processes arriving or there are waiting processes
or if theres a process still executing */
while(next_processsize !=0 || proc != NULL)
{
if (proc!=NULL && proc->T >= proc->BT) /* if the current process has terminated its burst time */
{
tquant = 0; /* restart quantum */
proc->WT = time - (proc->AT + proc->BT); /* calculate how much time it waited */
proc->TaT = time - proc->AT; /* calculate turn around time */
proc = dequeue_process(ready_queue); /* get another process from FIFO queue */
}
else if (tquant>= quantum) /* if a quantum has elapsed */
{
tquant = 0; /* restart quantum */
enqueue_process(proc, ready_queue); /* enqueue current process */
proc = dequeue_process(ready_queue); /* get another process from FIFO queue */
}
/* if one or more new processes have arrived */
while (next_process= data[next_process].AT)
enqueue_process(&data[next_process++], ready_queue); /* enqueue it */
if (proc == NULL)
proc = dequeue_process(ready_queue); /* get process from FIFO queue */
if(proc != NULL)
proc->T++; /* increment elapsed time of process */
time++; /* increment time */
tquant++; /* increment quantum time */
}
print_scheduling_data(data, n_data, output_filename);
free(ready_queue); /* free queue */
}
int main()
{
int selection;
int quit;
char input_filename[MAX_NAME]; /* input file name */
char output_filename[MAX_NAME]; /* output filename */
scheduling_data_t *data; /* scheduling data */
int n_data;
char c;
quit = 0; /* initialize quit to zero to enter loop */
while(!quit) /* repeat while the user doesn't select Quit */
{
show_menu(); /* show option menu */
scanf("%d", &selection); /* read the selected option from user */
while((c = getchar()) != '\n' && c != EOF); /* flush all input to get rid of newline */
if (selection >= 1 && selection <=3)
{
get_filenames(input_filename, output_filename); /* get filenames */
data = load_dataset(input_filename, &n_data); /* load dataset */
if (data != NULL) /* if there were no errors */
{
sort_by_AT(data, n_data); /* sort input data by arrival time */
switch (selection)
{
case 1:
simulate_FCFS(data, n_data, output_filename); /* do the FCFS scheduling */
break;
case 2:
simulate_SJF(data, n_data, output_filename); /* do the SJF scheduling */
break;
case 3:
simulate_RR(data, n_data, output_filename); /* do the RR scheduling */
break;
}
free(data); /* free dataset */
}
}
else if (selection == 4)
quit = 1; /* set variable to 1 to exit program */
else /* else, it was an invalid option */
printf("Invalid selection! Please try again\n");
printf("\n");
}
return 0;
}