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

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

/>Введение

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

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

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

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

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

Структура для матрицы переменных размерностей.

Создайте структуру для хранения информации о матрице переменныхразмерностей. Рассмотрите две возможности

StructMatr1{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 с.