Ответы на вопросы по курсу “Системное программирование” (стр. 5 из 7)
При операции PUSH указатель стека SP увеличится на 1, при извлечении уменьшится на 1.
Природа стека делает необходимым соответствие операций PUSH и POP. Если его нет, то возможно 2 ситуации:
а) переполнение – SP вышел за пределы верхнего значения
б) антипереполнение –“- нижнего.
Очередь – структура данных с дисциплиной FIFO – “первым вошел, первым вышел”.
| -tp | |
| -hp |
Здесь HP – указатель на последнее значение, tp – номер последнего выбранного элемента. Если HP=TP – очередь пуста.
ENQx - добавляем в очередь
HP=HP+1
A[HP]=x
DEQx - извлекаем из очереди
TP=TP+1
x = A[TP]
Особые ситуации - так же как и со стеком.
Для реализации динамических структур данных используют т.н. кучу (heap). Это объем памяти, в котором можно выделить участок для произвольного элемента данных. Для кучи есть 2 операции: выделения памяти ALLOCATE и освобождения FREE. Эти функции не делают никаких действий с собственно памятью. При выделении программист получает адрес, а при освобождении доступный объем кучи становится больше. Одного адреса для этих операций недостаточно, требуется еще и размер элемента данных.
Списки – сложные динамические структуры данных, представляющие собой структуры, содержащие указатели на другие подобные структуры. Если такой указатель в структуре 1 – односвязный список, если 2 – двусвязный, если много – многосвязный. Стек и очередь можно легко представить в виде одно- и двусвязного списка. Списки характеризуются тем, что для них легко реализуется любая дисциплина ввода-вывода за счет простого добавления и удаления элемента.
Для добавления элемента достаточно выделить под него память и присвоить адрес памяти нового элемента соответствующему предыдущему элементу. Для удаления элемента память из-под него освобождается, а указателям на него присваивается некоторое зарезервированное значение NULL – “указатель на ничто”.
   data;struct s *next; | data;struct s *next; | data;struct s *next; | NULL |
Односвязный список
    data;struct s *prev;struct s *next; | data;struct s *prev;struct s *next; | data;struct s *prev;struct s *next; | NULL |
Двусвязный список
Дерево – структура данных, в которой каждому элементу может соответствовать несколько подчиненных элементов, например, для бинарного дерева – два подчиненных элемента. Структура для представления такого дерева – данные и указатели на левого и правого потомков. На таком списке реализуются все операции по обходу деревьев.
 | ||||
 | ||||
 |  | |||
NULL NULL
 |  |  |  |
NULL NULL NULL NULL
Структура двоичного дерева. Каждый элемент содержит поле данных и два указателя - на левого и правого потомков.
Способы выделения памяти в программах: абсолютное, статическое, динамическое и автоматическое распределения. Механизм стека и кучи при реализации процессоров языка программирования.
Статическое выделение памяти – выделение памяти под данные внутри сегмента данных программы. Такие данные существуют на протяжении всей жизни программы до ее завершения.
Автоматическое распределение – выделение памяти под данные в стеке. Такие данные существуют на протяжении работы текущей подпрограммы (функции или процедуры), затем уничтожаются.
Динамическое выделение – выделение памяти под данные самой программой, когда это необходимо. Время жизни таких данных зависит от программы.
В стеке размещаются данные для возврата из подпрограмм, а также их аргументы и автоматические данные. Все это может потребовать достаточно большого размера стека. Как правило, программист может определять размер стека в программе.
Куча. Для реализации динамических структур данных используют т.н. кучу (heap). Это объем памяти, в котором можно выделить участок для произвольного элемента данных. Для кучи есть 2 операции: выделения памяти ALLOCATE и освобождения FREE. Эти функции не делают никаких действий с собственно памятью. При выделении программист получает адрес, а при освобождении доступный объем кучи становится больше. Одного адреса для этих операций недостаточно, требуется еще и размер элемента данных. Если указатель типизированный, размер будет получен автматически. В случае нетипизированного указателя размер должен быть передан в функцию.
Для реализации кучи ЯВУ снабжаются диспетчерами памяти, которые выделяют и освобождают память, имеют сведения о ее фрагментации, знают наибольший кусок свободной памяти и ее общее количество и т.п. При ненадобности память должна своевременно освобождаться. При использовании динамической памяти возможноа ситуация образования «мусора» – кусков памяти, на которые утеряны ссылки, но которые не были своевремменно освобождены, поэтому менеджер считает их занятыми. Для оптимизации известна процедура “уборка мусора” – перестройка динамических структур с освобождением памяти из-под тех данных, на которые отсутствуют ссылки.
Среды ссылок: глобальная, локальная и нелокальная их реализация в исполняющих системах ЯВУ.
Понятие программного модуля: подпрограммы, функции, сопрограммы.
Модульное программирование подразумевает разбиение программы на подпрограммы по специфике обрабатываемых данных. Для этой цели в ЯВУ используются функции и процедуры. При вызове подпрограммы в стеке сохраняется текущее значение счетчика команд (ближняя модель вызова) и значение сегмента кода (дальняя модель вызова). При использовании дальней модели вызова подпрограмма необязательно должна находиться в том же сегменте, что и вызывающая программа. По окончании выполнения кода подпрограммы эти данные восстанавливаются, управление передается на следующий оператор после оператора вызова процедуры.
До вызова подпрограммы в стек помещаются параметры – аргументы подпрограммы. Если передан не сам аргумент, а его адрес, то подпрограмма может изменить аргумент, в противном случае нет, т.к. по завершению работы подпрограммы стек очищается от аргументов. Отличие функций от процедур в том, что функции могут возвращать значения в вызывающую программу и их можно присваивать, например, какой-либо переменной. В действительности функция при возврате значений просто модифицирует регистры процессора, а ЯВУ по соглашению использует данные из этих регистров.
Способы передачи управления между модулями. Применение стека для организации связи в подпрограммах и функциях.
Переписать 26 без первых 2 предложений.
Параметры подпрограмм и функций. Способы передачи параметров – по значению, по ссылке, по имени.
До вызова подпрограммы в стек помещаются фактические параметры – аргументы подпрограммы. Если требуется изменит аргумент в процедуре, то передается не сам аргумент, а его адрес. Существует два способа передачи параметров в подпрограмму для 8086 – соглашения о передаче параметров в С и Паскале. При передаче параметров первым способом запись аргументов в стек идет с последнего до первого, в Паскале наоборот.
Передача самого аргумента – передача параметра по значению. Передача адреса аргумента – передача по ссылке.
В С можно писать подпрограммы с переменным числом параметров, однако это не рекомендуется, т.к. стек имеет ограниченный размер и не желательно передавать по значению элементы данных большого размера.
После выполнения пролога все параметры подпрограммы имеют отрицательное смещение от регистра BP. После выполнения пролога, как правило, в стеке выделяется место под локальные переменные.
По окончании работы процедуры стек очищается от локальных переменнных и параметров.
Общая структура программного модуля для микропроцессора 80х86 – регистр BP, локальные переменные, глобальные переменные, параметры.
Обобщение 26, 28 (см. их для того, чтобы написать более подробно)
Регистр BP – относительно него с отрицательным смещением происходит адресация параметров после выполнения кода пролога в подпрограмме.
push bp
mov bp, sp
mov ax, word ptr [bp-2]; загрузка в ах аргумента
Локальные переменные – размещаются в стеке после вызова процедуры и выполнения кода пролога и удаляются перед завершением.
Глобальные переменные – размещаются в сегменте данных программы и существуют в течение всей жизни программы.