Как написать оптимальный алгоритм замены страницы?

Question

Я делюсь своей логикой. Мне нужно знать, хорошо ли это.

Я создал массив, который хранит общее количество вхождений для каждой страницы.

Например, последовательность требований к странице { 1,2,3,1,2}. Давайте назовем этоseq"массив.

Тогда массив = { 2,2,1 } . Давайте назовем этоcount"массив

Теперь я перебираю seq и распределить его по кадру, пока я не исчерпал все кадры или если кадр еще не находится в памяти. Затем я нажимаю на это кадр нет. а его оставшихся нет. вхождений в очередь с минимальным приоритетом.

    for (int i = 1; i <= M; ++i)
    {
        if (frameAssigned[arr[i]] != 0)    //frame already assigned
        {
            count[arr[i]]--;
            PQ.push(ii(count[arr[i]], arr[i]));
            continue;
        }

        if (freeFrames >= 1)
        {
            frameAssigned[arr[i]] = presentFrame++; //presentFrame=0 initially
            freeFrames--;
            noOfReplacements++;
            count[seq[i]]--;
            PQ.push(ii(count[seq[i]], seq[i]));
            continue;
        }

    //Now, if all free frames are exhausted, I do the following. Replace the page which is 
    //occurring the minimum number of times.

    ii temp = PQ.top(); // ii = pair<int,int>
    PQ.pop();
    int frameNumber = temp.second;
    count[seq[i]]--;
    if (seq[arr[i]] >= 0) PQ.push(ii(count[seq[i]], seq[i]));
    frameAssigned[arr[i]] = frameAssigned[custNumber];
    frameAssigned[custNumber] = 0;
    noOfReplacements++;

Однако этот алгоритм кажется неверным. Я не понимаю почему. Я нашел правильный алгоритм здесь, но я не понимаю, почему мой не работает.

Answer 1

Давайте посмотрим на следующую страницу вхождения:

1,2,3,2,3,2,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1

Предположим, что 2 страницы могут храниться в памяти. Согласно вашему алгоритму, когда 3 прибудет в первый раз, 2 будет заменено, потому что число вхождений 1 довольно велико, что не является оптимальным.

В оптимальном алгоритме замены страницы критерии замены страницы основаны на времени, по истечении которого на страницу снова будут ссылаться.

---

Я рекомендую вам пройти редакцию этой проблемы http://www.codechef.com/AUG14/problems/CLETAB только она исчезнет.