Для учёта распределения страниц между внешней и основной памятью каждая строка таблицы страниц дополняется битом местонахождения страницы. Valid/invalid bit.

В том случае, если процессор пытается использовать страницу, помеченную значением invalid, возникает событие, называемое страничная недостаточность (paging fault).

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

На рисунке показаны основные этапы обработки события «страничная недостаточность».

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

2. если значение бита invalid, то процесс прерывается и управление передается операционной системе для обработки события страничная недостаточность.

3. разыскивается необходимая страница во вторичной памяти и свободная страничная рамка в основной**.

4. требуемая страница загружается в выбранную страничную рамку.

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

6. управление передается прерванному процессу

4.2. Замещение страниц.

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

Метод замещения страниц означает, что в основной памяти выбирается наименее важная/используемая страница, называется страница — жертва (victim page), которая временно перемещается в swap space, а на её место загружается страница, вызываемая страничной недостаточностью.

Обработка страничной недостаточности с учетом замещения осуществляется по следующему алгоритму:

1. определяется местонахождение страницы путем анализа бита местонахождения

2. если значение бита invalid, то разыскивается свободная страничная рамка.

2.1.если имеется свободная страничная рамка, то она используется.

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

2.3.страница — жертва перемещается в swap space и редактируется таблица страниц.

3. требуемая страница загружается на место страницы — жертвы и соответствующим образом редактируется таблица страниц.

Управление передается прерванному процессу. Приведенный алгоритм замещения требует двухстраничных перемещений.

1. страница - жертва перемещается в swap space.

2. требуемая страница перемещается в освободившуюся страничную рамку.

Страницу - жертву можно не копировать в swap space в том случае, если за время, прошедшее от последнего перемещения её содержимое не модифицировалось. В этом случае время замещения уменьшается примерно вдвое.

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

Для практического использования метода страничирования по запросу необходимо разработать два алгоритма.

1. алгоритм распределения страничных рамок (from allocation algorith).

2. алгоритм замещения страниц (page replacement algorith).

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

Алгоритм замещения страниц решает, какую из страниц выбрать в качестве жертвы.

4.2.1. FIFO.

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

Уч