15. Динамічні зп з довільною вибіркою.
Основная память компьютера, осуществляющая операции записи и др., состоит из из запоминающих устройств двух разновидностей: статические (СтЗУ) и динамические (ДЗУ).
Элементы СтЗУ сохраняют данные, пока не будет отключено питание.
Каждый элемент динамической памяти требует обращения с интервалом минимум 4 мкс, в ином случае информация будет утеряна. В качестве запоминающих элементов в ДЗУ служат микроскопические конденсаторы (заряжен – “1”, незаряжен – “0”).
ДЗУ требует наличия дополнительной управляющей схемы для периодической регенерации каждого элемента памяти. ДЗУ является медленнее СтЗУ, требует перезарядки конденсаторов между последовательными обращениями.
Устройство микросхем ДЗУ:
Рассматриваемое ДЗУ имеет организацию 256х1 и вводит 18–битный адрес в 2 такта. Сначала на линию А0–А8 поступают 9 бит адреса, которые называются адресом строки и фиксируются в микросхеме стробом RAS. Оставшиеся 9 бит адреса называются адресом столбца и фиксируются стробом CAS. Сигнал разрешения записи WE показывает выполнение операции считывания или записи. Записываемый элемент по линии Din считывается и фиксируется в защелке. Считываемый бит снимается с выхода Dout.
16. Стекова адресація. Польський зворотній запис.
Стек – это структура данных, которая используется для временного хранения информации. Программа может поместить данные в стек (PUSH) или забрать их оттуда (POP). Стековая структура данных предполагает упорядочивание помещенных в него данных специальным образом. Во всех случаях первым из стека извлекается то, что было в нем сохранено последним. Такая организация хранения данных сокращенно обозначается LIFO (last in, first out – последний введенный первым выводится). Если мы поместили в стек сначала A, затем B, то первое, что мы извлечем из него будет B. Следующая команда извлечения (POP) вернет A. Информация возвращается из стека в порядке, строго противоположном порядку ее помещения в стек.
Компьютер снабжает стек зарезервированным участком памяти и указателем, называемым указателем стека. Программа использует указатель стека для того, чтобы фиксировать последние помещенные в стек данные, в отличие от почты, где сами элементы очереди продвигаются вперед по мере движения очереди. В компьютере намного легче использовать для слежения за данными указатель и при записи или считывании данных из стека изменять только его. В ответ на выполнение операций POP и PUSH указатель стека соответственно увеличивается или уменьшается.
Операции со стеком
Микропроцессор 8088 адресует стек с помощью регистровой пары SS:SP. Помещение объектов в стек приводит к тому, что он растет в сторону меньших адресов памяти. Стек, кроме всего прочего, служит и для запоминания адресов возврата из подпрограмм.
Рассмотрим некоторые команды, которые непосредственно работают со стеком.
Мнемоника команд очевидна; за кодами операций PUSH и POP следует имя регистра для указания операнда. Единственным исключением является помещение и извлечение из стека регистра флагов, которые используют мнемонику PUSHF и POPF соответственно. Содержимое любой ячейки памяти, которую программа может адресовать, используя возможные способы адресации, также может быть помещено или извлечено из стека.
При любых действиях со стеком в микропроцессоре 8088 базовой единицей информации является 16=битовое слово. Длина любого объекта, помещаемого в стек либо извлекаемого из стека, составляет одно или несколько слов. Байтовых команд, связанных с засылкой данных или извлечением их из стека, не существует. Если, например, программе необходимо сохранить содержимое регистра AL а стеке, она должна поместить содержимое регистра AX, так как не существует способа сохранения только содержимого регистра AL.
Основное назначение стека – временное хранение информации. Стек может использоваться для сохранения адреса возврата; программа также может сохранять данные. Если программа хочет использовать регистр, пусть даже сохранить текущие данные, она может послать значение этого регистра в стек. Эти данные сохраняются в стеке и позже могут быть восстановлены. Например, программе нужно ввести код из порта ввода-вывода 3DAH, а в регистре DX находятся важные данные. Следующая последовательность команд сохраняет регистр DX в стеке на то время, пока он нужен в программе для выполнения команды IN.
PUSH DX
MOV DX, 3DAH
IN AL, DX
POP DX
Операции сохранения регистров в стеке обычно используется в начале программы. В большинстве случаев подпрограмма старается избегать изменения содержимого любого регистра. Поэтому подпрограмма, которой нужны регистры для вычислений и для хранения адресов, помещает все необходимые ей регистры в стек до выполнения команд обработки. Затем, после выполнения, подпрограмма восстанавливает регистры из стека с помощью команд POP.
Если программе выполняется последовательность команд
PUSH BX
PUSH CX
POP BX
POP CX
то результирующим эффектом будет обмен значений в регистрах BX и CX. Еще одним важным моментом является то, что команды PUSH и POP должны быть сбалансированы, т.е. каждой команде PUSH должна соответствовать команда POP. Точно так же, как и в случае скобок в арифметическом выражении, если посылки и извлечения из стека не сбалансированы, результаты будут неверны. Более того, несбалансированные команды PUSH/POP обычно приводят к возврату из подпрограмм по адресу значения данных, а не значения указателя команд из-за того, что микропроцессор 8088 записывает в стек адрес возврата. Обычно это вынуждает микропроцессор выполнять программу, которую программист никогда не писал.
Наряду с сохранением данных, программа может использовать стек в качестве буфера при некоторых пересылках; в частности, не существует команды пересылки, которая бы переносила данные из одного сегментного регистра в другой. В обычном случае загрузка одного сегментного регистра из другого требует сначала загрузки его значения в промежуточный регистр. Это достигается следующей последовательностью из двух команд:
MOV AX,CS ;переслать значение регистра ;CS в регистр AX
MOV DS,AX ;загрузить это значение в регистр DS
Каждая из этих команд имеет длину несколько байт, и эта последовательность разрушает содержимое регистра AX. Альтернативным подходом может быть
PUSH CS ; регистр CS поместить в стек
POP DS ; поместить это значение в регистр DS
Результирующий эффект этой последовательности команд тот же, регистр DS загружается из регистра CS. Здесь длина программы – всего два байта, и к тому же не требуется промежуточный регистр.
Однако эти две команды занимают больше времени, так как нужны дополнительные циклы чтения и записи в стек. Это – метод потери в скорости выполнения ради уменьшения размера объектного кода.
Обратная польская нотация
Объясним обратную польскую нотацию на примере:
Предположим, имеем задачу, которая состоит в написании программы для калькулятора. Здесь допускаются операции +,-,*,/ и знак = (для выдачи ответа). Вместо инфиксного представления калькулятор будет использовать обратную польскую нотацию, поскольку ее несколько легче реализовать. В обратной польской нотации знак следует за операндами; инфиксное выражение типа
(1-2)*(4+5)=
записывается в виде
12-45+*=
круглые скобки при этом не нужны
Реализация оказывается весьма простой. Каждый операнд помещается в стек; когда поступает знак операции, нужное число операндов (два для бинарных операций) вынимается, к ним применяется операция, и результат направляется обратно в стек. Так в приведенном выше примере 1 и 2 помещаются в стек и затем заменяются их разностью, -1. После этого 4 и 5 вводятся в стек и затем заменяются своей суммой,9. Далее числа -1 и 9 заменяются в стеке на их произведение, равное -9. Операция = печатает верхний элемент стека, не удаляя его (так что промежуточные вычисления могут быть проверены).
При реализации, нужна отдельная функция для выборки из ввода следующей операции или операнда. Таким образом, структура программы имеет вид:
WHILE (поступает операция или операнд, а не конец)