Thread: Implementing priority CPU scheduling.

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?

I'm still confused over how to store a task in a linked list. So if a task arrives then I want to put it in my ready queue and place these tasks in the linked list based on their priority number. After a certain task is finished, I then want to grab whatever task is at the head of the linked list. I'm just having so much trouble figuring out how that works.

So then could I do something like this?

Code:

        if (tasks[current_tick].arrival_time <= current_tick + 1){
            nodes[current_tick].priority = tasks[current_tick].priority;
            n++;
            if (error) break;
            printf("priority = %d \n"), nodes[current_tick].priority;
            cleanup(&head, &tail);
        }

So when a task arrives, I want to store its priority number into the nodes list then I can search through the list and find the lowest priority number.

It would seem that the code was "borrowed" from somewhere since the OP doesn't seem to understand it at all.

I'm just trying to figure everything out and it's very confusing. So what I want to happen is I want to know when the task has arrived and when it has arrived I want to insert it into the linked list at the arrived position. I'll then go back to figuring out how to sort the linked list.

I actually didn't use that code. The code at the end of my post was given to me as part of the first come first serve algorithm and I added that for loop at the top. I know how priority scheduling works its just that everything I've tried doesn't run. What I want to happen is that whenever a new task arrives, I want to add that task in a ready queue and sort that queue so that the task with the lowest priority is at the front. Then when I pick the next task, I pick whatever value is at the head of the linked list. Here's something I've attempted to write which is supposed to store any newly arrived tasks in an array.

Code:

                if (tasks[i].arrival_time <= current_tick + 1 && tasks[i].cpu_cycles < tasks[i].length){
                    R[i] = tasks[i].priority;
                }