Технология программирования
| Вид материала | Документы |
- Лекция 4 Тема 3 Технология программирования и основные этапы ее развития, 46.22kb.
- Программа как формализованное описание процесса обработки данных. Программное средство., 362.79kb.
- Календарный план учебных занятий по дисциплине «Языки и технология программирования», 43.35kb.
- Программа обучения студентов (Syllabus) по дисциплине тр302- технология программирования, 375.44kb.
- Программа курса "Технология программирования и управление программными проектами", 100.25kb.
- Курсовой проект по курсу «Технология программирования», 147.33kb.
- Рабочая программа дисциплины: б б 7 Конструирование программного обеспечения для направления, 156.05kb.
- В. А. Основы объектного программирования на языке C# оо – технология и обучение программированию, 141.07kb.
- Рабочая учебная программа по дисциплине «Технология программирования» Направление №230100, 109.02kb.
- Технологии программирования, 30.41kb.
Вопрос № 6. Динамически распределяемая память (ДРП). Типы организации данных в ДРП (списки).
В традиционных языках программирования, таких как Си, Фортран, Паскаль, существуют три вида памяти: статическая, стековая и динамическая. Конечно, с физической точки зрения никаких различных видов памяти нет: оперативная память - это массив байтов, каждый байт имеет адрес, начиная с нуля. Когда говорится о видах памяти, имеются в виду способы организации работы с ней, включая выделение и освобождение памяти, а также методы доступа.
^ Статическая память
Статическая память выделяется еще до начала работы программы, на стадии компиляции и сборки. Статические переменные имеют фиксированный адрес, известный до запуска программы и не изменяющийся в процессе ее работы. Статические переменные создаются и инициализируются до входа в функцию main, с которой начинается выполнение программы.
Существует два типа статических переменных:
- глобальные переменные - это переменные, определенные вне функций, в описании которых отсутствует слово static. Обычно описания глобальных переменных, включающие слово extern, выносятся в заголовочные файлы (h-файлы). Слово extern означает, что переменная описывается, но не создается в данной точке программы. Определения глобальных переменных, т.е. описания без слова extern, помещаются в файлы реализации (c-файлы или cpp-файлы).
- статические переменные - это переменные, в описании которых присутствует слово static. Как правило, статические переменные описываются вне функций. Такие статические переменные во всем подобны глобальным, с одним исключением: область видимости статической переменной ограничена одним файлом, внутри которого она определена, - и, более того, ее можно использовать только после ее описания, т.е. ниже по тексту. По этой причине описания статических переменных обычно выносятся в начало файла. В отличие от глобальных переменных, статические переменные никогда не описываются в h-файлах (модификаторы extern и static конфликтуют между собой).
^ Стековая, или локальная, память
Локальные, или стековые, переменные - это переменные, описанные внутри функции. Память для таких переменных выделяется в аппаратном стеке. Память выделяется в момент входа в функцию или блок и освобождается в момент выхода из функции или блока. При этом захват и освобождение памяти происходят практически мгновенно, т.к. компьютер только изменяет регистр, содержащий адрес вершины стека.
^ Динамическая память, или куча
Помимо статической и стековой памяти, существует еще практически неограниченный ресурс памяти, которая называется динамическая, или куча (heap). В этом случае память под величины отводится во время выполнения программы. Программа может захватывать участки динамической памяти нужного размера. После использования ранее захваченный участок динамической памяти следует освободить.
Под динамическую память отводится пространство виртуальной памяти процесса между статической памятью и стеком. Обычно стек располагается в старших адресах виртуальной памяти и растет в сторону уменьшения адресов. Программа и константные данные размещаются в младших адресах, выше располагаются статические переменные. Пространство выше статических переменных и ниже стека занимает динамическая память:
| адрес | содержимое памяти |
| 0 4 8 | код программы и данные, защищенные от изменения |
| ... | статические переменные программы |
| | динамическая память |
| max. адрес (232-4) | стек ↑ |
Структура динамической памяти автоматически поддерживается исполняющей системой языка Си или C++. Динамическая память состоит из захваченных и свободных сегментов, каждому из которых предшествует описатель сегмента. При выполнении запроса на захват памяти исполняющая система производит поиск свободного сегмента достаточного размера и захватывает в нем отрезок требуемой длины. При освобождении сегмента памяти он помечается как свободный, при необходимости несколько подряд идущих свободных сегментов объединяются.
Динамически распределяемые области памяти весьма удобны при создании множества небольших блоков данных. Связанными списками и деревьями проще мани пулировать, используя именно ДРП, а не виртуальную память или файлы, проецируемые в память. Преимущество динамически распределяемой памяти в том, что она позволяет игнорировать гранулярность выделения памяти и размер страниц и сосредотачиваться непосредственно на своей задаче. Недостаток — выделение и освобождение блоков памяти проходит медленнее, чем при использовании других механизмов, и, кроме того, теряется прямой контроль над передачей физической памяти и ее возвратом системе.
ДРП — это регион зарезервированного адресного пространства. Первоначально большей его части физическая память не передается. По мере того, как программа занимает эту область под данные, специальный диспетчер, управляющий ДРП, постранично передаст ей физическую память (из страничного файла). А при освобождении блоков в ДРП диспетчер возвращает системе соответствующие страницы физической памяти.
^ Динамические структуры данных: списки
Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера.
Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.
Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти.
^ Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.
Сами динамические величины не требуют описания в программе, поскольку во время компиляции память под них не выделяется. Во время компиляции память выделяется только под статические величины. Указатели — это статические величины, поэтому они требуют описания.
Следует отчетливо понимать, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: сначала ищется указатель, затем по нему — величина.
Списки
В динамической памяти можно создать структуру данных переменного размера.
Например:
В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) и записываются в компьютерную память для дальнейшей обработки. Заранее неизвестно, сколько будет произведено измерений.
Если для обработки таких данных не использовать внешнюю память (файлы), то разумно расположить их в динамической памяти. Во-первых, динамическая память позволяет хранить больший объем информации, чем статическая. А во-вторых, в динамической памяти эти числа можно организовать в связанный список, который не требует предварительного указания количества чисел, подобно массиву. Связанный список схематически выглядит так:
Здесь Inf — информационная часть звена списка (величина любого простого или структурированного типа, кроме файлового), Next — указатель на следующее звено списка; First — указатель на заглавное звено списка.
Согласно определению, список располагается в динамически распределяемой памяти, в статической памяти хранится лишь указатель на заглавное звено. Структура, в отличие от массива, является действительно динамической: звенья создаются и удаляются по мере необходимости, в процессе выполнения программы.
Для объявления списка сделано исключение: указатель на звено списка объявляется раньше, чем само звено.
Если указатель ссылается только на следующее звено списка (как показано на рисунке и в объявленной выше структуре), то такой список называют однонаправленным, если на следующее и предыдущее звенья — двунаправленным списком. Если указатель в последнем звене ссылается на заглавное звено списка, то такой список называется кольцевым. Кольцевыми могут быть и однонаправленные, и двунаправленные списки.
Типовые операции над списками:
- добавление звена в начало списка;
- удаление звена из начала списка;
- добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан);
- удаление звена из произвольного места списка, отличного от начала (например, после звена, указатель на которое задан);
- проверка, пуст ли список;
- очистка списка;
- печать списка.