СКИПОД ответы на билеты (1127807), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

[править] Расслоение оперативной памяти.

Расслоение ОЗУ – один из аппаратных путей решения проблемы дисбаланса в скорости доступа к данным, размещенным в ОЗУ и производительностью ЦП. Суть расслоения ОЗУ состоит в следующем. Все ОЗУ состоит из k блоков, каждый из которых может работать независимо. Ячейки памяти распределены между блоками таким образом, что у любой ячейки ее соседи размещаются в соседних блоках. Возможность предварительной буферизации при чтении команд/данных. Оптимизация при записи в ОЗУ больших объемов данных.

При конвейерном доступе при М-кратном расслоении и регулярной выборке на обращение к одной ячейке памяти может тратиться 1/М цикла памяти. Но возможны конфликты по доступу, если шаг регулярной выборки достаточно большой или кратен числу банков памяти.

[править] Ассоциативная память.

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

Для получения номера телефона второго абонента следует обратиться: load (2) и получить в регистре ответа R = 9448304. Такой вид памяти, при котором необходимая информация определяется номером строки памяти, называется адресной. Другой вид оперативной памяти – ассоциативной можно рассматривать также как двумерную таблицу, но у каждой строки которой есть дополнительное поле, поле ключа.

Например:

После обращение к ассоциативной памяти с запросом : load (Петров) для данного примера получим ответ: R = 9448304. Здесь задание координаты строки памяти производится не по адресу, а по ключу. Но при состоянии ассоциативной памяти:

можно получить номер телефона из второй строки запросом: load (2). Таким образом на ассоциативной памяти можно моделировать работу адресной. Ассоциативная память имеет очевидное преимущества перед адресной, однако, у нее есть большой недостаток - ее аппаратная реализация невозможна для памяти большого объема.

Телефонная книга, реализованная на обычной памяти требует перебор для поиска n/2. А в ассоциативной памяти все находится за 1 такт.

ВОПРОС: Предложите схему реализации модели ассоциативной памяти при помощи адресной.

Ответ: Область памяти делим ровно пополам. Первая половина заполняется ключами, вторая соответствующими ключам значениями. Когда найден ключ, известен его адрес как смещение относительно начала памяти. Тогда адрес содержимого по ключу – это смещение + размер области ключей, то есть адрес ячейки из второй половины памяти, которая соответствует ключу. А не имеется ли тут в виду реализация hash или индексных деревьев?

[править] Виртуальная память.

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

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

[править] Базирование адресов.

Элементарное программно-аппаратное решение – использование возможности базирования адресов.

Суть его состоит в следующем: пусть имеется исполняемый программный модуль. Виртуальное адресное пространство этого модуля лежит в диапазоне [0, A_кон]. В ЭВМ выделяется специальный регистр базирования R_баз, который содержит физический адрес начала области памяти, в которой будет размещен код данного исполняемого модуля. При этом исполняемые адреса, используемые в модуле будут автоматически преобразовываться в адреса физического размещения данных путем их сложения с регистром R_баз. Таким образом, код используемого модуля может загрузиться в любое свободное место в памяти. Эта схема является элементарным решением организации простейшего аппарата виртуальной памяти. Аппарат виртуальной памяти – аппаратные средства компьютера, обеспечивающие преобразование (установление соответствия) программных (виртуальных) адресов, используемых в программе адресам физической памяти в которой размещена программа при выполнении.

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

[править] Страничная организация памяти

Страничная организация памяти предполагает разделение всего пространства ОЗУ на блоки одинакового размера – страницы. Обычно размер страницы равен 2^k. В этом случае адрес, используемый в данной ЭВМ, будет иметь следующую структуру:

Модельная (упрощенная) схема организации функционирования страничной памяти ЭВМ следующая: Пусть одна система команд ЭВМ позволяет адресовать и использовать m страниц размером 2^k каждая. То есть, виртуальное адресное пространство программы/процесса может использовать для адресации команд и данных до m = 2^r страниц, где r - разрядность поля "номер страницы".

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

В виртуальном адресе размер поля определяется максимальным числом виртуальных страниц – m.

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

В ЦП ЭВМ имеется аппаратная таблица страниц (иногда таблица приписки) следующей структуры:

Таблица содержит m строк. Содержимое таблицы определяет соответствие виртуальной памяти физической для выполняющейся в данный момент программы/процесса. Соответствие определяется следующим образом: i-я строка таблицы соответствует i-й виртуальной странице. Содержимое строки αi определяет, чему соответствует i-я виртуальная страница программы/процесса. Если αi ≥ 0, то это означает, что αi есть номер физической страницы, которая соответствует виртуальной странице программы/процесса. Если αi= -1, то это означает, что для i-й виртуальной страницы нет соответствия физической странице ОЗУ (обработка этой ситуации ниже).

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

1. При выполнении очередной команды схемы управления ЦП вычисляют некоторый адрес операнда (операндов) A_исп. Это виртуальный исполнительный адрес.

2. Из A_исп выделяется значение поля "номер страницы" (номер виртуальной страницы). По этому значению происходит индексация и доступ к соответствующей строке таблицы страниц.

3. Если значение строки ≥ 0, то происходит замена содержимого поля номер страницы на соответствующее значение строки таблицы, таким образом, получается физический адрес. И далее ЦП осуществляет работу с физическим адресом. Если значение строки таблицы равно –1 это означает, что полученный виртуальный адрес не размещен в ОЗУ. Причины такой ситуации? Их две. Первая – данная виртуальная страница отсутствует в перечне станиц, доступных для программы/процесса, то есть имеет место попытка обращения в “чужую”, нелегитимную память. Вторая ситуация, когда операционная система в целях оптимизации использования ОЗУ, откачала некоторые страницы программы/процесса в ВЗУ(свопинг).

[править] Алгоритмы управления страницами ОЗУ.

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

Существуют разные алгоритмы:

[править] Алгоритм NRU

(Not Recently Used – "не использовавшийся в последнее время"), который использует биты статуса страницы в записях таблицы страниц. R - обращение, M - изменение. Эти биты устанавливаются аппаратно.

1. При запуске процесса M и R для всех страниц процесса обнуляются

2. По таймеру происходит обнуление всех битов R

3. При возникновении страничного прерывания ОС делит все страниц на классы по изменению.

4. Случайная выборка страницы для удаления в непустом классе с минимальным номером

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

[править] Алгоритм FIFO

«Первым прибыл – первым удален» - простейший вариант FIFO. (проблемы «справедливости»)

Модификация алгоритма (алгоритм вторая попытка):

1. Выбирается самая «старая страница». Если R=0, то она заменяется

2. Если R=1, то R – обнуляется, обновляется время загрузки страницы в память (т.е. переносится в конец очереди). На п.1

[править] Алгоритм «Часы»

1. Если R=0, то выгрузка страницы и стрелка на позицию вправо.

2. Если R=1, то R-обнуляется, стрелка на позицию вправо и на П.1.

[править] Алгоритм LRU

Least Recently Used – наиболее давно используемая страница

Вариант реализации:

• Памяти N страниц. Существует битовая матрица NxN (изначально полностью обнулена).

• При каждом обращении к i-ой странице происходит присваивание 1 всем битам i-ой строки и 0 - всем битам i-ого столбца.

• Строка с наименьшим двоичным кодом - искомая

[править] Алгоритм NFU

Not Frequently Used – редко использовавшаяся страница (Программная модификация LRU (?))

Для каждой физической страницы i – программный счетчик Counti0. Изначально Counti – обнуляется для всех i.

1. По таймеру Counti = Counti + Ri (R - бит обращения)

2. Выбор страницы с минимальным значением {Counti}

Недостаток – «помнит» всю активность по использованию страниц

Модификация NFU – алгоритм старения

1. Значение счетчика сдвигается на 1 разряд вправо.

2. Значение R добавляется в крайний левый разряд счетчика.

[править] Использование в ЭВМ принципа локальности вычислений.

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

• расслоение памяти - ускорение доступа к последовательным ячейкам

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

• spatial reuse в cache - если мы считали cache line, то там, помимо нужной ячейки, окажутся и соседние

[править] Полностью ассоциативная кэш-память.

Кэш-память

Характеристики

Список файлов ответов (шпаргалок)