Продолжаем разбор примитивов синхронизации. Ранее мы рассмотрели мьютексы и то как они работают внутри. При этом не упомянул семафор - фундаментальный примитив синхронизации.
Что такое семафор?
Семафор - примитив синхронизации, который ограничивает количество потоков, одновременно имеющих доступ к общему ресурсу. Внутри это целочисленная переменная над которой доступны 2 операции:
-
wait уменьшает значение счётчика. Используется перед критической секцией. Если значение счетчика внутри семафора меньше или равно 0 мы блокируемся и ждем.-
signal увеличивает значение счётчика. Используется при выходе из критической секции.Само собой, под капотом должны быть атомарный фундамент, такой же как у рассмотренного ранее мьютекса.
В каких задачах бывает полезен семафор?
Сигналы / уведомления другим потокам. Начальное значение - 0), один поток ждет, а второй делает работу, по окончанию увеличивает счетчик тем самым дает сигнал ожидающему.
Взаимное исключение. В интернете часто пишут что Mutex это частный случай семафора, а именно семафора с счетчиком = 1 (бинарный семафор). И ведь действительно похожи примитивы. Но есть две особенности:
1. Mutex в отличии от семафора может отпустить только тот поток который захватил.
2. Mutex не может быть создан с стартовым состоянием - locked.
Ограничение параллелизма. Используем семафор как ограничитель - не более N потоков могут работать одновременно. Завершив работу поток увеличивает счетчик и разблокирует следующий.
Паттерн "Производитель - потребитель". В этой задаче нам требуется защита буффера и с этой задачей справляется семафор. Разберем подробнее на примерах кода попозже.
Семафоры как отдельная сущность выделены в POSIX в пакете <semaphore.h>. Помимо этого каждая операционная система имеет свою реализацию c теми или иными особенностями.
Одной из причин почему у каждой ОС своё - особенности реализации планировщика задач в каждом конкретном случае. Всё ради того чтобы минимизировать ситуацию starvation (голодание).
Сильные и слабые семафоры. Ресурсное голодание
Рассмотрим 4 требования, которые мы так или иначе предъявляем к нашему железу и софту когда пишем код:
1. Если есть хотя бы одна задача, готовая к исполнению, она должна исполняться. Все логично. Если есть чем нагрузить железяку то надо брать в работу.
2. Если задача готова к исполнению, время до начала её исполнения должно быть конечным. Недопустима ситуация когда задача попала в очередь и постоянно вытесняется другими задачами. Если уж поток попал в очередь рано или поздно он должен получить процессорное время.
3. Если происходит сигнализирование семафором, по которому есть заблокированные задачи, то, по крайней мере, одна из них должна перейти в состояние готовности к исполнению. Тоже все логично. Если семафор освободили то разблокировка одной из заблокированных задач - то что мы ожидаем. Недопустима ситуация когда один поток постоянно захватывает семафор и отпускает, а остальные в вечном ожидании.
4. Если задача заблокирована по семафору, то количество других задач, которые будут разблокированы по тому же семафору до заданной, должно быть конечным. Это расширение правила №3 - недопустима ситуация когда одни и теже потоки захватывают и отпускают семафор, а остальные ждут.
Если связка планировщик-семафор гарантирует соблюдение первых 3х правил - это слабый семафор. Все 4 - сильный.
-----
На этом на сегодня всё. Буду рад почитать о вашем опыте работы с семафорами (или высокоуровневыми примитивами им подражающими). В следующих постах чуть глубже начнем разбираться с проблемами семафоров и мьютексов и искать решения к этим проблемам.