Привздохнув, произнесла:
«Как же долго я спала!»
![image](https://habrastorage.org/files/ddd/a95/15b/ddda9515b1e9414f8baf11fc782a688e.jpeg)
Все примеры относятся к Linux, хотя многие из них справедливы для других *nix систем, я просто взял за основу самую активно развивающуюся ОС, к тому же ту, которая у меня перед глазами и где я могу быстро проверить предлагаемый код.
Обратите внимание, в заголовке я написал «плохо документированные» а не «малоизвестные», поэтому тех кто в курсе прошу выкладывать в комментариях ссылки на членораздельную документацию, я с удовольствием добавлю в конце список.
Возвращается ли освобожденная память обратно в ОС?
Этот вопрос, заданный вполне мною уважаемым коллегой, послужил спусковым крючком для этой публикации. Целых полчаса после этого я смешивал его с грязью и обзывал сравнительными эпитетами, обьясняя что еще классики учили — память в Unix выделяется через системный вызов sbrk(), который просто увеличивает верхний лимит доступных адресов; выделяется обычно большими кусками; что конечно технически возможно понизить лимит и вернуть память в ОС для других процессов, однако для аллокатора очень накладно отслеживать все используемые и неиспользуемые фрагменты, поэтому возвращение памяти не предусмотрено by design. Этот классический механизм прекрасно работает в большинстве случаев, исключение — сервер часами/месяцами тихо сидящий без дела, вдруг запрашивающий много страниц для обработки какого-то события и снова тихо засыпающий (но в этом случае выручает своп). После чего, удовлетворив свое ЧСВ, я
Каков минимальный интервал который процесс/поток может проспать?
Тот же самый Морис Бах учил: планировщик (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 мкс, в 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, запускается вперед него если стоит в очереди на мьютексе первым. Ну по крайней мере в целом все работает, а вот
у Solaris в этом месте вообще дырка
Несколько лет назад я прогнал этот тест под Solaris и обнаружил что приоритеты потоков полностью игнорируются, потоки пробуждаются в совершенно произвольном порядке. Я тогда связался с тех.поддержкой Sun, но получил на удивление невнятный и бессодержательный ответ (до этого они охотно с нами сотрудничали). Через две недели Sun не стало. Я искренне надеюсь что не мой запрос послужил этому причиной.
Для тех кто хочет сам пограться с приоритетами и классами, исходный код там же.
Задержанные 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
Здесь могла бы быть ваша ссылка на затронутые темы
Первые ласточки:
- @Sov1et: TCP/IP Architecture, Design and Implementation in Linux есть в списке free e-books. Перевода не нашел
- По рекомендации a5b добавляю ссылкы на man'ы. Полезная фича: есть группировка по проектам. Для любителей учиться по man'ам.
А еще мне действительно интересно, сколько же все таки я проспал и насколько отстал от жизни. Позвольте включить небольшой опрос.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Насколько малоизвестны затронутые вопросы?
2.4% Все тривиально и общеизвестно, именно так все и должно работать.28
2.23% В принципе все известно, но это все действительно отклонения от классического Unix26
53.64% Узнал что-то новое. Интересно626
19.54% Никогда ничего подобного не слышал228
9.85% Использую высокоуровневые библиотеки и фреймворки. Такие проблемы никогда не возникают115
1.2% На каком языке это написано? Используйте <....> и проблем не будет14
11.14% Что такое Linux?130
Проголосовали 1167 пользователей. Воздержались 370 пользователей.