Как ОС обновляет соответствующую таблицу страниц при удалении страницы-жертвы?

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

Предположим, что памяти не хватает, и ОС нужно выбрать страницу для удаления из физической памяти. Для этого есть разные алгоритмы. Например, ФИФО, ЛРУ. Как только ОС выбирает страницу для удаления, как она делает недействительными любые существующие ссылки на страницу?

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

Подробное описание структуры таблицы страниц x86 начинается на слайде 22 этой презентации:

http://www.scs.stanford.edu/12au-cs140/notes/l8.pdf

Я также нашел несколько полезных обзоров виртуальной памяти:

http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/9_VirtualMemory.html http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Memory/virtual.html

Аналогичный вопрос о переполнении стека без ответа:

как Linux обновляет таблицу страниц после переключения контекста


operating-system virtual-memory page-tables
person BitPusher16    schedule 09.07.2015    source источник

Ответы (2)


arrow_upward
2
arrow_downward

На самом деле, то, о чем вы спрашиваете, называется обратное сопоставление. Например, в Linux вы можете найти полезную функцию try_to_unmap_anon Внутри дескриптора страницы есть поле, называемое сопоставлением. Это поле anon_vma для анонимные страницы. Как видите, это не просто обычная структура, но и элемент списка. Для одной страницы может быть несколько anon_vmas (см. try_to_unmap_anon):

list_for_each_entry(vma, &anon_vma->head, anon_vma_node)

ровно один на сопоставление страницы. Все это vmas связано в список. Именно так ядро ​​​​узнает, какие процессы (и их таблицы страниц) задействованы. Теперь о том, как ядро ​​определяет виртуальный адрес... ответ снова можно найти здесь: vma_address

233         pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
234         unsigned long address;
235 
236         address = vma->vm_start + ((pgoff - vma->vm_pgoff) << PAGE_SHIFT);

Итак, теперь мы можем коротко ответить на ваш вопрос: чтобы не сканировать таблицы страниц, ядро ​​хранит все, что ему нужно (для быстрой выборки), в дескрипторе страницы (struct page).

person Alex Hoppus    schedule 09.07.2015

arrow_upward
1
arrow_downward

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

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

person user3344003    schedule 10.07.2015