Организация памяти в современных ОС

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

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

Адрес состоит из двух компонентов: номер сегмента, смещение внутри сегмента.
Большинство современных ОС поддерживают сегментную организацию памяти. В некоторых архитектурах (Intel, например) сегментация поддерживается оборудованием.

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

Логические и физические адресные пространства ни по организации, ни по размеру не соответствуют друг другу. Максимальный размер логического адресного пространства обычно определяется разрядностью процессора (например, 2³²) Процессор и ОС должны быть способны отобразить ссылки в коде программы в реальные физические адреса, соответствующие текущему расположению программы в основной памяти. Такое отображение адресов называют трансляцией (привязкой) адреса или связыванием адресов.

Стек представляет собой непрерывную область памяти, адресуемую регистрами ESP (указатель стека) и SS (селектор сегмента стека). Особенность стека заключается в том, что данные в него помещаются и из него извлекаются по принципу «первым вошел — последним вышел». Данные помещаются в стек с помощью инструкции PUSH (заталкивание), а извлекаются по инструкции POP (вытаскивание). Стек автоматически используется процессором при выполнении инструкций вызова, возвратов, входа и выхода из процедур, а также при обработке прерываний.

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

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

Выделение у системы большого количества объектов небольшого размера оказывается. Решение этой проблемы организуется следующим образом: у операционной системы выделяется достаточно большой участок памяти, а уже из него для прикладной программы "нарезаются" небольшие участки. Такая организация называется кучей, а механизм, который следит за выделением и освобождением участков памяти называется менеджером кучи. Куча позволяет решить как проблему потери производительности - менеджер кучи может функционировать на уровне прикладной программы, так и проблему гранулярности - менеджер запрашивает у системы один большой участок памяти.

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

4. Доминирующие множества и алгоритмы их построения. Использование доминирующих множеств.

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

Для графа на рис.2.4 доминирующими множествами (ДМ) являются: , , .

Доминирующее множество называется минимальным (МДМ), если и

(, (2.10)

или можно определить МДМ следующим образом: подмножество вершин есть МДМ, если

,

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

Для графа на рис.2.4 МДМ являются: , . Если - семейство всех МДМ, то число

(2.11)

называется числом доминирования графа , а множество , на котором достигается минимум, называется наименьшим ДМ. Так для графа на рис.2.4 наименьшим ДМ является множество и 2.

ДМ может быть определено и как множество такое, что

. (2.12)

Утверждение 2.1. Доминирующее множество является минимальным тогда и только тогда, когда для каждой выполняется одно из следующих двух условий:

1. Для , не существует дуг таких, что ;

2. Существует такая, что, , причем является единственной дугой из в .

Для того чтобы не было ДМ, необходимо и достаточно, чтобы не выполнялось хотя бы одно из этих условий.

Утверждение 2.2. Любой неориентированный граф без изолированных вершин имеет такое ДМ , что его дополнение также является ДМ.

Утверждение 2.3. Если – неориентированный граф без изолированных вершин, то дополнение , где – минимальное доминирующее множество, является ДМ.

Утверждение 2.4. Если - неориентированный граф без изолированных вершин, то для любого МДМ существует другое, не пересекающееся с ним ДМ.