Память. Организация процесса проектирования

1.

Организация процесса проектирования
Программного обеспечения
Лекция: Память
ст. преп. кафедры ВТ
Васильев В. С.
Использованы материалы Ф. Короткого (Яндекс) и А. Аксенова (Авито)

2.

Пример выделения памяти на куче и на стеке
2

3.

Аллокатор — это просто!
OS ==> libc:
- mmap.
libc ==> программа:
- malloc;
- free.
Проблемы:
- нельзя взять еще памяти;
- нельзя освободить память;
- гонки потоков.
Плюсы:
- быстро работает.
3

4.

Чуть более сложный аллокатор
4

5.

Сложно, но...
Проблемы с фрагментацией.
Надо как-то решить проблему гонок.
5
Сколько занимает метаинформация?
Где ее хранить?
+24 байта на аллок.

6.

Чего не хватает?
1) Избежать обход free списка.
2) Не хранить 20+ байт на мелкие аллоки.
3) Не обходить арены без свободных блоков нужного размера.
6

7.

Чего не хватает?
Чтобы выполнить free нужно по адресу на
Как и в предыдущей версии проблема с m
7

8.

Устройство Jemalloc
Одновременно поддерживает 2 алгоритма:
* Small — 16Б, 32Б, 48Б, … 14Кб.
* Large — 16Кб, 20Кб, … , 48Мб, 56Мб, 64Мб
Tcache - Локальный для потока кэш свободных объектов.
Очень быстрый и очень глупый: void* clip[16];
8

9.

Устройство Jemalloc
9

10.

Устройство Jemalloc
Если локальный кэш опустел, его нужно наполнить
Thread выполняет что-то типа
tcache.add(Arena.refill())
10

11.

Устройство Jemalloc
Потоки выделяют память из разных арен.
Глобальная куча разделена на независимые арены. Как?
Как устроена Арена?
11

12.

Устройство Jemalloc
Мы пришли в арену и запросом
› Дай мне 8 объектов размера 16 байт
Мы просим много маленьких объектов
› Важно держать накладные расходы на один объект небольшими
› Важно бороться с фрагментацией
› Не нужно освобождать объекты сразу
Slab – массив объектов одинакового размера + bitmap
12

13.

Устройство Jemalloc
Что делать если slab полностью заполнен?
› Вариант A: Поискать свободный slab
› Вариант Б: Создать новый slab
13

14.

Устройство Jemalloc
Все незаполненные slab-ы хранятся в очереди
› Ключом в очереди является адрес slab-a
› Такой подход всегда выделяет новые объекты
из более старого slab-а
14

15.

Устройство Jemalloc. Осознаем что узнали
- у каждого потока своя Арена, которую делят 2 системы;
- «мелкая» арена поделена на Slab-ы;
- Slab-ы хранятся в очереди с приоритетами;
- в какой-то момент (получения памяти) арена делится на память и очеред
- каждый Slab = массив объектов + bitmap;
- объекты из Slab-а запрашиваются «пачками» и помещаются в кэш (котор
Все это чтобы не хранить метаинформацию для маленьких объектов
15

16.

Устройство Jemalloc
Что если нам нужно 4 байта, но:
1) в Tcache ничего нет;
2) очередь свободных Slab-ов пуста?
slab = new Slab();
› Внутри slab хранились маленькие объекты – но сам slab является б
› Выделение новых slab-ов обслуживается наравне с пользовательск
После создания Slab рубится на объекты, формируется bitmap, напо
16