Полустатические структуры данных
По мотивам В.Д.Далека и др. "Модели и структуры данных"
Полустатические структуры данных характеризуются следующими признаками: они имеют переменную длину и простые процедуры ее изменения; изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.
Наиболее распространены следующие типы полустатических структур: очереди FIFO, стеки и строки.
Очередь FIFO
Очередью FIFO (First In First Out - "первым пришел первым вышел") называется такой вектор (последовательный список) с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Основные операции над очередью: включение нового элемента (put) и исключение элемента (get).
При размещении очереди в памяти для нее выделяется память, как для вектора.
С очередью связаны два указателя: на начало очереди (на первый элемент в
очереди) - head - и на ее конец (первый свободный элемент в очереди) - tail.
При включении элемента в очередь новое значение записывается по адресу tail,
после чего этот указатель инкрементируется. При исключении элемента из
очереди выбирается значение, адресуемое указателем head, после чего этот
указатель инкрементируется. В приведенном примере под очередь выделено четыре
ячейки оперативной памяти, H - указатель начала, T - указатель конца.
|
put(B) |
|
put(C) |
|
get → A |
|
Очевидно, что со временем указатель на конец при очередном включении элемента достигнет верхней границы той области памяти, которая выделена для очереди. Однако, если операции включения чередовались с операциями исключения элементов, то в начальной части отведенной под очередь памяти имеется свободное место. Для того, чтобы места, занимаемые исключенными элементами, могли быть повторно использованы, очередь замыкается в кольцо: указатели (на начало и на конец), достигнув конца выделенной области памяти, переключаются на ее начало. Такая организация очереди в памяти называется кольцевой очередью.
| put(D) |
|
Возможны, конечно, и другие варианты организации: например, всякий раз, когда указатель конца достигнет верхней границы памяти, сдвигать все непустые элементы очереди к началу области памяти, но как этот, так и другие варианты требуют перемещения в памяти элементов очереди и менее эффективны, чем кольцевая очередь.
В исходном состоянии указатели на начало и на конец указывают на начало области памяти. Равенство этих двух указателей (при любом их значении) является признаком пустой очереди. Если в процессе работы с кольцевой очередью число операций включения превышает число операций исключения, то может возникнуть ситуация, в которой указатель конца "догонит" указатель начала. Когда указатель конца лишь на один элемент отстает от указателя начала, очередь считается заполненной и дальнейшие попытки записи в нее блокируются (хотя остается еще один свободный элемент, эта ситуация не будет отличима от ситуации пустой очереди).
Примером кольцевой очереди в вычислительной системе является буфер клавиатуры, реализуемый средствами BIOS. Буфер клавиатуры занимает последовательность байтов памяти по адресам от 0040:001E до 0040:003D включительно (32 байта). По адресам 0040:001A и 0040:001C располагаются указатели на начало и конец очереди, соответственно. При нажатии на любую клавишу генерируется прерывание 9. Обработчик этого прерывания читает скан-код нажатой клавиши и помещает в конец очереди этот скан-код, а также ASCII-код нажатой клавиши (для расширенных (двухбайтовых) кодов помещается только расширенный код). Коды нажатых клавиш могут накапливаться в буфере клавиатуры, прежде чем они будут прочитаны программой. Программа при вводе данных с клавиатуры обращается к сервису операционной системы, который выбирает код клавиши из буфера - из начала очереди - и передает в программу.
Очередь является одним из ключевых понятий в многозадачных операционных системах (Windows NT, Unix, OS/2 и др.). Ресурсы вычислительной системы (процессор, оперативная память, внешние устройства и т.п.) используются всеми задачами, одновременно выполняемыми в среде такой операционной системы. Поскольку многие виды ресурсов не допускают реально одновременного использования разными задачами, такие ресурсы предоставляются задачам поочередно. Таким образом, задачи, претендующие на использование того или иного ресурса, выстраиваются в очередь к этому ресурсу. Также в современных операционных системах одним из средств взаимодействия между параллельно выполняемыми задачами являются очереди сообщений, называемые также почтовыми ящиками. Каждая задача имеет свою очередь - почтовый ящик, и все сообщения, отправляемые ей от других задач, попадают в эту очередь. Задача-владелец очереди выбирает из нее сообщения.
Стек
Стек - это вектор (последовательный список) с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны вектора, называемой вершиной стека. Применяются и другие названия стека: магазин и очередь LIFO (Last In First Out - "последним пришел первым вышел"). Основные операции над стеком: включение нового элемента (push) и исключение элемента из стека (pop).
При размещении стека в памяти для него выделяется память, как для вектора. Вершина стека (указатель стека - stack pointer) может указывать либо на первый свободный элемент стека, либо на последний записанный в стек элемент. (Все равно, какой из этих двух вариантов выбрать, важно в последствии строго придерживаться его при обработке стека.) В приведенном примере под стек выделено четыре ячейки памяти, а указатель стека (SP) адресует последний записанный элемент.
|
push(B) |
|
push(C) |
|
pop → C |
|
Если считать, что стек растет в сторону уменьшения адресов, то при занесении нового значения в стек, указатель стека декрементируется и включаемое в стек значение записывается по адресу, соответствующему новому значению указателя стека. При извлечении элемента из стека, производится выборка значения, адресуемого указателем стека, и инкрементируется указатель стека. Элементы ниже значения, адресуемого указателем стека, считаются свободными. Если вся отведенная под стек область заполнена, очередная операция занесения в стек приводит к ситуации, именуемой переполнением стека (stack overflow). Попытка чтения из пустого стека называется опустошением стека (stack underflow).
Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов процедур. Предположим, имеется процедура A, которая вызывает процедуру B, а та в свою очередь - процедуру C. Когда выполнение процедуры A дойдет до вызова B, процедура A приостанавливается и управление передается на входную точку процедуры B. Когда B доходит до вызова C, приостанавливается B и управление передается на процедуру C. Когда заканчивается выполнение процедуры C, управление должно быть возвращено в B, причем в точку, следующую за вызовом C. При завершении B управление должно возвращаться в A, в точку, следующую за вызовом B. Правильную последовательность возвратов легко обеспечить, если при каждом вызове процедуры записывать адрес возврата в стек. Так, когда процедура A вызывает процедуру B, в стек заносится адрес возврата в A; когда B вызывает C, в стек заносится адрес возврата в B. Когда C заканчивается, адрес возврата выбирается из вершины стека - а это адрес возврата в B. Когда заканчивается B, в вершине стека находится адрес возврата в A, и возврат из B произойдет в A.
В микропроцессорах семейства Intel IA-32, как и в большинстве современных процессорных архитектур, поддерживается программно-аппаратный стек. Стек располагается в основной памяти, указатель стека содержится в паре специальных регистров - SS:SP (SS:ESP), доступных для программиста. Стек растет в сторону уменьшения адресов, указатель стека адресует первый свободный элемент. Выполнение команд CALL (вызов процедуры) и INT (вызов программного прерывания), а также аппаратных прерываний включает в себя запись в стек адреса возврата. Выполнение команд RET (возврат из процедуры) и IRET (возврат из прерывания) включает в себя выборку из стека адреса возврата и передачу управления по этому адресу. Пара команд (PUSH и POP) обеспечивает использование стека для программного решения других задач.
В качестве примера полностью аппаратного стека можно привести математические сопроцессоры по стандарту IEEE-754 (например, устройство вещественной арифметики (FPU) в IA-32).
Соглашения о вызовах
Free Pascal Programmers' Manual
Системы программирования для блочно-ориентированных языков (Паскаль, Си и др.) используют стек для размещения в нем параметров и локальных переменных процедур. При каждой активизации процедуры память для ее параметров и локальных переменных выделяется в стеке. При завершении процедуры эта память освобождается. Поскольку при вызовах процедур всегда строго соблюдается вложенность, то в вершине стека всегда находятся локальные переменные и параметры активной в данный момент процедуры. Этот прием делает возможной легкую реализацию рекурсивных процедур. Когда процедура вызывает сама себя, то для всех ее локальных переменных выделяется новая память в стеке, и вложенный вызов работает с собственным представлением локальных переменных. Когда вложенный вызов завершается, занимаемая его переменными область памяти в стеке освобождается и актуальным становится представление локальных переменных предыдущего уровня.
Низкоуровневая (зависящая от реализации) схема передачи параметров функций и получения их результата называется соглашением о вызовах (calling conventions). Если ассортимет функций, смысл их параметров и результата определяется прикладным программным интерфейсом (API), то соглашение о вызовах является частью двоичного интерфейса приложений (ABI). Реализация соглашения о вызовах зависит от платформы, языка программирования и компилятора.
Соглашение о вызовах определяет:
- порядок (слева направо или справа налево) и способ передачи параметров функции (через стек, через регистры процессора или микс);
- значения каких регистров процессора могут быть изменены вызываемой функцией, а каких — сохраняются;
- особенности подготовки стека перед вызовом функции и при возврате из неё.
На 32-битной платформе Intel (x86) наибольшее распространение получили три соглашения о вызовах: cdecl, pascal и stdcall. Большинство компиляторов (например, Free Pascal Compiler, GNU Compiler Collection и др.) позволяют указать, какое соглашение о вызовах использовать при генерации кода.
Соглашение о вызовах языка Паскаль (pascal) (используется компилятором Borland Pascal) определяет, что параметры в стек помещаются слева направо, а по завершении процедуры стек от параметров очищается самой процедурой. Результат функции возвращается в регистре-аккумуляторе (8-битные значения — в AL, 16-битные — в AX, 32-битные — в EAX или в DX:AX в 16-битном режиме).
Пример вызова функции с двумя целочисленными параметрами:
(* Паскаль: *) res:=sum(a,b); | PUSH a PUSH b CALL sum MOV [res],EAX |
Код любой функции содержит пролог и эпилог. В прологе обязательно сохраняется регистр EBP, т.к. каждая итерация любой функции использует именно этот регистр для обращения к своим параметрам и локальным переменным, которые образуют стековый кадр (stack frame). Затем в EBP загружается новое значение указателя стекового кадра, соответствующее вершине стека. Положительные смещения относительно указателя стекового кадра соответствуют:
- старому значению указателя стекового кадра (из родительской процедуры),
- адресу возврата (EIP),
- значениям параметров.
После пролога следует основной код процедуры или функции. В эпилоге при
необходимости в аккумулятор заносится результат функции, затем стек освобождается
от локальных переменных (команда LEAVE приравнивает ESP значению EBP и
восстанавливается указатель стекового кадра родительской процедуры) и
происходит возврат с освобождением указанного количества элементов стека от
параметров процедуры.
function sum(a, b:integer):integer; pascal; var tmp:integer; begin tmp:=a+b; sum:=tmp; end; |
int pascal sum(int a, int b)
{
int tmp;
tmp=a+b;
return tmp;
}
| PUSH EBP MOV EBP,ESP SUB ESP,8 MOV EAX,[EBP+12] ADD EAX,[EBP+8] MOV [EBP-8],EAX MOV [EBP-4],EAX MOV EAX,[EBP-4] LEAVE RET 2 |
|
Соглашение о вызовах языка Си (cdecl) определяет, что параметры в стек помещаются справа налево, а по завершении процедуры стек от параметров очищается вызываемым кодом. Результат функции возвращается в регистре-аккумуляторе (EAX). Это соглашение позволяет работать с функциями с переменным числом параметров, однако генерируемый код получается больше, чем в первом случае.
Пример вызова функции с двумя целочисленными параметрами. Сначала в стек
помещается второй параметр, затем - первый. После возврата из функции указатель
стека увеличивается на размер параметров, освобождая, таким образом, от них стек.
/* Си: */ res=sum(a,b); | PUSH b PUSH a CALL sum ADD ESP,8 MOV [res],EAX |
Пример реализации такой функции:
function sum(a, b:integer):integer; cdecl; var tmp:integer; begin tmp:=a+b; sum:=tmp; end; |
int cdecl sum(int a, int b)
{
int tmp;
tmp=a+b;
return tmp;
}
| PUSH EBP MOV EBP,ESP SUB ESP,8 MOV EAX,[EBP+8] ADD EAX,[EBP+12] MOV [EBP-8],EAX MOV [EBP-4],EAX MOV EAX,[EBP-4] LEAVE RET |
|
Поскольку стек от параметров освобождается в вызывающем коде, команда RET извлекает лишь адрес возврата, не затрагивая параметры.
В реализациях соглашения о вызовах языка Си бывают вариации. Например, поздние версии компилятора GCC (начиная с 4.5) при вызове любой функции всегда выравнивают стек по 16-байтной границе.
Стандартное соглашение о вызовах (stdcall) определяет, что параметры в стек помещаются справа налево, а по завершении процедуры стек от параметров очищается самой процедурой. Результат функции возвращается в регистре-аккумуляторе (EAX). Это соглашение допускает использование функций с переменным числом параметров (с некоторыми оговорками), а код по длине не превышает первый случай. Это соглашение используется, например, в функциях Windows API.
На 64-битной платформе Intel (x86_64) используются два соглашения о вызовах: Microsoft x64 и System V.
Соглашение о вызовах Microsoft x64 используется в 64-битных версиях Windows и UEFI. Четыре первых аргумента функции помещаются в регистры процессора: RCX, RDX, R8, R9. Все последующие — в стек (справа налево). Результат возвращается в регистре-аккумуляторе (RAX). Вызывающий код должен перед вызовом зарезервировать в стеке 32 байта (shadow space) под схранение старых значений регистров RCX, RDX, R8, R9 и освободить стек от них после вызова. Стек должен быть выровнен по 16-байтной границе.
Соглашение о вызовах System V AMD64 является стандартом для 64-битных Unix-подобных операционных систем на платформе Intel x86_64 (Solaris, Linux, FreeBSD, macOS, ...). Шесть первых аргументов функции помещаются в регистры процессора: RDI, RSI, RDX, RCX, R8, R9. Все последующие — в стек (справа налево). Результат возвращается в регистре-аккумуляторе (RAX). От параметров стек очищается вызывающим кодом. Стек должен быть выровнен по 16-байтной границе.