Семафоры в UNIX как средство синхронизации процессов
Семафоры в UNIX. Отличие операций над UNIX-семафорами от классических операций
В материалах предыдущего семинара речь шла о необходимости синхронизации работы процессов для их корректного взаимодействия через разделяемую память . Как упоминалось в лекции 6, одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году. При разработке средств System V IPC семафоры вошли в их состав как неотъемлемая часть. Следует отметить, что набор операций над семафорами System V IPC отличается от классического набора операций
- A(S, n) – увеличить значение семафора S на величину n ;
- D(S, n) – пока значение семафора S , процесс блокируется. Далее S = S — n;
- Z(S) – процесс блокируется до тех пор, пока значение семафора S не станет равным 0 .
Изначально все IPC-семафоры инициируются нулевым значением.
Мы видим, что классической операции P(S) соответствует операция D(S,1) , а классической операции V(S) соответствует операция A(S,1) . Аналогом ненулевой инициализации семафоров Дейкстры значением n может служить выполнение операции A(S,n) сразу после создания семафора S , с обеспечением атомарности создания семафора и ее выполнения посредством другого семафора. Мы показали, что классические семафоры реализуются через семафоры System V IPC . Обратное не является верным. Используя операции P(S) и V(S) , мы не сумеем реализовать операцию Z(S) .
Поскольку IPC-семафоры являются составной частью средств System V IPC , то для них верно все, что говорилось об этих средствах в материалах предыдущего семинара. IPC-семафоры являются средством связи с непрямой адресацией , требуют инициализации для организации взаимодействия процессов и специальных действий для освобождения системных ресурсов по его окончании. Пространством имен IPC-семафоров является множество значений ключа, генерируемых с помощью функции ftok() . Для совершения операций над семафорами системным вызовам в качестве параметра передаются IPC- дескрипторы семафоров, однозначно идентифицирующих их во всей вычислительной системе, а вся информация о семафорах располагается в адресном пространстве ядра операционной системы. Это позволяет организовывать через семафоры взаимодействие процессов, даже не находящихся в системе одновременно.
Создание массива семафоров или доступ к уже существующему. Системный вызов semget()
В целях экономии системных ресурсов операционная система UNIX позволяет создавать не по одному семафору для каждого конкретного значения ключа, а связывать с ключом целый массив семафоров (в Linux – до 500 семафоров в массиве , хотя это количество может быть уменьшено системным администратором). Для создания массива семафоров , ассоциированного с определенным ключом, или доступа по ключу к уже существующему массиву используется системный вызов semget() , являющийся аналогом системного вызова shmget() для разделяемой памяти, который возвращает значение IPC-дескриптора для этого массива . При этом применяются те же способы создания и доступа (см. семинары 6-7 раздел «Разделяемая память в UNIX . Системные вызовы shmget() , shmat() , shmdt() «), что и для разделяемой памяти. Вновь созданные семафоры инициируются нулевым значением.
Источник
Семафоры как средство синхронизации процессов
Характеристика семафоров — удобного средства для синхронизации и взаимного исключения процессов, учёта ресурсов. Внутренняя структура, разновидности операционных систем. Основы планирования и алгоритмы диспетчеризации заданий в многопользовательской ЭВМ.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 22.10.2014 |
| Размер файла | 1,3 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
СЕМАФОРЫ КАК СРЕДСТВО СИНХРОНИЗАЦИИ ПРОЦЕССОВ
1. Семафоры как средство синхронизации процессов
Взаимное исключение на семафоре
Синхронизация на семафоре
Семафор — счетчик ресурсов
2. Теоретические основы планирования и диспетчеризации
3. Исходные данные
Дисциплина обслуживания с абсолютным приоритетом
Дисциплина обслуживания LIFO
1. Семафоры как средство синхронизации процессов
Семафоры традиционно использовались для синхронизации процессов, обращающихся к разделяемым данным. Каждый процесс должен исключать для всех других процессов возможность одновременно с ним обращаться к этим данным (взаимоисключение). Когда процесс обращается к разделяемым данным, говорят, что он находится в своем критическом участке.
Для решения задачи синхронизации необходимо, в случае если один процесс находится в критическом участке, исключить возможность вхождения для других процессов в их критические участки. Хотя бы для тех, которые обращаются к тем же самым разделяемым данным. Когда процесс выходит из своего критического участка, то одному из остальных процессов, ожидающих входа в свои критические участки, должно быть разрешено продолжить работу.
Процессы должны как можно быстрее проходить свои критические участки и не должны в этот период блокироваться. Если процесс, находящийся в своем критическом участке, завершается (возможно, аварийно), то необходимо, чтобы некоторый другой процесс мог отменить режим взаимоисключения, предоставляя другим процессам возможность продолжить выполнение и войти в свои критические участки.
В теории операционных систем семафор представляет собой неотрицательную целую переменную, над которой возможны два вида операций: P и V.
· P-операция над семафором представляет собой попытку уменьшения значения семафора на 1. Если перед выполнением P-операции значение семафора было больше 0, P-операция выполняется без задержек. Если перед выполнением P-операции значение семафора было 0, процесс, выполняющий P-операцию, переводится в состояние ожидания до тех пор, пока значение семафора не станет большим 0.
· V-операция над семафором представляет собой увеличение значения семафора на 1. Если при этом имеются процессы, задержанные на выполнении P-операции на данном семафоре, один из этих процессов выходит из состояния ожидания и может выполнить свою P-операцию.
Семафоры являются гибким и удобным средством для синхронизации и взаимного исключения процессов, учета ресурсов, скрытые семафоры также используются в операционных системах как основа для других средств взаимодействия процессов.
Взаимное исключение на семафоре
Для реализации взаимного исключения, например, предотвращения возможности одновременного изменения двумя или более процессами общих данных, создается двоичный (с возможными значениями 0 и 1) семафор S. Начальное значение этого семафора — 1. Критические секции кода (секции, которые могут одновременно выполняться только одним процессом) обрамляются «скобками» P(S) (в начале секции) и V(S) (в конце секции). Процесс, входящий в критическую секцию, выполняет операцию P(S) и переводит семафор в 0. Если в критической секции уже находится другой процесс, то значение семафора уже 0, тогда второй процесс, желающий войти в критическую секцию, блокируется в своей P-операции до тех пор, пока процесс, находящийся в критической секции сейчас, не выйдет из нее, выполнив на выходе операцию V(S).
Синхронизация на семафоре
Для обеспечения синхронизации создается двоичный семафор S с начальным значением 0. Значение 0 означает, что событие, еще не наступило. Процесс, сигнализирующий о наступлении события, выполняет операцию V(S), устанавливающую семафор в 1. Процесс, ожидающий наступления события, выполняет операцию P(S). Если к этому моменту событие уже произошло, ожидающий процесс продолжает выполняться, если же событие еще не произошло, процесс переводится в состояние ожидания до тех пор, пока сигнализирующий процесс не выполнит V(S).
В случае, если одного и того же события ожидают несколько процессов, процесс, успешно выполнивший операцию P(S), должен вслед за ней выполнить V(S), чтобы продублировать сигнал о событии для следующего ожидающего процесса.
Семафор — счетчик ресурсов
Если у нас имеется N единиц некоторого ресурса, то для контроля его распределения создается общий семафор S с начальным значением N. Выделение ресурса сопровождается операцией P(S), освобождение — операцией V(S). Значение семафора, таким образом, отражает число свободных единиц ресурса. Если значение семафора 0, то есть, свободных единиц болше не остается, то очередной процесс, запрашивающий единицу ресурса будет переседен в ожидание в операции P(S) до тех пор, пока какой-либо из использующих ресурс процессов не освободит единицу ресурса, выполнив при этом V(S).
2. Теоретические основы планирования и диспетчеризации
Функцией службы управления процессом является распределение аппаратных ресурсов центрального процессора.
Можно выделить следующие компоненты этой службы:
· планировщик задач (планировщик процессов).
Задание представляет собой описание комплекса работ, которые пользователь хочет выполнить на ЭВМ. Этот комплекс может быть представлен в виде последовательности некоторых частных работ, описываемых с помощью шагов задания. Из шагов задания формируются задачи. Для выполнения задач система создает процессы.
Объектами работы планировщика заданий (ПЛАНИРОВЩИКа) являются задания, а планировщик задач управляет процессами.
ПЛАНИРОВЩИК решает — какие задания и в какой последовательности должны поступать на обработку (своего рода «макропланировщик»). Планировщик задач выступает в роли «микропланировщика», распределяющего процессор между процессами.
В случае мультипрограммирования ПЛАНИРОВЩИК выбирает несколько заданий из множества всех представленных и вводит их в систему. Для программного выполнения заданий ПЛАНИРОВЩИК создает процессы и выделяет им необходимые ресурсы (память, внешние устройства). Планировщик процессов должен решить, какому из созданных процессов предоставить процессор, в какой момент и на какое время.
ПЛАНИРОВЩИК обеспечивает определенную дисциплину выбора заданий на обработку. Для принятия такого решения могут учитываться такие характеристики заданий, как приоритет, необходимые ресурсы и т.п. ПЛАНИРОВЩИК не только выделяет необходимые ресурсы для поступающего на обработку задания, но и освобождает ресурсы после выполнения задания.
Дисциплиной обслуживания называют правило, на основе которого из очереди выбирается задание на обслуживание.
Классификация дисциплин обслуживания приведена на рис. 1.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Рис. 1. Классификация дисциплин обслуживания
Существует несколько оценок эффективности планирования. Одной из них является время обращения задания — время, прошедшее с момента поступления задания в систему до момента завершения его выполнения.
где t — время обращения задания;
tЗ — время завершения задания;
tП — время поступления задания.
Но эта оценка не является универсальной. Например, если сравнивать время обращения одночасового и одноминутного задания (при условии, что задания начнут выполняться сразу же, как только поступят в систему), то время обращения одночасового задания будет значительно больше, чем время обращения одноминутного. Но это совсем не значит, что одночасовое задание было обслужено плохо, т.к. время обращения задания не может быть меньше времени выполнения.
Более универсальной оценкой, позволяющей сравнивать между собой задания любой длины, является взвешенное время обращения
где W — взвешенное время обращения;
T — действительное время выполнения задания (трудоемкость).
Для случая M заданий можно провести оценку по среднему взвешенному времени обращения
где — средневзвешенное время обращения;
— взвешенное время обращения i-го задания;
Источник
Синхронизация процессов с помощью семафоров
Дейкстра для решения проблемы взаимного исключения предложил концепцию семафоров.
Семафор — это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных операций (семафорных примитивов) P и V и операции инициализации.
Двоичные (бинарные) семафоры могут принимать только значения 0 или 1 (true или false), то есть могут находиться в двух состояниях: закрыт и открыт. Считающие семафоры (семафоры со счетчиками) могут принимать целые значения. Считающий семафор открыт, если значение счетчика больше 0.
Операции P и V — это семафорные примитивы (неделимые операции), во время выполнения которых процессом к переменной-семафору нет доступа для других процессов. Если одновременно несколько процессов запрашивают выполнение операций P и/или V над одним и тем же семафором, то эти операции будут выполняться последовательно, в произвольном порядке.
Примитив P — процедура, сбрасывающая или уменьшающая значение семафора на 1, эта процедура заключает в себе потенциальное ожидание вызывающих процессов в том случае, если к моменту выполнения этой процедуры процессом соответствующий семафор закрыт.
Процедура V отрывает семафор или увеличивает значение счетчика на 1. Таким образом, вызов этой процедуры может активизировать некоторый ожидающий открытия семафора процесс.
В зависимости от ограничений, установленных для значения счетчика считающего семафора, изменяется смысл семафорной переменной и алгоритм выполнения семафорных примитивов.
Если для счетчика допускаются только целые неотрицательные значения, то смысл его значения — счетчик количества некоторого ресурса. Процедура P — процедура запроса единицы этого ресурса, запрос может быть удовлетворен или может заблокировать процесс, выполнивший его, если количество ресурса равно 0. Процедура V — процедура освобождения единицы ресурса.
Если счетчик может принимать и отрицательные целые значения, то отрицательное значение семафора означает длину очереди процессов, попытавшихся пройти через семафор (запросивших соответствующий ему ресурс).
Операции выборки значения семафорной переменной S, ее изменения и сохранения не могут быть прерваны. Во время выполнения последовательности этих операций в процедурах P и V, вызванных одним процессом, над каким-либо семафором он недоступен для других процессов. Операция hold(S) означает перевод процесса в состояние ожидания на семафоре S и выход из P. Это ожидание не должно быть “занятым” (то есть нельзя зациклить процедуру P на проверке состояния семафора, так как в этом случае ни один другой процесс не смог бы получить доступ к этой защищенной переменной даже для выполнения операции открытия этого семафора). Для устранения занятого ожидания с каждым семафором связывается список блокирования (список процессов, ожидающих открытия семафора). Процесс, который не может продолжиться после выполнения P(S), будет заблокирован с сохранением его состояния в соответствующем S списке блокирования. Операция release(S) — выполняет проверку списка блокирования, связанного с семафором S, если этот список не пуст, то активизируется некоторый процесс из этого списка, пропускается через семафор, а значение семафора изменяется при этом соответствующим образом (бинарный семафор снова закрывается, а для семафора со счетчиком возвращенная процессом, выполнившем операцию V(S), единица ресурса передается очередному процессу из списка).
Ниже приведено описание семафорных примитивов для бинарных и считающих семафоров. Алгоритмы выполнения семафорных операций можно представить так:
Источник
Семафоры в синхронизации процессов
Семафор был предложен Дейкстрой в 1965 году. Это очень важный метод управления параллельными процессами с использованием простого целочисленного значения, известного как семафор. Семафор — это просто переменная, которая неотрицательна и разделена между потоками. Эта переменная используется для решения проблемы критической секции и для синхронизации процессов в многопроцессорной среде.
Семафоры бывают двух типов:
- Двоичный семафор — это также известно как блокировка мьютекса. Он может иметь только два значения — 0 и 1. Его значение инициализируется равным 1. Он используется для реализации решения проблемы критического сечения с несколькими процессами.
- Подсчет семафора — его значение может варьироваться в неограниченном домене. Он используется для управления доступом к ресурсу, который имеет несколько экземпляров.
Теперь давайте посмотрим, как это сделать.
Сначала рассмотрим две операции, которые можно использовать для доступа и изменения значения переменной семафора.
Некоторый пункт относительно работы P и V
- Операция P также называется операцией ожидания, ожидания или выключения, а операция V также называется операцией сигнала, активации или пробуждения.
- Обе операции являются атомарными, и семафор (ы) всегда инициализируется в одну. Здесь атомарная означает, что переменная, в которой считывание, изменение и обновление происходит в одно и то же время / момент без упреждения, то есть между чтением, изменением и обновлением не выполняется никаких других операций. выполняется, что может изменить переменную.
- Критическая секция окружена обеими операциями для реализации синхронизации процесса. См. Ниже image.critical секция Процесса P находится между операциями P и V.
Теперь давайте посмотрим, как это реализует взаимное исключение. Пусть будет два процесса P1 и P2, и семафор s инициализирован как 1. Теперь, если предположить, что P1 входит в его критическую секцию, тогда значение семафора s становится 0. Теперь, если P2 хочет войти в свою критическую секцию, он будет ждать, пока s > 0, это может произойти, только когда P1 заканчивает свою критическую секцию и вызывает операцию V на семафорах s. Таким образом достигается взаимное исключение. Посмотрите на изображение ниже для деталей, которые являются двоичным семафором.
Реализация бинарных семафоров:
// q содержит все блоки управления процессом (PCB)
Источник