Locks
Из введения в параллелизм мы увидели одну из фундаментальных проблем параллельного программирования: мы хотели бы выполнить серию инструкций атомарно, но из-за наличия прерываний на одном процессоре (или нескольких потоков, выполняющихся на нескольких процессорах одновременно), мы не можем. Таким образом, в этой главе мы непосредственно решаем эту проблему, вводя нечто, называемое блокировкой (lock). Программисты дополняют исходный код блокировками, помещая их вызовы вокруг критических секций, таким образом гарантируя, что любой код критической секции выполняется так, как если бы это была одна атомарная инструкция.
28.1 Блокировки: базовая идея
В качестве примера предположим, что код критической секции выглядит как каноническое обновление общей переменной:
Конечно, возможны и другие примеры кода критической секции, такие как добавление элемента в связный список или другие более сложные обновления общих структур, но мы пока будем рассматривать простой пример. Чтобы использовать блокировку, мы добавляем некоторый код вокруг критической секции например так:
Блокировка - это просто переменная, и поэтому для ее использования необходимо объявить какую-либо переменную блокировки (lock variable) (например, mutex выше). Такая переменная блокировки (или просто "lock" для краткости) удерживает состояние блокировки в любой момент времени. Она либо доступна (разблокирована или свободна), и, следовательно, ни один поток не удерживает блокировку, либо занята (заблокирована, или удерживается), и, таким образом, ровно один поток удерживает блокировку и, предположительно, находится в критической секции. Мы могли бы также хранить другую информацию в типе данных, например, в каком потоке находится блокировка, или очередь для запроса на получение блокировки, но подобная информация скрыта от пользователя блокировки.
Семантика функций lock() и unlock() проста. Вызов функции lock() попробует осуществить блокировку; если никакой другой поток не удерживает блокировку (т.е. она свободна), поток создаст блокировку и войдёт в критическую секцию; такой поток иногда называют хозяином (owner) блокировки. Если другой поток вызовет lock() используя такую же переменную блокировки (mutex в данном примере), он не вернётся к выполнению пока блокировка удерживается другим потоком; таким образом другие потоки не могут войти в критическую секцию, если в ней находится другой поток удерживающий блокировку.
Как только owner вызывает unlock(), блокировка становится доступной для других потоков. Если нет потоков ожидающих блокировку (т.е. нет потоков вызвавших lock() и застрявших в этом вызове), состояние переменной блокировки просто меняется на свободное (free). Если ожидающие потоки существуют (застрявшие в lock()), один из них будет уведомлён об изменении состояния переменной блокировки, поток займёт блокировку и войдёт в критическую секцию.
Блокировки обеспечивают программистам некоторый минимальный контроль над планированием. В общем случае, мы рассматриваем потоки как объекты, созданные программистом, но запланированные операционной системой в таком порядке который выберет операционная система. Блокировки возвращают часть этого контроля программисту; устанавливая блокировку вокруг раздела кода, программист может гарантировать, что в этом коде может быть активно не более одного потока. Таким образом, блокировки помогают превратить хаос, который представляет собой традиционное планирование операционной системы, в более контролируемую деятельность.
28.2 Pthread Locks
mutex - это имя, которое библиотека POSIX использует для блокировки, поскольку оно используется для обеспечения взаимного исключения между потоками, т.е. если один поток находится в критической секции, он исключает вход в неё для других потоков до тех пор, пока он ни пройдёт раздел заблокированного кода. Таким образом, когда вы видите следующий код потоков POSIX, вы должны понимать, что он делает то же самое, что и код выше (мы снова используем wrappers, которые проверяют наличие ошибок при блокировке и разблокировке):
Вы также можете заметить, что вариант блокировок POSIX использует переменную для управления блокировкой. Мы можем использовать разные переменные для защиты разных критических секций. Это может увеличить параллелизм: вместо одной большой блокировки, которая используется при каждом доступе к любому критическому разделу (стратегия крупнозернистой блокировки или coarse-grained locking), часто можно защищать разные данные и структуры данных с помощью разных блокировок, тем самым позволяя большему количеству потоков находиться в заблокированном коде одновременно (более мелкозернистый подход fine-grained approach).
28.3 Создание блокировки
К настоящему времени вы должны иметь некоторое представление о том, как работает блокировка, с точки зрения программиста. Но как мы можем создать блокировку? Какая для этого нужна аппаратная поддержка? Какая нужна поддержка ОС? Именно этот набор вопросов мы рассмотрим в остальной части этой главы.
ЗАДАЧА: КАК СОЗДАТЬ БЛОКИРОВКУ?
Как можно создать эффективную блокировку? Эффективные блокировки обеспечивают взаимное исключение при низких затратах, а также могут обладать несколькими другими свойствами, которые мы обсудим ниже. Какая аппаратная поддержка необходима? Какая необходима поддержка со стороны ОС?
Чтобы создать работающую блокировку, нам понадобится помощь нашего старого друга, аппаратного обеспечения, а также нашего хорошего приятеля, операционной системы. За прошедшие годы в наборы инструкций различных компьютерных архитектур было добавлено множество различных аппаратных примитивов; хотя мы не будем изучать, как реализуются эти инструкции (в конце концов, это тема урока компьютерной архитектуры), мы изучим, как их использовать для создания примитива взаимного исключения, такого как блокировка. Мы также изучим, как задействована операционная система, чтобы завершить картину и позволить нам создать сложную библиотеку блокировок.
28.4 Оценка целесообразности блокировок
Прежде чем создавать какие-либо блокировки, мы должны понять, каковы наши цели, и поэтому мы спрашиваем, как оценить эффективность конкретной реализации блокировки. Чтобы оценить, работает ли блокировка (и работает ли хорошо), мы должны установить некоторые основные критерии. Первый заключается в том, выполняет ли блокировка свою основную задачу, которая заключается в обеспечении взаимного исключения (mutual exclusion). В принципе, работает ли блокировка, предотвращая попадание нескольких потоков в критическую секцию?
Второе - это справедливость. Получает ли каждый поток, претендующий на блокировку, справедливый шанс получить ее, как только она станет доступна? Другой способ посмотреть на проблему рассматривает более экстремальный случай: возможна ли ситуация при которой поток ожидает блокировку но никогда её не получает? Т.е. находится в бесконечном ожидании доступности блокировки. (прим. пер. в оригинале поток испытывает голод - starve)
Последним критерием является производительность, в частности, временные накладные расходы, добавляющиеся при использовании блокировки. Здесь стоит рассмотреть несколько различных случаев. Один из них - это случай отсутствия разногласий; когда работает один поток, который захватывает и снимает блокировку, каковы накладные расходы на это? Другой случай, когда несколько потоков борются за блокировку одного процессора; в этом случае существуют ли проблемы с производительностью? Наконец, как выполняется блокировка, когда задействовано несколько процессоров, и потоки на каждом из них борются за блокировку? Сравнивая эти различные сценарии, мы можем лучше понять влияние на производительность использования различных методов блокировки, как описано ниже.
28.5 Контроль прерываний
Одним из самых ранних решений, использовавшихся для обеспечения взаимного исключения, было отключение прерываний для критических секций; это решение было изобретено для однопроцессорных систем. Код будет выглядеть следующим образом:
Предположим, что мы работаем в такой однопроцессорной системе. Отключая прерывания (используя какую-либо специальную аппаратную инструкцию) перед входом в критическую секцию, мы гарантируем, что код внутри критической секции не будет прерван и, следовательно, будет выполняться так, как если бы он был атомарным. Когда мы закончим, мы снова включаем прерывания (опять же, с помощью аппаратной инструкции), и, таким образом, программа продолжается в обычном режиме.
Главным плюсом такого подхода является его простота. Вам, конечно, не нужно слишком сильно чесать голову, чтобы понять, почему это работает. Без прерывания поток может быть уверен, что выполняемый им код будет выполнен и что никакой другой поток не будет ему мешать.
Минусов, к сожалению, много. Во-первых, этот подход требует, чтобы мы разрешали любому вызывающему потоку выполнять привилегированную операцию (включение и выключение прерываний) и, таким образом, были уверены, что этим средством не злоупотребляют. Как вы уже знаете, каждый раз, когда от нас требуется доверять произвольной программе, мы, вероятно, попадаем в беду. Здесь проблема проявляется множеством способов: жадная программа может вызвать функцию lock() в начале своего выполнения и, таким образом, монополизировать процессор; хуже того, ошибочная или вредоносная программа может вызвать функцию lock() и перейти в бесконечный цикл. В этом последнем случае операционная система никогда не восстанавливает контроль над системой, и есть только один выход: перезагрузить систему. Использование отключения прерываний в качестве решения для синхронизации общего назначения требует слишком большого доверия к приложениям.
Во-вторых, этот подход не работает на многопроцессорных системах. Если несколько потоков запущены на разных процессорах, и каждый пытается войти в одну и ту же критическую секцию, не имеет значения, отключены ли прерывания; потоки смогут работать на других процессорах и, следовательно, могут войти в критическую секцию. Поскольку мультипроцессорные системы сейчас стали обычным явлением, наше общее решение должно быть лучше.
В-третьих, отключение прерываний на длительные периоды времени может привести к потере прерываний, что может привести к серьезным системным проблемам. Представьте, например, что центральный процессор пропустил тот факт, что дисковое устройство завершило запрос на чтение. Как операционная система узнает, что нужно запустить процесс, ожидающий указанного чтения?
Наконец, и, вероятно, наименее важно, этот подход может быть неэффективным. По сравнению с обычным выполнением команд, код, который маскирует или демаскирует прерывания, как правило, выполняется медленно современными процессорами.
По этим причинам отключение прерываний используется только в ограниченных контекстах в качестве примитива взаимного исключения. Например, в некоторых случаях сама операционная система будет использовать маскировку прерываний, чтобы гарантировать атомарность при доступе к своим собственным структурам данных или, по крайней мере, для предотвращения возникновения определенных ситуаций с беспорядочной обработкой прерываний. Такое использование имеет смысл, поскольку проблема доверия исчезает внутри операционной системы, которая всегда доверяет себе выполнение привилегированных операций в любом случае.
28.6 Неудачная попытка: использование загрузок/хранилищ
Чтобы выйти за рамки методов, основанных на прерываниях, нам придется полагаться на аппаратное обеспечение процессора и инструкции, которые оно предоставляет нам для создания правильной блокировки. Давайте сначала попробуем создать простую блокировку с помощью одной переменной флага. В этой неудачной попытке мы рассмотрим некоторые основные идеи, необходимые для создания блокировки, и (надеюсь) поймем, почему простого использования одной переменной и доступа к ней через обычные загрузки и хранилища недостаточно.
В этой первой попытке (рис. 28.1) идея довольно проста: используйте простую переменную (флаг), чтобы указать, владеет ли какой-либо поток блокировкой. Первый поток, который войдет в критическую секцию, вызовет функцию lock(), которая проверяет, равен ли флаг 1 (в данном случае это не так), а затем устанавливает флаг равным 1, чтобы указать, что поток теперь удерживает блокировку. По завершении критической секции поток вызывает функцию unlock() и снимает флаг, указывая таким образом, что блокировка больше не удерживается.
Если другой поток вызовет функцию lock(), пока этот первый поток находится в критической секции, он просто будет вращаться - ждать в цикле while, пока этот поток вызовет функцию unlock() и снимет флаг. Как только этот первый поток сделает это, ожидающий поток выйдет из цикла while, установит для себя флаг равным 1 и перейдет в критический раздел.
К сожалению, у кода есть две проблемы: одна из них связана с корректностью, а другая - с производительностью.
Проблему корректности легко увидеть, как только вы привыкнете думать о параллельном программировании. Представьте себе чередование кодов на рис. 28.2; для начала предположим, что flag = 0.
Как вы можете видеть из этого чередования, при своевременных (несвоевременных?) прерываниях мы можем легко создать случай, когда оба потока устанавливают флаг равным 1, и, таким образом, оба потока могут войти в критическую секцию. Такое поведение профессионалы называют ”плохим" – мы явно не выполнили самое основное требование: обеспечить взаимное исключение.
Проблема производительности, которую мы рассмотрим подробнее позже, заключается в том, что поток ожидает получения блокировки, которая уже удерживается: он бесконечно проверяет значение флага, метод, известный как spin-waiting. Spin-waiting тратит время на ожидание, пока другой поток снимет блокировку. Потери исключительно высоки в однопроцессорной системе, где ожидающий поток даже не может запуститься (по крайней мере, до тех пор, пока не произойдет переключение контекста)! Таким образом, по мере того, как мы продвигаемся вперед и разрабатываем более сложные решения, мы также должны рассмотреть способы избежать такого рода траты ресурсов в пустую.
28.7 Создание рабочей spin-lock с использованием Test-And-Set
Поскольку отключение прерываний не работает на нескольких процессорах, а также из-за того, что простые подходы с использованием загрузок и хранилищ (как показано выше) не работают, разработчики систем начали изобретать аппаратную поддержку блокировки. Самые ранние многопроцессорные системы, такие как Burroughs B5000 в начале 1960-х годов [M82], имели такую поддержку; сегодня все системы обеспечивают этот тип поддержки, даже для систем с одним процессором.
Самая простая для понимания часть аппаратной поддержки известна как инструкция test-and-set (или atomic exchange*). Мы определяем, поведение инструкции test-and-set, с помощью следующего фрагмента кода C:
*Каждая архитектура, поддерживающая test-and-set, называет его другим именем. В SPARC это называется инструкцией загрузки/сохранения неподписанных байтов (ldstub); на x86 это заблокированная версия атомарного обмена (xchg).
ДОПОЛНЕНИЕ: АЛГОРИТМЫ ДЕККЕРА И ПЕТЕРСОНА
В 1960-х годах Дейкстра поставил проблему параллелизма перед своими друзьями, и один из них, математик по имени Теодорус Йозеф Деккер, предложил решение [D68]. В отличие от решений, которые мы обсуждаем здесь, которые используют специальные аппаратные инструкции и даже поддержку ОС, алгоритм Деккера использует только загрузки и хранилища (при условии, что они являются атомарными по отношению друг к другу, что было верно на раннем оборудовании).
Подход Деккера был позже усовершенствован Петерсоном [P81]. Опять же, используются только загрузки и хранилища, и идея состоит в том, чтобы гарантировать, что два потока никогда не войдут в критическую секцию одновременно. Вот алгоритм Петерсона (для двух потоков); посмотрите, сможете ли вы понять код. Для чего используются переменные flag и turn?
int flag[2];
int turn;
void init() {
// indicate you intend to hold the lock w/ ’flag’
flag[0] = flag[1] = 0;
// whose turn is it? (thread 0 or 1)
turn = 0;
}
void lock() {
// ’self’ is the thread ID of caller
flag[self] = 1;
// make it other thread’s turn
turn = 1 - self;
// spin-wait while it’s not your turn
while ((flag[1-self] == 1) && (turn == 1 - self)) ;
}
void unlock() {
// simply undo your intent
flag[self] = 0;
}
По какой-то причине разработка блокировок, которые работают без специальной аппаратной поддержки, на некоторое время вошла в моду, создавая теоретикам множество проблем в работе. Конечно, это направление работы стало совершенно бесполезным, когда люди поняли, что гораздо проще обеспечить небольшую аппаратную поддержку (и действительно, эта поддержка существовала с самых первых дней многопроцессорной обработки). Кроме того, алгоритмы, подобные приведенным выше, не работают на современном оборудовании (из-за ослабленных моделей согласованности памяти), что делает их еще менее полезными, чем раньше. Еще больше исследований отправлено на свалку истории...
Инструкция test-and-set выполняется следующим образом. Он возвращает старое значение, на которое указывает old_ptr, и одновременно изменяет указанное значение на new. Ключевым моментом, конечно, является то, что эта последовательность операций выполняется атомарно. Причина, по которой она называется “test-and-set”, заключается в том, что она позволяет вам “test” старое значение (которое и возвращается), одновременно “set” ячейку памяти на новое значение; как оказалось, этой немного более мощной инструкции достаточно для создания простой spin-lock, как мы сейчас рассмотрим на рисунке 28.3. Или еще лучше: сначала разберитесь в этом сами!
Давайте убедимся в том, что мы понимаем, почему работает эта блокировка. Представьте сначала случай, когда поток вызывает функцию lock(), и ни один другой поток в данный момент не удерживает блокировку; таким образом, флаг должен быть равен 0. Когда поток вызывает TestAndSet(flag, 1), подпрограмма вернет старое значение flag, равное 0; таким образом, вызывающий поток, который проверяет значение flag, не попадет в цикл while и получит блокировку. Поток также атомарно установит значение 1, тем самым указывая, что блокировка теперь удерживается. Когда поток завершает свою критическую секцию, он вызывает функцию unlock(), чтобы установить флаг обратно на ноль.
Второй случай, который мы можем себе представить, возникает, когда в одном потоке уже удерживается блокировка (т.e. флаг равен 1). В этом случае этот поток вызовет функцию lock(), а затем вызовет функцию TestAndSet(flag, 1). На этот раз функция TestAndSet() вернет старое значение flag, равное 1 (поскольку блокировка удерживается), одновременно снова установив его равным 1. Пока блокировка удерживается другим потоком, функция TestAndSet() будет многократно возвращать 1, и, таким образом, этот поток будет вращаться и вращаться до тех пор, пока блокировка не будет окончательно снята. Когда flag, наконец, будет установлен в 0 каким-либо другим потоком, этот поток снова вызовет функцию TestAndSet(), которая теперь вернет 0 при атомарной установке значения в 1 и, таким образом, получит блокировку и войдет в критическую секцию.
Делая как проверку test (старого значения блокировки), так и установку set (нового значения) одной атомарной операцией, мы гарантируем, что только один поток получит блокировку. И вот как построить работающий примитив взаимного исключения!
СОВЕТ: ПОДУМАЙТЕ О ПАРАЛЛЕЛИЗМЕ КАК О ВРЕДОНОСНОМ ПЛАНИРОВЩИКЕ
Из этого примера вы можете получить представление о подходе, который вам необходимо использовать, чтобы понять параллельное выполнение. Что вам следует попытаться сделать, так это притвориться, что вы злонамеренный планировщик, который прерывает потоки в самое неподходящее время, чтобы помешать их слабым попыткам создать примитивы синхронизации. Какой же вы подлый планировщик! Хотя точная последовательность прерываний может казаться чем-то невероятным, это возможно, и это все, что нам нужно, чтобы продемонстрировать, что конкретный подход не работает. Может быть полезно думать злонамеренно! (по крайней мере, иногда)
Теперь вы также можете понять, почему этот тип блокировки обычно называют spin-lock. Это самый простой тип блокировки для создания, и он просто вращается, используя циклы процессора, до тех пор, пока блокировка не станет доступной. Для корректной работы на одном процессоре требуется упреждающий планировщик (т.е. такой, который будет прерывать поток с помощью таймера, чтобы время от времени запускать другой поток). Без упреждения spin locks не имеют большого смысла на одном процессоре, так как поток, вращающийся на процессоре монополизирует его.
28.8 Оценка Spin Locks
Учитывая нашу базовую spin-lock, теперь мы можем оценить, насколько она эффективна по нашим ранее описанным показателям. Наиболее важным аспектом блокировки является корректность: обеспечивает ли она взаимное исключение? Ответ здесь утвердительный: блокировка вращения позволяет только одному потоку входить в критическую секцию одновременно. Таким образом это корректная блокировка.
Следующий показатель - это справедливость. Насколько справедлива блокировка вращения для ожидающего потока? Можете ли вы гарантировать, что ожидающий поток когда-либо войдет в критическую секцию? Ответ здесь, к сожалению, заключается в плохих новостях: spin locks не дают никаких гарантий справедливости. В условиях конкуренции потоков - ожидающий поток может ожидать вечно. Простые spin locks (как обсуждалось до сих пор) несправедливы и могут привести к бесконечному ожиданию.
Последний показатель - это производительность. Каковы затраты на использование блокировки вращения? Чтобы проанализировать это более тщательно, мы предлагаем подумать о нескольких различных случаях. В первом случае представьте потоки, конкурирующие за блокировку на одном процессоре; во втором рассмотрим потоки, распределенные по многим процессорам.
Для spin locks в случае с одним процессором накладные расходы на производительность могут быть довольно болезненными; представьте себе случай, когда поток, удерживающий блокировку, вытесняется в критической секции. Затем планировщик может запустить любой другой поток (представьте, что есть N − 1 потоков), каждый из которых пытается получить блокировку. В этом случае каждый из этих потоков будет ожидать в течение определенного отрезка времени, прежде чем отпустить процессор, что приведет к пустой трате циклов процессора.
Однако на нескольких процессорах spin locks работают достаточно хорошо (если количество потоков примерно равно количеству процессоров). Мышление выглядит следующим образом: представьте себе поток A на процессоре 1 и поток B на процессоре 2, оба борются за блокировку. Если поток A (процессор 1) захватит блокировку, а затем поток B попытается это сделать, B будет вращаться (на процессоре 2). Однако, предположительно, критический раздел короткий, и поэтому вскоре блокировка становится доступной и приобретается потоком B. Вращение в ожидании блокировки, удерживаемой на другом процессоре, в этом случае не тратит много циклов впустую и, следовательно, может быть эффективным.
28.9 Compare-And-Swap
Другой аппаратный примитив, реализованный в некоторых системах, называется инструкцией compare-and-swap (как он называется в SPARC например), или compare-and-exchange (название в x86). Псевдокод на языке С для такой инструкции можно найти на рисунке 28.4
Основная идея compare-and-swap заключается в проверке адреса определённого в ptr с адресом ожидаемым в expected; если адреса совпадают, значение в ptr обновляется с использованием значения из параметра new. Если нет - ничего не происходит. В любом случае из вызова вернётся значение переменной original, что позволит вызывающему понять успешным ли был вызов.
Используя compare-and-swap мы можем создать блокировку работающую проще чем с использованием подхода test-and-set. Например мы могли бы заменить процедуру lock следующей:
Остальная часть кода такая же, как в приведенном выше примере test-and-set. Этот код работает совершенно аналогично; он просто проверяет, равен ли flag нулю, и если да, то атомарно присваивает 1, таким образом получая блокировку. Потоки, которые пытаются захватить блокировку, пока она удерживается, будут ожидать в цикле до тех пор, пока блокировка не будет окончательно снята.
Если вы хотите увидеть как действительно сделать compare-and-swap на языке С для процессора x86, пример кода из ссылки [S05] может помочь*.
*github.com/remzi-arpacidusseau/ostep-code/tree/master/threads-locks
Наконец, как вы возможно почувствовали, compare-and-swap более мощная инструкция чем test-and-set. Мы воспользуемся этой мощью в будущем, когда кратко рассмотрим такие темы, как lock-free synchronization [H91]. Однако, если мы просто создадим с его помощью простую spin lock, ее поведение будет идентично spin lock, которую мы проанализировали выше.
28.10 Load-Linked and Store-Conditional
Некоторые платформы предоставляют пару инструкций, которые работают согласованно, помогая создавать критические разделы. В архитектуре MIPS [H93], например, инструкции load-linked и store-conditional, могут использоваться в тандеме для построения блокировок и других параллельных структур. Псевдокод C для этих инструкций приведен на рисунке 28.5. Alpha, PowerPC и ARM предоставляют аналогичные инструкции [W09].
load-linked работает так же, как обычная инструкция загрузки, и просто извлекает значение из памяти и помещает его в регистр. Ключевое отличие заключается в store-conditional, который выполняется успешно (и обновляет значение, сохраненное по адресу, с которого только что была загружена ссылка), только в том случае, если по адресу не было изменений с момента чтения с помощью load-linked. В случае успеха, store-conditional возвращает 1 и обновляет значение ptr с помощью value; в случае неудачи - значение ptr не обновляется и возвращается 0.
В качестве вызова для себя попробуйте подумать о том, как создать блокировку, используя load-linked и store-conditional. Затем, когда вы закончите, посмотрите на приведенный ниже код, который предлагает одно простое решение. Сделай это! Решение приведено на рисунке 28.6.
Код lock() - единственная интересная деталь. Во-первых, поток находится в цикле, ожидая, пока флаг будет установлен в 0 (и, таким образом, укажет, что блокировка не удерживается). Как только это произойдет, поток попытается получить блокировку с помощью store-conditional; если это удастся, поток атомарно поменяет значение флага на 1 и, таким образом, сможет перейти в критическую секцию.
Обратите внимание, как может возникнуть сбой в store-conditional. Один поток вызывает функцию lock() и выполняет load-linked, возвращается 0, так как блокировка не удерживается. Прежде чем он сможет попытаться выполнить вызов store-conditional, он прерывается, и другой поток входит в заблокированный код, также выполняя инструкцию load-linked, и также получая 0. На этом этапе два потока выполнили вызов load-linked, и каждый из них собирается выполнить вызов store-conditional. Ключевой особенностью этих инструкций является то, что только одному из этих потоков удастся обновить флаг до 1 и, таким образом, получить блокировку; второй поток, пытающийся выполнить store-conditional, завершится неудачей (поскольку другой поток обновил значение флага между его вызовом load-linked и store-conditional) и, следовательно, должен попытаться получить блокировку снова.
На занятиях несколько лет назад студент-бакалавр Дэвид Кейпел предложил более краткую форму вышеизложенного для тех из вас, кто любит сокращать булевы условные обозначения. Посмотрите, сможете ли вы понять, почему это эквивалентно. Это, конечно, короче!
28.11 Fetch-And-Add
Одним из последних аппаратных примитивов является инструкция fetch-and-add, которая атомарно увеличивает значение, возвращая старое значение по определенному адресу. Псевдокод на С для инструкции fetch-and-add:
СОВЕТ: ЧЕМ МЕНЬШЕ КОДА, ТЕМ ЛУЧШЕ КОД (ЗАКОН ЛАУЭРА)
Программисты склонны хвастаться тем, сколько кода они написали, чтобы что-то сделать. Это в корне неверно. Скорее следует хвастаться тем, как мало кода было написано для выполнения данной задачи. Короткий, лаконичный код всегда предпочтительнее; он, скорее всего, легче для понимания и содержит меньше ошибок. Как сказал Хью Лауэр, обсуждая создание операционной системы Pilot: “Если бы у одних и тех же людей было вдвое больше времени, они могли бы создать такую же хорошую систему с объёмом кода меньшим в половину”. [L81] Мы назовем это Законом Лауэра, и его стоит запомнить. Поэтому в следующий раз, когда вы будете хвастаться тем, сколько кода вы написали, чтобы закончить задание, подумайте еще раз, а еще лучше, вернитесь назад, перепишите и сделайте код максимально ясным и кратким.
В этом примере мы будем использовать функцию fetch-and-add для создания более интересной ticket lock, предложенной Меллором-Крамми и Скоттом [MS91]. Код блокировки и разблокировки приведен на рисунке 28.7.
Вместо одного значения это решение использует комбинацию переменных ticket и turn для создания блокировки. Основная операция довольно проста: когда поток желает получить блокировку, он сначала выполняет атомарную fetch-and-add над значением ticket; это значение теперь считается “очередью” (насколько я понимаю - номером в очереди) этого потока (myturn). Затем глобальная переменная lock->turn используется для определения номера в очереди для потока; когда (myturn == turn) для данного потока наступает очередь войти в критическую секцию. Разблокировка достигается простым увеличением переменной turn таким образом, чтобы следующий ожидающий поток (если он есть) теперь мог войти в критическую секцию.
Обратите внимание на одно важное отличие этого решения от наших предыдущих попыток: оно обеспечивает прогресс для всех потоков. Как только потоку будет присвоен номер в очереди, он будет запланирован в какой-то момент в будущем (как только те, кто перед ним, пройдут через критическую секцию и снимут блокировку). В наших предыдущих попытках такой гарантии не существовало; поток, вращающийся при применении test-and-set (например), мог вращаться вечно, даже когда другие потоки получают и снимают блокировку.
28.12 Слишком много циклов: что теперь?
Наши аппаратные блокировки просты (всего несколько строк кода), и они работают (вы даже можете доказать это, если захотите, написав некоторый код), что является двумя отличными свойствами любой системы или кода. Однако в некоторых случаях эти решения могут быть весьма неэффективными. Представьте, что вы запускаете два потока на одном процессоре. Теперь представьте, что один поток (поток 0) находится в критической секции и, следовательно, заблокирован и, к сожалению, прерывается. Второй поток (поток 1) теперь пытается получить блокировку, но обнаруживает, что она удерживается. Таким образом, он начинает вращаться в цикле. И вращаться. Потом он вращается ещё немного. И, наконец, прерывание по таймеру отключается, снова запускается поток 0, который снимает блокировку, и, наконец (скажем, при следующем запуске) потоку 1 не придется так много вращаться и он сможет получить блокировку. Таким образом, каждый раз, когда поток попадает в подобную ситуацию, он тратит впустую весь временной отрезок, ничего не делая, кроме проверки значения, которое не изменится! Проблема усугубляется тем, что N потоков борются за блокировку; Аналогичным образом могут быть потрачены N − 1 временных отрезков, которые просто вращаются и ждут, пока один поток снимет блокировку. И, таким образом появляется наша следующая проблема:
ПРОБЛЕМА: КАК ИЗБЕЖАТЬ ВРАЩЕНИЯ
Как мы можем разработать блокировку, которая не будет напрасно тратить время на вращение процессора?
Аппаратная поддержка сама по себе не может решить проблему. Нам также понадобится поддержка операционной системы! Давайте теперь выясним, как это может сработать.
28.13 Простое решение: : Just Yield, Baby
Аппаратная поддержка позволила нам довольно далеко продвинуться: рабочие блокировки и даже (как в случае с ticket lock) справедливость в получении блокировок. Однако у нас все еще есть проблема: что делать, когда в критической секции происходит переключение контекста, и потоки начинают бесконечно вращаться, ожидая повторного запуска прерванного (удерживающего блокировку) потока?
Наша первая попытка - это простой и дружественный подход: когда вы собираетесь вращаться, вместо этого передайте процессор другому потоку. Как мог бы сказать Эл Дэвис: “just yield, baby!” [D91]. На рисунке 28.8 показан подход.
В этом подходе мы предполагаем, что существует примитив операционной системы yield(), который поток может вызывать, когда он хочет отказаться от процессора и позволить другому потоку работать. Поток может находиться в одном из трех состояний (running, ready, или blocked); yield - это просто системный вызов, который переводит вызывающий поток из состояния running в состояние ready и, таким образом, способствует запуску другого потока. Таким образом, поток вызывающий yield, снимает контекст с себя (deschedules itself).
Подумайте о примере с двумя потоками на одном процессоре; в этом случае наш yield-based подход, работает довольно хорошо. Если поток случайно вызовет функцию lock() и обнаружит, что блокировка удерживается, он просто отключит процессор, и, таким образом, другой поток запустится и завершит свою критическую секцию. В данном простом примере подход с использованием yield показывает себя хорошо.
Давайте теперь рассмотрим случай, когда существует множество потоков (скажем, 100), которые неоднократно борются за блокировку. В этом случае, если один поток получит блокировку и будет вытеснен перед ее освобождением, остальные 99 потоков вызовут функцию lock(), обнаружат, что блокировка удерживается, и уступят процессор. Предполагая какой-то циклический планировщик, каждый из 99 выполнит этот шаблон запуска и выхода до того, как поток, удерживающий блокировку, снова запустится. Хотя этот подход лучше, чем наш подход к вращению (который потратил бы 99 временных срезов на вращение), он по-прежнему является дорогостоящим; стоимость переключения контекста может быть существенной, и, следовательно, возникает большая трата ресурсов.
Хуже того, мы вообще не решили проблему starvation. Поток может попасть в бесконечный цикл выхода, в то время как другие потоки многократно входят и выходят из критической секции. Нам явно понадобится подход, который непосредственно решит эту проблему.
28.14 Использование очередей: спящий режим вместо вращения
Реальная проблема наших предыдущих подходов заключается в том, что они слишком многое оставляют на волю случая. Планировщик определяет, какой поток запускается следующим; если планировщик делает неправильный выбор, запускается поток, который должен либо вращаться в ожидании блокировки (наш первый подход), либо немедленно освободить процессор (наш второй подход). В любом случае, существует вероятность пустой траты ресурсов и отсутствие предотвращения проблемы голода.
Таким образом, мы должны явно осуществлять некоторый контроль над тем, какой поток в следующий раз получит блокировку после того, как ее освободит текущий владелец. Для этого нам понадобится немного больше поддержки ОС, а также очередь для отслеживания того, какие потоки ожидают получения блокировки.
Для простоты мы будем использовать поддержку, предоставляемую Solaris, в виде двух вызовов: park(), чтобы перевести вызывающий поток в спящий режим, и unpark(ThreadId), чтобы разбудить определенный поток указанный в ThreadId. Эти две процедуры можно использовать в тандеме для создания блокировки, которая переводит вызывающий поток в спящий режим, если он пытается получить удерживаемую блокировку, и будит его, когда блокировка свободна. Давайте посмотрим на код на рисунке 28.9, чтобы понять одно из возможных применений таких примитивов.
ДОПОЛНЕНИЕ: ЕЩЕ ОДНА ПРИЧИНА ИЗБЕГАТЬ ВРАЩЕНИЯ: ИНВЕРСИЯ ПРИОРИТЕТА
Одной из веских причин избегать блокировок вращения является производительность: как описано в основном тексте, если поток прерывается при удержании блокировки, другие потоки, использующие блокировки вращения, будут тратить большое количество процессорного времени, просто ожидая, пока блокировка станет доступной. Однако, оказывается, есть еще одна интересная причина избегать спин-блокировок в некоторых системах: корректность. Проблема, которой следует опасаться, известна как инверсия приоритетов, которая, к сожалению, является межгалактическим бедствием, происходящим на Земле [M15] и Марсе [R97]!
Давайте предположим, что в системе есть два потока. Поток 2 (T2) имеет высокий приоритет планирования, а поток 1 (T1) имеет более низкий приоритет. В этом примере давайте предположим, что планировщик ЦП всегда будет запускать T2 поверх T1, если действительно оба могут выполняться; T1 запускается только тогда, когда T2 не может этого сделать (например, когда T2 заблокирован при вводе / выводе).
Теперь о проблеме. Предположим, что T2 по какой-то причине заблокирован. T1 выполняется, захватывает блокировку вращения и входит в критическую секцию. Теперь T2 становится разблокированным (возможно, из-за завершения ввода-вывода), и планировщик ЦП немедленно планирует его (таким образом, отменяя выполнение T1). Теперь T2 пытается получить блокировку, и поскольку он не может (T1 удерживает блокировку), он просто продолжает вращаться. Поскольку блокировка является блокировкой вращения, T2 вращается вечно, и система зависает.
Просто отказ от использования спин-блокировок, к сожалению, не позволяет избежать проблемы инверсии (увы). Представьте себе три потока, T1, T2 и T3, с наивысшим приоритетом T3 и наименьшим приоритетом T1. Представьте теперь, что T1 захватывает блокировку. Затем запускается T3, и поскольку он имеет более высокий приоритет, чем T1, запускается немедленно (вытесняя T1). T3 пытается получить блокировку, которую удерживает T1, но застревает в ожидании, потому что T1 все еще удерживает ее. Если T2 начнет выполняться, у него будет более высокий приоритет, чем у T1, и, следовательно, он будет запущен. T3, который имеет более высокий приоритет, чем T2, застрял в ожидании T1, который может никогда не запуститься теперь, когда запущен T2. Разве не печально, что могучий T3 не может работать, в то время как скромный T2 управляет процессором? Иметь высокий приоритет - это уже не то, что раньше.
Проблему инверсии приоритетов можно решить несколькими способами. В конкретном случае, когда проблема возникает из-за спин-блокировок, вы можете отказаться от использования спин-блокировок (подробнее описано ниже). В более общем плане поток с более высоким приоритетом, ожидающий поток с более низким приоритетом, может временно повысить приоритет потока с более низким приоритетом, тем самым позволяя ему работать и преодолевая инверсию, метод, известный как наследование приоритетов (priority inheritance). Последнее решение является самым простым: убедитесь, что все потоки имеют одинаковый приоритет.
В этом примере мы делаем пару интересных вещей. Во-первых, мы объединяем старую идею test-and-set с явной очередью ожидания блокировки, чтобы сделать блокировку более эффективной. Во-вторых, мы используем очередь, чтобы помочь контролировать, кто получит блокировку следующим, и таким образом избежать голода.
Вы можете заметить, как используется защита (рис. 28.9), в основном в качестве блокировки вокруг флага и манипуляций с очередями, которые использует блокировка. Таким образом, этот подход не позволяет полностью избежать ожидания в цикле; поток может быть прерван при получении или снятии блокировки и, таким образом, привести к тому, что другие потоки будут вращаться - ожидая, пока этот поток снова запустится. Однако время, затрачиваемое на вращение, довольно ограничено (всего несколько инструкций внутри кода блокировки и разблокировки вместо определяемого пользователем критического раздела), и поэтому такой подход может быть разумным.
Вы также можете заметить, что в lock(), когда поток не может получить блокировку (она уже удерживается), мы осторожно добавляем себя в очередь (вызывая функцию gettid(), чтобы получить идентификатор текущего потока), устанавливаем guard в 0 и отпускаем процессор. Вопрос к читателю: Что произошло бы, если бы запись в guard для данной блокировки произошло бы после вызова park(), а не раньше? Подсказка: что-то плохое.
Кроме того, вы можете обнаружить, что флаг не возвращается к 0 при пробуждении другого потока. Почему это так? Что ж, это не ошибка, а скорее необходимость! Когда поток пробуждается, это происходит так, как если бы он возвращался из вызова park(); однако в этот момент он не удерживает переменную guard и, следовательно, не может даже попытаться установить флаг равным 1. Таким образом, мы просто передаем блокировку непосредственно из потока, снимающего блокировку, следующему потоку, получающему ее; flag не установлен в 0 между ними.
Наконец, вы можете заметить предполагаемое состояние гонки в решении, непосредственно перед вызовом функции park(). При неправильном выборе времени поток будет готов к парковке, предполагая, что он должен спать до тех пор, пока блокировка больше не будет снята. Переключение в это время на другой поток (скажем, поток, удерживающий блокировку) может привести к проблемам, например, если этот поток затем снимет блокировку. Первый поток, вызвав park() будет спать вечно (потенциально), проблема, иногда называемая wakeup/ waiting race.
Solaris решает эту проблему, добавляя третий системный вызов: setpark(). Вызывая эту процедуру, поток может указать, что он собирается припарковаться. Если затем произойдет прерывание и другой поток вызовет unpark до фактического вызова park, последующий park немедленно вернется вместо спящего режима. Модификация кода внутри lock() довольно мала:
Другое решение могло бы передать защиту в ядро. В этом случае ядро может принять меры предосторожности, чтобы атомарно снять блокировку и вывести запущенный поток из очереди.
28.15 Разные ОС, разная поддержка
До сих пор мы видели один тип поддержки, который может предоставить ОС для создания более эффективной блокировки в библиотеке потоков. Другие ОС предоставляют аналогичную поддержку; детали различаются.
Например, Linux предоставляет futex, который аналогичен интерфейсу Solaris, но обеспечивает большую функциональность в ядре. В частности, с каждой futex связана определенная ячейка физической памяти, а также очередь в ядре для каждого futex. Вызывающие потоки могут использовать вызовы futex (описано ниже) для засыпания и пробуждения по мере необходимости.
В частности, доступны два вызова. Вызов функции futex_wait(address, expected) переводит вызывающий поток в спящий режим, предполагая, что значение в address равно expected. Если они не равны, вызов немедленно возвращается. Вызов futex_wake(address) пробуждает один поток, ожидающий в очереди. Использование этих вызовов в мьютексе Linux показано на рисунке 28.10.
Этот фрагмент кода из lowlevellock.h в библиотеке nptl (часть библиотеки gnu libc) [L09] интересен по нескольким причинам. Во-первых, он использует одно целое число для отслеживания как того, удерживается блокировка или нет (старший бит целого числа), так и количества ожидающих блокировку (все остальные биты). Таким образом, если блокировка отрицательна, она удерживается (поскольку установлен старший бит, и этот бит определяет знак целого числа).
Во-вторых, фрагмент кода показывает оптимизацию для общего случая, особенно когда нет конкуренции за блокировку; когда только один поток получает и снимает блокировку, выполняется очень мало работы (проверка и установка атомарного бита для блокировки и атомарное добавление для снятия блокировки).
Посмотрите, сможете ли вы разобраться с остальной частью этой блокировки из “реального мира”, чтобы понять, как она работает. Сделайте это и станьте мастером блокировки Linux или, по крайней мере, кем-то, кто слушает, когда книга говорит вам что-то сделать*
*Например, купить печатную копию OSTEP! Несмотря на то, что книга доступна бесплатно онлайн, разве вам не понравилась бы твердая обложка для вашего стола? Или, еще лучше, десять копий, чтобы поделиться ими с друзьями и семьей? И, может быть, один дополнительный экземпляр, чтобы бросить во врага? (книга тяжелая, и поэтому выбрасывание ее удивительно эффективно)
28.16 Двухфазные блокировки
Последнее замечание: подход Linux имеет привкус старого метода, который использовался в течение многих лет, начиная, по крайней мере, с блокировок Dahm в начале 1960-х годов [M82], и теперь называется двухфазной блокировкой (two-phase lock). Двухфазная блокировка позволяет понять, что вращение может быть полезным, особенно если блокировка вот-вот будет снята. Таким образом, на первом этапе поток некоторое время вращается, надеясь, что он сможет получить блокировку.
Однако, если блокировка не была получена во время первой фазы вращения, вводится вторая фаза, в которой вызывающий абонент погружается в спящий режим и просыпается только тогда, когда появляется возможность получить блокировку. Приведенная выше блокировка Linux является формой такой блокировки, но она выполняется только один раз; обобщение этого может выполняться в цикле в течение фиксированного промежутка времени, прежде чем использовать поддержку futex для перехода в спящий режим.
Двухфазные блокировки - это еще один пример гибридного подхода, когда объединение двух хороших идей действительно может привести к лучшей. Конечно, так это или нет, сильно зависит от многих факторов, включая аппаратную среду, количество потоков и другие детали рабочей нагрузки. Как всегда, создание единой блокировки общего назначения, подходящей для всех возможных вариантов использования, является довольно сложной задачей.
28.17 Выводы
Приведенный выше подход показывает, как в наши дни создаются реальные блокировки: некоторая аппаратная поддержка (в виде более мощной инструкции) плюс некоторая поддержка операционной системы (например, в виде примитивов park() и unpark() в Solaris или futex в Linux). Конечно, детали различаются, и точный код для выполнения такой блокировки обычно сильно настраивается. Ознакомьтесь с кодовыми базами Solaris или Linux, если хотите узнать больше подробностей; это увлекательное чтение [L09, S09]. Также см. отличную работу Дэвида и др. для сравнения стратегий блокировки на современных многопроцессорах [D + 13].
Ссылки
[D91] “Just Win, Baby: Al Davis and His Raiders” by Glenn Dickey. Harcourt, 1991. The book about Al Davis and his famous quote. Or, we suppose, the book is more about Al Davis and the Raiders, and not so much the quote. To be clear: we are not recommending this book, we just needed a citation.
[D+13] “Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask” by Tudor David, Rachid Guerraoui, Vasileios Trigonakis. SOSP ’13, Nemacolin Woodlands Resort, Pennsylvania, November 2013. An excellent paper comparing many different ways to build locks using hardware primitives. Great to see how many ideas work on modern hardware.
[D68] “Cooperating sequential processes” by Edsger W. Dijkstra. 1968. Available online here: http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF. One of the early seminal papers. Discusses how Dijkstra posed the original concurrency problem, and Dekker’s solution.
[H93] “MIPS R4000 Microprocessor User’s Manual” by Joe Heinrich. Prentice-Hall, June 1993. Available: http://cag.csail.mit.edu/raw/documents/R4400 Uman book Ed2.pdf. The old MIPS user’s manual. Download it while it still exists.
[H91] “Wait-free Synchronization” by Maurice Herlihy. ACM TOPLAS, Volume 13: 1, January 1991. A landmark paper introducing a different approach to building concurrent data structures. Because of the complexity involved, some of these ideas have been slow to gain acceptance in deployment.
[L81] “Observations on the Development of an Operating System” by Hugh Lauer. SOSP ’81, Pacific Grove, California, December 1981. A must-read retrospective about the development of the Pilot OS, an early PC operating system. Fun and full of insights.
[L09] “glibc 2.9 (include Linux pthreads implementation)” by Many authors.. Available here: http://ftp.gnu.org/gnu/glibc. In particular, take a look at the nptl subdirectory where you will find most of the pthread support in Linux today.
[M82] “The Architecture of the Burroughs B5000: 20 Years Later and Still Ahead of the Times?” by A. Mayer. 1982. Available: www.ajwm.net/amayer/papers/B5000.html. “It (RDLK) is an indivisible operation which reads from and writes into a memory location.” RDLK is thus testand-set! Dave Dahm created spin locks (“Buzz Locks”) and a two-phase lock called “Dahm Locks.”
[M15] “OSSpinLock Is Unsafe” by J. McCall. mjtsai.com/blog/2015/12/16/osspinlock -is-unsafe. Calling OSSpinLock on a Mac is unsafe when using threads of different priorities – you might spin forever! So be careful, Mac fanatics, even your mighty system can be less than perfect...
[MS91] “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors” by John M. Mellor-Crummey and M. L. Scott. ACM TOCS, Volume 9, Issue 1, February 1991. An excellent and thorough survey on different locking algorithms. However, no operating systems support is used, just fancy hardware instructions.
[P81] “Myths About the Mutual Exclusion Problem” by G.L. Peterson. Information Processing Letters, 12(3), pages 115–116, 1981. Peterson’s algorithm introduced here.
[R97] “What Really Happened on Mars?” by Glenn E. Reeves. research.microsoft.com/ en-us/um/people/mbj/Mars Pathfinder/Authoritative Account.html. A description of priority inversion on Mars Pathfinder. Concurrent code correctness matters, especially in space!
[S05] “Guide to porting from Solaris to Linux on x86” by Ajay Sood, April 29, 2005. Available: http://www.ibm.com/developerworks/linux/library/l-solar/.
[S09] “OpenSolaris Thread Library” by Sun.. Code: src.opensolaris.org/source/xref/ onnv/onnv-gate/usr/src/lib/libc/port/threads/synch.c. Pretty interesting, although who knows what will happen now that Oracle owns Sun. Thanks to Mike Swift for the pointer.
[W09] “Load-Link, Store-Conditional” by Many authors.. en.wikipedia.org/wiki/LoadLink/Store-Conditional. Can you believe we referenced Wikipedia? But, we found the information there and it felt wrong not to. Further, it was useful, listing the instructions for the different architectures: ldl l/stl c and ldq l/stq c (Alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS), and ldrex/strex (ARM). Actually Wikipedia is pretty amazing, so don’t be so harsh, OK?
[WG00] “The SPARC Architecture Manual: Version 9” by D. Weaver, T. Germond. SPARC International, 2000. http://www.sparc.org/standards/SPARCV9.pdf. See developers. sun.com/solaris/articles/atomic sparc/ for more on atomics.