Реализация операций семафора
При разработке семафора должна быть учтена возможность параллельного вызова процессами. Планирование очереди процессов, ожидающих у данного семафора, существуют разные подходы. Важным архитектурным вопросом, который следует решить при проектировании системы, является местоположение класса семафоров и его связь с подсистемой управления процессами.
1) Параллельная реализация семафоров – в любой, многопроцессорной или однопроцессорной, системе, реализованной без специальных ограничений, может одновременной поступать любое количество методов SimWait() и SimSignal() одного семафора. Реализация операций SimWait() и SimSignal() может потребовать изменения целочисленного значения семафора, его очереди и составляющего процесса. Все изменения должны осуществляться в составе одной атомарной операции, во избежание перевода системы в неопределенное состояние, т.е. либо должны быть выполнены все 3три действия, либо ни одного. Организация семафора должна отвечать требованиям монопольного доступа к его внутренним данным. Методы SimWait() и SimSignal() содержат критические секции, связанные с внутренней структурой данных семафора и не могут одновременно выполняться несколькими процессами. Однако семафор предназначен для решения проблемы взаимных исключений и синхронизации, поэтому необходимо обеспечить возможность одновременного обращения к ним.
2) Планирование очередей SImWait(). Простейший вариант планирования процессов, ожидающих у семафора может осуществляться с использованием стратегии FIFO. Но тут существует две проблемы:
а) низкоприоритетный процесс, завладевший семафором, может удерживать остальные процессы в состоянии ожидания в независимости от их приоритета до тех пор, пока сам не закончит работу с ресурсом и не вызовет метод SimSignal(); в случае приоритетного планирования с абсолютными динамическими приоритетами он может быть вытеснен с процессора до того, как будет освободит семафор и таким образом задержит выполнение ожидающих процессов; эта ситуация называется инверсией приоритетов;
б) низкоприоритетный процесс может стоять в очереди семафора перед процессом с более высоким приоритетом.
В однопроцессорных системах проблема (б) может быть решена следующим образом: метод SimSignal() освобождает все ожидающие процессы, после чего каждый из них снова осуществляет вызов SimWait(). После освобождения первым на выполнение будет процесс с наивысшим приоритетом, он и получит семафор. Недостатком такой схемы являются системные затраты на многократное блокирование и разблокирование процессов.
Планирование FIFO подходит для систем определенных типов. К ним относятся системы, не требующие ответов в реальном времени или в которых процессы, ожидающие у данного семафора, обычно выполняются с одинаковым приоритетом, а также системы, в которых очередь семафора очень короткая.
Если система должна отвечать в реальном времени, очереди семафоров в ней можно упорядочить с помощью приоритетов. В этом случае семафор должен иметь возможность узнать приоритет вызванного процесса. Для решения проблемы инверсии приоритетов можно добавить временное повышение приоритета процесса, который удерживает семафор до уровня самого высокоприоритетного в очереди. Эта операция называется наследование приоритета. Процесс, удерживающий семафор выполняется с действующим приоритетом равным большему из двух значений: исходный приоритет процесса и его унаследованный приоритет. Система реального времени должна реагировать на события с определенной скоростью. Если процесс блокируется в ожидании ресурса, важно, чтобы он не вышел за отведенные ему временные рамки.
Некоторые системы реального времени дополняют статистический анализ на этапе проектирования. Для таких систем заранее определен перечень процессов и ресурсов, используемых каждым из них, поэтому для любого семафора известны процессы, которым он может потребоваться и в частности процессы с наивысшим приоритетом, называемый потолком приоритетов семафора. В подобном случае для ограничения времени задержки процесса может использоваться протокол с потолком приоритетов.
Этот протокол ограничивает время ожидания для низкоприоритетных процессов максимальным временем выполнения критической секции одного низкоприоритетного процесса. Основная идея заключается в том, что даже если семафор свободен, процесс может получить его лишь в случае, когда все остальные семафоры, удерживаемые в этот момент процессами, имеют более низкий потолок приоритетов, чем приоритет данного процесса.
В общем случае, семафор инициализируется количеством доступных ресурсов. Процесс запрашивает экземпляр ресурса и, если уже все экземпляры выданы, то процесс блокируется. Один из ожидающих процессов может приступить к работе, когда очередной процесс завершит работу с ресурсом. Такая схема подходит для динамического выделения процессам устройств, элементов общей структуры данных и т.д.
3) Реализация семафоров на пользовательском уровне. Пользовательский поток, которому требуется доступ к общему ресурсу или синхронизация с другим пользовательским потоком, может вызвать методы SimWait() и SimSignal() класса семафора, реализованного в исполнительной системе.
Если в значении семафора указано, что общий ресурс свободен, пользовательский поток, который вызвал метод SimWait() может продолжить работу. В данном случае блокировка его вызова не выполняется. Если же ресурс занят, необходимо уведомить механизм обработки прерываний о том, что поток ждет освобождения этого ресурса, заблокировать данный поток и направить другой поток на выполнение. Блокирование и планирование производится исполнительной системой на пользовательском уровне и ОС в этом не участвует.
Единственный видимый ОС прикладной процесс остается в состоянии выполнения все время, пока происходит переключение от пользовательского потока к обработчику прерываний, затем к модулю управления процессами, и снова пользовательскому потоку.
Возможен другой вариант. Чтобы блокировать пользовательский поток, должен быть заблокирован соответствующий поток ядра, для чего вызывается ОС. Когда пользовательский поток выполняет вызов SimSignal() при отсутствии ожидающих потоков, значение семафора увеличивается на 1 и обращение к модулю управления процессами не происходит.Если же несколько процессов уже ждут у семафора, один из них удаляется из очереди и выполняется вызов для разблокирования семафора. Этот вызов может направляться модулю управления процессами пользовательского уровня или ОС. В обоих случаях сигнализирующий поток переводится из состояния блокирования в состояние готовности.
