На рисунке показаны основные этапы обработки события «страничная недостаточность».
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 algorithm).
2. алгоритм замещения страниц (page replacement algorithm).
Алгоритм распределения страничных рамок решает, сколько страничных рамок в основной памяти выделить каждому из процессов мультипрограммной смеси.
Алгоритм замещения страниц решает, какую из страниц выбрать в качестве жертвы.
4.2.1. FIFO.
Наиболее простым алгоритмом замещения страниц является алгоритм FIFO. Этот алгоритм ассоциирует с каждой страницей время, когда эта страница была помещена в память. Для замещения выбирается наиболее старая страница.
| 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 |
|
| 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 |
| |
Учет времени необязателен, когда все страницы в памяти связаны в FIFO-очередь, а каждая помещаемая в память страница добавляется в хвост очереди.
Алгоритм учитывает только время нахождения страницы в памяти, но не учитывает используемость страницы. Например, первые страницы программы могут содержать переменные, используемые на протяжении работы всей программы. Это приводит к немедленному возвращению к только что замещенной странице.
4.2.2. Оптимальный алгоритм.
Этот алгоритм имеет наилучшее соотношение количества замещенных страниц к количеству ссылок. Алгоритм строится по следующему принципу: замещается та страница, на которую нет ссылки на протяжении наиболее длительного периода времени. Для реализации этого алгоритма необходимо каждый раз сканировать весь поток ссылок, поэтому он нереализуем на практике и используется для оценки реально работающих алгоритмов.
4.2.3. LRU — алгоритм (least recently used).
Алгоритм выбирает для замещения ту страницу, на которую не было ссылки на протяжении наиболее длинного периода времени. Least recently used ассоциирует с каждой страницей время последнего использования этой страницы. Для замещения выбирается та страница, которая дольше всех не использовалась. Этот алгоритм наиболее часто используется в системах страничирования по запросу. Обычно применяется два подхода при внедрении этого алгоритма.
1. подход на основе логических часов (счетчика)
2. подход на основе стека номеров страниц
1. ассоциируют с каждой строкой таблицы поле “время использования” а в CPU добавляются логические часы. Логические часы увеличивают своё значение при каждом обращении к памяти. Каждый раз, когда осуществляется ссылка на страницу, значение регистра логических часов копируется в поле “время использования”. Заменяется страница с наименьшим значением в отмеченном поле путем сканирования всей таблицы страниц. Сканирование отсутствует при использовании подхода на основе стека.
2. стек номеров страниц хранит номера страниц, упорядоченных в соответствии с историей их использования, на вершине стека располагается только что использованная страница, а на дне least recently used страница. Как только осуществляется ссылка на страницу, она перемещается на вершину стека, а номера всех страниц сдвигаются вниз.
5. ОБЩИЕ СВЕДЕНИЯ
Теперь, после ознакомления с теорией операционных систем, рассмотрим вкратце каждую из выше перечисленных*. Все эти операционные системы работают в многозадачном однопользовательском режиме работы (UNIX также поддерживает и многопользовательский режим); поддерживают иерархическую файловую систему, межпроцессное взаимодействие, встроенные средства отладки программ, стандартизируют программный интерфейс для многих внешних устройств, обычно трактуя их как файлы с последовательным доступом.
5.1. УПРАВЛЕНИЕ ПАМЯТЬЮ.
Все рассматриваемые операционные системы обеспечивают выделение участка памяти для нужд программы, изменение его размера и освобождение. По-разному поддерживается концепция виртуальной памяти.
Операционная система OS/2 использует страничную модель памяти, то есть программа получает память порциями по 4 кб; подкачка также осуществляется порциями по 4 кб. Программа не может управлять процессом подкачки.
Важной особенностью OS/2 является возможность создания специальных разделяемых областей памяти, которые могут использоваться для межпроцессного взаимодействия (см. гл. межпроцессное взаимодействие).
Microsoft Windows использует сегментированную модель память. Исторически сложилось так, что ОС (а, точнее, программная оболочка) Microsoft Windows до разработки процессора 80386 работала в реальном режиме (’real mode’) и защищенном режиме 80286-го процессора (’standart mode’). В реальном режиме механизм подкачки не использовался; при наличии 286-го процессора ОС позволяла выгружать на диск только MS-DOS-освские программы. С появлением процессора 80386 и использованием его защищенного режима, возможности использования виртуальной памяти резко расширились: появилась возможность выгрузить на диск любой сегмент памяти компьютера. С помощью системных вызовов, программа пользователя может управлять многими нюансами распределения памяти: разрешением на выгрузку страницы, сборкой мусора, перемещением объектов в памяти.