Алгоритмы, основанные на квантовании

Каждому потоку в порядке очереди предоставляются ограниченные непрерывные периоды процессорного времени – кванты

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

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

Синхронизация процессов и потоков

Важным понятием синхронизации потоков является понятие «критической сек­ции» программы. Критическая секция — это часть программы, результат выполнения которой может непредсказуемо меняться, если переменные, относящиеся к этой части программы, изменяются другими потоками в то время, когда выполнение этой части еще не завершено.

Критическая секция всегда определяется по отношению к определенным критическим данным

Механизм синхронизации:

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

 

Семафоры

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

Для работы с семафорами вводятся два примитива, традиционно обозначаемых Р и V. Пусть переменная S представляет собой семафор. Тогда действия V(S) и P(S) определяются следующим образом.

• V(S): переменная S увеличивается на 1 единым действием.

• P(S): уменьшение S на 1, если это возможно. Если S=0, то в этом случае поток, вызывающий операцию Р, ждет, пока это уменьшение станет возможным.

Использование внешней памяти: оверлеи, свопинг, виртуальная память. Статичное распределение памяти. Сегментное распределение памяти.

Необходимо больше памяти, чем есть реально в системе à Неиспользуемые в данный момент участки памяти могут быть временно перемещены на жесткий диск

Оверлеи

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

Свопинг

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

+ Относительно простой способ управления памятью

- Процесс, требующий памяти больше, чем реально есть в системе загрузить нельзя

- Полная загрузка/выгрузка процессов требует много времени

Виртуальная память

+ Позволяет полностью или почти полностью скрыть от прикладной программы реальную организацию памяти – каждый процесс имеет «личное» адресное пространство, которое практически не ограничено в размерах.

+ Позволяет защитить процессы друг от друга

- Большие накладные расходы на преобразование виртуального адреса в физический. (Проблема решается аппаратной поддержкой виртуальной памяти)

- Непредсказуемо время доступа к памяти (Частично решается применением алгоритмов, предсказывающих обращения к памяти)

Виртуальная память

• Страничное распределение памяти

• Сегментное распределение памяти

• Сегментно-страничное распределение

 

Страничное распределение

Физическая память делится на части фиксированного размера – страницы

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

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

Для каждого процесса хранится таблица страниц

Запись таблицы страниц включает следующую информацию:

• номер физической страницы;

• признак присутствия;

• признак модификации страницы;

• признак обращения к странице.

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