Самодел 2 (1114717), страница 22

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 22)

Стратегии и методы управления:

1.Одиночное непрерывное распределение.

2.Распределение разделами.

3.Распределение перемещаемыми разделами.

4.Страничное распределение.

5.Сегментное распределение.

6.Сегменто-страничное распределение.

План рассмотрения стратегий управления:

1.Основные концепции.

2.Необходимые аппаратные средства.

3.Основные алгоритмы.

4.Достоинства, недостатки.

Распределения:

Одиночное непрерывное распределение

Основные концепции:

Реально используется

доступно

(выделено)

Н
еобходимые аппаратные средства:

•Регистр границ + режим ОС / режим пользователя.

•Если ЦП в режиме пользователя попытается обратиться в область ОС, то возникает прерывание.

Алгоритмы:

очевидны.

Достоинства:

простота.

Недостатки:

1.Часть памяти не используется.

2.Процессом/заданием память занимается все время выполнения.

3.Ограничение на размеры задания.

Распределение неперемещаемыми разделами

Основные концепции:

Раздел₁

Раздел₂

Раздел_N

N входных очередей Одна входная очередь

(Вариант А) (Вариант В)

Необходимые аппаратные средства:

1.Два регистра границ.

Недостатки:

а. перегрузка регистра границ при каждой смене контекста;

б. сложности при использовании каналов/процессоров ввода/вывода.

2.

2.Ключи защиты (PSW).

Алгоритмы:

Модель статического определения разделов

А. Сортировка входной очереди процессов по отдельным очередям к разделам. Процесс размещается в разделе минимального размера, достаточного для размещения данного процесса. В случае отсутствия процессов в каких-то под очередях – неэффективность использования памяти.

Б. Одна входная очередь процессов.

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

Проблема: большие разделы - маленькие процессы.

2. Освобождение раздела; поиск процесса максимального размера, не превосходящего размер раздела.

Проблема: дискриминация “маленьких” процессов.

3. Оптимизация варианта 2. Каждый процесс имеет счетчик дискриминации. Если значение счетчика процесса ³ K, то обход его в очереди невозможен.

Достоинства:

1.Простое средство организации мультипрограммирования.

2.Простые средства аппаратной поддержки.

3.Простые алгоритмы.

Недостатки:

1.Фрагментация.

2.Ограничение размерами физической памяти.

3.Весь процесс размещается в памяти – возможно неэффективное использование.

Распределение перемещаемыми разделами

Основные концепции:

Виртуальная память

Процесс₄

(например, V= V₂+1/2V₅)

Необходимые аппаратные средства:

Защита:

1.Регистры границ + регистр базы

2.Ключи + регистр базы

(базирование)

Алгоритмы:

Аналогично предыдущему

Достоинства:

Ликвидация фрагментации

Недостатки:

1.Ограничение размером физической памяти

2.Затраты на перекомпоновку

Основные концепции:

Память представляется как последовательность блоков фиксированного размера (страницы), размер страницы – 2ⁿ.

Мы рассматривали случаи, когда есть аппаратная таблица страниц. Сделаем преобазование – замену в вируальном адресе на соответствующий номер физической страницы. В таблице будет: (Номер строки)=(номер виртуальной страницы)+(некоторые атрибуты) – получаем, что вся информация находится в памяти, всё это должно быть реализовано аппаратно. При смене процесса ЦП должне перераспределять страницы. Размер страниц и их количество зависит от разрядности. Накладные расходы очень большие – поэтому не существует аппаратной реализации такой таблицы.

Можно огранизовать таблицу страниц в памяти – перегрузка будет минимальнойю Но на каждый обмен нужен ещё один обмен – это неэффективно.

Таблица страниц – отображение номеров виртуальных страниц на номера физических.

Проблемы:

1. Размер таблицы страниц (количество 4кб страниц при 32-х разрядной адресации – 1000000. Любой процесс имеет собственную таблицу страниц).

2. Скорость отображения.

Необходимые аппаратные средства (решения):

1.Полностью аппаратная таблица страниц (стоимость, полная перегрузка при смене контекстов, скорость преобразования).

2.Регистр начала таблицы страниц в памяти (простота, управление смены контекстов, медленное преобразование).

3.Гибридные решения. (сейчас используются чаще всего)

Алгоритмы и организация данных:

Размеры таблицы страниц – иерархическая организация таблицы страниц.

Модельная структура записи таблицы страниц

α – присутствие/отсутствие

β – защита (чтение, чтение/запись, выполнение)

γ – изменения

δ – обращение (чтение, запись, выполнение)

ε – блокировка кэширование

Таблицы страниц

TLB (Translation Lookaside Buffer)

TLB – это буфер быстрого преобразования адреса. (таблица, составленная по ассоциативному принципу, небольшая, фиксированного размера)

В поле два адреса – виртуальный и реальный. Осуществляется быстрый параллельый поиск vp и offset. Если не нашли – ситуация miss (промах), то возникает прерывание – ОС обращается в таблицу страниц, которая находится в ОП, находит там информацию. Если всё нормально, то TLB строится заново, поэтому промахи относительно редки.

Иерархическая организация таблицы страниц

Проблема:

размер таблицы страниц. Объем виртуальной памяти современного компьютера - 2³²,…2⁶⁴

Пример:

V_вирт.= 2³²

V_стр. = 2¹²

(4Kb)

Количество виртуальных страниц – 2²⁰ (много)

Решение:

использование многоуровневых таблиц страниц (2^х, 3^х, 4^х)

Двухуровневая организация

Остается проблема для 64-х разрядных вычислительных систем (иерархические решения => количество уровней неприемлемо).

Использование хэштаблиц

•Обычно используются для адресации

•Используется больше 32 разрядов.

Веделяется номер страницы, срабатывает хэш-функция, поиск виртуальной страницы.

Инвертированные таблицы страниц

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

Достоинство:

Не надо использовать много таблиц, таблица одна для всех процессов.

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

Достоинство страничной организации:

В памяти может находится небольшая часть процесса.

Проблема загрузки «новой» страницы в память. Необходимо выбрать страницу для удаления из памяти (с учетом ее модификации и пр.). Т.е.:

1. планирование той страницы, которую надо загрузить.

2. Куда её надо загрузить.

Если есть место, то надо замещать. Что замещать – определяется по двум критериям:

1. как долго страница находилась в памяти

2. Как интенсивно использовалась.

Алгоритм NRU (Not Recently Used – не использовавшийся в последнее время)

Используются биты статуса страницы в записях таблицы страниц.

R - обращение

M - изменение устанавливаются аппаратно

Обнуление – программно (ОС).

Алгоритм:

1.При запуске процесса M и R для всех страниц процесса обнуляются

2.По таймеру происходит обнуление всех битов R

3.При возникновении страничного прерывания ОС делит все страниц на классы:

•Класс 0: M=R=0.

•Класс 1: M=1, R=0.

•Класс 2: M=0, R=1.

•Класс 3: M=R=1.

4.Случайная выборка страницы для удаления в непустом классе с минимальным номером

Стратегия:

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

Алгоритм FIFO

«Первым прибыл – первым удален» - простейший вариант FIFO. (проблемы «справедливости» - выбор самой старой страницы).

Модификация алгоритма (алгоритм вторая попытка):

1.Выбирается самая «старая страница». Если R=0, то она заменяется

2.Если R=1, то R – обнуляется, обновляется время загрузки страницы в память (т.е. переносится в конец очереди). На п.1

Алгоритм Часы

1.Если R=0, то выгрузка страницы и

стрелка на позицию вправо.

2.Если R=1, то R-обнуляется, стрелка на

позицию вправо и на П.1.

(все страницы организованы в

циклический список)

Алгоритм LRU (Least Recently Used – «менее недавно» - наиболее давно используемая страница)

Вариант возможной аппаратной реализации.

Памяти N – страниц.

Битовая матрица NxN (изначально все биты обнулены).

При каждом обращении к i^ой странице происходит присваивание 1 всем битам i^ой строки и обнуление все битов i^го столбца.

Строка с наименьшим 2^ным кодом соответствует искомой странице.

(аппаратная реализация крайне тяжелая).

Алгоритм NFU (Not Frequently Used – редко использовавшаяся страница)

Программная модификация LRU.

Для каждой физической страницы i – программный счетчик Count_i

Характеристики

Список файлов лекций