Project

General

Profile

Actions

Task #4055

closed

[mmu] Определение политики вытеснения PLRU

Added by Alexander Kamkin about 11 years ago. Updated almost 11 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
-
Target version:
-
Start date:
04/02/2013
Due date:
% Done:

0%

Estimated time:
Spent time:
Detected in build:
svn
Published in build:

Description

Насколько я понимаю, политика вытеснения PLRU (Pseudo Least Recently Used) до сих пор не определена.

Actions #1

Updated by Alexander Kamkin about 11 years ago

Я обещал описать алгоритм. Если я ничего не путаю, алгоритм следующий.

Пусть ассоциативность равна N.

Для вытеснения используются N бит (bits). В начальный момент они инициализируются нулем (bits = 0;).

При попадании в колонку с номером i, в i-ый бит записывается 1 (bits |= (1 << i);). Если все биты при этом становяться равными 1, они все дружно обнуляются 0 (if(bits == (1 << N) - 1) { bits = 0; }).

При промахе ищется индекс первого нулевого бита (for(int i = 0; ...) { if((bits & (1 << i)) != 0) { return i; } }).

Actions #2

Updated by Taya Sergeeva almost 11 years ago

  • Status changed from New to Resolved

r1178.

Actions #3

Updated by Alexander Kamkin almost 11 years ago

  • Status changed from Resolved to Open

Таня, нужно проверять то, что пишется. Я говорю даже не о тестах, а визуальной инспекции кода.

Для чего, например, нужен массив plru? Он заполняется в конструкторе, но потом не используется. Или, например, вот этот код:

if (bits != (1 << i)) 
{
    bits = 1;
} 

У меня было написано bits |= (1 << i) (установка в 1 i-ого бита), a не bits != (1 << i).

Как в коде выражается условие попадания в i-ую строку множества?

Нельзя писать код, если до конца не понимаешь, как устроен алгоритм. Получается никому не нужный код, который остается только выкинуть и написать новый. Какая от этого польза? Зачем тратить на это время?

Подход простой:

1. Понять (в деталях) как устроен алгоритм/программа/система (какие функции, как эти функции реализуются и т.п.);
2. Аккуратно запрограммировать задуманное (каждая строчка должна быть осмысленной).
3. Не менее аккуратно проверифицировать/протестировать написанный код.

P.S. Еще раз. Нужно понимать назначение каждой строки написанного кода. Если нет понимания, код - в мусорный бак. Его нельзя использовать. Если автор его не понимает, его не поймет никто.

Применительно к политике замещения данных нужно четко понимать что такое политика замещения, какие у нее функции, как эти функции реализуются и т.п.

Actions #4

Updated by Alexander Kamkin almost 11 years ago

Предлагаю попробовать еще раз. Расчитываю на серьезный, вдумчивый подход.

Actions #5

Updated by Alexander Kamkin almost 11 years ago

Также давай договоримся, что работа не считается выполненной, пока не написаны (и не пройдены) тесты, не написаны комментарии.

Символы табуляции нужно заменить на пробелы (1 tab -> 4 spaces).

P.S. Лучше делать медленно, но качественно, чем быстро, но плохо. (в последнем случае не делается ничего.)

Actions #6

Updated by Taya Sergeeva almost 11 years ago

  • Status changed from Open to Resolved

r1250

Actions #7

Updated by Alexander Kamkin almost 11 years ago

Стало лучше, но вопросы остались

Методы hit и miss не нужны (ни в классе Policy, ни в его наследниках).

public abstract void hit(Address address);
public abstract int miss(Address address);

choseVictim нужно переименовать в chooseVictim.

public abstract void accessLine(int index);
public abstract int choseVictim();

При перегрузке методов базового класса нужно указывать аннотацию @Override.

Комментарии к методам accessLine и chooseVictim лучше перенести в базовый класс Policy. А в классах-наследниках писать

/**
 * {@inheritDoc}
 */
@Override
public void accessLine(int i) { ... }

В начало файла нужно поместить комментарий с APL (см. мои файлы).

Не забываем писать автора кода

/**
 * This class implements ...
 *
 * @author <a href="mailto:leonsia@ispras.ru">Taya Sergeeva</a>
 */
class X { ... }

И, конечно, общий тест на политики вытеснения.

Actions #8

Updated by Taya Sergeeva almost 11 years ago

r1252

Actions #9

Updated by Alexander Kamkin almost 11 years ago

  • Status changed from Resolved to Closed
Actions

Also available in: Atom PDF