Файл: Каган Б.М. Цифровые вычислительные машины и системы учеб. пособие.pdf

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

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

2*Р( р)+ I.

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

До сих пор мы рассматривали распределение памя­ ти только для одной целевой программы. Фактически их будет несколько, и каждый пользователь имеет свою собственную виртуальную память, которая, как он пред­ полагает, простирается от нуля до максимального адре­ са, допускаемого длиной разрядной сетки адреса. Так как программирование целевых программ производится независимо друг от друга, различные программы будут использовать одни и те же виртуальные адреса, которые тем не менее должны относиться к различным физичес­ ким областям памяти (рис. 11-8). Следовательно, стра­ ничная таблица должна учитывать также принадлеж­ ность страниц различным пользователем, и номер физи­ ческой страницы может быть представлен как функция двух переменных: номера виртуальной страницы р и но­ мера пользователя N. Следовательно, виртуальный адрес 2®р-\-1 преобразуется в истинный адрес 2t p(p, N)+l .

В мультипрограммной системе с распределением опе­ ративной памяти использование страничной организации

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

Рис. 11-8. Виртуальная и физическая памяти.

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

594

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

Аппаратная реализация преобразования страниц. Ес­ ли страничная таблица хранится в оперативной памяти, то выборка каждого слова требует двух циклов обра­ щения к памяти вместо одного: лишний цикл необходим для обращения к страничной таблице. Для уменьшения потерь времени страничные таблицы хранят в специаль­ ных запоминающих устройствах (в быстродействующей памяти небольшой емкости на ферритовых сердечниках либо триггерных регистрах). Например, в машине Sigma-7 для этой цели используется память на интег­ ральных схемах, добавляющая только 60 нсек к каждо­ му циклу оперативной памяти.

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

1)каждой виртуальной странице соответствует одна строка страничной таблицы; строка содержит номер фи­ зической страницы, хранящей данную виртуальную страницу;

2)каждой физической странице соответствует одна строка страничной таблицы; строка содержит номер виртуальной страницы, хранимой в данной физической странице.

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

Впримере, изображенном на рис. 11-9, в регистре

команд содержится виртуальный адрес, в соответствии с которым из памяти запрашивается страница 02, слово

361. Выполняется в настоящий момент программа № 5. Аппаратура преобразования страниц обращается к пя­ той страничной таблице и находит там строку, соответ­ ствующую виртуальной странице 02. В этой строке за­ писан номер физической страницы 43, который переда­ ется в старшие разряды адресного регистра памяти;

Страничные

та б л и ц ы

О

Рис. 11-9. Память со страничными таблицами, построенны­ ми на основе виртуальных страниц.

в младшие разряды передается без изменений номер слова и обращение к памяти производится по физичес­ кому адресу 43 361.

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

596

Например, в машине CDC 3300, где используется подоб­

страниц, приходящихся на программу, приводит к воз­ растанию емкости дорогостоящей памяти страничных

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

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

597

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

А дресѵ і/й р е г и с т р

Рис. 11-10. Ассоциативная память для хранения странич­ ной таблицы.

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

598

происходит прерывание и супервизор вызывает нужную страницу из внешней памяти.

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

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

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

2aN + p- P(p,N).

При обращении к памяти происходит сравнение за­ прашиваемых номеров программы и виртуальной стра­ ницы с числом 2 во всех ассоциативных регистрах. Если ассоциативная память содержит запрашиваемую информацию, то она выдает номер требуемой физичес­ кой страницы Р(р, N), к последнему присоединяется но­ мер слова, после чего возбуждается цикл обращения к памяти. Если требуемая информация отсутствует в ас­ социативных регистрах, то выполняется полная процеду­ ра обращения к страничной таблице. После того как из страничной таблицы будет найден номер физической страницы, в один из ассоциативных регистров вписыва­ ется только что полученная пара чисел 2а N-\-p и P(p,N); таким образом, в следующий раз доступ к данной физи­ ческой странице не потребует полной процедуры.

599