Переменная turn, изначально равная 0, отслеживает, чья очередь входить в критическую область. Постоянная проверка значения переменной, в ожидании некоторого значения, называется активным ожиданием и является бесцельной тратой процессорного времени. Используется только в случае небольшого времени ожидания. Блокировка, использующая активное ожидание, называется спин-блокировкой. Недостаток: допустим, процесс 1 вышел из критической области и выполняет работу вне ее. Процесс 0 попадает в критическую область, быстро выполняет ее, передает очередь процессу 1, быстро выполняет свою некритическую секцию и возвращается к активному ожиданию. В этот момент оба процесса находятся в некритической области и процесс 1 блокирует процесс 0, что нарушает условие №3.
13. Решение проблемы взаимного исключения. Алгоритм Петерсона.
int turn;
int interested[2];
void enter_region(int process)
{
int other;
other = 1 - process;
interested[process] = TRUE;
turn = process;
while (turn == process && interested[other] == TRUE); // активное ожидание
}
void leave_region(process)
{
interested[process] = FALSE;
}
Прежде чем войти в критическую область, процесс вызывает процедуру enter_region со своим номером в качестве параметра. После выхода из критической области процесс вызывает процедуру leave_region и разрешает другому процессу войти в критическую область. Этот алгоритм является достаточно надежным, но использует активное ожидание.
14. Решение проблемы взаимного исключения. Команда TSL.
Команда TSL (Test and Set lock) - это решение требуют части аппаратного обеспечения. Некоторые компьютеры могут иметь команду tsl rg, lock. Команда считывает в регистр содержимое переменной lock, а в переменную lock сохраняет некоторое ненулевое значение. При этом гарантируется, что операция считывания и сохранения слова неделима (атомарная операция). Это означает, что во время выполнения команды не может произойти переключение контекста и другой процесс не сможет обратиться к слову lock, пока команда не выполнена до конца.
enter_ko:
tsl rg, lock
cmp rg, 0
jne enter_region
ret
leave_ko:
mov lock, 0
ret
Прежде чем попасть в критическую область, процесс вызывает процедуру enter_region, которая выполняет активное ожидание до снятия блокировки, устанавливает новую блокировку и возвращает управление. Алгоритм надежен, однако использует активное ожидание.
15. Проблема инверсии приоритетов (производителя и потребителя).
Проблема инверсии приоритета. Оба последних решения имеют один недостаток - активное ожидание, которое, кроме бесцельной траты процессорного времени, могут иметь другие неожиданные последствия. Допустим, есть 2 процесса: процесс H с высокий приоритетом и процесс L - с низким. Допустим, процесс H переходит в состояние выполнения Run как только переходит в состояние готовности Ready. Допустим, процесс L находится в критической области. В это время процесс H переходит в состояние готовности и немедленно запускается. Он пробует войти в критическую область, но, поскольку там находится процесс L, он попадает в состояние вечного активного ожидания. Поскольку процесс L не может получить процессорное время, пока активен процесс H, оба процесса взаимозаблокируются. Такое состояние называется проблемой инверсии приоритета.
Проблема производителя-потребителя. Два процесса совместно используют буфер ограниченного размера. Производитель помещает данные в буфер. Потребитель считывает их оттуда. Допустим, буфер полон и производитель пытается поместить туда порцию данных, либо буфер пуст и потребитель пытается считать данные оттуда.
16. Проблема производителя – потребителя. Решение с помощью примитивов sleep и wake.
Наиболее удачным решением проблемы становится уход проблемного процесса в состояние блокировки, пока второй процесс не активизирует его. Для решения данной проблемы используются примитивы межпроцессного взаимодействия sleep, wake.
Примитивы sleep, wake
Sleep - системный запрос, в результате которого вызывающий процесс блокируется, пока его не разбудит другой процесс. Wake будит процесс, который указывается в качестве параметра.
#define N 100 // объем буфера
int count = 0;
void producer(void)
{
int item;
while(TRUE)
{
item = produce_item();
if (count == N)
sleep();
insert_item(item);
count++;
if (count == 1)
wake(consumer);
}
}
void consumer(void)
{
int item;
while(TRUE)
{
if(count == 0)
sleep();
item = remove_item();
count--;
if (count == N - 1)
wake(producer);
consume_item(item);
}
}
При таком решении возможно возникновение состояние состязания, поскольку не ограничен доступ к переменной count. Допустим, буфер пуст. Потребитель считал значение переменной count, сверил его с нулем. В этот момент произошла передача управления производителю. Производитель заполнил буфер одной порцией данных и послал сигнал wake. Поскольку потребитель не был в состоянии блокировки, сигнал wake пропал. После передачи управления потребитель уйдет в состояние блокировки. Через какое-то время производитель заполнит буфер и так же уйдет в состояние блокировки. Решением этой проблемы может стать использование переменной ожидания активации. Если сигнал wake послан процессу, не находящемуся в режиме блокировки, значение переменной увеличивается. При попытке блокировки данного процесса проверяется состояние переменной активации. Если она не равна нулю, блокировка не происходит, а значение переменной уменьшается.
17. Проблема производителя – потребителя. Мьютексы.
Мьютекс - переменная, которая может находится либо в блокированном, либо в неблокированном состоянии. Похож на семафор, но не умеет считать. Перед входом в критическую область выполняется функция lock. Если мьютекс не заблокирован, то происходит вход в приоритетную область и блокировка мьютекса, иначе происходит блокирование потока (процесса).
mutex_lock:
tsl rg, mutex
cmp rg, 0
jz ok
call thread_yield
jmp mutex_lock
ok:
ret
mutex_unlock:
mov mutex, 0
ret
Процедура обработки мьютекса использует команду tsl и, при невозможности входа в критическую область, вместо активного ожидания передает управление другому потоку либо уходит в состояние блокировки. При повторной передаче управления заново проверяет возможность входа в критическую область.
18. Проблема производителя – потребителя. Семафоры.
Семафоры - тип переменных, используемых для подсчета сигналов запуска, сохраненных на будущее. Может принимать значение 0 либо целое положительное число. Для работы с семафорами предусмотрены 2 функции: down, up.
Функция down сравнивает значение семафора с нулем. Если значение больше 0, то оно уменьшается на единицу и управление возвращается вызывающему процессу. Если значение равно 0, то процесс блокируется по этому семафору.
Операция up увеличивает значение семафора. Если предыдущее значение семафора было равно 0, то посылается сигнал активации по этому семафору и его значение не изменяется. Все операции с семафорами (сравнение, умеличение, уменьшение, блокировка, активация) выполняются атомарно.
#define N 100
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void producer(void)
{
int item;
while(TRUE)
{
item = pruduce_item();
down(&empty);
down(&mutex);
insert_item(item)
up(&full);
up(&mutex);
}
}
void consumer(void)
{
int item;
while(TRUE)
{
down(&full);
down(&mutex);
item = remove_item();
up(&empty);
up(&mutex);
counsume_item(item);
} }
19. Проблема производителя – потребителя. Мониторы.
Монитор - набор процедур, переменных и других структур данных, объединенных в особый модуль. Процессы могут вызывать процедуры монитора, но при этом доступ к внутренним данным монитора имеют только процедуры, объявленные внутри него.
monitor mon1
{
int i;
int mas[10];
char condition;
void producer(void)
{
...
}
void consumer(void)
{
...
}
}
Доступ к переменным i, mas, condition имеют только функции producer, consumer. Эти функции могут вызываться из внешней программы. Реализации взаимных исключений способствует важное свойство монитора: при обращении к монитору в любой момент времени активным может быть только один процесс. Мониторы являются структурным компонентом языка программирования. Поэтому компилятор обрабатывает вызовы процедур монитора иначе, чем вызовы остальных процедур: первые несколько команд проверяют наличие в мониторе другого процесса. Кроме реализации взаимного исключения необходим способ блокировки тех процессов, которые не могут продолжать свою деятельность. Решение заключается во введении переменных состояния и двух функций: wait, signal. Когда процедура обнаруживает, что не может далее продолжать работу, она выполняет функцию wait на одной из переменных состояний. Это приводит к блокировке процесса, что позволяет другому процессу войти в монитор. С помощью функции signal процесс может активизировать другой процесс, заблокированный на одной из переменных состояния. Процесс, выполняющий функцию signal, должен немедленно покинуть монитор. Переменные состояния, в отличие от семафоров, не являются счетчиками, поэтому операция wait должна выполнятся раньше, чем операция signal, что можно оценить по значению переменных состояния.
В отличие от функций sleep и wake с функциями wait и signal не может произойти ситуация, когда другой один процесс пытается активизировать другой до того как он заблокируется. Даже в случае переключения контекста между проверкой и выполнением функции wait, первый процесс не сможет попасть в монитор, пока из него не выйдет второй.
20. Планирование и диспетчеризация. Общие положения.
Со времен систем пакетной обработки данных планировщик играет важную роль в функционировании ОС. При правильном выборе алгоритма планирования можно значительно повысить эффективность системы. С появлением многозадачных интерактивных ОС роль планировщика возросла. Теперь, кроме повышения эффективности, нужно обращать внимание на время отклика отдельных задач. Тем не менее планировщик должен эффективно использовать процессор, поскольку переключение между процессами требует значительных затрат:
- переключение в режим ядра;
- сохранение контекста;
- сохранение карты памяти;
- запуск блока управления памятью с картой памяти нового процесса;
- восстановление контекста нового процесса из таблицы процессов;
- запуск нового процесса и переключение в режим пользователя.
В связи с этим, количество переключений между процессами следует минимизировать. С точки зрения планирования процессы бывают двух типов:
- процессы, ограниченные возможностями процессора. Характеризуются длинными периодами использования процессора и редким ожиданием ввода/вывода;
Ключевым вопросом планирования является выбор момента для принятия решений. Самые распространенные ситуации:
- создание нового процесса - планировщику необходимо выбрать: запустить дочерний процесс либо продолжить выполнять родительский;
- когда процесс завершает работу, планировщик должен выбрать один процесс из списка готовых;
- процесс блокируется на операции ввода/вывода либо семафоре;
- при возникновении прерывания от устройства ввода/вывода планировщик может восстановить прерванный процесс либо запустить процесс, ожидаюий это прерывание, либо какой-то другой процесс;
- при каждом k-ом прерывании по таймеру алгоритмы планирования можно разделить на 2 больших типа:
‡ без переключений - выбранный процесс может работать до завершения блокировки либо пока сам не отдаст процессор;
‡ с переключениями (приоритетное плаинрование) - выбранному процессу позволяют работать некоторое максимально возможное фиксированное время. Если к концу этого времени процесс не заблокируется или не завершится, управление передается другому процессу. Такие алгоритмы требуют прерывание по таймеру.
21. Планирование и диспетчеризация. Алгоритмы планирования.
Задачи алгоритмов планирования:
- справедливость - каждому процессу предоставляется справедливая доля процессорного времени. Сопоставимые процессы получают сопоставимое обслуживание;
- принудительное применение политики планирования;
- контроль занятости всех частей системы - при постоянной работе всех компонентов эффективность системы будет выше, чем, если отдельные компоненты будут работать попеременно.
Для систем пакетной обработки данных:
- пропускная способность - количество задач, выполененных в единицу времени;
- оборотное время - статистически усредненное время от момента получения задачи до ее выполнения.
Стоит заметить, что алгоритм, увеличивающий пропускную способность, необязательно минимизирует оборотное время.
Для интерактивных систем:
- задача минимизации времени отклика - время между получением команды и получением результата;
- достижение соразмерности - задачи должны исполняться такое время, какое от них ожидает пользователь.
Для систем реального времени (мультимедийные системы):
- жесткие сроки выполнения некоторых операций с целью предотвращения потери данных;
- предсказуемость - предотвращение деградации качества в мультимедийных процессах. Планировщик должен делать их выполнение предсказуемым и регулярным.
Алгоритмы планирования.
Для систем пакетной обработки данных:
- FIFO (First In First Out) - задачи поступают на выполнение по мере поступления в систему. Алгоритм легок для понимания и программирования. Не выполняется задача баланса использования системы;
- «кратчайшая задача – первая» - если в очереди одновременно есть несколько задач, на исполнение выбирается самая короткая. Такой алгоритм минимизирует оборотное время. Версией этого алгоритма с переключением является алгоритм "наименьшее оставшееся время выполнения".
Для интерактивных систем:
- циклическое планирование - каждому процессу предоставляется квант процессорного времени. Если по его истечении процесс продолжает работать, то управление передается другому процессу, а сам процесс помещается в конец очереди. Интересным моментом данного алгоритма является выбор кванта времени, поскольку переключение между процессами так же занимает определенное время. Значение кванта времени нужно устанавливать чуть выше, чем средний интервал работы процессора без переключения. В этом случае переключение процессов будет происходить редко. Большинство процессов будет выполнять блокировку до истечения кванта времени, что улучшит производительность системы за счет устранения принудительных переключений.
Приоритетное планирование
В циклическом алгоритме планирования есть важное допущение о том, что все процессы равнозначны. Принимая во внимание все факторы, появляется необходимость приоритетного планирования. Каждому процессу присваивается определенный приоритет, и к выполнению принимается процесс с наивысшим приоритетом. Чтобы предотвратить бесконечную работу высокоприоритетных процессов, блокировщик может, например, с каждым тактом часов уменьшать приоритет текущего процесса, пока не произойдет переключение. Приоритеты могут присваиваться статически и динамически. Аналогом статического выделения приоритета могут служить воинские звания. В некоторых ОС существует специальная команда nice, которая позволяет программисту добровольно понизит приоритет процесса. ОС может динамически назначать приоритеты для достижения своих целей. Например, разумно давать высокий приоритет процессам, ограниченным возможностями устройств ввода/вывода. Поскольку большинство времени такие процессы ожидают прерывания, логично предоставить им процессор как только он потребуется, чтобы инициировать новую операцию ввода/вывода и заблокировать данный процесс. Простейшие алгоритмы обслуживания таких процессов состоит в установке приоритета = 1/f, где f - часть использованного в последний раз кванта времени.
Часто бывает удобно сгруппировать процессы в классы по приоритетам и использовать приоритетное планирование среди классов и циклическое планирование внутри класса. Процесс из нижнего класса получит управление только тогда, когда очередь верхнего класса пуста. Поскольку каждое переключение между процессами занимает значительную часть времени, логично выделять процессам, ограниченным возможностями процессора, больший квант времени, что может привести к ухудшению времени отклика. Чтобы исправить этот недостаток, процессам из разных классов выдавались разные кванты времени. Например, процессам первого класса выдвался 1 квант, второго - 2 и т.д. Если процесс использовал все отведенное ему время, на следующий раз ему уменьшали приоритет и увеличивали время работы. Если процесс одно время работает как вычислительный, то есть использует все отведенное ему время, а в другие моменты становится интерактивным, то, для увеличения его приоритета, отслеживается приход специального сигнала.
Лотерейное планирование
В основе алгоритма лежит раздача процессам так называемых лотерейных билетов для доступа к разным ресурсам. Когда планировщику необходимо принять решение, он вытягивает один билет, и его обладатель получает доступ к ресурсу. Более приоритетным процессам можно раздать несколько билетов, чтобы увеличить вероятность выигрыша. Кроме этого, взаимодействующие процессы могут обмениваться билетами между собой.
22. Управление памятью. Однозадачные системы. Многозадачность с фиксированными разделами.
Часть ОС, которая занимается управлением, распределением, очисткой памяти называется менеджером памяти. Менеджеры памяти делятся на 2 типа:
- не перемещают процессы между оперативной памятью и диском;
- перемещают процессы между оперативной памятью и диском:
‡ перемещают процессы целиком (swapping);
‡ перемещают процессы постранично (paging).
Однозадачные системы без подкачки на диск
Самая простейшая из сехм управления памятью заключается в том, что в каждый момент времени работает только одна программа. Существует 3 варианта таких систем:
- первая схема использовалась в ранний компьютерах фоннеймоновской архитектуры;
- вторая схема используется до сих пор в простейших контроллерах;
- треться схема использовалась в ранних компьютерах на основе ОС DOS. Используется до сих пор в сложных контроллерах.
Многозадачность с фиксированными разделами
Большинство современныз систем поддерживают псевдопараллельную работу нескольких процессов. Самый легкий способ достижения многозадачности - это разделение памяти на N возможно неравных частей. Когда задание поступает в память, его располагают во входной очереди к наименьшему разделу, способному вместить его. Поскольку размер разделов фиксирован, все пространство раздела, не используемое процессом, пропадает.
Недостаток такой схемы проявляется, когда к большому разделу нет очереди, в то время как к маленькому разделу выстроилась большая очередь задач. Небольшие задания (чаще всего интерактивные и высокоприоритетные) вынуждены ждать в то время как основная часть памяти пустует.
23. Управление памятью. Настройка адресов и защита.
Настройка адресов и защита
Допустим, первая команда программы представляет собой вызов процедуры по абсолютному адресу 100 внутри двоичного файла. Если программа загрузится в раздел 1, то команда обратится к абсолютному адресу 100, находящемуся внутри ОС, а правильная процедура находится по адресу 100к + 100. Эта проблема известна как проблема перемещения программ в памяти или настройка адресов.
Одним из возможных решений является модификация команд при загрузке программ в памяти. К каждому адресу будет добавляться абсолютный адрес раздела. Для выполнения такой настройки компоновщик должен присоеденить к программе список слов, которые являются адресами и подлежат модификации. Настройка адресов во время загрузки не решает проблему защиты. Вредоносная программа может создать новую команду с абсолютным адресом и перейти в другой раздел. Не существует стандартных средств, способных запретить программе обращения к любому слову в памяти. В качестве решения IBM разделила память на блоки по 2кб и назначила каждому блоку 4-битовый защитный код. Регистр PSW (Programm Status/Security Word) содержит 4-битовый ключ. Аппаратура перехватывает все попытки обратиться к любой части памяти, чей защитный код отличался от значения регистра PSW работающего процесса.
Другим аппаратным решением обоих проблем является оснащение машины двумя аппаратными регистрами: базовым и предельным. При загрузке процесса, в базовый регистр загружается адрес начала раздела, а в предельный - длина раздела. К каждому адресу автоматически добавлялось содержимое базового регистра без изменения самой команды. Сами адреса проверяются по отношению к предельному регистру, чтобы гарантировать их нахождение внутри раздела. Базовый и предельный регистры защищаются аппаратно. Недостатком является выполнение операций сложения и сравнения при каждом обращении к памяти.
24. Управление памятью. Многозадачность с динамическими разделами. Основная подкачка.
Фиксированные разделы эффективны для пакетных систем. Однако, для систем реального времени или интерактивных, ОЗУ бывает недостаточно для размещения всех активных процессов. В этом случае избыток процессов хранится на диске и динамически переносится в основную память для последующей обработки. Простейшая стратегия называется swapping или простая подкачка. Она заключается в том, что каждый процесс полностью переносится в память, некоторое время работает и затем целиком возвращается на диск.
В отличие от фиксированных разделов, количество, размер и размещение разделов изменяются по мере поступления и завершения задачи. Такая гибкость позволяет эффективнее использовать память, усложняя при этом операции размещения, освобождения и отслеживания изменения в памяти. Когда в результате подкачки в памяти появится множество неиспользованных маленьких фрагментов, возможно провести уплотнение памяти, передвинув все процессы в сторону младших адресов. Если процесс имеет фиксированный размер, то ему предоставляется точно необходимое количество памяти. Однако, в случае динамических структур данных, проблема предоставления памяти будет возникать каждый раз при попытке процесса увеличиться. Если рядом с выделенным участком находится свободный участок, то он может быть предоставлен в пользу процесса. В противном случае данный процесс необходимо целиком перенести на другой достаточно большой свободный участок либо перекачать на диск соседний раздел. Если процесс имеет два изменяющихся участка, то может быть предложена альернативная схема.
25. Управление памятью с помощью битовых массивов
При таком методе управления, ОС разбивает память на единичные блоки, и каждому блоку соответствует один бит в так называемом битовом массиве либо битовой карте. Занятому под процесс блоку соответствует единица, свободному - нуль. Битовая карта является достаточно простым способом отслеживания распределения памяти. Однако, поиск серии заданной длины является достаточно медленной операцией, посколькю искомая последовательность может пересекать границы слов. При выборе маленького размера единичного блока, битовая карта может занимать значительный объем памяти. При выборе большого блока могут возникнуть значительные потери из-за частичного использования последнего блока серии.
26. Управление памятью с помощью связанных списков. Алгоритмы предоставления памяти.
правление памятью с помощью связных списков
Другой способ отслеживания состояния памяти заключается в поддержке связных списков занятых или свободных фрагментов памяти, где фрагментом является либо процесс, либо участок между двумя процессами. Запись состоит из:
- атрибута занятости - P - занят (process), H - свободен, дыра (hole);
- адреса начала фрагмента;
- длины фрагмента;
- указателя на следующую запись.
Так же для модификации удобнее иметь список с двумя связями, одна из которых указывает на предыдущую запись. В случае сортировки списка по адресам имеется несколько алгоритмов предоставления памяти процессу:
- первый подходящий участок - просматривается список областей, пока не находится достаточно большой свободный участок. Он делится на две части, в список добавляется одна запись, модифицируются указатели соседних списков. Алгоритм является самым быстрым;
- следующий подходящий участок - работает как первый алгоритм, но поиск начинается с адреса, записанного при предыдущем поиске. Позволяет равномерно использовать память, но является немного медленнее первого алгоритма;
- самый подходящий участок - выполняет поиск по всему списку, выбирает наименьший по размеру подходящий участок. Является медленнее предыдущих алгоритмов, поскольку должен просматривать весь список. Приводит к очень сильной фрагментации памяти;
- самый неподходящий участок - выбирает наибольший свободный участок, чтобы после разделения оставалась достаточно большая область для размещения других процессов. Меньше фрагментирует память, чем предыдущий алгоритм, однако появляются проблемы с размещением больших процессов.
Все алгоритмы можно ускорить, если поддерживать отдельные списки для свободных и занятых областей. В таком случае увеличится скорость поиска свободного участка, однако увеличится время модификации списков при освобождении памяти. Если, в случае двух списков, список свободных участков отсортировать по размеру, то быстрее всего будет работать алгоритм "самый подходящий участок", а алгоритм "следующий подходящий участок" не имеет смысла.
В менеджере памяти можно реализовать алгоритм "быстрый подходящий участок", если поддерживать отдельные списки для областей с наиболее часто запрашиваемыми размерами. Алгоритм позволяет быстро выделять память, однако приводит к сильной фрагментации и является проблемным при освобождении памяти.
27. 28. Виртуальная память. Страничная организация памяти. Основные проблемы.
Виртуальная память
Основная идея виртуальной памяти заключается в том, что в случае, когда объединенный размер кода, данных, стека и других частой программы превышает объем основной памяти, то в каждый момент в памяти присутствуют только используемые части программы, а остальные части хранятся на диске. Такие части называются оверлеями (overlay). Способ разделения программы на части выбирает программист, а работу по загрузке и сохранению оверлеев выполняет ОС.
Страничная организация памяти
Большинство систем виртуальная памяти используют страничную организацию памяти (paging). Все программно формируемые адреса называются виртуальными адресами и формируют виртуальное адресное пространство. Если ОС не использует виртуальное адресное пространство, то виртуальный адрес подается непосредственно на адресную шину. В противном случае виртуальный адрес передается диспетчеру памяти, который преобразует виртуальный адрес в физический и уже его подает на шину. Допустим, рассматриваемая система может формировать 16-разрядные адреса от 0 до 64к - это виртуальное адресное пространство. Так же система имеет основную память объемом 32к. Виртуальное адресное пространство разделено на блоки памяти, называемые страницами (page). Физическая память разделена на блоки точно такого же размера и эти блоки называются страничными кадрами (page frame).
В фактическом аппаратном обеспечении страницы, присутствующие в оперативной памяти, отслеживаются с помощью бита присутствия/отсутствия. В случае инструкции mov ax, 16k произойдет обращение к неотображаемой странице. В этом случае диспетчер памяти инициирует прерывание ЦП, передающее управление ОС. Такое прерывание называется страничным прерыванием (page fault). ОС блокирует вызвавший прерывание процесс, выбирает малоиспользуемый страничный блок и записывает его на диск. Далее соответствующая страница записывается в освободившийся страничный кадр, и устанавливается бит присутствия, после чего управление передается либо прерванному процессу либо планировщику. 16-разрядный адрес состоит из 4-битного номера страницы и 12-битного смещения (4к). Номер страницы используется в качестве индекса в таблице страниц, которая выдает номер страничного кадра, соответствующего виртуальной странице.
Номер страницы используется в качестве индекса в таблице страниц, выдающей номер страничного блока. Если бит присутствия равен нулю, происходит страничная ошибка и управление передается ОС. Если бит равен единице, то номер страничного блока, найденный в таблице страниц, записывается в 3 старших бита выходного регистра, а 12 битов смещения копируются без изменений. В сумме они составляют 15-разрядный физический адрес, который подается на адресную шину.
В нашей системе 32к виртуального адресного пространства и 16к основной памяти.
При использовании таблиц страниц могут возникнуть две проблемы:
- таблица может быть слишком большой. При размере страницы 4к, для 32-разрядного адресного пространства, каждая таблица страниц будет содержать 2^20 записей, при том, что каждый процесс нуждается в своей собственной таблице страниц;
- отображение должно быть быстрым, поскольку преобразование виртуального адреса в физический будет происходить при каждом обращении к памяти. В среднем время преобразования должно быть в 4 раза короче, чем время выполнения команды.
Потребность в большом, но быстром страничном преобразовании накладывает существенные ограничения на способы построения компьютеров. Простейшим конструкторским решением является поддержка таблицы страниц, состоящей из массива быстрых аппаратных регистров. Когда процесс запускается, ОС загружает регистры из оперативной памяти и больше не нуждается в обращении к ней. Преимуществом является простота реализации и скорость преобразования. Недостатками являются дороговизна и необходимость загрузки всей таблицы при каждом переключении контекста.
Другой вариант решения заключается в том, что таблица целиком располагается в основной памяти и существует один единственный аппаратный регистр, который указывает на начало таблицы. При переключении контекста потребуется перезагрузка только одного регистра, однако, при выполнении каждой команды, потребуется несколько обращений к памяти для чтения/записи таблицы страниц.
Многоуровневые таблицы страниц
Чтобы не хранить в памяти огромные таблицы страниц, многие системы используют многоуровневые таблицы. Виртуальный адрес разделяется на несколько полей, необязательно одинакового размера.
Когда виртуальный адрес поступает в диспетчер памяти, из него выделяется поле PT1. Которое используется в качестве индекса в каталоге таблиц. Соответствующая запись выдает адрес таблицы страниц второго уровня. В качестве индекса для этой таблицы используется поле PT2. По этому индексу находится номер страничного кадра, соответствующего виртуальной таблице. Этот номер складывается со смещением, в результате чего получается физический адрес. Преимуществом использования многоуровневых таблиц страниц является тот факт, что в каждый момент времени в памяти могут находится не все таблицы второго уровня, а только необходимые в данный момент времени.
30. Структура элемента таблицы страниц.
Наиболее распространенный размер - 32 бита. В зависимости от системы, точная структура может изменяться, но основная информация в основном совпадает.
Бит присутствия: 1 - страницы присутствует в памяти. 0 - страница отсутсвует в памяти, при обращении возникает страничная ошибка.
Биты защиты: в простейшей схеме 1 бит. 0 - только чтение. 1 - чтение/запись. В сложных схемах используются 3 бита, по одному для каждой операции (чтение, запись, выполнение).
Бит изменения: устанавливается в 1 при изменении страницы. Учитывается при решении ОС освободить страничный кадр. Если бит установлен в 1 - страница должна быть перезаписана на диск.
Бит обращения - устанавливается при каждом обращении к данной странице. Сбрасывается через определенные промежутки времени. Используется при выборе страниц на удаление из памяти.
Бит запрета кэширования - важен для страниц, отображенных не на память, а на регистры устройств. Бит устанавливается для того, чтобы программа получала новые данные из устройства, а не старую информацию из кэша.
В записи не содержится адреса места на диске для страницы, выгруженной из памяти. Эта информация хранится в служебных таблицах ОС.
31. Буфер быстрого преобразования адреса.
Буферы быстрого преобразования адреса. Ассоциативная память
Из-за значительного размера таблиц страниц они хранятся в оперативной памяти. Таким образом, при выполнении простейших команд, требуются дополниетльные обращения к памяти, что приводит к потере производительности. Решение по минимизации обращений к памяти основано на наблюдении, что большинство программ делают множество обращений к небольшому количеству страниц. Исходя из этого наблюдения, компьютер снабжается небольшим аппаратным устройством, служащим для преобразования виртуальных адресов в физические без перехода по таблице страниц.
Это устройство называется ассоциативной памятью, TLB - Translation Lookaside Buffer. Оно находится внутри диспетчера памяти и содержит несколько табличных записей (порядка 512 записей). Каждая запись содержит информацию об одной странице и однозначно соответствует записи в таблице страниц. Когда на вход менеджера памяти поступает виртуальный адрес, аппаратура одновременно сравнивает этот адрес со всеми записями внутри буфера. Если найдено совпадение и не нарушены биты защиты, номер страничного кадра берется прямо из буфера, без переход по таблице страниц. Если биты защиты нарушены, формируется стандартная ошибка защиты. Если соответствующая запись не найдена, то происходит стандартный поиск по многоуровневой таблице и найденная запись заносится в TLB.
32. Инвертированные таблицы страниц.
Традиционные таблицы страниц требуют по одной записи для каждой виртуальной страницы. Для 32-разрядного виртуального адресного пространства и страницы размером в 4к таблицы страниц займет 4Мб. Для 64-разрядного адресного пространства таблица займет порядка 15Тб. Чтобы решить эту проблему используются инвертированные таблицы страниц. В такой модели таблица содержит по одной записи на каждый страничный блок. Тогда для 64-разрядного виртуального адресного пространства при 256Мб оперативной памяти с размером страничного блока 4к, таблица страниц займет 4б*64к (менее 1Мб). Хотя инвертированные таблицы экономят много места, усложняется процесс перевода виртуального адреса в физический. Когда процесс N обращается к виртуальной странице P, аппаратное обеспечение не сможет найти физическую страницу используя только номер P в качестве индекса. Вместо этого поиск должен производиться по паре (N,P) во всей инвертированной таблице. Кроме того поиск должен выполняться при каждом обращении к памяти. Ускорить процесс можно с помощью ассоциативной памяти. Буфер TLB может содержать все часто используемые страницы. В этом случае поиск будет проходить так же быстро, как и с обычными таблицами. Однако, при неудачном поиске придется программно искать пару во всей инвертированной таблице. Усовершенствовать такой поиск можно с помощью хэш-таблицы виртуальных страниц. Все виртуальные страницы, которые находятся в данный момент в памяти и имеют одинаковое значение хэш-функции, сцепляются друг с другом.
Хотя при каждом прерывании можно выбирать случайную страницу, производительность системы увеличится, если удалить саму редко используемую страницу.
Оптимальный алгоритм
В момент страничного прерывания в памяти находится определенный набор страниц. Каждая страница может быть помечена числом команд, которые будут выполнены до первого обращения к ней. Оптимальный алгоритм удаляет страницу с наибольшей меткой. На практике такой алгоритм невыполним, так как ОС не может знать, когда произойдет обращение к той или иной странице. Осуществить оптимальный алгоритм можно в рамках эксперимента при повторном прогоне. Результаты оптимального алгоритма можно сравнивать с результатами других алгоритмов для определения их эффективности.
NRU (Not Recently Used) алгоритм (не использовавшаяся в последнее время страница)
В табличной записи для каждой страницы присутствуют 2 бита:
- бит R (бит обращения) устанавливается в единицу при каждом обращении к странице. Возможен сброс этого бита, например каждые n тиков таймера, чтобы отличить страницы, к которым давно не было обращения;
- бит M (бит модификации) устанавливается в единицу при изменении страницы. Сигнализирует о том, что при удалении надо страницу записать на диск.
При страничном прерывании, на основании значений битов R и M, ОС делит все страницы на 4 класса. Для удаления случайным образом выбирается страница из низшего класса. Алгоритм легок в реализации и может дать вполне достаточный результат.
34. Алгоритмы замещения страниц. FIFO. Вторая попытка. Алгоритм LRU.
FIFO алгоритм
ОС поддерживает список всех страниц, находящихся в памяти. Список отсортирован в порядке появления страниц. При страничном прерывании выгружается страница из начала списка. Алгоритм редко используется в чистом виде.
Алгоритм "вторая попытка"
Является модификацией алгоритма FIFO. При страничном прерывании, у первой страницы в списке изучается бит R. Если он равен единице, страница помещается в конец списка, а бит R сбрасывается, и проверяется следующая страница. Данный алгоритм ищет в списке страницу, к которой не было обращений за последние n тиков таймера. Если происходили ссылки на все страницы, алгоритм превращается в обычный FIFO.
Предыдущий алгоритм является корректным, однако неэффективным, потому что постоянно передвигает все страницы по списку. Поэтому лучше хранить записи страниц в кольцевом списке и использовать указатель на одну из ячеек. Когда происходит страничное прерывание, проверяется бит R у страницы, на которую указывает указатель. В зависимости от бита R содержимое записи может измениться, и изменяется значение указателя, что значительно быстрее модификации всего списка. Алгоритм полностью идентичен алгоритму "вторая попытка", кроме непосредственной реализации.
Алгоритм LRU (Last Recently Used), страница, не использовавшаяся больше всего
В основе этого алгоритма лежит наблюдение, что страницы, к которым происходило многократное обращение в нескольких последних командах, вероятно, так же будут использоваться в последующих командах и наоборот. Алгоритм состоит в том, что при страничном прерывании из памяти выгружается страница, к которой дольше всего не было обращений. Реализация данного алгоритма является недешевой. Для полного осуществления необходимо поддерживать связанный список всех содержащихся в памяти страниц, где последняя используемая страница находится в начале списка. Сложность заключается в том, что список должен обновляться при каждом обращении к памяти. При таком подходе поиск страницы, ее удаление и вставка в начало списка занимают очень много времени. Существуют аппаратные методы реализации данного алгоритма.
Для первого метода требуется оснащение компьютера специальным N-разрядным счетчиком, который автоматически возрастает после каждой команды. Кроме этого, каждая запись в таблице страниц должна иметь поле для хранения значения этого счетчика. После каждого обращения к памяти, значение счетчика запоминается в записи в таблице в соответствующей странице, к которой произошло обращение. Если возникает страничное прерывание, менеджер памяти проверяет значение счетчиков во всей таблице и ищет наименьшее. Эта страница и является неиспользуемой дольше всего.
Второй вариант аппаратной реализации заключается в том, что на системе с N-страничными блоками поддерживается аппаратная матрица размером NxM, изначально равных нулю. При обращении к странице k аппаратура присваивает всем битам k-ой строки единицу, затем всем битам k-ого столбца - нуль. В любой момент времени строка с наименьшим двоичным значением является неиспользуемой дольше всего.
36. 37. Сегментация памяти. Сегментация в ядрах Intel Pentium.
Сегментация
Описанная выше виртуальная память представляет собой одномерное пространство, то есть виртуальные адреса идут по порядку от 0 до некоторого максимума. В этом адресном пространстве могут одновременно располагаться различные наборы данных, например CODE, DATA, STACK. В случае использования виртуальных адресов программа не видит разницы между разными наборами данных и может, например, попытаться поменять данные из набора CODE.
В таких обстоятельствах удобно было бы иметь несколько отдельных виртуальных адресных пространств. Самым простым решением является обеспечение компьютера так называемыми сегментами. Каждый сегмент может иметь разную длину, свои атрибуты защиты и начинаться с любого адреса. Для адресации внутри сегмента вместо 32-разрядного виртуального адреса используется пара значений: номер сегмента и смещение внутри сегмента (sg:offs). Поскольку сегменты независимы друг от друга, они самостоятельно могут изменять размер. Сегмент является логическим объектом, что должно учитываться программистом при написании программы (например, сегмент не должен одновременно содержать данные и код). При наличии различных атрибутов защиты и отсутствии криворукости у разработчика можно избежать попыток несанкционированного доступа к разным типам данных.
Сегментация с использованием страниц в системах Intel Pentium
Виртуальная память компьютера Pentium поддерживает 16к независимых сегментов. Основой виртуальной памяти являются две таблицы: GDT, LDT (глобальная и локальная таблицы дескрипторов). У каждой программы есть своя собственная локальная таблица дескрипторов. Глобальная таблица одна для всех программ и несет информацию о системных сегментах, в том числе сегментах ОС. Чтобы получить доступ к сегменту, программа должна загрузить в один из сегментных регистров 16-разрядный селектор.
Третий бит указывает на принадлежность сегмента к локальному либо глобальному. Индекс указывает на номер дескриптора соответствующей таблицы. Каждая таблица содержит 8к дескрипторов. Дескриптор 0 является запрещенным. Во время загрузки селектора соответствующий дескриптор извлекается из таблицы и записывается в микропрограммные регистры для быстрого доступа к нему. Размер дескриптора - 8 байт.
При обращении к сегментному регистру (селектору), программа может найти в микропрограммных регистрах соответствующий дескриптор. Если сегментный регистр (селектор) равен нулю, то сегмент не существует и система вызывает прерывание. Далее проверяется бит присутствия. В случае нуля так же происходит прерывание. Далее проверяется, не выходит ли смещение за границы сегмента (смещение сравнивается со значением поля Lim). Если бит G равен нулю, то поле Lim указывает размер в сегментах с точностью до 1 байта. Если G равно единице, то размер указывается в страницах по 4к каждая. При выходе за пределы сегмента вызывается прерывание. Если все проверки пройдены, то значение Base (адрес начала сегмента) складывается со смещением Offset и получается 32-разрядный линейный адрес. Если бит G равен нулю, линейный адрес интерпретируется как физический. Если бит G равен единице, то доступна страничная подкачка и линейный адрес преобразуется в физический с помощью двухуровневой таблицы страниц.
Система Pentium поддерживает 4 уровня защиты (привилегии):
