Оптимальный алгоритм.

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

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

Fifo алгоритм «Первым пришел - первым обслужен

В рамках этого алгоритма из памяти выгружается страница которая дольше всего там находится. Организуется очередь страниц, где каждая загружаемая страница включается в конец очереди, для освобождения кадра выбирается первая страница очереди.Минус в том что с достаточной вероятностью будет вытолкнута активноиспользуемая страница, что сразу приводит к страничному прерыванию.Плюс в том что не используется процессорная поддержка.Возможна модификация FIFO которая позволяет избежать потери часто используемой страницы Second-Chance использует анализ бита обращения к странице, если 1 то страница идет в конец очереди и очищается бит, если на все страницы ссылаются то алгоритм становится FIFO

Алгоритм NRU «Не использовавшаяся в последнее время страница».

процессы:

• 0 класс – небыло обращений и изменений R0 M0

• 1класс – небыло обращений, изменено R0 M1

• 2класс – было обращение, не изменено R1 M0

• 3 класс – было обращение, изменено R1 M1

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

Алгоритм LRU «Дольше всего не использовавшаяся страница».

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

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

Проблемы реализации LRU.

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

Алгоритм NFU «Редко используемая страница».

Один из таких возможных алгоритмов - это алгоритм NFU.

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

Таким образом, кандидатом на освобождение оказывается страница с наименьшим значением счетчика, как страница, к которой реже всего обращались. Главным недостатком алгоритма NFU является то, что он никогда ничего не забывает. Например, страница, к которой очень много обращались некоторое время, а потом обращаться перестали, все равно не будет удалена из памяти, потому что ее счетчик содержит большую величину. Например, в многопроходных компиляторах страницы, которые активно использовались во время 1-го прохода, могут надолго сохранить большие значения счетчика, мешая загрузке полезных в дальнейшем страниц.

К счастью, возможна небольшая модификация алгоритма, которая реализует "забывание". Достаточно, чтобы при каждом прерывании по времени содержимое каждого счетчика сдвигалось вправо на 1 бит, а уже затем производилось бы его увеличение для страниц с установленным флагом обращения

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

Причины изменения частоты страничных прерываний.

Пробуксовка.

Хотя теоретически возможно уменьшить число кадров процесса до минимума, существует какое-то число активно используемых страниц, без которого процесс часто генерирует faltы. Эта высокая частота страничных нарушений называется трешинг (trashing, иногда употребляется русский термин пробуксовка). Процесс находится в состоянии трешинга, если он больше времени занимается подкачкой страниц, нежели выполнением. Критическая ситуация такого рода возникает вне зависимости от конкретных алгоритмов замещения.

Модель рабочего множества.

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

Алгоритмы «Рабочее множество».

Замещение страниц в многозадачной среде.

Демоны системы управления памятью.

Управление памятью в операционной системе UNIX.

Вспомогательные структуры данных.

Совместное использование областей.

Операции над областями.

Взаимодействие между процессами

Причины взаимодействия процессов.

Организация обмена данными.

Средства обмена данными.

Категории средств обмена.

Обмен данными.

Порядок начала связи.

Инициализация обмена.

Способы адресации средств связи.

Порядок обмена.

Характеристики средств связи.

Информационная валентность и направленность и средств связи.

Порядок завершения связи.

Передача информации с помощью каналов связи.

Модели передачи данных.

Буферизация.

Надежность средств связи.

Понятие протокола связи.

Организация взаимодействия процессов в UNIX.

Механизмы IPC и общие принципы их организации.

Идентификация экземпляров средства связи.

Разделяемая память.

Сообщения.

Сигналы.

Обработка сигналов.

Каналы.

Виды каналов.

Особенности чтение и записи данных при работе с каналами.

Семафоры.

Примеры взаимодействия.

Конфликты и состояния состязания.

Взаимное исключение.

Критические области..

Общая схема реализации взаимного исключения.

Алгоритмы синхронизации процессов.

Условия корректности алгоритмов синхронизации.

Запрет прерываний.

Взаимное исключение с активным ожиданием.

Переменные блокировки.

Строгое чередование.

Флаги готовности.

Нарушение условий реализации взаимного исключения.

Алгоритм Петерсона.

Доказательство выполнения условий взаимного исключения в алгоритме Петерсона.

Алгоритм булочной.

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

Команда TS.

Недостатки алгоритмов с активным ожиданием.

Инверсия приоритета.

Проблема производителя и потребителя.

Семафоры.

Решение проблемы производителя и потребителя с помощью семафоров.

Мониторы.

Решение проблемы производителя и потребителя с помощью мониторов.

Сообщения.

Решение проблемы производителя и потребителя с помощью сообщений.