Страничная организация памяти. Выбор размера страниц. Управление страничным обменом. Алгоритмы замены страниц

При использовании виртуальной памяти каждому процессу выделяется определенное виртуальное адресное пространство. Это пространство делится на части фиксированного размера - виртуальные страницы. Вся оперативная память машины также делится на части такого же размера –физические страницы.

Размер страниц выбирается кратным степени двойки. Обычно -4Кб.

Так как большинство современных машин – 32 разрядные, то они могу адресовать 4Гб. данных (максимальный размер виртуальной памяти). На адрес страницы уходит 4Гб/4Кб=2²⁰ – 20 бит. Другие 12 бит идут на смещение внутри страницы (4Кб=2¹²байт)

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

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

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

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

Алгоритмы замены страниц:

Оптимальный алгоритм - выгружается та страница, которую дольше всего не придется загружать.
Алгоритм наименее часто использовавшихся.
Алгоритм дольше всех не использовавшихся.
Алгоритм first in – first out. Выгружается страница, находящаяся в памяти дольше других.
Часовой алгоритм. Маркер проходит по очереди по всем страницам и если они не использовались в последнее время (признак доступа=0) – замещает их. А если этот признак = 1, то алгоритм меняет его на 0, чтобы при проходе по кругу всех страниц (если у всех он =1) он хотя бы на 2-ом круге нашел страницу для замещения

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

Задача

Имеется многозадачный компьютер, в котором каждое задание имеет идентичные характеристики. В течение цикла вычисления одного задания Т половину времени занимает ввод-вывод, а вторую половину – работа процессора. Для выполнения каждого задания требуется N циклов. Для планирования используется простой алгоритм циклического обслуживания, а ввод-вывод выполняется одновременно с работой процессора.

Определить значения следующих величин:

1. Реальное время, затрачиваемое на выполнение задания.

2. Доля времени, в течение которого процессор активен (не находится в режиме ожидания).

3. Эти значения требуется вычислить для одного, двух и трех одновременно выполняющихся заданий, считая, что время цикла Т распределяется следующим способом: в течении первой половины периода выполняется ввод-вывод, а в течении второй – работа процессора.

Решение

Все довольно просто. Рисуются диаграммы следующего вида и по ним все считается. Принцип следующий: пока один процесс вычисляется, другой осуществляет ввод/вывод. Все можно посчитать в уме: