Привздохнув, произнесла:
«Как же долго я спала!»
Когда-то, впервые встретив Unix, я был очарован логической стройностью и завершенностью системы. Несколько лет после этого я яростно изучал устройство ядра и системные вызовы, читая все что удавалось достать. Понемногу мое увлечение сошло на нет, нашлись более насущные дела и вот, начиная с какого-то времени, я стал обнаруживать то одну то другую фичу про которые я раньше не знал. Процесс естественный, однако слишком часто такие казусы обьединяет одно — отсутствие авторитетного источника документации. Часто ответ находится в виде третьего сверху комментария на stackoverflow, часто приходится сводить вместе два-три источника чтобы получить ответ на именно тот вопрос который задавал. Я хочу привести здесь небольшую коллекцию таких плохо документированных особенностей. Ни одна из них не нова, некоторые даже очень не новы, но на каждую я убил в свое время несколько часов и часто до сих пор не знаю систематического описания.
Все примеры относятся к Linux, хотя многие из них справедливы для других *nix систем, я просто взял за основу самую активно развивающуюся ОС, к тому же ту, которая у меня перед глазами и где я могу быстро проверить предлагаемый код.
Обратите внимание, в заголовке я написал «плохо документированные» а не «малоизвестные», поэтому тех кто в курсе прошу выкладывать в комментариях ссылки на членораздельную документацию, я с удовольствием добавлю в конце список.
Возвращается ли освобожденная память обратно в ОС?
Этот вопрос, заданный вполне мною уважаемым коллегой, послужил спусковым крючком для этой публикации. Целых полчаса после этого я смешивал его с грязью и обзывал сравнительными эпитетами, обьясняя что еще классики учили — память в Unix выделяется через системный вызов sbrk(), который просто увеличивает верхний лимит доступных адресов; выделяется обычно большими кусками; что конечно технически возможно понизить лимит и вернуть память в ОС для других процессов, однако для аллокатора очень накладно отслеживать все используемые и неиспользуемые фрагменты, поэтому возвращение памяти не предусмотрено by design. Этот классический механизм прекрасно работает в большинстве случаев, исключение — сервер часами/месяцами тихо сидящий без дела, вдруг запрашивающий много страниц для обработки какого-то события и снова тихо засыпающий (но в этом случае выручает своп). После чего, удовлетворив свое ЧСВ, я как честный человек пошел подтвердить в интернетах свое мнение и с удивлением обнаружил, что Linux начиная с 2.4 может использовать как sbrk() так и mmap() для выделения памяти, в зависимости от запрошенного размера. Причем память аллоцированная через mmap() вполне себе возвращается в ОС после вызова free()/delete. После такого удара мне оставалось только одно два — смиренно извиниться и выяснить чему же точно равен этот таинственный предел. Поскольку никакой информации так и не нашел, пришлось мерить руками. Оказалось, на моей системе (3.13.0) — всего 120 байт. Код линейки для желающих перемерить — здесь.
Каков минимальный интервал который процесс/поток может проспать?
Тот же самый Морис Бах учил: планировщик (scheduler) процессов в ядре активируется по любому прерыванию; получив управление, планировщик проходит по списку спящих процессов и переводит те из них которые проснулись (получили запрошенные данные из файла или сокета, истек интервал sleep() и т.д.) в список «ready to run», после чего выходит из прерывания обратно в текущий процесс. Когда происходит прерывание системного таймера, которое случалось когда-то раз в 100 мс, потом, по увеличении скорости CPU, раз в 10 мс, планировщик ставит текущий процесс в конец списка «ready to run» и запускает первый процесс из начала этого списка. Таким образом, если я вызвал sleep(0) или вообще заснул на мгновение по любому поводу, так что мой процесс был переставлен из списка «ready to run» в список «preempted», у него нет никаких шансов заработать снова раньше чем через 10 мс, даже если он вообще один в системе. В принципе, ядро можно перестроить уменьшив этот интервал, однако это вызывает неоправданно большие расходы CPU, так что это не выход. Это хорошо известное ограничение долгие годы отравляло жизнь разработчикам быстро-реагирующих систем, именно оно в значительной степени стимулировало разработку real-time systems и неблокирующих (lockfree) алгоритмов.
И вот как-то я повторил этот эксперимент (меня на самом деле интересовали более тонкие моменты типа распределения вероятностей) и вдруг увидел что процесс просыпается после sleep(0) через 40 mks, в 250 раз быстрее. То же самое после вызовов yield(), std::mutex::lock() и всех прочих блокирующих вызовов. Что же происходит?!
Поиск довольно быстро привел к Completely Fair Scheduler введенному начиная с 2.6.23, однако я долго не мог понять как именно этот механизм приводит к такому быстрому переключению. Как я выяснил в конце-концов, отличие заключается именно в самом алгоритме default scheduler class, того под которым запускаются все процессы по умолчанию. В отличие от классической реализации, в этой каждый работающий процесс/поток имеет динамический приоритет, так что у работающего процесса приоритет постепенно понижается относительно других ожидающих исполнения. Таким образом, планировщик может принять решение о запуске другого процесса немедленно, не ожидая окончания фиксированного интервала, а сам алгоритм перебора процессов теперь О(1), существенно легче и может выполнятся чаще.
Это изменение ведет к удивительно далеко идущим последствиям, фактически зазор между real-time и обычной системой почти исчез, предлагаемая задержка в 40 микросекунд реально достаточно мала для большинства прикладных задач, то же самое можно сказать про неблокирующие алгоритмы — классические блокирующие структуры данных на мьютексах стали очень даже конкурентноспособны.
А что такое вообще эти классы планировщика (scheduling policies)?
Эта тема более-менее описана, повторятся не буду, и тем не менее, откроем одну и вторую авторитетные книги на соответствующей странице и сравним между собой. Налицо почти дословное в некоторых местах повторение друг друга, а так же некоторые расхождения с тем что говорит man -s2 sched_setscheduler. Однако симптом.
Давайте тогда просто немножко поиграемся с кодом. Я создаю несколько потоков с разными приоритетами, подвешиваю их всех на мьютекс и всех разом бужу. Ожидаю я естественно что просыпаться они будут в строгом соответствии со своим приоритетом:
iBolit# ./sche -d0 -i0 -b0 -f1 -r2 -f3 -i0 -i0 -i0 -d0
6 SCHED_FIFO[3]
5 SCHED_RR[2]
4 SCHED_FIFO[1]
1 SCHED_OTHER[0]
2 SCHED_IDLE[0]
3 SCHED_BATCH[0]
7 SCHED_IDLE[0]
8 SCHED_IDLE[0]
9 SCHED_IDLE[0]
10 SCHED_OTHER[0]
Число в начале строки показывает порядок в котором потоки создавались. Как видим два приоритетных класса SCHED_FIFO и SCHED_RR всегда имеют приоритет перед тремя обычными классами SCHED_OTHER, SCHED_BATCH и SCHED_IDLE, и между собой ранжируются строго по приоритету, то что и требовалось. Но вот например то, что все три юзер-класса на старте равноправны вообще нигде не упомянуто, даже SCHED_IDLE, который намного поражен в правах по сравнению с дефолтным SCHED_OTHER, запускается вперед него если стоит в очереди на мьютексе первым. Ну по крайней мере в целом все работает, а вот
Для тех кто хочет сам пограться с приоритетами и классами, исходный код там же.
Задержанные TCP пакеты
Если предыдущие примеры можно считать приятным сюрпризом, то вот этот вот приятным назвать трудно.
История началась несколько лет назад когда мы вдруг обнаружили что один из наших серверов, посылающий клиентам непрерывный поток данных, испытывает периодические задержки в 40 милисекунд. Это случалось нечасто, однако позволить себе такую роскошь мы не могли, поэтому был исполнен ритуальный танец со сниффером и последующим анализом. Внимание, при обсуждении в интернете эту проблему как правило связывают с алгоритмом Нагла (Nagle algorithm), неверно, по нашим результатам проблема возникает на Linux при взаимодействии delayed ACK и slow start. Давайте вспомним другого классика, Ричарда Стивенса, чтобы освежить память.
delayed ACK — это алгоритм задерживающий отправку ACK на полученный пакет на несколько десятков милисекунд в расчете что немедленно будет послан ответный пакет и ACK можно будет встроить в него с очевидной целью — уменьшить трафик пустых датаграм по сети. Этот механизм работает в интерактивной TCP сессии и в 1994 году, когда вышла TCP/IP Illustrated, был уже стандартной частью TCP/IP стека. Что важно для понимания дальнейшего, задержка может быть прервана в частности прибытием следующего пакета данных, в этом случае кумулятивный ACK на обе датаграммы отправляется немедленно.
slow start — не менее старый алгоритм призванный защитить промежуточные маршрутизаторы от чересчур агрессивного источника. Посылающая сторона в начале сессии может послать только один пакет и должна дождаться ACK от получателя, после этого может послать два, четыре и т.д., пока не упрется в другие механизмы регулирования. Этот механизм очевидно работает в случае обьемного трафика и, что существенно, он включается в начале сессии и после каждой вынужденной ретрансляции потерянной датаграммы.
TCP сессии можно разделить на два больших класса — интерактивные (типа telnet) и обьемные (bulk traffic, типа ftp). Легко заметить что требования к регулирующим трафик алгоритмам в этих случаях часто противоположны, в частности требования «задержать ACK» и «дождаться ACK» очевидно противоречат друг другу. В случае стабильной TCP сессии спасает условие упомянутое выше — получение следующего пакета прерывает задержку и ACK на оба сегмента высылается не дожидаясь попутного пакета с данными. Однако, если вдруг один из пакетов теряется, посылающая сторона немедленно инициирует slow start — посылает одну датаграмму и ждет ответа, принимающая сторона получает одну датаграмму и задерживает ACK, поскольку данные в ответ не посылаются, весь обмен подвисает на 40 мс. Voilà.
Эффект возникает именно в Linux — Linux TCP соединениях, в других системах я такого не видел, похоже что-то у них в реализации. И как с этим бороться? Ну, в принципе Linux предлагает (нестандартную) опцию TCP_QUICKACK, которая отключает delayed ACK, однако опция эта нестойкая, отключается автоматически, так что взводить флажок приходится перед каждым read()/write(). Есть еще /proc/sys/net/ipv4, в частности /proc/sys/net/ipv4/tcp_low_latency, но вот делает ли она то что я подозреваю она должна делать — неизвестно. Кроме того этот флажок будет относиться ко всем TCP соединениям на данной машине, нехорошо.
Какие будут предложения?
Из тьмы веков
И напоследок, самый первый казус в истории Linux, просто для полноты картины.
С самого начала в Linux присутствовал нестандартный системный вызов — clone(). Он работает так же как и fork(), то есть создает копию текущего процесса, но при этом адресное пространство остается в совместном пользовании. Нетрудно догадаться для чего он был придуман и действительно, это изящное решение сразу выдвинуло Linux в первые ряды среди ОС по реализации многопоточности. Однако всегда есть один нюанс…
Дело в том что при клонировании процесса также клонируются все файловые дескрипторы, в том числе и сокеты. Если раньше была отработанная схема: открывается сокет, передается в другие потоки, все дружно сотрудничают посылая и получая данные, один из потоков решает закрыть сокет, все другие сразу видят что сокет закрылся, на другом конце соединения (в случае TCP) тоже видят что сокет закрыт; то что получается теперь? Если один из потоков решает закрыть свой сокет, другие потоки об этом ничего не знают, поскольку они на самом деле отдельные процессы и у них свои собственные копии этого сокета, и продолжают работать. Более того, другой конец соединения тоже считает соединение открытым. Дело прошлое, но когда-то это нововведение поломало паттерн многим сетевым программистам, да и кода пришлось переписать под Linux изрядно.
Литература
- Maurice J. Bach. The Design of the UNIX Operating System.
- Robert Love. Linux Kernel Development
- Daniel P. Bovet, Marco Cesati. Understanding the Linux Kernel
- Richard Stevens. TCP/IP Illustrated, Volume 1: The Protocols
- Richard Stevens. Unix Network Programming
- Richard Stevens. Advanced Programming in the UNIX Environment
- Uresh Vahalia. UNIX Internals: The New Frontiers
Здесь могла бы быть ваша ссылка на затронутые темы
А еще мне действительно интересно, сколько же все таки я проспал и насколько отстал от жизни. Позвольте включить небольшой опрос.
Автор: degs
