+1 678 648 4277 

Using Queue Data Structures to Simulate Processes

Scheduling algorithms for a single CPU in C programming assignment help

* 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; }