Динамическое распределение памяти (стр. 2 из 2)
¾ длина блока в параграфах (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. Дополнительные фунции ДРП
Определение размера свободной области кучи
unsignedlongcoreleft(void);
Возвращает размер неиспользованной памяти в байтах, расположенной за последним занятым блоком. "Дырки" в куче не учитываются.
Блочное выделение памяти
void *calloc(size_tNItems, size_tSizeOfItem);
Выделяет и обнуляет память для 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.
Проверка свободных блоков кучи
intheapcheckfree(unsignedintfillvalue);
Проверяет байты свободных блоков кучи на их равенство константному значению 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. Выведите их на экран в виде таблицы. Массив представьте в виде строки.
Структура для матрицы переменных размерностей.
Создайте структуру для хранения информации о матрице переменных размерностей. Рассмотрите две возможности
StructMatr1{ intm, n; int *ptr;};
Struct Matr2{ int m, n; int **ptr;};
Напишитефункции
int DinMatr1(Matr1 *matr);
intDinMatr2(Matr2 *matr);
для корректного выделения памяти под массив
Умножение матриц
Напишите функцию умножения матриц переменных размерностей.
Ввод чисел
С клавиатуры вводятся натуральные числа. Признак конца ввода - число 0. Сохраняйте числа в куче. По окончании ввода выдайте числа на экран.
Список строк
Создайте односвязный список для хранения текстовых строк, вводимых с клавиатуры. Выведите их на экран в обратном порядке.
Норма матрицы
Октаэдрической нормой квадратной матрицы А, nxn, называется число ÷÷A÷÷∞ = max{÷a1j÷+÷a2j÷+ …+÷anj÷: j=1,…n}. Напишитефункцию для вычисления нормы матрицы.Размеры матрицы произвольный.
Наибольшая по размеру квадратная матрица.
Найдите наибольший размер N, для которого в куче можно выделить в памяти место для квадратной матрицы NxN чисел типа float. Получите результат при запуске программы из командной строки DOS и из оболочки BC.
Модификация функции coreleft.
Напишите функцию вычисления общего размера свободной кучи.
Свободна ли куча?
Напишите функцию определяющую, свободна ли куча.
Работа с файлом.
Запишите динамическую матрицу в файл, прочитайте из файла и распечатайте.
Библиографический список
1. Керниган Б, Ритчи Д. Язык программирования Си. М.: Фин. и стат., 1992.
2. Керниган Б, Ритчи Д. Язык программирования Си. Задачи по курсу Си. М.: Фин.и стат., 1985.
3. Уинер Р. Язык ТурбоСи. М.:Мир, 1991.
4. Хинт К. Си без проблем. Руководство пользователя. М.: Бином, 1997.
Трофимов С.П. Программирование в Си. Организация ввод-вывода // Метод. указания, Екатеринбург, Изд-во УГТУ, 1998, 20 с.