|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Mudry 2:5020/400 16 Jan 2003 16:03:54
To : Andrew Evdokimov
Subject : Поиск свободных блоков и фрагментация
--------------------------------------------------------------------------------
Hello, Andrew!
You wrote to All on Sat, 11 Jan 2003 10:59:18 +0300:
AE> Вот интересо стало, какие существуют алгоритмы поиска свободных
AE> блоков? Т.е., есть некое пространство, разделённое на одинаковые по
AE> размеру блоки, часть из них занята, свободна. Hеобходимо найти
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
