Примитивы межпроцессного взаимодействия
Решение Петерсона и с помощью команды TSL корректны, но у них один и тот же недостаток – использование активного ожидания (процесс входит в цикл, ожидая возможности войти в критическую область). Существует еще так называемаяпроблема инверсии приоритета: процессу с низким приоритетом никогда не будет предоставлено процессорное время, если в это время выполняется процесс с высоким приоритетом. Если процесс с низким приоритетом находится в критической области, а процесс с высоким приоритетом, заканчивая операцию ввода-вывода, оказывается в режиме ожидания, процессорное время будет отдано процессу с высоким приоритетом. В результате процесс с низким приоритетом никогда не выйдет из критической области, а процесс с высоким приоритетом будет бесконечно выполнять цикл
Поэтому вместо циклов ожидания применяются примитивы межпроцессного взаимодействия, которые блокируют процессы в случае запрета на вход в критическую область
Простейший вариант – пара примитивов sleep и wakeup. sleep – системный запрос, в результате которого вызывающий процесс блокируется, пока его не запустит другой процесс. У запрос wakeup есть один параметр – процесс, который следует запустить. Также возможно наличие одного параметра у обоих запросов – адреса ячейки памяти для согласования запросов ожидания и запуска
Два процесса совместно используют буфер ограниченного размера. Один из них – производитель – помещает данные в буфер, а потребитель считывает их оттуда. Трудности начинаются в тот момент, когда производитель хочет поместить в буфер очередную порцию данных и обнаруживает, что буфер полон. Для производителя решением является ожидание, пока потребитель полностью или частично не очистит буфер. Если потребитель хочет забрать данные из буфера, а буфер пуст, потребитель уходит в состояние ожидания и выходит из него, как только производитель положит что-нибудь в буфер и разбудит его
Это решение достаточно простое, но приводит к состояниям состязания. Нужна переменная count для отслеживания количества элементов в буфере. Если максимальное число элементов, хранящихся в буфере, равно N, программа производителя должна проверить, не равно ли N значению count, прежде, чем поместить в буфер следующую порцию данных. Если count = N, производитель уходит в состояние ожидания; в противном случае производитель помещает данные в буфер и увеличивает значение count
Код программы потребителя прост: сначала проверить, не равно ли значение count нулю. Если равно, то уйти в состояние ожидания; иначе забрать порцию данных из буфера и уменьшить значение count. Каждый из процессов также должен проверять, не следует ли активизировать другой процесс, и в случае необходимости проделывать это
Возникновение состояния состязания возможно, поскольку доступ к переменной count не ограничен. Может возникнуть следующая ситуация: буфер пуст, и потребитель только что считал значение переменной count, чтобы проверить, не равно ли оно нулю. В этот момент планировщик передал управление производителю, производитель поместил элемент в буфер и увеличил значение count, проверив, что теперь оно стало равно 1. Зная, что перед этим оно было равно 0 и потребитель находился в состоянии ожидания, производитель активизирует его с помощью вызова wakeup. Но потребитель не был в состоянии ожидания, так что сигнал активизации пропал впустую. Когда управление перейдет к потребителю, он вернется к считанному когда-то значению count, обнаружит, что оно равно 0, и уйдет в состояние ожидания. Рано или поздно производитель наполнит буфер и также уйдет в состояние ожидания. Оба процесса так и останутся в этом состоянии
Суть проблемы в данном случае состоит в том, что сигнал активизации, пришедший к процессу, не находящемуся в состоянии ожидания, пропадает. Если бы не это, проблемы бы не было. Быстрым решением может быть добавление бита ожидания активизации. Если сигнал активизации послан процессу, не находящемуся в состоянии ожидания, этот бит устанавливается. Позже, когда процесс пытается уйти в состояние ожидания, бит ожидания активизации сбрасывается, но процесс остается активным. Этот бит исполняет роль копилки сигналов активизации. Несмотря на то, что введение бита ожидания запуска спасло положение в этом примере, легко сконструировать ситуацию с несколькими процессами, в которой одного бита будет недостаточно. Можно добавить еще один бит, или 8, или 32, но это не решит проблему
Дейкстра предложил использовать семафор – переменную для подсчета сигналов запуска. Семафор – объект синхронизации, который может регулировать доступ к некоторому ресурсу. Было предложено использовать вместо sleep иwakeup операции down и up. Их отличие в следующем: если значение семафора больше нуля, down просто уменьшает его на 1 и возвращает управление процессу, в противном случае процесс переводится в режим ожидания. Все операции проверки значения семафора, его изменения и перевода процесса в состояние ожидания выполняются как единое и неделимое элементарное действие, то есть это время ни один процесс не может получить доступ к этому семафору. Операция up увеличивает значение семафора. Если с этим семафором связаны один или несколько ожидающих процессов, которые не могут завершить более раннюю операцию down, один из них выбирается системой и разблокируется. Проблема производителя и потребителя легко решается с помощью семафоров
Иногда используется упрощенная версия семафора – мьютекс – переменная, которая может находиться в одном из двух состояний: блокированном или неблокированном. Для описания мьютекса требуется один бит. Мьютекс может охранять неразделенный ресурс, к которому в каждый момент времени допускается только один поток, а семафор может охранять ресурс, с которым может одновременно работать не более N потоков
Недостаток: одна ошибка при их реализации программистом приводит к остановке всей ОС. Чтобы упростить написание программ, было предложено использовать примитив синхронизации более высокого уровня – монитор – набор процедур, переменных и других структур данных, объединенных в модуль или пакет. Процессы могут вызывать процедуры монитора, но у процедур, объявленных вне монитора, нет прямого доступа к внутренним структурам данных монитора. При обращении к монитору в любой момент времени активным может быть только один процесс. Не все ЯП поддерживают мониторы и не во всех ОС есть их встроенная реализация (в Windows их нет)
Все описанные примитивы не подходят для реализации обмена информации между компьютерами в распределенной системе с несколькими процессорами. Для этого используется передача сообщений. Этот метод межпроцессного взаимодействия использует два примитива: send и receive, которые скорее являются системными вызовами, чем структурными компонентами языка. Первый запрос посылает сообщение заданному адресату, а второй получает сообщение от указанного источника. Передача сообщений часто используется в системах с параллельным программированием
Последний из рассмотренных механизмов синхронизации – барьер, предназначенный для синхронизации группы процессов: несколько процессов выполняют вычисления с разной скоростью, а затем посредством применения барьера ожидают, пока самый медленный не закончит работу, и только потом все вместе продолжают выполнение команд
4. Основы управления памятью в ОС: функции управления, идентификация переменных и команд, виртуальное пространство, преобразование адресов. Основные методы распределения памяти: с фиксированными разделами, с динамическими разделами, с перемещаемыми разделами. Основы виртуализации и свопинга. Реализации виртуальной памяти
Менеджер памяти – часть ОС, управляющая памятью
Функции ОС по управлению памятью в мультипрограммной системе: отслеживание свободной и занятой памяти, выделение и освобождение памяти для процессов, управление подкачкой, настройка адресов программы на конкретную область физической памяти
Типы адресов для идентификации переменных и команд на разных этапах ЖЦ программы:
- символьные имена, или метки – идентификаторы переменных в программе на ЯП
- виртуальные, или математические, или логические, адреса вырабатывает транслятор, переводящий программу на машинный язык. Во время трансляции неизвестно, в какое место ОП будет загружена программа, поэтому транслятор присваивает переменным и командам виртуальные (условные) адреса, обычно считая по умолчанию, что начальным адресом программы будет нулевой адрес
- физические адреса соответствуют номерам ячеек ОП, где в действительности расположены переменные и команды
Виртуальное адресное пространство процесса – совокупность его виртуальных адресов. Диапазон возможных адресов виртуального пространства одинаков для всех процессов. Совпадение виртуальных адресов переменных и команд у различных процессов не приводит к конфликтам – когда эти переменные одновременно присутствуют в памяти, ОС отображает их на разные физические адреса
Подходы к преобразованию виртуальных адресов в физические:
- замена виртуальных адресов на физические выполняется один раз для каждого процесса во время начальной загрузки программы в память
- динамическое преобразование адресов: программа загружается в память в неизмененном виде и работает с виртуальными адресами, которые выработал транслятор. В самом простом случае, когда виртуальная и физическая память процесса представляют собой единые непрерывные области адресов, ОС преобразует виртуальные адреса в физические по следующей схеме: при загрузке фиксируется смещение действительного расположения программного кода относительно виртуального адресного пространства; во время выполнения программы при каждом обращении к ОП выполняется преобразование виртуального адреса в физический:
Методы распределения памяти:
- с использованием внешней памяти: страничное, сегментное, сегментно-страничное распределение
- без использования внешней памяти: фиксированными, динамическими, перемещаемыми разделами
Методы распределения памяти с фиксированными разделами
Однозадачная система без подкачки на диск – система, в которой в каждый момент времени работает только одна программа
Простейшие модели организации памяти при наличии ОС и одного пользовательского процесса:
Устаревшая модель; модель, используемая на некоторых встроенных системах; модель, использовавшаяся на ранних ПК под управлением MS-DOS (в роли ПЗУ выступает BIOS)
При использовании многозадачности повышается эффективность загрузки ЦП. К примеру, если средний процесс выполняет вычисления только 20% от того времени, которое он находится в памяти, то при присутствии в памяти одновременно пяти процессов ЦП должен быть занят все время
Многозадачная система с фиксированными разделами
Память разбивается на разделы – области фиксированной величины – вручную оператором во время старта системы или во время установки. После этого границы разделов не изменяются
Новый процесс помещается в общую очередь или в очередь к некоторому разделу:
Подсистема управления памятью сравнивает объем памяти, требуемый для вновь поступившего процесса, с размерами свободных разделов и выбирает подходящий раздел, а затем загружает программу в один из разделов и настраивает адреса. Уже на этапе трансляции разработчик программы может задать раздел, в котором ее следует выполнять. Это позволяет сразу, без использования перемещающего загрузчика, получить машинный код, настроенный на конкретную область памяти. «+»: простота реализации. «–»: жесткость заданных размеров памяти для каждого процесса. Схема применялась в OS/360; сейчас не используется
Методы распределения памяти с динамическими разделами
Память машины не делится заранее на разделы. Сначала вся память, отводимая для приложений, свободна. Каждому поступающему приложению на этапе создания процесса выделяется вся необходимая ему память (если память недостаточно, приложение не принимается на выполнение и процесс для него не создается). После завершения процесса память освобождается, и на это место может быть загружен другой процесс
Функции ОС:
- ведение таблиц свободных и занятых областей, в которых указываются начальные адреса и размеры участков памяти
- при создании процесса – анализ требований к памяти, просмотр таблицы свободных областей и выбор подходящего по размеру раздела по разным правилам (первый попавшийся раздел достаточного размера, раздел, имеющий наименьший достаточный размер, раздел, имеющий наибольший достаточный размер)
- загрузка программы в выделенный ей раздел и корректировка таблиц свободных и занятых областей. Программный код не перемещается во время выполнения, а значит, настройка адресов может быть проведена единовременно во время загрузки
- после завершения процесса – корректировка таблиц свободных и занятых областей
«+»: больше гибкости
«–»: фрагментация памяти – наличие несмежных участков свободной памяти
Методы распределения с перемещаемыми разделами
Один из методов борьбы с фрагментацией – перемещение занятых участков памяти в сторону старших или младших адресов. К функциям ОС при распределении памяти динамическими разделами добавляется необходимость сжатия – время от времени нужно копировать содержимое разделов из одного места памяти в другое, корректируя таблицы свободных и занятых областей
«+»: более эффективное использование памяти, «–»: большие временные затраты
Использовался в ранних версиях OS/2