Когда вы сталкивались с проблемой остановки в полевых условиях?[закрыто]
https://stackoverflow.com/questions/235984
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Когда вы лично сталкивались с проблема с остановкой в поле?Это может произойти, когда коллега/начальник предложил решение, которое нарушает фундаментальные ограничения вычислений, или когда вы сами поняли, что проблему, которую вы пытались решить, на самом деле решить невозможно.
Последний раз я придумал это, когда изучал программы проверки типов.Наш класс понял, что невозможно написать идеальную программу проверки типов (которая принимала бы все программы, работающие без ошибок типов, и отклоняла бы все программы, запускающиеся с ошибками типов), поскольку это фактически решило бы проблему остановки. .Другой случай произошел, когда мы в том же классе поняли, что на этапе проверки типов невозможно определить, произойдет ли когда-либо деление на ноль, поскольку проверка того, является ли число во время выполнения нулем, также является задачей. версия проблемы остановки.
Решение
Мне буквально была назначена проблема с остановкой, как в "написать подключаемый модуль монитора, чтобы определить, постоянно ли отключен хост". Шутки в сторону? Хорошо, так что я просто дам ему порог. " Нет, потому что он может вернуться позже. "
Последовало много теоретического изложения.
Другие советы
Несколько лет назад я помню, как читал обзор (кажется, в журнале Byte) продукта под названием Basic Infinite Loop Finder или BILF.Предполагалось, что BILF просканирует исходный код Microsoft Basic и найдет все незавершенные циклы.Он утверждал, что может найти в коде любые бесконечные циклы.
Рецензент был достаточно сообразителен, чтобы указать, что для того, чтобы эта программа работала во всех случаях, ей необходимо решить проблему остановки, и зашел так далеко, что предоставил математическое доказательство того, почему она не может работать во всех случаях.
В следующем номере они опубликовали письмо представителя компании, в котором объясняется, что проблема будет исправлена в следующем релизе.
Обновлять: Я наткнулся на изображение статьи на imgur.Я вспомнил не тот журнал.Это были Creative Computing, а не Byte.В остальном все примерно так, как я запомнил.
Вы можете увидеть его версию в высоком разрешении на imgur.
В проекте, над которым я сейчас работаю , есть неразрешимые проблемы. Это генератор модульных тестов, поэтому в общем случае он пытается ответить на вопрос " что делает эта программа " . Который является примером проблемы остановки. Другая проблема, которая возникла во время разработки, заключается в том, что " дают две (тестирующие) функции одинаковому " ? Или даже " порядок этих двух вызовов (утверждений) имеет значение " ?
Что интересно в этом проекте, так это то, что, хотя вы не можете ответить на эти вопросы в всех ситуациях, вы можете найти умные решения, которые решают проблему на 90% время, которое для этого домена на самом деле очень хорошо.
Другие инструменты, которые пытаются рассуждать о другом коде, такие как оптимизация компиляторов / интерпретаторов, инструменты статического анализа кода, даже инструменты рефакторинга, могут столкнуться (и поэтому вынуждены будут искать обходные пути) с проблемой остановки.
Пример 1. Сколько страниц в моем отчете?
Когда я учился программировать, я занимался созданием инструмента для распечатки красивых отчетов из данных. Очевидно, я хотел, чтобы он был действительно гибким и мощным, чтобы генераторы отчетов заканчивали работу всех генераторов отчетов.
Определение отчета оказалось настолько гибким, что завершилось по Тьюрингу. Он может смотреть на переменные, выбирать между альтернативами, использовать циклы для повторения.
Я определил встроенную переменную N - количество страниц в экземпляре отчета, чтобы вы могли поместить строку, в которой говорилось "страница n из N". на каждой странице. Я сделал два прохода, первый для подсчета страниц (в течение которого N был установлен на ноль), а второй для их фактического генерирования, используя N, полученный из первого прохода.
Иногда при первом проходе вычисляется N, а затем при втором проходе генерируется другое количество страниц (потому что теперь ненулевое N изменило бы работу отчета). Я пытался делать проходы итеративно, пока N не успокоился. Тогда я понял, что это безнадежно, потому что, если это не успокоится?
Это приводит к вопросу: «Могу ли я по крайней мере обнаружить и предупредить пользователя, если итерация никогда не остановится на стабильном значении количества страниц, создаваемых их отчетом?» " К счастью, к этому времени я заинтересовался чтением о Тьюринге, Годеле, вычислимости и т. Д. И установил связь.
Спустя годы я заметил, что MS Access иногда печатает "Страница 6 из 5", что поистине изумительно.
Пример 2. Компиляторы C ++
Процесс компиляции включает в себя расширение шаблонов. Определения шаблонов могут быть выбраны из нескольких специализаций (достаточно хороших, чтобы служить в качестве «cond»), и они также могут быть рекурсивными. Таким образом, это полная (чисто функциональная) метасистема Тьюринга, в которой определения шаблонов являются языком, типы являются значениями, а компилятор действительно является интерпретатором. Это был несчастный случай.
Следовательно, невозможно исследовать какую-либо конкретную программу на C ++ и сказать, может ли компилятор в принципе завершиться успешной компиляцией программы.
Поставщики компиляторов обходят это, ограничивая глубину стека рекурсивного шаблона. Вы можете настроить глубину в g ++.
Много-много месяцев назад я помогал консультанту нашей компании, который внедрял очень сложную рельсовую систему для перемещения корзин с металлическими деталями внутрь и из доменной печи на 1500 градусов. Сама трасса представляла собой довольно сложный «мини-рельс» в цехе, который пересекался в нескольких местах. Несколько моторизованных поддонов перевозили корзины деталей по расписанию. Было очень важно, чтобы двери печи были открыты как можно быстрее.
Поскольку завод работал на полную мощность, консультант не смог запустить свое программное обеспечение в режиме «реального времени» для проверки своих алгоритмов планирования. Вместо этого он написал симпатичный графический симулятор. Пока мы наблюдали за перемещением виртуальных паллет по его экранной схеме, я спросил: "Как вы узнаете, есть ли у вас какие-либо конфликты при планировании?"
Его быстрый ответ "Легко - симуляция никогда не остановится".
Сложный статический анализ кода может столкнуться с проблемой остановки.
Например, если виртуальная машина Java может доказать, что часть кода никогда не получит доступ к индексу массива вне пределов, она может пропустить эту проверку и работать быстрее. Для некоторого кода это возможно; поскольку это становится более сложным, это становится проблемой остановки.
Это все еще проблема для шейдеров в приложениях с графическим процессором. Если шейдер имеет бесконечный цикл (или очень длинный расчет), должен ли драйвер (через некоторое время) остановить его, уничтожить фрагмент или просто запустить? Для игр и других коммерческих вещей, первое, вероятно, то, что вы хотите, но для научных вычислений / вычислений на GPU, второе - то, что вам нужно. Хуже того, некоторые версии окон предполагают, что, поскольку графический драйвер некоторое время не отвечает, он убивает его, что искусственно ограничивает вычислительную мощность при выполнении вычислений на графическом процессоре.
Для приложения нет API, который бы управлял поведением драйвера или устанавливал время ожидания, или что-то в этом роде, и, конечно, у драйвера не было способа определить, завершится ли ваш шейдер или нет.
Я не знаю, улучшилась ли эта ситуация в последнее время, но я хотел бы знать.
Другой распространенной версией этого является "нам нужно устранить любые взаимоблокировки в нашем многопоточном коде". Совершенно разумный запрос с точки зрения управления, но для предотвращения взаимных блокировок в общем случае вам необходимо проанализировать каждое возможное состояние блокировки, в которое может войти программное обеспечение, что неудивительно, что эквивалентно проблеме остановки.
Есть способы частично "решить" взаимоблокировки в сложной системе путем наложения другого слоя поверх блокировки (как определенный порядок сбора данных), но эти методы не всегда применимы.
<Ч>Почему это эквивалентно проблеме остановки:
Представьте, что у вас есть две блокировки, A и B, и два потока, X и Y. Если поток X имеет блокировку A и также хочет блокировку B, а поток Y имеет блокировку B и тоже хочет A, то у вас есть тупик ,
Если X и Y имеют доступ к A и B, то единственный способ убедиться, что вы никогда не попадете в плохое состояние, - это определить все возможные пути, которые каждый поток может пройти через код, и порядок в котором они могут приобрести и удерживать замки во всех этих случаях. Затем вы определяете, могут ли два потока получить более одной блокировки в другом порядке.
Но определение всех возможных путей, которые каждый поток может пройти через код, эквивалентно (в общем случае) проблеме остановки.
Система тестирования Perl поддерживает счетчик тестов. Вы либо помещаете количество тестов, которые вы собираетесь запустить, в верхней части программы, либо заявляете, что не собираетесь их отслеживать. Это предохраняет от преждевременного выхода из вашего теста, но есть и другие охранники, так что это не так уж важно.
Время от времени кто-то пытается написать программу для подсчета количества тестов для вас. Это, конечно, побеждено простой петлей. В любом случае они продвигаются вперед, делая все более и более сложные трюки, чтобы попытаться обнаружить петли и угадать, сколько будет повторений и решить проблему остановки. Обычно они заявляют, что это должно быть "достаточно хорошо".
Однажды я работал над проектом интеграции в домене банкоматов (банкоматов). Клиент попросил меня сгенерировать отчет из моей системы для транзакций, отправленных переключателем страны, которые не были получены моей системой !!
Я нашел статью в Беркли: Лупер:Легкое обнаружение бесконечных циклов во время выполнения http://www.eecs.berkeley.edu/~jburnim/pubs/BurnimJalbertStergiouSen-ASE09.pdf
LOOPER может быть полезен, поскольку большинство бесконечных циклов являются тривиальными ошибками.Однако этот документ даже не упоминается проблема остановки!
Что они говорят о своих ограничениях?
[LOOPER] обычно не может рассуждать о циклах, где нет прекращения зависит от особенностей мутации кучи в каждой итерации цикла.Это потому, что наша символическая казнь консервативна в конкретизация указателей, и наши символические рассуждения недостаточно мощный. Мы считаем, что объединение наших методов с анализом формы и более мощным инвариантным поколением и доказывание будет ценной будущей работой.
Другими словами, «проблема будет исправлена в следующем выпуске».
Из Обзора функций визуального редактора (Eclipse) :
Визуальный редактор Eclipse (VE) может быть используется для открытия любого .java файла. Тогда анализирует исходный код Java для визуальных бобов. ...
Некоторые инструменты визуального редактирования предоставить визуальную модель кода, которая этот конкретный визуальный инструмент сам по себе имеет генерироваться. Последующее прямое редактирование исходного кода может помешать визуальный инструмент от разбора кода и построение модели.
Eclipse VE, однако, ... может быть используется для редактирования графического интерфейса с нуля, или из файлов Java, которые были «жестко» или встроенный в другой визуальный инструмент. Исходный файл может либо обновляться с использованием графического Средство просмотра, дерево JavaBeans или свойства просмотреть или можно редактировать напрямую с помощью Редактор исходного кода.
Может быть, я должен сейчас придерживаться Матисса.
Не имеет отношения, вот кто-то просит проблема остановки в Eclipse.
Честно говоря, домен VE довольно ограничен, и он, вероятно, не сойдет с ума от таких хитрых вещей, как рефлексия. Тем не менее утверждение о создании графического интерфейса пользователя из любого Java-файла кажется недействительным.
" Как вы можете быть уверены, что ваш код на 100% не содержит ошибок? "
