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?

> The variable n is supposed to keep track of how many elements are in the linked list
And how does that differ from int num_tasks ?

> Here's my two struct declarations as well as some global varaibles:
Yeah, far too many global variables.

You really ought to have something like

Code:

---

struct scheduler {
  task_t *tasks;  // array of tasks
  int numTasks;  // number of tasks present
  int maxTasks;  // max length of tasks (for malloc/realloc purposes)
  // other data
};

---

Then you would define your functions with say
void priority_scheduling(scheduler *sched)



Your linked list is just a list of numbers.
Shouldn't it be a list of tasks?

Besides, for the purposes of simulation, an array of tasks and a sorted array should be all you need.
Sorted insertion into the middle of a linked list is an optimisation.

Code:

---

int prioritysortfn( const void *a, const void *b ) {
  task_t **pa = a;
  task_t **pb = b;
  if ( pa->priority > pb->priority ) return -1;
  if ( pa->priority < pb->priority ) return +1;
  // priorities equal, now sort by arrival_time
  if ( pa->arrival_time < pb->arrival_time ) return -1;
  if ( pa->arrival_time > pb->arrival_time ) return +1;
  // both are the same
  return 0;
}

---

This should ensure that the highest priority, earliest arrival time task is always at the start of the array.

Call it with
qsort(tasks,numtasks,sizeof(*tasks),prioritysortfn );


> while (!feof(stdin))
See the FAQ for why this is wrong.
It would be better to do

Code:

---

while ( fscanf(stdin, "%d %d %f %d\n", &in_task_num,
            &in_task_arrival, &in_task_length, &in_task_priority) == 4 ) {
}

---

> assert(num_tasks == in_task_num);
Using assert to check user input is very bad (very BAD).
If asserts are disabled, the code does absolutely nothing.
If asserts are enabled, and triggered, then program halts immediately.
User input always needs to be checked, and always needs to be handled gracefully if it's wrong.

Your malloc/realloc need attention as well, but probably suffice for now.

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.

Your linked list needs two bits of information
- the data you want to store (which you presently have as int index)
- the linked list pointers.

So as an exercise, try this

Code:

---

#include <stdio.h>
#include <stdlib.h>

typedef struct node_t
{
    int value; // this will become task_t *task later
    struct node_t *next;
    struct node_t *prev;
} node_t;

node_t *listSortedInsert ( node_t *head, int data ) {
  node_t *newnode = malloc( sizeof(*newnode) );
  // carry on, write your code here
}

void listPrint ( node_t *head ) {
  while ( head != NULL ) {
    printf("%p %p : %d\n", head->prev, head->next, head->value );
    head = head->next;
  }
}

int main ( ) {
  node_t *list = NULL;
  for ( int i = 0 ; i < 10 ; i++ ) {
    list = listSortedInsert(list, rand() % 3);
  }
  listPrint(list);
}

---

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.

Indexing things by current_tick makes no sense.
I'm assuming current_tick is measuring time, so is increasing quite rapidly. Your arrays are NOT expanding at the same rate - surely.

You've gone off at a complete tangent, so I've no idea whether any existing problems have been solved, and your last post makes no sense in context.

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.

Quote:

---

Originally Posted by brandon236

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.

---

The arrival position is always the end of the list - given the only sensible arrival time is 'now', which will necessary be after all those tasks which arrived at some earlier time.

Sorting a whole list is a bit of a PITA.
Which is why I suggested you implement listSortedInsert() as an exercise.

So it would seem...
CSC-360/simsched.c at master * Hoverbear/CSC-360 * GitHub
cpu-scheduler/cpusched.c at master * jwsmithgit/cpu-scheduler * GitHub

Show something which is entirely your OWN attempt, then perhaps we can get to the bottom of where your knowledge is lacking.
I'm not going to waste my time retrofitting your requirements into someone else's crappy code.

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

---