diff options
Diffstat (limited to 'documentation/content/ru/books/arch-handbook/smp/_index.adoc')
| -rw-r--r-- | documentation/content/ru/books/arch-handbook/smp/_index.adoc | 360 |
1 files changed, 360 insertions, 0 deletions
diff --git a/documentation/content/ru/books/arch-handbook/smp/_index.adoc b/documentation/content/ru/books/arch-handbook/smp/_index.adoc new file mode 100644 index 0000000000..8c4b741566 --- /dev/null +++ b/documentation/content/ru/books/arch-handbook/smp/_index.adoc @@ -0,0 +1,360 @@ +--- +description: 'Документ по архитектуре SMPng' +next: books/arch-handbook/partii +params: + path: /books/arch-handbook/smp/ +prev: books/arch-handbook/vm +showBookMenu: true +tags: ["SMPng", "introduction", "locks"] +title: 'Глава 8. Документ по архитектуре SMPng' +weight: 9 +--- + +[[smp]] += Документ по архитектуре SMPng +:doctype: book +:toc: macro +:toclevels: 1 +:icons: font +:sectnums: +:sectnumlevels: 6 +:sectnumoffset: 8 +:partnums: +:source-highlighter: rouge +:experimental: +:images-path: books/arch-handbook/ + +ifdef::env-beastie[] +ifdef::backend-html5[] +:imagesdir: ../../../../images/{images-path} +endif::[] +ifndef::book[] +include::shared/authors.adoc[] +include::shared/mirrors.adoc[] +include::shared/releases.adoc[] +include::shared/attributes/attributes-{{% lang %}}.adoc[] +include::shared/{{% lang %}}/teams.adoc[] +include::shared/{{% lang %}}/mailing-lists.adoc[] +include::shared/{{% lang %}}/urls.adoc[] +toc::[] +endif::[] +ifdef::backend-pdf,backend-epub3[] +include::../../../../../shared/asciidoctor.adoc[] +endif::[] +endif::[] + +ifndef::env-beastie[] +toc::[] +include::../../../../../shared/asciidoctor.adoc[] +endif::[] + +[[smp-intro]] +== Введение + +В этом документе представлены текущая архитектура и реализация SMPng. Сначала вводятся основные примитивы и инструменты. Затем излагается общая архитектура модели синхронизации и выполнения ядра FreeBSD. Далее обсуждаются стратегии блокировок для конкретных подсистем, описывающие подходы к внедрению детализированной синхронизации и параллелизма для каждой подсистемы. В заключение приводятся подробные заметки по реализации, объясняющие выбор проектных решений и информирующие читателя о важных последствиях использования конкретных примитивов. + +Этот документ находится в стадии разработки и будет обновляться в соответствии с текущими проектированием и реализацией, связанными с проектом SMPng. Многие разделы в настоящее время существуют только в виде набросков, но будут дополняться по мере продвижения работы. Обновления или предложения по документу могут быть направлены редакторам документа. + +Цель SMPng — обеспечить параллелизм в ядре. Ядро представляет собой одну довольно большую и сложную программу. Чтобы сделать ядро многопоточным, мы используем те же инструменты, что и для многопоточности других программ. К ним относятся мьютексы, разделяемые/монопольные блокировки, семафоры и условные переменные. Для определений этих и других терминов, связанных с SMP, см. раздел crossref:smp[smp-glossary, Глоссарий] в этой статье. + +[[smp-lock-fundamentals]] +== Основные инструменты и основы блокировки + +=== Атомарные инструкции и барьеры памяти + +Можно найти много описаний барьеров памяти и атомарных инструкций, поэтому в этом разделе не будет много деталей. Проще говоря, нельзя читать переменные без блокировки, если блокировка используется для защиты записи в эту переменную. Это становится очевидным, если учесть, что барьеры памяти лишь определяют относительный порядок операций с памятью; они не дают никаких гарантий относительно времени выполнения этих операций. То есть, барьер памяти не принуждает к сбросу содержимого локального кэша или буфера записи процессора. Вместо этого, барьер памяти при освобождении блокировки просто гарантирует, что все записи в защищённые данные будут видны другим процессорам или устройствам, если видна запись, освобождающая блокировку. Процессор может хранить эти данные в своём кэше или буфере записи сколько угодно долго. Однако, если другой процессор выполняет атомарную инструкцию над тем же данным, первый процессор должен гарантировать, что обновлённое значение будет видно второму процессору, наряду с любыми другими операциями, которые могут потребоваться согласно барьерам памяти. + +Например, предполагая простую модель, в которой данные считаются видимыми, когда они находятся в основной памяти (или в глобальном кэше), когда начинается выполнение атомарной инструкции на одном процессоре, буферы записи и кэши других процессоров должны выполнить все записи в ту же строку кэша вместе с любыми ожидающими операциями за барьером памяти. + +Это требует особой осторожности при использовании элемента, защищённого атомарными инструкциями. Например, в реализации мьютекса сна мы должны использовать `atomic_cmpset` вместо `atomic_set` для установки бита `MTX_CONTESTED`. Причина в том, что мы считываем значение `mtx_lock` в переменную и затем принимаем решение на основе этого чтения. Однако значение, которое мы ранее прочитали, может быть устаревшим или измениться, пока мы принимаем решение. Таким образом, когда выполняется `atomic_set`, это может привести к установке бита на другом значении, отличном от того, на котором мы основывали своё решение. Поэтому мы должны использовать `atomic_cmpset`, чтобы установить значение только в том случае, если значение, на котором мы приняли решение, актуально и действительно. + +Наконец, атомарные инструкции позволяют обновить или прочитать только один элемент. Если необходимо атомарно обновить несколько элементов, вместо этого следует использовать блокировку. Например, если требуется прочитать два счётчика и получить их значения, согласованные друг с другом, то эти счётчики должны быть защищены блокировкой, а не отдельными атомарными инструкциями. + +=== Блокировки на чтение и блокировки на запись + +Блокировки на чтение не требуют такой же строгости, как блокировки на запись. Оба типа блокировок должны гарантировать, что данные, к которым они обращаются, не устарели. Однако запись требует монопольного доступа. Несколько потоков могут безопасно читать значение. Использование разных типов блокировок для чтения и записи может быть реализовано несколькими способами. + +Во-первых, блокировки sx могут использоваться таким образом: монопольная блокировка при записи и разделяемая блокировка при чтении. Этот метод достаточно прост. + +Второй метод несколько менее очевиден. Вы можете защитить данные несколькими блокировками. Для чтения данных достаточно получить блокировку на чтение одной из блокировок. Однако для записи данных необходимо получить блокировку на запись всех блокировок. Это может сделать запись довольно затратной, но может быть полезно, когда данные доступны различными способами. Например, указатель на родительский процесс защищён как `proctree_lock` sx-блокировкой, так и мьютексом процесса. Иногда блокировка процесса удобнее, так как мы просто проверяем, кто является родителем уже заблокированного процесса. Однако в других случаях, таких как `inferior`, необходимо обходить дерево процессов через указатели на родителя, и блокировка каждого процесса была бы слишком затратной, а также сложной для гарантии того, что проверяемое условие остаётся верным как во время проверки, так и при выполнении действий, основанных на этой проверке. + +=== Условия и результаты блокировки + +Если вам нужна блокировка для проверки состояния переменной, чтобы можно было выполнить действие на основе прочитанного состояния, вы не можете просто удерживать блокировку во время чтения переменной, а затем снять блокировку перед выполнением действия на основе прочитанного значения. Как только вы снимаете блокировку, переменная может измениться, что сделает ваше решение недействительным. Таким образом, вы должны удерживать блокировку как во время чтения переменной, так и во время выполнения действия в результате проверки. + +[[smp-design]] +== Общая Архитектура и Дизайн + +=== Обработка прерываний + +Следуя примеру нескольких других многопоточных ядер UNIX(R), FreeBSD реализрвала обработчики прерываний, предоставив им собственный контекст потока. Предоставление контекста для обработчиков прерываний позволяет им блокироваться на блокировках. Однако, чтобы избежать задержек, потоки обработки прерываний выполняются с приоритетом реального времени в ядре. Таким образом, обработчики прерываний не должны выполняться слишком долго, чтобы не лишать ресурсов другие потоки ядра. Кроме того, поскольку несколько обработчиков могут использовать один поток прерываний, обработчики прерываний не должны переходить в режим сна или использовать блокировки, допускающие сон, чтобы не лишать ресурсов другие обработчики прерываний. + +Текущие потоки обработки прерываний в FreeBSD называются тяжеловесными потоками обработки прерываний. Они получили такое название, потому что переключение на поток обработки прерывания включает в себя полное переключение контекста. В первоначальной реализации ядро не было вытесняющим, поэтому прерывания, которые прерывали поток ядра, должны были ждать, пока поток ядра не заблокируется или не вернётся в пользовательское пространство, прежде чем у них появится возможность выполниться. + +Для решения проблем с задержками ядро FreeBSD стало вытесняющим. В настоящее время вытеснение потока ядра происходит только при освобождении мьютекса сна или при поступлении прерывания. Однако планируется сделать ядро FreeBSD полностью вытесняющим, как описано ниже. + +Не все обработчики прерываний выполняются в контексте потока. Вместо этого, некоторые обработчики выполняются непосредственно в основном контексте прерывания. Эти обработчики прерываний в настоящее время ошибочно называются "быстрыми" обработчиками прерываний, поскольку для их обозначения применяется флаг `INTR_FAST`, использовавшийся в более ранних версиях ядра. Единственные прерывания, которые в настоящее время используют такие обработчики прерываний, — это прерывания от часов и последовательных устройств ввода-вывода. Поскольку эти обработчики не имеют собственного контекста, они не могут захватывать блокирующие блокировки и, следовательно, могут использовать только спин-мьютексы. + +Наконец, существует одна дополнительная оптимизация, которую можно добавить в код MD, называемая легковесными переключениями контекста. Поскольку поток обработки прерывания выполняется в контексте ядра, он может заимствовать vmspace любого процесса. Таким образом, при легковесном переключении контекста переход к потоку обработки прерывания не меняет vmspace, а заимствует vmspace прерванного потока. Чтобы гарантировать, что vmspace прерванного потока не исчезнет во время работы, прерванному потоку запрещается выполнение до тех пор, пока поток обработки прерывания больше не использует его vmspace. Это может произойти, когда поток обработки прерывания либо блокируется, либо завершается. Если поток обработки прерывания блокируется, то при повторном запуске он будет использовать свой собственный контекст. Таким образом, он может освободить прерванный поток. + +Недостатки этой оптимизации заключаются в том, что они очень специфичны для конкретной машины и сложны, поэтому стоят усилий только в случае значительного улучшения производительности. На данный момент, вероятно, ещё рано делать выводы, и, фактически, это может даже ухудшить производительность, так как почти все обработчики прерываний будут немедленно блокироваться на Giant и потребуют исправления потока при блокировке. Кроме того, Майк Смит предложил альтернативный метод обработки прерываний, который работает следующим образом: + +. Каждый обработчик прерывания состоит из двух частей: предиката, который выполняется в основном контексте прерывания, и обработчика, который выполняется в контексте собственного потока. +. Если у обработчика прерывания есть предикат, то при срабатывании прерывания этот предикат выполняется. Если предикат возвращает значение `true`, прерывание считается полностью обработанным, и ядро возвращается из прерывания. Если предикат возвращает `false` или предиката нет, то запланированный обработчик запускается. + +Встраивание легковесных переключений контекста в эту схему может оказаться довольно сложным. Поскольку мы, возможно, захотим перейти на эту схему в будущем, вероятно, лучше отложить работу над легковесными переключениями контекста до тех пор, пока мы не определимся с окончательной архитектурой обработки прерываний и не выясним, как легковесные переключения контекста могут (или не могут) в неё вписаться. + +=== Ядро с вытеснением и критические секции + +==== Ядро и вытеснение вкратце + +Вытеснение ядра довольно просто. Основная идея заключается в том, что процессор всегда должен выполнять наиболее приоритетную доступную работу. Ну, это в идеале, по крайней мере. Есть несколько случаев, когда затраты на достижение идеала не стоят совершенства. + +Реализация полной вытесняющей многозадачности в ядре очень проста: когда вы планируете выполнение потока, помещая его в очередь выполнения, вы проверяете, является ли его приоритет выше, чем у текущего выполняемого потока. Если да, вы инициируете переключение контекста на этот поток. + +Хотя блокировки могут защитить большинство данных в случае вытеснения, не все части ядра безопасны для вытеснения. Например, если поток, удерживающий спин-блокировку, будет вытеснен, а новый поток попытается захватить ту же спин-блокировку, новый поток может вращаться вечно, так как прерванный поток может никогда не получить шанс на выполнение. Кроме того, некоторый код, такой как код для назначения номера адресного пространства процессу во время `exec` на Alpha, не должен быть вытеснен, так как он поддерживает фактический код переключения контекста. Для таких участков кода вытеснение отключается с использованием критической секции. + +==== Критические Секции + +Ответственность API критической секции заключается в предотвращении переключения контекста внутри критической секции. В полностью вытесняющем ядре каждый вызов `setrunqueue` для потока, отличного от текущего, является точкой вытеснения. Одна из реализаций заключается в том, что `critical_enter` устанавливает флаг для каждого потока, который сбрасывается его парной функцией. Если `setrunqueue` вызывается, когда этот флаг установлен, вытеснение не происходит, независимо от приоритета нового потока относительно текущего. Однако, поскольку критические секции используются в спин-блокировках для предотвращения переключения контекста и может быть захвачено несколько спин-блокировок, API критической секции должен поддерживать вложенность. По этой причине текущая реализация использует счетчик вложенности вместо одиночного флага для каждого потока. + +Для минимизации задержек прерывания внутри критической секции откладываются, а не отбрасываются. Если поток, который в обычных условиях должен быть вытеснен, становится готовым к выполнению, пока текущий поток находится в критической секции, то устанавливается флаг для данного потока, указывающий на ожидающее прерывание. При выходе из самой внешней критической секции флаг проверяется. Если флаг установлен, текущий поток вытесняется, чтобы позволить выполниться потоку с более высоким приоритетом. + +Прерывания создают проблему для спин-мьютексов. Если обработчик низкоуровневого прерывания требует блокировки, он не должен прерывать любой код, которому нужна эта блокировка, чтобы избежать возможного повреждения структур данных. В настоящее время этот механизм реализован через API критических секций с помощью функций `cpu_critical_enter` и `cpu_critical_exit`. Сейчас этот API отключает и снова включает прерывания на всех текущих платформах FreeBSD. Такой подход может быть не идеально оптимальным, но он прост для понимания и надежен в реализации. Теоретически, этот второй API нужен только для спин-мьютексов, используемых в основном контексте прерываний. Однако, для упрощения кода, он используется для всех спин-мьютексов и даже для всех критических секций. Возможно, стоит отделить MD API от MI API и использовать его только совместно с MI API в реализации спин-мьютексов. Если будет принят такой подход, то MD API, вероятно, потребуется переименовать, чтобы показать, что это отдельный API. + +==== Компромиссы проектирования + +Как упоминалось ранее, были сделаны некоторые компромиссы, чтобы пожертвовать случаями, когда идеальная вытесняющая многозадачность не всегда обеспечивает наилучшую производительность. + +Первый компромисс заключается в том, что код вытеснения не учитывает другие процессоры. Предположим, у нас есть два процессора A и B, где приоритет потока A равен 4, а приоритет потока B равен 2. Если процессор B делает поток с приоритетом 1 готовым к выполнению, то теоретически мы хотим, чтобы процессор A переключился на новый поток, чтобы выполнялись два потока с наивысшим приоритетом. Однако стоимость определения, на какой процессор нужно применить вытеснение, а также фактическая сигнализация этому процессору через IPI вместе с необходимой синхронизацией были бы огромными. Таким образом, текущий код вместо этого заставит процессор B переключиться на поток с более высоким приоритетом. Заметим, что это всё равно улучшает состояние системы, так как процессор B выполняет поток с приоритетом 1, а не поток с приоритетом 2. + +Второй компромисс ограничивает немедленное вытеснение ядра только потоками ядра с реальным временем. В простом случае вытеснения, описанном выше, поток всегда вытесняется немедленно (или как только будет покинута критическая секция), если становится доступным поток с более высоким приоритетом. Однако многие потоки, выполняющиеся в ядре, работают в контексте ядра лишь короткое время перед тем, как либо заблокироваться, либо вернуться в пользовательское пространство. Таким образом, если ядро вытеснит эти потоки для выполнения другого потока ядра без реального времени, оно может переключиться с выполняемого потока как раз перед тем, как тот собирается завершиться или перейти в режим ожидания. Кэш процессора должен затем адаптироваться к новому потоку. Когда ядро возвращается к вытесненному потоку, оно должно восстановить все потерянные кэшированные данные. Кроме того, выполняются два дополнительных переключения контекста, которых можно было бы избежать, если бы ядро отложило вытеснение до момента, пока первый поток не заблокируется или не вернётся в пользовательское пространство. Таким образом, по умолчанию код вытеснения будет немедленно вытеснять поток только в том случае, если поток с более высоким приоритетом имеет приоритет реального времени. + +Включение полной вытесняющей многозадачности для всех потоков ядра полезно в качестве средства отладки, так как позволяет выявить больше состояний гонки. Это особенно полезно на однопроцессорных системах (UP), где многие гонки сложно воспроизвести другими способами. Таким образом, существует опция ядра `FULL_PREEMPTION` для включения вытеснения для всех потоков ядра, которая может использоваться для целей отладки. + +=== Миграция потоков + +Простыми словами, поток мигрирует, когда переходит с одного CPU на другой. В неперемещаемом ядре это может происходить только в определённых точках, например, при вызове `msleep` или возврате в пользовательское пространство. Однако в перемещаемом ядре прерывание может вызвать вытеснение и возможную миграцию в любой момент. Это может негативно сказаться на данных, специфичных для CPU, поскольку, за исключением `curthread` и `curpcb`, данные могут изменяться при любой миграции. Поскольку потенциально миграция может произойти в любой момент, это делает незащищённый доступ к данным, специфичным для CPU, практически бесполезным. Поэтому желательно иметь возможность отключать миграцию для участков кода, где требуется стабильность данных, специфичных для CPU. + +Критические секции в настоящее время предотвращают миграцию, поскольку они не допускают переключения контекстов. Однако это может быть слишком строгим требованием в некоторых случаях, так как критическая секция также эффективно блокирует потоки прерываний на текущем процессоре. В результате был предоставлен другой API, позволяющий текущему потоку указать, что если он будет вытеснен, он не должен мигрировать на другой CPU. + +Этот API известен как закрепление потока и предоставляется планировщиком. API состоит из двух функций: `sched_pin` и `sched_unpin`. Эти функции управляют счетчиком вложенности `td_pinned` для каждого потока. Поток считается закрепленным, когда его счетчик вложенности больше нуля, и прекрашает быть закрепленным с нулевым счетчиком вложенности. Каждая реализация планировщика должна гарантировать, что закрепленные потоки выполняются только на том CPU, на котором они выполнялись при первом вызове `sched_pin`. Поскольку счетчик вложенности изменяется только самим потоком и читается другими потоками только тогда, когда закрепленный поток не выполняется, но удерживается `sched_lock`, то `td_pinned` не требует блокировки. Функция `sched_pin` увеличивает счетчик вложенности, а `sched_unpin` уменьшает его. Обратите внимание, что эти функции работают только с текущим потоком и привязывают текущий поток к CPU, на котором он выполняется в данный момент. Для привязки произвольного потока к определенному CPU следует использовать функции `sched_bind` и `sched_unbind`. + +=== Обратные вызовы + +Функция ядра `timeout` позволяет службам ядра регистрировать функции для выполнения в рамках программного прерывания `softclock`. События планируются на основе заданного количества тактов часов, и вызовы предоставленной потребителем функции будут происходить приблизительно в нужное время. + +Глобальный список ожидающих событий с таймаутом защищен глобальной спин-блокировкой `callout_lock`; любой доступ к списку таймаутов должен выполняться с удержанием этой блокировки. Когда `softclock` пробуждается, он сканирует список ожидающих таймаутов на предмет тех, которые должны сработать. Чтобы избежать инверсии блокировок, поток `softclock` освобождает блокировку `callout_lock` при вызове предоставленной функции обратного вызова `timeout`. Если флаг `CALLOUT_MPSAFE` не был установлен во время регистрации, то `Giant` будет захвачен перед вызовом обратного вызова, а затем освобожден после него. Блокировка `callout_lock` будет повторно захвачена перед продолжением работы. Код `softclock` аккуратно поддерживает список в согласованном состоянии во время освобождения блокировки. Если включен `DIAGNOSTIC`, то измеряется время выполнения каждой функции, и если оно превышает пороговое значение, генерируется предупреждение. + +[[smp-lock-strategies]] +== Конкретные стратегии блокировки + +=== Учетные данные + +`struct ucred` — это внутренняя структура учетных данных ядра, которая обычно используется в качестве основы для управления доступом на уровне процессов внутри ядра. Системы, производные от BSD, используют модель «копирования при записи» для учетных данных: могут существовать множественные ссылки на структуру учетных данных, и когда требуется внести изменение, структура дублируется, изменяется, а затем ссылка заменяется. Благодаря широко распространенному кэшированию учетных данных для реализации контроля доступа при открытии, это приводит к значительной экономии памяти. С переходом на детализированную SMP (симметричную многопроцессорность), эта модель также существенно экономит на операциях блокировки, требуя, чтобы модификации выполнялись только для неразделяемых учетных данных, избегая необходимости явной синхронизации при использовании известных разделяемых учетных данных. + +Структуры учетных данных с единственной ссылкой считаются изменяемыми; разделяемые структуры учетных данных не должны изменяться, иначе возникает риск состояния гонки. Мьютекс `cr_mtxp` защищает счетчик ссылок структуры `struct ucred` для поддержания согласованности. Любое использование структуры требует действительной ссылки на протяжении всего времени использования, иначе структура может быть освобождена из-под нелегитимного потребителя. + +Мьютекс `struct ucred` является листовым мьютексом и реализован через пул мьютексов по соображениям производительности. + +Обычно учетные данные используются в режиме только для чтения для принятия решений по контролю доступа, и в этом случае `td_ucred`, как правило, предпочтительнее, поскольку не требует блокировки. Когда учетные данные процесса обновляются, блокировка `proc` должна удерживаться на протяжении операций проверки и обновления, чтобы избежать состояний гонки. Учетные данные процесса `p_ucred` должны использоваться для операций проверки и обновления, чтобы предотвратить гонки между временем проверки и временем использования. + +Если при системных вызовах будет выполняться контроль доступа после обновления учетных данных процесса, значение `td_ucred` также должно быть обновлено до текущего значения процесса. Это предотвратит использование устаревших учетных данных после изменения. Ядро автоматически обновляет указатель `td_ucred` в структуре потока из `p_ucred` процесса всякий раз, когда процесс входит в ядро, что позволяет использовать свежие учетные данные для контроля доступа в ядре. + +=== Дескрипторы файлов и таблицы дескрипторов файлов + +Подробности будут позже. + +=== Структуры клеток + +`struct prison` хранит административные данные, связанные с обслуживанием клеток, созданных с использованием API man:jail[2]. Это включает имя хоста для каждой клетки, IP-адрес и связанные настройки. Эта структура имеет счетчик ссылок, так как указатели на её экземпляры разделяются многими структурами учётных данных. Один мьютекс, `pr_mtx`, защищает чтение и запись счётчика ссылок и всех изменяемых переменных внутри `struct jail`. Некоторые переменные устанавливаются только при создании клетки, и действительной ссылки на `struct prison` достаточно для чтения этих значений. Точная блокировка каждой записи документирована в комментариях файла [.filename]#sys/jail.h#. + +=== MAC Framework + +Фреймворк TrustedBSD MAC поддерживает данные в различных объектах ядра в виде `struct label`. Как правило, метки в объектах ядра защищаются тем же механизмом блокировки, что и остальная часть объекта ядра. Например, метка `v_label` в `struct vnode` защищается блокировкой vnode. + +В дополнение к меткам, поддерживаемым в стандартных объектах ядра, MAC Framework также поддерживает список зарегистрированных и активных политик. Список политик защищен глобальной мьютекс-блокировкой (`mac_policy_list_lock`) и счетчиком использования (также защищенным мьютексом). Поскольку множество проверок контроля доступа может выполняться параллельно, вход в framework для доступа только на чтение к списку политик требует удержания мьютекса во время увеличения (и последующего уменьшения) счетчика использования. Мьютекс не обязательно удерживать на протяжении всей операции входа в MAC — некоторые операции, такие как операции с метками на объектах файловой системы, выполняются длительное время. Для изменения списка политик, например во время регистрации и отмены регистрации политик, мьютекс должен быть удержан, а счетчик ссылок должен быть равен нулю, чтобы предотвратить изменение списка во время его использования. + +Условная переменная `mac_policy_list_not_busy` доступна для потоков, которым необходимо дождаться освобождения списка, но ожидание на этой условной переменной допустимо только если вызывающий поток не удерживает других блокировок, иначе может возникнуть нарушение порядка блокировок. Фактически, счетчик занятости действует как форма разделяемой/исключающей блокировки доступа к фреймворку: отличие в том, что, в отличие от sx-блокировки, потребители, ожидающие освобождения списка, могут подвергаться голоданию, вместо того чтобы допускать проблемы порядка блокировок в отношении счетчика занятости и других блокировок, которые могут удерживаться при входе в (или внутри) MAC Framework. + +=== Модули + +Для подсистемы модулей существует единая блокировка, которая используется для защиты общих данных. Эта блокировка является shared/exclusive (SX) и с высокой вероятностью потребует захвата (разделяемого или исключительного), поэтому были добавлены несколько макросов для упрощения работы с ней. Эти макросы можно найти в [.filename]#sys/module.h#, и их использование довольно простое. Основные структуры, защищаемые этой блокировкой, — это структуры `module_t` (при разделяемом доступе) и глобальная структура `modulelist_t` modules. Для более глубокого понимания стратегии блокировок рекомендуется изучить соответствующий исходный код в [.filename]#kern/kern_module.c#. + +=== Дерево устройств Newbus + +Система newbus будет использовать одну блокировку sx. Читатели будут удерживать разделяемую (read) блокировку (man:sx_slock[9]), а писатели — эксклюзивную (write) блокировку (man:sx_xlock[9]). Внутренние функции не будут выполнять блокировку вообще. Внешне видимые функции будут блокироваться по мере необходимости. Элементы, для которых не важно, выиграна гонка или проиграна, не будут блокироваться, так как они обычно читаются во многих местах (например, man:device_get_softc[9]). Изменения в структурах данных newbus будут относительно редкими, поэтому одной блокировки должно быть достаточно, и это не приведёт к снижению производительности. + +=== Каналы (pipe) + +... + +=== Процессы и потоки + +- иерархия процессов + +- блокировки и ссылки proc + +- потокоспецифичные копии записей proc для заморозки во время системных вызовов, включая td_ucred + +- межпроцессные операции + +- группы процессов и сеансы + +=== Планировщик + +Множество ссылок на `sched_lock` и примечания, указывающие на конкретные примитивы и связанные с ними особенности в других частях документа. + +=== Select и Poll + +Функции `select` и `poll` позволяют потокам блокироваться в ожидании событий на файловых дескрипторах — чаще всего, доступности файловых дескрипторов для чтения или записи. + +... + +=== SIGIO + +Служба SIGIO позволяет процессам запрашивать доставку сигнала SIGIO своей группе процессов при изменении статуса чтения/записи указанных файловых дескрипторов. Не более одного процесса или группы процессов может зарегистрироваться для получения SIGIO от любого заданного объекта ядра, и такой процесс или группа называется владельцем. Каждый объект, поддерживающий регистрацию SIGIO, содержит поле-указатель, которое имеет значение `NULL`, если объект не зарегистрирован, или указывает на структуру `struct sigio`, описывающую регистрацию. Это поле защищено глобальным мьютексом `sigio_lock`. Вызывающие функции обслуживания SIGIO должны передавать это поле «по ссылке», чтобы локальные копии регистра не создавались без защиты блокировкой. + +Один `struct sigio` выделяется для каждого зарегистрированного объекта, связанного с любым процессом или группой процессов, и содержит обратные ссылки на объект, владельца, информацию о сигнале, учетные данные и общее состояние регистрации. Каждый процесс или группа процессов содержит список зарегистрированных структур `struct sigio`: `p_sigiolst` для процессов и `pg_sigiolst` для групп процессов. Эти списки защищены блокировками процесса или группы процессов соответственно. Большинство полей в каждой `struct sigio` остаются постоянными на протяжении регистрации, за исключением поля `sio_pgsigio`, которое связывает `struct sigio` со списком процесса или группы процессов. Разработчикам, реализующим новые объекты ядра с поддержкой SIGIO, как правило, следует избегать удержания блокировок структур при вызове функций поддержки SIGIO, таких как `fsetown` или `funsetown`, чтобы не определять порядок блокировок между блокировками структур и глобальной блокировкой SIGIO. Обычно это возможно за счет использования повышенного счетчика ссылок на структуру, например, путем опоры на ссылку файлового дескриптора на канал во время операции с каналом. + +=== Sysctl + +Сервис `sysctl` MIB вызывается как из ядра, так и из пользовательских приложений с использованием системного вызова. По крайней мере, два вопроса возникают в отношении блокировок: во-первых, защита структур, поддерживающих пространство имен, и во-вторых, взаимодействие с переменными и функциями ядра, к которым обращается интерфейс `sysctl`. Поскольку `sysctl` позволяет прямое экспортирование (и изменение) статистики ядра и параметров конфигурации, механизм `sysctl` должен учитывать соответствующие семантики блокировок для этих переменных. В настоящее время `sysctl` использует единую глобальную sx-блокировку для сериализации использования `sysctl`; однако предполагается, что он работает под защитой Giant, и другие защиты не предоставляются. Оставшаяся часть этого раздела рассматривает возможные изменения в блокировках и семантике `sysctl`. + +- Необходимо изменить порядок операций для sysctl, которые обновляют значения из чтения старого, copyin и copyout, записи нового на copyin, блокировку, чтение старого и запись нового, разблокировку, copyout. Обычные sysctl, которые просто копируют старое значение и устанавливают новое, которое они копируют, могут по-прежнему следовать старой модели. Однако, возможно, будет чище использовать вторую модель для всех обработчиков sysctl, чтобы избежать операций блокировки. + +- Для упрощения распространённого случая, sysctl может включать указатель на мьютекс в макросах SYSCTL_FOO и в структуре. Это будет работать для большинства sysctl. Для значений, защищённых sx-блокировками, спин-мьютексами или другими стратегиями синхронизации, отличными от одиночного мьютекса сна, можно использовать узлы SYSCTL_PROC для обеспечения корректной блокировки. + +=== Очередь задач + +Интерфейс `taskqueue` имеет две основные блокировки, связанные с ним, для защиты соответствующих общих данных. Мьютекс `taskqueue_queues_mutex` предназначен для защиты TAILQ `taskqueue_queues`. Другая блокировка мьютекса, связанная с этой системой, находится в структуре данных `struct taskqueue`. Использование примитива синхронизации здесь необходимо для защиты целостности данных в `struct taskqueue`. Следует отметить, что нет отдельных макросов, помогающих пользователю заблокировать свою собственную работу, поскольку эти блокировки, скорее всего, не будут использоваться за пределами [.filename]#kern/subr_taskqueue.c#. + +[[smp-implementation-notes]] +== Заметки о реализации + +=== Очереди сна + +Очередь сна — это структура, которая содержит список потоков, ожидающих на канале ожидания. Каждый поток, который не находится в состоянии ожидания на канале ожидания, хранит структуру очереди сна при себе. Когда поток блокируется на канале ожидания, он передаёт свою структуру очереди сна этому каналу. Очереди сна, связанные с каналом ожидания, хранятся в хеш-таблице. + +Хеш-таблица очередей сна содержит очереди сна для каналов ожидания, у которых есть хотя бы один заблокированный поток. Каждая запись в хеш-таблице называется цепочкой очереди сна. Цепочка содержит связанный список очередей сна и спин-мьютекс. Спин-мьютекс защищает список очередей сна, а также содержимое структур очередей сна в списке. С каждым каналом ожидания связана только одна очередь сна. Если несколько потоков блокируются на одном канале ожидания, то очереди сна, связанные со всеми потоками, кроме первого, хранятся в списке свободных очередей сна в главной очереди сна. Когда поток удаляется из очереди сна, он получает одну из структур очереди сна из свободного списка главной очереди, если он не является единственным потоком в очереди. Последний поток получает главную очередь сна при возобновлении. Поскольку потоки могут удаляться из очереди сна в порядке, отличном от порядка добавления, поток может покинуть очередь сна с другой структурой очереди сна, чем та, с которой он в неё попал. + +Функция `sleepq_lock` блокирует спин-мьютес цепи очереди сна, соответствующей определённому каналу ожидания. Функция `sleepq_lookup` выполняет поиск в хеш-таблице главной очереди сна, связанной с заданным каналом ожидания. Если главная очередь сна не найдена, функция возвращает `NULL`. Функция `sleepq_release` разблокирует спин-мьютес, связанный с заданным каналом ожидания. + +Поток добавляется в очередь ожидания с помощью `sleepq_add`. Эта функция принимает канал ожидания, указатель на мьютекс, защищающий канал ожидания, строку описания сообщения ожидания и маску флагов. Цепь очереди ожидания должна быть заблокирована с помощью `sleepq_lock` перед вызовом этой функции. Если канал ожидания не защищен мьютексом (или защищен мьютексом Giant), то аргумент указателя на мьютекс должен быть `NULL`. Аргумент флагов содержит поле типа, указывающее на вид очереди ожидания, в которую добавляется поток, и флаг, указывающий, является ли ожидание прерываемым (`SLEEPQ_INTERRUPTIBLE`). В настоящее время существует только два типа очередей ожидания: традиционные очереди, управляемые через функции `msleep` и `wakeup` (`SLEEPQ_MSLEEP`), и очереди ожидания условных переменных (`SLEEPQ_CONDVAR`). Тип очереди ожидания и аргумент указателя на блокировку используются исключительно для внутренних проверок утверждений. Код, вызывающий `sleepq_add`, должен явно разблокировать любой блокировочный механизм, защищающий канал ожидания, после того как связанная цепь очереди ожидания будет заблокирована через `sleepq_lock` и перед блокировкой в очереди ожидания с помощью одной из функций ожидания. + +Таймаут для сна устанавливается вызовом `sleepq_set_timeout`. Функция принимает канал ожидания и время таймаута в виде относительного количества тиков в качестве аргументов. Если сон должен быть прерван поступающими сигналами, следует также вызвать функцию `sleepq_catch_signals`. Эта функция принимает канал ожидания в качестве единственного параметра. Если для данного потока уже есть ожидающий сигнал, то `sleepq_catch_signals` вернёт номер сигнала; в противном случае она вернёт 0. + +После добавления потока в очередь ожидания он блокируется с использованием одной из функций `sleepq_wait`. Существует четыре функции ожидания в зависимости от того, хочет ли вызывающий код использовать таймаут, прерывание сна перехваченными сигналами или прерывание от планировщика потоков пользовательского пространства. Функция `sleepq_wait` просто ожидает, пока текущий поток не будет явно возобновлён одной из функций пробуждения. Функция `sleepq_timedwait` ожидает, пока поток не будет явно возобновлён или пока не истечёт таймаут, установленный предыдущим вызовом `sleepq_set_timeout`. Функция `sleepq_wait_sig` ожидает, пока поток не будет явно возобновлён или его сон не будет прерван. Функция `sleepq_timedwait_sig` ожидает, пока поток не будет явно возобновлён, не истечёт таймаут, установленный предыдущим вызовом `sleepq_set_timeout`, или сон потока не будет прерван. Все функции ожидания принимают канал ожидания в качестве первого параметра. Кроме того, функция `sleepq_timedwait_sig` принимает второй логический параметр, указывающий, обнаружил ли предыдущий вызов `sleepq_catch_signals` ожидающий сигнал. + +Если поток явно возобновлен или прерван сигналом, функция ожидания возвращает ноль, указывая на успешное завершение сна. Если поток возобновлен по таймауту или прерыванию от планировщика потоков в пользовательском пространстве, вместо этого возвращается соответствующее значение errno. Обратите внимание, что поскольку `sleepq_wait` может возвращать только 0, она ничего не возвращает, и вызывающая сторона должна считать сон успешным. Также, если сон потока прерывается одновременно по таймауту и другим причинам, `sleepq_timedwait_sig` вернет ошибку, указывающую на срабатывание таймаута. Если возвращено значение ошибки 0 и для блокировки использовались `sleepq_wait_sig` или `sleepq_timedwait_sig`, следует вызвать функцию `sleepq_calc_signal_retval` для проверки ожидающих сигналов и вычисления соответствующего возвращаемого значения, если таковые обнаружены. Номер сигнала, полученный при предыдущем вызове `sleepq_catch_signals`, должен быть передан в качестве единственного аргумента в `sleepq_calc_signal_retval`. + +Потоки, находящиеся в состоянии ожидания на канале ожидания, явно возобновляются функциями `sleepq_broadcast` и `sleepq_signal`. Обе функции принимают канал ожидания, с которого нужно возобновить потоки, приоритет, на который нужно поднять возобновлённые потоки, и аргумент флагов, указывающий тип очереди ожидания, которую нужно возобновить. Аргумент приоритета трактуется как минимальный приоритет. Если у возобновляемого потока уже есть более высокий приоритет (численно меньший), чем указанный в аргументе, его приоритет не изменяется. Аргумент флагов используется для внутренних проверок, чтобы гарантировать, что очереди ожидания не обрабатываются как неправильный тип. Например, функции условных переменных не должны возобновлять потоки на традиционной очереди ожидания. Функция `sleepq_broadcast` возобновляет все потоки, заблокированные на указанном канале ожидания, тогда как `sleepq_signal` возобновляет только поток с наивысшим приоритетом, заблокированный на канале ожидания. Перед вызовом этих функций цепочка очереди ожидания должна быть заблокирована с помощью функции `sleepq_lock`. + +Спящий поток может быть прерван с помощью вызова функции `sleepq_abort`. Эта функция должна вызываться с удержанием `sched_lock`, а поток должен находиться в очереди сна. Поток также может быть удалён из определённой очереди сна с помощью функции `sleepq_remove`. Эта функция принимает как поток, так и канал ожидания в качестве аргументов и пробуждает поток только в том случае, если он находится в очереди сна для указанного канала ожидания. Если поток не находится в очереди сна или находится в очереди сна для другого канала ожидания, эта функция ничего не делает. + +=== Турникеты + +- Сравнение/сопоставление с очередями сна. + +- Поиск/ожидание/освобождение. - Описать состояние гонки TDF_TSNOBLOCK. + +- Приоритетное распространение. + +=== Подробности реализации мьютекса + +- Должны ли мы требовать владения мьютексами для `mtx_destroy()`, так как иначе мы не можем безопасно утверждать, что они не принадлежат кому-либо ещё? + +==== Вращающиеся мьютексы + +- Использование критической секции... + +==== Мьютексы сна (Sleep Mutexes) + +- Опишите гонки с оспариваемыми мьютексами + +- Почему безопасно читать mtx_lock оспариваемой мьютекса при удержании блокировки цепочки турникета. + +=== Witness + +- Что это делает + +- Как это работает + +[[smp-misc]] +== Разные темы + +=== Источники прерываний и абстракции ICU + +- struct isrc + +- pic драйверы + +=== Другие случайные вопросы/темы + +- Передавать ли блокировку в `sema_wait`? + +- Должны ли мы иметь sx блокировки без возможности сна? + +- Добавить некоторую информацию о правильном использовании счетчиков ссылок. + +:sectnums!: + +[glossary] +[[smp-glossary]] +== Глоссарий + +[.glosslist] +atomic (атомарный):: +Операция является атомарной, если все её эффекты видны другим процессорам одновременно при соблюдении соответствующего протокола доступа. В простейшем случае атомарные инструкции предоставляются непосредственно архитектурой процессора. На более высоком уровне, если несколько элементов структуры защищены блокировкой, то набор операций является атомарным, если все они выполняются при удержании блокировки без её освобождения между любыми из операций. ++ +См. также operation (операция). + +block (блокировать):: +Поток блокируется, когда он ожидает блокировку, ресурс или условие. К сожалению, этот термин в результате немного перегружен. ++ +См. также sleep (спать). + +critical section (критическая секция):: +Фрагмент кода, который не может быть вытеснен. Критическая секция начинается и завершается с использованием API man:critical_enter[9]. + +MD:: +Машинозависимый (machine dependent). ++ +Смотри также MI. + +memory operation (операция с памятью):: +Операция с памятью выполняет чтение и/или запись в ячейку памяти. + +MI:: +Машинно-независимый (machine independent). ++ +См. также MD. + +operation (операция):: +См. memory operation (операция с памятью). + +primary interrupt context (основной контекст прерывания):: +Основной контекст прерывания относится к коду, который выполняется при возникновении прерывания. Этот код может либо напрямую запускать обработчик прерывания, либо планировать выполнение асинхронного потока прерывания для обработчиков прерываний данного источника. + +realtime kernel thread (поток ядра реального времени):: +Высокоприоритетный поток ядра. В настоящее время единственными потоками ядра с реальным приоритетом являются потоки обработки прерываний. ++ +См. также thread (поток). + +sleep (спать):: +Поток находится в состоянии сна, когда он заблокирован на условной переменной или в очереди сна через `msleep` или `tsleep`. ++ +См. также block (блокировать). + +sleepable lock (блокировка с возможностью сна):: +блокировка с возможностью сна — это блокировка, которая может удерживаться потоком, находящимся в состоянии сна. В настоящее время в FreeBSD единственными блокировками с возможностью сна являются lockmgr и sx. В будущем некоторые sx-блокировки, такие как allproc и proctree, могут стать блокировками с возможностью сна. ++ +См. также sleep (спать). + +thread (поток):: +Поток ядра, представленный структурой `struct thread`. Потоки владеют блокировками и содержат единственный на поток контекст выполнения. + +wait channel (канал ожидания):: +Виртуальный адрес ядра, на котором потоки могут переходить в режим ожидания. + +:sectnums: |