Промоделируй простейший аллокатор памяти со стратегией first-fit и без
освобождения (только последовательные выделения).
В начале есть один свободный блок [0, size) — вся память свободна. На каждый
запрос размера r нужно выделить первый подходящий кусок свободной памяти,
считая слева. Так как ничего не освобождается, свободная память всегда лежит
сплошным хвостом справа: достаточно держать «курсор» — смещение начала свободной
области.
Функция Allocate(size int, requests []int) []int для каждого запроса возвращает
смещение начала выделенного куска, либо -1, если запрос не помещается в
оставшуюся свободную память. Длина результата равна длине requests.
Правила:
- курсор начинается с
0;
- для запроса
r: если r <= size - cursor, выделяем кусок по смещению
cursor, затем сдвигаем курсор на r;
- иначе записываем
-1, а курсор не двигаем — поэтому следующий, более
мелкий запрос ещё может влезть в оставшийся хвост.
Allocate(10, []int{2, 3, 1})
// → [0, 2, 5] // курсор: 0→2→5→6
Allocate(10, []int{6, 5, 4})
// → [0, -1, 6] // 6 влезает (курсор 0→6); 5 не влезает (5 > 10-6=4);
// // 4 влезает в хвост [6,10)
Краевые случаи:
- пустой
requests → [] (пустой срез);
- запрос ровно по размеру остатка влезает (
r == size - cursor);
- после отказа (
-1) последующие меньшие запросы могут ещё поместиться.
Механику свободного места разбираем в главе
«Свободное место».