АРХИТЕКТУРА ПРОГРАММНЫХ СИСТЕМ

во время выполнения ЗЧ (ПРС)
Динамические алгоритмы - допускающие перераспределения ОП

во время выполнения ЗЧ (ПРС)
Распределение разделами – статический алгоритм, при котором ОП при инициализации ОС разделяется на фиксированные по объему области – РАЗДЕЛЫ. Каждое ЗД получает раздел и выполняет свои ЗЧ в этом разделе по очереди. Монитор Управления Памятью (УП) регистрирует свободные и занятые разделы, назначает ЗД и ЗЧ на раздел и снимает после окончания.
Требование к монитору УП определяется объемом модуля М (например, 4,5 Mb), для которого монитор ищет подходящий раздел Pi  M. Оставшаяся память раздела Pi не используется (простаивает). Простой достигает 50% памяти раздела. Критерий поиска раздела min [(Pi – M)>0] (i=1,,n), n – число разделов.
Число параллельных процессов в таком алгоритме УП не превышает числа разделов n, опреленного заранее. Даже при наличии свободной памяти новых разделов не создать.

М2 ....

ОС
Р1

2. Распределение перемещаемыми разделами. Разделы . перекомпоновываются при назначении ЗД и ЗЧ на раздел, причем допустимо увеличение числа разделов при наличии свободной памяти. В ОС существует список или Таблица областей свободной памяти {Vсвi}. Новый модуль M получает раздел по критерию min [(Vсвi - M)>0], а остаток памяти (Vсвi – M) поступает в список областей свободной памяти. Если в списке свободной памяти нет областей для размещения модуля M , то выделенные разделы сдвигаются к началу ОП и освобождают непрерывную область свободной памяти, в которой образуется новый раздел с модулем M. Процедура перемещения свободных разделов называется реорганизацией ОП или сборкой мусора (Garbage collection).
Вероятность удовлетворения запроса растет, если уменьшаются требования к основной памяти от модуля M.

создание нового раздела, 3) реорганизация памяти, 4) размещение большого раздела

состоит из компонент с отредактированными связями. Компоненты A,B,C,D настроены на

абсолютные или относительные адреса основной памяти

Разновидности модулей, загружаемых в основную память. Модуль простой структуры M – требует память объема V = Va+Vв +Vc +Vd, после получения памяти программы и данные модуля загружаются в выделенную область V и выполняются. После выполнения память возвращается.
Модуль оверлейной структуры M – требует память объема V, равного максимальному объему альтернативной ветви V = max (Va+Vв, Va +Vc +Vd), после получения памяти V в нее последовательно загружаются ветви A,B затем A,С,D и выполняются. После выполнения память возвращается.

такого объема, который соответствует текущим требованиям модуля V = (Va

, Va+Vв, Va, Va +Vc, Va +Vc +Vd), память распределяется по мере выполнения. Организация модуля соответствующей структуры осуществляется на фазе редактирования связей по соответствующему описанию. Программы и данные компонент пишутся (транслируются) на память, размещенную в непрерывной области, начиная от некоторой базы.
Потери от управления памятью на основе модели разделов 1. Потери производительности ПРЦ возникают из-за временной недоступности частей ОП из-за раздробленности ОП на небольшие области в составе разделов или в составе списка свободных областей памяти. Небольшие куски раздробленной ОП не удовлетворяют большинству запросов и приводят к простоям ПРЦ на время реорганизации.
2. Потери также связаны с медленным обменом ОП и ВНП при необходимости заместить объекты ОП на объекты ВНП и наоборот.

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

остается надежным. Надежное состояние — это состояние, при котором общая ситуация с ресурсами такова, что все пользователи имеют возможность со временем завершить свою работу. Ненадежное состояние — это состояние, которое может со временем привести к тупику.
Вычислительный процесс Выделено Мах потребность
ВПРС1 4 6
ВПРС2 1 5
ВПРС3 3 5
ВПРС4 2 9
Свободно - 2

информация размещается кусочно в N непрерывных областях ОП или страницах

фиксированного размера (1К, 2К, 4К, 256К ...1M, 4М….).
Хотя физически N страниц могут быть размещены в любых областях ОП, при написании программы используется модель размещения информации в N непрерывных логических страницах с адресами от 0 до N-1.
Связь логического адреса страницы P с адресом его фактического размещения обеспечивает страничная организация памяти.
Существуют варианты организации Таблицы страниц:
Таблица, содержащая все страницы виртуальной памяти (ВИП) – следующий слайд
Таблица, содержащая столько строк сколько страниц в ОП – последующий слайд Ассоциативная Таблица страниц использует номер страницы P как ключ ассоциативного поиска.

стр. Р Запись (ФА,О ) по адр.P (например: Р=1) Обмен В_СТР

с О_СТР

Адр_Табл_Стр

1

2

3

Запрос стр.ОП с вытеснением Выдел_ФА занятой стр.ОП Pj: Откачка О_СТР в В_СТР Pj Отметка в Pj.ТАБЛ_СТР (О->C) Запись (ФА,О ) по освоб. адр. О_СТР Обмен В_СТР Pi с О_СТР

ВНП

ОП

Обмен

1000000:

стр. Р Запись (ФА,О ) по адр.P (например: Р=1, C->О) Обмен

В_СТР с О_СТР

АДР_Табл_стр

1

2

3

Запрос стр.ОП с вытеснением Выдел_ФА занятой стр.ОП Pj: Откачка О_СТР во В_СТР Pj Отметка в Pj.ТАБЛ_СТР (О->C) Запись (ФА,О ) по освоб. адр. О_СТР Обмен В_СТР Pi с О_СТР

Ассоциатив-ная Табл_стр

ВНП

ОП

Обмен

ОП.
Диспетчер ОП содержит список свободных страниц, на основе которого

удовлетворяет запросы ЗЧ. Если свободного места не хватает, то существуют алгоритмы замещения, в соответствии с которыми часть страниц ОП временно перегружается в соответствующие им страницы ВНП (что препятствует появлению «клинчей» или блокировок по памяти), а освободившееся место поступает в список свободных страниц и перераспределяется.
Потери от управления памятью со страничной организацией:
Замедление времени исполнения за счет обменов ОП-ВНП
Издержки внутренней фрагментации, возникающие из-за неполного использования модулем объема страницы (размер кода модуля не кратен размеру страницы)
Возможность большого числа перезагрузок страниц ОП-ВНП во время выполнения.

очередного шага ПРС мы выталкиваем страницу, которую будем использовать на

следующем шаге, через шаг...

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

адресная структура отражает содержательное членение информации. Сегменты или секции объединяют

модули программ и данных, которые выполняют вместе некоторую вычислительную работу (ПРС). В программе сегменты и входящие в них объекты выделяются описанием.
В случае сегментно-страничной организации памяти откачка осуществляется для страниц сегмента N, а не для страниц сегмента S, за счет того что Таблица страниц сегмента S будет использована для поиска кандидатов на откачку в самую последнюю очередь.
Принципиальная возможность откачивать не нужные в данный момент страницы чужих или в крайнем случае своего сегмента дает возможность выполнять модули с числом страниц m>M - максимального числа страниц ОП.

| b
АДР_Табл_Сегм
О
ФА_Тстр_N
…

О
ФА_Тстр_S
Табл.Сегментов
…

Data S.P3
Data S.P4
Пример выбора страниц сегмента на замещение
Выталкивание страниц

минимальное количество страниц сегмента, которое допускает продвижение ПРС вперед. Откачка

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

При наличии в ОП 1/3 страниц сегмента, поток заявок на обмен падает до приемлемого уровня

пробуксовки и сохранения РН использовать хорошие стратегии вытеснения страниц.
FIFO LRU OPT
FIFO –

Учет времени. Уход самой старой страницы по времени пребывания в ОП (плох при плотной загрузке ВС, поскольку вытесняет страницы РН)
LRU – Учет числа обращений. Удаление страницы, которой не пользовались долее всего (Last Recently Used).
OPT – Удаление тех страниц ОП, которые наименее нужны в будущем (алгоритм Биледи требует знания предистории)
Разница OPT и LRU в пределах 30%, поэтому LRU очень популярен в реализациях.

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

и быстродействия запоминающих устройств. Например:
Виртуальная память (ВИП) – модель памяти

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