Изменения

Цена пропуска сектора ''внутри'' одного Erase Unit’а примерно равна цене его записи. Так как если бы мы его записали, то с одного стирания (занимающего большую часть времени) мы бы «сняли» на единицу больше записанных секторов. ''Целые'' Erase Unit’ы при этом можно пропускать вполне свободно (какой из них «открыть» следующим — флешке пофигу). То есть, «цена» записи в частично занятый сегмент такая же, как и на «голом» MTD — там занятые секторы нужно сначала куда-то переместить, и это занимает такое же время.

Проблемаочистки, на самом деле, общая для всех лог-структурированных устройств («cleaning overhead»). Выхода два:

А Голый MTD с точки зрения данного алгоритма отличается от флешки тем, что делать перед началом записи занятые блоки нужно куда-то переместить, а сегмент — стереть. Но зато при перемещении мы можем без лишних затрат бороться с фрагментацией, группируя блоки по возрасту (так как операция «открытия» блока не занимает времени и писать можно в любой стёртый сектор). А если, например, флешку записать целиком, а потом много раз перезаписывать каждый второй сектор — мы получим 50 % свободного места в каждом сегменте, и ничего не сможем с этим поделать без лишних затрат времени ''перед началом записи''. Конкретно, если перемещать сектора — в самом худшем случае мы можем затратить вплоть до (N-1) стираний, где N — число секторов в сегменте. Чтобы подобным образом бороться с фрагментацией нам?на флешке — перемещать блоки из частично занятых секторов нужно перед окончанием записи в сегмент — в тот момент, когда в записываемом сегменте остаётся нужный объём пространства. Но в худшем случае это ограничивает перемещение числом свободных секторов в записываемом сегменте.

А вот что — Итого, что же делать с фрагментацией нам? Ответ — выбирать сегмент на основе оценки стоимости и возраста данных. Идея простая — стоимость очистки блока, в который мы будем писать, в точности равна числу занятых в нём секторов, следовально, для записи надо выбирать максимально свободный сегмент (в идеале — совсем свободный). Однако:

* Вместо того, чтобы писать блок в произвольный выбранный сегмент, лучше группировать его вместе с блоками, близкими к нему по возрасту. Для этого вместо одного «активного сегмента» таковых помнить нужно несколько (<= лимиту числа открытых на запись блоков на флешке минус один, необходимый под индекс). В качестве каждого активного сегмента нужно выбирать либо любой пустой, либо ближайший по среднему возрасту сохранённых в нём логических блоков к центру группы, построенному с помощью K-средних.* Вместо того, чтобы записывать сегмент целиком, может оказаться лучше оставить в нём немного места и переместить туда близкие по возрасту данные, извлечённые из частично свободного сегмента — то есть, сделать дефрагментацию в процессе записи.

Таким образом, при выборе кластера для записи блока мы имеем два критерия качества: (основной) число свободных блоков и (дополнительный) близость среднего возраста к центру выбранной для записи блока группы K-средних. Остаётся вопрос — как Комбинировать их комбинироватьнужно примерно так — если считать, что разница в возрасте блоков в сегменте потенциально может привести к тому, что к моменту, когда мы будем его перезаписывать, более старые блоки (ранее перезаписанные меньшее число раз), вероятно, ещё не будут перезаписаны, а более новые уже будут. А голый MTD с точки зрения данного алгоритма отличается от флешки только темТо есть можно считать, что перед началом «цена» записи занятые блоки всё-таки нужно стереть и куда-то переместитьв частично занятый сегмент больше на число блоков, относящихся к более старой возрастной группе, чем записываемый. Можно этот показатель ещё домножить на некий варьируемый коэффициент.