ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ

Введение

Целью данной работы является выработка навыков использования динамической памяти, приучение к осознанному выбору подходящей модели памяти при компиляции программы.
Динамическое распределение памяти предоставляет программисту большие возможности при обращении к ресурсам памяти в процессе выполнения программы, и корректная работа приложения в существенной степени зависит от правильного обращения к соответствующим функциям.
Для выполнения заданий по этой теме студенты должны уметь работать в пошаговом отладчике, изображать схематичное расположение памяти при работе с указателями.
Студенты должны научиться исследованию программ, используя режим отладки. Они должны убедиться в пользе отладчика не только при поиске ошибок, но и на стадии разработки программы.
Для обязательного выполнения рекомендуются задания 1, 6, 7, 10. Задание 4 можно использовать в качестве курсовой работы.

1. Модели памяти

Виды моделей

Моделью памяти называется набор опций компилятора, определяющий размер и структуру оперативной памяти, предоставляемой программе при ее выполнении.
В BC++2.0 существуют несколько видов моделей памяти: tiny, small, medium, compact, large, huge. Программа может быть откомпилирована в любой из этих моделей, если установить соответствующий флажок в Opions-Compiler-Code Generation-Model. При этом используются различные наборы встроенных библиотек и создаются различные obj-файлы. Например, для модели large в директории Lib имеются файлы C0l.obj, Cl.lib, Mathl.lib и другие. Возможная ошибка на этапе линковки (“Не могу найти файл Сol.obj”) вызвана неполной версией пакета и неверным выбором модели.
Модели памяти не являются частью языка Си, а зависят от используемой оболочки.
Когда программа загружается в ОЗУ для выполнения, ей отводится определенное место, в котором можно выделить несколько областей: область кода (ОК); область данных, глобальных и статических переменных(ОД); стек; куча (heap или динамическая память).
Таблица 1

вид модели памяти	максимальный размер
	Область кода	область данных	стек	куча	взаимное расположение
tiny	64К	64К	64К	64К	все области в одном сегменте
small	64К	64К	64К	64К	ОД,стек и куча в одном сегменте
medium	1М	64К	64К	64К	различные сегменты
compact	1М	64К	64К	1М	различные сегменты
large	1М	64К	64К	1М	различные сегменты
huge	1М	64К	64К	1М	различные сегменты

Модель Large

Модели памяти устроены по-разному. Рассмотрим расположение областей памяти в модели large.

PSP  код  данные     стек            куча         640K

 

Рис. 1
PSP представляет собой префикс программного сегмента, занимает 256 байт и помещается перед исполняемыми файлами при их загрузке в память. Он содержит переменные, используемые MS-DOS для управления программой, а также место для переноса данных окружения.
Область кода содержит машинные коды функций программы. Функции, присоединенные к exe-файлу на стадии линковки, размещаются вне области кода.
Область данных содержит глобальные и статические переменные, строковые константы.
В стеке размещаются локальные переменные, параметры, передаваемые функциям, и ряд других данных. Как правило, стек растет сверху вниз, занимая пульсирующую непрерывную область. В случае переполнения стека происходит его "налезание" стека на область данных и выдается соответствующее сообщение. Проверка стека увеличивает время работы программы и ее можно отключить в Options-Entry/Exit Code Generation-Stack options-Test stack overflow.
В кучу данные помещаются только по указанию программиста и не имеют имени. К ним можно обратиться только по адресу, расположенному в локальной или глобальной переменной.

Сегментные регистры

Сегмент - это область памяти размером не более 64K, созданная для хранения кода, данных или стека. Сегменты всегда выровнены на границу параграфа (16 байт), поэтому их адрес получается умножением сегментного регистра на 0x10=16.
В некоторых моделях памяти код может занимать больше 64K. Области кода, данных и стек начинаются с параграфов с номерами содержащимися, соответственно, в регистрах CS, DS, SS.
В режиме отладчика можно просматривать содержимое регистров в окне Window-Register. При повторных запусках программы сегментные регистры могут быть различны.
Значения сегментных регистров, кроме того, хранятся в глобальных псевпеременных, имеющих то же название с подчеркиванием: _CS, _DS и т.д. Их можно использовать в программе, например, распечатать, учитывая, что псевпеременные являются шестнадцатиричными беззнаковыми числами printf(”CS =%x”, _CS);

Просмотр переменных

В режиме отладчика можно определить адреса и значения переменных, находящихся в своей области видимости, с помощью Alt-F4. Например.
-        Для переменной i, описанной как int i; i = 5; окно просмотра имеет вид
-         

8FAC:FFF4	5(0x0005)
Int

Здесь указан адрес переменной в формате [сегмент]:[смещение]. Полный адрес переменной равен 8FAC0+FFF4=9FAB4
-        Для переменной ptri, описанной как
int i = 4, *ptri;
ptri = &i;
окно просмотра имеет вид

8FAC:FFF2	п	Ds:FFF4
[0]		4(0x0004)
Int *

Здесь указаны: адрес самой переменной ptri, равный 8FAC:FFF2; значение этой переменной Ds:FFF4; а также содержимое ячейки по адресу Ds:FFF4, т.е. значение i. Для того, чтобы узнать содержимое ячеек, окружающих переменную i, нужно воспользоваться комбинацией клавиш Alt-I, ввести начальный индекс (Starting index) и число ячеек (Count). Если, например, введены числа -5 и 15, то можно в приведенном выше окне можно просмотреть элементы массива ptri[-5], ptri[-4],…,ptri[10].
Объекты, размещенные в куче, не имеют имени. Поэтому просматривать динамические объекты можно только предыдущим способом, т.е. по адресу.

Абсолютные адреса и размеры областей памяти в модели large

Область кода занимает часть ОЗУ, содержащую параграфы с номерами от CS до DS-1. Таким образом, размер области кода равен (DS-CS)*0x10.
Область данных занимает часть ОЗУ, содержащую параграфы с номерами от DS SS-1. Таким образом, размер области данных равен (SS-DS)*0x10.
Стек начинается с параграфа SS, но растет справа налево, от старших адресов к младшим. Новые данные помещаются в стек в вершине стека. Смещение вершины стека относительно SS равно SP. Таким образом, полный адрес вершины равен SS:SP. В начале программы стек пуст, поэтому он занимает ячейки с адресами от SS*0x10 до SS*0x10, а размер стека равен SP.
На кучу остается память с адреса SS*0x10+SP по 0xA0000=640K.
Реальный размер кучи зависит от способа запуска программы. Сама оболочка Borland C++2.0 занимает в ОЗУ порядка 200K, и для программы, выполнямой из оболочки, остается немного места - примерно 300K. Если же программа запускается из командной строки DOS или из Norton Commander, то куча будет значительно больше.
При выполнении программы из оболочки и в отладчике под кучу отводится еще меньше места, поэтому ее размер в этом случае разрешается устанавливать вручную с помощью опции Options-Debugger-Program heap size.
2. Основные функции ДРП

Выделение памяти

void *malloc(size_t size);
Выделяет блок ДП размером size байт. Здесь size_t совпадает с типом unsigned int. Таким образом, блок не превосходит размер в 64K. В случае отсутствия непрерывного блока заказанной длины, возвращается NULL.
Пример 1. Выделение массива для 1000 чисел типа float.
main() {
float *ptrf;
if((ptrf =(float *) malloc(1000 * sizeof(float)) == NULL)
printf("\nОшибка при выделении памяти!");
}

Освобождение памяти

void free(void *block);
Освобождает блок ДП, начинающийся с адреса block. Этот адрес должен находится в заголовке ранее выделенного блока (см. п.3). В противном случае, будет освобожден случайный блок и возникнет логическая ошибка. Динамические переменные не освобождаются автоматически при выходе из области действия и, таким образом, засоряют кучу.

Перевыделение памяти

void *realloc(void *block, size_t size);
Изменяет размер блока, на который указывает block. Новый размер блока будет равен size. Старая информация сохраняется. При нехватке свободных байт блок будет перемещен в новое место с одновременным копированием информации. Функция возвращает адрес нового блока, не изменяя переменную block.
Пример 2. Выделение памяти под двумерный массив
main() {
float **A;
int n=5, n=10;
A = (float **)malloc(m * sizeof(float *));
if(A == NULL)
{
printf("\nОшибка при выделении памяти под массив указателей!");
exit(1);
}
for (int i=0; i< m; i++)
{
A[i] = (float *)malloc(n * sizeof(float));
if(A[i] == NULL)
{
printf("\nОшибка памяти под%d-ую строку!", i);
for(int j=0; j< i; j++)
free(A[j]);
free(A);
exit(2);
}
//…….
for(i=0; i< m; i++)
free(A[i]);
free(A);
}
3. Менеджер ДРП
Управлением ДП занимается специальный фрагмент кода, вызываемый в функциях ДРП. Он называется менеджером ДП. Мы исследуем работу менеджера в модели памяти large. В других моделях менеджер устроен по-другому.
Первоначально менеджер рассматривает кучу как свободную область. При каждом обращении к памяти выделяется непрерывный блок, состоящий из одного или нескольких параграфов. В первом параграфе имеется заголовок блока. При освобождении памяти блок помечается как свободный. Таким образом, в процессе работы программы свободные и занятые блоки начинают чередоваться. В результате увеличивается фрагментация кучи, когда общей свободной памяти много, а непрерывного блока необходимой длины нет.
Выделяемый блок памяти имеет вид

2

2

14

16

…..

16

В заголовке находятся:
¾   длина блока в параграфах (2 байта),
¾   сегментный адрес предыдущего блока (2 байта),
¾   далее идут данные. Адрес начала данных и возвращается функциями ДРП.
Блоки организованы в односвязный список. При запуске программы в начале куче выделяется блок для системных нужд. Первый выделенный программой блок будет ссылаться на имеющийся блок и т.д. При освобождении блока в его заголовке обнуляется ссылка на предыдущий блок. Длина блока не изменяется, а в информационную область заносятся данные, используемые при корректировке кучи.
Таким образом, зная адрес последнего занятого блока, можно определить длину, адрес и статус остальных блоков. Рассмотрим программу
main(){
char *block1=(char *)malloc(100);
char *block2=(char *)malloc(110);
char *block3=(char *)malloc(120);
free(block2);
}
Выполняя ее в отладчике, увидим, что до освобождения второго блока куча будет иметь вид (конкретные адреса будут другими!)

0х0007

0х90EF

…

0x0008

0x910F

….

0x0008

0x9116

Block1

Block2

Block3

Рис. 2
После выполнения оператора free(block2) куча будет иметь вид

0х0007

0х90EF

…

0x0008

0x0000

….

0x0008

0x9116

Block1

Block2

Block3

Рис. 3
Замечание 1. Особенность динамических символьных строк.
Рассмотрим фрагмент кода, создающий динамическую строку.
main()
{
char *str; // ячейка str находится в стеке
str = (char *)malloc(13);
strcpy(str, "Hello,World!");
// строка Hello,World! помещается в кучу
}
Строка "Hello,World!" реально состоит из 13 символов, так как кроме самих символов содержит 0 - признак конца строки. Поэтому, если выделить только 12 элементов
Str = (char *)malloc(12),
то признак конца строки "залезет" на заголовок следующего блока ДП и изменит длину этого блока. Если бы длина строки была меньше 12 байт, то фраза уместилась бы в первом параграфе, и ошибки бы не произошло. Источник хорошо скрытой логической ошибки!
4. Дополнительные фунции ДРП

Определение размера свободной области кучи

unsigned long coreleft(void);
Возвращает размер неиспользованной памяти в байтах, расположенной за последним занятым блоком. "Дырки" в куче не учитываются.

Блочное выделение памяти

void *calloc(size_t NItems, size_t SizeOfItem);
Выделяет и обнуляет память для Nitems фрагментов по SizeOfItem байт каждый. Размер фрагмента не превосходит 64K, но общий объем памяти может превышать 64K. В случае неудачи возвращается NULL.

Проверка целостности кучи

int heapcheck(void);
Просматривает кучу и проверяет для каждого блока указатели, размер и другую критическую информацию. Если все нормально, то возвращаемое значение больше 0. В противном случае, возвращается отрицательное число.

Просмотр блоков кучи

int heapwalk(struct heapinfo *hi);
Просматривает кучу блок за блоком. Предполагается, что сбоев в куче нет, для этого используйте heapcheck. Фнукция получает указатель на структуру heapinfo. При первом вызове, установите hi.ptr в 0. Функция устанавливает этот указатель на адрес очередного блока. Другие поля структуры size, in_use позволяют определить размер блока в байтах и его занятость. Для очередного блока функция вернет _HEAPOK, для последнего блока _HEAPEND.
Пример 3. Занятые и свободные блоки.
#include <stdio.h>
#include <alloc.h>
#define NUM_PTRS 4
#define NUM_BYTES 20
int main(void)
{
struct heapinfo hi;
char *array[ NUM_PTRS ];
for(int i = 0; i < NUM_PTRS; i++)
array[ i ] = (char *)malloc(NUM_BYTES);
for(i = 0; i < NUM_PTRS; i += 2)
free(array[ i ]);
hi.ptr = NULL;
printf(" Размер Статус\n");
printf(" ---- ------\n");
while(heapwalk(&hi) == _HEAPOK)
{
printf("%7u ", hi.size);
printf("%s\n",(hi.in_use?"используется": "свободен"));
}
return 0;
}
В результате будет напечатано

Размер	Статус
528	Используется
32	Свободен
32	Используется
32	Свободен
32	Используется

Инициализация свободных блоков кучи

int heapfillfree(unsigned int fillvalue);
Заполняет байты свободных блоков кучи константным значением fillvalue.

Проверка свободных блоков кучи

int heapcheckfree(unsigned int fillvalue);
Проверяет байты свободных блоков кучи на их равенство константному значению fillvalue.

Функции группы far.

В моделях памяти, где куча не превышает 64K, можно использовать память вне этой области - дальнюю кучу. Для работы с дальней кучей имеются свои версии функций, c префиксом far.
5. Лабораторные задания
Области памяти
Для следующей программы укажите значения сегментных регистров. Укажите абсолютные адреса и размеры в байтах области кода; области данных, глобальных и статических переменных; стека; кучи. Модель памяти large. Определите в отладчике адреса и размещение по областям переменных: main; Privet; Dlit в функции main; i и Dlit в функции Privet; printf.
void Privet(int sound); // прототип функции Privet
main(){
int Dlit = 5;
Privet(Dlit);         //вызов функции Privet
}
void Privet(int Dlit) { // заголовок функции Privet
{
printf("Привет!\n");
printf("С добрым утром!");
for(int i = 0; i<Dlit; i++) //печатает первые Dlit
printf("%c", i); // символов ascii-таблицы
}
Исследование менеджера ДРП
Выделите динамическую память для трех данных типа char. Адреса сохраните в переменных char *x, *y, *z. Определите в отладчике адреса *x, *y, *z. Убедитесь, что для кажго из однобайтовых данных будет отведено в куче 16 байт,т.е. целый параграф.
Односвязный список менеджера
Разместите в куче несколько данных разного типа, найдите их адреса, размер блоков. Убедитесь в наличии односвязного списка.
Новый менеджер
Язык Си не пускает дефрагментации ДП. Напишите свой менеджер, содержащий функции mymalloc, myfree, mydefrag.
Сумма свободных блоков
Определите суммарный объем "дырок" в куче, образовавшихся после освобождения блоков.
Выделение памяти под одномерный массив
Выделите память под 20 переменных типа int. Заполните их случайными целыми числами из интервала от -3 7. Выведите их на экран.
Выделение памяти под двумерный массив
Выделите память под двумерный массив 3х5 типа float. Заполните их случайными вещественными числами из интервала от -3.6 7.4 с шагом 0.1. Выведите их на экран в виде таблицы. Массив представьте в виде строки.
Структура для матрицы переменных размерностей.
Создайте структуру для хранения информации о матрице переменных размерностей. Рассмотрите две возможности
Struct Matr1{ int m, n; int *ptr;};
Struct Matr2{ int m, n; int **ptr;};
Напишите функции
int DinMatr1(Matr1 *matr);
int DinMatr2(Matr2 *matr);
для корректного выделения памяти под массив
Умножение матриц
Напишите функцию умножения матриц переменных размерностей.
Ввод чисел
С клавиатуры вводятся натуральные числа. Признак конца ввода - число 0. Сохраняйте числа в куче. По окончании ввода выдайте числа на экран.
Список строк
Создайте односвязный список для хранения текстовых строк, вводимых с клавиатуры. Выведите их на экран в обратном порядке.
Норма матрицы
Октаэдрической нормой квадратной матрицы А, nxn, называется число ÷÷A÷÷_∞ = max{÷a_1j÷+÷a_2j÷+ …+÷a_nj÷: j=1,…n}. Напишите функцию для вычисления нормы матрицы. Размеры матрицы произвольный.
Наибольшая по размеру квадратная матрица.
Найдите наибольший размер N, для которого в куче можно выделить в памяти место для квадратной матрицы NxN чисел типа float. Получите результат при запуске программы из командной строки DOS и из оболочки BC.
Модификация функции coreleft.
Напишите функцию вычисления общего размера свободной кучи.
Свободна ли куча?
Напишите функцию определяющую, свободна ли куча.
Работа с файлом.
Запишите динамическую матрицу в файл, прочитайте из файла и распечатайте.

 

Библиографический список

1.      Керниган Б, Ритчи Д. Язык программирования Си. М.: Фин. и стат., 1992.
2.      Керниган Б, Ритчи Д. Язык программирования Си. Задачи по курсу Си. М.: Фин.и стат., 1985.
3.      Уинер Р. Язык ТурбоСи. М.:Мир, 1991.
4.      Хинт К. Си без проблем. Руководство пользователя. М.: Бином, 1997.
Трофимов С.П. Программирование в Си. Организация ввод-вывода // Метод. указания, Екатеринбург, Изд-во УГТУ, 1998, 20 с.