Что такое семафор?

351

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

Что такое семафор и как вы его используете?

bmurphy1976
источник
14
логический флаг, значение которого основано на том, достиг ли целочисленный счетчик установленного верхнего предела. Запутывание по максимуму!
Сэм

Ответы:

400

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

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

Вот очень педагогический пример в C # :-)

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace TheNightclub
{
    public class Program
    {
        public static Semaphore Bouncer { get; set; }

        public static void Main(string[] args)
        {
            // Create the semaphore with 3 slots, where 3 are available.
            Bouncer = new Semaphore(3, 3);

            // Open the nightclub.
            OpenNightclub();
        }

        public static void OpenNightclub()
        {
            for (int i = 1; i <= 50; i++)
            {
                // Let each guest enter on an own thread.
                Thread thread = new Thread(new ParameterizedThreadStart(Guest));
                thread.Start(i);
            }
        }

        public static void Guest(object args)
        {
            // Wait to enter the nightclub (a semaphore to be released).
            Console.WriteLine("Guest {0} is waiting to entering nightclub.", args);
            Bouncer.WaitOne();          

            // Do some dancing.
            Console.WriteLine("Guest {0} is doing some dancing.", args);
            Thread.Sleep(500);

            // Let one guest out (release one semaphore).
            Console.WriteLine("Guest {0} is leaving the nightclub.", args);
            Bouncer.Release(1);
        }
    }
}
Патрик Свенссон
источник
6
если это похоже на вышибалы в ночном клубе, он должен позволять гостям входить последовательно, но когда я это пробовал, это случайно. Например. Гость 40 пришел первым, прежде чем Гость 39. Можем ли мы что-нибудь сделать, чтобы это контролировать?
TNA
2
@TNA: Да, это связано с тем, как в этом примере запускаются новые потоки, а не в рамках ответа.
Патрик Свенссон
5
Аналогия с вышибалами действительно эпическая, но интересно, что она уже использовалась: albahari.com/threading/part2.aspx#_Semaphore
Игорь Брейц,
Какую ценность семафоры предлагают в распределенных системах?
csandreas1
198

Статья « Мьютексы и семафоры, демистифицированные » Майклом Барром, представляет собой краткое краткое описание того, что делает мьютексы и семафоры разными, а также когда они должны и не должны использоваться. Я выдержал несколько ключевых параграфов здесь.

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

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

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

...

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

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

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

...

Правильное использование семафора для передачи сигналов от одной задачи к другой. Мьютекс предназначен для взятия и освобождения, всегда в таком порядке, каждой задачей, которая использует общий ресурс, который он защищает. Напротив, задачи, которые используют семафоры, либо сигнализируют, либо ждут, но не оба. Например, Задача 1 может содержать код для публикации (т. Е. Сигнала или приращения) определенного семафора, когда нажата кнопка «питание», и Задача 2, которая активирует отображение, ожидает этого же семафора. В этом сценарии одна задача является источником сигнала события; другой потребитель.

...

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

...

Причина широко распространенной современной путаницы между мьютексами и семафорами является исторической, поскольку она восходит к 1974 году, когда был изобретен Семафор (заглавная "S" в этой статье) Джикстра. До этой даты ни один из механизмов синхронизации и сигнализации о безопасных прерываниях, известных компьютерным специалистам, не был эффективно масштабируемым для использования более чем двумя задачами. Революционный, безопасный и масштабируемый семафор Дейкстры был применен как для защиты критических участков, так и для сигнализации. И так началась неразбериха.

Однако впоследствии разработчикам операционных систем стало очевидно, что после появления приоритетной ОСРВ с приоритетом (например, VRTX, около 1980 г.), публикации научных работ, посвященных RMA и проблемам, вызванным инверсией приоритетов, и документа о приоритете. Протоколы наследования в 1990 году 3 показали, что мьютексы должны быть чем-то большим, чем просто семафоры с двоичным счетчиком.

Mutex: обмен ресурсами

Семафор: сигнализация

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

Адам Дэвис
источник
10
Посмотрите на этот PDF-документ о параллельности в Стэнфорде. Посмотрите на страницы 8. Приведенное выше объяснение будет иметь больше смысла, чем .. see.stanford.edu/materials/icsppcs107/…
Крис Субраманян
3
Книжечка семафоров является ценным читать об этих вопросах.
Г. Бах
@KrisSubramanian Спасибо за ссылку. Но в документе говорится о семафорах и ничего о мьютексах. Однако подразумеваете ли вы, что общий буфер в этом примере может быть защищен с помощью Mutex? вместо двух семафоров emptyBuffers и fullBuffers
talekeDskobeDa
1
@Pramod True. Ссылка не добавляет заметки, связанные с Mutex. Я добавил ссылку, чтобы стороны Семафора стали понятны SO читателям. :) Интересно, что в этом случае буфер используется без каких-либо блокировок, поскольку к нему обращаются последовательно и в циклическом формате. т.е. Writer будет писать в 0 и сигнализировать читателю о чтении из 0. Если считыватель не читает из 0 и сигнализирует пишущему, то писатель блокирует. Поэтому нет необходимости использовать мьютекс для блокировки общего ресурса. Это отличается от аналогии с ванной, приведенной выше.
Крис Субраманян
@Kris Subramanian: хороший документ, но с небольшими ошибками: на 3-й странице говорится, что «каждый поток, который блокирует семафор, должен быть осторожен, чтобы разблокировать его» - они могут быть разблокированы любым потоком. Если вы делаете это в том же потоке, вы просто используете его как "brocken mutex". "Brocken", потому что он все еще может быть непреднамеренно разблокирован из другого потока - ошибки случаются - и нарушают вашу логику. До сих пор хороший документ, подумал.
Рустам А.
70

Mutex: эксклюзивный доступ к ресурсу

Семафор: n-членский доступ к ресурсу

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

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

Майкл Харен
источник
20
Согласно Ричарду У. Стивенсу, мьютекс на самом деле является двоичным семафором, имеющим только два возможных значения: 0 и 1.
Цян Сюй
19
@QiangXu в разделе « Внутренние компоненты операционных систем и принципы проектирования » Уильяма Сталлингса, двоичный семафор отличается от мьютекса одним очень важным способом, и я цитирую: «Ключевое различие между мьютексом и двоичным семафором заключается в том, что процесс, который блокирует мьютекс должен быть один, чтобы разблокировать его. Напротив, один процесс может заблокировать двоичный семафор, а другой - разблокировать его ». ,
Электрический кофе
3
Риск комментировать несвежую ветку, это не правильно. Как уже упоминалось в @AdamDavis, семафор не должен (должен?) Использоваться для доступа n-членов к ресурсу, что по-прежнему должно выполняться с помощью Mutex. Рассмотрим аналогию с ванной комнатой в Coffeeshop: несколько человек ожидают доступа или несколько других ванных комнат с похожими ключами от ванных комнат. Скорее Семафор должен использоваться для сигнализации между задачами.
cspider
21

Рассмотрим такси, которое может вместить в общей сложности 3 ( сзади ) +2 ( впереди ) человека, включая водителя. Итак,semaphore салоне находиться только 5 человек. И mutexпозволяет только 1 человек на одном сиденье автомобиля.

Следовательно, Mutexон должен разрешать монопольный доступ к ресурсу ( например, потоку ОС ), в то время как a Semaphoreдолжен предоставлять доступ к n количеству ресурсов одновременно.

NKumar
источник
19

@Craig:

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

Это не ограничено только одним потоком. Семафор можно настроить так, чтобы разрешить фиксированному количеству потоков доступ к ресурсу.

Матс Фредрикссон
источник
7
Это комментарий, а не ответ.
Касперский
11
Да, но я думаю, что написал это до того, как комментарии были добавлены в Переполнение стека. Или я не знаю, не помню. На этот раз я ответил в комментарии, хотя. :-)
Матс Фредрикссон
16

Семафор также можно использовать как ... семафор. Например, если у вас есть несколько процессов, помещающих данные в очередь, и только одна задача, потребляющая данные из очереди. Если вы не хотите, чтобы ваша задача-потребитель постоянно опрашивала очередь на наличие доступных данных, вы можете использовать семафор.

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

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

shodanex
источник
11

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

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

Семафор состоит из двух частей: счетчика и списка задач, ожидающих доступа к определенному ресурсу. Семафор выполняет две операции: wait (P) [это похоже на получение блокировки] и release (V) [аналогично освобождению блокировки] - это единственные две операции, которые можно выполнить с семафором. В двоичном семафоре счетчик логически переходит от 0 до 1. Вы можете думать, что он похож на блокировку с двумя значениями: открыт / закрыт. Счетный семафор имеет несколько значений для счета.

Важно понимать, что счетчик семафоров отслеживает количество задач, которые не нужно блокировать, т. Е. Они могут добиться прогресса. Задачи блокируются и добавляются в список семафоров только тогда, когда счетчик равен нулю. Следовательно, задача добавляется в список в процедуре P (), если она не может быть выполнена, и «освобождается» с помощью процедуры V ().

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

ех. Синхронизация:

thread A{
semaphore &s; //locks/semaphores are passed by reference! think about why this is so.
A(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
;// some block of code B2
...
}

//thread B{
semaphore &s;
B(semaphore &s): s(s){} //constructor
foo(){
...
...
// some block of code B1
s.V();
..
}

main(){
semaphore s(0); // we start the semaphore at 0 (closed)
A a(s);
B b(s);
}

В приведенном выше примере B2 может выполняться только после того, как B1 завершил выполнение. Предположим, что поток A выполняется первым, выполняет - получает sem.P () и ждет, так как счетчик равен 0 (закрыт). Появляется поток B, заканчивает B1, а затем освобождает поток A, который затем завершает B2. Таким образом, мы достигаем синхронизации.

Теперь давайте посмотрим на взаимное исключение с помощью двоичного семафора:

thread mutual_ex{
semaphore &s;
mutual_ex(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
//critical section
s.V();
...
...
s.P();
//critical section
s.V();
...

}

main(){
semaphore s(1);
mutual_ex m1(s);
mutual_ex m2(s);
}

Взаимное исключение также довольно просто - m1 и m2 не могут одновременно войти в критическую секцию. Таким образом, каждый поток использует один и тот же семафор, чтобы обеспечить взаимное исключение для его двух критических секций. Теперь возможно ли иметь больший параллелизм? Зависит от критических разделов. (Подумайте, как еще можно использовать семафоры для достижения взаимного исключения. Подсказка: мне обязательно нужно использовать только один семафор?)

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

Давайте возьмем самое простое из двух:

Синхронизация с использованием счетного семафора. Допустим, у вас есть 3 задачи - № 1 и 2, которые вы хотите выполнить после 3. Как бы вы разработали свою синхронизацию?

thread t1{
...
s.P();
//block of code B1

thread t2{
...
s.P();
//block of code B2

thread t3{
...
//block of code B3
s.V();
s.V();
}

Таким образом, если ваш семафор начинается закрытым, вы гарантируете, что блоки t1 и t2 будут добавлены в список семафоров. Затем приходит все важное t3, заканчивает свою деятельность и освобождает t1 и t2. В каком порядке они освобождены? Зависит от реализации списка семафоров. Может быть FIFO, может основываться на каком-то конкретном приоритете и т. Д. (Примечание: подумайте, как бы вы расположили свои P и V; если вы хотите, чтобы t1 и t2 выполнялись в каком-то определенном порядке, и если вы не знали о реализации семафора)

(Узнайте: что произойдет, если число V больше, чем число P?)

Взаимное исключение Использование счетных семафоров: я бы хотел, чтобы вы создали для этого свой собственный псевдокод (помогает вам лучше понимать вещи!), Но фундаментальная концепция такова: счетный семафор counter = N позволяет N задачам свободно входить в критическую секцию. , Это означает, что у вас есть N задач (или потоков, если хотите), попадающих в критическую секцию, но N + 1-я задача блокируется (попадает в наш любимый список заблокированных задач) и пропускается только тогда, когда кто-то из V семафор. Хотя бы один раз. Таким образом, счетчик семафоров, вместо того, чтобы колебаться между 0 и 1, теперь идет между 0 и N, позволяя N задачам свободно входить и выходить, не блокируя никого!

Черт возьми, зачем тебе такая глупость? Разве весь смысл взаимного исключения состоит в том, чтобы не позволить больше чем одному парню получить доступ к ресурсу ?? (Подсказка Подсказка ... у вас не всегда есть только один диск на вашем компьютере, не так ли? ...)

Для размышления : достигается ли взаимное исключение только с помощью счетного семафора? Что если у вас есть 10 экземпляров ресурса и 10 потоков входят (через счетный семафор) и пытаются использовать первый экземпляр?

aspen100
источник
7

Семафор - это объект, содержащий натуральное число (т. Е. Целое число, большее или равное нулю), для которого определены две модифицирующие операции. Одна операция, Vдобавляет 1 к естественному. Другая операция, Pуменьшает натуральное число на 1. Обе операции являются атомарными (т.е. никакая другая операция не может быть выполнена одновременно с a Vили a P).

Поскольку натуральное число 0 не может быть уменьшено, вызов Pсемафора, содержащего 0, будет блокировать выполнение вызывающего процесса (/ потока) до некоторого момента, когда число больше не равно 0 и Pможет быть успешно (и атомарно) выполнено.

Как упоминалось в других ответах, семафоры могут использоваться для ограничения доступа к определенному ресурсу максимальным (но переменным) числом процессов.

mweerden
источник
7

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

ExecutorService executor = Executors.newFixedThreadPool(7);

Semaphore semaphore = new Semaphore(4);

Runnable longRunningTask = () -> {
    boolean permit = false;
    try {
        permit = semaphore.tryAcquire(1, TimeUnit.SECONDS);
        if (permit) {
            System.out.println("Semaphore acquired");
            Thread.sleep(5);
        } else {
            System.out.println("Could not acquire semaphore");
        }
    } catch (InterruptedException e) {
        throw new IllegalStateException(e);
    } finally {
        if (permit) {
            semaphore.release();
        }
    }
};

// execute tasks
for (int j = 0; j < 10; j++) {
    executor.submit(longRunningTask);
}
executor.shutdown();

Вывод

Semaphore acquired
Semaphore acquired
Semaphore acquired
Semaphore acquired
Could not acquire semaphore
Could not acquire semaphore
Could not acquire semaphore

Пример кода из статьи

Владимир
источник
3

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

MABUTOBRIGHTON
источник
2

Семафоры действуют как ограничители потоков.

Пример: если у вас есть пул из 100 потоков, и вы хотите выполнить какую-либо операцию с БД. Если 100 потоков обращаются к БД в определенный момент времени, то в БД может возникнуть проблема с блокировкой, поэтому мы можем использовать семафор, который допускает только ограниченный поток за раз. В следующем примере разрешен только один поток за один раз. Когда поток вызывает acquire()метод, он получает доступ и после вызова release()метода освобождает доступ, так что следующий поток получит доступ.

    package practice;
    import java.util.concurrent.Semaphore;

    public class SemaphoreExample {
        public static void main(String[] args) {
            Semaphore s = new Semaphore(1);
            semaphoreTask s1 = new semaphoreTask(s);
            semaphoreTask s2 = new semaphoreTask(s);
            semaphoreTask s3 = new semaphoreTask(s);
            semaphoreTask s4 = new semaphoreTask(s);
            semaphoreTask s5 = new semaphoreTask(s);
            s1.start();
            s2.start();
            s3.start();
            s4.start();
            s5.start();
        }
    }

    class semaphoreTask extends Thread {
        Semaphore s;
        public semaphoreTask(Semaphore s) {
            this.s = s;
        }
        @Override
        public void run() {
            try {
                s.acquire();
                Thread.sleep(1000);
                System.out.println(Thread.currentThread().getName()+" Going to perform some operation");
                s.release();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        } 
    }
Sumit
источник
1

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

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

Есть также различия между двоичным / мьютексом и счетными семафорами.

Ознакомьтесь с примечаниями к лекции по адресу http://www.cs.columbia.edu/~jae/4118/lect/L05-ipc.html .

Студент Колумбии в классе Jae
источник
0

Это старый вопрос, но одно из самых интересных применений семафора - блокировка чтения / записи, и он явно не упоминался.

Р / ж замки работают простым способом: потребляют одно разрешение для читателя и все разрешения для писателей. Действительно, тривиальная реализация блокировки ar / w, но требует модификации метаданных при чтении (фактически дважды), которая может стать узким местом, все же значительно лучше, чем мьютекс или блокировка.

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

Далее читайте :

bestsss
источник
-3

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

Крейг Н
источник
13
звучит как мьютекс, а не семафор
Сэм