Pointer issues (I think)

[rissarissole]

Hi guys, hoping you can help me out a little here!

I have done C programming a bit before (basic knowledge) but I haven't done any for a while and am pretty rusty, so I apologise for that in advance! I have searched the net and my books but I think I've been staring at the code so long my brain just can't process it anymore!

The code below is part of an operating system scheduling program (runs through SIMCORE). I think the problem is on the lines that I've put "//***" afterwards. Everything compiles fine but when I run it it never terminates, just continually loops. I think the problem is that I'm assigning a pointer to another pointer, making them reference the same thing - is that right? If so, how should I keep a reference to the highest priority node?

READY_Q is a struct containing next and pcb, and pcb is a struct containing a range of things.

What I'm trying to do is find the process with the highest priority (the program does this bit fine) and then store a reference to the node containing that process and a reference to the node before it (so that I can remove it from the linked list). Of course, I have to get to the end of the linked list before I know if I have found the highest priority process.

Hopefully that makes sense, please let me know if I need to include some other information.
Basically, is the pointer thing my problem? Or is there something else that I've overlooked? Thanks for all your help!

static PCB *find_highest_priority_pcb()
{
	READY_Q  *highest_prior, *prev_highest_prior, *next_rdy, *prev_next_rdy;  /* pointer to READY_Q  */
	PCB      *ret_pcb;

	/* initialise variables */
	prev_next_rdy = NULL;
	prev_highest_prior = NULL;
	highest_prior = ready_q.head; 
	next_rdy  = ready_q.head;
	
	/* Find the highest priority process. */
	int prev_priority = highest_prior->pcb->priority;
	
	while(next_rdy != NULL){
		int priority = next_rdy->pcb->priority;
		
		if (priority > prev_priority){
			highest_prior = next_rdy;		//***
			prev_highest_prior = prev_next_rdy;	//***
			prev_priority = priority;
		}
		next_rdy = next_rdy->next;
	}	

	/* Remove the selected process from the ready queue (list). */
	if (prev_highest_prior != NULL){
		prev_highest_prior->next = highest_prior->next; //***
	}
	highest_prior->next = NULL;

	ret_pcb = highest_prior->pcb;
	free(highest_prior);
	return(ret_pcb);
}

[Salem]

One thing you're not doing is updating ready_q if the node you remove is at the head of the list.

A few useful desk checks when working with linked lists
- does it make sense on an empty list
- does it make sense with only one element in the list
- does it make sense for the head and tail elements of the list

[rasta_freak]

There's missing

prev_next_rdy = next_rdy;

before

next_rdy = next_rdy->next;

[rissarissole]

Thanks for your help! I've fixed those bits, but I'm still having issues with behaviour.

The following code compiles but gives "Idle CPU with non-empty ready queue" warnings when run, which isn't what it should be doing. The performance of this code is *massively* slower and less efficient than round robin (counter productive!)

That's why I thought my pointers were messed up. Could that be causing a problem or is my logic off?

static PCB *find_highest_priority_pcb()
{
	READY_Q  *highest_prior, *prev_highest_prior, *next_rdy, *prev_next_rdy;  /* pointer to READY_Q  */
	PCB      *ret_pcb;

	/* initialise variables */
	prev_next_rdy = NULL;
	prev_highest_prior = NULL;
	highest_prior = ready_q.head;    /* assume head pcb has the lowest cost */
	next_rdy  = ready_q.head;
	
	/* Find the highest priority process. */
	int prev_priority = highest_prior->pcb->priority;
	
	while(next_rdy != NULL){
		int priority = next_rdy->pcb->priority;
		
		if (priority > prev_priority){
		
			highest_prior = next_rdy;		//***
			prev_highest_prior = prev_next_rdy;	//***
			prev_priority = priority;
		}
		prev_next_rdy = next_rdy;
		next_rdy = next_rdy->next;
	}	

	/* Remove the selected process from the ready queue (list). */
	if (prev_highest_prior != NULL){
		prev_highest_prior->next = highest_prior->next; //***
	} else {
		ready_q.head = ready_q.head->next;
	}
	
	highest_prior->next = NULL;

	ret_pcb = highest_prior->pcb;
	free(highest_prior);
	return(ret_pcb);
}

If the list is empty, this function doesn't get called. If there is only one element, it is both the head and tail element, and next is set to NULL, so it still is OK for those situtations.

Thanks so much for your quick replies and pick ups on those bits and pieces! Like I said, I've been staring at the same piece of code so long it's getting confusing, so your help is *very* appreciated!

[rasta_freak]

Shouldn't there be something like

ready_q.head=NULL;

when you free last one (like Salem said)?

EDIT: ah, sorry, didn't see that line...

EDIT2: just a tiny note - "highest_prior->next = NULL;" has no effect when you free() it immediately after that.

[rissarissole]

You're right, thanks! For now I'll put a comment next to it, I won't take it out (in case I need it for some reason later and forget about it, lol).

The big issue wasn't the pointers, it's in my priority calulation! I finally found it.

Thanks for all of your help! If you do notice anything else though, please let me know.

(I feel really silly now - thanks for being patient!)