Processes & Threads #3

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

Семафоры

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

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

Семафор со счетчиком 1

В ванной могут возникать 2 ситуации:

  • дверь открыта и внутри никого нет
  • дверь закрыта и внутри кто-то есть

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

В некоторых операционных системах мютексов как таковых нет, они реализованы через семафоры.

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

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

Но для кухни такой вариант синхронизации не подойдет.

Семафор со счетчиком > 1

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

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

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

Существует еще несколько способов синхронизации — условные переменные, барьеры и т.д., но о них я здесь говорить не буду.

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

Прочитать

Processes & Threads #2

Поскольку основные определения и понятия уже введены перейду сразу к сути.

Взаимное исключение

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

Это именно то, что происходит с тредами при попытке доступа к общему ресурсу. Когда один тред захватывает его, то ставит на него блок(закрывает ванную изнутри на щеколду).

Это способ синхронизации, который использует объект mutex (от MUTual EXclusion — взаимное исключение). В этом примере это щеколда, которая блокирует доступ всем остальным участникам, когда кто-то помылся и вышел, т.е. снял защитный барьер, следующий тред начинает использовать ресурс и ставит на него защиту.

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

Приоритеты

Интересный вопрос встает перед операционной системой или же перед разработчиком приложения, что делать когда ванная откроется? Кого пускать первым?

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

Например можно решить это двумя факторами: приоритетом исполнения и временем ожидания.

Допустим 2 человека сразу ожидают очереди помыться, один из них уже сильно опаздывает на назначенную встречу, а у второго нет больших планов на это утро. Логичнее было бы пропустить того, у кого встреча, но каким образом это делать? Например, назначить ему больший приоритет, а человеку без планов низкий приоритет. Возможное решение делать это простыми числами от 1 до скольки-то.

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

Так что же происходит, когда дверь в ванную открывается? Мы даем возможность помыться тому, у кого приоритет выше остальных. В случае если остались все с одинаковым приоритетом "честно" будет отдать право воспользоваться ванной тому, кто дольше всех ждет.

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

Прочитать