Операционные системы. Курс лекций

       

Аппаратная поддержка взаимоисключений


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

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

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

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

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

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

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

Операционная проверка и установка реализована на большинстве компьютеров. Команда TS (test and set) является двухадресной.
Ее действие заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение 1. Команда TS является неделимой операцией, так как между ее началом и концом не могут выполняться никакие другие операции. Чтобы использовать команду TS для решения проблемы критического интервала, с ней связывают переменную, которая является общей для всех процессов, использующих некий критический ресурс. Данная переменная будет принимать единичное значение, если какой-либо из взаимодействующих процессов находится в своем критическом интервале.

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

При помощи команды TS возможна синхронизация только двух процессов.

Современные ЦП поддерживают либо атомарную операцию CAS (compare and swap), либо атомарную операцию LL/SC (linked loading/save condition). Предназначены для операций взаимного исключения. Команда считывает значение флага и помещает его в регистр назначения, а затем очищает флаг. Если исходное значение флага было 0, это говорит о том, что структура данных используется другим процессом. Соответственно процесс не может обращаться к общим данным и может цикле проверять значение флага, пока не обнаружит, что структура данных свободна.

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

В микропроцессорах, начиная с i8086 также используются специальные команды BTC, BTS и BTR.

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

1) этот подход очень простой, поэтому легко проверяем;

2)    применим к любому количеству процессов;

3)    может использоваться для поддержки множества критических разделов, каждый из которых может быть определен при помощи своей собственной переменной.

Недостатки:

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

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

3)    возможна взаимоблокировка.


Содержание раздела