Организация стека: 1.4. Организация стека.

1.4. Организация стека.

сегментируются по регистру CS; во всех остальных инструкциях, если адрес в команде не модифицируется или если он модифицируется, но среди модификаторов нет регистра BP, то этот адрес считается ссылкой в сегмент данных и сегментируется по регистру DS; если же адрес модифицируется по регистру BP, то он считается ссылкой в сегмент стека

ипоэтому по умолчанию сегментируется по регистру SS.

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

MOV AX, ES:[BX].

Стек – это специально выделенная область оперативной памяти, использующая механизм безадресной записи и выборки элементов данных. Этот механизм предполагает, что элемент, записанный последним, будет всегда прочитан первым. Адрес сегмента памяти, в котором располагается стек, определяется регистром SS. Для МП 8086 данные в стек помещаются только в виде слов (по 2 байта). Пара регистров SS:SP всегда указывает на текущую вершину стека. Для занесения слова в стек используется команда push, при этом сначала смещение в SP уменьшается на два, а затем производится запись слова в стек. Для извлечения слова из стека используется команда pop, при этом сначала производится чтение стека, а затем смещение в SP увеличивается на два. Важно помнить, что стек растет в направлении к началу памяти и уменьшается в направлении к ее концу. Стек предназначен для временного хранения переменных, передачи параметров вызываемым подпрограммам и сохранения адреса возврата при вызове процедур и прерываний.

1.5. Организация прерываний.

Иногда в процессе работы процессора возникает необходимость приостановки выполнения текущей программы и запуска другой программы – программы-обработчика, специально написанной для обработки некоторой ситуации. Такие особые ситуации называются прерываниями и делятся на два вида: внешние и внутренние прерывания. Внешние прерывания происходят, когда устройство, подключенное к процессору, само генерирует сигнал прерывания. Внутренние прерывания исходят от процессора в двух случаях: в результате выполнения программной команды int или при определенных условиях, таких как деление на ноль при выполнении команды div, когда генерируется сигнал прерывания для обработки этого типа ошибки.

3. Организация стековой памяти — Организация памяти компьютера

Стековой называют память, доступ к которой организован по принципу: «последним записан — первым считан» (LIFO). Использование принципа доступа к памяти на основе механизма LIFO началось с больших ЭВМ. Применение стековой памяти оказалось очень эффективным при построении компилирующих и интерпретирующих программ, при вычислении арифметических выражений с использованием польской инверсной записи. В малых ЭВМ она стала широко использоваться в связи с удобствами реализации процедур вызова подпрограмм и при обработке прерываний. Принцип работы стековой памяти состоит в следующем (см. рис. 1). Когда слово А помещается в стек, оно располагается в первой свободной ячейке памяти. Следующее записываемое слово перемещает предыдущее на одну ячейку вверх и занимает его место и т.д. Запись 8-го кода, после H, приводит к переполнению стека и потере кода A. Считывание слов из стека осуществляется в обратном порядке, начиная с кода H, который был записан последним. Заметим, что выборка, например, кода E невозможна до выборки кода F, что определяется механизмом обращения при записи и чтении типа LIFO. Для фиксации переполнения стека желательно формировать признак переполнения.   Рис. 1. Принцип работы стековой памяти. Перемещение данных при записи и считывании информации в стековой памяти подобно тому, как это имеет место в сдвигающих регистрах. С точки зрения реализации механизма доступа к стековой памяти выделяют аппаратный и аппаратно-программный (внешний) стеки. Аппаратный стек представляет собой совокупность регистров, связи между которыми организованы таким образом, что при записи и считывании данных содержимое стека автоматически сдвигается. Обычно емкость аппаратного стека ограничена диапазоном от нескольких регистров до нескольких десятков регистров, поэтому в большинстве микропроцессоров такой стек используется для хранения содержимого программного счетчика и его называют стеком команд. Основное достоинство аппаратного стека — высокое быстродействие, а недостаток — ограниченная емкость. Наиболее распространенным в настоящее время и, возможно, лучшим вариантом организации стека в ЭВМ является использование области памяти. Для адресации стека используется указатель стека, который предварительно загружается в регистр и определяет адрес последней занятой ячейки. Помимо команд CALL и RET, по которым записывается в стек и восстанавливается содержимое программного счетчика, имеются команды PUSH и POP, которые используются для временного запоминания в стеке содержимого регистров и их восстановления, соответственно. В некоторых микропроцессорах содержимое основных регистров запоминается в стеке автоматически при прерывании программ. Содержимое регистра указателя стека при записи уменьшается, а при считывании увеличивается на 1 при выполнении команд PUSH и POP, соответственно.

Assembler: 23. Принцип организации стека

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

Для работы со стеком предназначены три регистра:

• ss – сегментный регистр стека;
• sp/esp – регистр указателя стека;
• bp/ebp – регистр указателя базы кадра стека.

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

Перечислим еще некоторые особенности работы со стеком:
• запись и чтение данных в стеке осуществляется в соответствии с принципом LIFO
• по мере записи данных в стек последний растет в сторону младших адресов. Эта особенность заложена в алгоритм команд работы со стеком;
• при использовании регистров esp/sp и ebp/bp для адресации памяти ассемблер автоматически считает, что содержащиеся в нем значения представляют собой смещения относительно сегментного регистра ss.

В общем случае стек организован так:

Регистр ESP/SP всегда указывает на вершину стека, т. е. содержит смещение, по которому в стек был занесен последний элемент. Команды работы со стеком неявно изменяют этот регистр так, чтобы он указывал всегда на последний записанный в стек элемент.

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

Что делать, если нам необходимо получить доступ к элементам не на вершине, а внутри стека? Для этого применяют регистр ЕВР.
Например, типичным приемом при входе в подпрограмму является передача нужных параметров путем записи их в стек. Если подпрограмма тоже активно работает со стеком, то доступ к этим параметрам становится проблематичным. Выход в том, чтобы после записи нужных данных в стек сохранить адрес вершины стека в указателе кадра (базы) стека – регистре ЕВР. Значение в ЕВР в дальнейшем можно использовать для доступа к переданным параметрам.

Как реализовать стек в Python

Возможно вы что то слышали о стеках и задавались вопросом, что это такое? У вас есть общее представление об этом, но вам интересно, как реализовать стек в Python? Тогда вы пришли в нужное место!

В этой статье вы узнаете:

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

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

Что такое стек?

Стек — это структура данных, в которой элементы хранятся в порядке поступления. Его еще часто называют LIFO (Last-In/First-Out). Это отличается его от очереди, в которой элементы хранятся в порядке «первым пришел / первым обслужен» (FIFO).

Вероятно, проще всего понять стек, если вы представите сценарий использования, с которым вы, вероятно, знакомы: функция отмены (Undo) в вашем редакторе.

Давайте представим, что вы редактируете вашу программу на Python. Сначала вы добавляете новую функцию. Это добавляет новый элемент в стек отмены:

Вы можете видеть, что в стеке теперь есть операция Add Function. После добавления функции вы удаляете слово из комментария. Это также добавляется в стек отмены:

Обратите внимание, как элемент «Delete Word» помещается на вершину стека. Наконец, вы делаете отступ для комментария, чтобы он выстроился правильно:

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

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

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

Когда вы снова нажмете кнопку «Отменить», из стека выскочит следующий предмет:

Удалится элемент «Delete Word», оставляя только одну операцию в стеке.

Наконец, если вы нажмете Отменить в третий раз, то последний элемент будет вытолкнут из стека:

Стек отмены теперь пуст. Повторное нажатие кнопки «Отменить» после этого не даст никакого эффекта, поскольку ваш стек отмены пуст, по крайней мере, в большинстве редакторов. Вы увидите, что произойдет, когда вы вызовете .pop() для пустого стека в описании реализации ниже.

Реализация стека в Python

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

Мы посмотрим на следующие реализации стека:

• list
• collections.deque
• queue.LifoQueue

Использование list для создания стека

Встроенная структура list, которую вы, вероятно, часто используете в своих программах, может использоваться и в качестве стека. Вместо .push() можно использовать .append() для добавления новых элементов в верхнюю часть стека, в то время как .pop() удаляет элементы в порядке LIFO:

>>> myStack = []

>>> myStack. append('a')
>>> myStack.append('b')
>>> myStack.append('c')

>>> myStack
['a', 'b', 'c']

>>> myStack.pop()
'c'
>>> myStack.pop()
'b'
>>> myStack.pop()
'a'

>>> myStack.pop()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
IndexError: pop from empty list

В последней команде вы можете видеть, что список вызовет IndexError, если вы вызовете .pop() в пустом стеке.

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

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

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

Есть и менее серьезная проблема. Если вы используете .insert() для добавления элемента в ваш стек в позиции, отличной от конца, это может занять гораздо больше времени. Однако обычно это не то, что вы делаете со стеком.

Следующая структура данных поможет вам обойти проблему перераспределения памяти.

Использование collection.deque для создания стека

Модуль collection содержит deque, который полезен для создания стеков. deque переводиться как «колода» и означает «двусторонняя очередь».

Вы можете использовать те же методы для deque, которые мы видели выше для list, . append() и .pop():

>>> from collections import deque
>>> myStack = deque()

>>> myStack.append('a')
>>> myStack.append('b')
>>> myStack.append('c')

>>> myStack
deque(['a', 'b', 'c'])

>>> myStack.pop()
'c'
>>> myStack.pop()
'b'
>>> myStack.pop()
'a'

>>> myStack.pop()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
IndexError: pop from an empty deque

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

Зачем нужен deque если есть list?

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

Это отлично работает для нескольких операций, таких как индексация в списке. Так получение элемента по индексу myList[3] работает быстро, так как Python точно знает, где искать в памяти. Эта схема памяти также позволяет хорошо работать со срезами списков.

Непрерывное расположение памяти — причина, по которой списку может потребоваться больше времени для .append() одних объектов, чем других. Если блок смежной памяти заполнен, то ему потребуется получить другой блок, который может занять намного больше времени, чем обычный .append():

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

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

Добавление новой записи в структуру связанного списка требует только установки ссылки на новую запись так, чтобы она указывала на текущую вершину стека, а затем указывала вершину стека на новую запись:

Однако это постоянное добавление и удаление записей в стеке сопряжено с компромиссом. Получение данных по индексу myDeque[3] медленнее, чем для списка, потому что Python должен пройти через каждый узел списка, чтобы добраться до третьего элемента.

К счастью, вы редко будете выполнять случайную индексацию или использовать срезы в стеке. Большинство операций над стеком будут push или pop.

Операции .append() и .pop() с постоянным временем делают deque отличным выбором для реализации стека Python, если ваш код не использует многопоточность.

Python стеки и многопоточность

Стеки Python могут быть полезны и в многопоточных программах.

Два варианта, которые вы видели до сих пор, list и deque, ведут себя по-разному, если в вашей программе есть потоки.

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

Примечание. Если вам нужно освежить в памяти информацию о безопасности потоков и условиях гонки, ознакомьтесь с Введение в потоки в Python (An Intro to Threading in Python).

Однако, с deque немного иначе. Если вы прочтете документацию по deque, в ней будет четко указано, что обе операции .append() и .pop() являются атомарными, то есть они не будут прерваны другим потоком.

Так что если вы ограничитесь использованием только .append() и . pop(), то у вас не будет проблем с потоками.

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

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

Хорошо, если вы работаете с потоками, вы не можете использовать list для стека и, вероятно, не захотите использовать deque для стека, так как же вы можно построить стек Python для многопоточной программы?

Ответ находится в модуле очереди, queue.LifoQueue. Помните, как вы узнали, что стеки работают по принципу «последний пришел / первый вышел»? Ну, вот что означает «Lifo» в LifoQueue.

В то время как интерфейс для list и deque похожи, LifoQueue использует .put() и .get() для добавления и удаления данных из стека:

>>> from queue import LifoQueue
>>> myStack = LifoQueue()

>>> myStack.put('a')
>>> myStack.put('b')
>>> myStack.put('c')

>>> myStack
<queue.LifoQueue object at 0x7f408885e2b0>

>>> myStack.get()
'c'
>>> myStack.get()
'b'
>>> myStack.get()
'a'

>>> # myStack.get() <--- waits forever
>>> myStack.get_nowait()
Traceback (most recent call last):
  File "<console>", line 1, in <module>
  File "/usr/lib/python3.7/queue.py", line 198, in get_nowait
    return self.get(block=False)
  File "/usr/lib/python3. 7/queue.py", line 167, in get
    raise Empty
_queue.Empty

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

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

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

Стеки Python: какую реализацию следует использовать?

В общем случае, вы должны использовать deque, если вы не используете многопоточность. Если вы используете многопоточность, то вам следует использовать LifoQueue.

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

Заключение

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

Теперь вы можете:

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

Оригинальная статья: Jim Anderson  How to Implement a Python Stack

Была ли вам полезна эта статья?

[9 / 3. 7]

Организация — стек — Большая Энциклопедия Нефти и Газа, статья, страница 1

Организация — стек

Cтраница 1

Организация стека основана на связном списке, и поэтому стек занимает в памяти только необходимый на данный момент объем.
 [1]

Такая организация стека часто называется магазинной по аналогии с магазином винтовки: патрон, первым помещенный в магазин, выстрелит последним.
 [3]

Особенность организации стека состоит в следующем.
 [5]

Есть различные способы организации стека.
 [7]

Как следует изменить организацию центрального стека, содержащего таблицы сред во время выполнения.
 [8]

Их совместное использование также обеспечивает организацию стека с указателем, адресующим TOS. Однако растет такой стек в сторону увеличения адресов.
 [9]

Содержимое регистра SS определяет текущий сегмент, выделенный для организации стека. Все обращения к памяти, при которых для вычисления адреса прямо или косвенно используются регистры ВР или SP, осуществляются относительно содержимого регистра SS.
 [10]

Для любой программы, в которой используются подпрограммы, необходимо зарезервировать небольшую область памяти для организации стека адресов возврата. Для того чтобы указатель стека определял эту область памяти в начале программы, необходимо обеспечить его начальную установку с помощью команды LDS addr. Как показано на рис. 5.12, указатель стека всегда задает верхний элемент стека, а в случае отсутствия информации в стеке — элемент, смежный с областью памяти, отведенной под стек. Уменьшение значения указателя стека на 1 производится непосредственно перед загрузкой каждого байта в стек, а увеличение на 1 — непосредственно после извлечения байта из стека. Адрес возврата занимает 2 байт.
 [12]

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

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

Указатель стека reg всегда указывает на вершину стека, который заполняется в сторону уменьшения адресов. Это соответствует принятой ранее стандартной организации стека.
 [15]

Страницы:  

   1

   2

   3

Вычислительные системы,сети и телекоммуникации — Организация стека в вычислительных системах

Статистика Онлайн всего: 1 Гостей: 1 Пользователей: 0

Использование в сети того или иного стека коммуникационных протоколов во многом определяет лицо сети и ее характеристики. В небольших сетях может использоваться исключительно один стек. В крупных корпоративных сетях, объединяющих различные сети, параллельно используются, как правило, несколько стеков. Стек OSI. Следует четко различать модель OSI и стек OSI. В то время как модель OSI является концептуальной схемой взаимодействия открытых систем, стек OSI представляет собой набор вполне конкретных спецификаций протоколов. В отличие от других стеков протоколов стек OSI полностью соответствует модели OSI, он включает спецификации протоколов для всех семи уровней взаимодействия, определенных в этой модели. На нижних уровнях OSI поддерживает Ethernet, Token Ring, FDDI, а также такие протоколы как LLC, X.25 и ISDN. Сервисы сетевого, транспортного и сеансового уровней этого стека пока мало распространены. Наиболее популярными протоколами стека OSI являются протоколы, реализующие высокоуровневые сервисы по передаче файлов, эмуляции терминала, ведению каталогов имен и по организации электронной почты. Хотя в стеке OSI предусматривается еще ряд дополнительных высокоуровневых сервисов, многие из них еще не реализованы или реализованы частично.  Из-за своей сложности протоколы OSI требуют больших затрат вычислительной мощности центрального процессора, что делает их более подходящими для мощных машин, а не для сетей персональных компьютеров.  Стек OSI — международный, независимый от производителей, стандарт. Его поддерживает правительство США в своей программе GOSIP, в соответствии с которой все компьютерные сети, устанавливаемые в правительственных учреждениях США после 1990 года, должны или непосредственно поддерживать стек OSI, или обеспечивать средства для перехода на этот стек в будущем. Тем не менее, стек OSI более популярен в Европе, а не в США, так как в Европе меньше установлено старых сетей, использующих свои собственные протоколы. Большинство организаций пока только планируют переход к стеку OSI, и очень немногие приступили к созданию пилотных проектов. Из тех, кто работает в этом направлении, можно назвать Военно-морское ведомство США и сеть NFSNET. Одним из крупнейших производителей, поддерживающих OSI, является компания AT&T, ее сеть Stargroup полностью базируется на этом стеке.  Стек TCP/IP. Стек был разработан по инициативе Министерства обороны США (Department of Defense, DoD) более 20 лет назад для связи экспериментальной сети  ARPAnet с другими сетями как набор общих протоколов для разнородной вычислительной среды. Большой вклад в развитие стека TCP/IP, который получил свое название по популярным транспортным протоколам IP и TCP, внес университет Беркли, реализовав протоколы стека в своей версии ОС UNIX. Популярность этой операционной системы привела к широкому распространению протоколов TCP, IP и других протоколов стека. Этот стек используется для связи компьютеров всемирной информационной сети Internet. Организация Internet Engineering Task Force (IETF) вносит основной вклад в совершенствование стандартов стека, публикуемых в форме спецификаций RFC.  Стек TCP/IP на нижнем уровне поддерживает все популярные стандарты физического и канального уровня: для локальных сетей это Ethernet, Token Ring, FDDI, для глобальных — протоколы работы на аналоговых коммутируемых и выделенных линиях SLIP/PPP, протоколы территориальных сетей X.25 и ISDN.  В качестве основного протокола сетевого уровня в стеке используется протокол Internet Protocol (IP), который изначально проектировался как протокол передачи пакетов в сетях, состоящих из большого количества локальных сетей, объединенных как локальными, так и глобальными связями. Поэтому стек TCP/IP хорошо работает в сетях со сложной топологией, рационально используя наличие в них подсистем и экономно расходуя пропускную способность низкоскоростных линий связи.

Реализация стека TCP/IP на микроконтроллере Microchip PIC18 — Компоненты и технологии

Стеки протоколов TCP/IP для 8-разрядных микроконтроллеров поплнились реализацией для Microchip PIC18. Отличие этой реализации от сущесьвующих состоит в том, что она выполнена на С. Оставив за рамками рассмотрения данной статьи вопросы применения TCP/IP на 8-разрядных микроконтроллерах, обратим внимание на возможность применения языка С и средств разработки для микроконтроллеров Microchip для реализации сложных проектов.

Исходные коды и документация по реализации стека TCP/IP на микроконтроллере Microchip PIC18 доступны на сайте компании
www.microchip.com — application note 833 (
http://www.microchip.com/1010/suppdoc/appnote/all/an833/index.htm). Как можно видеть из документации и исходных кодов, проект был разработан одним человеком за достаточно короткое время. Также положительным свойством данной реализации является то, что проект может быть собран как MPLAB C18, так и HT-SOFT PIC18 компиляторами. То есть в данном случае имеется некая переносимость и независимость от средств разработки, представляемых производителем чипов. Следует заметить, что в отличие от большинства сложных проектов, поставляющихся производителями микросхем в качестве «application note», стек протоколов от Microchip не содержит ошибок и исполняемый файл (прошивка) собирается без проблем. Исходный текст сопровождается подробным и понятным документом (
http://www.microchip.com/download/ appnote/internet/00833b.pdf), содержащим объяснение принципов работы сетевых протоколов, описанием особенностей реализации и опций конфигурации для реализации различных сетевых протоколов и приложений.

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

При наличии отладочной платы PICDEM. net (
http://www.microchip.com/download/tools/picmicro/demo/pdemnet/51240a.pdf), предоставленной фирмой «Гамма», и средств разработки: MPLAB 6.xx, MPLAB C18, HT-SOFT PIC18 — автору удалось собрать работоспособный веб-сервер, несколько отличный от прошитого в плату по умолчанию. Конечно, реализация стека TCP/IP для 8-разрядных микроконтроллеров из-за ограниченных ресурсов не можетбыть полнофункциональной и сопоставимой с распространенным в мире встраиваемых приложений стеком BSD.

Следует заметить, что использование Linux-стека интернет-протоколов во встраиваемых системах ограничено GNU-лицензией, которая требует предоставления исходных кодов, что не всегда приемлемо. Поэтому разработчики встраиваемых систем работают со стеком BSD. Конечно, пока еще не существует 8-разрядных микроконтроллерови средств разработки к ним, которые позволят использовать стек BSD, но, скорее всего, такие микроконтроллеры и не появятся, так как 8-разрядники ориентированы на задачи, требующие минимума ресурсов.

Описание протоколов, реализованных в стеке

Приведем постоянно встречающуюся картинку структуры стека интернет-протоколов (рис. 1).

Как обычно, в построении сетевых решений присутствуют уровни абстракции, начиная с физического уровня, который в данном случае может быть либо SLIP по встроенному последовательному порту, либо 10-мегабитным Ethernet, реализованным на чипе Realtek RTL8019AS, и заканчивая уровнями приложений HTTP и FTP. Для выполнения конкретной задачи не требуется наличия всех уровней, например, при использовании SLIP не требуется протокол ARP. Из-за своей сложности некоторые протоколы реализованы не полностью. Также не обошлось без применения «хитростей», неизвестных автору (следует заметить, что автор не является специалистом по сетевым протоколам). Например, наряду с частичной реализацией DHCP, который служит для динамического выделения IP-адреса, предлагается более простой метод автоматического выделения адреса IP — IP Gleaning.

Это нестандартное решение обеспечивает настройку IP-адреса платы PICDEM. net следующим образом: плата должна получить запрос PING, направленный на адрес платы Ethernet (MAC), IP-адрес, указанный в этом запросе, присваивается плате, и плата отвечает на полученный запрос (и все последующие обращения) с этим IP-адресом.

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

Описание проведем снизу вверх, рассматривая различные варианты параллельно.

Всю работу со средой (MAC) обеспечивает RTL8019AS Network Interface Controller (NIC). Также в памяти сетевого контроллера хранятся пакеты и некоторые данные для протоколов верхних уровней. Альтернативный SLIP-протокол реализован не полностью и может использоваться только совместно с ПК под управлением операционной системы Windows.

Следует обратить внимание, что функции, реализующие «физический» уровень (С-код), вызываемые с верхних уровней, имеют одинаковые имена и набор параметров, что позволяет реализовать механизм абстракции уровней и наглядно демонстрирует структуру стека. То есть приложение или верхние уровни стека — все, что лежит выше MAC/SLIP (рис. 1), не знают, какая среда используется для передачи данных. Таким образом, эти функции являются взаимоисключающими и линкер не позволит собрать приложение, содержащее два способа физической передачи данных. Для решения этого конфликта и выбора остальных опций конфигурации используется препроцессор. Это достаточно мощное средство управления кодом на этапе компиляции. Фактически препроцессор С изменяет исходный код перед вызовом компилятора, и при установке различных опций компилируется различный код. Для микроконтроллера с ограниченными ресурсами такой механизм конфигурации позволяет избежать дополнительных затрат времени и памяти по сравнению с проверками во время исполнения. Также это позволяет собрать все изменения, требующиеся для различных конфигураций, в одном файле. В данном проекте этот файл StackTsk.h и выбор способа доступа к среде определяется константой STACK_USE_SLIP. То есть, если присутствует директива #define STACK_USE_SLIP — стек использует SLIP, если эта директива закомментирована, то используется Ethernet. В данной статье не приводятся все конфигурационные константы, полная таблица приведена в документе к AN833.

Следующим уровнем является ARP — протокол разрешения адреса, который ставит соответствие адреса Ethernet (MAC) и IP. Результатом действия этого протокола является динамически создаваемая таблица, содержащая пары адресов. Это одно из мест, в котором может ограничиваться количество соединений, поддерживаемое стеком одновременно.

Для экономии памяти предопределенное число 5 может быть уменьшено. При использовании соединения SLIP протокол ARP не нужен, что дает экономию оперативной памяти.

Следует заметить, что протокол ARP управляется автономной задачей (ARPtsk), что будет рассмотрено в описании реализации многозадачности.

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

Из-за ограниченного времени на подготовку статьи, автор не разобрался в том, как работает алгоритм маршрутизации в стеке от Microchip.

Так как механизмы маршрутизации достаточно сложные и требуют много памяти для построения таблиц, скорее всего предлагается сильно «облегченная» реализация. Но следует предположить, что вряд ли кто-нибудь будет разрабатывать шлюз или роутер на основе Microchip PIC18. По крайней мере, в данной реализации IP-протокола создаются уникальные пакеты, которые могут передаваться по сетям с возможностью прохождения по нескольким маршрутам и дублированием.

Над IP расположены протоколы TCP и UDP, которые служат непосредственно для передачи данных и образуют «транспортный» уровень. Протокол TCP наиболее известен и часто используется в приложениях. Этот протокол создает так называемые «сокеты», через которые может осуществляться непрерывная (потоковая) передача данных. При этом протокол генерирует непрерывный поток данных независимо от того, что IP-пакеты, которыми пользуется TCP, могут теряться, или нарушается последовательность их приема. Очевидно, что чем больше длина буфера для приема таких пакетов, тем меньше требуется повторов и тем выше скорость передачи. В данной реализации может быть открыто несколько «сокетов» (что дает возможность установить несколько TCP-соединений), но из-за экономии памяти «сокеты» используют общую память и их максимальное число достаточно мало. Автору не удалось поэкспериментировать с несколькими соединениями и нарушениямипоследовательности IP-пакетов (то есть реально проверить работу TCP/IP), но в небольшой локальной сети, где вероятность потери пакета и нарушения порядка следования мала, стек Microchip успешно поддерживал несколько соединений. Так как в TCP существует функция таймаута, то требуется поддержка часов — для этого есть специальная функция учета времени. Более простой в реализации протокол UDP обеспечивает передачу отдельных пакетов. При этом упрощением UDP данного стека является нулевая контрольная сумма, что перекладывает задачу сохранения целостности информации на приложение.

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

DHCP является протоколом высокого уровня, но непосредственно из приложений не вызывается, его предназначение — периодически получать от специального сервера информацию для работы протоколов IP и ARP. Существует отдельная задача, которая обеспечивает динамическую установку IP-адреса платы, IP-адреса шлюза и маски подсети. Для работы DHCP используется протокол UDP, который должен быть разрешен и должен поддерживать требуемое количество «сокетов».

Для работы протоколов HTTP и FTP требуется TCP. Эти протоколы реализованы с ограничениями, но для решения задач, которые могут быть поставлены перед платой PICDEM.net, они достаточны. Реализация файловой системы и поддержки CGI будет описана ниже.

Описание структуры программы

Так как реализация стека не использует какую-либо многозадачную ОС, то управление работой стека возлагается на пользователя.

В качестве примера управления в составе (AN833) приводится StackTsk.c, в котором содержится менеджер задач, реализующий невытесняющую многозадачность. На приложения пользователя это накладывает ряд ограничений: нельзя использовать циклы с ожиданием события, длинные вычисления должны быть разбиты на несколько этапов и т. п. Приложение должно достаточно часто проверять наличие пакетов в буфере NIC-контроллера и обрабатывать их следующим образом:

If a data packet received then
     Get data packet protocol type
         If packet type is IP then
             Fetch IP header of packet
             Get IP packet type
             if IP packet type is ICMP then
                  Call ICMP module
             else if IP packet type is TCP then
                  Call TCP module
             else if IP packet type is UDP then
                  Call UDP module
             else
                  Handle not supported protocol
             End If
          End If
     Else if packet type is ARP then
         Call ARP module
     End If
End If

В AN833 приводятся следующие размеры модулей после компиляции (табл. 1).

Таблица 1. Использование памяти при компиляции HI-TECH PICC18

1. Используется память NIC RNL8019AS.
2. Не учитывается память, требуемая для приемного и передающего буфера, объем которой определяется пользователем.
3. При хранении в памяти микроконтроллера.
4. Максимально возможный. Реальный объем может быть другим.

Автор использовал компилятор MPLAB C18 и получил несколько другие данные, но требуемые размеры не превышали имеющуюся в кристалле память. Также возможно, что при различных опциях компилятора исполнимый код и требования ОЗУ будут получаться различных размеров.

Для обеспечения динамического обновления веб-страниц и взаимодействия с пользователем «хитрым» образом используется механизм CGI. Для динамического отображения информации, реализованного в AN833, в CGI-файле должна быть строка %xx, где хх — номер переменной (0–99). Если HTTP-сервер встречает такую строку, то вызывает функцию, определенную пользователем (в коде приложения) HTTPGetVar. Эта функция изменяет байт (механизм передачи указателя), который затем передается HTTP-сервером клиенту. Функция позволяет передать как один байт, так и строку символов (функция вызывается сервером и передает по одному символу до тех пор, пока строка не закончится). Также механизм CGI позволяет выполнить действия в ответ на сообщение пользователя. Это делается с помощью функции HTTPExecCmd. Аргументами этой функции являются указатель на строки и число, определяющее количество строк (как в стандартной С-функции main). Это позволяет передать любое количество аргументов (ограниченное только размером ОЗУ) в функцию.

В прилагаемом в AN833 примере используются оба метода.

Описание простейшей файловой системы

HTTP-сервер работает с файлами (веб-страница и ее содержание — «контент»). Microchip HTTP-сервер распознает по расширению следующие типы файлов: «.txt», «.htm», «.gif», «.cgi», «.jpg», «.cla» и «.wav». Для хранения этих файлов должна существовать файловая система. В исходном коде к рассматриваемому примеру Microchip предлагает простейшую файловую систему MPFS — она создается один раз и хранится в ПЗУ (либо во внутреннем PIC18, либо во внешнем EEPROM). Для создания файловой системы прилагается специальная утилита — mpfs, а для доступа к файлам во время исполнения кода микроконтроллером предлагаются процедуры, исходный код которых хранится в файле MPFS.c. Организация файловой системы показана на рис. 2.

Microchip FTP-сервер позволяет закачать целый образ MPFS в память платы. То есть сервер поддерживает только команду put, а доступ к отдельным файлам отсутствует.

В идеале, пример должен позволить закачивать веб-странички по FTP, но автору не удалось добиться такой работоспособности.

В прилагаемом примере предлагается такая файловая система:

index.htmmain.htmform.htmcommands.htmstatus.cgiled1.gifled0.gifmchp.gif

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

Выводы

Данный проект является хорошим учебным пособием по разработке сложных структурированных проектов на языке С для Microchip PIC18. Его также можно рекомендовать для начального освоения структуры сетевых протоколов и как пример реализации работоспособного стека TCP/IP. Заслуживает внимания алгоритм реализации невытесняющей многозадачности, используемый в проекте, который при незначительной доработке может быть использован для решения задач, требующих детерминированного времени отклика (real time). Кроме того, может оказаться полезной реализация простейшей файловой системы — как функции для ее работы, так и утилита для создания.

Можно сказать, что это удачный и полезный пример (application note) реализации контроллеров Microchip PIC18. Наверное, наиболее полезным этот пример окажется для применения во встраиваемых системах, работающих с сетью (HTTP или FTP), так как компания Microchip не запрещает использовать этот код в разработках (по крайней мере, автор не обнаружил каких-либо лицензионных ограничений на применение кода).

Организация стека

Компьютеры, использующие организацию ЦП на основе стека, основаны на структуре данных, называемой , стек . Стек — это список слов данных. Он использует метод доступа Last In First Out (LIFO) , который является наиболее популярным методом доступа в большинстве процессоров. Регистр используется для хранения адреса самого верхнего элемента стека, известного как Указатель стека (SP) . В этой организации операции ALU выполняются с данными стека.Это означает, что в стеке всегда требуются оба операнда. После манипуляции результат помещается в стек.

Две основные операции, выполняемые над операторами стека, — это Push и Pop . Эти две операции выполняются только с одного конца.

1. Push —
   Эта операция приводит к вставке одного операнда наверху стека и уменьшению регистра указателя стека. Формат команды PUSH:

    PUSH 

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

    // уменьшаем SP на 1
   СП <- СП - 1
   
   // сохраняем содержимое указанного адреса памяти
   // в SP; то есть наверху стека
   SP <- (адрес памяти) 

2. Pop -
   Эта операция приводит к удалению одного операнда из вершины стека и увеличению регистра указателя стека. Формат инструкции POP:

 POP 

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

 // переносим содержимое SP (т.е. самые верхние данные)
// в указанную ячейку памяти
(адрес памяти) <- SP

// увеличиваем SP на 1
СП <- СП + 1 

В этой организации ЦП для инструкции типа операции не требуется поле адреса. Это связано с тем, что операция выполняется над двумя операндами, которые находятся наверху стека. Например:

 ПОД 

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

PDP-11, Intel 8085 и HP 3000 - вот некоторые из примеров компьютеров, организованных в стек.

Преимущества организации ЦП на основе стека -

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

Недостатки организации ЦП на основе стека -

• Размер программы увеличивается.

Примечание: Организация ЦП на основе стека использует команду нулевого адреса.

Структура данных стека

Стек - это список LIFO (последний пришел, первый ушел).Над стеком можно выполнять ровно две операции.

Схема стека

• Операция push добавляет новый элемент в начало стека.
• Операция выталкивания удаляет элемент из вершины стека.

 // sp указывает на следующий доступный элемент в стеке
     // sp инициализируется 0
     
     int push (int stack [], int sp, int значение)
     {
  если (sp == РАЗМЕР СТЕКА)
      вернуть STACK_FULL;
  еще
      стек [sp ++] = значение;
  вернуть УСПЕХ;
     }
     
     int pop (интервал стека [], интервал sp)
     {
  если (sp == 0)
      вернуть STACK_EMPTY;
  еще
      вернуть стек [- sp];
     } 

Введение в организацию ЦП на основе стека

Введение в организацию ЦП на основе стека

Компьютеры, использующие организацию ЦП на основе стека, основаны на структуре данных, называемой стеком .Стек - это список слов данных. Он использует метод доступа Last In First Out (LIFO) , который является наиболее популярным методом доступа в большинстве процессоров. Регистр используется для хранения адреса самого верхнего элемента стека, известного как Указатель стека (SP) . В этой организации операции ALU выполняются с данными стека. Это означает, что в стеке всегда требуются оба операнда. После манипуляции результат помещается в стек.

Две основные операции, выполняемые над операторами стека: Push и Pop .Эти две операции выполняются только с одного конца.

1. Push -
   Эта операция приводит к вставке одного операнда наверху стека и уменьшению регистра указателя стека. Формат команды PUSH:

    PUSH 

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

    // уменьшить SP на 1
   СП <- СП - 1
   
   // сохраняем содержимое указанного адреса памяти
   // в SP; я.е, вверху стека
   SP <- (адрес памяти) 

2. Pop -
   Эта операция приводит к удалению одного операнда из вершины стека и увеличению регистра указателя стека. Формат команды POP:
   

    POP 

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

    // передача содержимого SP (т.е. самые верхние данные)
   // в указанную ячейку памяти
   (адрес памяти) <- SP
   
   // увеличиваем SP на 1
   SP <- SP + 1 

   Для инструкции типа операции не требуется адресное поле в этой организации ЦП.Это связано с тем, что операция выполняется над двумя операндами, которые находятся наверху стека. Например:

    SUB 

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

   PDP-11, Intel 8085 и HP 3000 - вот некоторые из примеров компьютеров, организованных в стек.

   Преимущества организации ЦП на основе стека -

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

   Недостатки организации ЦП на основе стека -

   • Размер программы увеличивается.

   Примечание: Организация ЦП на основе стека использует команду нулевого адреса.

EazyNotes - Организация стека

СТЕКОВАЯ ОРГАНИЗАЦИЯ
Стек - это структура хранения, в которой информация хранится таким образом, что последний сохраненный элемент является первым извлеченным элементом.Он основан на принципе LIFO (Last-in-first-out). Стек в цифровых компьютерах - это группа ячеек памяти с регистром, который содержит адрес вершины элемента. Этот регистр, который содержит адрес вершины элемента стека, называется Указатель стека .

Операции со стеком
Две операции стека:

1. Push: Вставляет элемент поверх стопки.
2. Pop: Удаляет элемент сверху стопки.

Реализация стека
В цифровых компьютерах стек может быть реализован двумя способами:

1. Стек регистров
2. Стек памяти

Регистровый стек

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

Стек памяти

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

W3Professors

VacationBazaar

Соответствующее образование

Другие наши веб-сайты

mcatutorials.com | Организация стека

Указатель стека

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

.

Две операции стека:

1. Push: Вставляет элемент поверх стопки.
2. Pop: Удаляет элемент из верхней части стопки.

Реализация стека

1. Стек регистров
2. Стек памяти

Стек регистров

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

Стек памяти

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

Об организации стека

Что такое стек? Это особая область памяти вашего компьютера, в которой хранятся временные переменные, созданные каждой функцией (включая функцию main ()). Стек представляет собой структуру данных «FILO» (первым пришел - последний ушел), которая довольно тщательно управляется и оптимизируется процессором.Каждый раз, когда функция объявляет новую переменную, она «помещается» в стек. Затем каждый раз, когда функция завершается, все переменные, помещенные в стек этой функцией, освобождаются (то есть они удаляются). После освобождения переменной стека эта область памяти становится доступной для других переменных стека.

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

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

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

Суммируем стек:

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

Переменные стека

• существуют только тогда, когда функция, которая их создала, работает

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

Две операции - PUSH (вставить)
- Pop (удалить)

Пример подноса для кафетерия

В качестве примера того, как работает стопка, рассмотрим подпружиненный диспенсер для подносов, который часто встречается в кафетериях. Допустим, на каждом подносе выгравирован номер. По одному лотку загружается сверху, каждый опирается на уже загруженные лотки с пружиной, сжимающей, чтобы освободить место для дополнительных лотков по мере необходимости.Например, на рис. 1.1 лотки с номерами 42, 23, 2 и 9 загружены в стопку лотков, причем 42 загружаются первыми, а 9 загружаются последними.

Лоток «Последний вход» имеет номер 9. Таким образом, лоток «Первый ушел» также имеет номер 9. По мере того, как клиенты удаляют лотки из верхней части стопки, первый удаляемый лоток получает номер 9, а второй - лоток номер. 2. Допустим, на этом этапе было добавлено больше лотков. Затем эти лотки должны были выйти из стопки до того, как мы загрузили самый первый лоток. После любой последовательности толчков и хлопков стопки лотков лоток 42 все еще будет находиться внизу.Стопка снова станет пустой только после того, как лоток 42 будет выдвинут из верхней части стопки.

Полезная функция, которая включена в ЦП большинства компьютеров, - это стек или список «последний пришел - первый ушел» (LIFO). Стек - это запоминающее устройство, которое хранит информацию таким образом, что последний сохраненный элемент является первым извлеченным элементом. Операция со стопкой может быть сопряжена со стопкой лотков.

Стек регистров

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

В стеке из 64 слов указатель стека содержит 6 бит, потому что 26 = 64.

Однобитовый регистр FULL устанавливается в 1, когда стек заполнен, а однобитовый регистр EMTY устанавливается в 1, когда стек пуст. DR - это регистр данных, в котором записываются двоичные данные при чтении из стека.

Первоначально SP принимает решение о O, EMTY устанавливается в 1, FULL = 0, так что SP указывает на слово по адресу O, и стек маскируется пустым, а не полным.

PUSH SP ® SP + 1 указатель стека приращения
Элемент модуля M [SP] ® DR на вершине стека
Он (SP = 0) затем (FULL ® 1) проверяет, что стек заполнен
EMTY ® 0 маскирует стек не пусто.

POP DR ® [SP] прочитать элемент через верх стека
SP ® SP –1 декремент SP
Это (SP = 0) затем (EMTY ® 1) проверить, что стек пуст

FULL ® 0 указывает, что стопка не заполнена. Стек может быть помещен в часть большой памяти или может быть организован как
набор из конечного числа слов или регистров памяти. На рисунке X показан
организация стека регистров из 64 слов. Регистр указателя стека SP содержит
двоичное число, значение которого равно адресу слова, которое в данный момент находится наверху
стека.В стопку помещаются три предмета: A, B и C по порядку. пункт C
наверху стека, чтобы содержимое sp теперь равно 3. Чтобы удалить верхний элемент,
стек извлекается путем чтения слова памяти по адресу 3 и уменьшения содержимого SP. Элемент B теперь находится на вершине стека, поскольку SP содержит адрес 2. Чтобы вставить новый элемент

, стек проталкивается путем увеличения SP и записи слова в следующем
более высокое место в стеке. Обратите внимание, что элемент C был считан, но физически не удален.Это не имеет значения, потому что когда стек выталкивается, новый элемент записывается в его
место.

В стеке из 64 слов указатель стека содержит 6 бит, потому что 26
= 64. поскольку SP

имеет только шесть битов, он не может превышать число больше 63 (111111 в двоичном формате). Когда
63 увеличивается на 1, результат равен 0, так как 111111 + 1 = 1000000 в двоичном формате, но SP
может содержать только шесть младших битов. Аналогично, когда 000000 - это
уменьшается на 1, результат равен 111111. Однобитовый регистр Full устанавливается в 1, когда
стек заполнен, а однобитный регистр EMTY устанавливается в 1, когда стек пуст
Предметы.DR - это регистр данных, в котором хранятся двоичные данные для записи или считывания.
стека.

Первоначально SP сброшен на 0, Emty установлен на 1, а Full сброшен на 0, так что SP указывает
к слову по адресу o, и стек помечается как пустой и не полный. если стек нет
полный, новый элемент вставляется с помощью операции push. операция push реализована
со следующей последовательностью микроопераций.

SP ← SP + 1 (указатель увеличения стека)
M (SP) ← DR (запись элемента поверх стека)
if (sp = 0) then (Full ← 1) (проверка, заполнен ли стек)
Emty ← 0 (Стэк отмечен как непустой)

Указатель stac увеличивается на единицу, так что он указывает на адрес следующего более высокого слова.Операция записи в память вставляет слово из DR в верхнюю часть стека. Обратите внимание, что SP содержит адрес вершины стека и что M (SP) обозначает слово памяти, указанное адресом, доступным в настоящее время в SP, первый элемент, хранящийся в стеке, находится по адресу 1. Последний элемент сохраняется по адресу. 0, если SP достигает 0, стек заполнен элементами, поэтому FULLL устанавливается в 1. Это условие достигается, если верхний элемент до последнего нажатия находился в ячейке 63 и после

приращения SP, последний элемент, сохраненный в ячейке 0.Как только элемент сохраняется в ячейке 0, в стеке больше нет пустых регистров. Если элемент записан в стек, очевидно, что стек не может быть пустым, поэтому EMTY очищается до 0. DR ← M [SP] Прочитать элемент из вершины стека SP ← SP-1 Уменьшить указатель стека if (SP = 0 ) then (Emty ← 1) Проверить, пуст ли стек. FULL ← 0 Отметить, что стек не заполнен. Верхний элемент считывается из стека в DR. Затем указатель стека уменьшается. если его значение достигает нуля, стек пуст, поэтому для Emty устанавливается значение 1. Это условие достигается, если считанный элемент находился в ячейке 1.как только этот элемент считан, SP уменьшается и достигает значения 0, которое является начальным значением

SP. Обратите внимание, что если операция pop считывает элемент из местоположения 0, а затем SP уменьшается, SP изменяется на 111111, что равно десятичному значению 63. В этой конфигурации слово в адресе 0 получает последний элемент в стеке. Также обратите внимание, что ошибочная операция приведет к тому, что стек будет вытолкнут, когда FULL = 1, или вытянут, когда EMTY = 1.

Организация и архитектура компьютера (организация стека)

 SP ← SP + 1 Указатель стека приращения
M [SP] ← DR Записать элемент поверх стопки
Если (SP = 0), то (FULL ← 1) Проверить, заполнен ли стек
EMTY ← 0 Отметить стопку как непустую
 

 DR ← M [SP] Прочитать элемент сверху стека
SP ← SP - 1 Уменьшение указателя стека
Если (SP = 0), то (EMTY ← 1) Проверить, пуст ли стек
ПОЛНЫЙ ← 0 Отметить, что стопка не заполнена
 

 SP ← SP - 1
M [SP] ← DR
 

 DR ← M [SP]
SP ← SP + 1
 

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

 1. Единая аккумуляторная организация.
2. Генеральная регистрационная организация.3. Организация стека.

 

Компьютерная организация | Организация ЦП на основе стека

Компьютеры, использующие организацию ЦП на основе стека, основаны на структуре данных, называемой стеком .Стек - это список слов данных. Он использует метод доступа Last In First Out (LIFO) , который является наиболее популярным методом доступа в большинстве процессоров. Регистр используется для хранения адреса самого верхнего элемента стека, известного как Указатель стека (SP) . В этой организации операции ALU выполняются с данными стека. Это означает, что в стеке всегда требуются оба операнда. После манипуляции результат помещается в стек.

Две основные операции, выполняемые над операторами стека: Push и Pop .Эти две операции выполняются только с одного конца.

1. Push -
   Эта операция приводит к вставке одного операнда наверху стека и уменьшению регистра указателя стека. Формат команды PUSH:

    PUSH 

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

    // уменьшаем SP на 1
   СП <- СП - 1
   
   // сохраняем содержимое указанного адреса памяти
   // в SP; то есть наверху стека
   SP <- (адрес памяти) 

2. Pop -
   Эта операция приводит к удалению одного операнда из вершины стека и увеличению регистра указателя стека.Формат инструкции POP:

    POP 

   Удаляет слово данных наверху стека по указанному адресу. Может быть реализовано как:

    // переносим содержимое SP (т.е. самые верхние данные)
   // в указанную ячейку памяти
   (адрес памяти) <- SP
   
   // увеличиваем SP на 1
   СП <- СП + 1 

   Для инструкции типа операции не требуется адресное поле в этой организации ЦП. Это связано с тем, что операция выполняется над двумя операндами, которые находятся наверху стека.Например:

    ПОД 

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

   PDP-11, Intel 8085 и HP 3000 - некоторые из примеров компьютеров, организованных в стек.

   Преимущества организации ЦП на основе стека -

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

   Недостатки организации ЦП на основе стека -

   • Размер программы увеличивается.

   Примечание: Организация ЦП на основе стека использует команду нулевого адреса.

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

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

ins [data-ad-slot = "4502451947"] {display: none! important;}}
@media (max-width: 1000 пикселей) {# place_14> ins: not ([data-ad-slot = "4502451947"]) {display: none! important;}}
@media (max-width: 1000 пикселей) {# place_14 {width: 250px;}}
@media (max-width: 500 пикселей) {# place_14 {width: 120px;}}
]]>

1

8.3 Организация стека Стек: устройство хранения, которое хранит информацию таким образом, что последний сохраненный элемент является первым извлеченным элементом. Также называется списком «последний пришел - первый ушел» (LIFO). Полезно для сложных арифметических операций и вызовов вложенных подпрограмм.

2

8.3 Организация стека • Указатель стека (SP): регистр, который содержит адрес верхнего элемента в стеке. SP всегда указывает на верхний элемент в стопке • Push: операция по вставке элемента в стопку.• Pop: операция по извлечению элемента из стека.

3

СТЕК РЕГИСТРОВ • Стек может быть организован как набор из конечного числа регистров.

4

РЕГИСТРАЦИЯ СТЕКА • В стеке из 64 слов указатель стека содержит 6 битов. • Однобитовый регистр FULL устанавливается в 1, когда стек заполнен; Регистр EMPTY равен 1, когда стек пуст.• Регистр данных DR содержит данные, которые должны быть записаны в стек или считаны из него. 4

5

Следующие микрооперации связаны со стеком
Инициализация SP ¬ 0, EMPTY ¬ 1, FULL ¬ 0 Нажмите SP ¬ SP + 1 M [SP] ¬ DR Если (SP = 0), то (FULL ¬ 1) Обратите внимание, что SP становится 0 после 63 EMPTY ¬ 0 5

6

DR ¬ M [SP] SP ¬ SP - 1 Если (SP = 0), то (EMPTY ¬ 1) FULL ¬ 0
Следующие микрооперации связаны со стеком Pop DR ¬ M [SP] SP ¬ SP - 1 Если (SP = 0), то (ПУСТО ¬ 1) ПОЛНО ¬ 0 6

7

ОПЕРАЦИИ СО СТЕКОМ ОБРАТНАЯ ПОЛЬСКАЯ НОТАЦИЯ (постфикс)
Обратная польская запись: это постфиксная запись (операторы ставятся после операндов) (Пример) Инфиксная запись A + B Обратная польская запись AB + также называется постфиксной.

8

ОПЕРАЦИИ СО СТЕКОМ ОБРАТНАЯ ПОЛЬСКАЯ НОТАЦИЯ (постфикс)
Организация стека очень эффективна для вычисления арифметических выражений A * B + C * D  (AB *) + (CD *)  AB * CD * + (3 * 4) + (5 * 6)  34 * 56 * +

9

ОПЕРАЦИИ СТЕКА ОБРАТНАЯ ПОЛЬСКАЯ НОТАЦИЯ (постфикс)
• Процедура оценки: 1.Просканируйте выражение слева направо. 2. При достижении оператора выполните операцию с двумя операндами, расположенными слева от оператора. 3. Замените два операнда и оператор результатом, полученным в результате операции. (Пример) инфикс 3 * * 6 = 42 постфикс 3 4 * 5 6 * + *

10

ОПЕРАЦИИ СО СТЕКОМ ОБРАТНАЯ ПОЛЬСКАЯ НОТАЦИЯ (постфикс)
• Вычисление обратной польской нотации со стеком.Стек - это наиболее эффективный способ вычисления арифметических выражений. оценка стека: получить значение Если значение - данные: передать данные Иначе, если значение - операция: поп, вычислить и нажать.

11

ОПЕРАЦИИ СО СТЕКАМИ REVERSE POLISH NOTATION (постфикс)
(Пример) с использованием стека для этого * * 6 = 42 => 3 4 * 5 6 * +

12

8.4 Форматы инструкций • Наиболее распространенными полями в форматах инструкций являются: Поле режима: Определяет способ определения действующего адреса. Код операции: Определяет операции, которые должны быть выполнены. Поле адреса: обозначает адрес памяти или регистр процессора Mode Opcode Address 12

13

8.4 Форматы команд • Инструкция с нулевым адресом: используется стек. Арифметическая операция извлекает два операнда из стека и выталкивает результат.• Инструкции с одним адресом: AC и память. Поскольку аккумулятор всегда предоставляет один операнд, необходимо указать только один адрес памяти. • Две адресные инструкции: указываются два адресных регистра или две ячейки памяти, одна для окончательного результата. • Три адресные инструкции: указываются три адресных регистра или ячейки памяти, одна для конечного результата. Это также называется общей адресной организацией.

14

Инструкции с нулевым адресом
Инструкция: ADD Операции push и pop должны указывать один адрес, участвующий в передаче данных.Компьютер, организованный стеком, не использует поле адреса для инструкций ADD, а инструкция MUL: POP X Evaluate X = (A + B) * (C + D) PUSH, а инструкциям POP требуется поле адреса для указания операнда.

15

Инструкции с нулевым адресом
PUSH A PUSH B ADD PUSH C PUSH D MUL POP X Преимущества: Во время операции адреса памяти не требуются. Недостатки: приводит к более длинным программным кодам.

16

Инструкции с одним адресом
Один адрес может быть именем регистра или адресом памяти. ЕДИНАЯ ОРГАНИЗАЦИЯ АККУМУЛЯТОРА Поскольку аккумулятор всегда предоставляет один операнд, необходимо указать только один адрес памяти. Инструкция: ADD X Микрооперация: AC ¬ AC + M [X]

17

Инструкции с одним адресом
ЗАГРУЗИТЬ A ДОБАВИТЬ B СОХРАНИТЬ T Все операции выполняются между регистром AC и операндом памяти. Преимущества: для указания адреса требуется меньшее количество битов.Недостатки: приводит к написанию длинных программ.

18

Две адресные инструкции
• Предполагается, что адрес назначения совпадает с адресом первого операнда. Может быть адресом памяти или именем регистра. Инструкция: ADD R1, R2 Микрооперация: R1  R1 + R2

19

Две адресные инструкции
MOV R1, A MOV R2, B ADD R1, R2 MOV X, R1, наиболее часто встречающиеся в коммерческих компьютерах Каждое поле адреса задает либо регистр процессора, либо операнд памяти. Преимущества: позволяет писать программы среднего размера. Недостатки: больше. биты необходимы для указания двух адресов.

20

Трехадресная организация
ОБЩАЯ ОРГАНИЗАЦИЯ РЕГИСТРА • Три адресные инструкции: необходимо указать адреса памяти для двух операндов и одного адресата.