Как безопасность потоков может быть обеспечена языком программирования, аналогичным тому, как в Java и C # обеспечивается безопасность памяти?

10

Java и C # обеспечивают безопасность памяти, проверяя границы массивов и разыменования указателей.

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

mrpyo
источник
3
Вы можете быть заинтересованы в том, что делает Rust: Бесстрашный параллелизм с Rust
Винсент
2
Сделайте все неизменным или сделайте все асинхронным с безопасными каналами. Вы также можете быть заинтересованы в Go и Erlang .
Theraot
@Theraot "сделай все асинхронным с безопасными каналами" - хотелось бы, чтобы ты уточнил это.
mrpyo
2
@mrpyo вы бы не выставляли процессы или потоки, каждый вызов - это обещание, все выполняется одновременно (с планированием их выполнения и созданием / пулированием системных потоков за кулисами по мере необходимости), а логика, защищающая состояние, находится в механизмах который передает информацию вокруг ... среда выполнения может автоматически сериализоваться по расписанию, и будет существовать стандартная библиотека с поточно-ориентированным решением для более нюансов, в частности, необходим производитель / потребитель и агрегаты.
Theraot
2
Кстати, есть еще один возможный подход: транзакционная память .
Theraot

Ответы:

14

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

Таким образом, чтобы предотвратить гонки, вы должны сделать одно или несколько из этих условий неверными.

Различные подходы затрагивают различные аспекты. Функциональное программирование подчеркивает неизменность, которая устраняет изменчивость. Блокировка / атомика убирают одновременность. Аффинные типы удаляют псевдонимы (Rust удаляет изменяемые псевдонимы). Актерские модели обычно удаляют псевдонимы.

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

Недостатком этих различных механизмов является то, что они ограничивают программы, которые вы можете написать. Чем более тупо ограничение, тем меньше программ. Так что никакие псевдонимы или изменчивость не работают, и их легко рассуждать, но они очень ограничены.

Вот почему Руст вызывает такой ажиотаж. Это инженерный язык (в отличие от академического), который поддерживает псевдонимы и изменчивость, но проверяет компилятор, что они не встречаются одновременно. Хотя это и не идеал, он позволяет безопасно писать больший класс программ, чем многие его предшественники.

Alex
источник
11

Java и C # обеспечивают безопасность памяти, проверяя границы массивов и разыменования указателей.

Важно сначала подумать о том, как это делают C # и Java. Они делают это путем преобразования неопределенного поведения в C или C ++ в определенное поведение: сбой программы . Нулевые разыменования и исключения индекса массива никогда не должны быть обнаружены в правильной программе на C # или Java; они не должны происходить в первую очередь, потому что в программе не должно быть этой ошибки.

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

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

Следующая проблема, с которой мы сталкиваемся в связи с вашим вопросом, заключается в том, что «гоночные условия», в отличие от тупиков, трудно обнаружить. Помните, что то, что мы ищем в безопасности потоков, это не устранение гонок . Мы стремимся сделать программу правильной, независимо от того, кто выиграет гонку ! Проблема с условиями гонки состоит не в том, что два потока работают в неопределенном порядке, и мы не знаем, кто собирается закончить первым. Проблема с условиями гонки заключается в том, что разработчики забывают, что некоторые порядки завершения потоков возможны, и не учитывают эту возможность.

Таким образом, ваш вопрос в основном сводится к тому, "есть ли способ, которым язык программирования может гарантировать, что моя программа верна?" и ответ на этот вопрос на практике - нет.

До сих пор я только критиковал ваш вопрос. Позвольте мне попытаться переключить передачи здесь и обратиться к духу вашего вопроса. Есть ли выбор, который могли бы сделать разработчики языка, чтобы смягчить ужасную ситуацию с многопоточностью?

Ситуация действительно ужасна! Правильно получить многопоточный код, особенно на слабых архитектурах моделей памяти, очень и очень сложно. Поучительно подумать, почему это сложно:

  • Сложно рассуждать о нескольких потоках управления в одном процессе. Одна нить достаточно сложна!
  • Абстракции становятся чрезвычайно негерметичными в многопоточном мире. В однопоточном мире нам гарантируется, что программы ведут себя так, как будто они запускаются по порядку, даже если они на самом деле не запускаются по порядку. В многопоточном мире это уже не так; Оптимизации, которые были бы невидимы в одном потоке, становятся видимыми, и теперь разработчик должен понять эти возможные оптимизации.
  • Но это становится хуже. Спецификация C # говорит, что реализация НЕ обязана иметь согласованный порядок чтения и записи, который может быть согласован всеми потоками . Представление о том, что вообще существуют «гонки» и что есть явный победитель, на самом деле не соответствует действительности! Рассмотрим ситуацию, когда есть две записи и две операции чтения некоторых переменных во многих потоках. В разумном мире мы можем подумать: «Ну, мы не можем знать, кто победит в гонках, но, по крайней мере, будет гонка, и кто-то победит». Мы не в этом разумном мире. C # позволяет нескольким потокам расходиться во мнениях относительно порядка, в котором происходит чтение и запись; не обязательно существует непротиворечивый мир, который все наблюдают.

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

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

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

Этот последний пункт требует дальнейшего объяснения. Под «компонуемым» я подразумеваю следующее:

Предположим, мы хотим вычислить int с учетом double. Мы пишем правильную реализацию вычисления:

int F(double x) { correct implementation here }

Предположим, что мы хотим вычислить строку с использованием int:

string G(int y) { correct implementation here }

Теперь, если мы хотим вычислить строку, заданную двойным:

double d = whatever;
string r = G(F(d));

G и F могут быть составлены в правильное решение более сложной проблемы.

Но у замков нет этого свойства из-за тупиков. Правильный метод M1, который принимает блокировки в порядке L1, L2, и правильный метод M2, который принимает блокировки в порядке L2, L1, нельзя использовать в одной и той же программе без создания неверной программы. Блокировки делают так, что вы не можете сказать, что «каждый отдельный метод является правильным, так что все это правильно».

Итак, что мы можем сделать как дизайнеры языка?

Во-первых, не ходи туда. Несколько потоков управления в одной программе - плохая идея, а совместное использование памяти между потоками - плохая идея, поэтому не помещайте ее в язык или среду выполнения.

Это, очевидно, не стартер.

Давайте обратим наше внимание на более фундаментальный вопрос: почему у нас есть несколько потоков в первую очередь? Есть две основные причины, и они часто связаны в одно и то же, хотя они очень разные. Они объединены, потому что они оба об управлении задержкой.

  • Мы неправильно создаем потоки для управления задержкой ввода-вывода. Нужно написать большой файл, получить доступ к удаленной базе данных, что угодно, создать рабочий поток, а не блокировать ваш поток пользовательского интерфейса.

Плохая идея. Вместо этого используйте однопоточную асинхронность через сопрограммы. C # делает это красиво. Ява, не очень хорошо. Но это основной способ, которым современные разработчики языков помогают решить проблему с многопоточностью. awaitОператор в C # ( под влиянием F # асинхронные рабочие процессы и предшествующий уровень техники) в настоящее время включены во все более и более языках.

  • Мы создаем потоки, чтобы насыщать простаивающие процессоры вычислительной нагрузкой. По сути, мы используем потоки в качестве легких процессов.

Языковые дизайнеры могут помочь, создавая языковые функции, которые хорошо работают с параллелизмом. Подумайте, например, как естественным образом распространяется LINQ на PLINQ. Если вы разумный человек, и вы ограничиваете свои операции TPL ограниченными процессором операциями, которые являются высокопараллельными и не разделяют память, вы можете получить здесь большие победы.

Что еще мы можем сделать?

  • Заставьте компилятор выявлять самые глупые ошибки и превращать их в предупреждения или ошибки.

C # не позволяет вам ждать в замке, потому что это рецепт для взаимоблокировок. C # не позволяет вам блокировать тип значения, потому что это всегда неправильно; Вы блокируете коробку, а не значение. C # предупреждает вас, если вы используете псевдоним volatile, потому что псевдоним не навязывает семантику получения / выпуска. Существует гораздо больше способов, с помощью которых компилятор может обнаружить общие проблемы и предотвратить их.

  • Разработайте «яму качества», где самый естественный способ сделать это также самый правильный путь.

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

  • Огромное количество времени и усилий Microsoft Research направлено на то, чтобы добавить программную транзакционную память в C # -подобный язык, и они так и не смогли добиться достаточной производительности, чтобы включить ее в основной язык.

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

  • В другом ответе уже упоминалась неизменность. Если у вас есть неизменность в сочетании с эффективными сопрограммами, вы можете встроить такие функции, как модель актора, прямо в ваш язык; например, Эрланг.

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

  • Сделайте так, чтобы третьи лица могли легко писать хорошие анализаторы

После того, как я работал в Microsoft над Roslyn, я работал в Coverity, и одна из вещей, которые я сделал, - это получить интерфейс анализатора с использованием Roslyn. Благодаря точному лексическому, синтаксическому и семантическому анализу, предоставленному Microsoft, мы могли бы затем сосредоточиться на тяжелой работе по написанию детекторов, которые обнаружили общие проблемы многопоточности.

  • Поднять уровень абстракции

Фундаментальная причина, по которой у нас есть гонки и тупики и все такое, заключается в том, что мы пишем программы, которые говорят, что делать , и оказывается, что мы все дерьмо пишем императивные программы; компьютер делает то, что вы говорите, а мы говорим, чтобы он делал неправильные вещи. Многие современные языки программирования все больше и больше относятся к декларативному программированию: скажите, какие результаты вы хотите, и позвольте компилятору найти эффективный, безопасный и правильный способ достижения этого результата. Снова подумайте о LINQ; мы хотим, чтобы вы сказали from c in customers select c.FirstName, что выражает намерение . Позвольте компилятору выяснить, как писать код.

  • Используйте компьютеры для решения компьютерных проблем.

Алгоритмы машинного обучения в некоторых задачах намного лучше, чем алгоритмы с ручным кодированием, хотя, конечно, есть много компромиссов, включая правильность, время, затраченное на обучение, ошибки, вызванные плохим обучением, и так далее. Но вполне вероятно, что очень многие задачи, которые мы в настоящее время кодируем «вручную», скоро станут доступными для машинно-генерируемых решений. Если люди не пишут код, они не пишут ошибки.

Извините, это было немного бессвязно; Это огромная и сложная тема, и за 20 лет, в течение которых я следил за прогрессом в этой проблемной области, в сообществе ЛП не было достигнуто четкого консенсуса.

Эрик Липперт
источник
«Таким образом, ваш вопрос в основном сводится к тому,« есть ли способ, которым язык программирования может гарантировать, что моя программа верна? », И ответ на этот вопрос на практике - нет». - на самом деле, это вполне возможно - это называется формальной проверкой, и хотя это неудобно, я уверен, что это обычно делается на критически важном программном обеспечении, поэтому я бы не назвал это непрактичным. Но вы, будучи языковым дизайнером, наверняка знаете это ...
mrpyo
6
@mrpyo: я хорошо знаю. Есть много проблем. Первое: однажды я посетил официальную конференцию по верификации, на которой исследовательская группа MSFT представила потрясающий новый результат: они смогли расширить свою технику для проверки многопоточных программ длиной до двадцати строк и запустить верификатор менее чем за неделю. Это была интересная презентация, но бесполезная для меня; У меня была программа на 20 миллионов строк для анализа.
Эрик Липперт
@mrpyo: Во-вторых, как я уже упоминал, большая проблема с блокировками заключается в том, что программа, созданная из поточно-ориентированных методов, не обязательно является поточно-ориентированной. Формальная проверка отдельных методов не обязательно помогает, а анализ всей программы сложен для нетривиальных программ.
Эрик Липперт
6
@mrpyo: В-третьих, большая проблема с формальным анализом заключается в том, что, в основном, мы делаем? Мы представляем спецификацию предусловий и постусловий, а затем проверяем, соответствует ли программа этой спецификации. Большой; в теории это вполне выполнимо. На каком языке написана спецификация? Если есть однозначный, проверяемый язык спецификации , то давайте просто написать все наши программы на этом языке , и компилировать что . Почему бы нам не сделать это? Потому что оказывается, что действительно трудно писать правильные программы и на языке спецификаций!
Эрик Липперт
2
Возможен анализ заявки на корректность с использованием предварительных условий / постусловий (например, с использованием контрактов на кодирование). Однако такой анализ возможен только при условии, что условия являются составными, а блокировки - нет. Также отмечу, что написание программы таким способом, который позволяет проводить анализ, требует тщательной дисциплины. Например, приложения, которые не в состоянии строго придерживаться принципа подстановки Лискова, имеют тенденцию сопротивляться анализу.
Брайан