Семафоры в Linux медленно сходят со сцены
С годами подходы к обработке конкурентности в ядре 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 года, чтобы инициализатор поменяли так, чтобы он не создавал двоичный семафор по умолчанию. Разработчики ядра приходят и уходят, но код ядра, по крайней мере иногда, оказывается гораздо более живучим.
sem_overview(7) — Linux man page
A semaphore is an integer whose value is never allowed to fall below zero. Two operations can be performed on semaphores: increment the semaphore value by one (sem_post(3)); and decrement the semaphore value by one (sem_wait(3)). If the value of a semaphore is currently zero, then a sem_wait(3) operation will block until the value becomes greater than zero.
POSIX semaphores come in two forms: named semaphores and unnamed semaphores. Named semaphores A named semaphore is identified by a name of the form /somename; that is, a null-terminated string of up to NAME_MAX-4 (i.e., 251) characters consisting of an initial slash, followed by one or more characters, none of which are slashes. Two processes can operate on the same named semaphore by passing the same name to sem_open(3).
The sem_open(3) function creates a new named semaphore or opens an existing named semaphore. After the semaphore has been opened, it can be operated on using sem_post(3) and sem_wait(3). When a process has finished using the semaphore, it can use sem_close(3) to close the semaphore. When all processes have finished using the semaphore, it can be removed from the system using sem_unlink(3). Unnamed semaphores (memory-based semaphores) An unnamed semaphore does not have a name. Instead the semaphore is placed in a region of memory that is shared between multiple threads (a thread-shared semaphore) or processes (a process-shared semaphore). A thread-shared semaphore is placed in an area of memory shared between the threads of a process, for example, a global variable. A process-shared semaphore must be placed in a shared memory region (e.g., a System V shared memory segment created using shmget(2), or a POSIX shared memory object built created using shm_open(3)).
Before being used, an unnamed semaphore must be initialized using sem_init(3). It can then be operated on using sem_post(3) and sem_wait(3). When the semaphore is no longer required, and before the memory in which it is located is deallocated, the semaphore should be destroyed using sem_destroy(3).
The remainder of this section describes some specific details of the Linux implementation of POSIX semaphores.
Versions
Prior to kernel 2.6, Linux only supported unnamed, thread-shared semaphores. On a system with Linux 2.6 and a glibc that provides the NPTL threading implementation, a complete implementation of POSIX semaphores is provided.
Persistence
POSIX named semaphores have kernel persistence: if not removed by sem_unlink(3), a semaphore will exist until the system is shut down.
Linking
Programs using the POSIX semaphores API must be compiled with cc -pthread to link against the real-time library, librt.
Accessing named semaphores via the file system
On Linux, named semaphores are created in a virtual file system, normally mounted under /dev/shm, with names of the form sem.somename. (This is the reason that semaphore names are limited to NAME_MAX-4 rather than NAME_MAX characters.)
Since Linux 2.6.19, ACLs can be placed on files under this directory, to control object permissions on a per-user and per-group basis.
Conforming to
Notes
System V semaphores (semget(2), semop(2), etc.) are an older semaphore API. POSIX semaphores provide a simpler, and better designed interface than System V semaphores; on the other hand POSIX semaphores are less widely available (especially on older systems) than System V semaphores.