Второе издание
 Скачать 3.09 Mb.
|
|
Поток 1 Поток 2 захватить блокировку А захватить блокировку В попытка захватить блокировку В попытка захватить блокировку А ожидание освобождения блокировки В ожидание освобождения блокировки А Оба потока будут ожидать друг друга, и ни один из потоков никогда не освободит первоначально захваченной блокировки, поэтому ни одна из блокировок не будет освобождена. Такая тупиковая ситуация еще называется deadly embrace (буквально. смертельные объятия). Важно не допустить появление взаимоблокировок. Хотя сложно проверить гото- вый код на наличие взаимоблокировок, можно написать код, который не содержит взаимоблокировок. Такую возможность дает соблюдение нескольких простых правил. • Жизненно важным является порядок захвата блокировок. Вложенные блокиров- ки всегда должны захватываться в одном и том же порядке. Это предотвращает взаимоблокировку нескольких потоков (deadly embrace). Порядок захвата блоки- ровок необходимо документировать, чтобы другие тоже могли его соблюдать. 4 Б некоторых ядрах такой тип тупиковой ситуации предотвращается с помощью рекурсивных бло- кировок, которые позволяют одному потоку выполнения захватывать блокировку несколько раз. В операционной системе Linux, к счастью, таких блокировок нет. И это считается хорошим то- ном. Хотя рекурсивные блокировки позволяют избежать проблемы самоблокировок, они приводят к небрежному использованию блокировок. 172 Глава 8 • Необходимо предотвращать зависания. Следует спросить себя: "Всегда ли этот код сможет завершиться'?'''. Если не выполнится какое-либо условие, то не будет ли что-то ожидать вечно? • Не захватывать одну и ту же блокировку дважды. • Сложность в схеме блокировок — верный путь к тупиковым ситуациям, поэто- му при разработке необходимо стремиться к простоте. Первый пункт важный и наименее сложный для выполнения. Если две или бо- лее блокировок захватываются в одном месте, то они всегда должны захватываться в строго определенном порядке. Допустим, у нас есть три блокировки c a t , dog и fox, которые используются для защиты данных с такими же именами. И еще допустим, что у нас есть функция, которая должна работать с этими тремя структурами данных одновременно— например, может копировать данные между ними. Б любом случае, для того чтобы гарантировать безопасность доступа, эти структуры данных необхо- димо защищать блокировками. Если одна функция захватывает эти блокировки в следующем порядке: c a t , dog и в конце fox, то любая другая функция должна захва- тывать эти блокировки (или только некоторые из них) в том же порядке. Например, если захватывать сначала блокировку fox, а потом блокировку dog, то это потен- циальная возможность взаимоблокировки (а значит, ошибки в работе), потому что блокировка dog всегда должна захватываться перед блокировкой fox. И еще раз рас- смотрим пример, как может возникнуть взаимоблокировка. Поток 1 Поток 2 захватить блокировку cat захватить блокировку fox захватить блокировку dog попытка захватить блокировку dog попытка захватить блокировку fox ожидание освобождения блокировки dog ожидание освобождения блокировки fox — Поток 1 ожидает освобождения блокировки fox, которую удерживает поток 2, а поток 2 в это время ожидает освобождения блокировки dog, которую удерживает поток 1. Ни один из потоков никогда не освободит своих блокировок, и, соответ- ственно, оба потока будут ждать вечно — возникает тупиковая ситуация. Если оба по- тока всегда захватывают блокировки в одном и том же порядке, то подобной тупико- вой ситуации возникнуть не может. Если несколько процедур захвата блокировок вложены друг в друга, то должен быть принят определенный порядок захвата. Хорошая практика — всегда использо- вать комментарий сразу перед объявлением блокировки, который указывает на по- рядок захвата. Использовать что-нибудь вроде следующего будет хорошей идеей. /* * cat_lock - всегда захватывать перед блокировкой dog * (и всегда захватывать блокировку dog перед блокировкой fox) */ Следует заметить, что порядок освобождения блокировок не влияет на возможность появления взаимоблокировок, хотя освобождать блокировки в обратном порядке по отношению к их захвату — это хорошая привычка. Очень важно предотвращать взаимоблокировки. В ядре Linux есть некоторые от- ладочные возможности, которые позволяют обнаруживать взаимоблокировки при выполнении кода ядра. Эти возможности будут рассмотрены в следующем разделе. Введение в синхронизацию выполнения кода ядра 173 Конфликт при захвате блокировки и масштабируемость Термин "конфликт при захвате блокировки" (lock contention, или просто contention) используется для описания блокировки, которая в данный момент захвачена и на освобождение которой ожидают другие потоки. Блокировки с высоким уровнем кон- фликтов (highly contended) — это те, на освобождение которых всегда ожидает много потоков. Так как задача блокировок — это сериализация доступа к ресурсу, то не вы- зовет большого удивления тот факт, что блокировки снижают производительность системы. Блокировка с высоким уровнем конфликтов может стать узким местом в системе, быстро уменьшая производительность. Конечно, блокировки необходимы для того, чтобы предотвратить "развал" системы, поэтому решение проблемы высо- кого уровня конфликтов при блокировках также должно обеспечивать необходимую защиту от состояний конкуренции за ресурсы. Масштабируемость (scalability) — это мера того, насколько система может быть рас- ширена. В случае операционных систем, когда говорят о масштабируемости, подраз- умевают большее количество процессов, большее количество процессоров, больший объем памяти. О маштабируемости можно говорить в приложении практически к любому компоненту компьютера, который можно охарактеризовать количественным параметром. В идеале удвоение количества процессоров должно приводить к удвое- нию процессорной производительности системы. Однако на практике, конечно, та- кого не бывает никогда. Масштабируемость операционной системы Linux на большее количество про- цессоров возросла поразительным образом с того времени, когда поддержка много- процессорной обработки была встроена в ядра серии 2.0. В те дни, когда поддержка многопроцессорности в операционной системе Linux только появилась, лишь одно задание могло выполняться в режиме ядра в любой момент времени. В ядрах серии 2.2 это ограничение было снято, так как механизмы блокировок стали более мелко- структурными. В серии 2.4 и выше блокировки стали еще более мелкоструктурными. Сегодня в ядрах серии 2.6 блокировки имеют очень мелкую гранулярность, а мас- штабируемость получается очень хорошей. Структурность (гранулярность, granularity) блокировки— это описание объемов тех данных, которые защищаются блокировкой, например все структуры данных одной подсистемы. С другой стороны, блокировка на уровне очень мелких структур- ных единиц (fine grained), используется для защиты очень маленького объема дан- ных, например одного поля структуры. В реальных ситуациях большинство блоки- ровок попадают между этими крайностями, они используются не для защиты целой подсистемы, но и не для защиты одного поля, а возможно для защиты отдельного экземпляра структуры. Большинство блокировок начинали использоваться на уровне крупных структурных единиц (cource graine), а потом их стали разделять на более мелкие структурные уровни, как только конфликты при захвате этих блокировок становились проблемой. Один из примеров перевода блокировок на более мелкий структурный уровень — это блокировки очередей выполнения планировщика (runqueue), которые рассмо- трены в главе 4, "Планирование выполнения процессов". В ядрах серии 2.4 и более ранних планировщик имел всего одну очередь выполнения (вспомним, что очередь 174 Глава 8 выполнения— это список готовых к выполнению процессов). В серии 2.6 был пред- ложен О(1)-планировтцик, в котором для каждого процессора используется своя очередь пыполнения, каждая очередь имеет свою блокировку. Соответствующие бло- кировки развились из одной глобальной блокировки в несколько отдельных блоки- ровок для каждой очереди, а использование блокировок развилось из глобального блокирования в использование блокировок на отдельных процессорах. Эта оптими- зация очень существенна, так как на больших машинах блокировка очереди выпол- нения имеет очень высокий уровень конфликтов при захвате, что приводит к сери- ализации планирования выполнения процессов. Иными словами, код планировщика выполнял только один процессор системы в любой момент времени, а остальные процессоры — ждали. В общем такое повышение масштабируемости — это очень хорошая вещь, которая позволяет повысить производительность операционной системы Linux на больших и более мощных системах. Чрезмерное увлечение "ростом" масштабируемости мо- жет привести к снижению производительности на небольших многопроцессорных и однопроцессорных машинах, потому что для небольших машин не требуются такие мелкоструктурные блокировки, а им приходится иметь дело с большей сложностью и с большими накладными расходами. Рассмотрим связанный список. Первоначальная схема блокировки обеспечивает одну блокировку на весь список. Со временем эта одна блокировка может стать узким местом на очень большой многопроцессорной машине, на которой очень часто обращаются к связанному списку. Для решения про- блемы одна блокировка может быть разбита на большое количество блокировок — одна блокировка на один элемент списка. Для каждого элемента списка, который необходимо прочитать или записать, необходимо захватывать уникальную блокиров- ку этого элемента. Теперь конфликт при захвате блокировки будет только в случае, когда несколько процессоров обращаются к одному элементу списка. Что делать, если все равно есть высокий уровень конфликтов? Может быть, необходимо исполь- зовать блокировку для каждого поля элемента списка? (Ответ: НЕТ.) Если серьезно, даже когда очень мелко структурированные блокировки хорошо работают на очень больших SMP-машинах, то как они будут работать на двухпроцессорных машинах? Накладные расходы, связанные с дополнительными блокировками, будут напрасны- ми, если на двухпроцессорной машине нет существенных конфликтов при работе с блокировками. Тем не менее масштабируемость— это важный фактор. Важно с самого нача- ла разрабатывать схему блокировок для обеспечения хорошей масштабируемости. Блокировки на уровне крупных структурных единиц могут стать узким местом даже на машинах с небольшим количеством процессоров. Между крупноструктурными и мелкоструктурными блокировками очень тонкая грань. Слишком крупноструктур- ные блокировки приводят к большому уровню конфликтов, а слишком мелкострук- турные — к напрасным накладным расходам, если уровень конфликтов при захвате блокировок не очень высокий. Оба варианта эквивалентны плохой производитель- ности. Необходимо начинать с простого и переходить к сложному только при необ- ходимости. Простота — это ключевой момент. Введение в синхронизацию выполнения кода ядра 175 Блокировки в вашем коде Обеспечение безопасности кода при SMP-обработке — это не то, что можно от- кладывать на потом. Правильная синхронизация, блокировки без тупиковых ситуа- ций, масштабируемость и ясность кода- все это следует учитывать при разработке с самого начала и до самого конца. При написании кода ядра, будь то новый систем- ный вызов или переписывание драйвера устройства, необходимо, прежде всего, по- заботиться об обеспечении защиты данных от конкурентного доступа. Обеспечение достаточной защиты для любого случая — SMP, вытеснение кода ядра и так далее — в результате приведет к гарантии того, что все данные будут за- щищены на любой машине и в любой конфигуратщи. В следующей главе будет рас- сказано о том, как это осуществить. Теперь, когда мы хорошо подкованы в теории параллелизма, синхронизации и блокировок, давайте углубимся в то, какие существуют конкретные инструменты, предоставляемые ядром Linux, для того чтобы гарантировать отсутствие состояний конкуренции и тупиковых ситуаций в коде. 176 Глава 8 9 Средства синхронизации в ядре В предыдущей главе обсуждались источники и решения проблем, связанных с конкуренцией за ресурсы. К счастью, в ядре Linux реализовано большое семей- ство средств синхронизации. В этой главе обсуждаются эти средства, интерфейсы к ним, а также особенности их работы и использования. Эти решения позволяют раз- работчикам писать код, в котором отсутствуют состояния конкуренции за ресурсы. Атомарные операции Атомарные операции (atomic operations) предоставляют инструкции, которые выполняются атомарно, — т.е. не прерываясь. Так же как и атом вначале считался неделимой частицей, атомарные операции являются неделимыми инструкциями. Например, как было показано в предыдущей главе, операция атомарного инкремен- та позволяет считывать из памяти и увеличивать на единицу значение переменной за один неделимый и непрерывный шаг. В отличие от состояния конкуренции за ре- сурс, которая обсуждалась в предыдущей главе, результат выполнения такой опера- ции всегда один и тот же, например, как показано в следующем примере (допустим, что значение переменной i вначале равно 7). Поток 1 Поток 2 инкремент i (7->8) инкремент i (8->9) Результирующее значение 9— правильное. Параллельное выполнение двух атомар- ных операций с одной и той же переменной невозможно никогда. Таким образом, для такой операции инкремента состояние конкуренции за ресурс возникнуть не может. Ядро предоставляет два набора интерфейсов для выполнения атомарных опе- раций: один — для работы с целыми числами, а другой — для работы с отдельными битами. Эти интерфейсы реализованы для всех аппаратных платформ, которые под- держиваются операционной системой Linux. Большинство аппаратных платформ поддерживают атомарные операции или непосредственно, или путем блокировки шины доступа к памяти при выполнении одной операции (что в свою очередь га- рантирует, что другая операция не может выполниться параллельно). Это как-то по- зволяет справиться с проблемой в случае аппаратных платформ, таких как SPARC, которые не поддерживают базовых машинных инструкций для выполнения атомар- ных операций. Целочисленные атомарные операции Средства выполнения атомарных операций с целыми числами работают с типом данных a t o m i c t . Вместо того, чтобы использовать функции, которые работают непосредственно с типом данных i n t языка С, по ряду причин используется спе- циальный тип данных. Во-первых, функции, которые выполняют атомарные опера- ции, принимают только аргументы типа a t o m i c t , это гарантирует, что атомарные операции выполняются только с данными этого специального типа. В то же время это также гарантирует, что данные этого типа не смогут передаваться в другие функ- ции, которые не выполняют атомарных операций. Действительно, ничего хорошего не будет от таких атомарных операций, которые иногда атомарные, а иногда— нет. Следующий момент— использование типа atomic_t позволяет гарантировать, что компилятор (по ошибке, но для повышения эффективности) не будет оптимизи- ровать операции обращения к атомарным переменным. Важно, чтобы атомарные операции получали правильное значение адреса переменной в памяти, а не адреса временных копий. И наконец, за типом a t o m i c t скрываются различия между реа- лизациями для различных аппаратных платформ. Кроме того, что тип atomic_t — это 32-разрядное целое число на всех машинах,- которые поддерживаются операционной системой Linux, при разработке кода не- обходимо учитывать, что максимальный диапазон значений переменной этого типа не может быть больше 24 бит. Это связано с аппаратной платформой SPARC, для которой используется несколько странная реализация атомарных операций: в млад- шие 8 бит 32-разрядного целого числа типа i n t встроена блокировка, как показано па рис. 9.1. 32-разрядный тип atomic_t (Бит) 31 7 О Рис. 9.1, Структура 32-битового типа atomic_t для аппа- ратной платформы SPARC в старой реализации Блокировка используется для предотвращения параллельного доступа к перемен- ной атомарного типа, так как для аппаратной платформы SPARC отсутствует соот- ветствующая поддержка на уровне машинных инструкций. Следовательно, на маши- нах SPARC могут быть использованы только 24 бит. Хотя код, который рассчитан на использование полного 32-битового диапазона значений, будет работать и на маши- нах других типов, он может приводить к странным и коварным ошибкам на машинах типа SPARC, и так делать не нужно. В последнее время умные хакеры додумались, как для аппаратной платформы SPARC обеспечить тип atomic_t, который позволя- 178 Глава 9 24-битовое знаковое целое Блокировка ет хранить полноценное 32-разрядное целое число, и указанного ограничения боль- ше не существует. Тем не менее старая 24-битовая реализация все еще используется в старом коде для аппаратной платформы SPARC, и этот код все еще имеется в файле Объявления всего, что необходимо для использования целочисленных атомарных операций, находятся в заголовочном файле Объявление переменных типа a t o m i c _ t производится обычным образом. При необходимости можно установить заданное значение этой переменной. . atomic_t u; /* определение переменной и */ atomic_t v = ATOMIC_INIT(0); /* определение переменной v и инициализация ее в значение нуль */ Выполнять операции так же просто. atomic_set(&v, 4 ) ; /* v = 4 (атомарно) */ atomic_add(2, &v) ; / * v = v + 2 = 6 (атомарно) */ atomic_inc(&v); / * v = v + l = 7 (атомарно) */ Если необходимо конвертировать тип a t o m i c _ t в тип i n t , то нужно использо- вать функцию a t o m i c _ r e a d ( ) . printk("%d\n", atomic_read(&v)); /* будет напечатано "7" */ Наиболее частое использование атомарных целочисленных операций — это инкремент счетчиков. Защищать один счетчик с помощью сложной системы бло- кировок — это глупо, поэтому разработчики используют вызовы a t o m i c _ i n t () и atomic_dec (), которые значительно быстрее. Еще одно использование атомарных целочисленных операций — это атомарное выполнение операции с проверкой ре- зультата. Наиболее распространенный пример — это атомарные декремент и про- верка результата, с помощью функции int atomic_dec_and_test(atomic_t *v) Эта функция уменьшает на единицу значение заданной переменной атомарного типа. Если результат выполнения операции равен нулю, то возвращается значение t r u e , иначе возвращается f a l s e . Полный список всех атомарных операций с целы- ми числами (т.е. тех, которые доступны для всех аппаратных платформ) приведен в табл. 9.1. Все операции, которые реализованы для определенной аппаратной плат- формы, приведены в файле Обычно атомарные операции реализованы как функции с подстановкой тела и встраиваемыми инструкциями на языке ассемблера (разработчики ядра любят i n l i n e ) . В случае если какая-либо из функций обладает внутренней атомарнос- тью, то обычно она выполняется в виде макроса. Например, для большинства нор- мальных аппаратных платформ считывание одного машинного слова данных — это атомарная операция. Операция считывания всегда возвращает машинное слово в непротиворечивом состоянии или перед операцией записи, или после нее, но во Средства синхронизации в ядре 179 |