ДС18в14-виртуальная-память-Концепция (Лекции Северов Часть 1)

Виртуальная память 1: КонцепцияОсновы информатики.Компьютерные основы программированияgoo.gl/X7evFНа основе CMU 15-213/18-243:Introduction to Computer Systemsgoo.gl/Q7vgWwЛекция 14, 7 мая, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.rucs.mipt.ru/wp/?page_id=3461Виртуальная память – 1: понятия¢¢¢¢¢Пространства адресовВП как средство кешированияВП как средство управления памятьюВП как средство защиты памятиТрансляция адресов2Система с физической адресациейЦП...Основная память0:1:Физический адрес 2:3:(ФА)4:45:6:7:8:M-1:Слово данных¢Используется в “простых” системах – микроконтроллерах,встроенных в датчики, регуляторы света, часы3Системы с виртуальной адресациейКристалл ЦПЦПВиртуальный адрес(ВА)4100УУП(MMU)...Основная память0:1:2:Физический адрес3:(ФА)4:45:6:7:8:M-1:Слово данных¢¢Используется во всех современных серверах, ПК,смартфонахОдна из замечательных идей в информатике4Адресные пространства¢¢¢¢¢Линейное адресное пространство: Упорядоченное множествосмежных неотрицательных целых адресов: {0, 1, 2, 3 … }Виртуальное адресное пространство: Множество N = 2n виртуальныхадресов: {0, 1, 2, 3, …, N-1}Физическое адресное пространство: Множество M = 2m физическихадресов {0, 1, 2, 3, …, M-1}Четкое различием между данными (байтами) и их атрибутами(адресами)Каждый байт в основной памяти имеет:один физический адрес, один (или более) виртуальных адресов5Виртуальная память нужна, чтобы…¢использовать физическую память эффективно§ DRAM – кеш к частям виртуального пространства¢упростить управление памятью§ Каждый процесс получает типовой экземпляр линейного адресногопространства¢изолировать адресные пространства§ Один процесс не может обращаться к памяти другого§ Программы пользователей не имеют доступа привилегированнойинформациии ядра ОС6Виртуальная память – 1: понятия¢¢¢¢¢Пространства адресовВП как средство кешированияВП как средство управления памятьюВП как средство защиты памятиТрансляция адресов7ВП как средство кеширования¢¢Виртуальная память - массив N смежных байт на дискеСодержимое массива на диске кешируется в физическойпамяти (DRAM cache)§ Блоки этого кеша – страницы размером P = 2p байтВиртуальная памятьВС 0ВС 1ВС 2n-p-1Не используетсяЕсть в кешеОтсутствует в кешеНе используетсяЕсть в кешеОтсутствует в кешеЕсть в кешеОтсутствует в кешеФизическая память00СвободнаФС 0ФС 1СвободнаСвободнаM-1ФС 2m-p-1N-1Виртуальные страницы(ВС) на дискеФизические страницы(ФС) в DRAM8Организация DRAМ-кеша¢Определяется огромной ценой промаха§ DRAM на 1 порядок (10 раз) медленнее SRAM§ Диск на 4 порядка (10 тысяч раз) медленнее DRAM¢Следствия§ Большой размер страницы (блока): обычно 4-8 KB, иногда 4 MB§ Полностью ассоциативенлюбая ВС может быть размещена в любой ФС§ требует “большую” функцию отображения, в отличие от кешей ЦП§ Изощрённые, дорогостоящие алгоритмы замены§ Слишком сложные и неустоявшиеся для аппаратной реализации§ Write-back, но не write-through§9Таблица страниц¢Страничная таблица – массив табличных записей (PTE)отображений виртуальных страниц на физические.§ Отдельная для каждого процесса структура данных ядра ОС в DRAMНомерфизической страницыили адрес на дискев кешеPTE 0 0null110100PTE 7 1nullФизическая память(DRAM)ВС 1ВС 2ВС 7ВС 4ФС 0ФС 3Виртуальная память(диск)ВС 1Таблица страницв памяти (DRAM)ВС 2ВС 3ВС 4ВС 6ВС 710Страничное попадание¢Страничное попадание: ссылка на страницу ВП говорит,что страница находится в DRAM (попадание DRAM-кеша)Виртуальный адресНомерфизической страницыили адрес на дискев кешеPTE 0 0null110100PTE 7 1nullФизическая память(DRAM)ВС 1ВС 2ВС 7ВС 4ФС 0ФС 3Виртуальная память(диск)ВС 1Таблица страницв памяти (DRAM)ВС 2ВС 3ВС 4ВС 6ВС 711Страничный сбой¢Страничный сбой: ссылка на страницу ВП говорит, чтостраница отсутствует в DRAM (промах DRAM-кеша)Виртуальный адресНомерфизической страницыили адрес на дискев кешеPTE 0 0null110100PTE 7 1nullФизическая память(DRAM)ВС 1ВС 2ВС 7ВС 4ФС 0ФС 3Виртуальная память(диск)ВС 1Таблица страницв памяти (DRAM)ВС 2ВС 3ВС 4ВС 6ВС 712Обработка страничного сбоя – 1¢Страничный промах вызывает страничный сбой (исключение)Виртуальный адресНомерфизической страницыили адрес на дискев кешеPTE 0 0null110100PTE 7 1nullФизическая память(DRAM)ВС 1ВС 2ВС 7ВС 4ФС 0ФС 3Виртуальная память(диск)ВС 1Таблица страницв памяти (DRAM)ВС 2ВС 3ВС 4ВС 6ВС 713Обработка страничного сбоя – 2¢¢Страничный промах вызывает страничный сбой (исключение)Обработчик страничного сбоя выбирает жертву откачки (здесь ВС 4)Виртуальный адресНомерфизической страницыили адрес на дискев кешеPTE 0 0null110100PTE 7 1nullФизическая память(DRAM)ВС 1ВС 2ВС 7ВС 4ФС 0ФС 3Виртуальная память(диск)ВС 1Таблица страницв памяти (DRAM)ВС 2ВС 3ВС 4ВС 6ВС 714Обработка страничного сбоя - 3¢¢¢Страничный промах вызывает страничный сбой (исключение)Обработчик страничного сбоя выбирает жертву откачки (здесь ВС 4)Обработчик подкачивает с диска в память нужную страницу (здесь ВС 3)Виртуальный адресНомерфизической страницыили адрес на дискев кешеPTE 0 0null110100PTE 7 1nullФизическая память(DRAM)ВС 1ВС 2ВС 7ВС 3ФС 0ФС 3Виртуальная память(диск)ВС 1Таблица страницв памяти (DRAM)ВС 2ВС 3ВС 4ВС 6ВС 715Обработка страничного сбоя - 4¢¢¢¢Страничный промах вызывает страничный сбой (исключение)Обработчик страничного сбоя выбирает жертву откачки (здесь ВС 4)Обработчик подкачивает с диска в память нужную страницу (здесь ВС 3)Сбойная команда повторно выполняется : страничное попадание!Виртуальный адресНомерфизической страницыили адрес на дискев кешеPTE 0 0null110100PTE 7 1nullФизическая память(DRAM)ВС 1ВС 2ВС 7ВС 3ФС 0ФС 3Виртуальная память(диск)ВС 1Таблица страницв памяти (DRAM)ВС 2ВС 3ВС 4ВС 6ВС 716Размещение страниц¢Размещение новой страницы (ВС 5) виртуальной памяти.Номерфизической страницыили адрес на дискев кешеPTE 0 0null111000PTE 7 1Физическая память(DRAM)ВС 1ВС 2ВС 7ВС 3ФС 0ФС 3Виртуальная память(диск)Таблица страницв памяти (DRAM)ВС 1ВС 2ВС 3ВС 4ВС 5ВС 6ВС 717Локальность снова выручает!¢¢Виртуальная память работает благодаря локальностиВ каждый момент времени, программы стремятсядоступаться к набору активных виртуальных страниц –рабочему набору§ Программы с лучшей временной локальностью будут иметь рабочийнабор меньшего размера¢Если размер рабочего набора < размера основной памяти§ Хорошая производительность процесса после неизбежных промахов¢Если сумма размеров рабочих наборов > размераосновной памяти§ Пробуксовка (Thrashing): деградация производительности принепрерывной откачке/подкачке страниц18Виртуальная память – 1: понятия¢¢¢¢¢Пространства адресовВП как средство кешированияВП как средство управления памятьюВП как средство защиты памятиТрансляция адресов19ВП как средство управления памятью - 1¢Ключевая идея: каждому процессу – собственноевиртуальное адресное пространство§ память представляется простым линейным массивом§ отображение разбрасывает адреса по физической памятиудачные отображения упрощают распределение и управлениеТрансляция 00ФизическоеВиртуальноеадресовадресноеадресноеВС 1§пространстводля процесса 1:ВС 2ФС 2...пространство(DRAM)N-1ФС 6Виртуальноеадресноепространстводля процесса 2:0ФС 8ВС 1ВС 2......N-1(например, только читаемыйкод библиотеки)M-120ВП как средство управления памятью - 2¢Распределение памяти§ Любая виртуальная страница может отображаться на любую физическую§ Виртуальная отображается в различные физические в разное время¢Разделение кода и данных между процессами§ Отображение виртуальных страниц на одну физическую (здесь: ФС 6)Виртуальноеадресноепространстводля процесса 1:0ВС 1ВС 2Трансляцияадресов0ФС 2...Физическоеадресноепространство(DRAM)N-1ФС 6Виртуальноеадресноепространстводля процесса 2:0ФС 8ВС 1ВС 2......N-1(например, только читаемыйкод библиотеки)M-121Упрощение связывания и загрузкивиртуальная память ядра ОС¢СвязываниеСтек пользователя(создаётся при выполнении)§ Все программы имеют сходноевиртуальное адресноепространство§ Код, стек и разделяемые%rsp(указательстека)Область памятиразделяемых библиотекбиблиотеки всегда начинаются содинаковых адресов¢ПамятьнедоступнаяпользователюЗагрузка§ execve лишь резервируетКуча времени исполнения(создаётся malloc)виртуальные страницы и дляразделов .text and .data, т.е.помечает PTE как «не в кеше»Сегмент чтения/записи(.data, .bss)§ Разделы .text и .dataподгружаются, страница застраницей по требованиям0x08048000подсистемы виртуальной памяти0Сегмент только чтения(.init, .text, .rodata)brkЗагружены изисполняемогофайлаНе используется22Виртуальная память – 1: понятия¢¢¢¢¢Пространства адресовВП как средство кешированияВП как средство управления памятьюВП как средство защиты памятиТрансляция адресов23ВП как средство защиты памяти¢¢PTE дополняются битами-признаками разрешенийОбработчик сбоев страниц проверяет перед отображением§ При нарушении, отправляет процессу SIGSEGV (segmentation fault)Процесс i: Супер Чтение Запись Исполн.АдресВС 0:НетДаНетДаФС 6ВС 1:НетДаДаДаДаДа•••ДаФС 4НетФС 2ВС 2:ФизическоеадресноепространствоФС 2ФС 4Процесс j: Супер Чтение Запись Исполн.ФС 6AddressВС 0:НетДаНетДаФС 9ВС 1:ВС 2:ДаДаДаФС 6НетДаДаДаДаФС 11ФС 8ФС 9ФС 1124Виртуальная память – 1: понятия¢¢¢¢¢Пространства адресовВП как средство кешированияВП как средство управления памятьюВП как средство защиты памятиТрансляция адресов25Трансляция адресов ВП¢Виртуальное адресное пространство§ V = {0, 1, …, N–1}¢Физическое адресное пространство§ P = {0, 1, …, M–1}¢Трансляция адресов§ MAP: V → P U {∅}§ Для виртуального адреса a:§§MAP(a) = a’ если данные по виртуальному адресу a находятсяпо физическому адресу a’ в PMAP(a) = ∅ если данные по виртуальному адресу a отсутствуютв физической памяти – или их нет совсем, или они на диске26Обозначения трансляции адресов¢Основные параметры§ N = 2n : количество адресов в виртуальном адресном пространстве§ M = 2m : количество адресов в физическом адресном пространстве§ P = 2p : размер страницы (в байтах)¢Части виртуального адреса (VA)§§§§¢TLBI: индекс TLBTLBT: метка TLBVPO: сдвиг (от начала) виртуальной страницыVPN: номер виртуальной страницыЧасти физического адреса (PA)§§§§§PPO: сдвиг (от начала) физической страницы (тот же, что VPO)PPN: номер физической страницыCO: сдвиг байта (от начала) линии кешаCI: индекс кешаCT: метка кеша27Трансляция адресов с таблицей страницВиртуальный адресРегистр началатаблицы страницАдрестаблицы страницпроцессаn-1p p-1№ виртуальной страницы (VPN)0сдвиг в странице (VPO)Таблица страницв кеше№ физической страницы (PPN)бит «в кеше» = 0:страница не в DRAM(страничный сбой)m-1p p-1№ физической страницы (PPN)0сдвиг в странице (PPO)Физический адрес28Трансляция адресов: страничное попадание2Адрес PTEКристалл ЦПЦП1ВиртуальныйадресУУП(MMU)PTE3Физическийадрес4Кеш/ПамятьДанные51) Процессор направляет виртуальный адрес УУП2-3) УУП считывает PTE из таблицы страниц в памяти4) УУП направляет физический адрес кешу/памяти5) Кеш/память направляют данные процессору29Трансляция адресов: страничный сбойИсключениеОбработчикстраничного сбоя42Адрес PTEКристалл ЦПЦП1ВиртуальныйадресУУП(MMU)PTE3страница жертваКеш/Память75Дискноваястраница61) Процессор направляет виртуальный адрес УУП2-3) УУП считывает PTE из таблицы страниц в памяти4) Бит «в кеше» - нулевой, УУП запускает исключение «страничный сбой»5) Обработчик выбирает жертву (и, если менялась, откачивает на диск)6) Обработчик подкачивает новую страницу и меняет PTE в памяти7) Обработчик возвращается в процесс для повтора сбойной команды30Объединение ВП и кешаPTEКристалл ЦПЦПВиртуальныйадресПопаданиеPTE адресаАдрес PTEУУП(MMU)ФизическийадресПромахPTE адресаПромахФиз.адресаПопаданиеФиз.адресаДанныеPTEАдрес PTEФизическийадресДанныеПамятьКешуровня 1PTE: запись в таблице страниц31Ускорение трансляции с помощью TLB¢Записи в таблице страниц (PTE) кешируются в уровне 1 каклюбое другое слово памяти§ PTE могут выталкиваться обращениями к другим данным§ попадание PTE всё ещё требует небольшой задержки уровня 1¢Решение: Translation Lookaside Buffer (TLB)§ небольшой аппаратный кеш в УУП (MMU)§ отображает номера виртуальных страниц в номера физических§ содержит целиком записи для небольшого количества страниц32Доступ к TLB¢УУП использует часть VPN в виртуальном адресе длядоступа к TLB:T = 2t наборовVPNTLBT сравниваетсяс меткой линии внабореНабор 0Набор 1vметкаvPTEметкаPTEНабор T-1 vметкаPTEp+t p+t-1p p-1TLB метка (TLBT) TLB индекс (TLBI)метка0VPOPTEvметкаPTEvметкаPTEпо TLBI выбираетсянабор…vn-133Попадание TLBКристалл ЦПTLB2Номервирт.