Чем запись в таблице страниц в схеме виртуальной памяти отличается от соответствующей

Обновлено: 04.07.2024

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

СОДЕРЖАНИЕ

Роль таблицы страниц

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

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

Процесс перевода

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

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

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

Ошибки перевода

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

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

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

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

  • Попытка записи, когда в таблице страниц установлен бит только для чтения, вызывает сбой страницы. Это обычная часть реализации копирования при записи во многих операционных системах ; это также может произойти, когда запись выполняется в место, из которого процессу разрешено читать, но в которое ему не разрешено писать, и в этом случае сигнал доставляется процессу.
  • Попытка выполнить код, когда в таблице страниц установлен бит NX ( бит запрета выполнения) в таблице страниц, вызывает сбой страницы. Это может использоваться операционной системой в сочетании с битом только для чтения, чтобы обеспечить возможность записи XOR Execute, которая останавливает некоторые виды эксплойтов.

Данные таблицы кадров

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

Данные таблицы страниц

Таблица страниц - это массив записей таблицы страниц.

Запись в таблице страниц

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

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

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

Типы таблиц страниц

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

Таблицы перевернутых страниц

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

IPT объединяет таблицу страниц и таблицу фреймов в одну структуру данных. По своей сути это таблица фиксированного размера с количеством строк, равным количеству кадров в памяти. Если имеется 4 000 фреймов, в перевернутой таблице страниц будет 4 000 строк. Для каждой строки есть запись для номера виртуальной страницы (VPN), номера физической страницы (не физического адреса), некоторых других данных и средств для создания цепочки конфликтов , как мы увидим позже.

Поиск по всем записям базовой структуры IPT неэффективен, и хеш-таблица может использоваться для сопоставления виртуальных адресов (и информации адресного пространства / PID, если необходимо) с индексом в IPT - здесь используется цепочка конфликтов. . Эта хеш-таблица известна как хеш-таблица привязки . Функция хеширования обычно не оптимизирована для покрытия - более желательна чистая скорость. Конечно, в хеш-таблицах возникают коллизии. Из-за этой выбранной функции хеширования мы можем столкнуться с множеством конфликтов при использовании, поэтому для каждой записи в таблице предоставляется VPN, чтобы проверить, является ли это поисковой записью или коллизией.

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

Виртуальный адрес в этой схеме можно разделить на два, первая половина - это номер виртуальной страницы, а вторая половина - смещение на этой странице.

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

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

Таблицы перевернутых страниц используются, например, в PowerPC , UltraSPARC и архитектуре IA-64 .

В каких случаях производится невытесняющее кратковременное планирование процессов?

  • (Правильный ответ) когда процесс переводится из состояния исполнение в состояние ожидание
  • когда процесс переводится из состояния ожидание в состояние готовность
  • (Правильный ответ) когда процесс переводится из состояния исполнение в состояние завершил исполнение

Планирование заданий стало возможным:

  • с появлением систем пакетной обработки
  • (Правильный ответ) с появлением предварительной записи пакета заданий на магнитный диск
  • с появлением предварительной записи пакета заданий на магнитную ленту

Возможность интерактивного взаимодействия пользователя и программы возникает с появлением:

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

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

Какие процессы могут обмениваться информацией через pipe?

  • произвольные процессы в системе
  • только процесс, создавший pipe, и его непосредственный процесс-ребенок
  • (Правильный ответ) только процессы, имеющие общего родителя, создавшего pipe

Какие из условий для организации корректного взаимодействия двух процессов с помощью программного алгоритма выполнены для алгоритма «флаги готовности»?

  • условие прогресса
  • (Правильный ответ) условие взаимоисключения
  • условие ограниченного ожидания

Условные переменные в мониторах Хора обычно используются:

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

В операционных системах, поддерживающих нити исполнения (threads) внутри одного процесса на уровне ядра системы, процесс находится в состоянии готовность, если:

  • хотя бы одна нить исполнения находится в состоянии готовность, и нет ни одной нити в состоянии ожидание
  • (Правильный ответ) хотя бы одна нить процесса находится в состоянии готовность, и нет ни одной нити в состоянии исполнение.
  • хотя бы одна нить процесса находится в состоянии готовность

Термин «критическая секция» относится:

  • к участку процесса, в котором процесс совместно с другими процессами использует разделяемые переменные
  • к участку процесса с наибольшим объемом вычислительной работы
  • (Правильный ответ) к участку процесса, выполнение которого совместно с другими процессами может привести к неоднозначным результатам

В функциях-методах мониторов Хора обычно реализовываются

  • только прологи и эпилоги критических участков
  • только различные операции над внутренними переменными монитора (как операции над внутренними переменными класса в ООП)
  • (Правильный ответ) критические участки взаимодействующих процессов

Рассмотрим механизм синхронизации, называемый бинарными семафорами. Бинарный семафор — это семафор, который может принимать всего два значения: 0 и 1 . Операция P для этого семафора выглядит так же, как и для семафора Дейкстры, а операция V заключается в простом присваивании семафору значения 1 . Бинарные семафоры

  • обладают большими возможностями, чем семафоры Дейкстры
  • (Правильный ответ) эквивалентны семафорам Дейкстры
  • обладают меньшими возможностями, чем семафоры Дейкстры

Какое из условий для организации корректного взаимодействия двух процессов с помощью программного алгоритма выполнено для алгоритма «переменная-замок»?

  • условие ограниченного ожидания
  • условие взаимоисключения
  • (Правильный ответ) условие прогресса

В вычислительной системе стартует несколько процессов, взаимодействие которых организовано с помощью монитора Хора. Сколько процессов будет находиться в состоянии ожидание, если после старта процессов над условной переменной монитра выполнить последовательность операций signal, wait, signal, wait ?

В вычислительной системе со страничной организацией памяти и 32-х битовым адресом размер страницы составляет 8 Mбайт. Для некоторого процесса таблица страниц в этой системе имеет вид:

Номер страницы
Адрес начала страницы

1 0x00000000 2 0x02000000 5 0x06000000 6 0x10000000

Какому физическому адресу соответствует логический адрес 0х00827432 ?

  • 0x02027432
  • (Правильный ответ) 0x27432
  • 0x10027432

Чем обусловлена эффективность иерархической схемы памяти?

  • скоростью обмена с оперативной памятью
  • количеством уровней в иерархии
  • (Правильный ответ) принципом локальности

На каком уровне иерархии памяти находится выполняющаяся часть кода процесса в состоянии исполнение

  • разные компоненты программы могут находиться на различных уровнях
  • (Правильный ответ) в оперативной памяти
  • на магнитном диске

Чем обычно определяется максимальный размер сегмента?

  • размером свободной оперативной памяти
  • размером оперативной памяти
  • (Правильный ответ) разрядностью архитектуры компьютера

Для некоторого процесса, запущенного в вычислительной системе со страничной организацией памяти с использованием LRU алгоритма замещения страниц, выделение процессу 4 кадров памяти приводит к 11 page faults, а выделение 6 кадров памяти – к 9 page faults(вначале все кадры свободны). Какой (какие) вариант(ы) количества page faults для того же процесса и того же количества кадров может быть получен при использовании OPT алгоритма замещения страниц?

  • 9 и 6
  • (Правильный ответ) 8 и 7
  • 7 и 8
  • 12 и 8

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

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

Главная задача файловой системы:

  • (Правильный ответ) связывание имени файла с выделенным ему пространством внешней памяти
  • обеспечение совместного доступа к файлам
  • обеспечение защиты от несанкционированного доступа

В вычислительной системе с двухуровневой страничной организацией памяти среднее время доступа процессора к одному данному составляет 185 нс. Частота попаданий в ассоциативную память при обращении к данным (hit ratio) составляет 75%. Оцените время доступа процессора к оперативной памяти, если время обращения к ассоциативной памяти равно 20 нс.

  • 120 нс
  • 100нс
  • (Правильный ответ) 110 нс

Какие из перечисленных функций базовой подсистемы ввода-вывода могут быть делегированы драйверам:

  • поддержка блокирующихся, неблокирующихся и асинхронных системных вызовов
  • (Правильный ответ) обработка ошибок и прерываний, возникающих при операциях ввода-вывода
  • осуществление spooling’а и монопольного захвата внешних устройств

Сколько удаленных адресов может иметь сетевой компьютер?

  • только один
  • (Правильный ответ) потенциально произвольное количество
  • не более двух

Какие операционные системы позволяют взаимодействовать удаленным процессам и имеют сходное строение с автономными вычислительными системами?

  • (Правильный ответ) сетевые операционные системы
  • операционные системы, поддерживающие работу многопроцессорных вычислительных систем
  • распределенные операционные системы

Какие из перечисленных ситуаций обнаруживаются процессором между выполнением команд?

  • (Правильный ответ) прерывания
  • исключительные ситуации
  • программные прерывания

Какие из условий для организации корректного взаимодействия двух процессов с помощью программного алгоритма выполнены для алгоритма «строгое чередование»?

  • (Правильный ответ) условие взаимоисключения
  • (Правильный ответ) условие ограниченного ожидания
  • условие прогресса

Из какого состояния процесс может перейти в состояние «ожидание»?

  • из состояния «готовность»
  • (Правильный ответ) из состояния «исполнение»
  • из состояния «рождение»

Какие из перечисленных алгоритмов могут быть использованы при невытесняющем кратковременном планировании процессов

Что такое мультипрограммная вычислительная система?

  • система, в памяти которой находится несколько программ, чье исполнение чередуется по прошествии определенного промежутка времени
  • система, в которой реализован спулинг (spooling)
  • (Правильный ответ) система, в памяти которой одновременно находится несколько программ. Когда одна из программ ожидает завершения операции ввода-вывода, другая программа может исполняться

При помощи списка прав доступа операционная система обеспечивает:

  • доступ к файлу только определенного числа процессов
  • каждый процесс списком файлов, к которым он может иметь доступ
  • (Правильный ответ) защиту файлов от несанкционированного доступа
  • 6 и 0
  • (Правильный ответ) 7 и 0
  • 5 и 4096

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

  • (Правильный ответ) алгоритмы лавинной маршрутизации
  • алгоритмы состояния связей
  • маршрутизация от источника данных

Для чего применяется журнализация в файловых системах?

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

Файл autoexec.bat, который обычно входит в состав файлов корневого каталога во многих ОС компании Microsoft, относится к категории:

  • системных справочников, поддерживающих структуру файловой системы
  • специальных символьных файлов
  • (Правильный ответ) обычных файлов

Предположим, что сетевой сервер затоплен мощным потоком запросов. К какой категории атак относится это действие:

  • попытка нарушить функционирование системы при помощи программ- «червей»
  • (Правильный ответ) атака типа отказ в обслуживании
  • попытка проникновения в систему под видом легального пользователя

Схема выделения дискового пространства связным списком блоков не нашла широкого применения, так как:

  • неэффективно использует дисковое пространство
  • (Правильный ответ) требует большого количества обращений к диску при работе с файлами
  • страдает от внутренней фрагментации

Среди несимметричных алгоритмов шифрования наиболее известен:

Пусть в вычислительную систему поступают пять процессов различной длительности по следующей схеме:

Номер процесса
Момент поступления в систему
Время исполнения

Чему равно среднее время ожидания процесса (waiting time) при использовании вытесняющего алгоритма SJF? При вычислениях считать, что процессы не совершают операций ввода-вывода, временем переключения контекста пренебречь.

1) V – признак присутствия, определяет загружена ли страница в основой памяти или нет (1 –данная виртуальная страница находится в ОП; в этом случае в поле номера физической страницы находится номер страницы ОП; 0 – виртуальная страница отсутствует в основной памяти, генерируется сигнал страничного сбоя (PF), по нему происходит замена, т.е. данная виртуальная страница загружается в ОП через карту диска) и далее V = 1. 2) R – признак использования страницы, устанавливается при обращении к данной странице, информация эта используется при замещении страницы в основной памяти; по данному признаку анализируется, какую страницу выпускать из ОП, если нужно записать другую страницу (см. КЭШ). 3) M – признак модификации (“грязная страница”), данное поле работает, как в КЭШ памяти, определяет была ли изменена страница в процессе работы. 0 – страница не изменялись; 1 – страница изменялись. Если 1 (страница ВП изменялись), то выполняется перезапись данных во внешнюю память. Иначе – сохранять не надо, ее копия уже лежит на диске 4) A – признак прав доступа, данный признак используется с целью защиты информации и определяет, какой вид доступа разрешен в этой таблице (например, 0 – read/write, 1 – read only). Кроме того в страничной таблице содержатся и другие признаки (для защиты) : 5) U/S пользователь/супервизор. Определяет уровень привилегий страницы. Используется для защиты системных страниц (вариант Intel – номер кольца защиты ring 0-3). 6) R/W/Х чтение/запись/исполнение. Атрибуты страницы (ограничивает доступ). Достоинства: а) не нужно хранить размер блока. б) в таблице указывается не начальный адрес, а номер блока виртуальной памяти. в) аналогично для файла подкачки. г) не надо проверять влезет ли блок в свободное пространство. Недостатки : при страничной организации памяти вся ВП рассматривается как непрерывное линейное пространство, ОДНАКО специфика некоторых программ требует, чтобы реализация была другой. Поэтому возникла сегментная организация. Для того, чтобы сократить число обращений к ТОС в процессор вводят специальный кэш страниц (ассоциативная таблица, признак ассоциативного поиска – номер виртуальной страницы).


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

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

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

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

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

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

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

18. Какие существуют варианты организации и использования таблиц страниц?

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

1. Многоуровневая таблица страниц

Для примера рассмотрим двухуровневую таблицу с размером страниц 4 Кбайт, реализованную в 32-разрядной архитектуре Intel. Таблица, состоящая из 2 20 строк, разбивается на 2 10 таблиц второго уровня по 2 10 строк. Эти таблицы второго уровня объединены в общую структуру при помощи одной таблицы первого уровня, состоящей из 2 10 строк. 32-разрядный адрес делится на 10-разрядное поле p1, 10-разрядное поле p2 и 12-разрядное смещение d. Поле p1 указывает на нужную строку в таблице первого уровня, поле p2– второго, а поле d локализует нужный байт внутри указанного страничного кадра.

При помощи всего лишь одной таблицы второго уровня можно охватить 4 Мбайт (4 Кбайт x 1024) оперативной памяти. Таким образом, для размещения процесса с большим объемом занимаемой памяти достаточно иметь в памяти одну таблицу первого уровня и несколько таблиц второго уровня.

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

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

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

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

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

3. Инвертированная таблица страниц

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

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

Читайте также: