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

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

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

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

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

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

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

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

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

Кроме команды TAS, современные процессоры поддерживают атомарную операцию CAS («сравнить и поменять местами»). Простейшей командой, предназначенной для поддержки взаимного исключения, является операция – «прочитать и очистить». Команда считывает значение флага и помещает его в регистр назначения, а затем очищает флаг. Если исходным значением флага был 0, это говорит о том, что структура данных используется другим процессором и очистка флага ничего не меняет. Соответственно процесс не должен обращаться к общим данным и в цикле проверяет значение флага, пока не обнаружит, что структура данных свободна. Если же, исходное значение флага было отличным от 0, это означает, что структура данных свободна. Тогда процесс входит в критическую секцию, а очищенный им флаг показывает другим процессам.?????

При помощи команды 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) возможна взаимоблокировка.

17) Синхронизация процессов и потоков. Семафоры Дейкстры.

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

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

В любой многозадачной ОС процессы взаимодействуют друг с другом и система должна поддерживать эту возможность:

1/Процессы взаимодействуют для выполнения общей задачи. Процессу может потребоваться возможность запрашивать сервисы у другого процесса и ждать выполнения соответствующих операций. Процессы могут также синхронизироваться друг с другом. Это происходит, когда один из процессов достигает точки, в которой ему нужно убедиться в выполнении другим процессом какой-либо операции и лишь затем продолжить работу. Процессу требуется операции «Ждать» для синхронизации с другим процессом или аппаратным обеспечением. Кроме того, необходимы механизмы сигнализации о завершении операции, когда процесс ждет, что-то должно инициировать продолжение его работы. Причем взаимную синхронизацию необходимо осуществлять независимо от того, имеется ли у процессов общее адресное пространство или нет.

2/Процессы «соревнуются» за монопольное использование сервисов или ресурсов. Многие клиенты могут параллельно запрашивать некоторый сервис. Несколько процессов могут пытаться одновременно использовать некоторый ресурс. Система должна всем этим управлять, в частности она должна устанавливать порядок, согласно которому процессы, в случае необходимости, организуются в очередь в ожидании тех ресурсов, который можно использовать только последовательно, а также осуществлять выбор между процессами, запросы которых совпали по времени. «Соревнующимся» процессам нужно ждать получения общего ресурса и сигнализировать о завершении его использования.

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

Для сигнализации используются специальные переменные, называющиеся семафорами. Семафор – переменная специального типа, доступная параллельным процессам для проведения над ней только двух операций: «закрытия» и «открытия».

Для выполнения семафорных операций Дейкстра ввел два новых примитива. Для передачи сигнала через семафор s процесс выполняет примитив signal(s), а для получения сигнала – примитив wait(s). В последнем случае процесс приостанавливается до тех пор, пока не осуществится передача соответствующего сигнала. В статье Дейкстры и многих других источниках вместо wait используется Р (от голландского proberen – проверка), а вместо signal – V (от голландского verhogen – увеличение). Предполагается, что примитивы wait и signal атомарны, т. е. они не могут быть прерваны, и каждая из подпрограмм может рассматриваться как единый шаг.

Существует несколько типов семафоров: двоичные, считающие, счетные, множественные и др.

Двоичный семафор может принимать два значения: 0 и 1.

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

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

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

Пусть S – семафор, операции над которым определяются следующим образом:

Wait (S): уменьшение значения семафора S на единицу, если это возможно. Если это значение становится отрицательным, процесс, выполняющий операцию wait, блокируется. Если значение S больше нуля, процесс продолжает работу.

Signal (S): если ни один процесс не ждет у данного семафора, S увеличивается на единицу. В противном случае – освобождается один процесс и его работа продолжается с инструкции, следующей за инструкцией wait. Переменная S увеличивается на единицу одним неделимым действием. Выборка, инкремент и запоминание не могут быть прерваны, и другим процессам отказано в доступе к S во время выполнения этой операции.

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

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

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

При выполнении wait(S) и signal(S) примитивов для счетного семафора допускается изменение семафора не на 1, а на любое определенное число R.

Такое изменение обозначается: wait(S, R) и signal(S, R). Если в результате выполнения примитива wait(S) полученное значение семафора остается положительным, то процесс продолжается. В противном случае процесс «засыпает» на семафоре.

18) Передача управления между параллельными процессами. Сообщения. Почтовый ящик.

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

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

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

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

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