68853

Устройства компьютеров и их взаимодействие

Лекция

Информатика, кибернетика и программирование

Концепция кэш-памяти возникла раньше чем архитектура IBM 360 и сегодня кэш-память имеется практически в любом классе компьютеров а в некоторых компьютерах во множественном числе. Все термины которые были определены раньше могут быть использованы и для кэш-памяти хотя слово строка line часто употребляется вместо слова блок block.

Русский

2014-09-26

753.5 KB

0 чел.

PAGE  31


C P U

Мост /контроллер памяти

Кэш 2-го ур.

DRAM

Локальная шина PCI

Граф. подсистема

Встроенный IDE

Интерфейс шины расширениярасширения

Шина ISA, EISA, MCA

РИС. 4.6. Архитектура персонального компьютера

онитор

Тема 4. Структура комп’ютерів.

Фізичні основи комп’ютерів. Пристрої комп’ютерів та їх взаємодія. Комбінаційні схеми та цифрові автомати. Базові логічні елементи “І”, “АБО”,”І-НІ”,”АБО-НІ”. Пристрої: тригери, дешифратори, мультиплексори, суматори, центральний процесор,  оперативна, дискова, флеш та інші види пам’яті. Опис набору регістрів. Організація оперативної, дискової, флеш та інших видів пам’яті. Системи переривань.

4.1.1. Пристрої комп’ютерів та їх взаємодія.

Процессор. Является основным компонентом любого ПК. Выполняет все вычисления и обработку данных, одной из наиболее существенных характеристик центрального процессора является размер шины данных и адресной шины.

В настоящее время наиболее распространены процессоры фирмы Intel, хотя ЦП других фирм (AMD, Cyrix) составляют им достойную конкуренцию. Производительность любого процессора при выполнении заданной программы зависит от трех параметров: такта (или частоты) синхронизации, среднего количества команд, выполняемых за один такт, и общего количества выполняемых в программе команд. Ни один из указанных параметров,  невозможно изменить,  независимо от других, поскольку соответствующие базовые технологии взаимосвязаны. При  этом,  частота синхронизации определяется достигнутым уровнем технологии интегральных схем и функциональной организацией процессора. Среднее количество тактов на команду зависит от функциональной организации и архитектуры системы команд, а количество выполняемых в программе команд определяется архитектурой системы команд и технологией компиляторов. Из этого видно, что создание нового высокопроизводительного процессора требует решения сложных вопросов во всех трех направлениях разработки. При этом эффективная с точки зрения стоимости конструкция не может полагаться только на увеличение тактовой частоты. Экономические соображения заставляют разработчиков принимать решения, основой которых является массовая технология.

4.1.2. Шина- это группы соединений для передачи сигналов или совокупность электрических линий для обмена данными между частями компьютера. Сигналы в компьютере передаются по шинам в виде последовательности 0 и 1. Кроме этого, тип шины определяет и сигналы, которые передаются по этим линиям. В персональном компьютере типы шин определяются материнской платой. Основными характеристиками шин являются разрядность передаваемых данных и скорость передачи данных в Мбайт/с.  Наибольший интерес вызывают два типа шин: системный и локальный.

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

a).  Шина стандарта ISA (Industry standart architecture - промышленная стандартная архитектура) принята в моделях персонального компьютера IBM PC, IBM PC/XT, IBM PC/AT и компьютерах с процессором i80386. Характеризуется 16-разрядными данными и относительно невысокими скоростями обмена данными по шине.

в). Шина стандарта EISA (Extended Industry Standart Architecture - усовершенствованная промышленная стандартная архитектура) используется в компьютерах с процессорами i80386 и i486. является не отдельным стандартом, а лишь расширением ISA, в связи с чем в нем сохраняется аппаратная совместимость с предыдущими моделями ПК.

в). Шина стандарта MCA (Micro Channel Architecture - микроканальная архитектура) предложена в 1987 г. фирмой IBM для PS/2. Обеспечивает быстрый обмен данными между отдельными устройствами, в частности с оперативной памятью, однако несовместима с ISA и EISA.

2). Локальной шиной, как правило, называется шина, непосредственно подключенная к контактам микропроцессора, т.е. шина процессора. Локальные шины начали использоваться с компьютеров на базе процессоров i486. Локальная шина работает на частоте, равной внешней частоте микропроцессора: 

- локальная шина стандарта VLB (VESA Local Bus, где VESA - Video Equipment Standards Assotiation - Ассоциация стандартов видеооборудования) разработана в 1992 г. Иногда эту шину называют VESA. Одним из недостатков шины VLB является невозможность ее использования с процессорами следующего поколения: Pentium, Alpha, Power PC и др. В настоящее время устарела;

- шина стандарта PCI (Peripheral Component Interconnect - взаимосвязь пе

ISA

EISA

VLB

PCI

Год создания

1984

1988

1992

1992

Разрядность

тракта данных

8,16

32

32

32

64

Частота шины,

МГц

8

8

33

40

33

33

Максимальная пропускная

способность,

Мбайт/с

8

33

133

148

132

264

риферийных компонентов) создана в 1992 г. Строго говоря, шина PCI не является локальной, т.к. между ней и шиной процессора имеется специальный, согласующий сигналы блок. Кроме этого, стандарт PCI предусматривает использование вспомогательного контроллера, который берет на себя разделение сигналов процессора и шины и осуществляет разрешение конфликтов. Таким образом, шина PCI является независимой от типа процессора. Частота работы шины тоже не зависит от частоты процессора и составляет 33 МГц. Имеется 64-разрядная версия шины. Шина PCI поддерживает технологию "plug-and-play" (вставь-и-работай). Широко используется в настоящее время. Во время перехода на шину PCI существова ли компьютеры с архитектурой, предусматривающей работу с тремя шинами ISA, VLB и PCI. Такая шина называется VIP (по начальным буквам входящих в нее стандартов).

3).Шинный контроллер. Контроллер, обеспечивающий формирование потоков данных, передаваемых по шине в соответствии со стандартом, и управляющий передачей сигналов по шине.

4.1.3. КЭШ пам'ять. Концепция кэш-памяти возникла раньше чем архитектура IBM/360, и сегодня кэш-память имеется практически в любом классе

компьютеров, а в некоторых компьютерах - во множественном числе.

Все термины, которые были определены раньше могут быть использованы и для кэш-памяти, хотя слово "строка" (line) часто употребляется вместо слова "блок" (block).

Таб. №4.2

Типовые значения ключевых параметров для кэш-памяти рабочих станций и серверов

Размер блока (строки)

4-128 байт

Время попадания (hit time)

1-4 такта синхронизации
(обычно 1 такт)

Потери при промахе (miss penalty)
(Время доступа - access time)
(Время пересылки - transfer time)

8-32 такта синхронизации
(6-10 тактов синхронизации)
(2-22 такта синхронизации)

Доля промахов (miss rate)

1%-20%

Размер кэш-памяти

4 Кбайт - 16 Мбайт

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

1. Где может размещаться блок в кэш-памяти?

Принципы размещения блоков в кэш-памяти определяют три основных типа их организации:

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

(адрес блока кэш-памяти) =  (адрес блока основной памяти) mod (число  

                                                    блоков в кэш-памяти)

- если некоторый блок основной памяти может располагаться на любом месте кэш-памяти, то кэш называется полностью ассоциативным (fully associative);

- если некоторый блок основной памяти может располагаться на ограниченном множестве мест в кэш-памяти, то кэш называется множественно-ассоциативным (set associative). Обычно множество представляет собой группу из двух или большего числа блоков в кэше. Если множество состоит из n блоков, то такое размещение называется множественно-ассоциативным с n каналами (n-way set associative). Для размещения блока прежде всего необходимо определить множество. Множество определяется младшими разрядами адреса блока памяти (индексом):

(адрес множества кэш-памяти) =
(адрес блока основной памяти) mod (число множеств в кэш-памяти)

Далее, блок может размещаться на любом месте данного множества.

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

2. Как найти блок, находящийся в кэш-памяти?

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

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

Адресация множественно-ассоциативной кэш-памяти осуществляется путем деления адреса, поступающего из процессора, на три части:

- поле смещения используется для выбора байта внутри блока кэш-памяти;

- поле индекса определяет номер множества;

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

3. Какой блок кэш-памяти должен быть замещен при промахе?

При возникновении промаха, контроллер кэш-памяти должен выбрать подлежащий замещению блок. Польза от использования организации с прямым отображением заключается в том, что аппаратные решения здесь наиболее простые. Выбирать просто нечего: на попадание проверяется только один блок и только этот блок может быть замещен. При полностью ассоциативной или множественно-ассоциативной организации кэш-памяти имеются несколько блоков, из которых надо выбрать кандидата в случае промаха. Как правило для замещения блоков применяются две основных стратегии: случайная и LRU.

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

Во втором случае, чтобы уменьшить вероятность выбрасывания информации, которая скоро может потребоваться, все обращения к блокам фиксируются. Заменяется тот блок, который не использовался дольше всех (LRU - Least-Recently Used).

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

Таб. № 4.3

Сравнение долей промахов для алгоритма LRU и случайного алгоритма замещения при нескольких размерах кэша и разных ассоциативностях при размере блока 16 байт

Ассоциативность:

2-канальная

4-канальная 8-канальная

Размер кэш-памяти

LRU Random

LRU Random LRU Random

16 KB

5.18% 5.69%

4.67% 5.29% 4.39% 4.96%

64 KB

1.88% 2.01%

1.54% 1.66% 1.39% 1.53%

256 KB

1.15% 1.17%

1.13% 1.13% 1.12% 1.12%

4. Что происходит во время записи?

При обращениях к кэш-памяти из реальных программ,  преобладают обращения по чтению. Все обращения за командами являются обращениями по чтению и большинство команд не пишут в память. Обычно операции записи составляют менее 10% общего трафика памяти. Желание сделать общий случай более быстрым означает оптимизацию кэш-памяти для выполнения операций чтения, однако при реализации высокопроизводительной обработки данных нельзя пренебрегать и скоростью операций записи.

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

Однако при выполнении операции записи ситуация коренным образом меняется. Именно процессор определяет размер записи (обычно от 1 до 8 байтов) и только эта часть блока может быть изменена. В общем случае это подразумевает выполнение над блоком последовательности операций чтение-модификация-запись: чтение оригинала блока, модификацию его части и запись нового значения блока. Более того, модификация блока не может начинаться до тех пор, пока проверяется тег, чтобы убедиться в том, что обращение является попаданием. Поскольку проверка тегов не может выполняться параллельно с другой работой, то операции записи отнимают больше времени, чем операции чтения.

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

  •  сквозная запись (write through, store through) - информация записывается в два места: в блок кэш-памяти и в блок более низкого уровня памяти.
  •  запись с обратным копированием (write back, copy back, store in) - информация записывается только в блок кэш-памяти. Модифицированный блок кэш-памяти записывается в основную память только когда он замещается. Для сокращения частоты копирования блоков при замещении обычно с каждым блоком кэш-памяти связывается так называемый бит модификации (dirty bit). Этот бит состояния показывает был ли модифицирован блок, находящийся в кэш-памяти. Если он не модифицировался, то обратное копирование отменяется, поскольку более низкий уровень содержит ту же самую информацию, что и кэш-память.

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

Когда процессор ожидает завершения записи при выполнении сквозной записи, то говорят, что он приостанавливается для записи (write stall). Общий прием минимизации остановов по записи связан с использованием буфера записи (write buffer), который позволяет процессору продолжить выполнение команд во время обновления содержимого памяти. Следует отметить, что остановы по записи могут возникать и при наличии буфера записи.

При промахе во время записи имеются две дополнительные возможности:

  •  разместить запись в кэш-памяти (write allocate) (называется также выборкой при записи (fetch on write)). Блок загружается в кэш-память, вслед за чем выполняются действия аналогичные выполняющимся при выполнении записи с попаданием. Это похоже на промах при чтении.
  •  не размещать запись в кэш-памяти (называется также записью в окружение (write around)). Блок модифицируется на более низком уровне и не загружается в кэш-память.

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

4.1.3.Увеличение производительности кэш-памяти
Формула для среднего времени доступа к памяти в системах с кэш-памятью выглядит следующим образом:

Среднее время доступа = Время обращения при попадании + Доля промахов * Потери при промахе

Эта формула наглядно показывает пути оптимизации работы кэш-памяти: сокращение доли промахов, сокращение потерь при промахе, а также сокращение времени обращения к кэш-памяти при попадании. Ниже в Таб. №4.4 кратко представлены различные методы, которые используются в настоящее время для увеличения производительности кэш-памяти. Использование тех или иных методов определяется прежде всего целью разработки, при этом конструкторы современных компьютеров заботятся о том, чтобы система оказалась сбалансированной по всем параметрам.

Таб. №4.4

Обобщение методов оптимизации кэш-памяти

Метод

Доля
прома

хов

Потери
при
пром
ахе

Время обращения при попадании Сложность аппаратуры Примечания

1

2

3

4

Увеличение размера блока

+

0

Повышение степени ассоциативности

+

 

- 1  

Кэш-память с вспомогательным кэшем

+

 

2  

Псевдоассоциативные кэши

+

 

2  

Аппаратная предварительная выборка команд и данных

+

 

2 Предварительная выборка данных затруднена

1

2

3

4

Предварительная выборка под управлением компилятора

+

 

3 Требует также неблокируемой кэш-памяти

Специальные методы для уменьшения промахов

+

 

0 Вопрос ПО

Установка приоритетов промахов по чтению над записями

 

+

1 Просто для однопроцессорных систем

Использование подблоков

 

+

+ 1 Сквозная запись + подблок на 1 слово помогают записям

Пересылка требуемого слова первым

 

+

2

Неблокируемые кэши

 

+

3

Кэши второго уровня

 

+

2 Достаточно дорогое оборудование

Простые кэши малого размера

-

 

+ 0

Обход преобразования адресов во время индексации кэш-памяти

 

 

+ 2  

Конвейеризация операций записи для быстрого попадания при записи

 

 

+ 1  

4.2.Принципы организации основной памяти в современных компьютерах

Основная память представляет собой следующий уровень иерархии памяти. Основная память удовлетворяет запросы кэш-памяти и служит в качестве интерфейса ввода/вывода, поскольку является местом назначения для ввода и источником для вывода. Для оценки производительности основной памяти используются два основных параметра: задержка и полоса пропускания. Традиционно задержка основной памяти имеет отношение к кэш-памяти, а полоса пропускания или пропускная способность относится к вводу/выводу. В связи с ростом популярности кэш-памяти второго уровня и увеличением размеров блоков у такой кэш-памяти, полоса пропускания основной памяти становится важной также и для кэш-памяти.

Задержка памяти традиционно оценивается двумя параметрами: временем доступа (access time) и длительностью цикла памяти (cycle time). Время доступа представляет собой промежуток времени между выдачей запроса на чтение и моментом поступления запрошенного слова из памяти. Длительность цикла памяти определяется минимальным временем между двумя последовательными обращениями к памяти.

Основная память современных компьютеров реализуется на микросхемах статических и динамических ЗУПВ (Запоминающее Устройство с Произвольной Выборкой). Микросхемы статических ЗУВП (СЗУПВ) имеют меньшее время доступа и не требуют циклов регенерации. Микросхемы динамических ЗУПВ (ДЗУПВ) характеризуются большей емкостью и меньшей стоимостью, но требуют схем регенерации и имеют значительно большее время доступа.

В процессе развития ДЗУВП с ростом их емкости основным вопросом стоимости таких микросхем был вопрос о количестве адресных линий и стоимости соответствующего корпуса. В те годы было принято решение о необходимости мультиплексирования адресных линий, позволившее сократить наполовину количество контактов корпуса, необходимых для передачи адреса. Поэтому обращение к ДЗУВП обычно происходит в два этапа: первый этап начинается с выдачи сигнала RAS - row-access strobe (строб адреса строки), который фиксирует в микросхеме поступивший адрес строки, второй этап включает переключение адреса для указания адреса столбца и подачу сигнала CAS - column-access stobe (строб адреса столбца), который фиксирует этот адрес и разрешает работу выходных буферов микросхемы. Названия этих сигналов связаны с внутренней организацией микросхемы, которая как правило представляет собой прямоугольную матрицу, к элементам которой можно адресоваться с помощью указания адреса строки и адреса столбца.

Дополнительным требованием организации ДЗУВП является необходимость периодической регенерации ее состояния. При этом все биты в строке могут регенерироваться одновременно, например, путем чтения этой строки. Поэтому ко всем строкам всех микросхем ДЗУПВ основной памяти компьютера должны прозводиться периодические обращения в пределах определенного временного интервала порядка 8 миллисекунд.

Это требование кроме всего прочего означает, что система основной памяти компьютера оказывается иногда недоступной процессору, так как она вынуждена рассылать сигналы регенерации каждой микросхеме. Разработчики ДЗУПВ стараются поддерживать время, затрачиваемое на регенерацию, на уровне менее 5% общего времени. Обычно контроллеры памяти включают в свой состав аппаратуру для периодической регенерации ДЗУПВ.

В отличие от динамических, статические ЗУПВ не требуют регенерации и время доступа к ним совпадает с длительностью цикла. Для микросхем, использующих примерно одну и ту же технологию, емкость ДЗУВП по грубым оценкам в 4 - 8 раз превышает емкость СЗУПВ, но последние имеют в 8 - 16 раз меньшую длительность цикла и большую стоимость. По этим причинам в основной памяти практически любого компьютера, проданного после 1975 года, использовались полупроводниковые микросхемы ДЗУПВ (для построения кэш-памяти при этом применялись СЗУПВ). Естественно были и исключения, например, в оперативной памяти суперкомпьютеров компании Cray Research использовались микросхемы СЗУПВ.

Для обеспечения сбалансированности системы с ростом скорости процессоров должна линейно расти и емкость основной памяти. В последние годы емкость микросхем динамической памяти учетверялась каждые три года, увеличиваясь примерно на 60% в год. К сожалению скорость этих схем за этот же период росла гораздо меньшими темпами (примерно на 7% в год). В то же время производительность процессоров начиная с 1987 года практически увеличивалась на 50% в год. В таб. № 4.5 представлены основные временные параметры различных поколений ДЗУПВ.

Очевидно, согласование производительности современных процессоров со скоростью основной памяти вычислительных систем остается на сегодняшний день одной из важнейших проблем. Приведенные в предыдущем разделе методы повышения производительности за счет увеличения размеров кэш-памяти и введения многоуровневой организации кэш-памяти могут оказаться не достаточно эффективными с точки зрения стоимости систем. Поэтому важным направлением современных разработок являются методы повышения полосы пропускания или пропускной способности памяти за счет ее организации, включая специальные методы организации ДЗУПВ.

Таб. № 4.5

Временные параметры ДЗУП

Год появления

Емкость крист.

Длительность RAS

Длительность CAS Время цикла Оптимизированный режим

 

 

max

min  

1980
1983
1986
1989
1992
1997

64 Кбит
256 Кбит
1 Мбит
4 Мбит
16 Мбит
64 Мбит

180 нс
150 нс
120 нс
100 нс
80 нс
65 нс

150 нс
120 нс
100 нс
80 нс
60 нс
45 нс 75 нс
50 нс
25 нс
20 нс
15 нс
10 нс 250 нс
220 нс
190 нс
165 нс
120 нс
100 нс 150 нс
100 нс
50 нс
40 нс
30 нс
20 нс

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

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

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

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

Примером организации широкой основной памяти является система Alpha AXP 21064, в которой кэш второго уровня, шина памяти и сама память имеют разрядность в 256 бит.

4.2.1.Память с расслоением. Наличие в системе множества микросхем памяти позволяет использовать потенциальный параллелизм, заложенный в такой организации. Для этого микросхемы памяти часто объединяются в банки или модули, содержащие фиксированное число слов, причем только к одному из этих слов банка возможно обращение в каждый момент времени. Как уже отмечалось, в реальных системах имеющаяся скорость доступа к таким банкам памяти редко оказывается достаточной . Следовательно, чтобы получить большую скорость доступа, нужно осуществлять одновременный доступ ко многим банкам памяти. Одна из общих методик, используемых для этого, называется расслоением памяти. При расслоении банки памяти обычно упорядочиваются так, чтобы N последовательных адресов памяти i, i+1, i+2, ..., i+ N-1 приходились на N различных банков. В i-том банке памяти находятся только слова, адреса которых имеют вид kN + i (где 0 ( k ( M-1, а M число слов в одном банке). Можно достичь в N раз большей скорости доступа к памяти в целом, чем у отдельного ее банка, если обеспечить при каждом доступе обращение к данным в каждом из банков. Имеются разные способы реализации таких расслоенных структур. Большинство из них напоминают конвейеры, обеспечивающие рассылку адресов в различные банки и мультиплексирующие поступающие из банков данные. Таким образом, степень или коэффициент расслоения определяют распределение адресов по банкам памяти. Такие системы оптимизируют обращения по последовательным адресам памяти, что является характерным при подкачке информации в кэш-память при чтении, а также при записи, в случае использования кэш-памятью механизмов обратного копирования. Однако, если требуется доступ к непоследовательно расположенным словам памяти, производительность расслоенной памяти может значительно снижаться.

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

Если система памяти разработана для поддержки множества независимых запросов (как это имеет место при работе с кэш-памятью, при реализации многопроцессорной и векторной обработки), эффективность системы будет в значительной степени зависеть от частоты поступления независимых запросов к разным банкам. Обращения по последовательным адресам, или в более общем случае обращения по адресам, отличающимся на нечетное число, хорошо обрабатываются традиционными схемами расслоенной памяти. Проблемы возникают, если разница в адресах последовательных обращений четная. Одно из решений, используемое в больших компьютерах, заключается в том, чтобы статистически уменьшить вероятность подобных обращений путем значительного увеличения количества банков памяти. Например, в суперкомпьютере NEC SX/3 используются 128 банков памяти. Подобные проблемы могут быть решены как программными, так и аппаратными средствами.

4.2.2.Использование специфических свойств динамических ЗУПВ

Как упоминалось раньше, обращение к ДЗУПВ состоит из двух этапов: обращения к строке и обращения к столбцу. При этом внутри микросхемы осуществляется буферизация битов строки, прежде чем происходит обращение к столбцу. Размер строки обычно является корнем квадратным от емкости кристалла памяти: 1024 бита для 1Мбит, 2048 бит для 4 Мбит и т.д. С целью увеличения производительности все современные микросхемы памяти обеспечивают возможность подачи сигналов синхронизации, которые позволяют выполнять последовательные обращения к буферу без дополнительного времени обращения к строке. Имеются три способа подобной оптимизации:

  •  блочный режим (nibble mode) - ДЗУВП может обеспечить выдачу четырех последовательных ячеек для каждого сигнала RAS.
  •  страничный режим (page mode) - Буфер работает как статическое ЗУПВ; при изменении адреса столбца возможен доступ к произвольным битам в буфере до тех пор, пока не поступит новое обращение к строке или не наступит время регенерации.
  •  режим статического столбца (static column) - Очень похож на страничный режим за исключением того, что не обязательно переключать строб адреса столбца каждый раз для изменения адреса столбца.

Начиная с микросхем ДЗУПВ емкостью 1 Мбит, большинство ДЗУПВ допускают любой из этих режимов, причем выбор режима осуществляется на стадии установки кристалла в корпус путем выбора соответствующих соединений. Эти операции изменили определение длительности цикла памяти для ДЗУВП. Преимуществом такой оптимизации является то, что она основана на внутренних схемах ДЗУПВ и незначительно увеличивает стоимость системы, позволяя практически учетверить пропускную способность памяти. Например, nibble mode был разработан для поддержки режимов, аналогичных расслоению памяти. Кристалл за один раз читает значения четырех бит и подает их наружу в течение четырех оптимизированных циклов. Если время пересылки по шине не превосходит время оптимизированного цикла, единственное усложнение для организации памяти с четырехкратным расслоением заключается в несколько усложненной схеме управления синхросигналами. Страничный режим и режим статического столбца также могут использоваться, обеспечивая даже большую степень расслоения при несколько более сложном управлении. Одной из тенденций в разработке ДЗУПВ является наличие в них буферов с тремя состояниями. Это предполагает, что для реализации традиционного расслоения с большим числом кристаллов памяти в системе должны быть предусмотрены буферные микросхемы для каждого банка памяти.

Новые поколения ДЗУВП разработаны с учетом возможности дальнейшей оптимизации интерфейса между ДЗУПВ и процессором. В качестве примера можно привести изделия компании RAMBUS. Эта компания берет стандартную начинку ДЗУПВ и обеспечивает новый интерфейс, делающий работу отдельной микросхемы более похожей на работу системы памяти, а не на работу отдельного ее компонента. RAMBUS отбросила сигналы RAS/CAS, заменив их шиной, которая допускает выполнение других обращений в интервале между посылкой адреса и приходом данных. (Такого рода шины называются шинами с пакетным переключением (packet-switched bus) или шинами с расщепленными транзакциями (split-traнсaction bus), которые будут рассмотрены в других главах. Такая шина позволяет работать кристаллу как отдельному банку памяти. Кристалл может вернуть переменное количество данных на один запрос и даже самостоятельно выполняет регенерацию. RAMBUS предлагает байтовый интерфейс и сигнал синхронизации, так что микросхема может тесно синхронизироваться с тактовой частотой процессора. После того, как адресный конвейер наполнен, отдельный кристалл может выдавать по байту каждые 2 нсек.

Большинство систем основной памяти используют методы, подобные страничному режиму ДЗУПВ, для уменьшения различий в производительности процессоров и микросхем памяти.

4.2.3.Виртуальная память и организация защиты памяти

4.2.3.1.Концепция виртуальной памяти. Общепринятая в настоящее время концепция виртуальной памяти появилась достаточно давно. Она позволила решить целый ряд актуальных вопросов организации вычислений. Прежде всего к числу таких вопросов относится обеспечение надежного функционирования мультипрограммных систем.

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

Другой вопрос, тесно связанный с реализацией концепции виртуальной памяти, касается организации вычислений на компьютере задач очень большого объема. Если программа становилась слишком большой для физической памяти, часть ее необходимо было хранить во внешней памяти (на диске) и задача приспособить ее для решения на компьютере ложилась на программиста. Программисты делили программы на части и затем определяли те из них, которые можно было бы выполнять независимо, организуя оверлейные структуры, которые загружались в основную память и выгружались из нее под управлением программы пользователя. Программист должен был следить за тем, чтобы программа не обращалась вне отведенного ей пространства физической памяти. Виртуальная память освободила программистов от этого бремени. Она автоматически управляет двумя уровнями иерархии памяти: основной памятью и внешней (дисковой) памятью.

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

Системы виртуальной памяти можно разделить следующие классы:

1) Страничная память. Системы с фиксированным размером блоков, называемых страницами;

2) Сегментная и сегментно-страничная организации памяти. Системы с переменным размером блоков, называемых сегментами.

4.2.3.2.Страничная организация памяти. В системах со страничной организацией основная и внешняя память (главным образом дисковое пространство) делятся на блоки или страницы фиксированной длины. Каждому пользователю предоставляется некоторая часть адресного пространства, которая может превышать основную память компьютера и которая ограничена только возможностями адресации, заложенными в системе команд. Эта часть адресного пространства называется виртуальной памятью пользователя. Каждое слово в виртуальной памяти пользователя определяется виртуальным адресом, состоящим из двух частей: старшие разряды адреса рассматриваются как номер страницы, а младшие - как номер слова (или байта) внутри страницы.

Управление различными уровнями памяти осуществляется программами ядра операционной системы, которые следят за распределением страниц и оптимизируют обмены между этими уровнями. При страничной организации памяти смежные виртуальные страницы не обязательно должны размещаться на смежных страницах основной физической памяти. Для указания соответствия между виртуальными страницами и страницами основной памяти операционная система должна сформировать таблицу страниц для каждой программы и разместить ее в основной памяти машины. При этом каждой странице программы, независимо от того находится ли она в основной памяти или нет, ставится в соответствие некоторый элемент таблицы страниц. Каждый элемент таблицы страниц содержит номер физической страницы основной памяти и специальный индикатор. Единичное состояние этого индикатора свидетельствует о наличии этой страницы в основной памяти. Нулевое состояние индикатора означает отсутствие страницы в оперативной памяти.

Для увеличения эффективности такого типа схем в процессорах используется специальная полностью ассоциативная кэш-память, которая также называется буфером преобразования адресов (TLB traнсlation-lookaside buffer). Хотя наличие TLB не меняет принципа построения схемы страничной организации, с точки зрения защиты памяти, необходимо предусмотреть возможность очистки его при переключении с одной программы на другую.

Поиск в таблицах страниц, расположенных в основной памяти, и загрузка TLB может осуществляться либо программным способом, либо специальными аппаратными средствами. В последнем случае для того, чтобы предотвратить возможность обращения пользовательской программы к таблицам страниц, с которыми она не связана, предусмотрены специальные меры. С этой целью в процессоре предусматривается дополнительный регистр защиты, содержащий описатель (дескриптор) таблицы страниц или базово-граничную пару. База определяет адрес начала таблицы страниц в основной памяти, а граница - длину таблицы страниц соответствующей программы. Загрузка этого регистра защиты разрешена только в привилегированном режиме. Для каждой программы операционная система хранит дескриптор таблицы страниц и устанавливает его в регистр защиты процессора перед запуском соответствующей программы.

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

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

4.2.3.3. Сегментная организации памяти. При сегментной организации виртуальный адрес по-прежнему является двумерным и состоит из двух полей - номера сегмента и смещения внутри сегмента.   Заметим, что с точки зрения ОС сегменты являются логическими сущностями и их главное назначение хранение и защита однородной информации (кода, данных и т.д.). С точки зрения пользователя  процесс представляется обычно не как линейный массив байтов, а как набор сегментов переменного размера (данные, код, стек).  Сегментация - схема управления памятью, поддерживающая этот взгляд пользователя.  Сегменты содержат процедуры, массивы, стек или скалярные величины, но обычно не содержат информацию смешанного типа.  Программисты, пишущие на языках низкого уровня должны иметь представление о сегментной организации, явным образом меняя значения сегментных регистров (это хорошо видно по текстам программ, написанных на Ассемблере). Логическое адресное пространство - набор сегментов. Каждый сегмент имеет имя, размер и другие параметры (уровень привилегий, разрешенные виды обращений, флаги присутствия). Пользователь специфицирует каждый адрес двумя величинами: именем сегмента и смещением. (В отличие от схемы пэйджинга, где пользователь задает только один адрес, который разбивается hardware на номер страницы и смещение,  прозрачным для программиста образом.)

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

Логический адрес  - упорядоченная пара v=(s,d), номер сегмента и смещение внутри сегмента.

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

Рис. 4.1  Преобразование  логического адреса при сегментной организации памяти.

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

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

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

Рис. 4.2  Формирование физического адреса при сегментно-страничной организации памяти.

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

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

Итак, виртуальный адрес состоит из виртуального номера страницы (high-order bits) и смещения (low-order bits). Номер виртуальной страницы используется как индекс в таблице страниц для нахождения  записи (entry) о виртуальной странице.  Из этой записи в таблице страниц находится  номер кадра (page frame number), затем прибавляется  смещение и формируется  физический адрес.  Помимо этого запись  в таблице страниц содержит информацию об атрибутах страницы, в частности биты защиты.

Основную проблему для эффективной реализации таблицы страниц создают большие размеры виртуальных адресных пространств современных компьютеров, которые обычно определяются разрядностью архитектуры процессора. Самыми распространенными на сегодняшний день являются 32-разрядные процессоры, позволяющие создавать виртуальные адресные пространства такого размером 4 Гб (для 64-разрядных компьютеров эта величина равна 2**64б).

Подсчитаем примерный размер таблицы страниц. В 32-битном адресном  пространстве при размере страницы 4К  (Intel) получаем  1М страниц, а в 64-битном и того более. Т.о. таблица должна иметь 1М строк (entry), причем  запись в строке состоит  из нескольких байт.  Заметим, что каждый процесс, нуждается  в своей таблице страниц (а в случае сегментно-страничной схемы  по одной на каждый сегмент). Итак,  в этом случае таблица страниц может быть слишком большой.

Кроме того, отображение  должно быть быстрым. Отображение должно быть быстрым  т.к. оно делается при каждом обращении к памяти, которое происходи практически в каждой машинной инструкции. Эта проблема решается главным образом за счет реализации ассоциативной памяти. Для того чтобы избежать необходимости  иметь огромную таблицу в памяти все время, а хранить лишь несколько ее фрагментов (это возможно опять же на основании свойства локальности!), многие компьютеры  используют многоуровневую таблицу страниц.

Рассмотрим модельный пример (см. рис. 4.3). Предположим, что  32-разрядный  адрес делится на 10-разрядное поле Рtr1, 10-разрядное поле Рtr2 и 12-разрядное смещение Offset. 12 разрядов смещения позволяют локализовать байт внутри страницы размером 4К (2**12), а всего имеем 2**20 страниц.  Как видно из рис. 9.4  1024 строки в  таблице верхнего уровня при помощи поля Ptr1 ссылаются на 1024  таблицы второго уровня, каждая из которых содержит  также 1024 строки. При помощи поля Ptr2  каждая строка  таблицы второго уровня указывает на  конкретную страницу. Смысл такой организации в том, чтобы  избежать поддержки всех таблиц второго уровня (а их 1024) в памяти  постоянно.  Рассмотрим  пример с круглыми цифрами.  Допустим, что процессу нужны 12М памяти: 4М в нижней части памяти для кода, 4М в нижней части для данных и 4М в верхней части памяти для стека. Между дном стека и верхом данных гигантское пространство  размером 4Gb-12Mb, которое  не используется.  Для этого случая необходимы лишь 1 таблица верхнего уровня и 3 таблицы второго уровня.

Такой подход естественным  образом обобщается на три и более уровней таблицы.

Рассмотрим  одну  из  записей  таблицы страниц. Ее размер колеблется от системы к системе, но 32 бита - наиболее общий случай. Самое важное поле - номер кадра.  Цель страничного отображения - локализовать эту величину.  Далее бит присутствия.  Далее биты защиты (например,  0 - read/write, 1 - read only ...) Есть еще биты модификации (если на нее писали) и биты ссылки, которые  помогают выделить мало используемые страницы, биты разрешающие кэширование. Заметим, что адреса страниц на диске не являются частью таблицы страниц.

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

                             Рис. 4.3.  Пример двухуровневой таблицы страниц.

Количество уровней в таблице страниц зависит от конкретных особенностей архитектуры. Можно привести примеры реализации одноуровневого (DEC PDP-11), двухуровневого (Intel, DEC VAX), трехуровневого (Sun SPARC, DEC Alpha) paging'а, а также paging'а с задаваемым количеством уровней (Motorola). Функционирование RISC процессора MIPS R2000 осуществляется вообще без таблицы страниц. Здесь поиск нужной страницы, если  эта страница отсутствует в ассоциативной памяти, должна взять на себя ОС (так называемый zero level paging).

4.3. Ассоциативная память.

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

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

Естественное решение -  снабдить компьютер  аппаратным устройством для отображения виртуальных  страниц в физические без обращения к таблице страниц,  то есть иметь небольшую, быструю  кэш-память,  хранящую необходимую на данный момент часть таблицы страниц.  Это устройство называется ассоциативная память,  иногда также употребляют термин ассоциативные регистры (иногда translation lookaside buffer (TLB)).

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

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

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

Рассмотрим  функционирование менеджера памяти при наличии ассоциативной памяти. Вначале  он  ищет виртуальную  страницу в ассоциативной памяти. Если  страница найдена - все нормально  за исключением случаев нарушения привилегий, когда запрос на обращение к памяти отклоняется.

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

Процент раз, когда номер страницы находится в ассоциативной памяти, называется hit (совпадение) ratio (пропорция, отношение). Таким образом, hit ratio - часть ссылок, которая  может быть сделана с использованием  ассоциативной памяти. Обращение к одним и тем же страницам повышает hit ratio.

Например,  предположим, что для доступа к таблице страниц необходимо 100 нс, а для доступа к ассоциативной  памяти 20 нс. С 90% hit ratio среднее  время доступа - 0.9*20+0.1*100 = 28 нс.

Вполне приемлемая производительность современных ОС доказывает эффективность использования ассоциативной памяти.  Высокое значение вероятности нахождения данных в ассоциативной памяти связано с наличием у данных объективных свойств: пространственной и временной локальности.

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

4.5 Иерархия памяти

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

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

.

                                    Рис.4.4  Иерархия памяти компьютера

Считается, что затраты, связанные с переписью информации из одной памяти в другую окажутся меньше выигрыша в быстродействии, который получается за счет сокращения времени выборки из более быстрых слоев памяти. Информация о странице, которая находится в памяти верхнего уровня, хранится также на уровнях с большими номерами. Если процессор не обнаруживает нужную страницу на i-м уровне, он начинает искать ее на  последующих уровнях. Когда нужная страница найдена, она переносится в более быстрые уровни. При этом происходит вытеснение какой-то старой страницы, обычно той, которая дольше всего не использовалась. Идея состоит в том, чтобы те страницы, которые чаще всего нужны в настоящее время, находились в более быстрых частях памяти. Эффективность такой схемы обусловлена все тем же свойством локальности (подробнее о локальности и связанным с ним понятием рабочего множества страниц будет рассказано в следующей главе). В результате среднее время доступа для многоуровневой схемы памяти оказывается весьма близким ко времени доступа первого уровня.

4.6  Размер страницы

Дизайнеры ОС для существующих машин редко имеют возможность влиять на размер страницы.  Однако для вновь создаваемых компьютеров решение относительно оптимального размера страницы является актуальным. Как и можно было ожидать нет одного наилучшего размера. Скорее есть набор факторов, влияющих на размер. Обычно размер страницы это степень двойки от 2**9 до 2**14 байт.

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

Как следует выбирать размер страницы?  Во-первых, нужно учитывать размер таблицы страниц,  здесь желателен большой размер страницы (страниц меньше, соответственно и таблица страниц меньше).  С другой стороны память лучше утилизируется с маленьким размером страницы. В среднем половина последней страницы процесса пропадает. Необходимо также учитывать объем ввода-вывода для взаимодействия с внешней памятью и другие факторы. Проблема не имеет хорошего ответа.  Историческая тенденция состоит в увеличении размера страницы. Как правило, размер страниц задается аппаратно, например, на Intel - это 4096 байт (или 4 Кбайт), на DEC PDP-11 - 8 Кбайт, на DEC VAX - 512 байт, на других архитектурах, таких как Motorola 68030, размер страниц может быть задан программно.

Итак, нами рассмотрены аппаратные особенности поддержки виртуальной памяти.

7) КЭШ 2-го уровня.  Система памяти персонального компьютера состоит обычно из под системного ОЗУ (опер. запоминающее устройство) и факультативного внешнего КЭШа процессора называемого так же КЭШ 2-го уровня или L2.  

6). Системная плата:

1) Связывает между собой:

- один или несколько процессоров и оперативную память;

- одну или множество стандартных шин ввода/вывода, размещенных на корпусею.

2) Обеспечивает:

- поддержкой технологии дисков и дисковых массивов RAID;

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

Например, локальная шина PCI (peripheral component Interconnect- межсоединение периферийных компонентов).  Первое и главное преимущество шины PCI заключается в том что, она обеспечивает   быстродействие РС, не перегружает центральный процессор. Практически она позволяет осуществлять передачу больших объемов данных со скоростью в 10 раз выше предельной скорости системы ISA.ISA ( Industry Standard architecture).

Суперсерверы, как правило, работают под управлением операционных систем UNIX, Windows NT, Windows  2000/2003 Server, которые обеспечивают многопотоковую многопроцессорную и многозадачную обработку. Суперсерверы должны иметь достаточные возможности наращивания дискового пространства и вычислительной мощности, средства обеспечения надежности

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

Мост/контроллер памяти предназначен  для того, чтобы отделить локальную шину CPU от шины PCI.

DRAM - динамическая память. . В настоящее время трудно найти конфигурацию с объёмом памяти менее 128 Мб. Для нормальной работы большинства программных продуктов желательно иметь хотя бы 256 Мб памяти.

Встроенная электроника канала IDE- это устройство для подключения магнитных дисков.

Интерфейс шины расширения предназначен для соединения шины ISA (EISA) с шиной PCI

Шина ISA (EISA) – устройство для подключения периферийных устройств к  компьютеру.

Рис. 4.5. Архитектура персонального компьютера и взаемодействие устройств

Дисковод для гибких дисков. Существует два стандарта : 5.25” и 3.5”. На сегодняшний день большинство компьютеров поставляется с дисководом 3.5”.

Жёсткий диск Начав своё шествие с объема в 5 МБ, достиг небывалых высот. На сегодняшний день не удивят диски объёмом 40 Гб, 60 Гб, 100 Гб и выше  Гб . Следует придать значение не только емкости диска, но и его временным характеристикам.

4.7  Комбінаційні схеми та цифрові автомати.

4.7.1. Комбинационные схемы - это цифровые автоматы с одним состоянием. Все устройства с памятью - это конечные цифровые автоматы. Любой микроконтроллер и микропроцессор - это цифровой автомат с гигантским числом состояний, переходы в котором определяются внешней программой. Любой компьютер также представляет из себя цифровой автомат с еще большим числом состояний. Что же такое простейший "цифровой автомат"? Прежде всего, это цифровое устройство. Следовательно, оно базируется на двоичной логике. Если оно базируется на двоичной логике, все устройство может быть описано булевыми функциями - дизъюнкии конъюнкций. Действия выполняются над некоторыми операндами. Значит, цифровой автомат - это устройство, которое обрабатывает входные данные. Таким образом, цифровой автомат может быть описан следующим образом:

     (4.7.1)

Где,  X - набор входных значений, f ( X ) - их обработка, Y - результат. Графически это может быть изображено следующим образом:

Рис. 4.6 Схема работы цифрового автомата

Таким образом можно описать работу компараторов, мультиплексоров, элементов "И", "ИЛИ", простых преобразователей кода.

Но существует большой класс устройств, которым требуется менять свое поведение в течении времени. Фактически, это любой непростейший алгоритм. Очевидно, формулы (4.7.1) уже недостаточно, так как там отсутствует параметр времени.

"Менять поведение" в цифровой технике называется "менять свое состояние". Что такое состояние? Это те элементы устройства, которые меняются со временем. Следовательно, это элементы памяти. В простых случаях это набор триггеров. В сложном случае (компьютер, например) это набор регистров, значение всех элементов памяти и внешние запоминающие устройства. Состоянием называется комбинация всех таких элементво памяти. Для описания всех состяний компьютера нужно учесть все запоминающие устройства. Наличие памяти создает обратные связи в устройстве (см. рис. 4.7.), которые определяют переход в новое состояние. Функция переходов определяется следующей формулой:

   (4.7. 2)

Рис. 4.7 Схема работы цифрового автомата с памятью

 

Состояние a зависит от времени t и текущего значения входных воздействий x ( t ). Интерес представляет текущее время t. Строго говоря, оно измеряется в секундах (точнее, в наносекундах). Используя это время, мы можем разграничить сосдение состояния:

Рис. 4.8  Переключение состояний

 Как видно из рисунка 4.8., некоторое время tст цифровое устройство пребывает в состоянии at. Однако потом за время tпер изменяется значение регистра памяти. Это время зависит от времени распространения сигнала внутри схемы и от быстродействия элементов памяти и логики. В это время автомат находится в практически непредсказуемом состоянии. Естественно, в это время значение выходов будет непредсказуемо. Этот промежуток времени весьма мал. Поэтому им обычно пренебрегают и условно считают нулевым (по крайней мере, его не рассматривают при моделировании схемы). Следовательно, если мы вычеркнем промежутки времени tпер, мы получим набор вполне дискретных состояний устройства. Важно ли нам будет знать физическое значение времени? Нет. Поэтому в рассмотрение берется некое условное время 0, 1, 2,. В какой момент времени происходит смена состояния устройства? Обычно это некоторый внешний сигнал. Говорят, что он "тактирует" работу устройства, "синхронизирует" смену его состояний (действительно, смена состояний происходит синхронно по всему устройству). Поэтому этот сигнал называют "тактом синхроимпульса". Для его реализации обычно делают генератор прямоугольных импульсов.

Итак, резюмируем (рис. 4.9). Цифровое устройство обрабатывает входные сигналы X по закону f ( X ) и выдает результат Y. При наличии элементов памяти изменяется состояние устройства a по закону . Смена состояний инициируется внешним сигналом c.

 

 

Рис. 4.9. Поведение цифрового устройства

4.7.2.Последовательный цифровой автомат - математическая модель. Цифровое устройство, оно же в нашем случае цифровой автомат описывается рядом множеств: множество входных воздействий X, множество выходных сигналов Y и множество состояний A. Множество входных воздействий - это набор всевозможных комбинаций, число которых определяется разрядностью входного слова. Все возможные входные слова образуют входной алфавит. Возможны ситуации (да так оно на практике, в основном, и происходит), когда используется не весь входной алфавит.

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

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

Из всех возможных значений важно выделить то состояние, в которое попадает автомат в первый раз. Как правило, включение питания вводит автомат в некоторое непредсказуемое состояние. Поэтому вводится внешний сигнал сброса, который переводит автомат в четко определенное состояние. Это состояние называется "начальным" и обычно обозначается a0 (или a1 - так более классически).

Помимо этих множеств необходимо указать две функции - функцию переходов и функцию выходов.

(4.7.2)

Функцию переходов (4.7.2) мы уже проанализировали. Функция выходов описывает значение выходов в зависимости от текущего состояния и текущих входных параметров:

(4.7.3)

Из формулы (4.7.3) возможны 4 частных случая - 1) автомат зависит от состояния и входов, 2) зависит только от состояния, 3) зависит только от входов и 4) вообще ни от чего не зависит. 3-ий случай - это комбинационная логика. 2-ой случай получил название автомата Мура. 1-ый случай - автомат Мили. 4-ый случай - генератор константы.

4.8.Итак, математическая модель классического цифрового автомата описывается следующей системой:

                      (4.8.1)

                                                        

                   (4.8.2)

                    (4.8.3)

                                        (4.8.4)

 

                  (4.8.5)                                                            

          (4.8.6)

                                                     (4.8.7)

В этом множестве формула ((4.8.1)) описывает множество входных слов, ((4.8.2)) - множество выходных сигналов, ((4.8.3)) - множество состояний, ((4.8.4)) - начальное состояние, ((4.8.5)) - функцию переходов, ((4.8.6)) - функцию выходов, ((4.8.7)) - дискретность работы во времени.

4.9.Параллельный цифровой автомат. Добавим параллелизм в конечный цифровой автомат(КЦА), за сщет изменения в системе (4.8) и без разрушения целостности с сохранением автомата как черного ящика неизменным. При этом, цифровой автомат как черный ящик поменяться не должен. То есть замена КЦА на эквивалентный ему ПЦА и наоборот должна быть снаружи незаметной (под "эквивалентностью" в данном случае понимается выполнение тех же самых функций) - интерфейс меняться не должен. Следовательно, множества (4.8.1) и (4.8.2) не меняются.

Не меняется концепция ПЦА как цифрового устройства с множеством состояний. Значит, (4.8.3) тоже не меняется.

Не меняется концепция дискретной смены времени - (4.8.7) не меняется. Если подумать, параллелизм в данном случае подразумевает наличие множества активных в данный момент состояний в отличие от одного активного у КЦА. Значит, изменяются уравнения (4.8.4), (4.8.5) и (4.8.6), где активно одно состояние.

Интерфейс цифрового автомата.

                    (4.9.1)

        (4.9.2)

 (4.9.3)

Что означает (4.9.1)? Это означает, что в начальный момент времени могут быть активными несколько состояний одновременно. (4.9.2) означает зависимость множества одновременно активных состояний в данный момент времени от множества активных в предыдущий дискретный момент времени и входных сигналов. (6.3) означает зависимость выходных значений от множества одноврмененно активных состояний и входных сигналов.

Изменяет ли система (4.9) интерфейс цифрового автомата? Очевидно, что нет, так как интерфейс ограничен множествами (4.8.1) и (4.8.2).

Смена состояний производится одновременно (уравнение (4.9.2)). По сигналу внешнего сброса автомат переходит в некоторое множество начальных состояний (уравнение (4.9.1)).

4.10.Итак, получена модель ПЦА. Добавление системы (4.9) в систему (4.8), а также несколько необходимых переобозначений дают нам математическую модель ПЦА:

           4.10.1

           4.10.2

           4.10.3

                                4.10.4

              4.10.5

4.10.6

 4.10.7

  4.10.8

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

Учитывая это, данную модель будем называть "абстрактной математической моделью".

4.11.Базові логічні елементи "не",   "и",   "или",  "если... , то".

4.11.1. Употребляемые в обычной речи слова и словосочетания "не",   "и",   "или",  "если... , то",   "тогда и только тогда" и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются   логическими связками. 

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

Так, например, из элементарных высказываний "Петров — врач", "Петров — шахматист" при помощи связки "и" можно получить составное высказывание "Петров — врач и шахматист", понимаемое как "Петров — врач, хорошо играющий в шахматы".

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

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание "Комп’ютер делает вычисление", а через В — высказывание "Комп’ютер работает в сети ",. Тогда составное высказывание   «Комп’ютер делает вычисление и  работает в сети»  можно кратко записать как     А и В.  Здесь   "и"  — логическая связка,   А,   В   — логические переменные, которые мoгут принимать только два значения —   "истина"   или   "ложь",  обозначаемые, соответственно,   "1"  и   "0".

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

НЕ    Операция, выражаемая словом "не", называется отрицанием и обозначается чертой над высказыванием (или знаком ).   Высказывание истинно, когда A ложно, и ложно, когда A истинно.   Пример. "Алгоритм — последовательность выполнения операций" (А); " Алгоритм — последовательность выполнения сложения " ().

И    Операция, выражаемая связкой "и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой " . " (может также обозначаться знаками или &). Высказывание А . В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание   "10 делится на 2 и 5 больше 3"   истинно, а высказывания     "10 делится на 2 и 5 не больше 3",     "10 не делится на 2 и 5 больше 3",     "10 не делится на 2 и 5 не больше 3"     —   ложны.

ИЛИ    Операция, выражаемая связкой "или" (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.   Например, высказывание   "10 не делится на 2 или 5 не больше 3"   ложно,     а высказывания "10 делится на 2 или 5 больше 3",   "10 делится на 2 или 5 не больше 3",   "10 не делится на 2 или 5 больше 3"     —   истинны.

ЕСЛИ-ТО   Операция, выражаемая связками   "если ..., то",  "из ... следует",  "... влечет ...",  называется импликацией (лат. implico — тесно связаны) и обозначается знаком . Высказывание   ложно тогда и только тогда, когда  А  истинно,  а  В  ложно.

Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: "данный четырёхугольник — квадрат" (А) и "около данного четырёхугольника можно описать окружность" (В). Рассмотрим составное высказывание  , понимаемое как "если данный четырёхугольник квадрат, то около него можно описать окружность". Есть три варианта, когда высказывание   истинно:

А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;

А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);

A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность.

Ложен только один вариант, когда А истинно, а В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

В обычной речи связка   "если ..., то" описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться "бессмысленностью" импликаций, образованных высказываниями, совершенно не связанными по содержанию.   Например, такими: "если президент США — демократ, то в Африке водятся жирафы",   "если арбуз — ягода, то в бензоколонке есть бензин". 

РАВНОСИЛЬНО   Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией или двойной импликацией и обозначается знаком    или  ~.   Высказывание  истинно тогда и только тогда, когда значения А и В совпадают.       Например, высказывания     "24 делится на 6 тогда и только тогда, когда 24 делится на 3",    "23 делится на 6 тогда и только тогда, когда 23 делится на 3"   истинны,   а высказывания   "24 делится на 6 тогда и только тогда, когда 24 делится на 5",   "21 делится на 6 тогда и только тогда, когда 21 делится на 3"   ложны.

Высказывания А и В, образующие составное высказывание , могут быть совершенно не связаны по содержанию, например:     "три больше двух" (А),     "пингвины живут в Антарктиде" (В). Отрицаниями этих высказываний являются высказывания   "три не больше двух" (),   "пингвины не живут в Антарктиде" ().   Образованные из высказываний А и В составные высказывания A B     и       истинны, а высказывания   A   и    B — ложны.

Итак, нами рассмотрены пять логических операций: отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция. 

Импликацию можно выразить через  дизъюнкцию  и  отрицание:

А В = v В.

 Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

А В = (v В) . (v А).

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

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

4.11.2. Логическая формула.

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

Определение логической формулы:

Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") — формулы.

Если  А и В — формулы,   то   ,   А . В ,   А v В ,   А B ,   А В   —  формулы.

Никаких других формул в алгебре логики нет.

В п. 4.11.1 определены элементарные формулы; в п. 4.11.2 даны правила образования из любых данных формул новых формул. 

В качестве примера рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Это высказывание формализуется в виде (A v B) C. Такая же формула соответствует высказыванию   "если Игорь знает английский или японский язык, то он получит место переводчика". 

Как показывает анализ формулы (A v B) C, при определённых сочетаниях значений переменных A, B и C она принимает значение "истина", а при некоторых других сочетаниях — значение "ложь" (разберите самостоятельно эти случаи). Такие формулы называются выполнимыми.

Некоторые формулы принимают значение "истина" при любых значениях истинности входящих в них переменных. Таковой будет, например, формула А v , соответствующая высказыванию "Этот треугольник прямоугольный или косоугольный". Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называются тождественно истинными формулами или тавтологиями. Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями. 

В качестве другого примера рассмотрим формулу А . , которой соответствует, например, высказывание "Катя самая высокая девочка в классе, и в классе есть девочки выше Кати". Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями. 

Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.

Равносильность двух формул алгебры логики обозначается символом "=" или символом "" Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

4.11..3. Какая связь между алгеброй логики и двоичным кодированием?

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: “1” и “0”.

Из этого следует два вывода:

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

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

4.11.4. В каком виде записываются в памяти компьютера и в регистрах процессора данные и команды?

Данные и команды представляются в виде двоичных последовательностей различной структуры и длины. Существуют различные физические способы кодирования двоичной информации. Мы уже рассмотрели способы записи двоичной информации на магнитных дисках и на CD-ROM. В электронных устройствах компьютера двоичные единицы чаще всего кодируются более высоким уровнем напряжения, чем двоичные нули (или наоборот), например:
 

4.11.5. Что такое логический элемент компьютера?

Логический элемент компьютера — это часть электронной логичеcкой схемы, которая реализует элементарную логическую функцию.

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ и другие (называемые также вентилями), а также триггер. 

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

Чтобы представить два логических состояния — “1” и “0” в вентилях, соответствующие им входные и выходные сигналы имеют один из двух установленных уровней напряжения. Например, +5 вольт и 0 вольт.

Высокий уровень обычно соответствует значению “истина” (“1”), а низкий — значению “ложь” (“0”).

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

Работу логических элементов описывают с помощью таблиц истинности.

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

4.11.6. Что такое   схемы  И,  ИЛИ,  НЕ,  И—НЕ,  ИЛИ—НЕ?

 

С х е м а   И

Схема И реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах схемы И с двумя входами представлено на рис. 4.111.


 
             
    Рис. 4.11.1

Таб. №4.6

                               

Таблица истинности схемы И

X

y

x . y

0

0

0

0

1

0

1

0

0

1

1

1

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом  z  этой схемы и входами  x  и  y  описывается соотношением:   z = x . y (читается как "x и y"). Операция конъюнкции на структурных схемах обозначается знаком  "&"  (читается как "амперсэнд"),  являющимся сокращенной записью английского слова  and.

С х е м а   ИЛИ

Схема  ИЛИ  реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы  ИЛИ  будет единица, на её выходе также будет единица.

Условное обозначение на структурных схемах схемы ИЛИ с двумя входами представлено на рис.     Рис. 4.11..2.   Знак "1" на схеме — от устаревшего обозначения дизъюнкции как   ">=1"  (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1).    Связь между выходом  z  этой схемы и входами  x  и  y   описывается соотношением:  z = x v y  (читается как "x или y").


 
                 
Рис. 4.11.2

Таб. №4.7

Таблица истинности схемы ИЛИ

X

y

x v y

0

0

0

0

1

1

1

0

1

1

1

1


 

С х е м а   НЕ

Схема   НЕ  (инвертор) реализует операцию отрицания.  Связь между входом   x  этой схемы и выходом   z  можно записать соотношением   z = , x где     читается как   "не x"   или  "инверсия х".

Если на входе схемы  0,  то на выходе  1.  Когда на входе  1,  на выходе  0.  Условное обозначение на структурных схемах инвертора — на рисунке 5.3


 
                  Рис.
    Рис. 4.11.3

Таб. №4.8

Таблица истинности схемы НЕ

x

0

1

1

0

С х е м а   И—НЕ

Схема И—НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом z и входами x и y схемы записывают следующим образом: , где     читается как   "инверсия x и y".   Условное обозначение на структурных схемах схемы   И—НЕ  с двумя входами представлено на   Рис. 4.11.4


 
                 

Рис. 4.11.4

Таб. №4.9

Таблица истинности схемы И—НЕ

X

y

0

0

1

0

1

1

1

0

1

1

1

0

С х е м а   ИЛИ—НЕ

Схема ИЛИ—НЕ состоит из элемента ИЛИ и инвертора  и осуществляет отрицание результата схемы ИЛИ.     Связь между выходом  z  и входами  x  и  y  схемы записывают следующим образом:  ,  где  ,  читается как  "инверсия  x или y ". Условное обозначение на структурных схемах схемы ИЛИ—НЕ с двумя входами представлено на рис.     Рис. 4.11.5


 
                 

Рис. 4.11.5

Таб. №4.10

Таблица истинности схемы ИЛИ—НЕ

X

y

0

0

1

0

1

0

1

0

0

1

1

0

 

4.11.7. Что такое триггер?

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

Термин триггер происходит от английского слова trigger — защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает “хлопанье”. Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить (“перебрасываться”) из одного электрического состояния в другое и наоборот.

Самый распространённый тип триггера — так называемый RS-триггер (S и R, соответственно, от английских set — установка, и reset — сброс). Условное обозначение триггера — на рис. 4.11.6.


Рис.
4.11.6

Он имеет два симметричных входа S и R и два симметричных выхода Q и , причем выходной сигнал Q является логическим отрицанием сигнала .

На каждый из двух входов S и R могут подаваться входные сигналы в виде кратковременных импульсов ( ).

Наличие импульса на входе будем считать единицей, а его отсутствие — нулем.


Рис.
4.11.7

На рис. 4.11.7 показана реализация триггера с помощью вентилей ИЛИ—НЕ и соответствующая таблица истинности. Проанализируем возможные комбинации значений входов R и S триггера, используя его схему и таблицу истинности схемы ИЛИ—НЕ (Таб. №4.10).

Если на входы триггера подать S=“1”, R=“0”, то (независимо от состояния) на выходе Q верхнего вентиля появится “0”. После этого на входах нижнего вентиля окажется R=“0”, Q=“0” и выход станет равным “1”.

Таб. №4.10

                           Истинность схемы ИЛИ—НЕ

S

R

Q

0

0

Запрещено

0

1

1

0

1

0

0

1

1

1

хранение бита

Точно так же при подаче “0” на вход S и “1” на вход R на выходе появится “0”, а на Q — “1”. Если на входы R и S подана логическая “1”, то состояние Q и не меняется. Подача на оба входа R и S логического “0” может привести к неоднозначному результату, поэтому эта комбинация входных сигналов запрещена.

Поскольку один триггер может запомнить только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, для запоминания килобайта, соответственно, 8 х 210 = 8192 триггеров. Современные микросхемы памяти содержат миллионы триггеров.

4.11.8. Что такое сумматор?

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

Многоразрядный двоичный сумматор, предназначенный для сложения многоразрядных двоичных чисел, представляет собой комбинацию одноразрядных сумматоров, с рассмотрения которых мы и начнём. Условное обозначение одноразрядного сумматора на рис. Рис. 4.11.8


Рис. 4.11.8

При сложении чисел A и B в одном i-ом разряде приходится иметь дело с тремя цифрами:

1. цифра ai первого слагаемого;

2. цифра bi второго слагаемого;

3. перенос pi–1 из младшего разряда.

В результате сложения получаются две цифры:

1. цифра ci для суммы;

2. перенос pi из данного разряда в старший.

Таб. №4.11

Входы

Выходы

Первое слагаемое

Второе слагаемое

Перенос

Сумма

Перенос

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

Таким образом, одноразрядный двоичный сумматор есть устройство с тремя входами и двумя выходами, работа которого может быть описана Таб. №4.11 истинности.

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

Например, схема вычисления суммы C = (с3 c2 c1 c0) двух двоичных трехразрядных чисел A = (a2 a1 a0) и B = (b2 b1 b0) может иметь вид:

4.11.9. Какие основные законы выполняются в алгебре логики?

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

Таб. №4.12

ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Закон

Для   ИЛИ

Для   И

Переместительный

Сочетательный

Распределительный

Правила де Моргана

Идемпотенции

Поглощения

Склеивания

Операция переменной с ее инверсией

Операция с константами

Двойного отрицания

4.11.10. Как составить таблицу истинности?

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

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

(0, 0),     (0, 1),     (1, 0),     (1, 1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь:

(0, 0, 0),     (0, 0, 1),     (0, 1, 0),     (0, 1, 1),     (1, 0, 0),     (1, 0, 1),     (1, 1, 0),     (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.

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

Примеры.

1. Составим таблицу истинности для формулы , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим Таб. №4.13

Таб. №4.13

Переменные

Промежуточные логические формулы

Формула

0

0

1

0

0

1

1

1

0

1

1

1

1

0

1

1

1

0

0

0

1

0

0

1

1

1

0

0

1

0

0

1

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.

2. Таблица истинности для формулы :

Таб. №4.14

Переменные

Промежуточные логические формулы

Формула

0

0

0

1

1

0

0

0

1

1

0

0

0

0

1

0

1

0

1

1

0

1

1

1

0

0

0

0

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.

3. Таблица истинности для формулы :

Таб. №4.14

Переменные

Промежуточные логические формулы

Формула

0

0

0

1

1

0

1

0

0

0

0

1

1

1

0

1

1

1

0

1

0

0

0

1

1

0

1

0

1

1

0

0

1

1

1

1

1

0

0

1

1

0

0

0

0

1

0

1

1

1

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

1

0

1

0

0

0

0

Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой.

4.11.11. Как упростить логическую формулу?

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

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

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1)  
(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами);

2)  
(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);

3)  
(
повторяется второй сомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания);

4)  
(
вводится вспомогательный логический сомножитель (); затем комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);

5)  
(сначала
 добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания);

6)  
(выносятся за скобки общие множители; применяется правило операций с константами);

7)  
(к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания);

8)  
(общий множитель x выносится за скобки, комбинируются слагаемые в скобках — первое с третьим и второе с четвертым, к дизъюнкции применяется правило операции переменной с её инверсией);

9)  
(используются распределительный закон для дизъюнкции, правило операции переменной с ее инверсией, правило операций с константами, переместительный закон и распределительный закон для конъюнкции);

10)  
(используются правило де Моргана, закон двойного отрицания и закон поглощения).

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

4.11. 12. Что такое переключательная схема?

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

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

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю.

Будем считать, что два переключателя Х и связаны таким образом, что когда Х замкнут, то разомкнут, и наоборот. Следовательно, если переключателю Х поставлена в соответствие логическая переменная х, то переключателю должна соответствовать переменная .

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

Найдем функции проводимости F некоторых переключательных схем:

a)  

Схема не содержит переключателей и проводит ток всегда, следовательно F=1;
 

б)  

Схема содержит один постоянно разомкнутый контакт, следовательно F=0;
 

в)  

Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, F(x) = x;
 

г)  

Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут, следовательно, F(x) = ;
 

д)  

Схема проводит ток, когда оба переключателя замкнуты, следовательно, F(x) = x . y;
 

е)  

Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, F(x)=x v y;
 

ж)  

Схема состоит из двух параллельных ветвей и описывается функцией .

Две схемы называются равносильными, если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале).

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

Задача нахождения среди равносильных схем наиболее простых является очень важной. Большой вклад в ее решение внесли российские учёные Ю.И. Журавлев, С.В. Яблонский и др.

При рассмотрении переключательных схем возникают две основные задачи: синтез и анализ схемы.

СИНТЕЗ СХЕМЫ по заданным условиям ее работы сводится к следующим трём этапам:

составлению функции проводимости по таблице истинности, отражающей эти условия;

упрощению этой функции;

построению соответствующей схемы.

АНАЛИЗ СХЕМЫ сводится к определению значений её функции проводимости при всех возможных наборах входящих в эту функцию переменных.

Получению упрощённой формулы.

Примеры.

1. Построим схему, содержащую 4 переключателя x, y, z и t, такую, чтобы она проводила ток тогда и только тогда, когда замкнут контакт переключателя t и какой-нибудь из остальных трёх контактов.

Решение. В этом случае можно обойтись без построения таблицы истинности. Очевидно, что функция проводимости имеет вид F(x, y, z, t) = t . (x v y v z), а схема выглядит так:

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

Схема имеет вид:

3. Найдем функцию проводимости схемы:

Решение. Имеется четыре возможных пути прохождения тока при замкнутых переключателях a, b, c, d, e : через переключатели a, b; через переключатели a, e, d; через переключатели c, d и через переключатели c, e, b. Функция проводимости F(a, b, c, d, e) = a . b   v   a . e . d   v   c . d   v   c . e . b.

4. Упростим переключательные схемы:

а)  

Решение:   

Упрощенная схема:

б)  

.

Здесь первое логическое слагаемое является отрицанием второго логического слагаемого , а дизъюнкция переменной с ее инверсией равна 1.

Упрощенная схема :

в)  

Упрощенная схема:

г)  

Упрощенная схема:

д )  

(по закону склеивания)

Упрощенная схема:

е)  

Решение: 

Упрощенная схема:

4.11. 13. Как решать логические задачи?

Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:

средствами алгебры логики;

табличный;

с помощью рассуждений.

Познакомимся с ними поочередно.

1). Решение логических задач средствами алгебры логики

Обычно используется следующая схема решения:

изучается условие задачи;

вводится система обозначений для логических высказываний;

конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

определяются значения истинности этой логической формулы;

из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Пример. Компьютер на котором  чаще всего выходят из строя три узла компьютера — a, b, c, и  есть необходимые детали для замены. Выяснить, какой именно узел надо заменить, он может по сигнальным лампочкам на контрольной панели. Лампочек тоже ровно три: x, y и z.

Инструкция по выявлению неисправных узлов такова:

если неисправен хотя бы один из узлов компьютера, то горит по крайней мере одна из лампочек x, y, z;

если неисправен узел a, но исправен узел с, то загорается лампочка y;

если неисправен узел с, но исправен узел b, загорается лампочка y, но не загорается лампочка x;

если неисправен узел b, но исправен узел c, то загораются лампочки x и y или не загорается лампочка x;

если горит лампочка х и при этом либо неисправен узел а, либо все три узла a, b, c исправны, то горит и лампочка y.

Компьютер сломался. На контрольной панели загорелась лампочка x. Тщательно изучив инструкцию, пользователь починил компьютер. Но с этого момента и он понял, что инструкция несовершенна, и есть случаи, когда она ему не поможет.

Какие узлы заменил пользователь? Какие изъяны он обнаружил в инструкции?

Решение. Введем обозначения для логических высказываний:

a — неисправен узел а;   x — горит лампочка х;

b — неисправен узел b;   y — горит лампочка y;

с — неисправен узел с;   z — горит лампочка z.

Правила 1-5 выражаются следующими формулами:

Формулы 1-5 истинны по условию, следовательно, их конъюнкция тоже истинна:

Выражая импликацию через дизъюнкцию и отрицание (напомним, что ), получаем:

Подставляя в это тождество конкретные значения истинности x=1, y=0, z=0, получаем:

Отсюда следует, что a=0, b=1, c=1. 

Ответ на первый вопрос задачи: нужно заменить блоки b и c; блок а не требует замены. Ответ на второй вопрос задачи получите самостоятельно.

2). Решение логических задач табличным способом

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

Пример 3. В КЦ приняли на работу трёх специалистов : Виктор, Олег и Анатолий, умеющих программировать  C, Pl, Fort, SQL, C++

Известно, что каждый владеет двумя языками программирования. На каких языках програмирует каждый из них, если каждый владеет двумя языками?

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

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

Из условия 4 следует, что Олег не програмирует ни на Pl, ни на Fort, а из условий 3 и 5, что Виктор не умеет програмировать  на Ассемблере, С, SQL и C++. Следовательно, инструменты ВикторaPl и Fort. Занесем это в таблицу, а оставшиеся клетки столбцов "Pl" и "Fotr" заполним нулями:

 

Ассемблер

С

Pl

Fort

SQL

C++

Виктор

0

0

1

1

0

0

Олег

 

 

0

0

 

0

Анатолий

 

 

0

0

 

 

Из таблицы видно, что на C++ может програмировать только Анатолий.

Из условий 1 и 2 следует, что Олег не программист на Ассемблере. Так как на Ассемблере не програмирует ни Виктор, ни Олег, то  программист на Ассемблере Анатолий. Оба языка программирования, на которых програмирует Анатолий , теперь определены, поэтому остальные клетки строки "Анатолий" можно заполнить нулями:

 

Ассемблер

С

Pl

Fort

SQL

C++

Виктор

0

0

1

1

0

0

Олег

0

 

0

0

 

0

Анатолий

1

0

0

0

0

1

Из таблицы видно, что програмировать на С и на SQL может только Олег.

 

Ассемблер

С

Pl

Fort

SQL

C++

Виктор

0

0

1

1

0

0

Олег

0

1

0

0

1

0

Анатолий

1

0

0

0

0

1

Ответ: Виктор програмирует на Pl и Fort, Олег  — на С  и SQL, Анатолий   — на Ассемблере и С++.

3). Решение логических задач с помощью рассуждений

Этим способом обычно решают несложные логические задачи.

Пример 6. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?

Решение. Имеется три утверждения:

Вадим изучает китайский;

Сергей не изучает китайский;

Михаил не изучает арабский.

Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

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

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

Ответ: Сергей изучает китайский язык, Михаил — японский, Вадим — арабский.


 

А также другие работы, которые могут Вас заинтересовать

66332. Особливості використання методики ейдотехніки на уроках у першому класі початкової школи 246.5 KB
  Механічне запам’ятовування через силу постійні повторювання негативно впливають на фізичний стан нервову та емоційну сферу дітей значно ускладнюють процес їхнього адаптування до навчання у школі; у засвоєнні знань часто дають зворотний ефект.
66333. Що треба знати, обираючи фах 32 KB
  Адже саме в процесі праці сформувалася людина і завдяки праці змінюється її власна природа в якій вона досягає своєї свідомої мети прагне до її реалізації конструює свій життєвий шлях. Людина зобов’язана працювати щоб залишити на землі свій власний слід...
66334. Малювання фарбами. Оздобления новорічних iгpaшок, виготовлених iз солоного тіста 48 KB
  Вчитель пропонує учневі зачитати вірш Миколай Коли замерзла річка І став біленький гай Зійшов у темну нічку На землю Миколай. На кого схожий Святий Миколай На Діда Мороза На яке свято приходить Дід Мороз Новий Рік Що робить Дід Мороз...
66335. Сценарій презентації поетичної збірки В.Федорової «Місце під сонцем» 41 KB
  Вітаємо вас у цій світлиці, у цьому затишному куточку Красноріченського освітнього округу, де зібралися люди, небайдужі до чистоти духовних криниць, до натхненної творчої праці та наділені великою любов’ю до культурного розквіту нашого краю.
66336. ШКОЛА ЮНОГО ФЕНОЛОГА 12.94 MB
  Дерева хоч і не вкрилися листям але вже пробудилися від зимових холодів. Багряне та золоте листя вірна ознака осені. Буває що частина листя жовкне задовго до осінніх днів. Іноді жовте листя на кущах і деревах з’являється ще в середині літа коли сухо та спекотно.
66337. Фестиваль юних обдарувань 55 KB
  Оформлення: святковоуричисто прикрашений актовий зал; емблема; кольрові кульки; квіти; виставка творчих робіт поробок; Державний прапор України; грамоти призерам; картки творчих досягнень; стрічки домінантам: Інтелектуал року Ерудит року Творча особистість Золоті руки Спортсмен року...
66338. Фестиваль європейських країн 112 KB
  Віддавна народи світу Мають власні прапори Наче долю горду й світлу Піднімають дороги 3й учень. Наш водій обирається учень якому дається кермо та головний убір водія рушаймо Пісню заспіваймо Учні і вчитель співають пісню Голубий вагон муз.
66339. Polymerase Chain Reaction (PCR) 40 KB
  Two primers, each about 20 bases long with sequence complementary to the sequence immediately adjacent to the DNA segment of interest.
66340. Функционирование русского языка в Республике Казахстан. Безударные гласные в корне слова (проверяемые, непроверяемые) 84.5 KB
  Языков на свете очень много – свыше двух тысяч. Точно установить их количество пока не удалось. Язык – явление общественное, он создается на протяжении длительного исторического периода. Язык возник в глубокой древности в процессе совместной трудовой деятельности людей.