13 521
правка
Изменения
м
Предлагается зарезервировать часть сегментов (не меньше NВо-1) и следитьпервых, чтобы кроме зарезервированных всегда был как минимум один свободный сегмент. При записиобеспечить возможность очистки сегмента в худшем случае, когда число свободных сегментов будет становится равным N-1, искать и очищать наиболее пустую (то есть, наиболее легко очищаемую) последовательность N сегментов. Резерв нужен для того, чтобы даже в худшем случае дефрагментация удалась. Худший случай — это сборка свободного сегмента из если осталось всего лишь N сегментов, в каждом из которых свободен только всего 1 кластер — чтобы вместить данные из этих N сегментов, очевидно, нужен кластер. Для этого N-1 свободныйсегмент должен быть зарезервирован.
Кроме тогоВо-вторых, понадобится и также нужен фоновый сборщик мусора. Он В-третьих, можно тоже пытаться разделять сектора по частоте их перезаписи. Очень простым способом — с помощью K-средних разбить всю флешку на K «регионов», и стараться писать сектора с соответствующим количеством перезаписи в принципесоответствующий регион. K нужно выбирать меньшим или равным лимиту открытых на запись блоков во флешке. При записи:* Выбираем подходящий регион с помощью K-средних.* Если в регионе не окажется свободных сегментов — попытаться найти свободный сегмент в других регионах, начиная с соседнего в сторону более «горячих» сегментов. Идея в том, что раз максимальное количество перезаписей может делать почти ту же операцию дефрагментации лишь расти, то больше вероятность того, что в будущем записанный сегмент окажется нужно двигать в фоновом режиме«меньшую» сторону. Плюс можно попробовать сделать такСледовательно, чтобы если он старался очищать последовательные областиизначально будет записан в следующий регион, то в будущем он с большей вероятностью окажется в правильном.* Если свободных сегментов нет ни в родном, ни в соседних регионах — значит, кончилось место и надо переходить к экстренной очистке. Экстренную очистку, опять-таки, пытаемся сначала сделать в «родном» сегменте, а потом в соседних.* Сначала пробуем найти наиболее легко очищаемую последовательность N сегментов и переместить из них данные в последовательность N-1 зарезервированных сегментов. После такой очистки мы получим связный регион, в котором N-1 сегмент станет зарезервированным, а в оставшийся 1 можно будет что-нибудь записать. Очищать пробуем сначала в родном регионе, потом — в соседних.* Если таких последовательностей уже не осталось — это значит, что места, во-первых, осталось довольно мало (теоретический максимум худшего случая — 1/N, но в среднем — гораздо меньше), а во-вторых, место сильно фрагментировано. Тогда очистку нужно делать по-другому — берём данные из сегмента, следующего за зарезервированными, и распределяем по отдельным свободным кластерам в разбросанных по всему диску сегментах. Такое разбиение флеш-памяти на регионы, хоть и способствует ускорению записи, всё равно непригодно для MTD (голой NAND памяти), потому что не осуществляет Wear-Leveling, а наоборот — больше изнашивает одни части памяти и меньше — другие.
→Запись
Вторая идея — пытаться при записи разделять «холодные» и «горячие» данные. Идея в том, что теоретически, чем лучше они разделены, тем больше вероятность того, что в сегменте все блоки будут устаревать вместе ⇒ его будет проще очищать.
А что делать с фрагментацией нам?А нам нужно:
== Дополнительная идея: сжатие ==