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

From

Valentin Davydov ()

To

Andrew Evdokimov

Date

2003-01-13T07:34:12Z

Area

RU.ALGORITHMS

From: Valentin Davydov <val@sqdp.trc-net.co.jp>

>   From: Andrew Evdokimov
>          <Andrew.Evdokimov@p8.f2468.n5020.z2.fidonet.org>
>   Date: Sat, 11 Jan 2003 10:59:18 +0300
>
>Вот интересо стало, какие существуют алгоритмы поиска свободных блоков? Т.е.,
>есть некое пространство, разделённое на одинаковые по размеру блоки, часть из
>них занята, свободна. Необходимо найти некоторое количество свободных блоков и
>занять их. Фрагментация возможна, но нежелательна. Иными словами, задача похожа
>на поиск свободного места в некоторых файловых системах - но как оптимально это
>реализовать. Приветствуются также ссылки на теоретические источники.

А чем тебе не нравятся файловые системы, базы данных и прочие malloc()/free() 
операционных систем? Разнообразие их реализаций, кстати, говорит о том, что 
задача весьма нетривиальна и малые на первый взгляд изменения критериев 
оптимальности подчас требуют кардинально различных подходов к решению.

Вал. Дав.
--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)