Блокировка памяти

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

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

Пусть имеются два (или более) циклических процесса Р1 и Р2, в которых есть абстрактные критические секции, то есть каждый из процессов состоит из двух частей: некоторого критического интервала и оставшейся части кода, в которой нет работы с общими (критическими) переменными. Пусть эти два процесса асинхронно разделяют во времени единственный процессор либо выполняются на отдельных процессорах, каждый из которых имеет доступ к некоторой общей области памяти, с которой работают критические секции. Проиллюстрируем эту ситуацию с помощью рис. 4.6.

Р1 Р2

 

 

Рис. 4.6. Модель взаимодействующих процессов

 

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

Р1 Р2

перекл:= 1;

 

Рис. 4.7. Модель реализации блокировки памяти

 

Решение, представленное на рисунке 4.7, обеспечивает взаимное исключение в работе критических интервалов. Однако, если бы часть программы P1 была намного длиннее, чем программа R2, или если бы процесс Р1 был заблокирован в секции PR1, или если бы процессор для Р2 был с большим быстродействием, то процесс Р2 вскоре вынужден был бы ждать (и, может быть, чрезвычайно долго) входа в свою критическую секцию CS2, хотя процесс Р1 и был бы вне CS1.

Объяснение: проблемы начинаются со второго цикла, когда после CS2 в Р2 перекл становится равным 1, а в Р1 еще выполняется PR1. В результате Р1 в критическую секцию не входит, но и Р2 войти не может.

То есть при таком решении один процесс вне своей критической секции может помешать вхождению другого в свою критическую секцию.

 

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

Пусть с каждым из процессов Р1 и Р2 будет связана переменная, по смыслу являющаяся переключателем, которая принимает значение true, когда процесс находится в своем критическом интервале, и false — в противном случае. Прежде чем войти в свой критический интервал, процесс проверяет значение переключателя другого процесса. Если это значение равное true, процессу не разрешается входить в свой критический интервал. В противном случае процесс “включает” свой собственный переключатель и входит в критический интервал. Этот алгоритм взаимного исключения представлен на рис. 4.8.

 

Р1 Р2

перекл1:= false;

перекл2:= false;

 

Рис. 4.8. Модель второго варианта реализации блокировки памяти

Данный алгоритм не гарантирует выполнения условия нахождения только одного процесса внутри критического интервала. Отсутствие гарантий связано с различными, в общем случае, скоростями развития процессов. Поэтому, например, между проверкой значения переменной перекл2 процессом Р1 и последующей установкой им значения переменной перекл1 параллельно выполняющийся процесс Р2 может установить перекл2 в значение true. Отсюда следует, что оба процесса могут войти одновременно в свои критические интервалы.

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

 

Операция “Проверка и установка”

Операция “ПРОВЕРКА И УСТАНОВКА” является, как и блокировка памяти, одним из аппаратных средств решения задачи критического интервала. Данная операция реализована на многих компьютерах. Так, в знаменитой IBM 360 (370) эта команда называлась TS (test and set). Команда TS является двухадресной (двухоперандной). Ее действие заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение, равное единице. Команда TS является неделимой операцией, то есть между ее началом и концом не могут выполняться никакие другие команды.

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

Программа решения проблемы критического интервала на примере двух параллельных процессов приведена на рис. 4.9.

 

Р1 Р2

common:= 0;

Рис. 4.9. Модель использования команды TS

 

Предположим, что первым захочет войти в свой критический интервал процесс Р1. В этом случае значение local1 сначала установится в единицу, а после цикла проверки с помощью команды TS (local1, common) — в ноль. При этом значение common станет равным единице. Процесс Р1 войдет в свой критический интервал. После выполнения этого критического интервала common примет значение, равное нулю, что даст возможность второму процессу Р2 войти в свой критический интервал.

Безусловно, предполагается, что в компьютере предусмотрена блокировка памяти, т.е. операция common:=0 неделима. Команда “ПРОВЕРКА И УСТАНОВКА” значительно упрощает решение проблемы критических интервалов. Главное свойство этой команды — ее неделимость.

Основной недостаток использования операции “ПРОВЕРКА И УСТАНОВКА” состоит в следующем: находясь в цикле проверки переменно common, процессы впустую потребляют время центрального процессора и другие ресурсы. Действительно, если предположить, что произошло прерывание процесса Р1 во время выполнения своего критического интервала и, в свою очередь, начал выполняться процесс Р2, то он войдет в цикл проверки, впустую тратя процессорное время.

 

Таким образом, несмотря на то, что и алгоритм, основанный только на блокировке памяти, и операция «ПРОВЕРКА И УСТАНОВКА» пригодны для реализации взаимного исключения, оба эти приема очень неэффективны.

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

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

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

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

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

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

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

Реализовать предложенный алгоритм можно с помощью одного из самых главных механизмов решения проблемы взаимного исключения – семафорам Дейкстры.