Order Now  +1 678 648 4277 

Scheduling algorithms for a single CPU in C programming assignment help

The assignment deals with simulating different scheduling algorithms using C. The program makes use of the queue data structure to keep track of the processes. Every process is modeled using a structure that holds all the process data. The program is interactive and uses a menu to select the algorithm to simulate. The process data is loaded from a file. The simulation ends by displaying the average turnaround time and the average waiting time for the simulated processes. Below is a demonstration of the quality of work you get from our C programming assignment help platform.

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