| netlib.narod.ru | < Назад | Оглавление | Далее > |
В главе 9 были описаны основные понятия семафоров и показано их применение для межпроцессного взаимодействия. В ядре предусмотрены собственные реализации семафоров для его собственных целей, и эти конструкции обычно называют «семафорами ядра». (В настоящей главе под словом «семафор» без пояснительных слов следует понимать «семафор ядра».) Точно такое же основное определение семафора, которое было приведено в главе 9, применяется и к семафорам ядра: семафор должен допустить к ресурсу максимально возможное число пользователей (равное числу ключей, первоначально размещенных на гвозде перед входной дверью) и установить правило, что каждый претендент на ресурс должен взять ключ перед переходом к использованию ресурса.
Теперь вы, наверное, представляете себе, как можно построить семафоры с применением либо проверки и установки, для двоичных («одноключевых») семафоров, либо с применением такой функция, как atomic_dec_and_test, для счетных семафоров. Именно это и применяется в ядре: в нем семафоры представлены целыми числами, а функции down (строка 11644) и up (строка 11714), в числе прочих, служат для уменьшения и увеличения этого целого. Как будет вскоре показано, основополагающий код уменьшения и увеличения значений целочисленных переменных аналогичен тому, который применяется в atomic_dec_and_test и подобных функциях.
В качестве исторической справки отметим, что впервые понятие семафора формализовал голландский ученый Эдсгер Дийкстра (Edsger Dijkstra), поэтому фундаментальные операции над семафорами названы по-голландски — Proberen и Verhogen, которые обычно сокращенно обозначают Р и V. Эти слова переводятся как «проверка» (что означает проверку того, доступен ли ключ и взятие его, если да) и «приращение» (возвращение ключа снова на гвоздь). Эти первые буквы стали источником терминов «procure» (приобрести) и «vacate» (освободить), которые были введены в предыдущей главе. Однако в ядре Linux эта традиция нарушена и соответствующие операции получили названия down и up.
В ядре для представления семафоров используется очень простой тип: struct semaphore, который определен в строке 11609. Он имеет только три члена:
count. Отслеживает число все еще доступных ключей. Если он равен 0, ключ взят; если он отрицателен, ключ взят и его возврата ждут другие претенденты. Кстати, отметим, что число дополнительных претендентов равно абсолютному значению величины count, если она равна 0 или отрицательна.
Макрокоманда sema_init (строка 11637) позволяет инициализировать count с установкой в любое значение, поэтому семафоры ядра могут быть двоичными (если величина count инициализирована значением 1) или счетными (если предусмотрено какое-то другое положительное начальное значение). Весь код семафора ядра полностью поддерживает и двоичные, и счетные семафоры, и первый тип семафора является просто особым случаем последнего. Однако на практике величина count всегда инициализируется значением 1, поэтому семафоры ядра всегда являются двоичными. Тем не менее, ничто не препятствует применению разработчиками счетных семафоров в будущем.
Кстати, нет ничего магического в том, что в работе с семафором в качестве первоначального значения count используется положительное число и его уменьшение служит в качестве сигнала о том, что нужен семафор. Можно также использовать отрицательное (или нулевое) первоначальное значение count и предусмотреть увеличение или придерживаться какой-то иной схемы. Просто применение положительного числа принято для семафоров ядра, и оказалось, что оно прекрасно сочетается с абстрактной моделью ключей на гвозде. И действительно, как будет показано ниже, блокировка ядра организована полностью иным образом; в ней соответствующие переменные первоначально принимают отрицательное значение и увеличиваются, когда процессы хотят приобрести эти блокировки.
11644: Операция down уменьшает величину count семафора. Можно было надеяться, что ее реализация будет столь же элементарной, как и само это понятие, но увы, жизнь не настолько проста.
11648: Уменьшение величины count семафора, которое в симметричной мультипроцессорной системе происходит с учетом необходимости атомарного выполнения этой операции. В симметричной мультипроцессорной системе (и, безусловно, в однопроцессорной системе), по существу, выполняется то же, что и в функции atomic_dec_and_test, за исключением того, что доступ к целому числу осуществляется в объекте другого типа.
У читателя может возникнуть вопрос: может ли произойти антипереполнение величины count? He может: процесс после уменьшения величины count всегда переходит в состояние ожидания, поэтому каждый конкретный процесс может захватить одновременно только один семафор, и в запасе есть еще намного больше отрицательных значений величины типа int по сравнению с числом процессов.
11652: Если знаковый разряд установлен, семафор отрицателен. Это значит, что значение count было равным 0 или отрицательным непосредственно перед тем, как было уменьшено, поэтому процесс не сумел получить семафор и должен перейти в состояние ожидания до тех пор, пока семафор не станет доступным. Реализация этого потребовала применения в следующих нескольких строках многих хитростей. Команда js выполняет переход, если знаковый разряд установлен (то есть, если результат команды decl был отрицателен), и 2f обозначает цель перехода. Здесь 2f — не шестнадцатиричное значение, а специальный синтаксис ассемблера GNU: 2 означает переход к локальному символу «2», a f — поиск этого символа впереди. (2b означало бы поиск самого последнего локального символа «2» сзади.) Этот локальный символ находится в строке 11655.
11653: Ветвление не выполнено, поэтому процесс получил семафор. Это фактически конец функции down, несмотря на то, что он так не выглядит. Это вскоре станет ясно.
11654: Одной из самых сложных для понимания частей функции down является директива .section, находящаяся непосредственно перед адресатом перехода, которая указывает, что следующий код нужно собрать в отдельной секции ядра: в секции под названием .text.lock. Данная секция будет размещаться в памяти и рассматриваться как выполнимая программа. Это указано флажком ах — строкой, которая следует за именем секции; обратите внимание, что этот флажок ах не имеет ничего общего с регистром АХ процессора х86. В результате ассемблер перемещает команды в строках 11655 и 11656 из секции down, в которой они находятся, в другую секцию выполнимого кода ядра, поэтому объектный код, вырабатываемый на основе этих строк, не является физически смежным с кодом, вырабатываемом на основе предыдущих строк. Вот почему строка 11653 представляет собой конец функции down.
11655: Это адресат перехода, достигаемый, если нельзя было получить семафор. Команда pushl $1b (ее можно также записать и без знака $) не помещает в стек шестнадцатиричное значение 1b — это была бы команда pushl S0x1b. Вместо этого, данное значение 1b представляет собой тот же синтаксис ассемблера GNU, с которым мы ранее встретились в случае применения 2f: он указывает на адрес команды, в данном случае — на адрес первой локальной метки «1», которая встретится при поиске в обратном направлении. Таким образом, эта команда помещает в стек адрес строки 11653; данный адрес станет адресом возврата, чтобы после последующего перехода ход выполнения вернулся к концу функции down.
11656: Переход отсюда к функции __down_failed (не включена в эту книгу). Эта функция сохраняет несколько регистров в стеке и вызывает функцию __down (строка 26932), которая будет описана ниже, для выполнения работы по ожиданию семафора. После возврата из функции __down функция __down_failed возвращается к down, которая также выполняет возврат. Функция __down не выполняет возврат до тех пор, пока процесс не приобретет семафор; в результате, когда бы ни произошел возврат из функции down, процесс имеет семафор, независимо от того, получил ли он его немедленно или должен был ждать.
11657: Назначение директивы ассемблера .previous не описано в документации, но она должна означать возвращение к предыдущей секции и прекращение действия директивы .section в строке 11654.
11664: Функция down_interruptible применяется, когда процесс желает приобрести семафор, но оставить за собой возможность прервать ожидание после поступления какого-либо сигнала. Реализация этой функции очень напоминает функцию down, но имеет два отличия, которые описаны в следующих двух абзацах.
11666: Первым отличием является то, что функция down_interruptible возвращает значение типа int для указания того, получила ли она семафор или была остановлена каким-то сигналом. Возвращаемое значение (которое представлено переменной result) равно 0 в первом случае и отрицательно — в последнем. Это частично выполняется в строке 11675, где переменная result обнуляется, если функция приобрела семафор без ожидания.
11679: Вторым отличием является то, что функция down_interruptible переходит на функцию __down_failed_interruptible (не включена в эту книгу), а не на функцию __down_failed. Следуя принципам, применяемым в функции __down_failed, __down_failed_interruptible просто корректирует несколько регистров и вызывает функцию __down_interruptible (строка 26942), которая будет описана ниже. Отметим, что адрес возврата, установленный для функции __down_failed_interruptible, строка 11676, следует за командой xorl, которая обнуляет переменную result в том случае, если семафор был приобретен сразу же. Возвращаемое значение функции __down_interruptible будет скопировано в переменную result.
11687: Функция down_trylock аналогична функции down_interruptible, за исключением того, что в ней предусмотрен вызов __down_failed_trylock (которая вызывает функцию __down_trylock, строка 26961, описанную ниже). Поэтому здесь нет необходимости рассматривать функцию down_trylock.
26900: Это первая из трех макрокоманд, где размещен некоторый код, общий для функций __down и __down_interruptible. В ней просто объявлено несколько переменных.
26904: Эта макрокоманда просто переводит задачу tsk (которая была объявлена в макрокоманде DOWN_VAR) в состояние, указанное параметром task_state, а затем добавляет tsk к очереди заданий, ждущих семафора. И наконец, она начинает бесконечный цикл; размещенные в цикле функции __down и __down_interruptible прервут этот цикл, когда будут готовы выйти.
26926: Эта макрокоманда начинается со связанной с окончанием цикла по переводу задачи tsk снова в состояние task_state в ходе подготовки к повторной попытке захватить семафор.
26929: Произошел выход из этого цикла; задача tsk либо приобрела семафор, либо была прервана каким-то сигналом (только в функции __down_interruptible). Так или иначе, задача готова продолжить выполнение и больше не ждет семафора, поэтому она снова переводится в состояние TASK_RUNNING и извлекается из очереди ожидания семафора.
26932: Функции __down и __down_interruptible организованы следующим образом:
Ниже рассмотрены только этапы, специфические для каждой функции (этапы 3 и 6).
26936: В теле цикла в функции __down происходит вызов функции waking_non_zero (не рассматривается), которая атомарно проверяет значение sem->waking для определения того, был ли процесс активизирован. Если да, она обнуляет значение waking и возвращает 1 (все это продолжает оставаться частью одной и той же атомарной операции); если нет, она возвращает 0. Поэтому возвращаемое ею значение указывает, захватил ли процесс семафор. Если он его захватил, происходит выход из цикла и функция выполняет возврат. В ином случае, процесс продолжает ждать. Кстати отметим, что функция __down пытается захватить семафор перед вызовом функции schedule. Почему бы не поступить иначе, если известно, что величина count семафора является отрицательной? Это не имело бы значения для любых итераций цикла, кроме первой, но удаление ненужной проверки может лишь немного ускорить первую итерацию. Если для этого есть какие-то конкретные причины, то вполне вероятно, что семафор мог бы быть освобожден (возможно, другим процессором) через несколько микросекунд после первой его проверки, и стоимость лишнего захвата флажка намного меньше стоимости дополнительного перепланирования. Поэтому функция __down могла бы также выполнить одну последнюю быструю проверку перед перепланированием.
26942: Функция __down_interruptible, по существу, аналогична функции __down, за исключением того, что она разрешает прерывания по сигналу.
26948: Следовательно, функция waking_non_zero_interruptible (не рассматривается) вызывается при захвате семафора. Она возвращает 0, если ей не удалось захватить семафор, возвращает 1, если она его получила, или –EINTR, если она была прервана каким-то сигналом. В первом случае цикл продолжается.
26958: В ином случае, функция __down_interruptible выходит, возвращая 0 (а не 1), если она получила семафор, или –EINTR, если была прервана.
26961: Иногда, если семафор нельзя было получить немедленно, ядро просто должно продолжить работу. Следовательно, функция __down_trylock не остается в цикле. Она просто вызывает функцию waking_nonzero_trylock (не рассматривается), которая захватывает семафор и, если это не удается, наращивает величину count семафора (поскольку ядро больше не собирается ждать его освобождения) и выполняет возврат.
11714: Мы подробно рассмотрели, что происходит, когда ядро пытается приобрести семафор, а также что происходит, когда это не удается. Теперь настало время рассмотреть другую сторону этого уравнения: что происходит при освобождении семафора. Эта часть сравнительно проста.
11721: Атомарное увеличение значения count семафора.
11722: Если результат — меньше или равен 0, какой-то процесс ждет активизации. Функция up переходит вперед к строке 11725.
11724: В функции up применяется такой же прием, как и в функции down: все последующие действия выполняются в отдельной секции ядра, а не в самой функции up. Адрес конца функции up помещается в стек и функция up переходит к функции __up_wakeup (не рассматривается). Она выполняет такие же манипуляции с регистрами, как и в функции __down_failed, и вызывает функцию __up, которая рассматривается ниже.
26877: Функция __up отвечает за активизацию всех процессов, ждущих данный семафор.
26879: Вызов функции wake_one_more (не рассматривается в этой книге), которая проверяет, не ждут ли какие-то процессы данный семафор и, если да, увеличивает значение члена waking, чтобы подать им сигнал, что они могут попытаться захватить семафор.
26880: Используется макрокоманда wake_up (строка 16612), которая просто вызывает функцию __wake_up (строка 26829) для активизации всех ждущих процессов.
26829: Как описано в главе 2, функция __wake_up активизирует все процессы в переданной ей очереди ожиданий, если они находятся в одном из состояний, предусмотренных параметром mode. При вызове из функции wake_up она активизирует все, что находится в состояниях TASK_UNINTERRUPTIBLE или TASK_INTERRUPTIBLE; при вызове из функции wake_up_interruptible (строка 16614), она активизирует только задачи, находящиеся в состоянии TASK_INTERRUPTIBLE.
26842: Процессы активизированы функцией wake_up_process (строка 26356), которая была кратко описана выше и будет рассмотрена более подробно далее в этой главе.
Сейчас для нас представляют интерес последовательности активизации всех процессов. Поскольку функция __wake_up активизирует все процессы, поставленные в очередь, а не только первый в очереди, все они конкурируют за семафор, поэтому в случае симметричной мультипроцессорной системы они могут претендовать на него буквально одновременно. Как правило, победителем будет тот, кто первым получил процессор. Это будет процесс с наилучшим значением адекватности (вспомните описание goodness, строка 26388, в главе 7). Это имеет смысл, поскольку процессы с более высоким значением goodness должны иметь приоритет при выполнении их работы. (Это может быть особенно важно для процессов в реальном масштабе времени.)
Недостатком этого подхода является риск перевода на голодный паек, который возникает, когда процесс постоянно лишается возможности получить ресурс, необходимый ему для продолжения работы. Здесь перевод на голодный паек может произойти, если два процесса, постоянно конкурирующие за один и тот же семафор, всегда находятся в таких условиях, когда первый процесс имеет более высокое значение goodness, чем второй. Второй процесс никогда не получит процессор. Этот сценарий не так уж маловероятен, как кажется: предположим, что один из них является процессом, работающим в реальном масштабе времени, а другой работает со значением nice (увеличение которого равносильно уменьшению приоритета), равным 20. Мы можем избежать риска перевода на голодный паек, всегда пробуждая только первый процесс в очереди, но это иногда было бы равносильно отказу в предоставлении процессора процессам, которые во всех иных отношениях в большей степени заслуживают его получения.
Этот вопрос до сих пор еще не рассматривался, но планировщик Linux может также полностью лишить процесс доступа к процессору при определенных обстоятельствах. Это не обязательно непредвиденное развитие событий, а лишь результат применения определенного проектного решения, и, по крайней мере, результат неуклонного применения конкретного принципа во всем коде ядра, что само по себе неплохо. Отметим также, что перевод на голодный паек может с таким же успехом возникать при использовании других описанных выше механизмов. Например, примитив проверки и установки так же может явиться потенциальной причиной перевода на голодный паек, как и семафор ядра.
Во всяком случае, на практике перевод на голодный паек возникает редко, поэтому представляет собой интересный теоретический случай.
| netlib.narod.ru | < Назад | Оглавление | Далее > |