Поддержка взаимоисключения на уровне ОС. Мьютексы и семафоры (Дейкстры). Команда ассемблера TSL.

Мьютексы и семафоры В этих алгоритмах поддерживаются взаимоисключения на уровне ОС. Процесс, ожидающий вход в критическую секцию не расходует процессорное время, нужно заблокировать его до тех пор пока нужные разделы ресурсов не станут свободными. В момент освобождения ресурсов процесс надо “разбудить” и желательно ресурс пометить как занятый. Блокировать процесс может только ОС. Под мьютексом в общем случае понимается объект с 2мя состояниями (открыт-закрыт). Программируют 2 операции Lock(), Unlock(). Unlock проходит успешно в любом случае, переводит объект в состояние открыт. А lock имеет 2 варианта:

-1й случай как ф-я Boolean при применении к открытому мьютексу она закрывает его и возвращает истину. При применении к закрытому мьютексу –ложь. Такое программирование неблокирующее.

-2й случай. Операция как процедура не возвращает значения. При применении к открытому мьютексу она закрывает его и возвращает управление. При применении к закрытому блокирует вызвавший процесс. Пока мьютекс не окажется открытым.

Важнейшее свойство операций это их атомарность. Обе операции должны выполняться как одно целое.

В алгоритме используем переменную S она будет обозначать мьютекс. А вместо присваиваний операций lock и unlock.

Неблокирующая реализация Lock

While (!lock(s)){} //ждем пока не удастся закрыть мьютекс

Section() // работает с разделенными данными

Unlock(s) //разрешить доступ другим процессам

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

Блокирующая реализация Lock

Lock (s) ;//ожидание пока не закроется мьютекс

Section();// работа с данными

Unlock(S);//разрешение доступа

Блокирующий вариант не имеет активного ожидания, необходимо содействие ядра ОС.

Семафоры Дейкстры

В данном алгоритме понятие семафор это обобщенное понятие Мьютекса. В обобщенном варианте это целочисленная переменная которая принимает только неотрицательные значения. Определено 2 операции up() down().

Up проходит успешно, увеличивает значение переменной на 1 , немедленно возвращает управление. Down уменьшает значение на 1, если текущее >0. Если значение 0, то она блокирует процесс пока значение не станет положительным, после чего уменьшает его на 1 и возвращает управление. Операции над семафором дБ атомарными либо целиком как объект ядра либо как набор операций ядра над переменной из памяти пользовательского процесса. С помощью семафора можно имитировать функционирование Мьютекса. Если 0-закрыт, 1-открыт, lock и unlock заменить на down и up. Надо чтобы up не применялось к положительному семафору (применяется в начале программы 1 раз или сразу после down). Семафорный алгоритм ОС используется для организации счетчика употребл. ресурсов. Некоторые версии ОС обобщ операции над семафорами, введя специальные целочисленные параметры. Up(sem,n) фиксирует величину изменения, down неблокир вариант этой операции. В сравнении с классическим вариантом вместо ожидания сразу возвращает управление (операция прошла успешно)

Известная реализация семафоров в system IPC представляет собой массивы семафоров с которыми можно производить сложные атомарные операции.

Существуют для них доп. операции: блокировка пока семафор не станет равным 0.

TSL Мьютекс можно реализовать без обращения к ядру, необходима команда TSL проверить и закрыть. Имеем 2 операнда регистр и адрес в памяти. Суть в том, чтобы за 1 неделимое действие поместить в регистр содержимое ячейки памяти, а в саму ячейку памяти поместить фиксированное значение 1. В одно действие можно установить переменной мьютекса значение соответствующее состоянию заперт, сохранить для проверки то значение которое было для мьютекса раньше. Если мьютекс до этого был открыт, то операция прошла успешно. Если закрыт, то надо ждать.

Mutex: DB, 0

Lock: TSL RX, Mutex

CMP RX, 0

JE ok

JMP lock

Ok: RET

Unlock: mov mutex, 0

RET

Есть возвращение к использованию активного ожидания.

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

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

Примеры взаимоисключений. Задача производителя и потребителя. Есть несколько процессов производящих данные и есть процессы обрабатывающие-потребители. Задача иллюстрирует применение семафоров, определяем вариант передачи информации. Работа с таким буфером мтребует взаимоисключений. Буфер-единое целое. На время выполнения любого процесса исключается возможность обращения к буферу другого процесса.Возможны 2 ситуации, требующие блокировки:

- потребитель готов получить порцию данных, но в буфере их нет.

-производитель подает порцию, но записать не может, тк все слоты заняты.

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

-считать свободные слоты, блокировать производителей, если их нет.

-считать слоты, запоминая данные

Идентификаторные empty & full этим величинам в начале создания буфера присвоили значения. Mutex блокирует операции с буфером над empty производится несколько раз up(empty) сколько есть свободжных слов. Mutex=m, помещение данных в буфер и извлечение из них put_data(), get_data()

Void procedur() {/*подготовка данных*/

Down (empty); lock(m);

Put_data();unlock(m);

Up(full);}

Void consumer() {down(full); lock(m); get_data(); unlock(m); up(empty);} /*обработка данных*/