Определение. Раздел 2. Основы разработки, реализации и организации функционирования ОС и СУБД

Раздел 2. Основы разработки, реализации и организации функционирования ОС и СУБД

Тема 1. Синхронизация процессов и доступа к ресурсам. Транзакции в ОС и СУБД

Лекция №1. Синхронизация процессов и доступа к ресурсам

В рамках данной лекции рассматриваются нижеследующие вопросы:

· Конкуренция процессов за ресурсы.

· Механизмы синхронизации. Семафоры. Мьютексы.

· Взаимное исключение. Критические секции. Блокировки. Взаимоблокировки. Запрет прерываний.

· Тупики

· Понятие транзакции

· Атомарность, согласованность, изолированность, долговечность транзакции.

· Последовательное и параллельное исполнение транзакций.

· Сериализуемость транзакций.

· Синхронизация доступа к разделяемым данным.

· Блокировки. Блокировки Exclusive (X), Shared (S);

· Изолирование транзакций. Проблемы «потери обновления», «грязного чтения», «неповторяемого чтение», «фантомы»;

· Журнализация.

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

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

Та часть процесса, т.е., программы, в которой используется доступ к общей памяти, называется критической секцией или критическим участком.

Пусть есть 2 процесса Р1, Р2, которые используют общий «ресурс» х. Пусть Р1 умножает содержимое х на 100, Р2 делит содержимое х на 2. Обобщенно каждый процесс должен выполнить считывание (R) значения х в свою локальную переменную (в своем адресном пространстве), произвести действие и записать (W) новое значение из локальной переменной в х. Как это может выполняться при параллельном исполнении процессов. Предположим, начальным содержимым х является 10.

Даже этот весьма упрощенный пример показывает, что процессы «мешают» друг другу, и чередование исполнения их атомарных операций влияет на конечный результат. В вариантах 1 и 2 к общему «ресурсу» процессы 1 и 2 осуществляют доступ одновременно, в варианте 3 общий «ресурс» используется процессом 2 после того, как процесс 1 завершил его использование. Другими словами в этом случае «ресурс» одновременно использовался только одним процессом.

Как известно, одним из требований к алгоритмам программ является детерминированность: программа должна обеспечивать одни и те же результаты при многократном исполнении. Если не предпринимать никаких мер, то для параллельно исполняемых программ это требование не будет выполняться.

Достаточные условия Бернстайна позволяют заранее определить, является ли набор процессов для программы детерминированным или нет. Их можно рассмотреть применительно к программам с разделяемыми переменными.

Пусть имеются наборы входных и выходных переменных программы. Для каждой атомарной операции наборы входных и выходных переменных - это наборы переменных, которые атомарная операция считывает и записывает. Пусть набор входных переменных программы R(P) представляет объединение наборов входных переменных для всех ее неделимых действий, а набор выходных переменных программы W(P) представляет объединение наборов выходных переменных.

Условия Бернстайна задаются следующим образом:

Если для двух активностей Z и Q:

· пересечение W(Z) и W(Q) пусто,

· пересечение W(Z) с R(Q) пусто,

· пересечение R(Z) и W(Q) пусто,

тогда выполнение Z и Q является детерминированным.

Если эти условия не соблюдены, возможно, что параллельное исполнение Z и Q детерминировано, но возможно, что и нет.

Условия Бернстайна являются жесткими: они требуют практически невзаимодействующих процессов.

Необходим способ и средство взаимного исключения (mutual exclusion), то есть, обеспечивающие правило, при котором если общие данные или файл используются одним процессом, возможность их использования всеми другими процессами исключается. В рамках ОС определен специальный синхронизирующий объект мьютекс (mutex) для организации межпроцессного взаимодействия.

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

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

Когда процесс находится в своем критическом участке, другие процессы не должны входить в свои критические участки.

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

Механизмом синхронизации более высокого уровня является семафор. Семафор представляет собой целую переменную, принимающую неотрицательные значения, доступ любого процесса к которой, за исключением момента ее инициализации, может осуществляться только через две атомарные операции: P (от датского слова proberen - проверять) и V (от verhogen - увеличивать). Классическое определение этих операций выглядит следующим образом:

Операционная система обеспечивает атомарность операций P и V, используя, например, метод запрета прерываний на время выполнения соответствующих системных вызовов. Если при выполнении операции P заблокированными оказались несколько процессов, то порядок их разблокирования может быть произвольным, например, FIFO.

Еще более высокий уровень представляют предложенные Хоаром (Hoare) в 1974 году мониторы. Монитор напоминает объект ООП: он обладает своими собственными переменными, определяющими его состояние. Значения этих переменных извне монитора могут быть изменены только с помощью вызова функций-методов, принадлежащих монитору. В свою очередь, эти функции-методы могут использовать в своей работе только данные, находящиеся внутри монитора и свои параметры. Особенностью мониторов является то, что в любой момент времени только один процесс может быть активен, т.е. находиться в состоянии готовность или исполнение, внутри данного монитора

В общем случае последовательностью действий для использования ресурса является:

· запросить (request) ресурс,

· использовать (use) ресурс,

· освободить (release) ресурс.

Если запросы и освобождения ресурса осуществляются некорректно, то возникают ситуации, называемые «тупиками». Эти ситуации означают «зависание программы».

Множество процессов находится в тупиковой ситуации, если каждый процесс из множества ожидает события, которое может вызвать только другой процесс данного множества. Поскольку все процессы ожидают, то ни один из них не сможет инициировать событие, которое разбудило (wake up) бы другой из множества и, следовательно, все процессы будут спать (sleep). Обычно событие, которого ждет процесс в тупиковой ситуации - освобождение ресурса

В 1971 г. Коффман, Элфик и Шошани сформулировали следующие четыре условия для возникновения тупиков.

1. Условие взаимоисключения (Mutual exclusion). Каждый ресурс выделен в точности одному процессу или доступен. Процессы требуют предоставления им монопольного управления ресурсами, которые им выделяются.

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (которые при этом обычно удерживаются другими процессами).

3. Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождаться он может только процессом, который его удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся другим процессам в цепи.