Операционные системы.
Операционные системы различаются особенностями реализации алгоритмов управления ресурсами компьютера, областями использования. Так, в зависимости от алгоритма управления процессором, операционные системы делятся на:
Однозадачные и многозадачные
Однопользовательские и многопользовательские
Однопроцессорные и многопроцессорные системы
Локальные и сетевые.
По числу одновременно выполняемых задач операционные системы делятся на два класса:
Однозадачные (MS DOS)
Многозадачные (OS/2, Unix, Windows)
В однозадачных системах используются средства управления периферийными устройствами, средства управления файлами, средства общения с пользователями. Многозадачные ОС используют все средства, которые характерны для однозадачных, и, кроме того, управляют разделением совместно используемых ресурсов: процессор, ОЗУ, файлы и внешние устройства.
В зависимости от областей использования многозадачные ОС подразделяются на три типа:
Системы пакетной обработки (ОС ЕС)
Системы с разделением времени (Unix, Linux, Windows)
Системы реального времени (RT11)
Системы пакетной обработки предназначены для решения задач, которые не требуют быстрого получения результатов. Главной целью ОС пакетной обработки является максимальная пропускная способность или решение максимального числа задач в единицу времени. Эти системы обеспечивают высокую производительность при обработке больших объемов информации, но снижают эффективность работы пользователя в интерактивном режиме. В системах с разделением времени для выполнения каждой задачи выделяется небольшой промежуток времени, и ни одна задача не занимает процессор надолго. Если этот промежуток времени выбран минимальным, то создается видимость одновременного выполнения нескольких задач. Эти системы обладают меньшей пропускной способностью, но обеспечивают высокую эффективность работы пользователя в интерактивном режиме. Системы реального времени применяются для управления технологическим процессом или техническим объектом, например, летательным объектом, станком и т.д.
Системой жесткого реального времени называется система, где неспособность обеспечить реакцию на какие-либо события в заданное время является отказом и ведет к невозможности решения поставленной задачи. Многие теоретики ставят здесь точку, из чего следует, что время реакции в жестких системах может составлять и секунды, и часы, и недели. Однако большинство практиков считают, что время реакции в системах жесткого реального времени должно быть все-таки минимальным. Большинство систем жесткого реального времени являются системами контроля и управления. Такие СРВ сложны в реализации, так как к ним предъявляются особые требования в вопросах безопасности.
Точного определения мягкого реального времени не существует, поэтому можно отнести сюда все СРВ, не подпадающие в категорию жестких. Так, система мягкого реального времени может не успевать все делать в заданное время, поэтому возникает проблема определения критериев успешности (нормальности) ее функционирования. По числу одновременно работающих пользователей на ЭВМ ОС разделяются на однопользовательские (MS DOS) и многопользовательские (Unix, Linux, Windows 95 - XP) В многопользовательских ОС каждый пользователь настраивает для себя интерфейс пользователя, т.е. может создать собственные наборы ярлыков, группы программ, задать индивидуальную цветовую схему, переместить в удобное место панель задач и добавить в меню Пуск новые пункты. В многопользовательских ОС существуют средства защиты информации каждого пользователя от несанкционированного доступа других пользователей. Многопроцессорные и однопроцессорные операционные системы. Одним из важных свойств ОС является наличие в ней средств поддержки многопроцессорной обработки данных. Такие средства существуют в OS/2, Net Ware, Widows NT.По способу организации вычислительного процесса эти ОС могут быть разделены на асимметричные и симметричные. Одним из важнейших признаков классификации ЭВМ является разделение их на локальные и сетевые. Локальные ОС применяются на автономных ПК или ПК, которые используются в компьютерных сетях в качестве клиента. В состав локальных ОС входит клиентская часть ПО для доступа к удаленным ресурсам и услугам. Сетевые ОС предназначены для управления ресурсами ПК включенных в сеть с целью совместного использования ресурсов. Они представляют мощные средства разграничения доступа к информации, ее целостности и другие возможности использования сетевых ресурсов.
Вычислительная среда (система) – это совокупность аппаратуры и операционной среды.
ОС – это преобразователь с языка возможностей аппаратуры на язык пользователя.
Аппаратура:
ЦП (центр и ядро системы 4*3 ГГц)
Кэш (скорость сравнима со скоростью ЦП)
ОЗУ (частота системной шины 0,5-1 ГГц)
устройства ввода-вывода
каналы ввода-вывода
групповые устройства ввода-вывода
Ресурс – это объект, распределяемый (в пространстве либо во времени) внутри системы.
2 способа распределения ресурсов:
Централизованный (сейчас основной) – кто-то один отвечает
Децентрализованный – каждое приложение отвечает
Основные функции операционной среды.
Обеспечение интерфейса между аппаратурой и прикладными программами
Предоставление средств для работы с большими структурами данных
Распределение времени процессора
Управление оперативной памятью
Обеспечение средствами виртуальной памяти
Управление вводом-выводом
Разделение программных ресурсов (реентерабельные программы – программы, в которых исполняемый код отделен от программы)
Синхронизация
Ключевая цель ОС – эффективное использование ресурсов при хорошем обслуживании задач.
Эксплуатационные требования к ОС:
Надежность – не ниже надежности аппаратуры.
Защищенность объектов операционной среды – защита пользователя от чужих ошибок и от злоумышленников.
Предсказуемость операционных характеристик вычислительной системы – скорость (время) выполнения задач.
Эффективность – ОС должна занимать минимум ресурсов (оперативная память, время ЦП).
Удобство работы пользователя в ОС.
ОС общего назначения как правило использует централизованное управление ресурсами
Все программы ОС и приложений подчиняются главной программе – супервизору (ядру).
Функции супервизора:
Контроль и управление выполнения задач пользователей.
Организация связи между программами.
Защита ОС и пользователей.
Обслуживающие программы супервизора – наиболее часто используемые функции, которые обладают низкой трудоемкостью.
Преимущества супервизора:
Простота организации – все основные функции в одном месте.
Простота реализации функций управления и защиты – все обращения с системным функциям и внешней среде проходят через супервизор.
Недостатки супервизора:
Супервизор может быть узким местом среды – при интенсивном обращении к супервизору за служебными функциями.
Трудность внесения изменений в функции супервизора – все функции супервизора тесно связаны.
Практически все современные аппаратные платформы имеют некоторый типичный набор средств аппаратной поддержки ОС, в который входят следующие компоненты:
средства поддержки привилегированного режима;
средства трансляции адресов;
средства переключения процессов;
система прерываний;
системный таймер;
средства защиты областей памяти.
Процессы.
Аппаратура ЭВМ работает параллельно.
ОС выполняет множество задач.
Процесс – формализация идеи независимости
Работа (задание)
Т.к. работы выполняются независимо, то и процессы должны быть независимы.
Поскольку компоненты ЭВМ работают с различными скоростями, то процессы, в общем случае, должны выполняться с различными скоростями.
Свойства процессов:
Независимые работы
Параллельное выполнение работ
Различные скорости выполнения работ
Иногда процессам необходимо обмениваться информацией (межпроцессное взаимодействие).
Процесс – это некая область памяти (множество ячеек), содержимое которых изменяется по определенным правилам. Эти правила описываются программой, представляющей этот процесс.
Процесс – это пространство состояний набора переменных (переменные состояния).
Состояния описываются заданием значений всех переменных.
Действие – это присваивание значений некоторым переменным состояния.
Функция действия – это функция, отображающая состояние в действие.
Обычно функция действия – это код программы.
Переменные состояния – это ячейки памяти с данными.
Процесс – это некая программа, данные, которые она обрабатывает и некий дескриптор, описывающий состояние процесса в реальной вычислительной среде.
Дескриптор – это некоторая структура данных, в которой содержится информация о процессе
Переменная состояния (определяет текущее состояние процесса):
готов к работе – в очереди готовых процессов
работающий (текущий) – на процессоре
заблокирован – в очереди ожидания (операции ввода-вывода, операции синхронизации)
Область сохранения (текущие значения регистров и других параметров системы, сохраняется при прерывании процесса).
Информация о ресурсах, которыми владеет процесс.
Разделяемые переменные, структуры данных, которые необходимы для общения с другими процессами.
Общение между процессами.
Процессы разделяют ресурсы (ЦП, внешние устройства, переменные, структуры и т.д.)
Критический ресурс – это такой ресурс, который допускает обслуживание только одного процесса в каждый момент времени.
Процессы, использующие один и тот же критический ресурс необходимо синхронизировать.
Участок программы, в котором используется критический ресурс, называется критическим участком.
Критические участки должны быть взаимно исключаемыми. Нужен некий механизм синхронизации.
Механизм синхронизации.
Свойства:
Если один или более процессов желает войти в критический участок, то один из них должен получить разрешение на вход.
В каждый момент времени только одному процессу разрешается находится в критическом участке.
Инструменты синхронизации.
Инструменты, основанные на неделимых операциях центрального процессора (нужны в многопроцессорных вычислительных системах).
Инструменты, основанные на низкоуровневых примитивах – низкоуровневые методы синхронизации (семафоры).
Высокоуровневые инструменты синхронизации.
Два источника параллелизма:
Независимые потоки команд (различные программы).
Несвязанные потоки данных.
Синхронизация на основе операций блокировки памяти.
Все операции в ЦП – неделимые для процессов.
Алгоритм Деккера (для синхронизации двух процессов).
{
bool c1, c2;
int q;
c1 = c2 = 0;
q = 1;
//c1, c2 - намерение процесса войти в критический участок
parbegin
процесс 1: {
c1 = 1;
while (c2 == 1) {
if (q == 2) {
c1 = 0;
while (q == 2) { }
c1 = 1;
}
}
<критический участок>
c1 = 0;
q = 2;
<оставшаяся часть первого процесса>
}
процесс 2: {
c2 = 1;
while (c1 == 1) {
if (q == 1) {
c2 = 0;
while (q == 1) { }
c2 = 1;
}
}
<критический участок>
c2 = 0;
q = 1;
<оставшаяся часть второго процесса>
}
parend
}
Минус– активное ожидание входа в критический участок.
Метод, основанный на неделимой операции «проверить и установить» - ПИУ – TSL
ПИУ(локальная переменная, общая переменная) => лок = общ; общ = 1;
begin int общ; общ := 0;
parbegin
П1:
begin
int лок1;
лок1 := 1;
do while (лок1 = 1)
ПиУ(лок1, общ)
end
<критический участок>
общ := 0;
<остальное>
end
П2:
begin
int лок2;
лок2 := 1;
do while (лок2 = 1)
ПиУ(лок2, общ)
end
<критический участок>
общ := 0;
<остальное>
end
parend
end
Минус– активное ожидание
Механизмы с пассивным ожиданием входа в КУ.
Реализуется через средства, расположенные в супервизоре.
Семафоры – прием, позволяющий реализовать пассивное ожидание.
Бывают общие и двоичные.
Семафор 
– целочисленная переменная, над которой
определены 2 неделимые операции: операция
– запросить ресурс либо вход в КУ, и 
– вернуть ресурс или выйти из КУ.
1)
2)
Если 
,
то процесс продолжает работать
3) Если 
,
то процесс останавливается и встает в
очередь
Процесс находится
в очереди ожидания, пока 
,
выполняемая другим процессом, не вернет
ресурс и не запустит другой процесс.
1)
2)
Если 
,
то процесс продолжает работу
3) Если 
,
то один из процессов удаляется из очереди
ожидания, получает ресурс и конкурирует
с текущим процессом за право получить
время ЦП.
Количество
конкурирующих процессов (
– количество ресурсов в системе
Возврат в прикладной процесс произойдет после завершения запроса к супервизору.
Двоичный семафор
1 – ни один процесс не находится в КУ
0 – один процесс находится в своем КУ
-1 – 1 процесс в КУ, 1 процесс ожидает вход в КУ
Алгоритм синхронизации 2-х процессов:
begin
int своб; своб = 1;
parbegin
П1:
begin
<начало П1>
P(своб)
КУ П1
V(своб)
<конец П1>
end
П2:
begin
<начало П2>
P(своб)
КУ П2
V(своб)
<конец П2>
end
parend
end
Задача поставщик-потребитель (используется при вводе-выводе)
Используется общий семафор
2 процесса:
поставляет данные для обработки
ведет обработку данных
Для общения процессов используется буфер обмена.
Общие семафоры:
Буф – количество свободных буферов
Зан – количество занятых буферов
Двоичный семафор: Синхро – используется для синхронизации работы с очередями
begin int буф, зан, синхро;
буф = <количество буферов в системе, выделенных для решения задач>
зан = 0;
синхро = 1;
parbegin
П1(поставщик):
begin
do while (true)
<приготовить данные>
P(буф)
P(синхро)
<взять буфер из списка>
<послать сообщение>
V(зан)
V(синхро)
end
end
П2(потребитель):
begin
do while (true)
P(зан)
P(синхро)
<получить сообщение>
V(буф)
V(синхро)
<обработка сообщения>
end
end
parend
end
В нетривиальных системах очень часто требуется организация сложного ожидания:
Одного из нескольких ресурсов
Нескольких ресурсов
Одного из нескольких событий
Нескольких событий
1+2+3+4
2 и 4 необходимо реализовывать через 1 и 3.
Мониторы.
Монитор– набор управляющих структур и процедуры доступа к ним. Эти процедуры неделимы для прикладных процессов и реализованы в ядре/супервизоре.
Монитор позволяет организовать сложные ожидания и взаимодействия процессов.
Ожидания:
1 из ресурсов из списка
1 из событий из списка
ограничения ожидания по времени
Монитор, основанный на таблице синхронизации.
Таблица синхронизации
|
Проц |
Обл. сохр |
Готовн |
Тай |
Ресур |
Соб1 |
Соб2 |
… |
СобN |
|
P1 |
Обл1 |
Не гот |
0 |
Спис1 |
0 |
1 |
|
1 |
|
P2 |
Обл2 |
Готов |
0 |
0 |
0 |
0 |
|
0 |
|
P3 |
Обл3 |
Не гот |
5 |
Спис3 |
1 |
1 |
|
1 |
|
… |
|
|
|
|
|
|
|
|
|
PM |
ОблM |
Готов |
0 |
0 |
0 |
0 |
|
0 |
PM– системный процесс
Процедуры работы с ТС:
TP(указатель на список ресурсов, указатель на список событий, таймаут) – запрос всего
TV(ресурс) – возврат ресурсов
TWAIT(указатель на список событий, таймаут) – запрос событий
TPOST(событие) – извещение о наступлении события
Процесс CLOCK
TP(указатель на список ресурсов, указатель на список событий, таймаут)
begin <задержать текущий процесс>
for i=1 to <число семафоров в процессе> do
if семафор(i)>0 then
<взять ресурс из списка ресурсов>
<передать семафор и экземпляр ресурса в область сохранения процесса>
<активизировать задержанный процесс>
end
end
табл[текущий, готовность]="не готов"
табл[текущий, таймер]=Tout
табл[текущий, ресурсы]=указатель на список ресурсов
<отметить в столбцах заказанные события>
<активизировать наиболее приоритетный процесс>
end
TV(семафор, ресурс)
begin <задержать текущий процесс>
for i=1 to <число строк в таблице> do
if <список ожидающих ресурсов содержит возвращаемый ресурс> then
<передать в область сохранения Pi адрес семафора и адрес ресурса>
for j=3 to <количество столбцов в таблице> do
табл[i, j]=0
end
табл[i, готов]=да
if i<текущий then
<активизировать Pi>
else
<активизировать текущий>
end
end
end
<возвратить ресурс в систему>
<активизировать текущий процесс>
end
TWAIT(указатель на список событий, Tout)
begin <задержать текущий процесс>
табл[текущий, готовность]= не готов
табл[текущий, таймер] = Tout
<отметить в таблице события, указанные в запросе>
<активизировать наиболее приоритетный процесс>
end
TPOST(событие)
begin <задержать текущий процесс>
for i = 1 to <количество строк в таблице> do
if табл[i, событие] <> 0 then
for j = 3 to <количество столбцов в таблице> do
табл[i, j] = 0
end
<отметить в области сохранения Pi наступление события>
табл[i, готовность] = готов
if i < текущий then
<активизировать Pi>
else
<активизировать текущий процесс>
end
end
end
<активизировать текущий процесс>
end
Процесс CLOCK
begin
do while (true)
<запустить на один цикл работы таймера текущий процесс>
for i = 1 to <количество строк в таблице> do
if табл[i, таймер] then
табл[i, таймер]--
if табл[i, таймер] = 0 then
for i = 3 to <количество столбцов в таблице> do
табл[i, j] = 0
end
табл[i, готов] = да
end
end
текущий = <самый приоритетный готовый процесс>
end
end
Тупики.
Ситуация, в которой процессы ждут друг друга неопределенно долго.
Вычислительная система = множество состояний + множество процессов
Процесс– это функция, отображающая одно состояние в другое
Необходимые условия тупика:
Условие взаимоисключения (монопольного управления ресурсами).
Условие ожидания ресурсов (процесс удерживает за собой некоторый набор ресурсов, и для продолжения работы требует (ожидает) еще дополнительных ресурсов).
Условие неперераспределяемости ресурсов (ресурсы нельзя отобрать насильно, ресурсы освобождаются добровольно после завершения обработки).
Условие кругового ожидания (процессы образуют замкнутую цепь, в которой каждый следующий процесс блокирует (занимает) те ресурсы, которые необходимы предыдущему процессу).
Тупик может наступить при выполнении всех 4 условий. Это необходимые условия.
Направления борьбы с тупиками:
Предупреждение (предотвращение) тупиков (нарушается одно из условий – стратегия Хавендера). Минус – неэффективное использование ресурсов.
Обход тупика (алгоритм банкира).
Тупики допускаются в вычислительных системах.
Обнаружение тупика и восстановление после него.
Стратегия Хавендера– нарушение одного из необходимых условий.
Нарушать нельзя (иначе - однопрограммность).
Все ресурсы, необходимые для обработки, запрашиваются сразу (в одном запросе). Минус– неэффективное использование ресурсов (простаивание ресурса по времени).
Разрешение насильного изъятия ресурсов у процессов. Минусы:
Возможность потери проделанной работы процессом, у которого изъяты ресурсы.
Возможность бесконечного откладывания процесса-жертвы.
Для всех процессов вводится упорядочение всех ресурсов по типам, запрос ресурсов возможен только в соответствие с номерами типов (в порядке, предусмотренном типами). Минусы:
Упорядочение ресурсов по типам может быть неудобно для некоторых процессов.
Усложняется разработка приложений.
Неэффективное использование ресурсов (простаивание ресурсов).
Алгоритм банкира– обход тупика.
Менее жесткие ограничения (по сравнению со стратегией Хавендера) => лучшее использование ресурсов.
Алгоритм:
Исходная информация:
Имеется K единиц ресурса.
Имеется N процессов.
Для каждого процесса известна потребность в ресурсах:
Максимальная потребность – MAXР.
Количество выделенных ресурсов – КВР.
Остаток потребности в ресурсах – ОР.
Проверка безопасности состояния при выделении ресурса (по запросу).
begin
сбоврес = k
for i = 1 to N do
begin
свобрес -= КВР[i]
ОР[i] = MAXР[i] - КВР[i]
тупик[i] = true
end
признак = true
do while признак
begin
признак = false
for i = 1 to N do
begin
if ОР[i] <= свобрес then
begin
свобрес += КВР[i]
признак = true
тупик[i] = false
end
end
end
if свобрес = K then
<состояние системы безопасное>
else
<состояние небезопасно>
end
Обнаружение и восстановление.
Установить факт тупика.
Определить количество процессов, вовлеченных в тупик.
Определить типы ресурсов, заблокированных в тупике.
Определение жертв-процессов.
Изъятие ресурсов у жертв => потеря проделанной работы.
Для снижения потерь используют реализацию точек отката (регистрируются в дескрипторе процесса, возможно сохранение на внешнем носителе).
Распределение времени процессора.
Основная причина введения принципа мультипрограммирования – стремление компенсировать существенно различные скорости ЦП и внешних устройств.
В вычислительной среде имеется смесь активных задач.
Различают 2 режима мультипрограммирования:
Режим разделения времени.
Существует 1 или более основных задач и совокупность фоновых задач. Фоновые задачи выполняются в периоды блокировки основных задач (вводы/вывода, ожидание событий).
Режим квантования времени.
Нет деления на основные и фоновые задачи.
Планирование времени процессора включает:
Способ выбора готового процесса на исполнение
Способ вычисления величины кванта
В общем случае каждому процессу ставится в соответствие число – приоритет (важность процесса).
Величина приоритета определяется статистическими и динамическими параметрами процесса.
Статистические:
Объем занимаемой памяти
Ожидаемое время выполнения
Ожидаемый ввод/вывод
Коэффициент важности задачи
Динамические:
Ресурсы, принадлежащие процессу
Общее время выполнения задачи
Количество процессорного времени, полученного за некоторый последний отрезок времени
Объем ввода/вывода за последний период времени
Время пребывания в заблокированном состоянии
При планировании используют следующие показатели производительности:
Загрузка ресурсов
Время простоя
Пропускная способность ВС
Время выполнения заданий
3 класса алгоритмов планирования:
По наивысшему приоритету (HPF – High Priority First)
Круговорот
Планирование с обратной связью – в системах пакетной обработки
Многоуровневое планирование
Разбивает задачу планирования на подзадачи
Планирование включает:
Работа с очередями
Переключение процессов
Вычисление приоритетов
Текущее измерение характеристик процессов
Элементы многоуровневого планирования:
Диспетчер
Кратковременный планировщик (более трудоемкий)
Долговременный планировщик (самый трудоемкий) – пересчитывает приоритеты
Управление памятью.
Управление памятью – отображение информации в оперативную память с помощью трех функций:
Именующая функция => отображает имя объекта, данное пользователем, в однозначный идентификатор информации.
Функция памяти => отображает идентификатор в программные адреса.
Функция содержимого (значения) – отображает программный адрес в значение , которое находится по этому адресу.
Имена пользователей, данные объектам –
Обработка программ включает этапы:
Компиляция
Сборка
Загрузка
Разрешение ссылок может быть выполнено несколькими способами:
Объединение модулей при компиляции
Объединение модулей
до загрузки на этапе сборки
во время загрузки
Объединение модулей откладывается до запуска на счет и реализуется системой (ОС) в процессе счета.
Исходная информация о модулях (объединяемых):
Модуль
Длина модуля.
Имена, описанные в модуле, на которые возможны ссылки из внешних модулей (ссылки внутрь).
Имена, не описанные в модуле, но на эти имена имеются ссылки (ссылки наружу).
Имена, адреса которых необходимо пересчитать в зависимости от положения модуля в собранной программе.
Работа сборщика.
Модули располагаются друг за другом.
При сборке составляется таблица сборщика.
|
Имя |
Ссылка разрешена |
Адрес объекта / список неразрешенных ссылок |
|
Имя 1 |
1 |
Адрес объекта, именуемый имя1 |
|
Имя2 |
0 |
Указатель на список неразрешенных ссылок |
После редактирования сборная программа существует в виде переместимого модуля загрузки, начинающегося с 0 адреса.
Главный вопрос задач распределения памяти состоит в том, чтобы решить, как объединенный модуль записать в ОЗУ.
Функция памяти – выдает переместимому модулю реальные ячейки памяти.
Статическое распределение
Привязку реализует
программист, компилятор до загрузки
загрузчик во время загрузки
Динамическое распределение
Привязка происходит во время выполнения программы
Узловые моменты привязки к памяти:
Программирование в абсолютных адресах => объединения отображений И и П раз и навсегда.
Программирование в символьных обозначениях.
Компилятор порождает адреса вместо символьных имен:
Порождаемые адреса – фиксированные абсолютные.
Привязка П происходит сразу же за И.
Порождаемые адреса допускают настройку и при загрузке получают абсолютные значения.
Привязка к памяти происходит во время загрузки.
Порождаемые адреса допускают настройку и получают абсолютные значения при каждом обращении к адресуемым объектам.
Привязка П реализуется при выполнении.
1, 2a, 2b – статическое
2c – динамические
Стратегии:
Перекрытие программ – планируется пользователем
Попеременная загрузка заданий – реализуется системой
Сегментация программ – ОС
Страничная организация памяти – ОС
3+4 = Сегментация программ со страничной организацией памяти
1, 2, 3… (Переписать)
Страничная организация памяти
Пространство адресов памяти делится на блоки фиксированной длины.
Программа – набор страниц той же длины.
N страниц – (n-1) страниц полные, n-ая неполная
Адрес: P – номер страницы
d – смещение внутри сегмента
Задание: таблица страниц – содержит описание страниц программ всего задания
ЦП – регистр в таблице страниц (РТСтр – таблица страниц текущего задания)
|
Признак (в памяти или нет) |
Биты защиты |
Адрес |
|
|
|
|
|
|
|
|
|
|
|
|
P – номер строки
Плюсы:
Перемещение страниц – нетрудоемкая задача (достаточно иметь список свободных страниц).
Минусы:
Для доступа к адресуемому объекту необходимо 2 обращения к ОЗУ.
Борьба: кеширование отображения контекст (идентификатор задачи) + P <-> адрес страницы
Кэш – ПАК
Невозможность совместного использования программ различными задачами.
Фрагментация при страничной организации памяти внутренняя (внутри страницы возможны неиспользуемые поля). При сегментной организации программ – внешняя (между сегментами возможны неиспользуемые поля).
Сочетание сегментной организации программ и страничную организацию памяти.
ОЗУ – разбивается на страницы фиксированной длины
Задание – совокупность сегментов с кодом и данными
Каждый сегмент делится на страницы той же длины
Адрес: S, P, d – номер сегмента, страницы, смещение
ЦП – РТС (регистр таблицы сегментов)
|
Размер сегмента |
Адрес таблицы страниц |
|
|
|
Плюсы: все преимущества сегментной организации программ и сегментной организации памяти.
Минусы:
Доступ к объекту требует 3 обращения к памяти.
Борьба – кэширование отображения контекст + S + P <-> физический адрес страницы.
Кэш – ПАК
Виртуальная память.
Цель: избавить программиста от необходимости учета ограничений размера физической памяти конкретной ВС при разработке приложения.
Виртуальная память основана на методах динамического распределения памяти.
Реализация ВП в том числе основана на аппаратных средствах.
Регистры, кэш, ОЗУ, HDD.
i < j:
M(i) быстрее M(j)
M(i) меньше M(j)
Удельная стоимость единицы памяти M(i) больше M(j)
Перемещение:
Страниц (4,5 метод)
Сегментов (3 метод)
Сегментация – логический подход к пространству адресов.
Страничная организация – физический подход.
Основные вопросы реализации ВП:
Как распределить память каждого уровня.
Какие критерии применять при подкачке адресуемых объектов.
Какие критерии применять при вытеснении АО.
Стратегии распределения памяти для сегментов переменной длины.
Задачи: найти стратегию распределения, которая
хорошо загружает память
при минимальных издержках распределяющих алгоритмов.
Решения:
Вести список свободной памяти.
Уплотнение множества фрагментов один экстент (непрерывная область)
Список свободной памяти – список пустот в нашей оперативной памяти.
Различают 3 классических способа ведения списков.
Список пустот, упорядоченных по возрастанию адресов
Пустота (указатель на следующую пустоту, длина)
Позволяет соседние пустоты объединять в одну пустоту.
Существует 2 стратегии поиска подходящей пустоты:
Выбор первой подходящей пустоты (
).Выбор самой подходящей пустоты (
).
Во многих случаях первая стратегия лучше загружает оперативную память, чем вторая.
Список пустот, упорядоченных по размерам пустот
При этом: 1 стратегия поиска дает 2-ю.
Пустота (указатель на следующую пустоту, длина)
Модификация способа 2:
Список пустот дополняется дополнительным списком (дополнительными указателями).
указывает на 1-ю пустоту размера 
Минусы:
Список трудно сопровождать.
Трудно объединить соседние пустоты.
Организация пустот системой расщепления.
Память представлена
множеством блоков размера 
где 
размер физической памяти.
Сопровождается
список.
Некоторые списки могут быть пустыми.
Поиск пустоты
размера 
:
Поиск начинается в списке
.
Если он не пуст, то выделяет пустоту.Если нет, поиск продолжается в списке
.
Если что-то есть, то пустота делится
пополам, 
пустоты отправляется в список 
,
а вторая часть пустоты предоставляется
запросу.
Если список S пуст, то запрос неудовлетворен.
Плюсы:
Легко сопровождать списки.
Легко объединять соседей.
Если не найдена пустота нужного размера:
Отказать в запросе
Вытеснить какой-нибудь сегмент
Выполнить операцию уплотнения (перегруппировка пустот и их объединение в единое целое)
Целесообразность:
Сумма пустот больше размера запроса
Если ЦП не загружен работой
Пустоты должны быть относительно велики (определяет трудоемкость уплотнения)
Стратегии подкачки:
Стратегия подкачки по запросу (по прерыванию).
Опережающая подкачка – при известной связи между сегментами/страницами.
Экономия на обработке прерываний.
Издержки – можно подкачать лишнего.
Стратегии вытеснения:
Случайный выбор.
Часто вытесняются нужные объекты.
FIFO.
Часто вытесняются нужные объекты.
Вытесняется по давности использования (LRU – Least Recently Used).
Имеет трудоемкое сопровождение.
Стратегия очень близка к оптимальной в большинстве случаев.
Оптимальное вытеснение – нереализуема.
Должна вытеснять объект, к которому не будет обращений дольше всего.
Используется для сравнения других стратегий.
Предписанные пользователем приоритеты.
Приоритеты, задаваемые задачам системой на основе измерений.
Смешанные методы – основаны на здравом смысле.
Для вытеснения предлагается на выбор список возможностей, упорядоченных по степени желательности:
АО
неактивной задаче, АО только для чтения.АО
неактивной задаче, АО только для записи.АО управляемый программой, к которой не было обращений уже
секунд.АО задачи, ожидающий в/в.
АО любой другой задачи.
Управление внешней памятью (на магнитном диске).
Время доступа к конкретной записи складывается из:
Время поиска цилиндра
(время позиционирования каретки с МГ)Время поиска записи на дорожке
Время чтения записи наших данных
Планировщик:
Анализ позиционных связей различных запросов
Перестройка очереди таким образом, чтобы реализация запросов минимизировала перемещение магнитных головок.