Виртуальная память

Июль 22, 2022

Главная
Информатика
Виртуальная память

Содержание

2. ИУС ФТК Коликова Т.В. О чем Введение Управление памятью Трансляция адресов Ассоциативный буфер трансляции Стратегия подкачки
3. ИУС ФТК Коликова Т.В. Виртуальная память Нельзя выполнить программу, размер которой > размера физической памяти Виртуальная
4. ИУС ФТК Коликова Т.В. Виртуальная память физическая и логическая структура Способ, которым ОС транслирует одну структуру
5. ИУС ФТК Коликова Т.В. Виртуальное адресное пространство (virtual address space)– это набор адресов памяти, которые могут
6. ИУС ФТК Коликова Т.В. Виртуальная память Система виртуальной памяти должна: Транслировать, или отображать (map) определяет по
7. ИУС ФТК Коликова Т.В. Виртуальная память Медленно перемещать по одному байту Виртуальное адресное пространство разделено на
8. ИУС ФТК Коликова Т.В. Виртуальная память Страницы, находящиеся в физической памяти и доступные немедленно, называются действительными
9. ИУС ФТК Коликова Т.В. Виртуальная память
10. ИУС ФТК Коликова Т.В. Виртуальная память При обращении потока по виртуальному адресу, который находится на недействительной
11. ИУС ФТК Коликова Т.В. Виртуальная память Обработка страничной ошибки – это дорогая операция, которая требует много
12. ИУС ФТК Коликова Т.В. Виртуальная память
13. ИУС ФТК Коликова Т.В. Управление памятью Диспетчер виртуальной памяти предоставляет набор базовых сервисов. Эти сервисы позволяют
14. ИУС ФТК Коликова Т.В. Windows API Memory Management Architecture Windows Program C library: malloc, free Heap
15. ИУС ФТК Коликова Т.В. Windows Memory Management Windows maintains pools of memory in heaps A process
16. ИУС ФТК Коликова Т.В. Managing Heap Memory dwFlags: HEAP_GENERATE_EXCEPTION, raise SEH on memory allocation failure STATUS_NO_MEMORY,
17. ИУС ФТК Коликова Т.В. Управление памятью Диспетчер виртуальной памяти выделяет память в два этапа: резервирование. Зарезервированная
18. ИУС ФТК Коликова Т.В. Управление памятью Резервирование памяти полезно при создании динамических структур данных Поток резервирует
19. ИУС ФТК Коликова Т.В. Трансляция адресов Приложения используют 32-разрядные виртуальные адреса С помощью структур данных создаваемых
20. ИУС ФТК Коликова Т.В. Трансляция адресов
21. ИУС ФТК Коликова Т.В. Paging Example Page 0 Page 1 Page 2 Page 3 logical memory
22. ИУС ФТК Коликова Т.В. Free Frames Before allocation After allocation Page 2 physical memory Page 0
23. ИУС ФТК Коликова Т.В. Valid (v) or Invalid (i) Bit in a Page Table Page 0
24. ИУС ФТК Коликова Т.В. Трансляция адресов Для трансляции виртуальных адресов в физические используется двухуровневая таблица страниц
25. ИУС ФТК Коликова Т.В. Two-Level Page-Table Scheme … … … … outer page table (page directory)
26. ИУС ФТК Коликова Т.В. Address-Translation Scheme Address-translation scheme for a two-level 32-bit paging architecture page number
27. ИУС ФТК Коликова Т.В. x86 Virtual Address Translation Page table selector Page table entry selector Byte
28. ИУС ФТК Коликова Т.В. Трансляция адресов
29. ИУС ФТК Коликова Т.В. Трансляция адресов Индекс каталога страниц (page directory index) применяется для поиска таблицы
30. ИУС ФТК Коликова Т.В. Трансляция адресов При трансляции виртуального адреса: Определяется адрес каталога страниц текущего процесса.
31. ИУС ФТК Коликова Т.В. Трансляция адресов Индекс таблицы страниц используется как указатель для поиска PTE, который
32. ИУС ФТК Коликова Т.В. Ассоциативный буфер трансляции Трансляция каждого адреса требует двух операций поиска: сначала нужно
33. ИУС ФТК Коликова Т.В. Ассоциативный буфер трансляции
34. ИУС ФТК Коликова Т.В. Paging Hardware With TLB CPU f d p d Physical memory Logical
35. ИУС ФТК Коликова Т.В. Byte within page Virtual page number Virtual Address Translation The hardware converts
36. ИУС ФТК Коликова Т.В. Ассоциативный буфер трансляции Виртуальные адреса объединяются в страницы по 2¹²( 4Кб ),
37. ИУС ФТК Коликова Т.В. Стратегия подкачки и рабочие наборы Обычно система виртуальной памяти определяет три типа
38. ИУС ФТК Коликова Т.В. Стратегия подкачки и рабочие наборы Стратегия считывания (fetch policy) определяет, когда надо
39. ИУС ФТК Коликова Т.В. Стратегия подкачки и рабочие наборы Диспетчер виртуальной памяти Windows использует алгоритм подкачки
40. ИУС ФТК Коликова Т.В. Стратегия подкачки и рабочие наборы При возникновении страничной ошибки система виртуальной памяти
41. ИУС ФТК Коликова Т.В. Стратегия подкачки и рабочие наборы Если страничная ошибка происходит, когда вся физическая
42. ИУС ФТК Коликова Т.В. Стратегия подкачки и рабочие наборы В первом случае необходимо, чтобы система виртуальной
43. ИУС ФТК Коликова Т.В. Стратегия подкачки и рабочие наборы Стратегии замещения делятся на: локальные (local replacement
44. ИУС ФТК Коликова Т.В. Стратегия подкачки и рабочие наборы В случае стратегии глобального замещения для обработки
45. ИУС ФТК Коликова Т.В. Стратегия подкачки и рабочие наборы Стратегия глобального замещения создает ряд проблем: процессы
46. ИУС ФТК Коликова Т.В. Стратегия подкачки и рабочие наборы Минимальный размер рабочего набора - минимальное число
47. ИУС ФТК Коликова Т.В. База данных страничных фреймов Таблицы страниц процесса содержат информацию о том, в
48. ИУС ФТК Коликова Т.В. База данных страничных фреймов Для этого используется база данных страничных фреймов (page
49. ИУС ФТК Коликова Т.В. База данных страничных фреймов Некоторые недействительные элементы таблицы страниц также ссылаются на
50. ИУС ФТК Коликова Т.В. База данных страничных фреймов
51. ИУС ФТК Коликова Т.В. База данных страничных фреймов Недействительные элементы таблицы страниц содержат адреса на диске,
52. ИУС ФТК Коликова Т.В. База данных страничных фреймов Резервный – данный фрейм использовался процессом, но был
53. ИУС ФТК Коликова Т.В. База данных страничных фреймов В базе данных страничные фреймы, находящиеся в одном
54. ИУС ФТК Коликова Т.В. База данных страничных фреймов В данные списки включены все страничные фреймы, которые
55. ИУС ФТК Коликова Т.В. База данных страничных фреймов
56. ИУС ФТК Коликова Т.В. База данных страничных фреймов Если диспетчеру виртуальной памяти требуется инициализированный нулями страничный
57. ИУС ФТК Коликова Т.В. База данных страничных фреймов
58. ИУС ФТК Коликова Т.В. База данных страничных фреймов Когда количество страниц в списках обнуленных, свободных и
59. ИУС ФТК Коликова Т.В. Paging Dynamics Standby Page List Zero Page List Free Page List Process
60. ИУС ФТК Коликова Т.В. Дескрипторы виртуальных адресов Момент загрузки страниц в память диспетчер памяти определяет, используя
61. ИУС ФТК Коликова Т.В. Дескрипторы виртуальных адресов Диспетчер памяти использует этот же механизм и при формировании
62. ИУС ФТК Коликова Т.В. Дескрипторы виртуальных адресов Как же тогда диспетчер виртуальной памяти определяет какие адреса
64. Скачать презентацию

Слайд 2

ИУС ФТК Коликова Т.В.
О чем
Введение
Управление памятью
Трансляция адресов
Ассоциативный буфер трансляции
Стратегия подкачки и

рабочие наборы
База данных страничных фреймов
Дескрипторы виртуальных адресов

Слайд 3

ИУС ФТК Коликова Т.В.
Виртуальная память
Нельзя выполнить программу, размер которой > размера

физической памяти
Виртуальная память – это централизованная система выгрузки на диск содержимого памяти при переполнении последней
Можно создавать и запускать “большие”
программы

Слайд 4

ИУС ФТК Коликова Т.В.
Виртуальная память
физическая и логическая структура
Способ, которым ОС транслирует

одну структуру в другую
Физическая память - последовательность однобайтовых ячеек
Логическая память или виртуальная память (virtual memory) – это способ представления памяти для программы
В современных ОС она не совпадает с физической структурой памяти
Системы виртуальной памяти используют:
cегментное
линейное представление памяти

Слайд 5

ИУС ФТК Коликова Т.В.
Виртуальное адресное пространство (virtual address space)– это набор

адресов памяти, которые могут использовать потоки процесса
Каждый процесс имеет отдельное адресное пространство > физической памяти
Диапазон физических адресов компьютера (у каждого байта уникальный адрес)
Диапазон виртуальных адресов – количество битов в адресе (32-разрядный адрес - в 4 Гб)

Виртуальная память

Слайд 6

ИУС ФТК Коликова Т.В.
Виртуальная память
Система виртуальной памяти должна:
Транслировать, или отображать (map)
определяет

по виртуальному адресу соответствующий физический адрес
Выгружать на диск часть содержимого памяти

Слайд 7

ИУС ФТК Коликова Т.В.
Виртуальная память
Медленно перемещать по одному байту
Виртуальное адресное

пространство разделено на блоки равного размера - страницы (pages)
Физическое адресное пространство разделяется на блоки - страничные фреймы (page frames)

Слайд 8

ИУС ФТК Коликова Т.В.
Виртуальная память
Страницы, находящиеся в физической памяти и доступные

немедленно, называются действительными страницами (valid pages)
Страницы, находящиеся на диске (или находящиеся в памяти, но недоступные немедленно), называются недействительными (invalid pages)

Слайд 9

ИУС ФТК Коликова Т.В.
Виртуальная память

Слайд 10

ИУС ФТК Коликова Т.В.
Виртуальная память
При обращении потока по виртуальному адресу, который

находится на недействительной странице процессор генерирует страничную ошибку (page fault)
Система виртуальной памяти находит нужную страницу на диске и загружает ее в свободный страничный фрейм физической памяти
Когда остается мало доступных страничных фреймов, система виртуальной памяти выбирает фреймы, которые можно освободить и копирует их содержимое на диск
Этот процесс называется подкачкой страниц (paging)

Слайд 11

ИУС ФТК Коликова Т.В.
Виртуальная память
Обработка страничной ошибки – это дорогая операция,

которая требует много тактов процессора
Можно снизить затраты за счет выбора оптимального размера страницы
При большем размере страницы мы загружаем в память большее количество данных и, поэтому страничные ошибки будут возникать реже
Но при слишком большом размере, мы можем загрузить лишние данные
Оптимальный размер – 4Кб

Слайд 12

ИУС ФТК Коликова Т.В.
Виртуальная память

Слайд 13

ИУС ФТК Коликова Т.В.
Управление памятью
Диспетчер виртуальной памяти предоставляет набор базовых сервисов.

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

Слайд 14

ИУС ФТК Коликова Т.В.
Windows API Memory Management Architecture
Windows Program
C library: malloc,

free

Heap API:
HeapCreate,HeapDestroy,
HeapAlloc, HeapFree

Virtual Memory API

Memory-Mapped Files API:
CreateFileMapping,
CreateViewOfFile

Windows Kernel with
Virtual Memory Manager

Physical Memory

Disc &
File System

Слайд 15

ИУС ФТК Коликова Т.В.
Windows Memory Management
Windows maintains pools of memory in

heaps
A process can contain several heaps
C library functions manage default heap: malloc, free, calloc
Heaps are Windows objects – have handle
Each process has own default heap
Return value of NULL indicates failure (instead of INVALID_HANDLE_VALUE)

HANDLE GetProcessHeap( VOID );
HANDLE HeapCreate (DWORD floptions, DWORD dwInitialSize, DWORD dwMaximumSize);
BOOL HeapDestroy( HANDLE hHeap );

Слайд 16

ИУС ФТК Коликова Т.В.
Managing Heap Memory
dwFlags:
HEAP_GENERATE_EXCEPTION,
raise SEH on memory allocation

failure
STATUS_NO_MEMORY, STATUS_ACCESS_VIOLATION
HEAP_NO_SERIALIZE:
no serialization of concurrent (multithreaded) requests
HEAP_ZEROC_MEMORY: initialize allocated memory to zero
dwSize:
Block of memory to allocate
For non-growable heaps: 0x7FFF8 (0.5 MB)
HeapFree(), HeapReAlloc(),
HeapCompact(), HeapValidate()

LPVOID HeapAlloc( HANDLE hHeap,
DWORD dwFlags,
DWORD dwBytes );

HeapLock(), HeapUnlock():
Manage concurrent accesses
to heap

Слайд 17

ИУС ФТК Коликова Т.В.
Управление памятью
Диспетчер виртуальной памяти выделяет память в два

этапа:
резервирование. Зарезервированная память (reserved memory) – это набор виртуальных адресов, которые диспетчер виртуальной памяти зарезервировал для использования процессом. Это быстрая и дешевая операция.
передача. Переданной памятью (committed memory) называется память, для которой диспетчер виртуальной памяти выделил место в файле подкачки (paging file) – файле на диске, в который он записывает виртуальные страницы, когда их надо удалить из памяти
Поток может сразу зарезервировать и передать виртуальную память, либо вначале зарезервировать ее, а передавать по мере необходимости

Слайд 18

ИУС ФТК Коликова Т.В.
Управление памятью
Резервирование памяти полезно при создании динамических структур

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

Слайд 19

ИУС ФТК Коликова Т.В.
Трансляция адресов
Приложения используют 32-разрядные виртуальные адреса
С помощью структур

данных создаваемых и поддерживаемых диспетчером памяти, происходит трансляция этих виртуальных адресов в физические
Каждый виртуальный адрес сопоставляется со структурой системного пространства, которая называется элементом таблицы страниц (page table entry, PTE)
Она и содержит физический адрес, соответствующий виртуальному

Слайд 20

ИУС ФТК Коликова Т.В.
Трансляция адресов

Слайд 21

ИУС ФТК Коликова Т.В.
Paging Example
Page 0
Page 1
Page 2
Page 3
logical memory
Page 0
Page

physical memory

Page 1

Page 3

frame number

page table

Слайд 22

ИУС ФТК Коликова Т.В.
Free Frames
Before allocation
After allocation
Page 2
physical memory
Page 0
Page 3
frame number
10
11
12
13
14
15
16
17
Page 1
7
8
9
10
11
12
13
14
15
16
17
7
8
9
Free

frame list 7, 8, 10, 11,13, 16

Free frame list 7, 10

New process page table

Process creation

Слайд 23

ИУС ФТК Коликова Т.В.
Valid (v) or Invalid (i) Bit in a

Page Table

Page 0

Page 1

Page 2

Page 3

logical memory

Page 0

Page 2

physical memory

Page 1

Page 3

frame number

page table

Invalid pages may be paged out

Слайд 24

ИУС ФТК Коликова Т.В.
Трансляция адресов
Для трансляции виртуальных адресов в физические используется

двухуровневая таблица страниц
Виртуальный 32-разрядный адрес состоит из трех элементов:
индекса каталога страниц
индекса таблицы страниц
индекса байта

Слайд 25

ИУС ФТК Коликова Т.В.
Two-Level Page-Table Scheme
…
…
…
…
outer page table (page directory)
page tables
memory

Слайд 26

ИУС ФТК Коликова Т.В.
Address-Translation Scheme
Address-translation scheme for a two-level 32-bit paging

architecture

page number

page offset

12
page directory
page table

Main memory

Слайд 27

ИУС ФТК Коликова Т.В.
x86 Virtual Address Translation
Page table
selector
Page table
entry selector
Byte within

page

Page Directory
(one per process, 1024 entries)

Page Tables
(up to 512 per process,
plus up to 512 system-wide)

Physical Pages
(up to 2^20)

CR3

physical
address

PFN 0

31 0

Слайд 28

ИУС ФТК Коликова Т.В.
Трансляция адресов

Слайд 29

ИУС ФТК Коликова Т.В.
Трансляция адресов
Индекс каталога страниц (page directory index) применяется

для поиска таблицы страниц, содержащий PTE для данного виртуального адреса
С помощью индекса таблицы страниц (page table index) осуществляется поиск PTE, который содержит физический адрес, по которому проецируется виртуальная страница
Индекс байта (byte index) позволяет найти конкретный адрес на физической странице
У каждого процесса есть один каталог страниц (page directory), который представляет собой страницу с адресами всех таблиц страниц для данного процесса

Слайд 30

ИУС ФТК Коликова Т.В.
Трансляция адресов
При трансляции виртуального адреса:
Определяется адрес каталога страниц

текущего процесса. При переключении контекста процесса ОС заносит этот адрес в специальный регистр процессора
Индекс каталога страниц используется для поиска элемента каталога страниц (page directory entry, PDE). Он указывает на ту таблицу страниц, которая нужна для трансляции виртуального адреса. PDE содержит номер фрейма страницы (page frame number, PFN) таблицы страниц (если она находится в памяти, таблица может быть выгружена в страничный файл)

Слайд 31

ИУС ФТК Коликова Т.В.
Трансляция адресов
Индекс таблицы страниц используется как указатель для

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

Слайд 32

ИУС ФТК Коликова Т.В.
Ассоциативный буфер трансляции
Трансляция каждого адреса требует двух операций

поиска:
сначала нужно найти подходящую таблицу страниц в каталоге страниц
а затем элемент в этой таблице
Выполнение этих операций при каждом обращении по виртуальному адресу снижает быстродействие системы
Процессоры кэшируют транслируемые адреса
Процессор типа x86 поддерживает такой кэш в виде массива ассоциативной памяти, называемого ассоциативным буфером трансляции (translation lookaside buffer, TLB)

Слайд 33

ИУС ФТК Коликова Т.В.
Ассоциативный буфер трансляции

Слайд 34

ИУС ФТК Коликова Т.В.
Paging Hardware With TLB
CPU
f
d
p
d
Physical memory
Logical address
Physical address
p
Page table
Page number
offset
Page #
Frame

TLB

TLB miss

TLB hit

Слайд 35

ИУС ФТК Коликова Т.В.
Byte within page
Virtual page number
Virtual Address Translation
The hardware

converts each valid virtual address to a physical address

Physical page number

Byte within page

Page
Directory

Page
Tables

virtual address

physical address

Translation
Lookaside
Buffer

a cache of recently-
used page table entries

Address translation (hardware)

if page
not valid...

page fault
(exception,
handled by
software)

Слайд 36

ИУС ФТК Коликова Т.В.
Ассоциативный буфер трансляции
Виртуальные адреса объединяются в страницы по

2¹²( 4Кб ), таким образом в каждом адресном пространстве получается 2²º страниц
Если один вход таблицы страниц имеет размер 2² (4б), то для отображения всей виртуальной памяти процесса потребуется ( 2²º * 2² : 2¹² ) 1024 страничных фрейма
И это только для адресного пространства одного процесса

Слайд 37

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Обычно система виртуальной

памяти определяет три типа стратегии:
стратегия считывания (fetch policy)
стратегия размещения (placement policy)
стратегия замещения (replacement policy)

Слайд 38

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Стратегия считывания (fetch policy)

определяет, когда надо перемещать страницу с диска в память
Можно пытаться загрузить страницы, которые потребуются процессу, до того как он их запросит (заранее)
А можно использовать стратегию подкачки по запросе (demand paging policy), в этом случае страница загружается в память только тогда, происходит страничная ошибка

Слайд 39

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Диспетчер виртуальной памяти Windows

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

Слайд 40

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
При возникновении страничной ошибки

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

Слайд 41

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Если страничная ошибка происходит,

когда вся физическая память заполнена, то применяется стратегия замещения (replacement policy)
Она определяет какую страницу нужно извлечь из памяти, чтобы освободить место для новой страницы
Обычно используют следующие стратегии:
замещение используемого меньше всего (least recently used)
первым пришел, первым ушел (first in, first out – FIFO)

Слайд 42

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
В первом случае необходимо,

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

Слайд 43

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Стратегии замещения делятся на:
локальные

(local replacement policy)
глобальные (global replacement policy)
При стратегии локального замещения каждому процессу выделяется фиксированное (динамически настраиваемое) число страничных фреймов
Когда процесс использовал все выделенные ему фреймы, система виртуальной памяти удаляет из физической памяти одну из его страниц при каждой страничной ошибке в данном процессе

Слайд 44

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
В случае стратегии глобального

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

Слайд 45

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Стратегия глобального замещения создает

ряд проблем:
процессы подвержены влиянию других процессов
плохое приложение может подорвать работу всей системы
По этим причинам диспетчер виртуальной памяти Windows использует стратегию локального замещения FIFO
Для реализации этого подхода ему необходимо для каждого процесса отслеживать его страницы, находящиеся в памяти
Это множество страниц называется рабочим набором (working set) процесса

Слайд 46

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Минимальный размер рабочего набора

- минимальное число страниц процесса, которые будут гарантированно находиться в памяти во время его исполнения
Максимальный размер рабочего набора
Когда физической памяти становится недостаточно, диспетчер виртуальной памяти использует автоматическое урезание рабочего набора (automatic working set trimming), для увеличения объема свободной памяти
Диспетчер виртуальной памяти, используя стратегии локального замещения и автоматического урезания рабочего набора, пытается обеспечить максимально возможную производительность для каждого процесса
Процесс может изменить минимальный и максимальный размер своего рабочего набора, вызвав сервис объекта процесс

Слайд 47

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Таблицы страниц процесса содержат информацию

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

Слайд 48

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Для этого используется база данных

страничных фреймов (page frame database)
Она представляет собой массив элементов (от 0 до число страничных фреймов в системе – 1)
Каждый элемент содержит информацию о соответствующем страничном фрейме
Действительные элементы таблицы страниц указывают на элементы базы данных страничных фреймов
Диспетчер виртуальной памяти использует этот указатель, когда процесс обращается по действительному виртуальному адресу, чтобы найти физическую страницу, соответствующую виртуальному адресу

Слайд 49

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Некоторые недействительные элементы таблицы страниц

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

Слайд 50

ИУС ФТК Коликова Т.В.
База данных страничных фреймов

Слайд 51

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Недействительные элементы таблицы страниц содержат

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

Слайд 52

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Резервный – данный фрейм использовался

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

Слайд 53

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
В базе данных страничные фреймы,

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

Слайд 54

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
В данные списки включены все

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

Слайд 55

ИУС ФТК Коликова Т.В.
База данных страничных фреймов

Слайд 56

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Если диспетчеру виртуальной памяти требуется

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

Слайд 57

ИУС ФТК Коликова Т.В.
База данных страничных фреймов

Слайд 58

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Когда количество страниц в списках

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

Слайд 59

ИУС ФТК Коликова Т.В.
Paging Dynamics
Standby
Page List
Zero
Page
List
Free
Page List
Process
Working
Sets
page read from disk or kernel allocations
demand

zero page faults

working set replacement

Modified
Page List

zero
page
thread

Bad
Page
List

Private pages at process exit

Слайд 60

ИУС ФТК Коликова Т.В.
Дескрипторы виртуальных адресов
Момент загрузки страниц в память диспетчер

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

Слайд 61

ИУС ФТК Коликова Т.В.
Дескрипторы виртуальных адресов
Диспетчер памяти использует этот же механизм

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

Слайд 62

ИУС ФТК Коликова Т.В.
Дескрипторы виртуальных адресов
Как же тогда диспетчер виртуальной памяти

определяет какие адреса свободны?
Чтобы решить эту проблему диспетчер поддерживает набор структур данных, которые позволяют вести учет зарезервированных и свободных виртуальных адресов в адресном пространстве процесса
Эти структуры данных называются дескрипторами виртуальных адресов (virtual address descriptors, VAD)
Для каждого процесса диспетчер памяти поддерживает свой набор VAD, описывающий состояние адресного пространства этого процесса

Виртуальная память

Содержание

ИУС ФТК Коликова Т.В.О чемВведениеУправление памятьюТрансляция адресовАссоциативный буфер трансляцииСтратегия подкачки и

ИУС ФТК Коликова Т.В.Виртуальная памятьНельзя выполнить программу, размер которой > размера

ИУС ФТК Коликова Т.В.Виртуальная памятьфизическая и логическая структураСпособ, которым ОС транслирует

ИУС ФТК Коликова Т.В.Виртуальное адресное пространство (virtual address space)– это набор

ИУС ФТК Коликова Т.В.Виртуальная памятьСистема виртуальной памяти должна:Транслировать, или отображать (map)определяет

ИУС ФТК Коликова Т.В.Виртуальная памятьМедленно перемещать по одному байту Виртуальное адресное

ИУС ФТК Коликова Т.В.Виртуальная памятьСтраницы, находящиеся в физической памяти и доступные

ИУС ФТК Коликова Т.В.Виртуальная память

ИУС ФТК Коликова Т.В.Виртуальная памятьПри обращении потока по виртуальному адресу, который

ИУС ФТК Коликова Т.В.Виртуальная памятьОбработка страничной ошибки – это дорогая операция,

ИУС ФТК Коликова Т.В.Виртуальная память

ИУС ФТК Коликова Т.В.Управление памятьюДиспетчер виртуальной памяти предоставляет набор базовых сервисов.

ИУС ФТК Коликова Т.В.Windows API Memory Management ArchitectureWindows ProgramC library: malloc,

ИУС ФТК Коликова Т.В.Windows Memory ManagementWindows maintains pools of memory in

ИУС ФТК Коликова Т.В.Managing Heap MemorydwFlags:HEAP_GENERATE_EXCEPTION, raise SEH on memory allocation

ИУС ФТК Коликова Т.В.Управление памятьюДиспетчер виртуальной памяти выделяет память в два

ИУС ФТК Коликова Т.В.Управление памятьюРезервирование памяти полезно при создании динамических структур

ИУС ФТК Коликова Т.В.Трансляция адресовПриложения используют 32-разрядные виртуальные адресаС помощью структур

ИУС ФТК Коликова Т.В.Трансляция адресов

ИУС ФТК Коликова Т.В.Paging Example Page 0Page 1Page 2Page 3logical memoryPage 0Page

ИУС ФТК Коликова Т.В.Free FramesBefore allocationAfter allocationPage 2physical memoryPage 0Page 3frame number1011121314151617Page 17891011121314151617789Free

ИУС ФТК Коликова Т.В.Valid (v) or Invalid (i) Bit in a

ИУС ФТК Коликова Т.В.Трансляция адресовДля трансляции виртуальных адресов в физические используется

ИУС ФТК Коликова Т.В.Two-Level Page-Table Scheme…………outer page table (page directory)page tablesmemory

ИУС ФТК Коликова Т.В.Address-Translation SchemeAddress-translation scheme for a two-level 32-bit paging

ИУС ФТК Коликова Т.В.x86 Virtual Address TranslationPage tableselectorPage tableentry selectorByte within

ИУС ФТК Коликова Т.В.Трансляция адресов

ИУС ФТК Коликова Т.В.Трансляция адресовИндекс каталога страниц (page directory index) применяется

ИУС ФТК Коликова Т.В.Трансляция адресовПри трансляции виртуального адреса:Определяется адрес каталога страниц

ИУС ФТК Коликова Т.В.Трансляция адресовИндекс таблицы страниц используется как указатель для

ИУС ФТК Коликова Т.В.Ассоциативный буфер трансляцииТрансляция каждого адреса требует двух операций

ИУС ФТК Коликова Т.В.Ассоциативный буфер трансляции

ИУС ФТК Коликова Т.В.Paging Hardware With TLBCPUfdpdPhysical memoryLogical addressPhysical addresspPage tablePage numberoffsetPage #Frame

ИУС ФТК Коликова Т.В.Byte within pageVirtual page numberVirtual Address TranslationThe hardware

ИУС ФТК Коликова Т.В.Ассоциативный буфер трансляцииВиртуальные адреса объединяются в страницы по

ИУС ФТК Коликова Т.В.Стратегия подкачки и рабочие наборы Обычно система виртуальной

ИУС ФТК Коликова Т.В.Стратегия подкачки и рабочие наборыСтратегия считывания (fetch policy)

ИУС ФТК Коликова Т.В.Стратегия подкачки и рабочие наборыДиспетчер виртуальной памяти Windows

ИУС ФТК Коликова Т.В.Стратегия подкачки и рабочие наборыПри возникновении страничной ошибки

ИУС ФТК Коликова Т.В.Стратегия подкачки и рабочие наборыЕсли страничная ошибка происходит,

ИУС ФТК Коликова Т.В.Стратегия подкачки и рабочие наборыВ первом случае необходимо,

ИУС ФТК Коликова Т.В.Стратегия подкачки и рабочие наборыСтратегии замещения делятся на:локальные

ИУС ФТК Коликова Т.В.Стратегия подкачки и рабочие наборыВ случае стратегии глобального

ИУС ФТК Коликова Т.В.Стратегия подкачки и рабочие наборыСтратегия глобального замещения создает

ИУС ФТК Коликова Т.В.Стратегия подкачки и рабочие наборыМинимальный размер рабочего набора

ИУС ФТК Коликова Т.В.База данных страничных фреймовТаблицы страниц процесса содержат информацию

ИУС ФТК Коликова Т.В.База данных страничных фреймовДля этого используется база данных

ИУС ФТК Коликова Т.В.База данных страничных фреймовНекоторые недействительные элементы таблицы страниц

ИУС ФТК Коликова Т.В.База данных страничных фреймов

ИУС ФТК Коликова Т.В.База данных страничных фреймовНедействительные элементы таблицы страниц содержат

ИУС ФТК Коликова Т.В.База данных страничных фреймовРезервный – данный фрейм использовался

ИУС ФТК Коликова Т.В.База данных страничных фреймовВ базе данных страничные фреймы,

ИУС ФТК Коликова Т.В.База данных страничных фреймовВ данные списки включены все

ИУС ФТК Коликова Т.В.База данных страничных фреймов

ИУС ФТК Коликова Т.В.База данных страничных фреймовЕсли диспетчеру виртуальной памяти требуется

ИУС ФТК Коликова Т.В.База данных страничных фреймов

ИУС ФТК Коликова Т.В.База данных страничных фреймовКогда количество страниц в списках

ИУС ФТК Коликова Т.В.Paging DynamicsStandbyPage ListZeroPageListFreePage ListProcessWorkingSetspage read from disk or kernel allocationsdemand

ИУС ФТК Коликова Т.В.Дескрипторы виртуальных адресовМомент загрузки страниц в память диспетчер

ИУС ФТК Коликова Т.В.Дескрипторы виртуальных адресовДиспетчер памяти использует этот же механизм

ИУС ФТК Коликова Т.В.Дескрипторы виртуальных адресовКак же тогда диспетчер виртуальной памяти

Похожие презентации

ИУС ФТК Коликова Т.В.
О чем
Введение
Управление памятью
Трансляция адресов
Ассоциативный буфер трансляции
Стратегия подкачки и

ИУС ФТК Коликова Т.В.
Виртуальная память
Нельзя выполнить программу, размер которой > размера

ИУС ФТК Коликова Т.В.
Виртуальная память
физическая и логическая структура
Способ, которым ОС транслирует

ИУС ФТК Коликова Т.В.
Виртуальное адресное пространство (virtual address space)– это набор

ИУС ФТК Коликова Т.В.
Виртуальная память
Система виртуальной памяти должна:
Транслировать, или отображать (map)
определяет

ИУС ФТК Коликова Т.В.
Виртуальная память
Медленно перемещать по одному байту
Виртуальное адресное

ИУС ФТК Коликова Т.В.
Виртуальная память
Страницы, находящиеся в физической памяти и доступные

ИУС ФТК Коликова Т.В.
Виртуальная память

ИУС ФТК Коликова Т.В.
Виртуальная память
При обращении потока по виртуальному адресу, который

ИУС ФТК Коликова Т.В.
Виртуальная память
Обработка страничной ошибки – это дорогая операция,

ИУС ФТК Коликова Т.В.
Виртуальная память

ИУС ФТК Коликова Т.В.
Управление памятью
Диспетчер виртуальной памяти предоставляет набор базовых сервисов.

ИУС ФТК Коликова Т.В.
Windows API Memory Management Architecture
Windows Program
C library: malloc,

ИУС ФТК Коликова Т.В.
Windows Memory Management
Windows maintains pools of memory in

ИУС ФТК Коликова Т.В.
Managing Heap Memory
dwFlags:
HEAP_GENERATE_EXCEPTION,
raise SEH on memory allocation

ИУС ФТК Коликова Т.В.
Управление памятью
Диспетчер виртуальной памяти выделяет память в два

ИУС ФТК Коликова Т.В.
Управление памятью
Резервирование памяти полезно при создании динамических структур

ИУС ФТК Коликова Т.В.
Трансляция адресов
Приложения используют 32-разрядные виртуальные адреса
С помощью структур

ИУС ФТК Коликова Т.В.
Трансляция адресов

ИУС ФТК Коликова Т.В.
Paging Example
Page 0
Page 1
Page 2
Page 3
logical memory
Page 0
Page

ИУС ФТК Коликова Т.В.
Free Frames
Before allocation
After allocation
Page 2
physical memory
Page 0
Page 3
frame number
10
11
12
13
14
15
16
17
Page 1
7
8
9
10
11
12
13
14
15
16
17
7
8
9
Free

ИУС ФТК Коликова Т.В.
Valid (v) or Invalid (i) Bit in a

ИУС ФТК Коликова Т.В.
Трансляция адресов
Для трансляции виртуальных адресов в физические используется

ИУС ФТК Коликова Т.В.
Two-Level Page-Table Scheme
…
…
…
…
outer page table (page directory)
page tables
memory

ИУС ФТК Коликова Т.В.
Address-Translation Scheme
Address-translation scheme for a two-level 32-bit paging

ИУС ФТК Коликова Т.В.
x86 Virtual Address Translation
Page table
selector
Page table
entry selector
Byte within

ИУС ФТК Коликова Т.В.
Трансляция адресов

ИУС ФТК Коликова Т.В.
Трансляция адресов
Индекс каталога страниц (page directory index) применяется

ИУС ФТК Коликова Т.В.
Трансляция адресов
При трансляции виртуального адреса:
Определяется адрес каталога страниц

ИУС ФТК Коликова Т.В.
Трансляция адресов
Индекс таблицы страниц используется как указатель для

ИУС ФТК Коликова Т.В.
Ассоциативный буфер трансляции
Трансляция каждого адреса требует двух операций

ИУС ФТК Коликова Т.В.
Ассоциативный буфер трансляции

ИУС ФТК Коликова Т.В.
Paging Hardware With TLB
CPU
f
d
p
d
Physical memory
Logical address
Physical address
p
Page table
Page number
offset
Page #
Frame

ИУС ФТК Коликова Т.В.
Byte within page
Virtual page number
Virtual Address Translation
The hardware

ИУС ФТК Коликова Т.В.
Ассоциативный буфер трансляции
Виртуальные адреса объединяются в страницы по

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Обычно система виртуальной

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Стратегия считывания (fetch policy)

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Диспетчер виртуальной памяти Windows

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
При возникновении страничной ошибки

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Если страничная ошибка происходит,

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
В первом случае необходимо,

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Стратегии замещения делятся на:
локальные

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
В случае стратегии глобального

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Стратегия глобального замещения создает

ИУС ФТК Коликова Т.В.
Стратегия подкачки и рабочие наборы
Минимальный размер рабочего набора

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Таблицы страниц процесса содержат информацию

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Для этого используется база данных

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Некоторые недействительные элементы таблицы страниц

ИУС ФТК Коликова Т.В.
База данных страничных фреймов

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Недействительные элементы таблицы страниц содержат

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Резервный – данный фрейм использовался

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
В базе данных страничные фреймы,

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
В данные списки включены все

ИУС ФТК Коликова Т.В.
База данных страничных фреймов

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Если диспетчеру виртуальной памяти требуется

ИУС ФТК Коликова Т.В.
База данных страничных фреймов

ИУС ФТК Коликова Т.В.
База данных страничных фреймов
Когда количество страниц в списках

ИУС ФТК Коликова Т.В.
Paging Dynamics
Standby
Page List
Zero
Page
List
Free
Page List
Process
Working
Sets
page read from disk or kernel allocations
demand

ИУС ФТК Коликова Т.В.
Дескрипторы виртуальных адресов
Момент загрузки страниц в память диспетчер

ИУС ФТК Коликова Т.В.
Дескрипторы виртуальных адресов
Диспетчер памяти использует этот же механизм

ИУС ФТК Коликова Т.В.
Дескрипторы виртуальных адресов
Как же тогда диспетчер виртуальной памяти