Файл: Классификация языков программирования. Критерии выбора среды и языка разработки программ. ( Процедурные языки программирования ).pdf

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

Операция peek возвращает элемент, который в настоящее время является головным. Никаких модификаций стека не происходит.

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

Рисунок 7. Операции со стеком на С.

Стек в своем программном виде применяется при обходе структур данных: деревьев, графов. Аппаратный вид стека применяется при использовании рекурсивных функций. Кроме того, стек также используется при создании стековой машины, которая производит вычисления арифметических выражений в обратной польской записи.

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

Арифметические сопроцессоры, программируемые микрокалькуляторы и язык Forth используют стековую модель вычислений.

Идея стека используется в стековой машине среди стековых языков программирования.

Куча (англ. heap) в информатике и программировании — название структуры данных, с помощью которой реализована динамически распределяемая память приложения[10].

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

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

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

Функция, выполняющая получение указателя на занятую область памяти в куче, выполняет следующие действия:

• просмотр списка областей памяти, принадлежащих куче, поиск свободной (занятой) области необходимого размера;
• может запросить расширение памяти у операционной системы в случае нехватки памяти;
• добавление области, которая была найдена, в список занятых или свободных областей;
• возвращает указатель на начало области;
• сообщает об ошибке в случае невозможности выделения необходимой памяти.

Функция, освобождающая память кучи, выполняет следующие процедуры:

• просмотр списка областей памяти, принадлежащих куче, поиск свободной (занятой) области необходимого размера;
• удаление найденной области из списка занятых областей;
• добавление очищенной области в список свободных.

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

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

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

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

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

Каждый элемент списка может хранить адрес области памяти, её размер, информацию о следующей (для поиска в прямом направлении) и/или предыдущей (для поиска в обратном направлении) области.

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

Рассмотрим пример реализации очереди с помощью одномерного массива и двух переменных. Структурная схема изображена на рисунке 8.

Рисунок 8. Реализация очереди при помощи массива и двух переменных.

Переменные используются для определения начала и конца очереди. Назовем их start и end соответственно. Start определяет начало очереди, а end – элемент, который будет заполнен когда в очередь войдет новый элемент. В процессе добавления элемента в очередь, в q[end] помещается новый элемент, а значение end уменьшается на 1. В том случае, если значение end становится равным 0, то массив обходится циклически и значение переменной становится равным n.

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

Пример реализации очереди в виде класса приведен на рисунке 9.

Рисунок 9. Класс «Очередь» на языке C#.

Вывод по разделу: переменной в языке программирования должен соответствовать какой-либо тип значения, хранящийся по адресу в памяти, на который она указывает. В зависимости от привязки переменной к типу, языки программирования разделяют на статически типизированные и динамически типизированные. Для первых характерна жёсткая привязка переменной к типу значения, которое она хранит, вторые же предоставляют возможность переменным хранить данные любого типа. Кроме того, существуют важные структуры данных, которые принято считать динамическими. Это стек, очередь и куча. Данные структуры находят широчайшее применение в том или ином виде при построении сложных программных конструкций, связанных с последовательной обработкой задач.

11. Области видимости переменных

Под областью видимости в программировании понимается часть кода, в рамках которой переменная остается связанной с этой частью программы, т.е. позволяет обратиться к себе, совершить какие-либо операции с её использованием. Грубо говоря, переменная «видна» в какой-либо части кода – это и есть простое определение области видимости. По области видимости переменные разделяют на локальные и глобальные[11].

Локальной называют переменную, объявленную внутри некоторого блока кода. Её область видимости ограничена данным блоком кода. Локальные переменные хранятся в стеке вызовов, таким образом, при рекурсивном вызове функции, её локальные переменные каждый раз создаются заново и получают новый сегмент памяти.

Благодаря использованию локальных переменных появляется возможность реализации рекурсивных процедур и функций. Применение локальных переменных также обусловлено принципом «разделяй и властвуй», что подразумевает использование своих переменных внутри сложных функций во избежание проблем, которые могут порождать глобальные переменные.

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

В качестве примера для большего понимания локальных переменных представлен код на языке C (рисунок 10).

Рисунок 10. Локальные переменные в C. Пример.

Результатом выполнения программы выше будет последовательность ‘012’. Этот пример демонстрирует то, что глобальная переменная ‘a’ скрывается такой же переменной в локальных областях видимости.

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

Глобальные переменные имеют ряд недостатков при использовании. В первую очередь, глобальная переменная при определенных условиях может быть изменена в любой функции или методе. Это может повлиять на работу всей программы, поэтому глобальные переменные, используемые для создания взаимосвязей и зависимостей, вносят дополнительную сложность в код. С другой стороны, глобальная переменная может найти своё применение во избежание использования множества локальных переменных внутри отдельных функций, по своей сути отождествленных. В то же время, глобальные переменные делают процесс внедрения модулей более сложным, так как ранее спроектированный и используемый код может иметь такие же названия переменных, которые имеются во встраиваемом модуле.

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

На рисунке 11 представлен фрагмент кода на C, который можно привести в качестве примера использования глобальных переменных.

Рисунок 11. Глобальные переменные. Пример на С.

Вывод по разделу: классификация переменных на глобальные и локальные связана с необходимостью разделять их области видимости и ограничивать область существования локальных переменных. Локальные переменные используются в ограниченных секциях кода и не существуют за их пределами, глобальные – применяются для обмена данными между процедурами и функциями. Применение глобальных переменных может сопровождаться появлением блокировок в многопоточном коде.

12. Критерии выбора языка и среды разработки программного обеспечения

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

Рисунок 12 – распределение языков программирования по решаемым задачам.

На начальном этапе создания программы так или иначе становится вопрос выбора языка программирования. Кто-то выбирает язык только из личных предпочтений, кто-то только потому, что знает только этот язык, кто-то об этом даже не задумывается. Однако, данный этап разработки является очень важным, так как от него в будущем могут возникнуть проблемы, а могут и не возникнуть — смотря как подойти к вопросу[12]. Определим основные критерии:

• Скорость работы конечного продукта.

Требовательным к скорости выполнения могут быть программы с большим объемом математических вычислений, например моделирование физических систем, расчеты большого объема экономических данных, выведение трехмерной графики и прочее. Для данных целей хорошо подойдут компилируемые языки: ассемблер, С/С++, фортран и т.д. Почему именно такие? После сборки программа не требует (грубо говоря) ничего лишнего и содержит в себе машинные команды, которые выполняются без лишних задержек. Схема работы таких программ такая: 1) программа исполняется сразу, так сказать она самодостаточна и не требует дополнительных библиотек; 2) программа кроме своего кода содержит вызовы библиотек с машинным кодом (как системных, так и входящих в проект), поэтому, кроме исполнения собственно своих команд, программа вызывает функции из библиотек; 3) в дополнение случаям 1 и 2, программа может работать через прослойку драйверов, которые написаны на языках низкого уровня и работают по умолчанию быстро. Как видно, максимум в схеме возможны 4 блока: программа -> библиотеки -> драйвера -> железо.