Когда Вы натолкнулись на проблему остановки в поле? [закрытый]

"Как можно уверить меня код, 100% свободны от ошибок?"

Я однажды работал над проектом интеграции в домене ATM (Automated Teller Machines). Клиент запросил меня генерировать отчет от своей системы для транзакций, отправленных переключателем страны, которые не были получены моей системой!!

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

существуют способы частично "решить" мертвые блокировки в сложной системе путем наложения другого слоя сверх блокировки (как определенный порядок приобретения), но эти методы не всегда применимы.

, Почему это эквивалентно проблеме остановки:

Предполагают, что у Вас есть две блокировки, A и B, и два потока, X и Y. Если поток X имеет блокировку A и хочет блокировку B также, и поток Y имеет блокировку B и хочет также, то у Вас есть мертвая блокировка.

, Если оба X и Y имеют доступ и к A и к B, то единственный способ гарантировать, чтобы Вы никогда не входили в плохое состояние, состоит в том, чтобы определить все возможные пути, которые каждый поток может взять через код и порядок, в котором они могут получить и содержать, привязывает все те случаи. Тогда Вы определяете, могут ли два потока когда-либо получать, больше чем один привязывает различный порядок.

, Но, определяя все возможные пути, которые каждый поток может взять через код, (в общем случае) эквивалентен проблеме остановки.

Система тестирования Perl поддерживает тестовый счетчик. Вы или помещаете количество тестов, которые Вы собираетесь запустить наверху программы, или Вы объявляете, что не собираетесь отслеживать его. Это принимает меры против Вашего теста, выходящего преждевременно, но существует другая защита, таким образом, это не все это важное.

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

Вот особенно тщательно продуманный пример.

Сложный статический анализ кода может столкнуться с проблемой остановки.

, Например, если виртуальная машина Java может доказать, что часть кода никогда не будет получать доступ к индексу массива за пределы, это может опустить ту проверку и работать быстрее. Для некоторого кода это возможно; поскольку это становится более сложным, это становится проблемой остановки.

Много много лун назад, я помогал консультанту для нашей компании, который реализовывал очень сложную железнодорожную систему для перемещения корзин металлических деталей в и из доменной печи на 1 500 градусов. Сама дорожка была довольно сложной 'мини-сортировочной станция' в цехе, который пересек себя в нескольких местах. Несколько моторизованных панелей доставили бы корзины в челноке частей вокруг согласно расписанию. Было очень важно, чтобы печные двери были открыты в течение максимально короткого времени.

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

Его быстрый ответ, "Легкий - моделирование никогда не будет останавливаться".

Пример 1. Сколько страниц в моем отчете?

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

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

я определил встроенную переменную N, число страниц в экземпляре отчета, таким образом, Вы могли поместить строку, которая сказала "страницу n N" на каждой странице. Я сделал две передачи, первая для подсчета страниц (во время которого N был обнулен), и второе для фактической генерации их, с помощью N, полученного из первой передачи.

Иногда первая передача вычисляла бы N, и затем вторая передача генерирует различное число страниц (потому что теперь ненулевой N изменил бы то, что отчет сделал). Я пытался делать передачи многократно до успокоенного N. Тогда я понял, что это было безнадежно, потому что, что, если это не успокоилось?

Это тогда приводит к вопросу, "Я могу, по крайней мере, обнаружить и предупредить пользователя, если повторение никогда не собирается обосновываться на стабильном значении для числа страниц, их отчет производит?" К счастью, к этому времени я заинтересовался чтением о Turing, Геделе, исчисляемость и т.д. и установил связь.

несколько лет спустя я заметил, что Доступ MS иногда печатает "Страницу 6 5", который является действительно чудесной вещью.

Пример 2: компиляторы C++

процесс компиляции включают расширяющиеся шаблоны. Шаблонные определения могут быть выбраны из нескольких специализаций (достаточно хороший для служения в качестве "cond"), и они могут также быть рекурсивными. Таким образом, это - полное по Тьюрингу (чистый функциональный) метасистема, в которой шаблонными определениями является язык, типы являются значениями, и компилятор является действительно интерпретатором. Это было несчастным случаем.

, Следовательно, не возможно исследовать любую данную программу C++ и сказать, мог ли компилятор в принципе завершиться с успешной компиляцией программы.

поставщики Компилятора обходят это путем ограничения глубины стека рекурсивного шаблона. Можно скорректировать глубину в g ++.

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

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

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

Несколько лет назад, я не забываю читать обзор (в журнале Byte, я верю) продукта под названием Основное Средство поиска Бесконечного цикла или BILF. BILF, как предполагалось, просканировал Вашу Microsoft Basic source code и нашел любые циклы, которые не завершались. Это утверждало, что было в состоянии, любой находит любые бесконечные циклы в коде.

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

В следующем выпуске, они опубликовали букву от представителя компании объяснение, что проблема будет решена в следующем выпуске.

Обновление: я натыкался на изображение статьи о imgur. Я помнил неправильный журнал. Это было Творческое Вычисление, не Байт. Иначе это в значительной степени, поскольку я помнил его.

Вы видите версию с высокой разрешающей способностью его на imgur.

Это - все еще проблема для программ построения теней в приложениях GPU. Если программа построения теней имеет бесконечный цикл (или очень длинное вычисление), должны, драйвер (через какое-то время предел) останавливает ее, уничтожает фрагмент, или просто позволяет ей работать? Для игр и другого коммерческого материала, первый, вероятно, что Вы хотите, но для вычислительного научного / вычислительный GPU, последний - то, что Вы хотите. Хуже, некоторые версии окон предполагают, что, так как графический драйвер был безразличен в течение некоторого времени, он уничтожает его, который искусственно ограничивает вычислительную мощность при выполнении вычисления на GPU.

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

я не знаю, улучшилась ли эта ситуация недавно, но я хотел бы знать.