Поиск свободных блоков и фрагментация

From

Sergey Mudry ()

To

Andrew Evdokimov

Date

2003-01-16T15:03:54Z

Area

RU.ALGORITHMS

From: "Sergey Mudry" <upx@nc.ru>

Hello, Andrew!
You wrote to All on Sat, 11 Jan 2003 10:59:18 +0300:

 AE> Вот интересо стало, какие существуют алгоритмы поиска свободных
 AE> блоков? Т.е., есть некое пространство, разделённое на одинаковые по
 AE> размеру блоки, часть из них занята, свободна. Необходимо найти
 AE> некоторое количество свободных блоков и занять их. Фрагментация
 AE> возможна, но нежелательна. Иными словами, задача похожа на поиск
 AE> свободного места в некоторых файловых системах - но как оптимально
 AE> это реализовать. Приветствуются также ссылки на теоретические
 AE> источники.
А можно ли что-нибудь хранить в свободных блоках?
Если можно, то логично создать из них связный список; т.е, внутри
каждого свободного блока
держать указатель на следующий свободный. Где-то также хранить указатель
на первый свободный. Тогда весь поиск и захват сводится к взятию и
модификации соответствующего количества указателей. Если к тому же этот
список поддерживать упорядоченным по возрастанию адресов, то и
фрагментация сводится к минимуму без больших затрат.

With best regards, Serg, aka upx@nc.ru, upx@ukr.net


--- ifmail v.2.15dev5
 * Origin: Donbass Internet Center DIPT (2:5020/400)