Устраняет ли неизменность необходимость блокировок при многопроцессорном программировании?

39

Часть 1

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

Я знаю, что многие функциональные программисты и математики любят говорить об «отсутствии побочных эффектов», но в «реальном мире» все имеет побочный эффект, даже если это время, которое требуется для выполнения машинной инструкции. Меня интересует как теоретический / академический ответ, так и практический / реальный ответ.

Если неизменность безопасна, учитывая определенные границы или предположения, я хочу знать, каковы границы «зоны безопасности». Некоторые примеры возможных границ:

  • I / O
  • Исключения / ошибки
  • Взаимодействие с программами, написанными на других языках
  • Взаимодействие с другими машинами (физическими, виртуальными или теоретическими)

Особая благодарность @JimmaHoffa за его комментарий, который начал этот вопрос!

Часть 2

Многопроцессорное программирование часто используется как метод оптимизации, чтобы заставить некоторый код работать быстрее. Когда быстрее использовать замки и неизменные объекты?

Учитывая ограничения, установленные в Законе Амдала , когда вы сможете достичь более высокой общей производительности (с учетом или без учета сборщика мусора) с неизменяемыми объектами по сравнению с блокировкой изменяемых объектов?

Резюме

Я объединяю эти два вопроса в один, чтобы попытаться найти ограничивающую рамку для Неизменности как решения проблем с многопоточностью.

GlenPeterson
источник
21
but everything has a side effect- Нет, это не так. Функция, которая принимает какое-то значение и возвращает какое-то другое значение, и ничего не нарушает вне функции, не имеет побочных эффектов и поэтому является поточно-ориентированной. Не важно, что компьютер использует электричество. Мы можем говорить о космических лучах, поражающих ячейки памяти, если хотите, но давайте продолжим рассуждать на практике. Если вы хотите рассмотреть такие вещи, как то, как способ выполнения функции влияет на энергопотребление, это другая проблема, чем поточно-ориентированное программирование.
Роберт Харви,
5
@RobertHarvey - Может быть, я просто использую другое определение побочного эффекта, и мне следовало бы сказать «реальный побочный эффект». Да, у математиков есть функции без побочных эффектов. Код, который выполняется на реальной машине, требует ресурсов машины для выполнения, независимо от того, изменяет ли он данные или нет. Функция в вашем примере помещает свое возвращаемое значение в стек в большинстве машинных архитектур.
ГленПетерсон
1
Если вы действительно можете пройти через это, я думаю, что ваш вопрос лежит в основе этой печально известной бумаги research.microsoft.com/en-us/um/people/simonpj/papers/…
Джимми Хоффа
6
В целях нашего обсуждения я предполагаю, что вы имеете в виду машину с полной Тьюрингом, которая выполняет какой-то четко определенный язык программирования, где детали реализации не имеют значения. Другими словами, не должно иметь значения, что делает стек, если функция, которую я пишу на моем выбранном языке программирования, может гарантировать неизменность в пределах языка. Я не думаю о стеке, когда я программирую на языке высокого уровня, и не должен это делать.
Роберт Харви,
1
@RobertHarvey spoonerism; Monads хе И вы можете собрать это из первых пар страниц. Я упоминаю об этом, потому что в целом в нем подробно описывается техника обработки побочных эффектов практически чистым способом, я почти уверен, что это ответит на вопрос Глена, поэтому разместил его в качестве хорошей заметки для любого, кто найдет этот вопрос в будущее для дальнейшего чтения.
Джимми Хоффа

Ответы:

35

Это странно сформулированный вопрос, который действительно, очень широкий, если на него ответить полностью. Я собираюсь сосредоточиться на прояснении некоторых особенностей, о которых вы спрашиваете.

Неизменность является компромиссом дизайна. Это усложняет некоторые операции (быстрое изменение состояния в больших объектах, частичное создание объектов, сохранение состояния выполнения и т. Д.) В пользу других (упрощение отладки, упрощение рассуждений о поведении программы, отсутствие необходимости беспокоиться о том, что что-то меняется под вами при работе) одновременно и т. д.). Это последний вопрос, который нас волнует в этом вопросе, но я хочу подчеркнуть, что это инструмент. Хороший инструмент, который часто решает больше проблем, чем вызывает (в большинстве современных программ), но не серебряная пуля ... Не то, что меняет внутреннее поведение программ.

Теперь, что это дает вам? Неизменность дает вам одну вещь: вы можете свободно читать неизменяемый объект, не беспокоясь об изменении его состояния под вами (при условии, что он действительно глубоко неизменен ... Наличие неизменяемого объекта с изменяемыми членами обычно нарушает условия сделки). Вот и все. Это освобождает вас от необходимости управлять параллелизмом (с помощью блокировок, моментальных снимков, разделения данных или других механизмов; первоначальный вопрос сосредоточен на блокировках ... Неправильно, учитывая объем вопроса).

Оказывается, что многие вещи читают объекты. IO делает, но сам IO имеет тенденцию плохо обрабатывать параллельное использование. Практически вся обработка выполняется, но другие объекты могут быть изменяемыми, или сама обработка может использовать состояние, не дружественное параллелизму. Копирование объекта является большой скрытой проблемой в некоторых языках, поскольку полная копия (почти) никогда не является атомарной операцией. Здесь вам помогут неизменные объекты.

Что касается производительности, это зависит от вашего приложения. Замки (обычно) тяжелые. Другие механизмы управления параллелизмом работают быстрее, но оказывают большое влияние на ваш дизайн. В целом , высококонкурентный дизайн, который использует неизменяемые объекты (и избегает их слабостей), будет работать лучше, чем высококонкурентный дизайн, который блокирует изменяемые объекты. Если ваша программа слегка параллельна, то это зависит и / или не имеет значения.

Но производительность не должна быть вашей главной заботой. Написание параллельных программ сложно . Отладить параллельные программы сложно . Неизменяемые объекты помогают улучшить качество вашей программы, устраняя возможности для ошибок при реализации управления параллелизмом вручную. Они облегчают отладку, потому что вы не пытаетесь отслеживать состояние в параллельной программе. Они делают ваш дизайн проще и, таким образом, устраняют ошибки там.

Итак, подведем итог: неизменность помогает, но не устраняет проблемы, необходимые для правильной обработки параллелизма. Эта помощь, как правило, широко распространена, но наибольшие выгоды получают с точки зрения качества, а не производительности. И нет, неизменность не освобождает вас от управления параллелизмом в вашем приложении, извините.

Telastyn
источник
+1 Это имеет смысл, но не могли бы вы привести пример, где на глубоко неизменном языке вам все еще нужно беспокоиться о правильном обращении с параллелизмом? Вы заявляете, что вы делаете, но такой сценарий мне не ясен
Джимми Хоффа
@JimmyHoffa На неизменяемом языке вам все равно нужно как-то обновить состояние между потоками. Два самых неизменных языка, которые я знаю (Clojure и Haskell), предоставляют ссылочный тип (атомы и Mvars), которые обеспечивают способ доставки измененного состояния между потоками. Семантика их типов ссылок предотвращает определенные типы ошибок параллелизма, но другие все еще возможны.
каменный металл
@stonemetal интересно, за 4 месяца работы с Haskell я еще даже не слышал о Mvars, я всегда слышал об использовании STM для передачи данных о состоянии параллелизма, которое ведет себя больше как передача сообщений Эрланга, как я думал. Хотя идеальный пример неизменяемости, не решающий параллельные проблемы, о которых я могу подумать, это обновление пользовательского интерфейса, если у вас есть два потока, пытающихся обновить пользовательский интерфейс с различными версиями данных, один из них может быть новее, и поэтому вам нужно получить второе обновление, чтобы у вас было состояние гонки, где вы должны как-то гарантировать последовательность .. Интересная мысль .. Спасибо за подробности
Джимми Хоффа
1
@jimmyhoffa - Наиболее распространенный пример - IO. Даже если язык неизменен, ваша база данных / веб-сайт / файл - нет. Еще ваша типичная карта / уменьшить. Неизменяемость означает, что агрегация карты более надежна, но вам все равно нужно обрабатывать координацию «как только все карты будут сделаны параллельно, уменьшите».
Теластин
1
@JimmyHoffa: MVars - это низкоуровневый изменяемый примитив параллелизма (технически неизменяемая ссылка на изменяемое место хранения), не слишком отличающийся от того, что вы видели бы в других языках; тупики и условия гонки очень возможны. STM - это высокоуровневая абстракция параллелизма для изменяемой разделяемой памяти без блокировок (очень отличающаяся от передачи сообщений), которая допускает составные транзакции без возможности взаимоблокировок или условий гонки. Неизменяемые данные просто поточнобезопасны, больше нечего об этом сказать.
CA McCann
13

Функция, которая принимает какое-то значение и возвращает какое-то другое значение, и ничего не нарушает вне функции, не имеет побочных эффектов и поэтому является поточно-ориентированной. Если вы хотите рассмотреть такие вещи, как способ выполнения функции влияет на энергопотребление, это другая проблема.

Я предполагаю, что вы имеете в виду машину, полную по Тьюрингу, которая выполняет какой-то четко определенный язык программирования, где детали реализации не имеют значения. Другими словами, не должно иметь значения, что делает стек, если функция, которую я пишу на моем выбранном языке программирования, может гарантировать неизменность в пределах языка. Я не думаю о стеке, когда я программирую на языке высокого уровня, и не должен это делать.

Чтобы проиллюстрировать, как это работает, я собираюсь предложить несколько простых примеров на C #. Чтобы эти примеры были правдой, мы должны сделать пару предположений. Во-первых, компилятор следует спецификации C # без ошибок, а во-вторых, что он создает правильные программы.

Допустим, я хочу простую функцию, которая принимает коллекцию строк и возвращает строку, которая является объединением всех строк в коллекции, разделенных запятыми. Простая, наивная реализация в C # может выглядеть так:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    string result = string.Empty;
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result += s;
        else
            result += ", " + s;
    }
    return result;
} 

Этот пример неизменен, prima facie. Откуда я это знаю? Потому что stringобъект неизменен. Однако реализация не идеальна. Поскольку он resultявляется неизменным, каждый раз в цикле необходимо создавать новый строковый объект, заменяя исходный объект, на который resultуказывает. Это может отрицательно повлиять на скорость и оказать давление на сборщик мусора, поскольку он должен очистить все эти дополнительные строки.

Теперь, допустим, я делаю это:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    var result = new StringBuilder();
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result.Append(s);
        else
            result.Append(", " + s);
    }
    return result.ToString();
} 

Обратите внимание, что я заменил string resultизменяемый объект StringBuilder. Это намного быстрее, чем в первом примере, потому что новая строка не создается каждый раз в цикле. Вместо этого объект StringBuilder просто добавляет символы из каждой строки в коллекцию символов и выводит все в конце.

Является ли эта функция неизменной, даже если StringBuilder изменчив?

Да, это. Зачем? Поскольку каждый раз, когда вызывается эта функция, создается новый StringBuilder только для этого вызова. Итак, теперь у нас есть чистая функция, которая является поточно-ориентированной, но содержит изменяемые компоненты.

Но что, если я сделал это?

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;

    public string ConcatenateWithCommas(ImmutableList<string> list)
    {
        foreach (string s in list)
        {
            if (isFirst)
                result.Append(s);
            else
                result.Append(", " + s);
        }
        return result.ToString();
    } 
}

Этот метод потокобезопасен? Нет, это не так. Зачем? Потому что класс теперь держит состояние, от которого зависит мой метод. Теперь в методе присутствует условие гонки: один поток может измениться IsFirst, но другой поток может выполнить первый Append(), и в этом случае у меня теперь есть запятая в начале моей строки, которой не должно быть.

Почему я могу захотеть сделать это так? Ну, я мог бы хотеть, чтобы потоки накапливали строки в моем, resultнезависимо от порядка или в порядке поступления потоков. Может, это регистратор, кто знает?

Во всяком случае, чтобы исправить это, я поместил lockзаявление во внутренности метода.

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;
    private static object locker = new object();

    public string AppendWithCommas(ImmutableList<string> list)
    {
        lock (locker)
        {
            foreach (string s in list)
            {
                if (isFirst)
                    result.Append(s);
                else
                    result.Append(", " + s);
            }
            return result.ToString();
        }
    } 
}

Теперь это снова потокобезопасно.

Единственный способ, которым мои неизменяемые методы могут быть не в состоянии быть потокобезопасными, - это если метод каким-то образом пропускает часть своей реализации. Может ли это случиться? Нет, если компилятор верен, а программа верна. Будут ли мне когда-нибудь нужны блокировки для таких методов? Нет.

Для примера того, как реализация может быть утечка в сценарии параллелизма, смотрите здесь .

Роберт Харви
источник
2
Если я не ошибаюсь, поскольку a Listявляется изменяемым, в первой функции, которую вы объявили «чистой», другой поток может удалить все элементы из списка или добавить еще несколько, пока он находится в цикле foreach. Не уверен, как это сыграло бы с IEnumeratorсуществом while(iter.MoveNext()), но если оно не IEnumeratorявляется неизменным (сомнительным), то это грозило бы разрушить цикл foreach.
Джимми Хоффа
Правда, вы должны предположить, что коллекция никогда не записывается, пока потоки читают из нее. Это было бы допустимым предположением, если бы каждый поток, вызывающий метод, строил свой собственный список.
Роберт Харви
Я не думаю, что вы можете назвать его «чистым», когда в нем есть тот изменяемый объект, который он использует по ссылке. Если он получил IEnumerable, вы можете сделать это заявление, потому что вы не можете добавлять или удалять элементы из IEnumerable, но тогда это может быть массив или список, переданный как IEnumerable, так что контракт IEnumerable не гарантирует никакой формы. чистоты Реальная техника, чтобы сделать эту функцию чистой, была бы неизменяемостью с передачей за копией, C # не делает этого, поэтому вам придется копировать List прямо тогда, когда функция его получает; но единственный способ сделать это с помощью foreach на нем ...
Джимми Хоффа
1
@JimmyHoffa: Черт возьми, ты одержим меня этой проблемой курицы и яйца! Если вы видите решение где-либо, пожалуйста, дайте мне знать.
Роберт Харви
1
Только что наткнулся на этот ответ сейчас, и это одно из лучших объяснений по теме, с которой я сталкивался, примеры очень лаконичны и действительно облегчают поиск. Благодарность!
Стивен Бирн
4

Я не уверен, что понял ваши вопросы.

ИМХО ответ - да. Если все ваши объекты неизменны, то вам не нужны замки. Но если вам нужно сохранить состояние (например, вы реализуете базу данных или вам нужно агрегировать результаты из нескольких потоков), тогда вам нужно использовать изменчивость и, следовательно, также блокировки. Неизменность устраняет необходимость в блокировках, но обычно вы не можете позволить себе иметь полностью неизменные приложения.

Ответ на часть 2 - блокировки должны быть всегда медленнее, чем отсутствие блокировок.

Maros
источник
3
Вторая часть спрашивает: «Каков компромисс производительности между замками и неизменяемыми структурами?» Это, вероятно, заслуживает своего собственного вопроса, если это даже ответственно.
Роберт Харви
4

Инкапсуляция связанного состояния в одной изменяемой ссылке на неизменяемый объект может сделать возможным выполнение многих видов изменения состояния без блокировки с использованием шаблона:

do
{
   oldState = someObject.State;
   newState = oldState.WithSomeChanges();
} while (Interlocked.CompareExchange(ref someObject.State, newState, oldState) != oldState;

Если оба потока пытаются обновить someObject.stateодновременно, оба объекта прочитают старое состояние и определят, каким будет новое состояние без изменений друг друга. Первый поток, выполняющий CompareExchange, будет хранить то, что, по его мнению, должно быть в следующем состоянии. Второй поток обнаружит, что состояние больше не соответствует тому, что он ранее прочитал, и, таким образом, пересчитает правильное следующее состояние системы с изменениями первого потока, вступившими в силу.

Этот шаблон имеет преимущество в том, что поток, который становится отложенным, не может блокировать продвижение других потоков. Это имеет еще одно преимущество, заключающееся в том, что даже при сильном конфликте некоторые потоки всегда будут прогрессировать. Однако у него есть недостаток, заключающийся в том, что при наличии конкуренции множество потоков могут тратить много времени на выполнение работы, которую они в конечном итоге отбрасывают. Например, если все 30 потоков на отдельных процессорах одновременно пытаются изменить объект, один из них преуспеет с первой попытки, один - со второй, один - с третьей и т. Д., Так что каждый поток в среднем завершает выполнение около 15 попыток. обновить свои данные. Использование «консультативной» блокировки может значительно улучшить ситуацию: прежде чем поток попытается выполнить обновление, он должен проверить, установлен ли индикатор «конкуренции». Если так, он должен получить блокировку перед обновлением. Если поток делает несколько неудачных попыток обновления, он должен установить флаг конкуренции. Если поток, который пытается получить блокировку, обнаруживает, что никто больше не ждет, он должен сбросить флаг конфликта. Обратите внимание, что блокировка здесь не требуется для «правильности»; код будет работать правильно даже без него. Цель блокировки - минимизировать время, затрачиваемое кодом на операции, которые вряд ли будут успешными.

Supercat
источник
4

Вы начинаете с

Очевидно, что неизменность сводит к минимуму необходимость блокировок в многопроцессорном программировании.

Неправильно. Вы должны внимательно прочитать документацию для каждого класса, который вы используете. Например, const std :: string в C ++ не является потокобезопасным. Неизменяемые объекты могут иметь внутреннее состояние, которое изменяется при доступе к ним.

Но вы смотрите на это с совершенно неправильной точки зрения. Неважно, является ли объект неизменным или нет, важно то, измените ли вы его. То, что вы говорите, все равно что сказать: «Если вы никогда не сдадите экзамен по вождению, вы никогда не потеряете свои водительские права за вождение в нетрезвом виде». Правда, но, скорее, не хватает сути.

Теперь в примере кода кто-то написал с функцией с именем «ConcatenateWithCommas»: если бы ввод был изменяемым и вы использовали блокировку, что бы вы получили? Если кто-то еще попытается изменить список, пока вы пытаетесь объединить строки, блокировка может предотвратить сбой. Но вы все еще не знаете, объединяете ли вы строки до или после того, как другой поток их изменил. Так что ваш результат довольно бесполезен. У вас есть проблема, которая не связана с блокировкой и не может быть исправлена ​​с помощью блокировки. Но затем, если вы используете неизменяемые объекты, а другой поток заменяет весь объект новым, вы используете старый объект, а не новый объект, поэтому ваш результат бесполезен. Вы должны думать об этих проблемах на реальном функциональном уровне.

gnasher729
источник
2
const std::stringплохой пример и немного красной сельди. Строки C ++ являются изменяемыми и constне могут гарантировать неизменность в любом случае. Все, что он делает, это говорит, что только constфункции могут быть вызваны. Тем не менее, эти функции могут по-прежнему изменять внутреннее состояние и constмогут быть отброшены. Наконец, существует та же проблема, что и на любом другом языке: только то, что моя ссылка такова const, не означает, что ваша ссылка тоже. Нет, должна использоваться действительно неизменная структура данных.