0

我正在编写一个执行 3 页替换算法的程序。FIFO、LRU 和 OPT 我在这里假设“需求”分页。

我有FIFO，LRU完成了。但我不知道如何处理 OPT。我提示输入一个我正在读取的文件，并逐行解析为 pid 和一个类中的引用号。我也在提示帧大小。

文件结构如下：

1 45  // 1= pid,  45 = ref
1 46
1 45

对于 LRU，我使用了第二个数组来使用计数器跟踪最近最少使用的插槽。

我只是不知道该怎么做选择。我需要在我正在解析的文件中向前看吗？我需要第二个数组吗？

我正在逐行解析文件并将其添加到类中，如下所示。这是我为其他 2 种算法所做的，需要逐行解析文件并提示帧大小。我可以将文件存储在一个数组中并处理我猜想的数组。

class pagetable
{

public:
int pid;
int ref;
int faults;
pagetable();
};

并在 main()

ifstream inputStream;
cout << "\n\n\t*********** Virtual Memory Management Simulator ***********\n";
cout << "\n";


while(!done){
 pagetable* page = new pagetable[frames];

getFileName(inputStream);//asks for input filename until it is valid
   cout << "\nEnter in the number of frames:";
cin >> frames;
   faults = runsimLFU2(inputStream, page, frames );

int runsimLFU2(ifstream &inputStream, pagetable* page, int frames ){

int i =0;
int j=0;
int pid =0;
int ref = 0;
int index = 0;
int count = 0;
int pagefaults = 0;
int lowest=0;

int counter = 1;

int * LRU;
LRU = new int[frames];


while(1){

  inputStream >> pid;  //parse the file line by line
  inputStream >> ref;
      page[index].pid = pid;   //lets add it... when needed
  page[index].ref = ref;

我只是不确定当我解析文件并且缓存已满并且文件中的数字不在缓存中时该怎么办我怎么知道把它放在哪里？你能用编码术语解释一下吗？

用数组对其进行编码的方法是什么？我是否在第二个数组中保留一个计数器？有人可以解释一下最简单的方法吗？

请记住，该文件可能长达数百行。

4

2 回答 2

0

不清楚您所说的“最佳”是什么意思。最优化的替换算法将是无所不知的，并且会提前知道未来页面将被引用的顺序。

如果您假设“需求”分页，您将选择替换下一个将在未来被引用的最远距离的页面。

如果您还假设无所不知的预测分页，它可能会变得更加复杂——我不知道是否有一个简单的规则。

如果您不假设无所不知，那么“最佳”可能是由分页统计驱动的，并且您会选择将来在统计上最不可能被引用的页面进行替换。

于 2012-11-19T02:31:46.813 回答
0 
**Optimal Page Replacement Full Program in C Language**

#include<stdio.h>
int main()
{
    int frame_size, no_of_pages, flag1, flag2, flag3, i, j, k, pos, max, page_faults = 0, hit = 0;
    int pri[20][30], frames[10], pages[30], temp[10];
    char x[20];

    printf("Enter number of pages: ");
    scanf("%d", &no_of_pages);

        printf("Enter the pages: ");
        for(i = 0; i < no_of_pages; ++i)
        {
                scanf("%d", &pages[i]);
        }

        printf("Enter number of frames: ");
    scanf("%d", &frame_size);

        for(i=0; i< no_of_pages; i++)
        {
                x[i]='X';
        }
    for(i = 0; i < frame_size; ++i)
        {
                frames[i] = -1;
    }


    for(i = 0; i < no_of_pages; ++i)
        {
                flag1 = flag2 = 0;

                for(j = 0; j < frame_size; ++j)
                {
                    if(frames[j] == pages[i])
                        {
                           flag1 = flag2 = 1;
                           x[i]='*';
                           break;
                    }
                }

                if(flag1 == 0)
                {
                    for(j = 0; j < frame_size; ++j)
                        {
                                if(frames[j] == -1)
                                {
                                        page_faults++;
                                        //x[j]='*';
                                frames[j] = pages[i];
                                flag2 = 1;
                                    break;
                                }
                }
                }

                if(flag2 == 0)
                {
                    flag3 =0;

                    for(j = 0; j < frame_size; ++j)
                        {
                                temp[j] = -1;

                                for(k = i + 1; k < no_of_pages; ++k)
                                {
                                    if(frames[j] == pages[k])
                                        {
                                        temp[j] = k;
                                                break;
                                   }
                                }
                    }

                    for(j = 0; j < frame_size; ++j)
                        {
                                if(temp[j] == -1)
                                {
                                        pos = j;
                                flag3 = 1;
                                break;
                                }
                    }

                    if(flag3 ==0)
                        {
                                max = temp[0];
                                pos = 0;

                                for(j = 1; j < frame_size; ++j)
                                {
                                    if(temp[j] > max)
                                        {
                                                max = temp[j];
                                                pos = j;
                                    }
                                }
                }

                        frames[pos] = pages[i];
                page_faults++;
                }

                for(j = 0; j < frame_size; j++)
                {
                    pri[j][i]=frames[j];
                }
    }

    for(i = 0 ; i < no_of_pages*5+2*frame_size+1; i ++)
                {
                        printf("-");
                }
//              printf("\n|Frames |");
                        printf("\n|       |");
                for(i=0; i<= 2* no_of_pages + 6; i++)
                {
                        printf(" ");
                }
                printf("Pages");
                for(i=0; i<= 2*no_of_pages + 6; i++)
                {
                        printf(" ");
                }
                printf("|");
printf("\n|Frames |");

                        for(i = 0 ; i < no_of_pages*5+2*frame_size - 8; i ++)
                {
                        printf("-");
                }
                printf("\n|\t|");


        for(i=0 ; i < no_of_pages ; i++)
                {
                        printf(" %2d |",pages[i]);
                }
                printf("\n|");
                for(i = 0 ; i < no_of_pages*5+2*frame_size + 0; i ++)
                {
                        printf("-");
                }
                printf("\n");



    for(i=0;i<frame_size;i++)
    {
        printf("| %2d",i);
        printf("\t|");

                for(j = 0; j < no_of_pages; j++)
                {
                        if(pri[i][j]== -1)
                        {
                                printf("  - |");
                        }
                        else
                    printf(" %2d |",pri[i][j]);
                }
                printf("\n");
        }
        for(i = 0 ; i < no_of_pages*5+2*frame_size+1; i ++)
        {
                printf("-");
        }

        printf("\n|       |");
                                                                                  for(i = 0; i< no_of_pages; i++)
        {
                if(x[i]=='X')
                {
                        printf("\033[0;31m");
                        printf(" %2c ",x[i]);
                        printf("\033[0m");
                        printf("|");
                }
                else
                {
                        printf("\033[0;32m");
                        printf(" %2c ",x[i]);
                        printf("\033[0m");
                        printf("|");
                }
        }
        //printf("\033[0m")
        printf("\n");
        for(i = 0 ; i < no_of_pages*5+2*frame_size+1; i ++)
        {
                printf("-");
        }

        hit = no_of_pages-page_faults;


        printf("\n\n Total Page Faults =  Total No of pages - Total Pages hits  \n");
    printf("                   =        %d      -       %d      \n",no_of_pages,hit);
    printf("                   =        %d      \n",page_faults);

        printf("\n Total Page Hits = Total No of pages - Total Pages Miss \n ");
        printf("                =       %d      -       %d      \n",no_of_pages,page_faults);
        printf("                 =      %d      \n",hit);

    printf("\nTotal Page Fault ratio = Total Page faults / Total pages \n");
        printf("                       =        %d      /       %d      \n",page_faults,no_of_pages);
        printf("                       =        %5.2f   \n",((float)page_faults/no_of_pages));

    printf("\nTotal Page Hit ratio = Total Page hits / Total pages \n");
    printf("                     =      %d      /       %d      \n",(no_of_pages-page_faults),no_of_pages);
    printf("                     =      %5.2f   \n",((float)no_of_pages-page_faults)/no_of_pages);
printf("\n");
return 0;
}

**OUTPUT**

[enter image description here][1]


  [1]: https://i.stack.imgur.com/qYG6x.png
于 2020-01-08T03:49:41.733 回答