Stack Allocator

from 39: Аллокатор (англ. Allocator) или распределитель памяти в программировании — специализированный класс, реализующий и инкапсулирующий малозначимые (с прикладной точки зрения) детали распределения и освобождения ресурсов компьютерной памяти.

Стековый аллокатор - это умная штука, которая позволяет управлять памятью, как стеком.

Предисловие

• Мы уже имели дело с аллокаторами памяти
• Они нужны, чтобы работать со структурами данных динамического размера
• Аллокатор работает с кучей (heap)
• Для аллокатора куча - множество блоков разного размера
• Блок - непрерывный кусок виртуальной памяти, который может быть либо выделенным (allocated), либо свободным (free).

Требования к аллокатору

• Последовательность запросов malloc и free - произвольная
  • Нельзя полагаться на порядок запросов
  • Но мы предполагаем, что free вызывается на участке, который был выделен
• Немедленный ответ на запрос
  • Нельзя буферизировать запросы или переупорядочивать
• Используется только куча
  • Все нескалярные структуры данных, которыми пользуется аллокатор, должны лежать в куче
• Выравнивание блоков
  • Нужно, чтобы в блоке могли размещаться данные любого типа
  • В большинстве систем выравнивается по 8 байт
• Нельзя модифицировать выделенные блоки
  • Можно манипулировать только свободными блоками

Цели