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

Question

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

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

Answer 1

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

Answer 2

@Craig:

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

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

Answer 3

Статья Mutexes and Semaphores Demystified Майкла Барра - отличное краткое введение в то, что делает мьютексы и семафоры разными, и когда их следует и не следует использовать. Здесь я привел несколько ключевых параграфов.

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

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

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

...

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

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

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

...

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

...

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

...

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

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

мьютекс: ресурс обмена

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

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

Answer 4

мьютекс: доступ к эксклюзивным членом к ресурсу

Семафор: Режим доступа н-членов к ресурсу

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

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

Answer 5

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

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

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

Answer 6

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

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

Вот очень педагогический пример в 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); 
     } 
    } 
} 

Answer 7

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

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

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

из очереди

Answer 8

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

Answer 9

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

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

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

Далее read:

Answer 10

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

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

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

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

Answer 11

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

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

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

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

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

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

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 (закрытый). Thread 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?)

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

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

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

Answer 12

Рассмотрите, такси. На такси может разместиться максимум 3 (задних) +2 (передних) человека, включая водителя. Таким образом, семафор позволяет одновременно вмещать только 5 человек внутри автомобиля. И мьютекс позволяет только одному человеку на сиденье в автомобиле. Итак, мьютекс должен разрешить эксклюзивный доступ к ресурсу. Семафор допускает одновременный доступ к n количеству ресурсов за раз.

Answer 13

Вот некоторые более интересные знания о семафора:

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

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

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

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

В обоих операциях P и V арифметика должна выполняться без помех. Если две операции V выполняются одновременно на одном и том же семафоре, чистый эффект должен состоять в том, что новое значение семафора на два больше, чем было.

Мнемоническое значение P и V непонятно для большей части мира, так как Дейкстра - голландский. Тем не менее, в интересах настоящей стипендии: P означает пролаген, составленное слово, полученное из proberen te verlagen, что означает попытку уменьшить. V означает verhogen, что означает увеличение. Это обсуждается в одной из технических заметок Дейкстры, EWD 74.

sem_wait (3RT) и sem_post (3RT) соответствуют операциям P и V Dijkstra. sem_trywait (3RT) является условной формой операции P: если вызывающий поток не может уменьшить значение семафора без ожидания, вызов немедленно возвращается с ненулевым значением.

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

Однако, хотя он не применяется, мьютексы должны быть разблокированы только резьбой, удерживающей замок. Не существует понятия «поток, содержащий семафор», поэтому любой поток может выполнять операцию V (или sem_post (3RT)).

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

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

Answer 14

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

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

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

Семафоры обычно используются для двух целей: 1) Общий доступ к памяти 2) Чтобы предоставить общий доступ к файлам.

Семафоры являются одним из методов межпроцессного взаимодействия (IPC).

Язык программирования C предоставляет набор интерфейсов или «функций» для управления семафорами.