 |
Запрещения прерываний и переменные блокировки
|
|
|
|
Попытка аппаратного решения проблемы
Самое простое решение состоит в запрещении всех прерываний при входе процесса в критическую область и разрешение прерываний при выходе из критической области. Если прерывания запрещены, то запрещены и прерывания по таймеру. Поскольку процессор переключается с одного процесса на другой только по прерыванию, отключение прерываний исключает передачу процессора другому процессу. Т.О. запретив прерывания, процесс может сохранять совместно используемые данные, не опасаясь вмешательства другого процесса, но все же неправильно давать пользовательскому процессу возможность запрета прерываний. Если напр., процесс отключил все прерывания, и в результате какого-либо сбоя не включил их обратно, ОС прекратит свое существование. Для ядра характерно запрещение прерываний для нескольких команд при работе с переменными и списками. Возникновение прерывания в момент, когда список готовых процессов находится в неопределенном состоянии, могло бы привести к состоянию состязания. Вывод: инструмент запрещения прерывания необходим для ОС, но не для пользовательских процессов.
Рассмотрим программные решения
Пусть имеется одна совместно используемая переменная блокировки, изначально = 0. Если процесс хочет попасть в критическую область, он предварительно считывает значение переменной блокировки; если переменная = 0, то процесс изменяет ее на 1 и входит в критическую область; если переменная = 1, то процесс ждет, пока ее значение не изменится на 0. Т.о. 0 означает, что ни одного процесса в критической области нет, а 1 – наоборот, что есть процессы в критической области. У этого метода те же проблемы, что и в примере с каталогом спулера, а именно: 1 процесс считывает переменную блокировки, обнаруживает, что она = 0, но прежде, чем успевает изменить ее на 1, управление получает другой процесс, изменяющий ее на 1. Когда первый процесс снова получает управление, он тоже заменяет переменную блокировки на 1, и два процесса одновременно оказываются в критической области. Проблема не решается повторной проверкой значения переменной. Второй процесс может получить управление как раз после того, как первый процесс закончил вторую проверку, но еще не заменил значение переменной блокировки.
|
|
|
АЛГОРИТМ ПЕТЕРСОНА. КОМАНДА TSL
Датский математик Деккер был первым, кто разработал программное решение проблемы взаимного исключения. В 1981 г. Петерсон разработал алгоритм, состоящий из двух процедур, написанных на языке Си. Прежде, чем обратиться к совместно используемым переменным процесс вызывает процедуру enter region со своим номером 0 или 1 в качестве параметра, поэтому процессу при необходимости придется подождать, прежде чем войти в критическую область. После выхода из критической области процесс вызывает процедуру have region, чтобы обозначить свой выход и тем самым разрешить другому процессу вход в критическую область. Команда TSL используется в современных микропроцессорах
ПРИМИТИВЫ МЕЖПРОЦЕССОРНОГО ВЗАИМОДЕЙСТВИЯ
Оба решения корректны, но они обладают одним и тем же недостатком: использование активного ожидания. Они реализуют следующий алгоритм: перед входом в критическую область процесс проверяет, можно ли это сделать. Если нельзя, то процесс входит в цикл, ожидая возможности войти в критическую область. Этот алгоритм не только бесцельно тратит процессорное время, но, кроме того, может возникнуть ситуация, которую называют проблемой инверсий приоритета. Возможность вхождения в критическую область должен предвидеть пользователь. Примитивы блокируют процессы в случае запрета на вход в критическую область. Одной из простейших является пара примитивов sleep и wake up. Примитив sleep – это системный запрос, в результате которого вызывающий процесс блокируется, пока его не разбудит другой процесс. У системного запроса wake up один параметр – это процесс, который следует запустить. Также возможно наличие одного параметра у обоих запросов: адрес ячейки памяти, используемой для согласования запросов ожидания и запуска.
|
|
|
ПРОБЛЕМА ПРОИЗВОДИТЕЛЯ И ПОТРЕБИТЕЛЯ
Эта проблема называется проблемой ограниченного буфера. Если один процесс (производитель) помещает данные в буфер, а другой процесс (потребитель), забирает их оттуда – может возникнуть проблема. Трудности могут возникнуть в момент, когда производитель хочет поместить в буфер очередную порцию данных, но обнаруживает, что буфер полон. Для производителя решением является ожидание, пока потребитель полностью или частично не освободит буфер. Аналогично, если потребитель хочет забрать данные из буфера, а он пуст, потребитель уходит в состояние ожидания до тех пор, пока производитель что-нибудь не положит туда и не разбудит потребителя. Это решение является простым, однако оно приводит к состоянию состязания, когда оба процесса могут оказаться в состоянии ожидания. Решением может быть использование бита ожидания активации. Если сигнал активации послан процессу, не находящемуся в состоянии ожидания, этот бит устанавливается. Позднее, когда процесс пытается уйти в состояние ожидания – бит активации сбрасывается, но процесс остается активным. Этот бит играет роль «копилки» сигналов активации.
СЕМАФОРЫ
В 1965 г. Дейкстра предложил использовать целую переменную для подсчета сигналов запуска, сохраненных на будущее. Им был предложен новый тип переменных – семафоры, значение которых может быть нулем (в случае отсутствия сохраненных сигналов активации) или некоторым положительным числом, соответствующим количеству отложенных активирующих сигналов. Он предложил две операции: down и up. Операция down сравнивает значение семафора с нулем. Если значение семафора >0, то операция down уменьшает его, т.е. расходует один из отложенных сигналов активации, и возвращает управление. Если значение семафора равно нулю – то процедура не возвращает управление процессу, а он сам переводится в состояние ожидания. Все операции проверки значения семафора, его изменение или переводы процессов в состоянии ожидания, выполняется как единое, не делимое, элементарное действие. Тем самым гарантируется, что после начала операции ни один процесс не получит доступа к семафору до окончания, либо блокировки операции. Операция up – увеличивает значение семафора. Если с ним связаны один или несколько ожидающих процессов, которые не могут завершить более раннюю операцию down, один из них выбирается системой, напр., случайным образом, и ему разрешается завершить свою операцию down. Т.О. после операции up, примененной к семафору, связанному с несколькими ожидающими процессами, значение семафора так и остается равным нулю. Но за то число ожидающих процессов уменьшается на единицу. Операция увеличения значения семафора и активации процесса также неделимы, т.е. ни один процесс не может быть блокирован во время выполнения операции up, также, как ни один процесс не может быть блокирован во время выполнения операции.
|
|
|
|
|
|
