С годами подходы к обработке конкурентности в ядре Linux сильно изменились. К 2023 году в арсенале разработчиков ядра появились, в частности, автозавершения, хорошо оптимизированные мьютексы, а также россыпь неблокирующих алгоритмов. Но были времена, когда управление конкурентностью сводилось к использованию обычных семафоров. Дискуссия о внесении небольшого изменения в API семафоров лишний раз свидетельствует, как сильно они изменились за долгую историю ядра.
В сущности, семафор — это целочисленный счётчик, с его помощью контролируется доступ к ресурсу. Тот код, которому требуется доступ, должен сначала понизить счётчик на единицу, но только при условии, что в данный момент значение этого счётчика выше нуля. В противном случае запрашивающий код должен дождаться, пока значение семафора увеличится. Высвобождение семафора зависит от увеличения значения счётчика. В реализации ядра Linux занятие семафора происходит путём вызова down() (или ещё одного из нескольких вариантов). Если семафор недоступен, то вызов down() будет дожидаться, пока какой-нибудь другой поток его не высвободит. Неудивительно, что операция высвобождения называется up(). В классической литературе (в трактовке Эдсгера Дейкстры) такие операции называются P() и V().
В версии ядра 0.01, вышедшей в 1991 году, семафоров не было — в сущности, как и любых других механизмов управления конкурентностью. В самом начале ядро работало только на однопроцессорных системах и, ядро, как и большинство Unix-систем того времени, обладало исключительным доступом к ЦП на такой срок, в течение которого оно работало. Процесс, работающий в ядре, не мог быть вытеснен и продолжал выполняться до тех пор, пока его явно не блокировали после некоторого события или не возвращали в пользовательское пространство, поэтому такая проблема, как гонки данных, была редкостью. Единственное исключение — это аппаратные прерывания. Чтобы предотвратить нежелательное конкурирование из-за прерываний, код обильно сдабривали вызовами cli() и sti(), позволявшими блокировать (и разблокировать) прерывания по мере необходимости.
В мае 1992 года вышла версия 0.96, в которой были привнесены некоторые важные изменения; в частности, появилась первичная поддержка «сетевых» операций. Такая поддержка обеспечивала работу с Unix-подобными сокетами при помощи специфичного для Linux системного вызова socketcall(). Правда, наиважнейшее нововведение в этом релизе заключалось, пожалуй, в том, что именно здесь была добавлена поддержка SCSI-устройств. Качественная поддержка SCSI сыграла ключевую роль на раннем этапе формирования аудитории Linux. С появлением подсистемы SCSI впервые зашла речь о семафорах в ядре; они были спрятаны глубоко в слое драйверов. Семафоры SCSI, как и многие появившиеся впоследствии, были двоичными. Таким образом, в качестве исходного значения для них устанавливалась единица, поэтому доступ к данному ресурсу (хост-контроллеру SCSI) мог получить всего один поток, тот, который им управлял. В версии 0.99.10, вышедшей в июне 1993 года, был повторно реализован сетевой уровень, и появилась поддержка семафоров System V в пользовательском пространстве, но общей поддержки семафоров в ядре к тому времени ещё не существовало.
Как в ядро были добавлены семафоры
Первая реализация семафоров общего назначения именно для ядра появилась в релизе 0.99.15c, вышедшем в феврале 1994 года. Первоначально их использовали на уровне виртуальной файловой подсистемы ядра, где семафор добавлялся к структуре inode; никаких других вариантов использования не предусматривалось до релиза 1.0, вышедшего месяцем позже. В версии 2.0 (июнь 1996) количество семафоров стало медленно расти, а также добавилась пресловутая большая блокировка ядра (BKL), которая семафором не была.
С этого началась поддержка SMP, и даже тогда код ядра по умолчанию работал под BKL. Поэтому по большей части коду ядра если и требовалось иметь дело с конкурентностью, то в ограниченном объёме. В сущности, при BKL сразу предполагалось, что код будет обладать исключительным доступом к ЦП — эта возможность была с самого начала глубоко вшита в код. В такой ситуации в любой момент ядро Linux могло работать только в одном ядре процессора. Поэтому в те времена для управления конкурентностью в ядре Linux прибегали преимущественно к отключению прерываний.
К релизу 2.2 (январь 1999) в ядре насчитывалось 71 объявление struct semaphore; к релизу 2.4.0 (январь 2001) это количество выросло до 138, а к 2.6.0 (декабрь 2003) их было уже 332. В релизе 2.6.14, октябрь 2005, было 483 объявления семафоров. К тому времени отключать прерывания ради управления конкурентностью становилось всё более не комильфо — попросту приходилось слишком серьёзно расплачиваться производительностью системы за такую практику — а большая блокировка ядра стала превращаться в самостоятельную проблему, осложнявшую масштабирование.
Тем временем, в рабочей версии ядра 2.1.23 была добавлена первая инфраструктура для работы со спинлоками, но она как следует не применялась до тех пор, пока в версии 2.1.30 не появился планировщик. Спинлок, в отличие от семафора — это чисто взаимоисключающий примитив, в нём не предусмотрен такой счётчик, как в семафоре. Кроме того, это «неспящая» блокировка. Код, дожидающийся спинлока, будет просто «крутиться» в плотном цикле, пока не появится доступная блокировка. До такого дополнения семафоры оставались единственным универсальным механизмом взаимоисключения, который поддерживался в ядре.
Во многих ситуациях спинлоки были уместнее семафоров, но с ними сопряжено такое ограничение: коду, удерживающему спинлок, не разрешается спать. Таким образом, для работы с семафорами всё равно требовалась семафороподобная структура. Но примерно к концу 2005 года разработчики стали подумывать, что для случая с двоичным семафором (а именно так использовалось большинство семафоров) могло бы существовать и более качественное решение. Оказалось, что исходная реализация мьютексов работает хуже семафоров. Но, как часто бывало в те времена, Инго Мольнар за считанные дни выкатил более быструю реализацию. Вскоре мьютексы были добавлены в ядро в качестве альтернативы семафорам, и начался процесс преобразования семафоров в мьютексы.
Медленный переход
Когда появились мьютексы, разработчики переживали, что из-за мьютексов возникнет необходимость «с завтрашнего дня жить по-новому», и все двоичные семафоры будут заменены на новый тип. Но мьютексы были добавлены, а старый тип — оставлен. Так они смогли сосуществовать, а преобразование кода из одной формы в другую не составляло труда. Неудивительно, что в ядре по сей день остаётся объявлено более 100 семафоров, и, по-видимому, основная масса из них — двоичные. Но сложно найти патчи, при которых добавлялись бы новые семафоры. Наверное, самый свежий — этот патч драйвера от августа 2022. Представляется, что большинству разработчиков ядра сейчас не приходится особо задумываться о семафорах.
Недавно Луис Чемберлен, занимающийся поддержкой модулей, работал над такой проблемой: если за короткое время поступает большое количество вызовов на загрузку модулей, то могут возникать сложности с подсистемой управления памятью. Проконсультировавшись с коллегами, он предложил механизм, который просто ограничивал бы количество операций по загрузке модулей, которые могут выполняться в любой конкретный момент. Ему быстро ответил Линус Торвальдс и напомнил, что для этой цели можно пользоваться семафорами — «классическим ограничителем конкурентности». С тех пор патч был переработан именно в таком духе.
Однако в рамках развернувшейся по этому поводу дискуссии Питер Зайлстра отметил, что макрос DEFINE_SEMAPHORE(), объявляющий и инициализирующий статический семафор, устанавливает его исходное значение в единицу, то есть, по умолчанию создаётся двоичный семафор. Поскольку, как он сказал, двоичные семафоры представляют собой «специальный случай», лучше было бы предусмотреть такую возможность: пусть DEFINE_SEMAPHORE() принимает дополнительный аргумент, указывающий, каково должно быть исходное значение. Торвальдс согласился с целесообразностью такого изменения. «Давайте просто признаем, что сегодня семафоры стоит использовать, только если это семафоры со счётчиками, и обеспечим, чтобы DEFINE_SEMAPHORE() принимал это число». По его словам, семафоры сегодня — «уже почти целиком перешли в категорию унаследованного кода». С тех пор Зайлстра уже опубликовал соответствующий патч.
Вероятно, это небольшое изменение, внесённое в API семафоров, затронет немногих разработчиков. Однако остаётся открытым вопрос: что же делать с теми десятками двоичных семафоров, которые до сих пор используются. Было бы здорово преобразовать их в мьютексы: и производительность бы улучшилась, и код выглядел бы для нынешних разработчиков привычнее. Но, как отметил Сергей Сеножатский, невозможно просто механически переделать их все, не присмотревшись к каждому. Например, двоичный семафор сохранился в коде printk(), так как mutex_unlock() нельзя вызывать из контекста прерывания, а up() — можно.
Это лишний раз демонстрирует, что в ядре, как и где угодно, старый код может сохраняться очень подолгу. Пожалуй, двоичные семафоры можно считать старомодными с 2006 года, но во многих контекстах они продолжают применяться, и пришлось дождаться 2023 года, чтобы инициализатор поменяли так, чтобы он не создавал двоичный семафор по умолчанию. Разработчики ядра приходят и уходят, но код ядра, по крайней мере иногда, оказывается гораздо более живучим.