201 lines
15 KiB
Org Mode
201 lines
15 KiB
Org Mode
#+LANG: ru
|
||
#+TITLE: Семинар 6: Аллокация памяти, арихитектура
|
||
|
||
|
||
* Что такое куча
|
||
|
||
В рамках этого семинара мы познакомимся с тем, как может быть устроена куча.
|
||
|
||
С данными связана такая характеристика как /время жизни/.
|
||
Это тот промежуток выполнения программы, когда обращаться к этим данным корректно и не ведёт к неопределённому поведению.
|
||
|
||
Данные в C могут быть выделены следующими способами:
|
||
|
||
- Автоматически: локальные переменные функций создаются в момент их запуска и живут до их завершения.
|
||
Правильно сказать: гарантированное время жизни переменных от запуска функции до её завершения.
|
||
|
||
Зная, что компиляторы оптимизируют локальные переменные, мы больше не будем говорить, что они выделяются в стеке.
|
||
|
||
- Глобальные переменные и локальные переменные функций, если локальные переменные помечены =static=.
|
||
|
||
И те, и другие создаются в глобальной области данных.
|
||
|
||
Других гарантированно возможных способов выделить память в "голом" C нет.
|
||
|
||
|
||
Чтобы выделить память в стеке или в глобальной области данных необходимо знать, сколько именно памяти понадобится, уже в момент компиляции.
|
||
Однако иногда мы не знаем этого заранее; например, когда принимаем по сети размер строки и саму строку; её нужно где-то выделить, а сколько под это выделять байт --- неясно.
|
||
|
||
В таком случае приходится использовать =аллокаторы= --- специальные программы, которые умеют резервировать области памяти и управляют тем, где будут находиться блоки памяти, которые программист запрашивает.
|
||
|
||
Функции =malloc=, =calloc=, =realloc=, =free= --- это интерфейс к аллокатору из стандартной библиотеки C.
|
||
С помощью вызова =malloc= можно выделить память, время жизни которой будет неопределённо долгим. Она может существовать до завершения работы программы, как глобальные переменные, или быть возвращена для переиспользования с помощью функции =free=.
|
||
|
||
|
||
Некоторые советы по работе с памятью:
|
||
|
||
- Если вам нужно выделить память, подумайте, нельзя ли её выделить в стеке. Это всегда проще, чем в куче.
|
||
- Не стесняйтесь передавать не очень большие структуры по значению.
|
||
|
||
|
||
* Аллокатор блоков
|
||
|
||
Самый простой аллокатор возвращает блоки фиксированного размера.
|
||
Их можно заполнять не полностью, остаток будет теряться.
|
||
Помимо блоков нужно хранить карту их занятости; здесь она хранится в виде массива =bool='ов, но для компактности можно было бы упаковывать булевы значения по восемь в каждый байт.
|
||
|
||
#+begin_src c
|
||
|
||
#define HEAP_BLOCKS 80
|
||
#define BLOCK_CAPACITY 1024
|
||
|
||
struct heap {
|
||
struct block {
|
||
char contents[BLOCK_CAPACITY];
|
||
} blocks[HEAP_BLOCKS];
|
||
bool is_occupied[HEAP_BLOCKS];
|
||
} global_heap = {0};
|
||
#+end_src
|
||
|
||
|
||
*Задание 1* Изучите файл [[./heap-0.c][heap-0.c]] и реализуйте в нём недостающие функции для резервирования блока и для возвращения блока в пул доступных. Почему =block_id= содержит ссылку на =struct heap=?
|
||
|
||
** Аллокатор множества блоков
|
||
|
||
|
||
В предыдущем аллокаторе есть несколько существенных недостатков:
|
||
|
||
- блоки и заголовки перемежаются, и размер блоков фиксирован, поэтому нельзя занять несколько блоков подряд.
|
||
- размер блока фиксирован, и потому мы можем нести накланые расходы по памяти.
|
||
|
||
|
||
*Задание 2* Модифицируйте аллокатор так, чтобы он умел выделять несколько блоков подряд.
|
||
См. файл [[./heap-1.c][heap-1.c]]. У блоков теперь будет статус с большей гранулярностью, нежели "занят --- не занят".
|
||
Придумайте тесты для вашего кода для проверки всех особых случаев.
|
||
|
||
#+begin_src c
|
||
enum block_status { BLK_FREE = 0, BLK_ONE, BLK_FIRST, BLK_CONT, BLK_LAST };
|
||
#+end_src
|
||
|
||
Блоки будут связываться в одну из следующих конфигураций:
|
||
|
||
#+begin_src c
|
||
BLK_FREE // свободный блок
|
||
BLK_ONE // единичный занятый блок.
|
||
// после него или свободный или занятый другими данными.
|
||
|
||
BLK_FIRST, BLK_CONT, BLK_CONT, BLK_LAST
|
||
// последовательность блоков с началом, серединкой и концом.
|
||
|
||
BLK_FIRST, BLK_LAST // то же, но без серединки.
|
||
|
||
#+end_src
|
||
|
||
Выделение памяти должно привести к выделению адекватного количества блоков; освобождение памяти должно привести к освобождению блоков начиная с указанного, если этот блок -- начало.
|
||
|
||
|
||
** Чего не хватает для эффективности?
|
||
|
||
Чтобы аллокатор стал более эффективным, можно отказаться от фиксированного размера блока, снабдив каждый из них заголовком и организовав в связный список.
|
||
Затем из единой непрерывной кучи можно сделать несколько фрагментов и добавить довыделение памяти (а именно страниц от операционной системы) в случае, когда куча закончилась.
|
||
Это и будет темой четвертой лабораторной работы.
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
* Задание 3
|
||
|
||
В качестве последнего задания на 2 балла вы можете выбрать одно из двух заданий.
|
||
|
||
** Первый вариант
|
||
|
||
Первый вариант задания - это развитие принтера, который вы увидели на прошлом семинаре.
|
||
Добавьте туда:
|
||
|
||
- вычислитель, который умеет вычислять формулы. Сделайте его расширяемым, так же, как сделан принтер. Подсказка: в отличие от принтера, который не имеет состояния, для вычисления потребуется накапливать состояние, поэтому функции будут иметь больше аргументов, нежели принтеры для узлов.
|
||
- парсер, который сможет распознавать верные формулы из сложения, умножения, деления и вычитания. Не забудьте про скобки!
|
||
- принтер, который будет выводить выражение используя постфиксную запись (обратная польская запись, без использования скобок).
|
||
|
||
В качестве стартовой точки для выполнения этого задания можете использовать расширенный вариант принтера ([[./ast.h][ast.h]], [[./ast.c][ast.c]], [[./main.c][main.c]], [[./makefile][makefile]]),
|
||
в который уже включен базовый токенайзер ([[./tokenizer.h][tokenizer.h]], [[./tokenizer.c][tokenizer.c]]), а также реализация стека и очереди для абстракнтых типов ([[./ring.h][ring.h]]).
|
||
|
||
|
||
** Второй вариант
|
||
|
||
Второй вариант задания - это реализация несложной структуры данных как абстрагированного модуля с непрозрачным типом. Ему посвящена эта заметка.
|
||
|
||
*Изначальный код*
|
||
|
||
У вас есть код внутри одной функции =main=, который реализует расширяемый массив (вектор).
|
||
Изучите его.
|
||
|
||
#+begin_src c
|
||
/* bad.c */
|
||
|
||
#include <inttypes.h>
|
||
#include <malloc.h>
|
||
#include <stdio.h>
|
||
|
||
int main() {
|
||
int64_t *array = malloc(sizeof(int64_t) * 5);
|
||
// вместимость -- сколько памяти выделено
|
||
size_t capacity = 5;
|
||
// количество -- сколько памяти по факту используется из выделенной.
|
||
size_t count = 0;
|
||
// заполните массив квадратами чисел от 0 до 100
|
||
// если не хватает места, расширяем в два раза
|
||
for (size_t i = 0; i <= 100; i++) {
|
||
if (count == capacity) {
|
||
array = realloc(array, sizeof(int64_t) * capacity * 2);
|
||
capacity = capacity * 2;
|
||
}
|
||
array[count++] = i * i;
|
||
}
|
||
|
||
for (size_t i = 0; i < 100; i++) {
|
||
printf("%" PRId64 " ", array[i]);
|
||
}
|
||
return 0;
|
||
}
|
||
#+end_src
|
||
|
||
Расширяемый массив в отличие от обычного имеет нефиксированный размер, в конец такого массива можно добавлять элементы.
|
||
Как это работает:
|
||
- Мы выделяем память с запасом.
|
||
- Мы храним два дополнительных числа: количество выделенных слотов под элементы и количество заполненных слотов в массиве.
|
||
- Пока у нас хватает выделенных слотов, мы просто дописываем элементы в массив, увеличивая количество занятых слотов.
|
||
- Если слотов перестало хватать, то увеличиваем количество слотов в 2 раза (или линейно на некоторый фиксированный размер).
|
||
Для этого используем =realloc= чтобы скопировать выделенную память в расширенный участок.
|
||
|
||
*Вопрос* Прочитайте раздел =man malloc= про функцию =realloc=.
|
||
|
||
*Задание (второй вариант)*
|
||
|
||
|
||
Ваша задача --- выделить из этого кода как минимум модуль с реализацией вектора, снабжённый заголовочным файлом.
|
||
|
||
- Вектор должен быть реализован как [[https://stepik.org/lesson/408352/step/6][непрозрачная структура данных]].
|
||
- Доступ к его элементам должен быть контролируем и осуществляться через getter и setter.
|
||
- Постарайтесь максимально переиспользовать код и ничего не дублировать.
|
||
- Вывод вектора реализуйте как отдельную функцию, которая принимает =FILE*=, в который нужно вывести его содержимое.
|
||
Эту функцию можно также разбить на функцию =foreach= и принтер одного элемента.
|
||
- Стремитесь сделать настолько маленькие функции, насколько возможно.
|
||
|
||
Ваша реализацяия как минимум должна позволять:
|
||
- Получить доступ к любому элементу.
|
||
- Получить информацию о текущей длинне массива и количестве выделенной памяти.
|
||
- Добавить элемент в конец массива.
|
||
- Добавить другой массив в конец массива (скопировать данные).
|
||
- Изменить размер массива на заданный (при необхоимости выделить память).
|
||
- Изменить размер массива на меньший с освобождением неиспользуемой памяти.
|
||
- Освободить память.
|
||
- Вывести массив в указанный поток вывода.
|
||
|
||
В результате должна получиться программа из нескольких файлов, которая делает то же самое, но в которой =main= содержит только заполнение вектора числами и вызов функции, печатающей его в =stdout=.
|
||
|
||
Прочитайте заметку [[[https://gitlab.se.ifmo.ru/c-language/main/-/wikis/%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%B0-%D1%81%D1%82%D0%B8%D0%BB%D1%8F-%D0%BD%D0%B0%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D1%8F-%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC-%D0%BD%D0%B0-C][Правила хорошего стиля]]] --- ваш код должен им соответствовать.
|
||
|