Динамическое распределение памяти

Тип работы:
Лабораторная работа
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

Введение

Целью данной работы является выработка навыков использования динамической памяти, приучение к осознанному выбору подходящей модели памяти при компиляции программы.

Динамическое распределение памяти предоставляет программисту большие возможности при обращении к ресурсам памяти в процессе выполнения программы, и корректная работа приложения в существенной степени зависит от правильного обращения к соответствующим функциям.

Для выполнения заданий по этой теме студенты должны уметь работать в пошаговом отладчике, изображать схематичное расположение памяти при работе с указателями.

Студенты должны научиться исследованию программ, используя режим отладки. Они должны убедиться в пользе отладчика не только при поиске ошибок, но и на стадии разработки программы.

Для обязательного выполнения рекомендуются задания 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.

Рис. 1

PSP представляет собой префикс программного сегмента, занимает 256 байт и помещается перед исполняемыми файлами при их загрузке в память. Он содержит переменные, используемые MS-DOS для управления программой, а также место для переноса данных окружения.

Область кода содержит машинные коды функций программы. Функции, присоединенные к exe-файлу на стадии линковки, размещаются вне области кода.

Область данных содержит глобальные и статические переменные, строковые константы.

В стеке размещаются локальные переменные, параметры, передаваемые функциям, и ряд других данных. Как правило, стек растет сверху вниз, занимая пульсирующую непрерывную область. В случае переполнения стека происходит его «налезание» стека на область данных и выдается соответствующее сообщение. Проверка стека увеличивает время работы программы и ее можно отключить в Options-Entry/Exit Code Generation-Stack options-Test stack overflow.

В кучу данные помещаются только по указанию программиста и не имеют имени. К ним можно обратиться только по адресу, расположенному в локальной или глобальной переменной.

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

Сегмент — это область памяти размером не более 64K, созданная для хранения кода, данных или стека. Сегменты всегда выровнены на границу параграфа (16 байт), поэтому их адрес получается умножением сегментного регистра на 0×10=16.

В некоторых моделях памяти код может занимать больше 64K. Области кода, данных и стек начинаются с параграфов с номерами содержащимися, соответственно, в регистрах CS, DS, SS.

В режиме отладчика можно просматривать содержимое регистров в окне Window-Register. При повторных запусках программы сегментные регистры могут быть различны.

Значения сегментных регистров, кроме того, хранятся в глобальных псевпеременных, имеющих то же название с подчеркиванием: _CS, _DS и т. д. Их можно использовать в программе, например, распечатать, учитывая, что псевпеременные являются шестнадцатиричными беззнаковыми числами printf («CS =%x», _CS);

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

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

— Для переменной i, описанной как int i; i = 5; окно просмотра имеет вид

-

8FAC: FFF4

5(0×0005)

Int

Здесь указан адрес переменной в формате [сегмент]: [смещение]. Полный адрес переменной равен 8FAC0+FFF4=9FAB4

— Для переменной ptri, описанной как

int i = 4, *ptri;

ptri = & i;

окно просмотра имеет вид

8FAC: FFF2

п

Ds: FFF4

[0]

4(0×0004)

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)*0×10.

Область данных занимает часть ОЗУ, содержащую параграфы с номерами от DS SS-1. Таким образом, размер области данных равен (SS-DS)*0×10.

Стек начинается с параграфа SS, но растет справа налево, от старших адресов к младшим. Новые данные помещаются в стек в вершине стека. Смещение вершины стека относительно SS равно SP. Таким образом, полный адрес вершины равен SS: SP. В начале программы стек пуст, поэтому он занимает ячейки с адресами от SS*0×10 до SS*0×10, а размер стека равен SP.

На кучу остается память с адреса SS*0×10+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 («%sn»,(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{a1j+a2j+ …+anj: j=1,…n}. Напишите функцию для вычисления нормы матрицы. Размеры матрицы произвольный.

Наибольшая по размеру квадратная матрица.

Найдите наибольший размер N, для которого в куче можно выделить в памяти место для квадратной матрицы NxN чисел типа float. Получите результат при запуске программы из командной строки DOS и из оболочки BC.

Модификация функции coreleft.

Напишите функцию вычисления общего размера свободной кучи.

Свободна ли куча?

Напишите функцию определяющую, свободна ли куча.

Работа с файлом.

Запишите динамическую матрицу в файл, прочитайте из файла и распечатайте.

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

1. Керниган Б, Ритчи Д. Язык программирования Си. М.: Фин. и стат., 1992.

2. Керниган Б, Ритчи Д. Язык программирования Си. Задачи по курсу Си. М.: Фин. и стат., 1985.

3. Уинер Р. Язык ТурбоСи. М. :Мир, 1991.

4. Хинт К. Си без проблем. Руководство пользователя. М.: Бином, 1997.

Трофимов С. П. Программирование в Си. Организация ввод-вывода // Метод. указания, Екатеринбург, Изд-во УГТУ, 1998, 20 с.

ПоказатьСвернуть
Заполнить форму текущей работой