While(some condition)
{ entry section
Critical section
Exit section
Remainder section}
Критические ресурсы.
Под критическим разумеется некоторый программный либо аппаратный ресурс, который в каждый момент времени может использоваться одним и только одним процессом, потоком или прерыванием. Правильное обращение с критическими ресурсами является основой грамотного, добротного и надежного программного обеспечения. Поэтому все программные компоненты, вызываемые несколькими различными потоками, должны рассматриваться с точки зрения отнесения к критическим ресурсам. Для этого будем использовать характеристику, обратную критичности, которая называется безопасностью по отношению к тем или иным событиям в программной системе. Для управляющих программ обычно требуется максимальный уровень безопасности компонент – по отношению к сигналам, то есть любым асинхронно возникающим в системе событиям: аппаратным прерываниям, переключениям контекста выполнения (потока) и другим.
Определим два уровня собственной сигналобезопасности программ.
1. Безусловная сигналобезопасность. Обеспечивается повторно-входимыми программными компонентами, обращение к которым может происходить в любой момент времени без каких-либо конфликтов. Такие программы должны выполняться независимо от любой другой программы, включая самою себя. Это достигается несколькими способами:
- Программа оперирует исключительно локальными данными, которые размещаются в стеке. Такой метод используется при реализации функций, допускающих рекурсивный вызов. Следует отметить, что стандарт языка программирования С поддерживает рекурсивное обращение к любым функциям.
- Программа блокирует все события (прерывания) в системе на время своего выполнения. Этот метод делает сигналобезопасной любую программу, однако должен использоваться лишь для минимальных сегментов кода. Блокировка всех событий может оказаться полезной для гарантированного обеспечения атомарности семафорных операций.
- Программа в состоянии восстановить в начальное состояние свои разделяемые ресурсы по завершении повторного вызова. Технология восстановления – на любителя, но весьма удобна для практического использования в частности, в управляющих программах, выполняемых без поддержки операционной системы и диспетчера потоков.
2. Транзакционная сигналобезопасность. Программные компоненты с транзакционной сигналобезопасностью могут вызываться в любой момент времени, но без повторной входимости. То есть выполнение программы должно полностью завершаться до ее очередного вызова. Транзакционно безопасная программа зависит только от самой себя, но независима от любой другой программы. Например, операции чтения и записи кольцевого буфера являются безусловно сигналобезопасными друг относительно друга, поскольку манипуляции головой и хвостом буфера независимы. Чтение буфера может быть прервано операцией записи и наоборот. Однако, ни чтение, ни запись сами по себе не являются повторно входимыми и должны рассматриваться как критические секции. Если программные компоненты зависят как от самих себя, так и от других программ, они не являются сигналобезопасными. Например, операции чтения и записи разделяемой памяти не являются сигналобезопасными: их наложение и на самих себя и друг на друга может привести к искажениям данных. Такие программы следует рассматривать как критические разделяемые ресурсы и применять внешние методы их защиты: семафоры или взаимные исключения (mutexes).
16. Понятие взаимного исключения. Критический участок.
В многопроцессной системе из-за взаимодействия процессов возможны 4 ситуации 1) взаимное исключение 2) синхронизация 3)взаимоблокировка 4)коммуникация. Критические области- ресурс, который допускает обслуживание пользователя за один раз наз. критическим. Если несколько процессов пользуются таким ресурсом, они должны синхронизировать свои действия. Место в программе, где процесс обращается к такому ресурсу наз. критическим участком. В каждый момент времени только один процесс может выполнять свой критический участок при работе с ресурсом. Для предотвращения этого используется взаимное исключение. Для реализации задач взаимного исключения необход. выполнение след. условий. 1) 2 процесса не должны одновременно находиться в критич. областях. 2)при запросе критич. ресурса несколькими процессами, только один получает разрешение. 3) процесс вне крит. Области не может блокир. Другие процессы. 4) процесс использует Крит область конечное время 5)любой процесс переходит в неактивное состояние только за пределами критич. области. 6) невозможна ситуация, когда процесс вечно ждет попадания в крит. область.
17. Способы реализации взаимного исключения: запрещение прерываний, блокировка памяти, строгое чередование.
1. Запрет прерываний
Выход процесса из состояния исполнения может быть по 2-ум причинам:
- блокировка из-за нехватки ресурсов
- конец кванта времени
Квант времени заканчивается по прерыванию таймера, поэтому, если запретить системе получать и обрабатывать прерывания, то процесс из состояний выполнения не выйдет, пока сам не разрешит прерывания.
Недостаток:
В случае зацикливания программы в КС или невыполнения эпилога, систему приходится перезагружать.
Этот алгоритм используется внутри ядра системы.
2. Блокировка памяти (переменная «Замок»)
shared int lock = 0;
while (1){
while (lock)
lock = 1;
КС
lock = 0;
}
Пролог не является атомарным, поэтому до того, как замок будет закрыт (lock = 1), управление может быть передано другому процессу, который тоже сможет войти в КС. Нарушается условие взаимоисключения.
3. Строгое чередование
Вводится переменная, которая идентифицирует номер процесса, который должен войти в КС.
shared int turn = 0;
while (1){
wile (turn != pid);
КС
turn=1-turn;
}
Взаимоисключение гарантируется, но алгоритм не удовлетворяет условию прогресса, потому что, если процессу, идентификатор которого равен turn не нужно в КС, то он и не выйдет из КС и не изменит значение turn, при этом другой процесс может бесконечно долго ожидать входа в КС.
18. Способы реализации взаимоисключения: алгоритм Деккера, операция «Проверка и установка» (команда TSL)
1. Алгоритм Деккера
Используется массив флагов и переменная кода.
shared int turn = 0;
while (1){
ready[pid] = 1;
turn = 1-pid;
while (ready[1-pid] && turn == 1-pid);
КС
ready[pid] = 0;
}
Процесс может войти в КС только, если флаг готовности другого процесса равен 0 и значение переменной turn = идентификатору текущего процесса.
Доказательство:
Представим, что 2 процесса одновременно находятся в КС. Значит, флаги готовности у них обоих равны 1, значит, условие цикла while у обоих процессов не выполнялось из-за второй части этого условия, т.е. для каждого процесса переменная turn равна идентификатору этого процесса, чего быть не может, что и требовалось доказать.
2. операция «Проверка и установка» (команда TSL).
Алгоритм Деккера, расширенный на n процессов.
int Test and Set (int *target)
{int tmp = *target; *target = 1;
Return temp;}
shared int lock = 0;
while (1){
while (Test and Set(&lock));
КС
Lock = 0;}.
19. Примитивы межпроцессного взаимодействия. Решение проблемы производителя и потребителя с использованием примитивов межпроцессорного взаимодействия
Простейшими примитивами являются sleep и wakeup. Sleep - системный запрос, в результате которого процесс блокируется пока его не запустит другой процесс. Wakeup – в качестве параметра содержит процесс, который следует запустить. Проблема состоит в следующем 2 процесса используют буфер ограниченного размера. Один -производитель помещает данные в этот буфер. Трудность возникает когда производитель хочет поместить в буфер очередную информацию и обнаружив, что он полон и будет ожидать. Другой потребитель будет ожидать пока буфер не будет заполнен в случае если захочет забрать из буфера данные, а буфер пуст.
Для решения этой проблемы вводим переменную (count) для отслеживания колич-ва элементов в буфере (N). Если соunt = N, то производитель уходит в состояние ожидания, в противном случае данные помещаются в буфер и count увеличивается. При соunt =0, потребитель уходит в состояние ожидания. В противном случае оттуда извлекается информация и значение count уменьшается. Производитель может активизировать потребителя с помощью вызова Wakeup в тот момент, когда потребитель не находится в состоянии ожидания.
Алгоритм Петерсона дает нам решение задачи корректной организации взаимодействия двух процессов. Давайте рассмотрим теперь соответствующий алгоритм для n взаимодействующих процессов, который получил название алгоритм булочной, Основная его идея выглядит так. Каждый вновь прибывающий клиент (он же процесс) получает талончик на обслуживание с номером. Клиент с наименьшим номером на талончике обслуживается следующим. К сожалению, из-за неатомарности операции вычисления следующего номера алгоритм булочной не гарантирует, что у всех процессов будут талончики с разными номерами. В случае равенства номеров на талончиках у двух или более клиентов первым обслуживается клиент с меньшим значением имени (имена можно сравнивать в лексикографическом порядке). Разделяемые структуры данных для алгоритма — это два массива
shared enum {false, true} choosing[n];
shared int number[n];
Изначально элементы этих массивов инициируются значениями false и 0 соответственно. Введем следующие обозначения
(a,b) < (c,d), если a < c или если a == c и b < d
max(a0, a1, ...., an) — это число k такое, что k >= ai для всех i = 0, ...,n