26. Явление пробуксовки в страничных системах и стратегия рабочего множества.

Стратегия управления страничной памятью с замещением страниц предполагает неограниченный уровень мультипрограммирования. Действительно. размер страниц обычно берется не более 4 Кбайт, а размер ОП составляет 1 Мбайт и более. Таким образом, число страниц ОП несколько сотен. Если для каждой задачи выделять десять страниц то в памяти одновременно может находиться несколько десятков задач Это уже достаточно высокий уровень мультипрограммирования. Но в ВС со страничной памятью с замещением страниц физическая память включает и внешнюю память на диске. Поэтому активная задача, если она находится в состоянии ожидания, может содержаться во внешней памяти, объем которой весьма велик.

Однако на практике уровень мультипрограммирования в ВС с такой стратегией управления памятью ограничен явлением, которое носит название "пробуксовка". Суть его состоит в следующем.

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

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

Стратегия "рабочего множества" используется во многих системах, так как явление пробуксовки возникает часто, если не принимать соответствующих мер.

27. Управление памятью с сегментным распределением.

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

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

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

Программный адрес

ОП

S L

Таблица

страниц

задачи

B

B

Физическая

L

страница

+

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

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

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

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

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

Учет сегментов задачи можно осуществлять с помощью таблицы сегментов задачи и таблицы внешних сегментов. Таблица сегментов задачи содержит элементы, каждый из которых связан с сегментом задачи. Структура элемента таблицы сегментов представлена на рисунке, где В - базовый адрес сегмента в ОП, s - бит состояния, RW - бит использования,Lmax - длина сегмента.

Lmax RW s B

Если бит состояния указывает, что в ОП сегмента нет, то по таблице внешних сегментов определяется его местоположение на диске.

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

Алгоритм программного обеспечения

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

АЛГОРИТМ

Поиск свободного участка в ОП для размещения сегмента.

ЕСЛИ Отсутствует свободный участок

ТО Определить общий объем свободной памяти

ЕСЛИ Общий объем свободной памяти удовлетворяет запроса

ТО Произвести перекомпоновку сегментов в ОП

ИНАЧЕ Удалить подходящий сегмент

ВСЕ ЕСЛИ

ВСЕ ЕСЛИ

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

Прочитать сегмент в ОП.

Откорректировать таблицу сегментов и список свободных участков.

Повторить команду.

КОНЕЦ

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

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

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