Нахождение последней записи, Помогите придумать надежный алгоритм Опции

[paskal]

Есть флеш память некоторого объема, куда последовательно одну за другой записываем страницы. Это значит что при каждой записи адрес увеличивается на размер страницы, а дойдя до конца памяти, адрес циклически возвращается к 0. Т.е. старые записи закрываются новыми. Для нахождения последней записи мы нумеруем их, и номер записываем вместе со страницей. Номеров больше чем страниц (например страниц 128, нумерация от 0 до 255). Естественно что и номера тоже циклически возвращаются к 0. При включении устройства мы просматриваем все страницы, и по номеру должны найти ту которая была записана последней.
Вопрос: какой алгоритм выбрать для нахождения последней записи? Задача осложнена тем, что устройство работает в условии помех и сбоев и существуют ошибочные номера. Алгоритм нужен такой чтоб если какая то страница один раз выбрана последней, потом после некоторой работы, включения-выключения, не могла бы выбраться более раняя запись.

[Dima_G]

Есть флеш память некоторого объема, куда последовательно одну за другой записываем страницы. Это значит что при каждой записи адрес увеличивается на размер страницы, а дойдя до конца памяти, адрес циклически возвращается к 0. Т.е. старые записи закрываются новыми. Для нахождения последней записи мы нумеруем их, и номер записываем вместе со страницей. Номеров больше чем страниц (например страниц 128, нумерация от 0 до 255). Естественно что и номера тоже циклически возвращаются к 0. При включении устройства мы просматриваем все страницы, и по номеру должны найти ту которая была записана последней.
Вопрос: какой алгоритм выбрать для нахождения последней записи? Задача осложнена тем, что устройство работает в условии помех и сбоев и существуют ошибочные номера. Алгоритм нужен такой чтоб если какая то страница один раз выбрана последней, потом после некоторой работы, включения-выключения, не могла бы выбраться более раняя запись.

По поводу алгоритма поиска - сравниваем индекс следующей страницы с текущей. Если он не равен текущий индекс + 1, то текущая страница - последняя.

На Си будет как-то так:

Код

//////////////////////////////////////////////////////
struct _sPage
{
  BYTE      bIndex;
  _sPage* psNext;
} sPage;

sPage* psCurPage_ = psFirst;

while (psCurPage_->bIndex + 1 == psCurPage_->psNext->bIndex)
  psCurPage_ = psCurPage_->psNext;

// psCurPage_ указывает на последнюю записанную страницу
//////////////////////////////////////////////////////

Про ошибочные номера нужно подробнее. Не понял что там может получиться

[_Pasha]

После записи блока данных заслать CRC32 всей наличной памяти. Как подсчет, так и проверка суть вещи медленные, но это 100% валидный маркер конца данных. От этого можно плясать в плане упрощения/ускорения

[Сергей Борщ]

Номеров больше чем страниц (например страниц 128, нумерация от 0 до 255).

Если использовать нумерацию по моджулю, не кратному количеству страниц (например, страниц 128, а нумеровать 0,1,2,3,4,5,0,1), то можно использовать количество номеров меньшее, чем количество страниц. Можно нумеровать вообще одним битом, если брать его с выхода генератора псевдослучайной последовательности. При поиске сдвиговый регистр загружается из подряд идущих страниц, замыкается обратная связь и он начинает генерить эталонную последовательность. Она сравнивается со считываемой из страниц. Несовпадение указывает на точку "разрыва" или на ошибочный номер. Можно сделать предположение о сбойнувшем номере и подставить вместо него номер с генератора образцовой последовательности. Если после этого синхронизация восстановилась - это был действительно сбой. Если нет - это была точка разрыва. Очень подробно эти приемы описаны в книге "синхронизация в телекоммуникационных системах. Анализ инженерных решений.". В интернете встречались сканы.

[paskal]

По поводу алгоритма поиска - сравниваем индекс следующей страницы с текущей. Если он не равен текущий индекс + 1, то текущая страница - последняя.
...........

Про ошибочные номера нужно подробнее. Не понял что там может получиться

Чтобы найти злополучный номер последней записи, я перебираю адреса страниц в обратном направлении, т.е. от 127 до 0. При этом я сравниваю разность соседних прочитанных номеров (которые от 0 до 255). Если разность больше 127, то это и есть граница последней записи. Например могут быть записаны такие номера:
0, 1, 2, 3, 4, 5, 86, 87 , 88... FE, FF - здесь последняя запись на номере 5
Или такие:
80, 81, 82, 83, 4, 5, 6, 7 .... 7E, 7F - здесь последняя запись на номере 83
В частном случае когда искомой разности не находится, например номера идут: 0, 1, 2 .... 7E, 7F то естественно последней записью считается последний адрес 7F.
Но все это в идеале. А в результате некорректной работы программы может быть искаженная последовательность:
0, 1, 2, 83, 84, 85, 6, 7 ... 7E, 7F
Здесь алгоритм определяет последнюю запись на номере 85. Далее до конца памяти исправно заполняется записями:
0, 1, 2, 83, 84, 85, 86, 87 .... FE, FF
И тут происходит сбой алгоритма. Теперь последней записью он находит старый номер 2, а все более новые записи с 83 по FF безвозвратно теряются!

Кстати, каждую запись я проверяю по CRC32, и если он неверен, запись пропускается.

Еще думаю, может что даст увеличение номера не на каждом следующем адресе, а только при циклическом возврате на нулевой адрес?

Если использовать нумерацию по моджулю, не кратному количеству страниц (например, страниц 128, а нумеровать 0,1,2,3,4,5,0,1), то можно использовать количество номеров меньшее, чем количество страниц. Можно нумеровать вообще одним битом, если брать его с выхода генератора псевдослучайной последовательности. При поиске сдвиговый регистр загружается из подряд идущих страниц, замыкается обратная связь и он начинает генерить эталонную последовательность. Она сравнивается со считываемой из страниц. Несовпадение указывает на точку "разрыва" или на ошибочный номер. Можно сделать предположение о сбойнувшем номере и подставить вместо него номер с генератора образцовой последовательности. Если после этого синхронизация восстановилась - это был действительно сбой. Если нет - это была точка разрыва. Очень подробно эти приемы описаны в книге "синхронизация в телекоммуникационных системах. Анализ инженерных решений.". В интернете встречались сканы.

одним битом кодировать действительно можно. Но для этого достаточно просто инвертировать его при циклическом возврате к началу. А что дает такое усложнение как псевдослучайная последовательность, я не понял. И спасет ли этот метод от сбойных записей?
ps
что то ссылка не работает

[scifi]

Как Вам такой вариант: для нумерации страниц использовать много разрядов, чтобы счётчик за время жизни устройства ни разу не переполнился. Тогда поиск последнего номера страницы очень простой: просто ищем максимальный номер.
Про сбои: они разные бывают. Если считать, что сбоить может что угодно и как угодно, то никакой алгоритм не поможет (может сбоить и процессор, и память программ). Поэтому по поводу сбоев в общем случае советовать что-либо бесполезно, сначала опишите задачу подробнее.

[paskal]

Как Вам такой вариант: для нумерации страниц использовать много разрядов, чтобы счётчик за время жизни устройства ни разу не переполнился. Тогда поиск последнего номера страницы очень простой: просто ищем максимальный номер.
Про сбои: они разные бывают. Если считать, что сбоить может что угодно и как угодно, то никакой алгоритм не поможет (может сбоить и процессор, и память программ). Поэтому по поводу сбоев в общем случае советовать что-либо бесполезно, сначала опишите задачу подробнее.

Использование большего количества разрядов разрядов действительно напрашивается. Но не подходит потому что не хватает места. Размер страницы 16 байт фиксирован физически, определяется устройством флеша. Я и так "утрамбовывал" данные по ниблам, осталось еще 4 разряда, а больше места не найти.
Сбоит только флеш, т.к. она сделана в виде внешней памяти, связанной по I2C. Процессор, и все что внутри него - ОЗУ, ПП, регистры, итд - не сбоит.
А смысл задачи в том, что в программе была ошибка. Из за неё во флеш писались неправильно номера страниц. К счастью ошибка вовремя обнаружилась и мне вернули из цеха кучу плат. Если просто записать правильную программу, то происходят описанные в предидущих постах глюки, т.к. последовательность номеров перепутана. Правда можно оставить плату включенной, подождать более 30 мин, за это время флеш целиком перезапишется корректными данными. Но учитывая количество понаделанных плат это жестокий метод
Вот и хотелось придумать алгоритм, чтоб правильно работал и с перепутанными номерами страниц не сбивая хронометраж записей.

[Baser]

Это ж какого размера у вас эта внешняя флеш?
Если это обычная I2C серия 24Схх, то больше нескольких мегабит быть не может.
Какие проблемы стереть(инициализировать) её после перепрошивки программы? Дело нескольких дополнительных секунд.

А по теме, взгляните тут, это не совсем то что вы спрашиваете, но очень близко...

[scifi]

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

Боюсь, нет такого алгоритма.
Если лень ждать 30 минут, то сделайте вспомогательную прошивку, которая перелопачивает флэш и исправляет неправильные номера страниц. Или сделайте эту процедуру частью стандартной прошивки.

[paskal]

Это ж какого размера у вас эта внешняя флеш?
Если это обычная I2C серия 24Схх, то больше нескольких мегабит быть не может.
Какие проблемы стереть(инициализировать) её после перепрошивки программы? Дело нескольких дополнительных секунд.

Технических проблем стереть действительно нет. К сожалению есть проблемы другого характера. Платы уже сданы заказчику. Я забирал их неофициально, но если они увидят что все счетчики обнулились, поднимется скандал, а это военная приемка, от них просто так не отвяжешся.
Записывать определенное значение, тоже возни много. Каждую страницу я защитил кодом CRC32. Для каждой платы нужно составлять свои данные, вычилсять ЦРЦ... в конечном итоге лучше 40 минут подождать, ведь само делается . Собственно я так пока и делаю.
Пробовал еще стирать не всю флеш, но это тоже не помогает в плане оперативности.

А по теме, взгляните тут, это не совсем то что вы спрашиваете, но очень близко...

Да, это точно такое же устройство, но то что там обсуждают, я для себя уже решил.

[ssvSerge]

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

А вам необходимо нумеровать и записи и страницы?
Или это лишь предложенное решение задачи?

Мне представяется, что можно обойтись "бегущей единицей" всего лишь.
Эталоном будет первый блок.
Если в нем записана "1", то это значит, что надо пропускать последовательно
все блоки вплоть до первого встреченного нуля.

При зацикливании первый блок должен быть перетерт и флаг должен
измениться на противоположный (с "1" на "0"). После этого будет
"бегущий ноль".

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

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

Сергей.