Like Tree4Likes

I need help with looping lowest priority values first

This is a discussion on I need help with looping lowest priority values first within the C Programming forums, part of the General Programming Boards category; Starting with your code from the last message: Code: while(needToContinue) { needToContinue = false; for(num_procs=0;num_procs<199;++num_procs)//loop through the array { while ...

  1. #16
    Registered User
    Join Date
    Jun 2010
    Location
    Michigan, USA
    Posts
    138
    Starting with your code from the last message:
    Code:
    while(needToContinue)
    {
    needToContinue = false;
    
    	for(num_procs=0;num_procs<199;++num_procs)//loop through the array
    	{
    	while (proc[num_procs].priority) {
    	do { 
    		while (proc[num_procs].priority == 0 ) 
    		{
    			proc[num_procs].quantum--; // this seems to be doing nothing 
    			printf("%s %d %d \n",proc[num_procs].id, proc[num_procs].quantum, proc[num_procs].priority);
    	 	} 
    	   } 	while (proc[num_procs].quantum > 0 ); // ensure theres quatum left
    	}	
    		if(proc[num_procs].quantum > 0)
    		{
    		proc[num_procs].quantum--;
    		printf("%s %d %d \n",proc[num_procs].id, proc[num_procs].quantum, proc[num_procs].priority);
    		}
    	}
    }
    I changed the indentation to make it readable to me. You did not have a consistent indentation style. You may not like mine; fine. But you need a consistent one. With a new indentation it looks like:

    Code:
    while(needToContinue)
    {
       needToContinue = false;
     
       for(num_procs=0;num_procs<199;++num_procs)//loop through the array
       {
          while (proc[num_procs].priority) {
             do { 
                while (proc[num_procs].priority == 0 ) 
                {
                   proc[num_procs].quantum--; // this seems to be doing nothing 
                   printf("%s %d %d \n",
                           proc[num_procs].id, 
                           proc[num_procs].quantum, 
                           proc[num_procs].priority);
                } 
             } while (proc[num_procs].quantum > 0 ); // ensure theres quatum left
          }   
          if(proc[num_procs].quantum > 0)
          {
             proc[num_procs].quantum--;
             printf("%s %d %d \n",
                     proc[num_procs].id, 
    	         proc[num_procs].quantum, 
                     proc[num_procs].priority);
          }
       }
    }
    So you have four layers of loop structures. Most people cannot manage code with four layers of loops.

    But lets see what we can learn from some simple restructuring. I am NOT trying to change the function of the code. I am going to show you my thinking as we go.

    I am NOT testing these changes so I could easily make an error.

    I am not trying to fix this code, because I do not understand what you are trying to do. I do not think you have given a clear explanation of what you are trying to do.

    Code:
    while(needToContinue)
    {
       needToContinue = false;
     
       .
       .
       .
    }
    OK, this is outter most loop. Unless, I missed something, needToContinue is not set anywhere else inside the loop. So this loop will execute 0 or 1 times depending on the initial value of needToContinue. Well, 0 or 1 times sounds like an if statement.


    Code:
    if (needToContinue)
    {
       .
       .
       .
    }
    Inside the if statement, we have this for loop.

    Code:
     
       for(num_procs=0;num_procs<199;++num_procs)//loop through the array
       {
           .
           .
           .
       }
    It contains a while loop and an if statement. That for loop seems straight forward. Let's look at the while loop.

    Code:
          while (proc[num_procs].priority) {
             .
             .
             .
          }
    This while loop executes 0 times if proc[num_procs].priority is 0. Since this value is not changed inside the loop, if it is not zero this will be an infinite loop unless the value of the .priority changes during the loop or if there is a break or goto statement in the loop.

    Since it is an infinite loop, the if statement that follows it will never be executed.

    Inside the probably infinite while loop, we have a do ... while loop. And inside it is a while loop. It is only inside that inner while loop that we decrement the proc[num_procs].quantum which controls this loop. Since this is a do ... while loop we will execute at least one time.
    Code:
             do { 
                while (proc[num_procs].priority == 0 ) 
                {
                   proc[num_procs].quantum--; // this seems to be doing nothing 
                   printf("%s %d %d \n",
                           proc[num_procs].id, 
                           proc[num_procs].quantum, 
                           proc[num_procs].priority);
                } 
             } while (proc[num_procs].quantum > 0 ); // ensure theres quatum left
    Now to look at that inner while loop. It executes 0 times if proc[num_procs].priority is not 0 and probably infinite times if it is zero. But from the outer while loop that we looked at earlier (the one that probably is infinite), we know that proc[num_procs].priority is not zero. So the contents of this while loop will not execute. That would explain why the decrement statement that you put the comment on saying "this seems to be doing nothing" is correct because it never gets executed.

    I hope this helps you to read your own code. And it provides a beginning to restructuring your code to do what you really want (whatever that is).
    Last edited by pheininger; 01-17-2012 at 05:33 PM.

  2. #17
    Registered User
    Join Date
    Nov 2011
    Location
    Saratoga, California, USA
    Posts
    334
    First, stop hacking your code in the hopes that you "make progress". You're not, and your last code doesn't even make sense (less sense than the first post!). You need to think and plan your solution before you touch the keyboard.

    The way you've set it up, you want to give cpu time to each process at the same priority level starting with priority 0 until none of those processes has/or requires any more quanta. So you want to make a single pass across this subset until all are at quantum 0. Each pass is your innermost loop, and outside of that is a continuous loop until all quantum are zero.
    Of course you want to process until your entire array has been gone through. This is your outermost loop.

    Now, all you need is a marker for where to begin the innermost loop. Then ask, what condition will stop that loop. Now ask yourself, what will the loop counter be pointing to when the loop condition fails - and should I save it?! After that, it's trivial to just use a flag like hasQuanta to continually restart your innermost loop, with your intermediate loop. And the conditional for ending the whole process should be obvious for your outermost loop.

    With all that said, you're approach is going to hit a wall if you ever try to expand on it. (But don't change your whole code on account of what I'm going to say unless you really, really want to ).

    What you're implementing is actually not Round Robin at the highest level. What you are trying to do is called Multilevel Queue Scheduling. And the name kind of gives away what you should be doing. Based on some given criteria, i.e. priority, every process goes into an appropriate queue of some particular level. Then, each queue would have a scheduling algorithm applied to it, i.e. Round Robin, depending on how it should be handled.

    Your approach will show its weaknesses when you move on to Multilevel Feedback Queue Scheduling or even move on to adding processes into the queue at some later time - a.k.a. the real world.

    Well, hope the above helped and good luck.

  3. #18
    Registered User spendotw's Avatar
    Join Date
    Dec 2011
    Location
    England
    Posts
    40

    Question

    Thanks for your feedback guys, I have took what you said into consideration, but with some of the terminology used I didn't quite understand :\ sorry.

    Right, after revising my code I have managed to do exactly what i wanted to do, but only with priorities that are of value 0. Which for me is better than nothing.

    I know what i need to do know, and that is to get something that will reference where my first process of that priority group is at, so that i can return. As my index is at [0] on this line it only works for the priority group 0. But i need something that will do this for all priority values.

    And again with the highest_priority variable i need this to jump back to the loop, increment by 1, return to back to the loop to process that priority value. You're probably laughing at me using something like the goto statement but as i said im new to C and i'm trying my hardest.

    Sorry if i haven't written this very clear, i'm not the best at explaining myself
    Thank you for any feed back
    Code:
    proc[num_procs].priority = proc[0].priority; // go back to the first process of
    Code:
    int highest_priority = 0;
    bool needToContinue = 1;
    while(needToContinue)
    {
        priority: 
        //reset the flag each loop of the array
        needToContinue = false;
        
        //loop thru the entire array
        for(num_procs=0;num_procs<199;++num_procs) //loop through the array
        {
        do { 
            if (proc[num_procs].quantum > 0 ) // As long as theres qauntum left
            {
                if ( proc[num_procs].priority == highest_priority ) // and the priority is the current highest
                {
                    proc[num_procs].quantum--; // give process time on cpu 
                    printf("%s %d %d \n",
                    proc[num_procs].id,
                    proc[num_procs].quantum, 
                    proc[num_procs].priority);
                    ++num_procs; // move the index onto the next process
                }
                if ( proc[num_procs].priority != highest_priority ) // if its last process, of that priority group
                proc[num_procs].priority = proc[0].priority; // go back to the first process of that priority group
    
                needToContinue = true; // Return to outer while loop  
             } 
           }    
                   while (proc[num_procs].quantum > 0); // checking process is 'still alive'          
        }
    }
    /* I was thinking something very roughly along the lines of this */
    if ( highest_priority < 20 ) // return to outer while loop to go through the whole process again
    {
    ++highest_priority; // go to next priority group 0, 1, 2, ... 20
    goto priority;
    }
    Last edited by spendotw; 01-18-2012 at 09:54 AM.

  4. #19
    Registered User spendotw's Avatar
    Join Date
    Dec 2011
    Location
    England
    Posts
    40
    Quote Originally Posted by spendotw View Post
    Thanks for your feedback guys, I have took what you said into consideration, but with some of the terminology used I didn't quite understand :\ sorry.

    Right, after revising my code I have managed to do exactly what i wanted to do, but only with priorities that are of value 0. Which for me is better than nothing.

    I know what i need to do know, and that is to get something that will reference where my first process of that priority group is at, so that i can return. As my index is at [0] on this line it only works for the priority group 0. But i need something that will do this for all priority values.

    And again with the highest_priority variable i need this to jump back to the loop, increment by 1, return to back to the loop to process that priority value. You're probably laughing at me using something like the goto statement but as i said im new to C and i'm trying my hardest.

    Sorry if i haven't written this very clear, i'm not the best at explaining myself
    Thank you for any feed back
    Code:
    proc[num_procs].priority = proc[0].priority; // go back to the first process of
    Code:
    int highest_priority = 0;
    bool needToContinue = 1;
    while(needToContinue)
    {
        priority: 
        //reset the flag each loop of the array
        needToContinue = false;
        
        //loop thru the entire array
        for(num_procs=0;num_procs<199;++num_procs) //loop through the array
        {
        do { 
            if (proc[num_procs].quantum > 0 ) // As long as theres qauntum left
            {
                if ( proc[num_procs].priority == highest_priority ) // and the priority is the current highest
                {
                    proc[num_procs].quantum--; // give process time on cpu 
                    printf("%s %d %d \n",
                    proc[num_procs].id,
                    proc[num_procs].quantum, 
                    proc[num_procs].priority);
                    ++num_procs; // move the index onto the next process
                }
                if ( proc[num_procs].priority != highest_priority ) // if its last process, of that priority group
                proc[num_procs].priority = proc[0].priority; // go back to the first process of that priority group
    
                needToContinue = true; // Return to outer while loop  
             } 
           }    
                   while (proc[num_procs].quantum > 0); // checking process is 'still alive'          
        }
    }
    Code:
     
    /* I was thinking something very roughly along the lines of this */
    if ( highest_priority < 20 ) // return to outer while loop to go through the whole process again
    {
        ++highest_priority; // go to next priority group 0, 1, 2, ... 20
        goto priority;
    }

    Actually i'v just looked back at this and i can see that it doesn't process the processes with priority of 0 it processes them all but is displaying them with a priority of 0

    Feel free to ignore this post, because this has got the best of me and i don't have no idea what to do with it now

  5. #20
    Registered User
    Join Date
    Nov 2011
    Location
    Saratoga, California, USA
    Posts
    334
    I tried to work with what you've written rather than just push my approach on you, but the number of problems in your code made me stop. So...

    Imagine a really dumb assembly-line worker standing in front of a long line of ordered boxes (processes) each with a number printed on the outside (priority) and each filled with various number of coins (quanta) and you are instructing him EXACTLY what you want him to do.

    Here's the algorithm of your program, starting at your for() loop...

    Start with first process (0) and
    1. continue until you go beyond process 199.
    2. If the current process has any quanta, check the priority
    2a. If the current process' priority is equal to our current priority, remove 1 quanta and move to the next process, otherwise,
    2b. do not remove anything, do not move on to the next process.
    3. If the current process' priority is NOT equal to our current priority, change it be so.
    4. Set the flag needToContinue to true, period. (and we loop indefinitely).
    5. Repeat steps 2-4 as long as whatever process you're at has quanta.
    6. Move to the next process from the one you are currently at and go to step 1.

    Compare that to the algorithm you want...

    Start with first process (0) and
    1. continue until you go beyond process 199.
    2. Set a marker "start" at the first process you are looking at so you remember where to come back to.
    3. Note what priority number is on the starting process.
    4. Do the following as long the process' priority is the same as noted in step 3.
    4a. If there are any quanta in the process, remove 1.
    4b. If there are any quanta still in the process, note that.
    4c. Move to the next process.
    5. You've moved to a process with a different priority, mark this process as "next", it is the beginning of the next set.
    6. If you noted any quanta left in any of the processes in step 4b, go back to the marker you set in step 2 and continue from step 3.
    7. Otherwise, move the marker you set in step 2 to where you placed marker "next" and continue from step 3.

    Note: a for() loop isn't called for in step 1, your outermost loop, because you are controlling how you move through the array deeper in, and it is not linear. So I'll give you a 1-shot outermost loop :
    Code:
    nextSubset = 0 ;
    while( start = nextSubset, start < 199 )  // magic number 199 in middle of code is bad by the way.
    {
      ...
    }

  6. #21
    Registered User spendotw's Avatar
    Join Date
    Dec 2011
    Location
    England
    Posts
    40
    There was a lot of unecessary stuff in the previous code:
    I removed the needToContinue flag. And now the current state of the program is that it compiles, it runs and executes all the priority 0's until the first process has no quantum left. But i need this to happen to each process not just the first one that makes it to 0 quantum. Once i have done this i can finally go onto writting a loop for the highest_priority variable so that it increments once a priority group has finished.

    Code:
     
    int highest_priority = 0;
    
    while(proc[num_procs].priority < 20)
    {
    	for(num_procs=0;num_procs<199;++num_procs) //loop through the array
    	{
    	
    	do { 
    		if (proc[num_procs].quantum > 0 ) // As long as theres qauntum left
    		{
    			if ( proc[num_procs].priority == highest_priority ) // and the priority is the current highest
    			{
    				proc[num_procs].quantum--; // give process time on cpu 
    				printf("%s %d %d \n",
    				proc[num_procs].id,
    				proc[num_procs].quantum, 
    				proc[num_procs].priority);
    				num_procs++; // move the index onto the next process
    				if ( proc[num_procs].priority > 0 ) // if last of that priority return to beginning of index
    				{ 
    					num_procs = 0;	
    				}
    			}
    			
    	 	} 
    	   }	
    	   		while (proc[num_procs].quantum > 0); // checking process is 'still alive'  		
    	} 
    }

  7. #22
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You needed to just go back and do what Salem said in the first post.
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #define PRIORITIES 3
    #define DEPTH 5
    #define QUEUE 10
    
    int main( void )
    {
        struct pqueue
        {
            int priority;
            int value;
        } pq[ QUEUE ];
        
        /* fill the queue with random junk */
        for( int x = 0; x < QUEUE; x++ )
        {
            pq[ x ].priority = x / (1 + PRIORITIES);
            pq[ x ].value = 1 + (rand () % DEPTH);
            printf( "pq[ %d ].priority %d, pq[ %d ].value %d\n",
                x, pq[ x ].priority, x, pq[ x ].value );
        }
        
        /* process each priority */
        for( int sb = 0, nsb = 0, priority = 0; priority < PRIORITIES; priority++ )
        {
            sb = nsb; /* Set the start bucket to the next start bucket. */
    
            printf( "Starting priority %d.\n", priority );
            /* process this priority level */
            for( int fp = 1, vsum = 0, ntp = 0, pcur = 0; ; pcur++ )
            {
    
                /* If we have gone too far... */
    
                if( sb + pcur == QUEUE || pq[ sb + pcur ].priority > priority )
                {
                    if( fp ) /* Is this the first pass? */
                    {
                        nsb = sb + pcur; /* set next bucket */
                        fp = 0;
                        ntp += vsum;
                        
                        printf( "Priority %d, vsum %d\n", priority, vsum );
                    }
                    pcur = 0; /* reset bucket */
    
                    if( ntp == 0 ) /* Do we have any that we need to process? */
                    {
                        printf( "Priority %d finished.\n\n", priority );
                        break;
                    }
                }
    
                /* If we have a value to process... */
                if( pq[ sb + pcur ].value > 0 )
                {
                    if( fp ) /* On the first pass, sum bucket values. */
                    {
                        vsum += pq[ sb + pcur ].value;
                    }
                    ntp--;
    
                    printf( "Processing priority %d, bucket pq[ %d ], value %d, ntp %d\n",
                        priority, sb + pcur, pq[ sb + pcur ].value, ntp );
                
                    pq[ sb + pcur ].value--;
                }      
            }
            
            
        }
    
        return 0;
    }

    Quzah.
    spendotw likes this.
    Hope is the first step on the road to disappointment.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating the lowest and highest values
    By Charak in forum C Programming
    Replies: 8
    Last Post: 01-30-2011, 08:57 PM
  2. Replies: 22
    Last Post: 11-13-2009, 04:51 PM
  3. Displaying highest and lowest values
    By beastofhonor in forum C++ Programming
    Replies: 3
    Last Post: 10-29-2006, 07:24 PM
  4. getting two lowest values in array by index
    By danielC++ in forum C++ Programming
    Replies: 8
    Last Post: 03-09-2005, 06:30 PM
  5. Finding lowest value
    By titleist_03 in forum C++ Programming
    Replies: 8
    Last Post: 11-09-2004, 07:11 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21