Околения компьютеров
 Скачать 1.67 Mb.
|
|
TLB (Translation Lookaside Buffer) – Буфер быстрого преобразования адресов. В процессоре есть буфер (не большой), который используется в качестве КЭШ таблицы страниц. Структура буфера: Каждая запись содержит 2 поля - №виртуальной страницы и № физической страницы. TLB буфер – буфер оперативной памяти. Поиск идет параллельно: за одну операцию просматривается наличие всей таблицы. Мы мимеем виртуальный адрес, в котором традиционно есть поле: «виртуальная страница» и есть поле «смещение». Процессор выбирает поле «виртуальная страница» и обращается к TLB буферу. Если мы фиксируем факт попадания, то в этом случае автоматически происходит замена поля виртуальной страницы на содержимое поля физической страницы – так мы получили физический адрес со всеми вытекающими параметрами, которые могут находиться в TLB. Если мы фиксируем промах, то в этом случае происходит прерывание, управление передается ОС. И ОС уже программно находит необходимую строчку и обновляет TLB буфер и соответственно дообрабатывает команду преобразования виртуального в физический. И И е е р р а а р р х х и и ч ч е е с с к к а а я я о о р р г г а а н н и и з з а а ц ц и и я я т т а а б б л л и и ц ц ы ы с с т т р р а а н н и и ц ц Проблема – размер таблицы страниц. Объем виртуальной памяти современногокомпьютера - 232,…264 Пример: Vстр. = 212 (4Kb) Количество виртуальных страниц – 220 (много) Решение – использование многоуровневых таблиц страниц (2х, 3х, 4х) TLB вирт. стр физ. стр. ... mis s hit VP offset Вирт. адрес: f p offset Физический адрес: Таблица страниц: Физическая память: ... V вирт. = 2 32 Современные системы используют многоуровневую организацию таблицы страниц. Система разделяет VP на 2 подполя: VP1 - индекс по внешней таблице страниц, а VP2 – смещение по странице, на которую указывает VP1. >4 уровней иерархии считается не целесообразно. Двухуровневая организация VP Offset Offset VP 1 VP 2 10 10 12 12 20 Смещение по странице, указанной через VP 1 Индекс по «внешней» таблице страниц Многоуровневая организация Суть многоуровневости достаточно простая: если мы имеем виртуальный адрес следующей структуры (на слайде): смещение 4кб и 20-ти разрядный адрес, то система разделяет поле виртуальной странички на два подполя. 1-е подполе – это индекс по внешней таблице страниц, через этот индекс мы попадаем на страничку, в которой находится продолжение описания этой таблицы; 2-е поле – это смещение по этой странице. Т.е. мы имеем внешнюю таблицу, по VP1 мы индексируемся и соответственно по содержимому этой таблицы попадаем на некоторую страницу, в которой находится часть таблицы страниц 2-го уровня. И по VP2 мы проходим смещение по этой странице и в соответствующем элементе получаем номер физической страницы. Этих уровней может быть 2, 3, 4. Больше 4-х считается нецелесообразным. Для 64-х разрядных машин таких уровней если их реализоввывать должно быть не менее 7, что совсем нецелесообразно. И И с с п п о о л л ь ь з з о о в в а а н н и и е е х х э э ш ш т т а а б б л л и и ц ц ХЭШ функции изначально использовались при организации таблицы имен. ХЭШ – функция берет номер виртуальной страницы и по этому номеру виртуальной страницы имеется некоторая функция, которая определяет номер записи хэш-таблицы. С этой записью связан список виртуальных страниц с их физическими страницами, которые имеют одинаковое значение хэш-функции. Это означает, что при преобразовании мы берем виртуальную страницу и фактически автоматически попадаем на этот самый список. Дальше по этому списку мы можем дойти до искомой страницы и получаем физическую страницу. Если в списке нет, то это означает, что и странички такой нет. И И н н в в е е р р т т и и р р о о в в а а н н н н ы ы е е т т а а б б л л и и ц ц ы ы с с т т р р а а н н и и ц ц Используется в более развитых системах, системах аппаратно поддерживающих pid обрабатываемого процесса. Каждая строка таблицы соответствует конкретной физической странице. Проблема – поиск по таблице З З а а м м е е щ щ е е н н и и е е с с т т р р а а н н и и ц ц Проблема загрузки «новой» страницы в память, если свободных мест в памяти нет. Необходимо выбрать страницу для удаления из памяти (с учетом ее модификации пр.) Алгоритм NRU (Not Recently Used – не использовавшийся в последнее время) Используются биты статуса страницы. R – обращение, М – модификация. Устанавливаются аппаратно при обращении или модификации. Алгоритм 1.При запуске процесса M и R для всех страниц процесса обнуляются 2.По таймеру происходит обнуление всех битов R 3.При возникновении страничного прерывания ОС делит все страниц на классы: •Класс 0: R=0; M=0; - не читался и не изменялся. •Класс 1: R=0; M=1; •Класс 2: R=1; M=0; •Класс 3: R=1; M=1; 4.Случайная выборка страницы для удаления в непустом классе с минимальным номером Стратегия:лучше выгрузить измененную страницу, к которой не было обращений как минимум в течение 1 «тика» таймера, чем часто используемую страницу ОС фиксирует время размещения страницы. Наиболее старую страницу удаляем, но это может быть неправильно, т.к. старая может часто использоваться, а новая - редко. Поэтому используется модификация этотого алгоритма. R – бит обращения. 1.Выбирается самая «старая страница». Если R=0, то она заменяется 2.Если R=1, то R – обнуляется, обновляется время загрузки страницы в память (т.е. переносится в конец очереди). На п.1 Алгоритм FIFO «Первым прибыл – первым удален» - простейший вариант FIFO. Для каждой страничке, которая была помещена в память, ОС фиксирует время ее размещения. Соответственно после этого наиболее старую страницу ОС удаляет. Это не очень справедливо (проблемы «справедливости»). Потому что в этом случае старая страница может активно использоваться и быть удалена. Поэтому реально используются модификации алгоритма FIFO. Модификация алгоритма (алгоритм вторая попытка): 1.Выбирается самая «старая страница». Если R=0, то она заменяется 2.Если R=1 (к ней обращения идут), то R – обнуляется, обновляется время загрузки страницы в память (т.е. считается, что она была загружена в момент обнуления признака чтения, т.е. фактически она переносится в конец очереди). На п.1 (начинаем смотреть следующую). Алгоритм «Часы» Алгоритм аналогичен предыдущему, только все страницы связаны в кольцевой список. Существует указатель (стрелка) на текущую страницу. Алгоритм LRU (Least Recently Used – «менее недавно» - наиболее давно используемая страница) Пусть в памяти N – страниц. Составляется битовая матрица NxN (изначально все биты обнулены). При каждом обращении к iой странице происходит присваивание 1 всем битам iой строки и обнуление всех битов iго столбца. Строка с наименьшим 2ным числом соответствует искомой странице. Алгоритм NFU (Not Frequently Used – редко использовавшаяся страница) Развитие предыдущего алгоритма. Для каждой физической страницы заводится программный счетчик, который изначально обнулен. По таймеру к счетчикам прибавляется признак доступа. В момент принятия решения выбирается страница с минимальным значением счетчика. Это все решается программно. Недостаток – если процесс поработал и «сидит без дела», то удалить его не удастся, а он не работает. Модификация: 1.Значение счетчика сдвигается на 1 разряд вправо. 2.Значение R добавляется в крайний левый разряд счетчика. Достоинства страничной памяти: - нет проблемы внешней фрагментации - никак не ограничены размерами физической памяти, т.е. мы часть страниц можем всегда держать во вне и через прерывания их закачивать, когда они нам нужны Недостатки: - проблема принятие решений об организации таблицы страниц - при страничной организации памяти адресное пространство представляет одну модель от 0 до Ν. Т.е. мы работаем с одним пространством адресации в этом процессе. В некоторых ситуациях это бывает не очень удобно. Билет 52. Управление ОП. Сегментное распределение. С С е е г г м м е е н н т т н н а а я я о о р р г г а а н н и и з з а а ц ц и и я я п п а а м м я я т т и и Основные концепции: •Виртуальное адресное пространство представляется в виде совокупности сегментов •Каждый сегмент имеет свою виртуальную адресацию (от 0 до N-1) •Виртуальный адрес: <номер_сегмента, смещение> Необходимые аппаратные средства для организации сегментной памяти достаточно концептуально просты. Это таблица сегментов, по которой при вычислении физического адреса из виртуального мы можем индексироваться по номеру сегмента. Соответственно каждая запись таблицы сегментов содержит размер сегмента и адрес начала сегмента. «+» простота реализации «+» размер таблицы сегментов может быть много меньше размера таблицы страниц «-» наличие внешней фрагментации «-»сегмент рассматривается как единое целое Преобразование происходит достаточно просто: мы индексируемся по таблице, получаем запись, после этого сравниваем смещение с размером сегмента: если смещение выходит за пределы размера – происходит прерывание, иначе мы значению базы прибавляем смещение и получаем физический адрес. Nseg offset size base Nseg Таблица сегментов offset > size да Прерывание нет base + offset Физический адрес Упрощенная модель Intel. Виртуальный адрес содержит 2 поля: селектор и смещение. Селектор содержит информацию о номере сегмента, о локализации. Поле Локализация это таблицы локальных дескрипторов (сегменты доступные для данного процесса) LDT (Local Descriptor Table) и Таблица глобальных дескрипторов (разделяемые между процессами сегменты) GDT (Global Descriptor Table). По LDT и GDT и виртуальному адресу мы вычисляем линейный адрес. Линейный адрес представляется в виде двухуровневой страничной организации. По этим параметрам мы вычисляем физический адрес. Сегменто - страничная организация памяти Виртуальный адрес содержит 2 поля: селектор и смещение. Селектор содержит информацию о номере сегмента, о локализации (есть 2 таблицы сегментов, который используются – это сегменты, которые доступны только для данного процесса, или сегменты, которые могут использоваться в разных процессах). При использовании алгоритма сегментно\страничной организации к плюсам страничной прибавляются плюсы сегментной. |