Алгоритм двойников

Алгоритм двойников (англ. Buddy memory allocation) — алгоритм динамического распределения памяти, при котором память поделена на блоки размером $2^n$$2^{n}$ и при запросе выделяется блок, размер которого максимально приближен к требуемой памяти. Cистема двойников впервые была предложена Гарри Марковицем в 1963 году.

Алгоритм Править

• Память выделяется блоками размером $2^n$$2^{n}$ 
• Когда требуется выделить память, ищем блок минимального подходящего размера $2^x$$2^{x}$ . Если блок найден, то используем этот блок для размещения памяти. Если блок подходящего размера не найден, то находим ближайший блок большего размера и делим его до тех пор, пока не получим блок нужного размера.
• При освобождении памяти проверяем, свободен ли соседний блок (двойник). Если свободен, то сливаем 2 блока в блок большего размера и повторяем это до тех пор, пока у получившегося блока есть свободные двойники.

См. также Править

• Менеджер памяти
• Динамическое распределение памяти