Электронные вычислительные машины и системы

Размещено на http://www.Allbest.ru/

1

Сдвиг

Различают операции арифметического, логического и циклического сдвига.

В описаниях языка микроопераций сдвиги имеют следующие обозначения СдвА, СдвЛ, СдвЦ. Ниже описана микрооперация арифметического сдвига содержимого регистра С на 4 разряда вправо:

Операция арифметического сдвига содержимого регистра D на 3 разряда влево:

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

Условные микрооператоры.

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

ЕСЛИ (условие) ТО микрооператор(ы) ИНАЧЕ микрооператор(ы)

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

ЕСЛИ (условие) ТО переход ИНАЧЕ микрооператор(ы) или наоборот.

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

РгАk k+lесли (условие) то РгВm m+lРгСn n+l

иначе РгDp p+lРгЕq q+l

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

1-ый такт:

2-ой такт:

В данном случае каждая микрокоманда содержит одну микрооперацию.

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

Безусловные микрокоманды:

РгА:= ША или РгИ:= ЗМ[РгА,0чn-1]

Условные микрокоманды (Пример графа микропрограммы):

Размещено на http://www.Allbest.ru/

1

ЛЕКЦИЯ 8. АРИФМЕТИКО-ЛОГИЧЕСКОЕ УСТРОЙСТВО

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

Все операции, выполняемые в АЛУ, можно разделить на следующие группы:

Ё операции двоичной арифметики для чисел с фиксированной точкой;

Ё операции двоичной (шестнадцатеричной) арифметики для чисел с плавающей точкой;

Ё операции десятичной арифметики над числами, представленными в двоично-десятичном коде;

Ё операции адресной арифметики (при модификации адресов команд);

Ё операции специальной арифметики (нормализация, сдвиг);

Ё логические операции;

Ё операции над алфавитно-цифровыми полями.

Для выполнения перечисленных операций в АЛУ включают следующие функциональные узлы:

Ё сумматор (для выполнения суммирования и других действий над кодами операндов);

Ё регистры (для хранения кодов операндов на время выполнения действия над ними);

Ё сдвигатели (для сдвига кода на один или несколько разрядов вправо или влево);

Ё преобразователи (для преобразования прямого кода числа в обратный или дополнительный);

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

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

Структура АЛУ

Обобщенная структурная схема АЛУ (рис. 8.1) включает:

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

- операционный блок, в котором осуществляется преобразование операндов в соответствии с реализуемыми алгоритмами;

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

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

Иногда АЛУ не содержит своего БР, в этом случае операционный блок непосредственно работает с регистрами общего назначения процессора. Для оперативного управления выполнением операции в ОБ на разных этапах анализируется преобразуемая информация и формируются сигналы признаков (флаги), которые используются в БУ для выработки и посылки в процессор сигнала признака результата (ПРез).

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

Рис. 8.1 Обобщенная структурная схема АЛУ

Сумматоры

Сумматоры АЛУ делятся:

Ё по типу использования для суммирования базовых элементов (комбинационные и накапливающие);

Ё по способу осуществления операции суммирования (последовательные и параллельные).

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

Рис. 8.2 Сумматор параллельного действия (на накапливающих элементах)

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

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

Классификация АЛУ

По способу представления чисел:

Ё для чисел с фиксированной точкой;

Ё для чисел с плавающей точкой;

Ё для десятичных чисел.

По способу действия над операндами:

Ё последовательные;

В параллельных АЛУ операнды представляются параллельным кодом и операции совершаются параллельно во времени над всеми разрядами операндов.

Ё параллельные.

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

По выполняемым функциям АЛУ подразделяются на:

Ё многофункциональные;

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

Ё функциональные (блочные).

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

По структурной организации АЛУ подразделяются на устройства, имеющие:

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

Ё магистральную структуру с сосредоточенной памятью и логикой.

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

Пример:

С регистром Рг1 непосредственно связан преобразователь кода ПК1. С регистром Рг3 объединен КСМ по схеме накапливания сумматора, а с КСМ, в свою очередь, связаны ПК2 и комбинационная схема КС для мультиплексирования входных данных. На регистре Рг3 выполняются микрооперации сдвига вправо или влево и сброс. Регистр Рг4 выполняет микрооперации сдвига и непосредственно связан с ПК3. Таким образом, в АЛУ с такой структурой функции хранения и преобразования информации выполняются одним и тем же операционным блоком.

Рис. 8.3 Регистровая структура с закрепленной логикой

В АЛУ с магистральной структурой регистры выделены в отдельный блок, а схемы для преобразования информации выделены также в отдельный операционный блок (ОБ), который связан с блоками регистров по входам и выходам (см. рис. 8.4). Блок регистров (БР) осуществляет функции приема, хранения и выдачи операндов и результатов, а ОБ выполняет весь набор микроопераций над словами, хранимыми в блоке регистров. В АЛУ с такой структурой блок регистров может быть реализован или как СОЗУ, или как совокупность отдельных регистров с индивидуальными схемами управления. Структура же ОБ имеет следующие модификации:

Ё последовательное соединение операционных узлов;

Ё параллельное соединение операционных узлов.

Пример АЛУ с магистральной структурой с последовательным соединением узлов ОБ.

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

Рис. 8.4 Магистральная структура с последовательным соединением операционных узлов

В случае же параллельного соединения операционных блоков АЛУ все операционные блоки: СМ, СДВ, КС, ПК параллельно соединяются с входными и выходными шинами блока регистров, что позволяет выполнять несколько микроопераций параллельно. Выглядит это так, как показано на рис. 8.5.

Рис. 8.5 Магистральная структура с параллельным соединением операционных узлов

Методы повышения быстродействия АЛУ

Одним из таких методов является реализация принципа локального параллелизма. Суть этого принципа - в распараллеливании во времени алгоритма выполняемой отдельно команды на ряд независимых этапов и их реализации на различных операционных блоках АЛУ.

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

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

Наиболее новый способ увеличения быстродействия всех блоков процессора ЭВМ - введение векторных операций - операций над упорядоченными массивами данных (в суперЭВМ векторные операции появились давно, в связи с чем в составе процессоров появилась специализация устройств по типам операндов - скалярные и векторные). Например, в современных процессорах появились регистровая память и средства обработки двух типов: векторные и скалярные.

К векторным средствам обработки относятся:

Ё один или несколько арифметических конвейеров для обработки элементов векторов;

Ё векторные регистры для хранения векторной информации.

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

вычислительный система логический оперативный процессор

ЛЕКЦИЯ 9. ПАМЯТЬ ЭВМ

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

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

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

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

Как и большинство устройств ЭВМ, память имеет иерархическую структуру. Обобщённая модель такой структуры, отражающая многообразие ЗУ и их взаимодействие, представлена на рисунке 9.1.

Рис. 9.1 Иерархическая структура памяти

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

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

На втором оперативном уровне, более низком, находится оперативная память (ОП), служащая для хранения активных программ и данных, то есть тех программ и данных, с которыми работает ЭВМ.

На следующем более низком внешнем уровне размещается внешняя память.

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

Сверхоперативная память. Иногда в архитектуре ЭВМ регистровая память организуется в виде сверхоперативного ЗУ с прямой адресацией. Такая память имеет то же назначение как и РОН, служит для хранения операндов, данных и служебной информации, необходимой процессору.

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

Буферная память. В функциональном отношении кэш-память рассматривается как буферное ЗУ, размещённое между основной (оперативной) памятью и процессором. Основное назначение кэш-памяти - кратковременное хранение и выдача активной информации процессору, что сокращает число обращений к основной памяти, скорость работы которой меньше, чем кэш-памяти. Кэш - память от английского cashe - тайник. Она не является программно доступной. Поэтому она оказывает влияние на производительность ЭВМ, но не влияет на программирование прикладных задач. В современных ЭВМ различают кэш первого и второго уровней. Кэш первого уровня интегрирована с блоком предварительной выборки команд и данных ЦП и служит, как правило, для хранения наиболее часто используемых команд. Кэш второго уровня служит буфером между ОП и процессором. В некоторых ЭВМ существует кэш память отдельно для команд и отдельно для данных.

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

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

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

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

При обращении к блоку данных, находящемуся на оперативном уровне, его копия пересылается в сверхоперативную буферную память. Последующие обращения к этому блоку данных производится к буферной памяти. Поскольку время выборки из СОЗУ t_СОЗУ много меньше времени выборки из оперативной памяти t_ОП, введение в структуру ЭВМ СОЗУ приводит к уменьшению эквивалентного времени обращения tэ по сравнению с временем обращения к оперативной памяти t_ОП:

t_Э = t_СОЗУ + бt_ОП,

гдеб = 1- q,

а q - вероятность попадания, т.е. вероятность того, что блок данных, к которому производится обращение, находится в СОЗУ.

9.1 Организация внутренней памяти процессора

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

Рис. 9.2 СОЗУ с прямой адресацией с одним адресным входом

Дешифратор адреса формирует управляющие сигналы 0,1,…,М, подключающие регистр с заданным адресом к шинам СОЗУ.

Адрес регистра, к которому производится обращение с целью записи или чтения (управляющий Сигнал ЗП/ЧТ) информации, поступает по шине А. Дешифратор адреса (ДША) формирует управляющие сигналы 0,1,…М, подключающие регистр с заданным адресом к шинам СОЗУ.

При использовании двухадресных команд типа «регистр - регистр» подобная организация СОЗУ становится неэффективной, т.к. за один такт может быть выбрано содержимое только одного регистра.

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

Рис. 9.3 СОЗУ с прямой адресацией с двумя адресными входами

Двухадресная команда, в которой адресуются два операнда, расположенные в регистрах, и результат операции размещается по одному из этих адресов [0…M].

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

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

Рис. 9.4 Стековая память

Предполагается, что область памяти для стека находится в сегменте стека, база которого определяется регистром SS - сегментным регистром стека. При добавлении записи в стек вначале проверяется, содержит ли указатель стека (ESP) значение, не меньше длины помещаемой в стек записи (2 байта для 16-разрядного и 4 байта для 32-разрядного процессора). Если это условие не удовлетворено, то генерируется особый случай нарушения стека. Если же ESP содержит значение не меньше требуемого, производится декремент указателя стека на 2(4) и операнд сохраняется по адресу SS:SP (SS:ESP) в текущем сегменте стека, на который указывает указатель стека.

(Число 4 - число байт в 32-х разрядном процессоре). При извлечении данных из стека содержимое ESP сравнивается с пределом SS. Если обращение оказывается вне предела, формируется особый случай нарушения стека. Когда обращение оказывается разрешенным, считываются данные по адресу SS:[ESP] и осуществляется инкремент ESP на 4. Извлечь данные из стека можно в регистр или в ЯП.

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

Прежде чем приступать к изучению принципов организации ОП, следует отметить следующее.

В последнее время емкость микросхем динамической памяти учетверялась каждые три года. Но скорость этих микросхем за тот же период возрастала гораздо меньшими темпами (примерно 7% в год). В то время, как производительность процессоров, начиная с 1987 г, увеличивалась на 50% в год. Таким образом, согласование производительности современных процессоров со скоростью ОП вычислительных машин и систем остается одной из важнейших проблем. Методы повышения производительности за счет увеличения размеров КЭШ-памяти и введения многоуровневой организации КЭШ могут оказаться недостаточно эффективными с точки зрения стоимости системы. Поэтому важным направлением современных разработок являются методы повышения пропускной способности памяти за счет ее организации, включая специальные методы организации динамических ЗУ.

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

Оперативная память (system memory) - имеет относительно небольшую емкость - от 8 до 128 Мбайт (в некоторых машинах - больше). Количество и быстродействие оперативной памяти оказывает чрезвычайно серьезное воздействие на быстродействие современных компьютеров. Работает на частоте системной шины. Время доступа к оперативной памяти составляет порядка 50-70 нс (для сравнения - время доступа к жестким магнитным дискам составляет десятки микросекунд). Доступ процессора к оперативной памяти происходит через кэш 2-го уровня. Некоторые подсистемы компьютера способны обращаться к оперативной памяти напрямую, минуя процессор. Строится ОП как правило на DRAM Dynamic Random Access Memory) - динамических запоминающих устройствах случайного доступа.

DRAM (Dynamic RAM) - динамическая память - разновидность памяти, единичная ячейка которой представляет собой конденсатор с диодной конструкцией. Наличие или отсутствие заряда конденсатора соответствует единице или нулю. Основной вид, применяемый для оперативной памяти, видеопамяти, а также различных буферов и кэшей более медленных устройств. По сравнению со SRAM заметно более дешевая, хотя и более медленная по двум причинам - емкость заряжается не мгновенно, и, кроме того, имеет ток утечки, что делает необходимой периодическую подзарядку.

SRAM (Static RAM) - статическая память - разновидность памяти, единицей хранения информации в которой является состояние «открыто-закрыто» в транзисторной сборке. Используется преимущественно в качестве кэш-памяти 2-го уровня. Ячейка SRAM более сложна по сравнению с ячейкой DRAM, поэтому более высокое быстродействие SRAM компенсируется высокой ценой. Несмотря на низкое энергопотребление, является энергозависимой, то есть при отключении питания информация теряется.

ОП является наиболее дефицитным и наиболее важным ресурсом в вычислительных машинах и системах.

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

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

ЛЕКЦИЯ 10. МЕТОДЫ УПРАВЛЕНИЯ ПАМЯТЬЮ БЕЗ ИСПОЛЬЗОВАНИЯ ДИСКОВОГО ПРОСТРАНСТВА (БЕЗ ИСПОЛЬЗОВАНИЯ ВНЕШНЕЙ ПАМЯТИ)

Все методы управления памятью могут быть разделены на два класса (рис. 10.1):

Ё методы распределения ОП без использования внешней памяти (дискового пространства);

Ё методы распределения памяти с использованием дискового пространства.

Рис. 10.1 Методы управления памятью

Рассмотрим вначале первую группу методов:

10.1 Распределение памяти фиксированными разделами

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

Рис. 10.2 Распределение памяти фиксированными разделами

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

Ё сравнения размера поступившей на выполнение программы с размерами свободных разделов памяти;

Ё выбора подходящего раздела;

Ё загрузка программы и настройка адресов.

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

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

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

Рис. 10.3 Распределения памяти динамическими разделами

В начальный момент времени t0 в ОП загружена только ОС. К моменту времени t1 ОП разделена между ОС и 5 программами (задачами), имеется также свободная область. К моменту времени t2 задача П2 уже завершена и покидает ОП, а на ее место может быть подгружена задача. На освободившееся место загружается задача П6, поступившая в момент времени t3. Выбором раздела для вновь поступившей задачи занимается ОС. Осуществляется выбор раздела по правилам: «первый попавшийся раздел достаточного размера», «раздел, имеющий наименьший достаточный размер», «раздел, имеющий наибольший достаточный размер».

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

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

Ё анализ запроса (при поступлении новой задачи);

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

Ё загрузка задачи в выделенный ей раздел;

Ё корректирование таблиц свободных и занятых областей (как после загрузки очередной задачи в ОП, так и после завершения задачи).

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

10.2 Размещение памяти с перемещаемыми разделами

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

Такая процедура называется сжатием и выполняется ОС в дополнение к функциям, которые ОС выполняет при распределении ОП переменными разделами.

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

Рис. 10.4 Распределение памяти перемещаемыми разделами

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

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

10.3 Организация виртуальной памяти

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

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

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

Т.о., виртуальная память (ВП) - это совокупность программно-аппаратных средств, позволяющих пользователям писать программы, размер которых превосходит имеющуюся ОП.

Для этого ВП решает след. задачи:

Ё размещает данные в ЗУ разного типа, например, часть программы в ОП, а часть на диске;

Ё перемещает данные по мере необходимости между ЗУ разного типа, например, подгружает нужную часть программы с диска в ОП;

Ё преобразует виртуальные адреса в физические.

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

10.4 Страничное распределение

Виртуальное адресное пространство каждого процесса (пр. 1 и пр. 2, см. рис. 10.5) делится на части фиксированного размера, называемые виртуальными страницами. Размер виртуального адресного пространства в общем случае не является кратным размеру страницы, поэтому последняя страница каждого процесса дополняется фиктивной областью. Вся ОП ЭВМ делится на части такого же размера, называемые физическими страницами (или блоками).

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



Рис. 10.5 Страничное распределение памяти

Часть виртуальных страниц процесса при его загрузке помещается в ОП, а часть на жесткий диск. ОС при загрузке процессора формирует для него отдельную информационную структуру - таблицу страниц, в которой устанавливается соответствие виртуальных страниц с определенными номерами (N в.с.) физическим страницам с определенными номерами (N ф.с.). Также в таблице страниц содержится управляющая информация (УИ): признак модификации страницы, признак невыгружаемости (выгрузка некоторых страниц может быть запрещена), признак обращения к странице (используется для подсчета обращений к странице за определенный период времени), а также некоторые другие данные создаваемые и используемые механизмом ВП.

При активизации очередного процесса в регистр адреса таблицы страниц считывается адрес таблицы страниц этого процесса.

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

Ё дольше всего не использовавшаяся страница;

Ё первая попавшаяся (случайная) страница;

Ё страница, к которой было меньше всего обращений.

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

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

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

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

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

Из этой записи извлекается номер физической страницы;

К номеру физической страницы присоединяется смещение, т.е. младшие разряды ВА (путем конкатенации).

Рис. 10.6 Механизм преобразования виртуального адреса

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

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

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

10.5 Сегментное распределение

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

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

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

Рис. 10.7 Распределение памяти сегментами

Система с сегментной организацией функционирует аналогично системе со страничной организацией.

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

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

Виртуальный при сегментной организации представлен парой чисел (g, s), где первое - номер сегмента, второе - смещение внутри сегмента.

ФА получается путем сложения начального ФА сегмента, найденного в таблице сегментов по номеру g, и смещения s. Операция сложения является более медленной, что в целом оказывает отрицательное влияние на быстродействие машины. Еще одним недостатком сегментной организации также является фрагментация на уровне сегментов.

10.6 Странично-сегментное распределение

Данный метод сочетает в себе достоинства обоих подходов, представляя собой их комбинацию. Всё виртуальное адресное пространство процесса делится на сегменты, а каждый сегмент - на страницы. ОП при этом делится на физические страницы. Загрузка процесса в ОП осуществляется постранично. ОС при загрузке процесса создает таблицу сегментов (TS) процесса. Для каждого сегмента создается своя таблица страниц (TP), структура которой полностью аналогична структуре таблицы страниц при страничном распределении. Адрес таблицы сегментов загружается в специальный регистр процессора, когда активизируется соответствующий процесс. В таблице страниц находятся адреса таблиц страниц для всех сегментов данного процесса. По схеме, приведенной на рисунке 10.8, виртуальный адрес преобразуется в физический.

Рис. 10.8 Схема преобразования виртуального адреса в физический

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

Если в системе реализовано такое устройство, то преобразование ВА в ФА осуществляется по такому принципу, называемому динамическим преобразованием адресов (см. рис. 10.9): ВА, представленный парой чисел (g,p) передается в качестве поискового признака в АЗУ, т.о. VAi первый появляется в ячейке А буфера. Вторым полем ячейки является ФА страницы в ОП. При обнаружении совпадения VAi с содержимым памяти из соответствующей ячейки Асс. Буфера, извлекается соответствующий ФА страницы, позволяющий сформировать полный ФА элемента данных в ОП. Если же VAi не совпадает ни с одной ячейкой АЗУ, то преобразование осуществляется обычным способом через таблицы сегментов и страниц. Эффективность применения динамического преобразования адресов определяется тем, насколько редко используются табличные преобразования. Как правило, при первом обращении к странице, расположенной в ОП, ФА определяется с помощью таблиц и загружается в соответствующую ячейку АЗУ, с тем чтобы последующие обращения к странице могли выполняться с использованием АЗУ.

Рис. 10.9 Механизм динамического преобразования адресов

Свопинг

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

Для того, чтобы задача могла начать выполняться, она должна быть загружена в ОП, объем которой ограничен.

На рис. 10.10 показан график зависимости коэффициента загрузки процессора в зависимости от числа одновременно выполняемых процессов и доли времени, проводимого этими процессами в состоянии ожидания ввода-вывода.

Рис 10.10 Зависимость загрузки процессора от числа задач и интенсивности ввода/вывода

Экспериментально выведена зависимость загрузки процессора от числа одновременно выполняемых задач и от интенсивности вв/выв. Из рисунка видно, что для того, чтобы загрузить процессор на 90%, достаточно 3-х задач с небольшой интенсивностью ввода-вывода, а чтобы обеспечить такую же загрузку интерактивными задачами с интенсивным вводом-выводом, потребуется 10 таких задач. Объем же ОП ограничен. Чтобы увеличить уровень мультипрограммирования, и был предложен метод организации вычислительного процесса, называемый свопингом. В соответствии с этим методом некоторые процессы (задачи), обычно находящиеся в состоянии ожидания, целиком могут отгружаться (откачиваться) на диск, а на их место подгружаться другие. При этом программа-планировщик ОС не исключает их из своего рассмотрения и при наступлении условий, в которых возможно выполнять некоторую задачу, находящуюся в области свопинга на диске, эта задача перемещается в ОП. Существуют различные алгоритмы отгрузки процессов на диск и подкачивания других процессов, а также различные способы выделения оперативной и дисковой памяти загружаемому процессу.

ЛЕКЦИЯ 11. МЕТОДЫ ПОВЫШЕНИЯ ПРОПУСКНОЙ СПОСОБНОСТИ ОП

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

11.1 Выборка широким словом

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

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

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

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

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

11.2 Расслоение сообщений

Другой способ повышения пропускной способности ОП связан с построением памяти, состоящей на физическом уровне из нескольких модулей (банков) с автономными схемами адресации, записи и чтения. При этом на логическом уровне управления памятью организуются последовательные обращения к различным физическим модулям. Обращения к различным модулям могут перекрываться, и т.о. образуется своеобразный конвейер. Эта процедура носит название расслоения памяти. Целью данного метода является увеличение скорости доступа к памяти посредством совмещения фаз обращений ко многим модулям памяти. Существуют несколько вариантов организации расслоения. Наиболее часто используемый способ - расслоение обращений за счет расслоения адресов. Этот способ основывается на свойстве локальности программ и данных, предполагающем, что адрес следующей команды на 1 больше адреса предыдущей (иными словами, линейность программы нарушается только командами перехода). Аналогичная последовательность адресов генерируется процессором при чтении слов данных.

Т.о., типичный случай распределения адресов - последовательность вида а, а+1, а+2, а+3 и т.д. (для слов данных - увеличение на 1 - условно, на самом деле 1 - число байт в машинном слове). Из этого следует, что расслоение обращений возможно, если ячейки с адресами а, а+1, а+2, а+3 и т.д будут размещаться в блоках 0,1,2… Такое распределение ячеек по модулям (банкам) обеспечивается за счет использования адресов вида (см. рис. 8.15).

Здесь В - k-разрядный адрес модуля (младшая часть m-разрядного адреса), С - n-разрядный адрес ячейки в модуле В (старшая часть адреса).

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

Принцип расслоения адресов иллюстрирован на рис 11.2 (а).

Все команды и данные размещены в адресном пространстве последовательно. Однако ячейки памяти, имеющие смежные адреса, находятся в различных модулях памяти. Если ОП состоит из 4-х модулей, то номер модуля кодируется двумя младшими разрядами адреса. При этом полные m - разрядные адреса 0,4,8,…. Относятся к блоку 0, адреса 1,5,9,13 - к блоку 1, адреса 2,6,10 - к блоку 2 и адреса 3,7,11,15 - к блоку 3. Т.о., последовательность обращений к адресам 0,1,2,3,4,5,6….будет расслоена между 4 модулями: 0,1,2,3,0,1,2…(см рис. 11.3)



Рис. 11.2 Организация адресного пространства при расслоении памяти (а), временная диаграмма работы модулей (б)

0, 1, 2, 3, 4, 5, 6

0, 1, 2, 3, 0, 1, 2…..

Рис. 11.3 Расслоение последовательности обращений к адресам между модулями памяти

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

На временной диаграмме видно, что время доступа к каждому модулю равно: ф = 4Т, где Т = t i + 1-ti - длительность такта. В каждом такте следуют обращения к модулям памяти в моменты времени t1, t2, t3,…. При наличии 4-х модулей темп выдачи квантов информации из памяти в процессор будет соответствовать 1 такту Т, при этом скорость выдачи информации из каждого модуля в 4 раза ниже, т.е. составит 4Т.

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

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

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

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

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

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

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

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

...