Какие ошибки могут возникнуть при использовании стека

Стек (или магазин) — структура данных в программировании, работающая по принципу магазина с патронами: последний помещеннный в него объект, обрабатывается первым.

Приработе со стекам часто приходится сталкиваться с двумя типичными ошибками: переполненем стека и опустошением стека.

Переполнение стека (stack overflow) — одна из типичных ошибок при работе со стеком, состоящая в попытке добавить в стек элемент, когда память, отведенная для хранения стека полностью занята.

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

Если стек моделируется на связанном списке, то переполнение стека обычно возникает только при исчерпании доступной для программы оперативной памяти. В этом случае программа завершается с диагностикой «Недостаточно памяти».

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

Опустошение стека (stack underflow) — другая типичная ошибка при работе со стеком, состоящая в попытке извлечь значение пустого стека.

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

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

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

Чтобы избегать ошибок при работе со стеком нужно следовать двум правилам.

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

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

Описанные правила безопасности приводят к тому, что программный код оказывается перегружен проверками. По этой причине более эффективным методом является уведомление об ошибках в работе со стеком при помощи механизма исключений или прерываний (например, конструкция  try … throw в языке С++).

Дополнительно в базе данных Генона: 

• Что такое стек в программировании?
• Для чего используются указатели в программировании?

Ссылки по теме:

• cyberforum.ru — реализация стека на С++ с использованием исключений 
• ru.wikipedia.org — Википедия: Переполнение буфера
• codenet.ru — рассматривается уязвимость Windows за счет использования переполнения стека  
• sdteam.com — статья «Переполнения стека»
• xakep.ru — статья «Переполнение буфера в стеке», Хакер, №2, 2003

Переполнение стека

• Определение
• Стек программы
• Последствия ошибки
• Причины ошибки
• Примеры
• Итог
• Библиографический список

Определение

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

Стек программы

Стек программы — это специальная области памяти, организованная по принципу очереди LIFO (Last in, first out — последним пришел, первым ушел). Название «стек» произошло из-за аналогии принципа его построения со стопкой (англ. stack) тарелок — можно класть тарелки друг на друга (метод добавления в стек, «заталкивание», «push»), а затем забирать их, начиная с верхней (метод получения значения из стека, «выталкивание», «pop»). Стек программы также называют стек вызовов, стек выполнения, машинным стеком (чтобы не путать его со «стеком» — абстрактной структурой данных).

Для чего нужен стек? Он позволяет удобно организовать вызов подпрограмм. При вызове функция получает некоторые аргументы; также она должна где-то хранить свои локальные переменные. Кроме того, надо учесть, что одна функция может вызвать другую функцию, которой тоже надо передавать параметры и хранить свои переменные. Используя стек, при передаче параметров нужно просто положить их в стек, тогда вызываемая функция сможет их оттуда «вытолкнуть» и использовать. Локальные переменные тоже можно хранить там же — в начале своего кода функция выделяет часть памяти стека, при возврате управления — очищает и освобождает. Программисты на высокоуровневых языках обычно не задумываются о таких вещах — весь необходимый рутинный код за них генерирует компилятор.

Последствия ошибки

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

Произойдет ошибка, называемая переполнением стека. Поскольку стек необходим для организации вызова пользовательских функций (а практически все программы на современных языках, в том числе объектно-ориентированных, так или иначе строятся на основе функций), больше они вызываться не смогут. Поэтому операционная система забирает управление, очищает стек и завершает программу. Здесь можно подчеркнуть различие между переполнением буфера и переполнением стека — в первом случае ошибка происходит при обращении к неверной области памяти, и если защита на этом этапе отсутствует, в этот момент не проявляет себя — при удачном стечении обстоятельств программа может отработать нормально. Если только память, к которой шло обращение, была защищена, происходит ошибка сегментации. В случае со стеком программа непременно завершается.

Чтобы быть совсем точным, следует отметить, что подобное описание событий верно лишь для компиляторов, компилирующих в «родной» (native) код. В управляемых языках у виртуальной машины есть свой стек для управляемых программ, за состоянием которого гораздо проще следить, и можно даже позволить себе при возникновении переполнения передать программе исключение. В языках Си и Си++ на подобную «роскошь» рассчитывать не приходится.

Причины ошибки

Что же может привести к такой неприятной ситуации? Исходя из описанного выше механизма, один из вариантов — слишком большое число вложенных вызовов функций. Особенно вероятен такой вариант развития событий при использовании рекурсии. Бесконечная рекурсия (при отсутствии механизма «ленивых» вычислений) прерывается именно таким образом, в отличие от бесконечного цикла, который иногда имеет полезное применение. Впрочем, при небольшом объеме памяти, отведенной под стек (что, например, характерно для микроконтроллеров), достаточно может быть и простой последовательности вызовов.

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

Однако динамическая память является довольно медленной в плане выделения и освобождения (поскольку этим занимается операционная система), кроме того, при прямом доступе приходится вручную выделять её и освобождать. Память же в стеке выделяется очень быстро (по сути, надо лишь изменить значение одного регистра), кроме того, у объектов, выделенных в стеке, автоматически вызываются деструкторы при возврате управления функцией и очистке стека. Разумеется, тут же возникает желание получить память из стека. Поэтому третий путь к переполнению — самостоятельное выделение в стеке памяти программистом. Специально для этой цели библиотека языка Си предоставляет функцию alloca. Интересно заметить, что если у функции для выделения динамической памяти malloc есть свой «близнец» для её освобождения free, то у функции alloca его нет — память освобождается автоматически после возврата управления функцией. Возможно, это только осложняет ситуацию — ведь до выхода из функции освободить память не получится. Даже несмотря на то, что согласно man-странице «функция alloca зависит от машины и компилятора; во многих системах ее реализация проблематична и содержит много ошибок; ее использование очень несерьезно и не одобряется» — она все равно используется.

Примеры

В качестве примера рассмотрим код для рекурсивного поиска файлов, расположенный на MSDN:

void DirSearch(String* sDir)
 {
     try
     {
         // Find the subfolders in the folder that is passed in.
         String* d[] = Directory::GetDirectories(sDir);
         int numDirs = d->get_Length();
         
         for (int i=0; i < numDirs; i++)
         {
             // Find all the files in the subfolder.
             String* f[] = Directory::GetFiles(d[i],textBox1->Text);
             int numFiles = f->get_Length();

             for (int j=0; j < numFiles; j++)
             {
                 listBox1->Items->Add(f[j]);
             }
             DirSearch(d[i]);
         }
     }
     catch (System::Exception* e)
     {
         MessageBox::Show(e->Message);
     }
 }

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

Пример второго подхода, взятый из вопроса «Почему происходит переполнение стека?» с сайта под названием Stack Overflow (сайт является сборником вопросов и ответов на любые программистские темы, а не только по переполнению стека, как может показаться):

#define W 1000
#define H 1000
#define MAX 100000 
//...
int main()
{
    int image[W*H];
    float dtr[W*H];
    initImg(image,dtr);
    return 0;
}

Как видно, в функции main выделяется память в стеке под массивы типов int и float по миллиону элементов каждый, что в сумме дает чуть менее 8 мегабайт. Если учесть, что по умолчанию Visual C++ резервирует под стек лишь 1 мегабайт, то ответ становится очевидным.

А вот пример, взятый из GitHub-репозитория проекта Flash-плеера Lightspark:

DefineSoundTag::DefineSoundTag(/* ... */)
{
    // ...
    unsigned int soundDataLength = h.getLength()-7;
    unsigned char *tmp = (unsigned char *)alloca(soundDataLength);
    // ...
}

Можно надеятся, что h.getLength()-7 не будет слишком большим числом, чтобы на следующей строчке не произошло переполнения. Но стоит ли сэкономленное на выделении памяти время «потенциального» вылета программы?

Итог

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

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

• Э. Таненбаум. Архитектура компьютера.
• Wikipedia. Stack Overflow.
• man 3 alloca.
• MSDN. How to recursively search folders by using Visual C++.
• Stack Overflow. Stack Overflow C++.
• GitHub. Lightspark — «tags.cpp».

To describe this, first let us understand how local variables and objects are stored.

Local variable are stored on the stack:

If you looked at the image you should be able to understand how things are working.

When a function call is invoked by a Java application, a stack frame is allocated on the call stack. The stack frame contains the parameters of the invoked method, its local parameters, and the return address of the method. The return address denotes the execution point from which, the program execution shall continue after the invoked method returns. If there is no space for a new stack frame then, the StackOverflowError is thrown by the Java Virtual Machine (JVM).

The most common case that can possibly exhaust a Java application’s stack is recursion. In recursion, a method invokes itself during its execution. Recursion is considered as a powerful general-purpose programming technique, but it must be used with caution, to avoid StackOverflowError.

An example of throwing a StackOverflowError is shown below:

StackOverflowErrorExample.java:

public class StackOverflowErrorExample {

    public static void recursivePrint(int num) {
        System.out.println("Number: " + num);
        if (num == 0)
            return;
        else
            recursivePrint(++num);
        }

    public static void main(String[] args) {
        StackOverflowErrorExample.recursivePrint(1);
    }
}

In this example, we define a recursive method, called recursivePrint that prints an integer and then, calls itself, with the next successive integer as an argument. The recursion ends until we pass in 0 as a parameter. However, in our example, we passed in the parameter from 1 and its increasing followers, consequently, the recursion will never terminate.

A sample execution, using the -Xss1M flag that specifies the size of the thread stack to equal to 1 MB, is shown below:

Number: 1
Number: 2
Number: 3
...
Number: 6262
Number: 6263
Number: 6264
Number: 6265
Number: 6266
Exception in thread "main" java.lang.StackOverflowError
        at java.io.PrintStream.write(PrintStream.java:480)
        at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
        at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
        at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
        at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
        at java.io.PrintStream.write(PrintStream.java:527)
        at java.io.PrintStream.print(PrintStream.java:669)
        at java.io.PrintStream.println(PrintStream.java:806)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:4)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        ...

Depending on the JVM’s initial configuration, the results may differ, but eventually the StackOverflowError shall be thrown. This example is a very good example of how recursion can cause problems, if not implemented with caution.

How to deal with the StackOverflowError

1. The simplest solution is to carefully inspect the stack trace and
   detect the repeating pattern of line numbers. These line numbers
   indicate the code being recursively called. Once you detect these
   lines, you must carefully inspect your code and understand why the
   recursion never terminates.

2. If you have verified that the recursion
   is implemented correctly, you can increase the stack’s size, in
   order to allow a larger number of invocations. Depending on the Java
   Virtual Machine (JVM) installed, the default thread stack size may
   equal to either 512 KB, or 1 MB. You can increase the thread stack
   size using the -Xss flag. This flag can be specified either via the
   project’s configuration, or via the command line. The format of the
   -Xss argument is:
   -Xss<size>[g|G|m|M|k|K]

To describe this, first let us understand how local variables and objects are stored.

Local variable are stored on the stack:

If you looked at the image you should be able to understand how things are working.

When a function call is invoked by a Java application, a stack frame is allocated on the call stack. The stack frame contains the parameters of the invoked method, its local parameters, and the return address of the method. The return address denotes the execution point from which, the program execution shall continue after the invoked method returns. If there is no space for a new stack frame then, the StackOverflowError is thrown by the Java Virtual Machine (JVM).

The most common case that can possibly exhaust a Java application’s stack is recursion. In recursion, a method invokes itself during its execution. Recursion is considered as a powerful general-purpose programming technique, but it must be used with caution, to avoid StackOverflowError.

An example of throwing a StackOverflowError is shown below:

StackOverflowErrorExample.java:

public class StackOverflowErrorExample {

    public static void recursivePrint(int num) {
        System.out.println("Number: " + num);
        if (num == 0)
            return;
        else
            recursivePrint(++num);
        }

    public static void main(String[] args) {
        StackOverflowErrorExample.recursivePrint(1);
    }
}

In this example, we define a recursive method, called recursivePrint that prints an integer and then, calls itself, with the next successive integer as an argument. The recursion ends until we pass in 0 as a parameter. However, in our example, we passed in the parameter from 1 and its increasing followers, consequently, the recursion will never terminate.

A sample execution, using the -Xss1M flag that specifies the size of the thread stack to equal to 1 MB, is shown below:

Number: 1
Number: 2
Number: 3
...
Number: 6262
Number: 6263
Number: 6264
Number: 6265
Number: 6266
Exception in thread "main" java.lang.StackOverflowError
        at java.io.PrintStream.write(PrintStream.java:480)
        at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
        at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
        at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
        at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
        at java.io.PrintStream.write(PrintStream.java:527)
        at java.io.PrintStream.print(PrintStream.java:669)
        at java.io.PrintStream.println(PrintStream.java:806)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:4)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        ...

Depending on the JVM’s initial configuration, the results may differ, but eventually the StackOverflowError shall be thrown. This example is a very good example of how recursion can cause problems, if not implemented with caution.

How to deal with the StackOverflowError

1. The simplest solution is to carefully inspect the stack trace and
   detect the repeating pattern of line numbers. These line numbers
   indicate the code being recursively called. Once you detect these
   lines, you must carefully inspect your code and understand why the
   recursion never terminates.

2. If you have verified that the recursion
   is implemented correctly, you can increase the stack’s size, in
   order to allow a larger number of invocations. Depending on the Java
   Virtual Machine (JVM) installed, the default thread stack size may
   equal to either 512 KB, or 1 MB. You can increase the thread stack
   size using the -Xss flag. This flag can be specified either via the
   project’s configuration, or via the command line. The format of the
   -Xss argument is:
   -Xss<size>[g|G|m|M|k|K]

Понятия стека (stack) и кучи (heap) фундаментальны для встраиваемой системы. Их настройка очень важна для стабильной и надежной работы системы. Некорректное использование может привести к тому, что Ваше встраиваемое устройство на микроконтроллере будет глючить самым непредсказуемым образом.

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

[Краткое введение в стек и кучу]

Описание в этой статье сосредоточено на разработке надежного стека и кучи: как минимизировать стек и кучу безопасным способом.

Настольные компьютерные системы (компьютеры PC) и встраиваемые системы одинаково страдают от общих ошибок в дизайне стека и кучи, однако полностью отличаются друг от друга в реализации многих других аспектов. Один пример различий в этих рабочих условиях — размер доступной памяти. Windows и Linux по умолчанию используют 1 и 8 мегабайт пространства под стек; этот размер даже может увеличиваться. Размер кучи ограничен только доступной физической памятью и/или размером файла подкачки. Встраиваемые системы, с другой стороны, имеют очень ограниченный размер по ресурсам памяти, особенно когда это память RAM. Несомненно здесь требуется минимизировать стек и кучу, чтобы уложиться в ограничения по памяти для этого рабочего окружения. Большинство малых встраиваемых систем не имеют механизма виртуальной памяти; выделения стека, кучи и глобальных данных (т. е. переменных, буферов TCP/IP, USB и т. д.) статические, и это происходит в момент сборки приложения.

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

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

Переполнение выделенных данных может произойти в трех областях хранения данных; глобальные переменные (global), стек (stack) и куча (heap). Запись в массивы с превышением индекса или запись по адресу в указателе может привести к выходу за пределы памяти, выделенной для объекта (в таком случае могут быть испорчены другие важные данные). Некоторые попытки доступа к массиву могут быть проверены статическим анализом, например самим компилятором или чекером MISRA C:

int array[32];
array[35] = 0x1234;

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

int* p = malloc(32 * sizeof(int)); 
p += 35;

*p = 0x1234;

Долгое время методы перехвата ошибок переполнения объектов были доступны для десктоп-систем (можно назвать некоторые из них: Purify, Insure++, Valgrind). Эти средства встраивали в код приложения специальные проверки обращений к памяти во время выполнения программы. Это происходит ценой снижения скорости выполнения кода приложения и увеличения размера кода, так что такой метод не может быть полезным для малых встраиваемых систем.

Stack. Стек это область памяти, где программа сохраняет, к примеру, следующие данные:

• Локальные переменные
• Адреса возврата из подпрограмм
• Аргументы функции
• Временные ячейки памяти, используемые компилятором
• Контекст прерываний

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

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

Рис. 1. Ситуация переполнения стека.

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

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

Heap. Куча это то место, где размещена подсистема динамического выделения памяти (не путайте в данном контексте динамическую память с DRAM и SDRAM!). Динамическая память и куча может во многих случаях быть необязательной для применения во встраиваемых системах (может рассматриваться как опция). Динамическая память делает возможным использование одной и той же памяти совместно разными частями программы (имеется в виду не одновременное использование). Когда один модуль больше не нуждается в своей выделенной памяти, он просто возвращает её в общий пул кучи, после чего она может повторно использоваться каким-то другим модулем. Операциями выделения и освобождения памяти заведует специальная библиотека управления динамической памяти, предоставляющая функции наподобие malloc, calloc, realloc и free [] на языке C. Язык C++ использует библиотеку динамической памяти в операторах new и delete. Кучу также могут использовать сторонние библиотеки кода и операционные системы реального времени (RTOS []). Обычно куча одна, но их может быть и несколько. Некоторые особо продвинутые библиотеки даже могут использовать свои функции для обслуживания динамической памяти. 

Типичные примеры данных, которые размещаются в куче:

• Объекты текущих данных
• Объекты C++, время жизни которых управляются операторами new/delete
• Контейнеры STL C++
• Исключения C++

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

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

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

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

[Разработка надежного стека]

Другие типы инструментов, у которых есть необходимая информация для вычисления максимального требования к стеку, это компилятор и линкер. Эта функциональность доступна для среды разработки IAR Embedded Workbench for ARM. Мы рассмотрим некоторые методы, которые можно использовать для оценки требований к размеру стека.

Различные методы установки размера стека. Один из способов вычисления глубины стека — использование адреса текущего указателя стека. Это можно реализовать получением адреса аргумента функции или её локальной переменной. Если это сделать в начале функции main и для каждой из функций, на которую у Вас есть подозрение а большое использование стека, то Вы можете вычислить размер стека, который нужен приложению. Ниже приведен пример, где мы предполагаем, что стек растет от старших адресов памяти к младшим (так организован стек у большинства процессоров, в том числе MCS51, ARM, 8080):

char *highStack, *lowStack;

int main(int argc, char *argv[])
{
   highStack = (char *)&argc; 
   // ... 
   printf("Текущее использование стека (глубина): %dn", highStack - lowStack); 
}

// Самая "подозрительная" функция на предмет углубления в стек:

void deepest_stack_path_function(void) 
{ 
   int a; 
   lowStack = (char *)&a;
   // ... 
}

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

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

Есть вариант этого метода — периодически делать выборку значения указателя стека внутри прерывания таймера, срабатывающего с достаточно высокой частотой. Частота прерываний таймера должна быть максимально возможной, пока она не начинает влиять на производительность реального времени приложения. Типичные частоты могут быть в диапазоне 10..250 кГц. Достоинство этого метода — не нужно вручную искать функцию с самым глубоким использованием стека. Также можно определять использование стека функциями обработки прерывания (ISR), если эта функция обработчика прерывания может вытеснять другие прерывания. Однако следует учитывать, что функции ISR обычно выполняются очень быстро, и анализирующая функция прерывания может пропустить короткий вызов одного из других прерываний.

void sampling_timer_interrupt_handler(void) 
{
   char* currentStack;
   int a;
   currentStack = (char *)&a;
   if (currentStack < lowStack) lowStack = currentStack;
}

Защитная зона стека (stack guard zone). Защитная зона стека это область памяти, размещенная непосредственно ниже стека, где стек оставляет следы, если происходит его переполнение. Этот метод всегда реализуется в настольных (больших) системах, где операционная система может быть просто настроена для детектирования ошибок защиты памяти в ситуациях переполнения стека. На малых встраиваемых системах без блока управления памятью (Memory Management Unit, MMU) защитная зона все еще может быть организована таким же способом, и это будет довольно полезно. Чтобы такая зона была достаточно эффективной, она должна иметь подходящий размер, чтобы поймать записи в эту защитную зону.

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

Самый лучший метод защитной зоны может быть реализован, если MCU оборудован (аппаратным) блоком защиты памяти (memory protection unit, MPU или MMU). В этом случае MPU может быть настроен таким образом, чтобы он срабатывал на записи в защитную зону. Если произошел такого рода недопустимый доступ, будет срабатывать исключение (exception), и обработчик исключения может записать или вывести в лог информацию о том, что произошло. Эту информацию можно будет впоследствии проанализировать.

Рис. 2. Стек с защитной (guard) зоной.

Заполнение области стека известными данными. Одна из техник определения переполнения стека — заполнить все пространство стека заранее известной маской, например байтами 0xCD, перед тем, как приложение начнет свое выполнение. Всякий раз, когда приложение останавливается (например, с помощью отладчика), область памяти стека можно просмотреть в области его конца. В используемой области стека 0xCD не присутствует, потому что туда записывались адреса возврата и значения различных локально используемых регистров и переменных. Если в области стека не найдено значений маски (0xCD), то это означает, что стек переполнился.

Хотя этот способ детектирования переполнения стека достаточно надежен, все равно нет гарантии, что переполнение стека будет обнаружено. Например, стек может некорректно вырасти, переходя через свои границы, и даже изменить память вне области стека, причем без модификации каких-либо байт в области стека. Также стек может быть поврежден в его рабочей области. Это может произойти, например, в случае грубой ошибки, когда приложение ошибочно изменяет области памяти (в том числе и стека), какие оно изменять не должно.

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

Рис. 3. Окно стека в среде разработки IAR Embedded Workbench.

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

Обычно компилятор будет генерировать эту информацию для каждой функции языка C, но в некоторых ситуациях Вы должны сами предоставить для системы информацию, относящуюся к стеку. Например, если в приложении присутствуют косвенные вызовы функций, indirect call (с использованием указателей на функции), то Вы должны предоставить список возможных функций, которые могут быть вызваны из каждой вызываемой функции. Вы можете сделать это с помощью директив pragma в файле исходного кода, или с помощью отдельного файла для управления использования стека (stack usage control file) в процессе линковки.

void foo(int i)
{

#pragma calls = fun1, fun2, fun3 
   func_arr[i](); 
}

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

• Имеется как минимум одна функция без информации по использованию стека.
• Имеется как минимум один косвенный вызов, для которого не предоставлен список возможных вызываемых функций.
• Нет известных косвенных вызовов, однако есть как минимум одна ни откуда не вызываемая функция, которая, как известно, не является корнем графа вызовов.
• Приложение содержит рекурсию (цикл в графе вызовов).
• Имеются вызовы функции, которая декларирована как корень графа вызовов.

Когда разрешен анализ использования стека, в генерируемый map-файл линкера будет добавлена секция использования памяти (usage), где перечисляется каждый граф вызовов от корня в виде цепочки вызовов до самого глубокого уровня использования стека.

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

[Надежный дизайн кучи]

Где тут можно сделать ошибку? Недооценка использования кучи может привести к ошибке при вызове malloc(), т. е. требуемая область памяти не будет выделена. Эту ситуацию можно очень просто отследить программно, проверяя результат вызова функции malloc(). Если она вернет NULL, то значит память не была выделена, но тогда может быть слишком поздно (если это произошло в рабочем изделии у заказчика). Это серьезная ситуация, поскольку в большинстве встраиваемых систем нет подходящего способа восстановления из ошибки по нехватке памяти в куче; есть только один доступный подходящий способ — перезапустить приложение. Переоценка использования кучи необходима из-за динамической природы работы кучи, однако слишком большое выделение памяти для кучи только впустую потратит ценные ресурсы памяти.

При использовании кучи могут произойти две другие ошибки:

• Перезапись данных кучи (переменные и указатели).
• Повреждение внутренней информационной структуры кучи.

Перед тем, как продолжить, давайте вспомним API выделения динамической памяти.

void* malloc(size_t size);

Функция malloc делает следующее:

• Выделяет непрерывный блок памяти размера size байт.
• Возвращает указатель на начало этого выделенного блока.
• Не делает никакую очистку выделенного блока памяти.
• Вернет NULL, если в куче не осталось необходимого количества памяти.

Описание работы функции free:

• Освобождает область памяти (ранее выделенный блок), на которую указывает аргумент p.
• Требует в качестве аргумента достоверного значения указателя p, которое было ранее получено из вызова malloc(), calloc() или realloc().
• Следует избегать нескольких вызовов free(p) для одного и того же значения p (после первого вызова free указатель p становится недостоверным).

void* calloc(size_t nelem, size_t elsize);

Функция calloc работает подобно malloc(), но с тем отличием, что очищает выделенный блок памяти.

void* realloc(void* p, size_t size);

Описание работы функции realloc:

• Работает подобно malloc().
• Увеличивает или уменьшает (меняет размер) ранее выделенного блока.
• Возвращенный блок может иметь новый адрес.

В C++ следующие встроенные операторы языка используют динамическую память кучи:

• Оператор new, работающий подобно malloc().
• new[].
• Оператор delete, работающий подобно free().
• delete[].

Имеется несколько вариантов реализации аллокатора динамической памяти. Наиболее часто сегодня используется Dlmalloc (Doug Lea’s Memory Allocator). Dlmalloc можно найти в Linux, а также во многих инструментах (библиотеках) разработки для встраиваемых систем. Dlmalloc свободно доступна для бесплатного использования (помещена в public domain).

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

Рис. 5 дает некий упрощенный вид на то, как различные структуры данных окружают выделенные пользовательские данные (user data). Становится очевидным, что любая запись в область вне пользовательских данных серьезно повредит кучу.

Рис. 5. Окружение служебными данными выделенного из кучи блока для пользовательских данных.

Вычисление требования к размеру кучи является нетривиальной задачей, если куча используется активно, т. е. когда в процессе работы программы происходит множество циклов выделения и освобождения блоков памяти (обычно это так и есть, иначе куча была бы не нужна). Большинство разработчиков для выбора размера кучи прибегают к методу проб и ошибок, потому что другие альтернативы слишком утомительны. Типичный алгоритм определения размера кучи: найти самый малый размер кучи, при котором приложение все еще работает, затем к полученному размеру добавляют 50% сверху.

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

• Ошибки инициализации

Не инициализированные глобальные данные всегда инициализируются нулями. Хорошо известный факт, что можно легко забыть о том, что вызовы malloc(), realloc() и оператор new языка C++ ничего подобного не делают, т. е. выделенная область данных заполнена мусором. Однако есть специальный вариант malloc(), носящий имя calloc(), который инициализирует нулями выделенный блок для данных. Оператор C++ new вызовет соответствующий конструктор, где следует гарантировать, что все элементы данных сконструированного (выделенного из кучи) объекта будут правильно инициализированы.

• Неправильное разделение скаляров и массивов

На языке C++ есть разные операторы для скаляров и массивов: new и delete применяются для выделения и освобождения скаляров, и new[] и delete[] применяются для массивов.

• Запись в уже освобожденную память

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

• Отсутствие проверки возвращенных значений

Все вызовы malloc(), realloc() и calloc() возвратят указатель NULL, чтобы показать отсутствие свободной памяти (неудачное выделение блока памяти, out of memory). Настольные системы сгенерируют события отказа памяти (memory fault) и нехватки памяти (out-of-memory), так что эти ситуации просто отследить еще в процессе разработки. Встраиваемые системы могут быть устроены по-другому: по адресу 0 у них может быть память программ FLASH, и в них могут происходить больше других тонких ошибок. Если в Вашем MCU есть блок защиты памяти (memory protection unit, MPU), то следует сконфигурировать его таким образом, чтобы генерировались ошибки доступа к памяти при попытке доступа во FLASH и другие критические области (ОЗУ, где находится исполняемый код, защитная область стека и т. п.).

• Освобождение несколько раз одного и того же блока памяти

Это скорее всего повредит внутренние структуры аллокатора памяти, и такую ситуацию сложно определить и исправить.

• Запись вне выделенной области

Это также повредит внутренние структуры аллокатора памяти, и такую ситуацию сложно определить и исправить.

Последние три вида ошибок проще обнаружить, если Вы напишете обертки вокруг стандартных функций malloc(), free() и связанных с выделением памяти функций. Эти обертки должны выделять дополнительные байты памяти, где должна размещаться информация, необходимая для проверок целостности. Пример организации выделения памяти для данных такой обертки показана на рис. 6. 

Рис. 6. Выделение памяти тестовой оберткой MyMalloc.

Здесь поле «magic number» перед данными (user data) используется для детектирования повреждения и будет проверен, когда память будет освобождаться. Поле size, находящееся ниже пользовательских данных, используется оберткой для free() (функция MyFree), чтобы найти «magic number». Пример оберток, показанный ниже, использует 8 байт дополнительной нагрузки на одно выделение памяти, что вполне допустимо для большинства приложений. Этот пример также показывает, как глобально переопределить (override) операторы new и delete языка C++. Пример перехватит только ошибки такого рода, что вся выделенная память не была соответственно освобождена в какой-то момент времени. Для некоторых приложений такая проверка может не потребоваться. В этом случае обертка должна вести список всех выделений памяти, и периодически проверять все выделения, записанные в этом списке. Дополнительная нагрузка реализации этого может быть не такая большая, как это может показаться на первый взгляд, поскольку встраиваемые системы обычно не очень интенсивно используют динамическую память, сохраняя размер списка выделений в разумных пределах.

#include < stdint.h>

#include < stdlib.h>

#define MAGIC_NUMBER 0xefdcba98

uint32_t myMallocMaxMem;

void* MyMalloc(size_t bytes)
{
   uint8_t *p, *p_end;
   static uint8_t* mLow = (uint8_t*)0xffffffff; /* самый малый адрес, возвращенный

                                                   вызовом malloc() */
   static uint8_t* mHigh;     /* самый большой адрес + data, возвращенный malloc() */
   bytes = (bytes + 3) & ~3;  /* гарантирует выравнивание для magic number */
   p = (uint8_t*)malloc(bytes + 8); /* учет области 2x32-бит для size и magic number */
   if (p == NULL)
   {
      abort(); /* ошибка нехватки памяти, out of memory */
   }
   *((uint32_t*)p) = bytes; /* запомнить размер size */
   *((uint32_t*)(p + 4 + bytes)) = MAGIC_NUMBER; /* записать magic number после

                                                    пользовательского выделения */
   /* Грубый метод оценки максимального используемого размера

      с момента запуска приложения. */
   if (p < mLow) mLow = p;
   p_end = p + bytes + 8;
   if (p_end > mHigh) mHigh = p_end;
   myMallocMaxMem = mHigh - mLow;
   return p + 4; /* выделяемая область начинается после size */
}

void MyFree(void* vp)
{
   uint8_t* p = (uint8_t*)vp - 4;
   int bytes = *((uint32_t*)p);
   /* Проверка, что magic number не был поврежден: */
   if (*((uint32_t*)(p + 4 + bytes)) != MAGIC_NUMBER)
   {
      abort(); /* Ошибка: переполнение данных или освобождение блока

                  памяти, который уже был освобожден */
   }
   *((uint32_t*)(p + 4 + bytes)) = 0; /* удаление magic number, чтобы можно было

                                         обнаружить ошибочно-повторное освобождение

                                         блока памяти */
   free(p);
}

#ifdef __cplusplus

// Глобальное переназначение операторов new, delete, new[] и delete[].

void* operator new (size_t bytes) { return MyMalloc(bytes); }

void operator delete (void *p) { MyFree(p); }

#endif

Как установить размер кучи. Итак, как можно определить требуемый минимальный размер кучи для приложения? Из-за того, что может произойти фрагментация памяти в процессе повторяющихся циклов освобождения и выделения памяти, ответ на этот вопрос нетривиален. Рекомендуется запустить тест системы при условиях, когда динамическая память будет использоваться по максимуму. Важно выполнить этот тест несколько раз, чтобы проанализировать переход от малого использования памяти кучи к интенсивному, и оценить её возможную фрагментацию. Когда тесты будут завершены, максимальный уровень выделения памяти в куче сравнивают с реально используемым размером кучи. Реальный размер кучи выставляют, добавляя от 25% до 100% к максимально определенному задействованному размеру кучи, в зависимости от того, как устроено приложение.

Для систем, которые тестируются на дестопных системах путем эмуляции sbrk(), максимальное использование кучи можно узнать через bymalloc_max_footprint().

Для встраиваемых систем, которые не эмулируют sbrk() (а среда разработки IAR Embedded Workbench как раз относится к таким встраиваемым системам), обычно для аллокатора памяти предоставляют память кучи одним куском. В таком случае вызов malloc_max_footprint() становится бесполезным; он просто вернет размер всей кучи. Одним из решений может быть вызов mallinfo() после каждого вызова malloc(), например в обертке функции, описанной раннее, и получить обзор общего выделенного пространства (mallinfo->uordblks). Функция mallinfo() выполняет довольно интенсивные вычисления, так что её использование может повлиять на производительность системы. Лучший метод — записывать максимальные расстояния между выделенными областями памяти. Это просто осуществить, и показано в примере обертки; максимальное значение записывается в переменной myMallocMaxMem. Этот метод будет работать, когда куча предоставлена в одном непрерывной (не состоящей из отдельных кусков) области памяти.

[Стек и куча в IAR 4.41]

В этой старой версии IAR распределение памяти задается в файле *.xcl, который настраивается в опциях проекта (Options… -> Linker -> закладка Config -> Linker command file). Стек начинается от старших (самых больших) адресов памяти и растет к нижним (самым малым адресам), навстречу к функциям __ramfunc и глобальным переменным. Вот пример настройки в XCL-файле, когда кучи нет, и определен только стек размера 400 байт:

//*************************************************************************
// Сегменты стека и кучи.
//*************************************************************************
-D_CSTACK_SIZE=(100*4)
-D_IRQ_STACK_SIZE=(3*8*4)
-D_HEAP_SIZE=0

Если в проекте определена куча, то она находится сразу за локальными переменными, и растет навстречу стеку. Вот другой пример, где определена куча размера 0x3C50 и стек размера 0x1D00:

-D_CSTACK_SIZE=(1D00)
-D_IRQ_STACK_SIZE=(3*8*4)
-D_HEAP_SIZE=3C50

Вот так может выглядеть карта памяти RAM микроконтроллера AT91SAM7X256 для второго примера:

Определить, насколько корректно заданы размер кучи и размер стека, можно с помощью заполнения области кучи и стека заранее известным значением байта. Например, всю память кучи можно заполнить байтом 0xaa, а всю свободную память стека можно заполнить байтом 0xbb. Это целесообразно делать в функции void AT91F_LowLevelInit(void), которая находится в модуле Cstartup_SAM7.c. Пример такого заполнения:

void AT91F_LowLevelInit(void)
{
   ...
   
   //Заполнение кучи известным значением 0xAA:

   #define HEAP_BEGIN 0x0020A344                //взято из map-файла PImain.map

   #define HEAP_SIZE  0x3C50                    //взято из map-файла PImain.map
   memset((void*)HEAP_BEGIN, 0xAA, HEAP_SIZE);
   //Заполнение стека известным значением 0xBB:

   #define STACK_BEGIN (HEAP_BEGIN+HEAP_SIZE)   //стек начинается сразу за кучей

   #define STACK_SIZE  0x1D00-0x0100)           //взято из файла at91SAM7X256_FLASH.xcl
                                                //с отступом 0x0100 байт от конца памяти
   memset((void*)STACK_BEGIN, 0xBB, STACK_SIZE);
}

Как узнать значения HEAP_BEGIN, HEAP_SIZE, STACK_BEGIN, STACK_SIZE. HEAP_BEGIN задает самый младший адрес области памяти кучи, а константа HEAP_SIZE задает размер заполняемой области. Значение HEAP_BEGIN можно узнать опытным путем в отладчике по адресу первого выделенного блока (через malloc или new), или если заглянуть в конец map-файла, раздел «SEGMENTS IN ADDRESS ORDER», там будет указаны начало и конец кучи, пример (параметры кучи выделены жирным шрифтом):

                ****************************************
                *                                      *
                *      SEGMENTS IN ADDRESS ORDER       *
                *                                      *
                ****************************************
SEGMENT              SPACE    START ADDRESS   END ADDRESS     SIZE  TYPE  ALIGN
=======              =====    =============   ===========     ====  ====  =====
ICODE                              00001000 - 0000111B         11C   rel    2
CODE                               0000111C - 0000C5C7        B4AC   rel    2
INITTAB                            0000C5C8 - 0000C5EB          24   rel    2
DATA_ID                            0000C5EC - 00014B6F        8584   rel    2
DATA_C                             00014B70 - 0001651F        19B0   rel    2
CODE_ID                            00016520 - 000169A7         488   rel    2
?FILL1                             000169A8 - 0003FFFF       29658   rel    0
CODE_I                             00200050 - 002004D7         488   rel    2
DATA_I                             002004D8 - 00208A5B        8584   rel    2
DATA_Z                             00208A5C - 0020A33D        18E2   rel    2
DATA_N                             0020A340 - 0020A343           4   rel    2

HEAP                               0020A344 - 0020DF93        3C50   rel    2
INTRAMEND_REMAP                         00210000                     rel    2 

HEAP_SIZE можно узнать из файла XCL в параметре HEAP_SIZE, или из того же map-файла, см. параметр SIZE таблицы выше.

STACK_BEGIN задает самый младший адрес области памяти стека, а STACK_SIZE задает размер заполняемой области. Значение STACK_BEGIN равно следующему за кучей адресу, а STACK_SIZE выбирается таким образом, чтобы заполнение памяти байтом 0xBB гарантированно не перекрыло содержимое стека, действующее в настоящий момент.

После запуска программы в рабочий режим устанавливают условия, при котором должно наблюдаться максимальное использование стека и кучи. Дают программе некоторое время поработать, после чего останавливают отладчик, и после этого в дампе памяти можно увидеть, насколько далеко продвинулось заполнение стека и кучи. Те места, которые еще свободны, будут заполнены байтами 0xAA и 0xBB для кучи и стека соответственно. Ниже на скриншоте показано, как может выглядеть память кучи и стека. Видно, что выделение памяти в куче подошло к своему пределу, дополнительное выделение памяти в куче может привести к переходу на область стека:

[Ссылки]

1. Mastering stack and heap for system reliability site:iar.com.
2. Nigel Jones, blog posts at embeddedgurus.com, 2007 and 2009.
3. John Regehr «Say no to stack overflow», EE Times Design, 2004.
4. Carnegie Mellon University, «Secure Coding in C and C++, Module 4, Dynamic Memory Management», 2010.
5. FreeRTOS: использование стека и проверка стека на переполнение.
6. FreeRTOS: практическое применение, часть 6 (устранение проблем).
7. FreeRTOS, STM32: отладка ошибок и исключений.
8. IAR C-SPY: предупреждение о переполнении стека.
9. Использование стека в IAR и файлы управления стеком.
10. Cortex: отдельный стек для ISR.

Информатика. 11 класс. Углубленный уровень. В 2 ч. Поляков К.Ю., Еремин Е.А. § 42. Стек, очередь, дек

Вопросы и задания

1. Что такое стек? Какие операции со стеком разрешены?
2. Как используется системный стек при выполнении программ?
3. Какие ошибки могут возникнуть при использовании стека?
4. В каких случаях можно использовать обычный массив для моделирования стека?
5. Как построить стек на основе динамического массива?
6. Почему при передаче стека в подпрограммы, приведённые в параграфе, соответствующий параметр должен быть изменяемым?
7. Что такое очередь? Какие операции она допускает?
8. Приведите примеры задач, в которых можно использовать очередь.

Подготовьте сообщение
а) «Моделирование стека и очереди в языке Си»
б) «Моделирование стека и очереди в языке Python»
в) «Моделирование очереди с помощью стеков»
г) «Очередь с приоритетом»

Задача

1. Напишите программу, которая «переворачивает» массив, записанный в файл, с помощью стека. Размер массива неизвестен. Все операции со стеком вынесите в отдельный модуль.

2. Напишите программу, которая вычисляет значение арифметического выражения, записанного в постфиксной форме. Выражение вводится с клавиатуры в виде символьной строки.

3. Напишите программу, которая проверяет правильность скобочного выражения с четырьмя видами скобок: (), [], {} и <>. Все операции со стеком вынесите в отдельный модуль.

*4. Найдите в литературе или в Интернете алгоритм перевода арифметического выражения из инфиксной формы в постфиксную и напишите программу, которая решает эту задачу.

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

*6. Перепишите программу из задачи 5 — используйте статический массив для организации очереди. Считайте, что в очереди может быть не более 100 элементов. Предусмотрите обработку ошибки «очередь переполнена».

*7. Напишите программу решения задачи о заливке области, помечая при этом точки, добавленные в очередь, чтобы не добавлять их повторно. В чём преимущества и недостатки такого алгоритма?