Algorithm code problem

[Djur0]

Ok i have the fallowing problem with this code. Exemple: If i have frame size 4, the first 4 numbers from string are stored correctly into the frame, but when the numbers in frame need to be replaced it replaces only the number which is in last spot of frame, so the algoritm isnt working correctly because of this.

here i read the string from a file and store it into array

 
                     .
                     . 
                     .
                     . 
            int num_frames= atoi(argv[1]);
            int frames[num_frames];
            int error=0;
            int j, avail,k;
            int n,b,v;
            int index_frame=-1;
            int idx_p=-1;
            int idx_pbest=-1;
            int idx_f=-1;
            

            for(i=0;i<num_frames;i++)
            {
                frames[i]= -1;
            }

            
            for(i=0;i<count;i++)
            {
                avail=0;
               for(k=0;k<num_frames;k++)
                {
                    if(frame[k]==ref_string[i])
                    {
                        printf("found %d: ",ref_string[i]);
                        for(k=0;k<num_frames;k++)
                     {                                      
                            printf(" %s %d","|",frame[k]);
                        }
                         avail=1;
                    }
                }
        
              if (avail==0)
              {
                    for(k=0;k<num_frames; k++)
                    {
                        if(frames[k]==-1)
                        {
                            index_frame=k;
                            break;
                        }
                    }        
                    
                    for(b=0; b<num_frames;b++)    
                    {
                        for(v=count-1; v>= i ;v--)
                        {
                            if(frame[b]==ref_string[v])
                            {
                                idx_p=v;
                            }
                        }

                        if(idx_pbest<idx_p)
                        {
                            idx_pbest=idx_p;
                            idx_f=b;
                        }        
                    }

                    if(index_frame !=-1)
                    {
                        
                        frame[index_frame]=ref_string[i];

                    }
                    else
                    {    
        
                            frames[idx_f]=ref_string[i];
            
                    }

                    
                    printf("insert %d: ",ref_string[i]);
                 error++;
            
                 for(k=0;k<num_frames;k++)
                 {                                      
                    printf(" %s %d","|",frames[k]);
                    }
                }
               printf("\n");
    
            }
           printf("Errors: %d%s",error,"\n");

        }

   return 0;

The algorithm is opt algorithm for page replacement

Ty for you help!

---

http://images.devshed.com/fds/buttons/reply_small.gif

[quzah]

Write out in words what it is you are actually trying to do. Don't take short cuts like "move a frame", say what that means exactly. Then turn those words into pseudo code. For example:

Words: "Swap two numbers."

Store one of the two numbers in a temporary variable.
Copy the second number over top of the first.
Copy the temporary number over top of the second.

Pseudo code:

temp = num1
num1 = num2
num2 = temp

If you can't do something like that for what you are trying to do, then you don't understand your problem, and won't be able to actually program it.


Quzah.

[Djur0]

Well do you know where the error is? I was looking at this code whole day and i didnt find why it is not working corectly....

[quzah]

Keep looking, because until you can do what I said, you won't understand how to program it, and I am not going to do it for you.


Quzah.

[iMalc]

I cant work out what it's supposed to do from the description. Perhaps some examples of what it should do would help?

[Djur0]

But i do know what it needs to do, just cant find the error. It supose to insert numbers from string to another array(reprisenting memory in computer, num of blocks). Than it checks if the number already exists in the array if it doesnt than it goes to look which number from frames array(blocks of memory) wont be used the longest(compers to string of numbers). That number should be than replaced with the number in ref string. But i dont know why it replace only the last number. Help!

[quzah]

Why is it so hard for you to do what was asked of you?


Quzah.

[iMalc]

Could you give a simple example of the input and output so that we can understand what it does please?

[Djur0]

Ok. So input is ref string that is read from file : 6 7 5 1 4 0 5 6 3 2 1 4 7 0 2 4 3 1 5 0 and numbers of frames are 3.

Output:

insert 6: | 6 | -1 | -1
insert 7: | 6 | 7 | -1
insert 5: | 6 | 7 | 5
insert 1: | 6 | 7 | 1
insert 4: | 6 | 7 | 4
insert 0: | 6 | 7 | 0
insert 5: | 6 | 7 | 5
found 6: | 6 | 7 | 5
insert 3: | 6 | 7 | 3
insert 2: | 6 | 7 | 2
insert 1: | 6 | 7 | 1
insert 4: | 6 | 7 | 4
found 7: | 6 | 7 | 4
insert 0: | 6 | 7 | 0
insert 2: | 6 | 7 | 2
insert 4: | 6 | 7 | 4
insert 3: | 6 | 7 | 3
insert 1: | 6 | 7 | 1
insert 5: | 6 | 7 | 5
insert 0: | 6 | 7 | 0
Errors: 18

You can se that the first 3 values are inserted correctly, but when there is no space in frames anymore it always replaces the last number. This algorithem should replace that number in frame which is not used for the longest time in the ref string.

Help pls!

[stahta01]

If I understand you are saying "insert 1" line was done wrong.

insert 6: | 6 | -1 | -1
insert 7: | 6 | 7 | -1
insert 5: | 6 | 7 | 5
insert 1: | 6 | 7 | 1

What is the correct way

insert 1: | 7 | 5 | 1

or

insert 1: | 1 | 7 | 5

NOTE: You really NEED to write out the algorithm you are trying to follow it words as quzah asked!

Tim S.

[Djur0]

First 3 lines are ok.

insert 6:  | 6 | -1 | -1
insert 7:  | 6 | 7 | -1
insert 5:  | 6 | 7 | 5

Down from here there is all wrong. It always insert the numbers to the last spot of frames. But it should look which number in frames wont be used for the longest time(numbers are compared to reference string.

Here is where it look which is number is used last.

                      for(b=0;b<num_frames;b++)
                      {
                            for(v=count-1; v>=i; v--)
                            {
                                if(frames[b]==ref_string[v])
                                {
                                    idx_p=v;
                                }
                            }

                            if(idx_pbest<idx_p)
                            {
                                idx_pbest=idx_p;
                                idx_f=b;
                            }
                      }

The correct output would be like this( ref string: 6 7 5 1 4 0 5 6 3 2 1 4 7 0 2 4 3 1 5 0 num of frames:3)

-1|-1|-1:
6|-1|-1:
6|7|-1:
6|7|5:
6|1|5:
6|4|5:
6|0|5:
6|0|5:
6|0|5:
3|0|5:
3|0|2:
1|0|2:
4|0|2:
7|0|2:
7|0|2:
7|0|2:
4|0|2:
3|0|2:
1|0|2:
5|0|2:
5|0|2

[Djur0]

Ok figure it out... Ty anyway!