Кузин - Логические основы
.pdfГлава I. Оперативная память
Кратко затронем вопрос о способе доступа к регистрам памяти. Говорят, что память устроена как память прямого доступа в случае, когда в операциях явно указывается адрес регистра памяти. Память прямого доступа называется равнодоступной (памятью со случайным доступом) в случае, когда время доступа к регистру памяти не зависит от того, какой регистр был доступен перед этим. Равнодоступная память (память со случайным доступом), подключенная непосредственно к устройству выполнения операций обработки данных (центральному процессору), называется оперативной памятью (оперативным запоминающим устройством -
ОЗУ). Ее англоязычное название - Random Access Memory (RAM).
По принципу действия и технической реализации RAM подразделяется на статическую SRAM, основой которой является триггер, и на динамическую память DRAM, основой которой служит конденсатор. Существенная особенность оперативной памяти - исчезновение хранящихся данных при выключении питания.
В настоящее время более употребительна оперативная память с одной шиной передачи данных (Рис. I.11.b).
Из сказанного выше ясно, что, принято различать логические единицы данных (знак, слово, текст) и технические устройства для хранения этих единиц (двоичный запоминающий элемент, регистр, память).
С целью измерения и сравнения размеров единиц данных вводятся следующие единицы.
Минимальной единицей измерения логической единицы данных служит бит - двоичный символ. Более крупная единица измерения – байт, которая определяется как единица данных в восемь двоичных символов - разрядов. Слово – единица данных , состоящая из целого числа байт.
Ниже приводятся более крупные единицы измерения размеров данных.
Килобайт - 210 байт = 1024 байт. Мегабайт - 220 байт.
Гигабайт - 230 байт. Терабайт -240 байт.
Вышеназванные единицы служат не только для измерения размеров данных, но также для измерения объемов запоминающих устройств, которые хранят эти данные. Термин «байт» используется в двух смыслах. Во - первых, это единица измерения размера данных– байт данных. Во - вторых, это запоминающий регистр емкостью в один байт - байт памяти. Какой смысл в каждом конкретном случае придается тому или иному термину, ясно из контекста.
Во всех современных компьютерных системах регистр оперативной памяти имеет размер в один байт. Говорят, что оперативная память построена «по байтовому» принципу. Таким образом, минимальная единица оперативной памяти, которую можно адресовать, - один байт.
С. Г. Кузин. Логические основы автоматической обработки данных 29
Глава I. Оперативная память
Оперативная память современных персональных компьютеров имеет емкость от 16-ти мегабайт и выше. Чтобы реально представить этот объем, скажем, что в одном мегабайте памяти можно сохранить 500 страниц печатного текста. (Цифра эта зависит от способа хранения и является весьма ориентировочной.)
Кроме емкости, другой характеристикой памяти является быстродействие. Быстродействие памяти определяется как время, необходимое для выполнения одной операции чтения (записи). Очевидно, чем больше быстродействие оперативной памяти – тем больше скорость обработки данных центральным процессором.
При конструировании компьютера определяется базисная техническая единица памяти - слово. Для современного персонального компьютера определяется слово размером в четыре байта (32 двоичных разряда). Для старых моделей персональных компьютеров определялось слово размеров в два байта (16 двоичных разрядов) и даже один байт (8 двоичных разрядов). Суперкомпьютеры имеют слово размером в восемь байт (64 двоичных разряда). На базе слова определяются производные логические единицы данных: полуслово, двойное слово и т.д.
Особо остановимся на зависимости адресного пространства памяти от длины адреса доступа. Для заданной длины p адреса доступа легко определить число различных адресов, которое равно 2p. Таким образом, очевидно соотношение для определения размера адресного пространства: Q = 2p. Ни меньшее, ни большее адресное пространство при заданном p создавать не имеет смысла. Таким образом, для шестнадцатиразрядной архитектуры размер адресного пространства 64 килобайта. Для тридцатидвухразрядной архитектуры размер адресного пространства: 232=4 Гб.
Примечание. Ширина шины данных (шины адреса) не всегда совпадает с длиной слова (длиной кода адреса). Из экономических соображений слово длины n (код адреса длины p) передается по дешевой шине меньшей ширины в несколько тактов.
Например, тридцатидвухразрядное слово может передаваться по шестнадцатиразрядной шине данных за два такта. Естественно, экономя в стоимости - проигрывают в быстродействии.
3.4.Почему компьютерная память двоичная
Стеоретической точки зрения, запоминающий регистр может строиться из n носителей символа, каждый из которых имеет B состояний равновесия и способен хранить любую из B цифр. В этом случае запоминающий регистр в целом может хранить n-разрядное B-ичное число. Однако память современных компьютеров строится на основе носителей двоичного символа. И для этого есть свои причины.
Прежде всего, очевидно, что чем меньше число состояний у носителя символа, - тем надежнее он работает. Минимальное число состояний у носителя символа равно двум.
30 С.Г. Кузин. Логические основы автоматической обработки данных
Глава I. Оперативная память
К счастью, критерий надежности не приходит в противоречие с критерием минимальной стоимости изготовления регистра. Существует разумное предположение, что стоимость изготовления регистра пропорциональна числу знаков регистра, которое определяется как произведение: z = B×n, где B- число состояний носителя знака, n-число разрядов регистра.
Пусть z = 20. Рассмотрим два крайних варианта: двухразрядный регистр из носителей знака с десятью состояниями равновесия и десятиразрядный регистр из носителей знака с двумя состояниями равновесия. В первом случае, регистр может хранить N =102 = 100 различных слов. Во втором случае: N = 210 = 1024 различных слова.
Закономерна постановка вопроса об оптимальном, с точки зрения эффективности, числе состояний носителя знака. Несложные расчеты показывают, что график зависимости N (число различных слов) от B (число состояний носителя знака) при постоянном z (стоимость изготовления регистра) имеет следующий вид:
N |
|
|
|
|
|
|
0 |
1 |
2 |
e |
3 |
4 |
5 |
|
Рис. I.12. График зависимости N от B |
|
||||
Из графика видно, что оптимальным, с точки зрения стоимости изготовления, является нецелое основание e = 2.71... Среди целых оснований оптимум достигается при B=3. Но разница между N(3) и N(2) незначительна. Поэтому, с учетом критерия надежности работы, в качестве регистра компьютера используется двоичный запоминающий регистр, что накладывает двоичную специфику на всю архитектуру компьютера.
Подводя итог, можно сказать следующее:
1.Основой оперативной памяти служит носитель текста (запоминающий массив) из 2p запоминающих регистров - байтов памяти;
2.В каждый момент времени каждый байт памяти хранит байт данных (8 - разрядное двоичное слово);
3.В каждый момент времени память в целом хранит двоичный текст размером 2p байт;
4.Оперативная память принимает p - разрядный двоичный код адреса с шины адреса и обеспечивает прямой доступ к каждому из 2p регистров массива запоминающих регистров по заданному адресу;
С. Г. Кузин. Логические основы автоматической обработки данных 31
Глава I. Оперативная память
5.Оперативная память является равнодоступной (время прямого доступа к байту памяти не зависит от предыстории);
6.Оперативная память обеспечивает выполнение операций чтения/записи для доступного регистра.
3.5.Контрольные вопросы
1.Понятие двоичного символа, двоичного слова и двоичного текста.
2.Технические средства запоминания одного двоичного символа.
3.Технические средства запоминания одного двоичного слова.
4.Технические средства запоминания множества двоичных слов.
5.Понятие разрядной сетки и адресного пространства.
6.Понятие прямого доступа и равнодоступности.
7.Оптимальность двоичной памяти.
8.Свойства оперативной памяти.
32 С.Г. Кузин. Логические основы автоматической обработки данных
Глава I. Типы данных
4. Типы данных
4.1. Понятие типа данных
Мы построили равнодоступную память (память со случайным доступом), состоящую из Q = 2p адресуемых регистров - байт памяти. В каждом байте памяти может храниться 8 - разрядное двоичное слово (содержимое байта памяти - байт данных). Однако при вычислениях компьютер имеет дело не с безликими словами, а с единицами данных. Таким образом, необходимо решить, каким образом различные единицы данных хранятся в компьютерной памяти.
Минимальной адресуемой единицей памяти является байт. Однако, в общем случае, восьми двоичных разрядов недостаточно для размещения любой единицы данных. Поэтому мы будем говорить, что единица данных хранится в ячейке памяти, которая состоит из нескольких байт оперативной памяти. Адресом ячейки служит адрес первого байта, ее образующего.
Здесь мы рассматриваем только простые единицы данных, каждая из которых хранится и обрабатывается как единое целое. К числу простых единиц данных относятся числа и символы. В некоторых случаях в качестве простой единицы данных выступает строка символов.
Понятие типа данных является важнейшим понятием программирования. Тип данных - совокупность правил, определяющих некоторую категорию данных как:
•множество допустимых для нее значений;
•множество допустимых операций над допустимыми значениями;
•способ хранения значения (формат ячейки хранения).
Каждая единица данных в программе является либо константой, либо переменной. Отличие заключается в том, что значение переменной может меняться в процессе выполнения программы.
Следует различать типы данных, реализованные схемотехнически в компьютере, и типы данных, реализованные программно в поддержку языка программирования. Компьютерные типы данных являются простыми (скалярными). Примеры: целое число, вещественное число, символ.
При разработке языков программирования повторяются простые типы данных и затем на их основе конструируются сложные (структурные) типы данных. Примеры: массив, запись, файл.
Типизация данных необходима с нескольких точек зрения. При вводе единицы данных имеется возможность автоматически определить формат ячейки, необходимой для ее хранения.
Указание типа позволяет проконтролировать корректность применения операции к операндам.
С. Г. Кузин. Логические основы автоматической обработки данных 33
Глава I. Типы данных
Например, сложение вещественного числа и символа не имеет смысла. Появляется также возможность использовать один символ для обозначения различных операций (перегрузка операций), например, операция сложения целых чисел и операция сложения вещественных чисел выполняются по различным алгоритмам, но обозначаются одним знаком «+». Исходя из описания типов операндов, можно автоматически распознать, какой алгоритм исполнения операции в данном конкретном случае применять. Более того, во многих случаях возможно автоматическое преобразование значений разнотипных операндов к одному формату.
4.2. Тип данных «целое без знака»
Рассмотрим ячейку памяти размером в один байт. Она состоит из 8-ми двоичных разрядов и может хранить 28 = 256 различных двоичных слова. Каждое такое слово можно интерпретировать как код целого неотрицательного числа (целое без знака).
Таким образом, с каждым состоянием можно связать вполне определенное целое без знака. И если байт находится в каком-либо состоянии rt, мы утверждаем, что он хранит число цбз(rt), связанное с этим состоянием (Рис. I.13)
Бесконечное множество целых чисел без знака |
||||
|
|
|
МАХ |
N+ |
|
|
|
|
|
0 |
1 |
2 |
255 |
|
Конечное множество состояний байта |
|
|||
|
|
|
Рис. I.13. Хранение целого без знака |
|
Однако конечность числа состояний байта памяти позволяет связать с его состояниями только первые 256 чисел. Отсюда возникает принципиальное для компьютерных вычислений понятие максимального представимого числа (в ячейке памяти). Как следствие - понятие диапазона представимости чисел в ячейке памяти Ω = (1…MAX). Образно говоря, число может "убираться или не убираться" в ячейку памяти.
Если для хранения целого числа без знака использовать ячейку
памяти размером в байт, получаем: MAXкороткое цбз = 255, Ωкороткое цбз=
(0...255).
Таким образом, мы определили формат хранения единицы данных: короткое целое без знака.
Если для хранения целого без знака использовать ячейку памяти размером в два байта, получаем тип данных целое без знака: MAXцбз =216
= 65535, Ωцбз= (0...65535).
34 С.Г. Кузин. Логические основы автоматической обработки данных
Глава I. Типы данных Короткое целое без знака
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
6 |
5 |
4 |
3 |
2 |
|
1 |
|
0 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
Целое без знака |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
15 |
14 |
13 |
12 |
|
11 |
|
|
10 |
9 |
8 |
7 |
|
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|||
Рис. I.14. Формат хранения целого числа без знака
Существует еще одно ограничение на использование целых без знака, связанное также с конечностью числа разрядов ячейки памяти. Дело в том, что каждое слагаемое может "убираться" в ячейку памяти, а их сумма уже не "убирается" в ячейку памяти. В этом случае, компьютер выдает сигнал "переполнение разрядной сетки" и прекращает дальнейшие вычисления.
Как говорилось выше, типы данных реализуются как аппаратным, так и программным путем. Поэтому в различных марках компьютеров по существу одинаковые типы данных могут иметь различные названия. В качестве примера перечислим типы данных, представляющие целые числа без знака, для языка программирования Паскаль (версия 6.0).
Таблица I.4. Целые без знака в языке Паскаль
Тип |
Наименование |
Диапазон |
Ячейка |
Операции |
byte |
байт |
0…255 |
1 байт |
<отн>,+,* |
word |
слово |
0…65535 |
2 байта |
<отн>,+,* |
Допустимые для этого типа операции: отношение (=,>,< и т.д.), сложение и умножение.
4.3. Типы данных «символ» и «строка символов»
Обозначение (код) символа на модельном уровне являет собой комбинацию графических линий. Число символов, используемых в модельном мире, конечно и они должны быть реализованы на клавиатуре компьютера в виде клавиш. Кроме того, некоторые, используемые лишь компьютером символы, на клавиатуре компьютера не представлены. Множество представимых символов образует алфавит символов компью-
тера: S=(s1,...,sk,...,sk).
Поставив в соответствие каждому символу алфавита уникальное целое без знака, получим множество чисел Nk=(d1,...,dk,...,dk), каждое из которых обозначает вполне определенный символ. Запись такого числа может храниться в двоичной памяти как код символа.
Теперь необходимо принять решение о размере ячейки памяти, которая используется для хранения символа. На заре эры компьютеризации было принято волевое решение - число различных символов должно быть не более двухсот пятидесяти шести. Для представления любого из 28 = 256 чисел необходима ячейка размером в 8 двоичных разрядов.
С. Г. Кузин. Логические основы автоматической обработки данных 35
Глава I. Типы данных
Таким образом, появилась единица измерения данных и памяти – байт, т.е. слово длиной в восемь двоичных разрядов.
Достаточно быстро выяснилось, что число различных символов, используемых для общения с компьютером, значительно больше двухсот пятидесяти шести. С целью увеличения числа комбинаций двоичных кодов, представляющих символы, были введены два дополнительных бита. Для реализации этих бит на клавиатуре компьютера были введены специальные клавиши. Сначала Ctrl, затем Alt - число комбинаций двоичных кодов символов возросло до 210.. Но и этого оказалось недостаточно. В настоящее время для хранения символов может использоваться ячейка размером в несколько байт.
Соответствие символов и кодирующих их целых чисел без знака представляется в таблице кодирования. При создании такой таблицы учитываются соображения эффективности передачи кода по каналам связи и помехозащищенности его при такой передаче. С целью удовлетворения различных требований существуют различные таблицы кодирования. Такие таблицы разрабатывались, прежде всего, в расчете на латинский алфавит. Поэтому в любой из них соблюдается упорядоченность кодирования цифр и букв. Так, буква “А” кодируется меньшим числом, чем буква “В” и т.д. Это позволяет использовать арифметические операции для сравнения букв (цифр). Например, для определения того, является ли значение переменной Symbol буквой, достаточно вычислить значение отношения: “А”<= Symbol<=“Z’. При включении русских букв (кириллицы) в таблицы кодирования принцип упорядоченности кодирования соблюдается не всегда. Следует учитывать это при программировании задач обработки символов.
Назовем наиболее распространенные таблицы кодирования символов: ASCII /альтернативная/, СP 866 (упорядоченность русских букв, используется в DOS) - Таблица I.5.
Таблица I.5. Кодирование ASCII
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A B C D E F |
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
9 |
|
3 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
4 |
|
A B C D E F G H |
I |
J K L M N O |
|||||||
5 |
P Q R S T U V W X |
Y |
Z |
||||||||
…
9
A
B
C
D
E
F
36 С.Г. Кузин. Логические основы автоматической обработки данных
Глава I. Типы данных
Таблица кодирования СР 125 также соблюдает упорядоченность кодирования русских букв, используется в операционной среде Windows. Таблица кодирования КОИ-8 не соблюдает упорядоченность кодирования русских букв, используется в операционной среде UNICS. Таблица кодирования ISO соблюдает упорядоченность кодирования русских букв и является Госстандартом для оформления документации в Российские фонды алгоритмов и программ.
Проблема кодирования (и хранения) символьных строк решается очевидным образом: последовательность образующих строку символов кодируется последовательностью кодов этих символов. Таким образом, если каждый символ занимает при хранении одну ячейку памяти, то строка длиной в q символов занимает q последовательных ячеек памяти.
К |
О |
Т |
01001011 |
01001111 |
01011110 |
1-й байт |
2-й байт |
3-й байт |
В качестве другого примера назовем типы данных, представляющие символы и строки символов, для языка программирования Паскаль.
Тип |
Наименование |
Диапазон |
Ячейка |
Операрции |
char |
символ |
ASCII |
1 байт |
Отношения |
string |
строка |
дл. стр.<256 |
дл. стр. |
Специфич. |
Операции для char: отношения, которые позволяют сравнивать и сортировать символы. Операции для string: отношения, определение длины строки, конкатенация строк, выделение подстроки, удаление подстроки, вставка подстроки, определение позиции подстроки.
4.4. Тип данных «целое»
При сложении двух целых без знака в качестве результата получается также целое без знака. Операция вычитания определяется как обратная операция к операции сложения. Однако при вычитании результат далеко не всегда является целым без знака. Говоря другими словами, множество N+ целых чисел без знака незамкнуто относительно операции вычитания (Рис. I.15).
- |
+ |
|
|
0 |
N |
|
Рис. I.15. Множество целых чисел без знака замкнуто относительно операции сложения и умножения, но незамкнуто относительно операции вычитания
Необходимо ввести понятие отрицательного числа и множества целых чисел со знаком или, просто, целых чисел Z. Операция вычитания замкнута относительно этого множества (Рис. I.16).
С. Г. Кузин. Логические основы автоматической обработки данных 37
Глава I. Типы данных
- +
Z
0
Рис. I.16. Множество целых чисел замкнуто относительно операций сложения, умножения и вычитания.
Очевидным образом вводится понятие алгебры целых чисел:
A<цч> = <Z;+,-,*, , ,div,mod> (I.20)
Здесь, Z - основное множество алгебры; +,-,* - бинарные операции сложения, вычитания и умножения целых чисел.
Существуют также две унарные операции изменения знака числа:- унарный плюс и - унарный минус. (В практике вычислений обозначения этих унарных операций такое же, как обозначение бинарных операций сложения и вычитания: + и -. Унарность или бинарность операции определяется из контекста записи арифметического выражения.)
Алгебра целых чисел замкнута относительно операций сложения, вычитания и умножения, а также операций изменения знака. Сложнее с операцией деления целых чисел. В общем случае при делении одного целого числа на другое целое число получается нецелое число. Поэтому, вводятся две специфические операции целочисленного деления: x div y (результат операции - целая часть от деления) и x mod y (результат операции - остаток от деления). Можно утверждать, что алгебра целых чисел замкнута относительно таких операций деления.
Позиционная система счисления (кодирования) целых чисел
строится по аналогии с позиционной системой счисления целых чисел без знака. Каноническое арифметическое выражение имеет вид:
ЗНАЧЕНИЕв(целое) = ±(dn-1*Bn-1+dn-2*Bn-1+...+d1*B1+d0*B0)в.( I.21)
Запись целого числа образуется очевидным образом: |
|
±< dn-1, dn-2,…d1,d0 > |
(I.22) |
Для хранения двоичного кода целого числа используется ячейка памяти, в которой старший разряд представляет знак числа: 0 - знак «плюс». 1 - знак «минус».
Ячейка памяти (размером один байт, два байта, четыре байта) имеет конечное число состояний (Рис. I.17). Отсюда следует, что имеется максимально представимое целое число (положительное) МАХ и минимально представимое целое число (отрицательное) MIN.
38 С.Г. Кузин. Логические основы автоматической обработки данных