Страничная организация по требованию в Windows NT

ОС Windows NT использует страничную организацию "по требованию" и кластеризацию, т.е. подкачку страниц, смежных с затребованной. Процессам выделяются минимальное и максимальное рабочие множества. Минимальное рабочее множество – это набор страниц, которые процесс гарантированно имеет в памяти. Процесс может иметь в памяти число страниц до максимума рабочего множества. Если объем свободной памяти в системе становится меньше некоторого порогового значения (threshold), то ОС выполняет сокращение рабочих множеств процессов (working set trimming).Сокращение рабочих множеств – это изъятие у процессов "лишних" страниц в оперативной памяти, которые превышают минимальный размер их рабочих множеств.

Страничная организация в Solaris

В ОС Solaris поддерживается список свободных страниц для выделения процессам, в которых происходят отказы страниц. Используется lotsfree– пороговый параметр для начала подкачки страниц. Управление страницами выполняет процесс pageout. Процесс pageoutсканирует страницы, используя модифицированный алгоритм, основанный на показаниях часов. Используется также scanrate– коэффициент, характеризующий процесс сканирования. Диапазон - от slowscanдо fastscan. Процесс pageoutвызывается более часто, в зависимости от размера свободной памяти.

Ключевые термины

mmap (memory map) –команда и системный вызов в ОС Solaris для организации файла, отображаемого в память.

Thrashing –ситуация критической нехватки основной памяти в системе, при которой процессор занят в основном откачкой и подкачкой страниц.

Алгоритм FIFO (First-In-First-Out) замещения страниц -наиболее простой алгоритм замещения страниц, при котором в качестве жертвы всегда выбирается фрейм, первым из имеющихся считанный в основную память.

Алгоритм Least Frequently Used (LFU) замещения страниц –алгоритм, при котором замещается страница с минимальным значением счетчика обращений (к которой было меньше всего обращений).

Алгоритм Least Recently Used (LRU) замещения страниц –алгоритм, при котором замещается та страница, которая раньше всего использовалась.

Алгоритм Most Frequently Used (MFU) замещения страниц– алгоритм, при котором замещается страница с максимальным значением счетчика обращений (к которой было больше всего обращений).

Алгоритм второго шанса (second chance) при замещении страниц –алгоритм, в котором замещается не та страница, к которой дольше всего не было обращения, а следующая за ней по списку страниц, упорядоченному в порядке возрастания времен обращений.

Аномалия Belady– рост числа отказов страниц в алгоритме FIFOпри четырех свободных фреймах у процесса, по сравнению с числом отказов страниц при трех свободных фреймах.

Бит модификации- бит элемента таблицы страниц, указывающий на модификацию страницы, с целью откачки на диск только модифицированных страниц.

Бит ссылки (reference bit)– бит элемента таблицы страниц, равный 0, если к странице не было обращения, и 1, если обращение к странице было.

Бит "valid/invalid" –бит элемента таблицы страниц, указывающий на присутствие или отсутствие страницы в основной памяти.

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

Выделение фреймов по приоритетам– выделение процессам фреймов страниц в основной памяти, в соответствии с приоритетами процессов: при замещении страниц замещается страница процесса с более низким приоритетом.

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

Замещение страницы (page replacement)– подкачка операционной системой страницы, к которой произошло обращение, вместо другой страницы, с откачкой последней, если она требуется.

Копирование при записи (Copy-on-Write)– стратегия создания процесса, при которой новый процесс разделяет адресное пространство с процессом-родителем до первой записи в адресное пространство, после чего для дочернего процесса создается новое адресное пространство – копия родительского.

Коэффициент отказов страниц (Page Fault Rate)– число от 0 до 1, характеризующее вероятность отказа страницы.

Локальное выделение фреймов– выделение процессам фреймов страниц в основной памяти, при котором наборы свободных фреймов выделяются для каждого процесса отдельно.

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

Отказ страницы( page fault) –прерывание по отсутствию страницы в основной памяти.

Пропорциональное выделение фреймов– выделение процессам фреймов страниц в основной памяти, пропорционально размерам процессов в памяти.

Рабочее множество– набор страниц, используемых процессом.

Сегментная организация по требованию (segmentation on demand)– метод организации виртуальной памяти, основанный на сегментной организации, при котором каждый сегмент загружается в память, только если он реально требуется при выполнении программы – содержит код или данные, к которым произошло обращение.

Страничная организация по требованию (paging on demand) –метод организации виртуальной памяти, основанный на страничной организации, при котором каждая страница загружается в память, только если она реально требуется при выполнении программы – содержит код или данные, к которым произошло обращение.

Файл, отображаемый в память (Memory-Mapped File)– файл, блоки которого отображены в основную память через таблицу страниц.

Фиксированное выделение фреймов –выделение фреймов страниц в основной памяти процессам либо равномерно, либо пропорционально размерам процессов в памяти.

Эффективное время доступа (Effective Access Time - EAT)– математическое ожидание времени доступа к странице.

Краткие итоги

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

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

Страничная организация по требованию – схема страничной организации, при которой страница подкачивается в основную память только при обращении к ней.При отсутствии адресуемой страницы в основной памяти происходит прерывание – отказ страницы (page fault). Бит valid-invalid элемента таблицы страниц указывает, присутствует ли страница в основной памяти.

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

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

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

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

Используются следующие алгоритмы замещения страниц: FIFO (замещается страница, загруженная в память раньше всех); оптимальный алгоритм (замещается страница, которая не использовалась в течение наибольшего периода времени); LRU (замещается страница, к которой раньше всего было обращение); LRU с использованием стека страниц с самой ранней по обращению страницей на вершине; замещение страниц с нулевым битом ссылки; алгоритм второго шанса (замещение второй по давности обращений страницы, с сохранением первой в памяти); LFU – замещение реже всего используемой страницы; MFU – замещение чаще всего используемой страницы.

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

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

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

В системе Solaris имеется пороговое значение для подкачки страниц; управление страницами выполняется на основе модифицированных показаний часов.

Вопросы для самопроверки:

1. Что такое виртуальная память?

2. Какие преимущества дает применение метода виртуальной памяти?

3. Какие два способа используются для организации виртуальной памяти?

4. Что такое страничная организация по требованию?

5. Что такое сегментная организация по требованию?

6. Что такое отказ страницы (page fault) и как ОС обрабатывает эту ситуацию?

7. Что такое бит valid-invalid?

8. Какие действия выполняет ОС при отсутствии свободного фрейма при обработке отказа страницы?

9. Что такое эффективное время доступа к странице и как оно вычисляется?

10. Что такое копирование при записи (copy-on-write)?

11. Что такое файл, отображаемый в память?

12. Что такое бит модификации и как он используется при откачке замещаемых страниц?

13. Каковы этапы алгоритма замещения страниц?

14. Что такое фрейм-жертва?

15. Что такое коэффициент отказов страниц?

16. Как зависит число отказов страниц от числа свободных фреймов?

17. Каковы принципы алгоритма FIFO замещения страниц?

18. Что такое аномалия Belady?

19. Что такое оптимальный алгоритм замещения страниц?

20. Каковы принципы алгоритма LRU замещения страниц?

21. Каковы принципы алгоритма на основе бита ссылки для замещения страниц?

22. Каковы принципы алгоритма второго шанса для замещения страниц?

23. Каковы принципы алгоритма LFU замещения страниц?

24. Каковы принципы алгоритма MFU замещения страниц?

25. Что такое выделение фреймов и по каким принципам оно может осуществляться?

26. Что такое равномерное выделение фреймов?

27. Что такое пропорциональное выделение фреймов?

28. Что такое выделение фреймов по приоритетам?

29. Что такое глобальное и локальное выделение фреймов?

30. Что такое thrashing и в каких случаях он происходит?

31. Что такое рабочее множество?

32. Каковы особенности страничной организации в Windows NT?

33. Каковы особенности страничной организации в Solaris?

Упражнения

1. Реализуйте модель страничной организации по требованию.

2. Реализуйте алгоритмы замещения страниц, рассмотренные в лекции.

3. Реализуйте модель стратегии рабочего множества с оценкой размеров рабочих множеств процессов и их сокращением, если объем памяти меньше порогового значения.

4.Реализуйте модель файла, отображаемого в память, и его взаимосвязи с таблицами страниц разделяющих его процессов.