Разработка ядра Linux - Роберт Лав

• Не захватывать одну и ту же блокировку дважды.

• Сложность в схеме блокировок — верный путь к тупиковым ситуациям, поэтому при разработке необходимо стремиться к простоте.

Первый пункт важный и наименее сложный для выполнения. Если две или более блокировок захватываются в одном месте, то они всегда должны захватываться в строго определенном порядке. Допустим, у нас есть три блокировки cat, dog и fox, которые используются для защиты данных с такими же именами. И еще допустим, что у нас есть функция, которая должна работать с этими тремя структурами данных одновременно— например, может копировать данные между ними. В любом случае, для того чтобы гарантировать безопасность доступа, эти структуры данных необходимо защищать блокировками. Если одна функция захватывает эти блокировки в следующем порядке: cat, 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 есть некоторые отладочные возможности, которые позволяют обнаруживать взаимоблокировки при выполнении кода ядра. Эти возможности будут рассмотрены в следующем разделе.

Конфликт при захвате блокировки и масштабируемость

Термин "конфликт при захвате блокировки" (lock contention, или просто contention) используется для описания блокировки, которая в данный момент захвачена и на освобождение которой ожидают другие потоки. Блокировки с высоким уровнем конфликтов (highly contended) — это те, на освобождение которых всегда ожидает много потоков. Так как задача блокировок — это сериализация доступа к ресурсу, то не вызовет большого удивления тот факт, что блокировки снижают производительность системы. Блокировка с высоким уровнем конфликтов может стать узким местом в системе, быстро уменьшая производительность. Конечно, блокировки необходимы для того, чтобы предотвратить "развал" системы, поэтому решение проблемы высокого уровня конфликтов при блокировках также должно обеспечивать необходимую защиту от состояний конкуренции за ресурсы.

Масштабируемость (scalability) — это мера того, насколько система может быть расширена. В случае операционных систем, когда говорят о масштабируемости, подразумевают большее количество процессов, большее количество процессоров, больший объем памяти. О маштабируемости можно говорить в приложении практически к любому компоненту компьютера, который можно охарактеризовать количественным параметром. В идеале удвоение количества процессоров должно приводить к удвоению процессорной производительности системы. Однако на практике, конечно, такого не бывает никогда.

Масштабируемость операционной системы Linux на большее количество процессоров возросла поразительным образом с того времени, когда поддержка многопроцессорной обработки была встроена в ядра серии 2.0. В те дни, когда поддержка многопроцессорности в операционной системе Linux только появилась, лишь одно задание могло выполняться в режиме ядра в любой момент времени. В ядрах серии 2.2 это ограничение было снято, так как механизмы блокировок стали более мелкоструктурными. В серии 2.4 и выше блокировки стали еще более мелкоструктурными. Сегодня в ядрах серии 2.6 блокировки имеют очень мелкую гранулярность, а масштабируемость получается очень хорошей.

Структурность (гранулярность, granularity) блокировки — это описание объемов тех данных, которые защищаются блокировкой, например все структуры данных одной подсистемы. С другой стороны, блокировка на уровне очень мелких структурных единиц (fine grained), используется для защиты очень маленького объема данных, например одного поля структуры. В реальных ситуациях большинство блокировок попадают между этими крайностями, они используются не для защиты целой подсистемы, но и не для защиты одного поля, а возможно для защиты отдельного экземпляра структуры. Большинство блокировок начинали использоваться на уровне крупных структурных единиц (coarse grained), а потом их стали разделять на более мелкие структурные уровни, как только конфликты при захвате этих блокировок становились проблемой.

Один из примеров перевода блокировок на более мелкий структурный уровень — это блокировки очередей выполнения планировщика (runqueue), которые рассмотрены в главе 4, "Планирование выполнения процессов". В ядрах серии 2.4 и более ранних планировщик имел всего одну очередь выполнения (вспомним, что очередь выполнения— это список готовых к выполнению процессов). В серии 2.6 был предложен O(1)-планировщик, в котором для каждого процессора используется своя очередь выполнения, каждая очередь имеет свою блокировку. Соответствующие блокировки развились из одной глобальной блокировки в несколько отдельных блокировок для каждой очереди, а использование блокировок развилось из глобального блокирования в использование блокировок на отдельных процессорах. Эта оптимизация очень существенна, так как на больших машинах блокировка очереди выполнения имеет очень высокий уровень конфликтов при захвате, что приводит к сериализации планирования выполнения процессов. Иными словами, код планировщика выполнял только один процессор системы в любой момент времени, а остальные процессоры — ждали.

В общем такое повышение масштабируемости — это очень хорошая вещь, которая позволяет повысить производительность операционной системы Linux на больших и более мощных системах. Чрезмерное увлечение "ростом" масштабируемости может привести к снижению производительности на небольших многопроцессорных и однопроцессорных машинах, потому что для небольших машин не требуются такие мелкоструктурные блокировки, а им приходится иметь дело с большей сложностью и с большими накладными расходами. Рассмотрим связанный список. Первоначальная схема блокировки обеспечивает одну блокировку на весь список. Со временем эта одна блокировка может стать узким местом на очень большой многопроцессорной машине, на которой очень часто обращаются к связанному списку. Для решения проблемы одна блокировка может быть разбита на большое количество блокировок — одна блокировка на один элемент списка. Для каждого элемента списка, который необходимо прочитать или записать, необходимо захватывать уникальную блокировку этого элемента. Теперь конфликт при захвате блокировки будет только в случае, когда несколько процессоров обращаются к одному элементу списка. Что делать, если все равно есть высокий уровень конфликтов? Может быть, необходимо использовать блокировку для каждого поля элемента списка? (Ответ: НЕТ.) Если серьезно, даже когда очень мелко структурированные блокировки хорошо работают на очень больших SMP-машинах, то как они будут работать на двухпроцессорных машинах? Накладные расходы, связанные с дополнительными блокировками, будут напрасными, если на двухпроцессорной машине нет существенных конфликтов при работе с блокировками.