Евгений Темиргалеев писал(а):
Что Вы скажете про подход, указанный у Кнута в разделе про списки. Выделенный у системы блок памяти превращается в односвязный список L свободных Piece. При выделении блоки удаляются из начала L, при освобождении по ref = 0 блоки добавляются в начало L.
Очень интересный подход. При достаточно больших полезных объёмах дополнительный указатель не сильно обременит.
Я думал сделать так: у системы берётся блок памяти P, скажем, на 100 Piece. Если в процессе работы окажется мало, то берутся дополнительные блоки P. Они связываются в кольцевой односвязный список (т.е. оверхед = 1 указатель на 100 Piece). В каждый момент времени менеджер памяти помнит только один указатель - на тот блок P, в котором был выделен последний Piece. При необходимости найти свободный Piece, идёт с начала этого P и по всему кругу в поиске Piece с ref = 0. Если прошёл весь круг и не нашёл, значит пора новый блок P попросить у ОС.
Время поиска будет явно не линейное, особенно в худшем случае, но не должно быть таким уж и большим: инкремент адреса, проверка значения по адресу на равенство нулю, проверка выхода за пределы блока P; при переходе к очередному блоку - проверка, не с этого ли блока начинали поиск (если да - выделяем доп. блок).
В любом случае меня ещё вот какой вопрос интересует: как предусмотреть возврат блока P обратно ОС. Скажем, после завершения некой пиковой нагрузки хочется, чтобы объём выделенной памяти вернулся к близкому к минимуму значению. Или это не актуально в современных ОС? Алгоритм Кнута никак не способствует высвобождению или дефрагментации памяти, а мой подход заставляет хотя бы по максимуму оставаться в пределах одного блока P.
И ещё, наверное, имеет смысл блока P согласовать с каким-то системным размером? Где почитать, какие блоки рекомендуется брать у ОС?