Задача размещения информации

Суть задачи: В результате решения задачи размещения (ЗР) в каком-либо АП выбираются конкретные страницы или сегменты, на которые отображается информация.

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

1. ОП и ВП значительно отличаются по размерам;

2. Эти пространства отличаются методами доступа к информации.

При рассмотрении этих задач выводятся следующие коэффициенты:

Размеры N_В > > N_ОП

Коэффициент расщепления АП: α =L/N_В β = L/N_ОП , α, β < < 1 и α < < β

Для оценки качества решения ЗР понятие фрагментации АП

· Внешняя фрагментация: между областями АП, выделенных под что-либо

· Внутренняя фрагментация: вследствие неполной занятости страниц или сегментов

Потери от фрагментации влияют на показатели: с увеличением фрагментации уменьшается темп обслуживания процессов и уменьшается коэффициент мультиплексирования АП (связан с количеством процессов, занимающих АП).

Рассмотрим алгоритм для выделения ВП:

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

Алгоритм строится с учетом уменьшения количества обращения к внешнему адресному пространству.

ЗР считается длинным процессом с точки зрения выполнения.

Пример:

N_ОП=512 Mb N_ВОП=4Gb

ВАП состоит из последовательных номеров страниц от 0 до max количества страниц.

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

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

Чтобы помнить что занято, а что не занято, хранят номер первой незанятой страницы М₀. ТО есть для идентификации реального свободного пространства системе нужно знать только М₀. По мере выполнения, процессы исчезают. В занятом секторе образуются псевдосвободные АП (псевдодыры в адресах).

При функционировании ВАП и решении ЗР псевдосвободные АП во внимание не принимаются. То есть даже если псевдодыры новый процесс размещается с М₀. Есть вероятность, что M₀ превысит максимум страниц. Выполняются алгоритм, который позволяется все псевдосводные участки собирает в свободный сектор АП. Все занятые адреса смещаются вниз. Всё это называется алгоритм перемещения без переиспользования.

Теперь в ОП. Предыдущий алгоритм не может быть использован, потому что:

· Слишком часто будет переполняться

· Возникают большие накладные расходы по перемещению занятых и свободных страниц.

В данном случае используется свойство процессов, что запрос на выделение памяти может потребовать только одну страницу. В этом случае для исполнения данного запроса может быть выделена любая свободная страница без ограничения на смежные страницы. Учет свободных и занятых страниц в самом простом случае может осуществляться с помощью двоичного вектора. Количество разрядов соответствует количеству страниц ОП. Занята или не занята фиксируется признаком 0 и 1. При выборе свободной страницы данный вектор сканируется и выбирается первая свободная страница. В неё размещается страница, вызываемая из ВАП.

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

Второй вариант – структуризация адресных пространств страницами переменной длины или сегментами.

Отличие – размер изменяется от 1 до размеров ОП.

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

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

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