Task #4055
closed[mmu] Определение политики вытеснения PLRU
Description
Насколько я понимаю, политика вытеснения PLRU (Pseudo Least Recently Used) до сих пор не определена.
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; } }).
Updated by Alexander Kamkin about 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. Еще раз. Нужно понимать назначение каждой строки написанного кода. Если нет понимания, код - в мусорный бак. Его нельзя использовать. Если автор его не понимает, его не поймет никто.
Применительно к политике замещения данных нужно четко понимать что такое политика замещения, какие у нее функции, как эти функции реализуются и т.п.
Updated by Alexander Kamkin about 11 years ago
Предлагаю попробовать еще раз. Расчитываю на серьезный, вдумчивый подход.
Updated by Alexander Kamkin about 11 years ago
Также давай договоримся, что работа не считается выполненной, пока не написаны (и не пройдены) тесты, не написаны комментарии.
Символы табуляции нужно заменить на пробелы (1 tab -> 4 spaces).
P.S. Лучше делать медленно, но качественно, чем быстро, но плохо. (в последнем случае не делается ничего.)
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 { ... }
И, конечно, общий тест на политики вытеснения.
Updated by Alexander Kamkin almost 11 years ago
- Status changed from Resolved to Closed