Семафоры и их применение - Независимые и взаимодействующие вычислительные процессы
Понятия, относящиеся к проблеме взаимоисключения, Дейкстра обобщил в своей концепции семафоров. Семафор - это переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: "закрытия" и "открытия", названных соответственно P - и V-операциями.
Значение семафора можно опрашивать и менять только при помощи примитивов P и V и операции инициализации. Семафоры могут быть двоичными (принимать значения только 0 или 1) или считающими (принимать целые неотрицательные значения).
Операции P и V неделимы в своем выполнении и взаимно исключают друг друга. Примитивы P и V значительно упростили синхронизацию процессов.
Семафорный механизм работает по схеме, в которой сначала исследуется состояние критического ресурса, идентифицируемое значением семафора, а затем уже осуществляется допуск к критическому ресурсу или отказ от него на некоторое время.
При отказе доступа к критическому ресурсу используется режим "пассивного ожидания". Поэтому в состав механизма включаются средства формирования и обслуживания очереди ожидающих процессов, которые реализуются супервизором операционной системы.
Находясь в списке заблокированных, процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо этого процессор занимается полезной работой, что повышает эффективность работы системы.
Пусть S - семафор. Операция V над семафором S записывается как V(S) и увеличивает переменную S на единицу одним неделимым действием, т. е. выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время операции V(S).
Операция P над семафором S записывается как P(S) и уменьшает переменную S на единицу, если это возможно. Если было S=0, то уменьшение S невозможно и процесс, вызвавший P-операцию, ждет, пока значение S не увеличится. Проверка и уменьшение значения S также являются одним неделимым действием.
Рассмотрим вариант реализации семафорных примитивов:
P(S): S:=S-1;
If S<0 Then {остановить процесс и поместить его в очередь ожидания к семафору S}
V(S): If S<0 Then {поместить один из ожидающих процессов очереди семафора S в очередь готовности};
S:=S+1;
Если несколько процессов одновременно запрашивают P - или V-операции над одним и тем же семафором, то эти операции будут выполняться последовательно в произвольном порядке. Аналогично, если несколько процессов ожидают выполнения P-операции и изменяемый семафор становится положительным, то процесс на продолжение выполнения может выбираться по произвольному закону. Участки взаимоисключения по семафору S в параллельных процессах обрамляются операциями P(S) и V(S).
Для работы с семафорными переменными необходимо еще иметь операцию инициализации самого семафора, т. е. операцию задания ему начального значения. Обычно эту операцию называют InitSem и она, как правило, имеет два параметра - имя семафорной переменной и ее начальное значение. Обращение к ней тогда будет иметь, например, следующий вид: InitSem(S,1).
В настоящее время используется много различных видов семафорных механизмов. Варьируемыми параметрами, которые отличают различные виды примитивов, являются начальное значение и диапазон изменения значений семафора, логика действий семафорных операций, количество семафоров, доступных для обработки при исполнении отдельного примитива. В некоторых реализациях семафорные переменные могут быть отрицательными, и величина отрицательного значения в таком случае указывает на длину очереди процессов, стоящих в состоянии ожидания открытия семафора.
Семафоры и операции над ними могут быть реализованы как программно, так и аппаратно. Программно они могут быть реализованы с использованием режима активного ожидания, однако это сопряжено с потерей эффективности. Как правило, они реализуются в ядре операционной системы, где осуществляется управление сменой состояния процессов.
Семафорные операции дают простое решение проблемы КС. Пусть S - семафор, используемый для защиты КС. Тогда примитив P(S) представляет собой вход взаимоисключения, а примитив V(S) - выход взаимоисключения. Рассмотрим пример программы, обеспечивающей взаимоисключение при помощи семафора.
Семафор имеет начальное значение, равное 1. Если первый и второй процессы попытаются одновременно выполнить примитив P(S), то это удастся успешно сделать только одному из них.
Предположим, что это сделал первый процесс. Он закрыл семафор, т. е. значение семафора стало S = 0, после чего данный процесс вошел в свой критический интервал. Второй процесс при этом оказывается заблокированным на семафоре - при попытке выполнения операции P(S) он "засыпает".
Взаимное исключение гарантировано, т. к. только один процесс может уменьшить значение S до нуля с помощью P-операции. Очевидным образом это решение распространяется на случай n процессов - тогда все другие процессы, пытающиеся войти в свои КС при S = 0, будут вынуждены ожидать по P(S). Взаимное блокирование невозможно, т. к. одновременные попытки войти в свои КС при S = 0 должны, по определению, преобразовываться в последовательные P-операции. После выхода из своей КС процесс выполняет V-операцию, тем самым открывая семафор и предоставляя возможность "пробуждения" блокированным процессам. Тогда один из блокированных процессов переводится в очередь готовности.
При реализации возможно одно из двух решений в отношении процессов, которые переводятся из очереди ожидания в очередь готовности при выполнении примитива V(S):
- - процесс при его активизации вновь пытается выполнить примитив P, считая предыдущую попытку неуспешной; - процесс при помещении его в очередь готовности отмечается как успешно выполнивший примитив P. Тогда при его активизации управление будет передано не на повторное выполнение примитива P, а на команду, следующую за ним.
При первом способе возможна следующая последовательность событий. Предположим, что начальное значение семафора было равно единице. Пусть процесс2 в какой-то момент времени выполнит операцию P(S), семафор S станет равным нулю, а процесс2 войдет в свою КС. Далее процесс1 тоже попытается выполнить операцию P(S) и "заснет" на семафоре, поскольку значение семафора теперь станет равным -1. После выхода из КС процесс2 выполнит V(S), при этом значение семафора станет равным 0, а процесс1 переведется в очередь готовности.
После активизации процесс1 снова выполнит P(S) и опять "уснет", то же самое произойдет с процессом2, если он пожелает войти в свою КС. "Пробуждать" процессы станет некому. Таким образом, возможно возникновение тупиковой ситуации.
При втором способе реализации тупиковой ситуации не будет. Действительно, при аналогичном варианте развития событий отличие начнется с момента активизации процесса1. Он сразу войдет в свою КС. При этом никакой другой процесс не попадет в критическую секцию, т. к. семафор остается закрытым (его значение равно 0).
После окончания работы процесса1 в КС в результате выполнения им операции V(S) значение семафора установится в единицу, если другие процессы не совершали попыток попасть в КС. Если процесс2, а также и другие процессы в случае их большего количества, во время работы процесса1 в КС также выполнят примитив P(S), то после выполнения процессом1 V-операции семафор установится в 0. Следовательно, он будет закрыт для всех процессов кроме того, который успел выполнить P-операцию, т. е. сделал заявку на КС. Таким образом, тупик не возникнет, а взаимоисключение гарантировано.
Возникновение тупиков возможно в случае несогласованного выбора механизма реактивации процессов из очереди, с одной стороны, и выбора алгоритмов семафорных операций - с другой (как мы видим в первом способе реализации).
Похожие статьи
-
Основной особенностью мультипрограммных операционных систем является то, что в их среде параллельно развивается несколько (последовательных)...
-
Основной особенностью мультипрограммных вычислительных систем является то, что в их среде параллельно развивается несколько (последовательных)...
-
Введение - Преимущества применения dataflow-парадигмы в вычислительных системах
Dataflow-парадигма В архитектурах вычислительных сетей на сегодняшний день преобладающую роль играют ВС, управляемые потоком команд - Control Flow. Такая...
-
СЕМАНТИКА, Схема подпрограммы вычитания - Теория вычислительных процессов
Операционная семантика команды sub al, 1 L1(al) 1 1 0 1 1 0 0 1 # 0 1 1 0 1 1 0 0 # L2 1. q01X1 Top1 q11 2. q11X1B1q02 3. q02X2 Top2 q12 4. q12X2 02 q22...
-
Ядром вычислительной dataflow-системы будем называть совокупность оборудования, которое осуществляет сбор данных для формирования исполняемого пакета. В...
-
Разделение вычислений на независимые части - Администрирование параллельных процессов
Выбор способа разделения вычислений на независимые части основывается на анализе вычислительной схемы решения исходной задачи. Требования, которым должен...
-
Взаимодействие задач с PVM - Администрирование параллельных процессов
В системе PVM каждая задача, запущенная на некотором процессоре, идентифицируется целым числом, которое называется идентификатором задачи (TID) и по...
-
Кодированием называется представление символов одного алфавита средствами другого алфавита. Алфавит содержащий два символа называется двоичным (часто их...
-
Вычислительные эксперименты для оценки эффективности параллельного варианта метода Гаусса для решения систем линейных уравнений проводились при следующих...
-
В работе использовались следующее программное обеспечение для решения поставленных задач: AutoCAD, ANSYS Workbench, ANSYS Icepak. Система AutoCAD...
-
Методика упреждающей диагностики заключается в следующем. Администратор сети должен непрерывно или в течение длительного времени наблюдать за работой...
-
При прогонах тестовой программы, написанной на ПЯ, для алгоритма бенчмарка Graph500, изменялись значения входных параметров, таких как: - N - число ИУ...
-
ВВЕДЕНИЕ, АНАЛИЗ ЗАДАЧИ - Теория вычислительных процессов
Ассемблер программа верификация Написать на языке ассемблер программу, реализующую вычитание двух целых упакованных 128- разрядных чисел. Описать...
-
Моделирование различных вычислительных систем можно разделить на два главенствующих класса: матечатическое моделировании и имитационное. Математическое...
-
Оценка моделируемой ВС осуществляется на основе анализа функционирования ВС на тестовых задачах по следующему набору параметров: - общее число ИУ в ВС; -...
-
Основные функции: - Исполнение запросов программ (ввод и вывод данных, запуск и остановка других программ, выделение и освобождение дополнительной памяти...
-
В реалиазации милликомандного типа управления вычислительной системой основную роль играет функциональное устройство "Автомат". Это устройство отвечает...
-
ОА-архитектура - Преимущества применения dataflow-парадигмы в вычислительных системах
В данной работе предлагается использование объектно-атрибутной архитектуры ВС (или ОА-архитектуры). В отличие от классической ВС, ОА-архитектура работает...
-
В основном для многих вычислительных систем топологическое проектирование производится с помощью нейросетевых алгоритмов так, чтобы минимизировать...
-
Назначение вычислительного кластера - Администрирование параллельных процессов
Кластеры используются в вычислительных целях, в частности в научных исследованиях. Для вычислительных кластеров существенными показателями являются...
-
Модель вычислительного процесса в GridMD - Повышение производительности работы библиотеки GridMD
Узлы графа исполнения, используемого в GridMD, представляют собой конкретные этапы исполнения, с которыми связываются действия, определяемые программным...
-
Моделирование параллельных программ Рассмотренная схема проектирования и реализации параллельных вычислений дает способ понимания параллельных алгоритмов...
-
Скалярные переменные - Язык программирования PERL. Сфера применения
Как отмечалось, скалярная переменная может содержать единственное значение. В языке Perl имена скалярных переменных всегда начинаются со знака ($). В еле...
-
Моделирование представляет собой один из основных методов познания, является формой отражения действительности и заключается в выяснении или...
-
Процессы и потоки - Разработка мобильного приложения расчета и учета оплаты коммунальных услуг
Когда хотя бы один из компонентов приложения (или все приложение) будет востребован, система Android запускает процесс, который содержит единственный...
-
Процесс декомпозиции - Администрирование параллельных процессов
Распараллеливание программ сводится к процессу декомпозиции задачи на независимые процессы, которые не требуют последовательного исполнения и могут,...
-
Многозадачный технологический процесс - Методы анализа объектов и решений
Многозадачный технологическим процессом называется технологический процесс изготовления группы деталей с разными (в определенных пределах)...
-
Ниже представлены результаты моделирования теста Grep на ОА-архитектуре. Моделирование проводилось при следующих параметрах анализируемого текста: 1)...
-
Выбор и обоснование критериев оценки моделируемой системы Основными критериями оценки созданной вычислительной системы с управлением потоком данных по...
-
СЕТЬ ПЕТРИ, ТЕКСТ ПРОГРАММЫ - Теория вычислительных процессов
Начальная разметка сети: одна фишка в позиции S1. После завершения функционирования сети фишка будет в позиции S2 Расшифровка переходов: 1. T1 - push f...
-
В предыдущем разделе был приведен необходимый для получения набор выходных характеристик моделируемой вычислительной системы, требуемый от тестирования....
-
Конечно-элементный анализ широко применяется при решении задач механики деформируемого твердого тела, теплообмена, гидро - и газодинамики, электро - и...
-
Каскадные коды Каскадный код представляет собой разновидность составного кода, формируемого последовательной схемой кодирования. При практической...
-
Сетевыми протоколами называют протоколы первого и второго уровней, определяющих архитектуру локальной сети, в том числе ее топологию, передающую среду,...
-
Идентификация процесса - ПИД-контроллеры фирмы Honeywell
Первый шаг в процесс автонастройки - определение подходящего описания объекта управления. Далее приводятся два наиболее часто используемых метода поиска...
-
Дистрибутивы развертывания кластера - Администрирование параллельных процессов
ParallelKnoppix - это модификация хорошо известного Linux-дистрибутива Knoppix live CD, которая позволяет установить кластер компьютеров для выполнения...
-
Модели параллельных вычислений - Администрирование параллельных процессов
Параллельное программирование представляет дополнительные источники сложности необходимо явно управлять работой тысяч процессоров, координировать...
-
Формы и характеристики параллелизма Параллелизм -- это возможность одновременного выполнения нескольких арифметико-логических или служебных операций. На...
-
Коммуникационная библиотека MPI MPI это интерфейс прикладного программирования к библиотеке пересылки сообщений, содержащий в себе спецификации к...
-
Понятие атаки на ИС. Примеры атак - Технологический процесс в электронной промышленности
Прежде чем обсуждать способы выявления атак, определим, что же такое атака. Итак, атака - это совокупность действий злоумышленника, приводящих к...
Семафоры и их применение - Независимые и взаимодействующие вычислительные процессы