Изменения

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

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

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

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