Алгоритм для поиска самых новых значений n

Question

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

Для сохранения истории данные сначала записываются на 1-ю страницу, а когда она заполнена, следующая страница должна использоваться. Наконец, последняя страница также заполнена, поэтому мы должны стереть данные на первой странице и использовать первую страницу. И так далее ...

Как я могу узнать, какая из страниц является «самой старой»? Как определить, что удалить?

Я думаю, что необходим счетчик, и этот счетчик увеличивается каждый раз, когда используется новая страница. Значения счетчика считаются в начале, чтобы найти, какая страница является самой новой, а затем следующая страница является самой старой (с момента кругового подхода). Однако, в конечном счете счетчик будет переполняться, счетчик перезагрузится, и будет невозможно убедиться, какое значение является самым высоким (поскольку новое значение равно 0).

Пример:

• 0 0 0 (от начала) (использовался page0)
• 1 2 0 (был использован стр.1)
• 1 2 3 (стр.2 было был использован используется)
• 4 2 3 (page0) использовали
• 4 5 3 (стр.1)
• ...
• 255 0 254 (я не знаю ...)

Является ли проблема понятной? В противном случае я могу попытаться объяснить.

Answer 1

Это метод, используемый в EEPROM износостойкость. Понятие состоит в том, что, поскольку EEPROM обычно имеет ограниченный срок службы циклов записи/стирания, мы балансируем износ в памяти, чтобы эффективно увеличивалась жизнь. Поскольку данные в EEPROM остаются в контроллере даже при выключении питания, нам может потребоваться периодически сохранять значения журнала некоторых переменных на EEPROM для дальнейшего использования.

Один простой подход, которым вы можете следовать, заключается в том, что, как предложено в комментариях, вы можете обновить счетчик, продолжая вычислять (счетчик по модулю 3).

Другой (более общий) подход состоит в том, чтобы иметь три регистра для счетчика.Всякий раз, когда вы должны написать на странице первого сканирования эти три регистра и проверить комбинации, где (C[i] != C[i-1] + 1)

0 0 0 
1 0 0 // 1 to 0 
1 2 0 // 2 to 0 
1 2 3 // 3 to 1 
4 2 3 // 4 to 2 
... 
255 0 254 // 0 to 254. 

Эта ссылка имеет больше информации об этой теме: Is there a general algorithm for microcontroller EEPROM wear leveling?

Answer 2

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

Причина, в которой вы нуждаетесь, заключается в том, что в начале - пока буфер не будет заполнен - ​​только один из них будет продвигаться, а другой останется неподвижным.

Answer 3

я такого рода циклы, как это:

// init 
int page0=adress of page0; // oldest data 
int page1=adress of page1; // old data 
int page2=adress of page2; // actual data (page for write) 

// after page 2 is full 
int tmp; 
tmp=page0; 
page0=page1; 
page1=page2; 
page2=tmp; 

• таким образом, вы знаете, какой ВСЕГДА страница, которая
• ра GE 0 ВСЕГДА старейшие данные
• страница 1 ВСЕГДА старые данные
• страница 2 ВСЕГДА фактические данные
• это легко расширяемой на любое количество страниц
• вместо адреса Вы можете сохранить номер страницы ... используйте то, что больше подходит для вашей задачи