I need to implement a non-preemptive priority scheduling in C. I'm having a few problems figuring out how this works. Here's what I have so far:
Code:
void priority_scheduling()
{
int current_task = 0;
int current_tick = 0;
struct process_priority;
int i;
for (;;) {
current_tick++;
if (current_task >= num_tasks) {
break;
}
if (tasks[current_task].arrival_time > current_tick-1) {
continue;
}
if (tasks[current_task].arrival_time <= current_tick){
for(i = 0; i<n; i++){
if(tasks[i].priority > tasks[current_task].priority){
insert(&head, i, &error);
}
}
}
tasks[current_task].cpu_cycles += 1.0;
if (tasks[current_task].cpu_cycles >= tasks[current_task].length) {
float quantum_fragment = tasks[current_task].cpu_cycles -
tasks[current_task].length;
tasks[current_task].cpu_cycles = tasks[current_task].length;
tasks[current_task].finish_time = current_tick - quantum_fragment;
tasks[current_task].dispatches = 1;
current_task = //whatever is at the front of the ready queue;
delete(&head, n, &error);
if (current_task > num_tasks) {
break;
}
tasks[current_task].cpu_cycles += quantum_fragment;
}
}
}
I'm not sure if this code is correct but what I want to do is whenever a task arrives, it goes into the ready queue. I'm using a for loop to determine where the newly arrived task should be placed in the linked list based on its priority number. After the current task is done, the next task will be whatever is at the front of the priority queue.
The problem is that I don't know how to retrieve whatever value is at the head of a linked list. My other problem is with my insert and delete methods:
Code:
void insert(node_t* head, int at, int* error_code)
{
printf("\nAdding node at index %d\n", at);
node_t* curr = head;
bool update_index = false;
while(curr != NULL) {
if(curr->index == at) {
node_t* node = (node_t*)(malloc(sizeof(node_t)));
if(node == NULL) {
printf("malloc failed!");
break;
}
node->index = at;
node->prev = curr->prev;
node->next = curr;
curr->prev->next = node;
curr->prev = node;
update_index = true;
}
if(update_index)
curr->index++;
curr = curr->next;
}
n++;
if (!update_index) {
(*error_code)++;
}
}
void delete(node_t* head, int at, int* error_code)
{
printf("\nDelete node at index %d\n", at);
node_t* curr = head;
bool update_index = false;
while(curr != NULL) {
if(curr->index == at) {
node_t* tmp = curr;
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
curr = curr->next;
free(tmp);
update_index = true;
}
if(update_index)
curr->index--;
curr = curr->next;
}
n--;
if (!update_index){
(*error_code)++;
}
}
The variable n is supposed to keep track of how many elements are in the linked list but I'm not sure where I need to increment/decrement my n value.
Here's my two struct declarations as well as some global varaibles:
Code:
typedef struct Task_t {
int arrival_time;
float length;
int priority;
float finish_time;
int dispatches;
float cpu_cycles;
} task_t;
typedef struct node_t
{
int index;
struct node_t *next;
struct node_t *prev;
} node_t;
void priority_scheduling(void);
void run_simulation(int, int);
void read_task_data(void);
void init_simulation_data(int);
void insert(node_t* head, int at, int* error_code);
void delete(node_t* head, int at, int* error_code);
int num_tasks = 0;
task_t *tasks = NULL;
int n;
node_t head = {.index = -1, .prev = NULL, .next = NULL};
int error = 0;
The data is read in from either a command line argument or a text file:
Code:
void read_task_data()
{
int max_tasks = 2;
int in_task_num, in_task_arrival, in_task_priority;
float in_task_length;
assert( tasks == NULL );
tasks = (task_t *)malloc(sizeof(task_t) * max_tasks);
if (tasks == NULL) {
fprintf(stderr, "error: malloc failure in read_task_data()\n");
exit(1);
}
num_tasks = 0;
while (!feof(stdin)) {
fscanf(stdin, "%d %d %f %d\n", &in_task_num,
&in_task_arrival, &in_task_length, &in_task_priority);
assert(num_tasks == in_task_num);
tasks[num_tasks].arrival_time = in_task_arrival;
tasks[num_tasks].length = in_task_length;
tasks[num_tasks].priority = in_task_priority;
num_tasks++;
if (num_tasks >= max_tasks) {
max_tasks *= 2;
tasks = (task_t *)realloc(tasks, sizeof(task_t) * max_tasks);
if (tasks == NULL) {
fprintf(stderr, "error: malloc failure in read_task_data()\n");
exit(1);
}
}
}
}
void init_simulation_data(int algorithm)
{
int i;
for (i = 0; i < num_tasks; i++) {
tasks[i].finish_time = 0.0;
tasks[i].dispatches = 0;
tasks[i].cpu_cycles = 0.0;
}
}
And for comparison, here's a first come first serve scheduling method that I tested and it is working:
Code:
void first_come_first_serve()
{
int current_task = 0;
int current_tick = 0;
for (;;) {
current_tick++;
if (current_task >= num_tasks) {
break;
}
if (tasks[current_task].arrival_time > current_tick-1) {
continue;
}
tasks[current_task].cpu_cycles += 1.0;
if (tasks[current_task].cpu_cycles >= tasks[current_task].length) {
float quantum_fragment = tasks[current_task].cpu_cycles -
tasks[current_task].length;
tasks[current_task].cpu_cycles = tasks[current_task].length;
tasks[current_task].finish_time = current_tick - quantum_fragment;
tasks[current_task].dispatches = 1;
current_task++;
if (current_task > num_tasks) {
break;
}
tasks[current_task].cpu_cycles += quantum_fragment;
}
}
}
So using this, how would I make a priority scheduler work?