Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

Надёжные программы из ненадёжных компонентов

Была у меня одна идея фикс, которая давно не давала покоя. Необычная, потому раньше ничего похожего не встречал. Это если идёт речь о программном обеспечении. А вот в технике вообще и в электронике в частности этим никого не удивишь. Идея заключалась в том, чтобы дать возможность писать программы так, чтобы они состояли из наборов дублирующих друг друга модулей. Чтобы эти модули исполнялись, а результаты их работы рассматривались бы программой-арбитром, сравнивались и выбирались правильные путём голосования.

Так работает распространённая в электронике система троирования. Там тоже есть электронные компоненты, которые выполнены в трёх экземплярах и результат которых рассматривается неким арбитром. В голосовании побеждает большинство голосов: два из трёх. Такая схема позволяет строить надёжные устройства на плохой элементной базе. Справедливости ради надо отметить, что этот способ резервирования далеко не единственный. Тема резервирования особенно востребована в ответственных применениях: на атомных электростанциях, в авиационной и космической технике. В частности, долгая жизнь и высокая репутация пассажирского самолёта Ту-154 связаны с тем, что у него жизненно важные узлы были продублированы.

Надо отметить, что проблема надёжности в ПО по важности ничуть не уступает проблеме надёжности электроники. Но если в электронике проблемы решаются — архитектурными способами или повышением качества чипов, то для ПО воз и ныне там: качество софта сильно уступает качеству чипов, а архитектурными способами надёжность ПО не повышают. Хотя проблема приобретает временами кричащие формы. Ну не принято у софтостроителей дублирование. То ли по причине наивной убеждённости в безгрешности своих творений, то ли из-за циничной уверенности, что «пипл и так схавает». Второе наиболее вероятно потому, что в индустрии ПО торжествует принцип «as is» («как есть»). Лицензионное соглашение, которое появляется в диалоговом окне при инсталляции ПО, для того и предназначено, чтобы заранее снять с производителей ПО всю ответственность и обезопасить от судебных исков.

Впервые идея о резервировании ПО посетила меня во время учёбы в вузе. При изучении электроники мы проходили тему повышения надёжности с помощью резервирования, а по программировании в это же самое время проходили тему структурного программирования — тоже для повышения надёжности. Взаимосвязанность этих вопросов казалась настолько очевидна, что был даже удивлён, что такой мысль о применении аналогичных методов никому в голову больше не пришла. Задал вопрос преподавателю, почему бы не поступать с программами так же, как с электроникой — дублировать или троировать. Внятного ответа я не услышал. Позже пытался найти что-то подобное в Интернете. Но тема словно окружена глухой стеной, ничего похожего долго не удавалось найти. Значит, думаю, это всё ерунда. Мало ли какой бред мог в голову прийти? И когда всё это начало казаться дебрями, в которые не стоит лезть, тут поиск всё-таки дал результат. Просто надо было упорнее перебирать слова в поисковых запросах. Поделюсь двумя ссылками, раз и два. Почитал. Оказывается, тема вполне себе проработана. Но, как всегда, захотелось добавить отсебятины. Тем более, что какие-то моменты, как показалось, не освещены.

Коротко можно перечислить основные методы повышения надёжности ПО:

  • проверки кодированием, например, контрольные суммы,
  • обратные вычисления (если они возможны) — получение начального результата из конечного и сравнения с исходным.
  • обнаружение и обработка ошибок, мы это уже рассматривали,
  • контрактное (аспектно-ориентированное) программирование, которое будет рассмотрено позже,
  • дублирование, троирование и бо́льшая степень резервирования модулей.

Говоря о написании нескольких версий одного и того же функционально эквивалентного ПО, надо помнить, что дублирование и троирование (написание ПО в двух или трёх версиях) — простейшие случаи, которые требуют минимальных дополнительных затрат на написание ПО. Но нет никаких ограничений на написание бо́льшего количества версий. Просто две версии ПО позволят обнаруживать ошибки, а три версии делают возможным ещё и коррекцию ошибок.

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

Но давайте рассмотрим троирование. Это простой и элегантный (даже красивый!) способ повысить надёжность ПО. Выбор правильного результата из трёх полученных будет проводиться «голосованием». Вероятность того, что одновременно ошибутся два модуля, крайне невелика. Всё очень просто и вместе с тем надёжно. Простота сама по себе является ценностью. А тут ещё она поможет в борьбе за надёжность.

Троирование

Необратимые побочные эффекты
Можем ли мы разбить наше ПО на три независимые части, одинаковые по функциональности? Очевидно, что нет. Всё дело в том, что какие-то составные части наших программ дают побочные эффекты. Эти эффекты оказывают такое воздействие на внешнюю среду, что в общем случае отменить оказание побочного эффекта невозможно или неправильно. Ведь если наше ПО состоит из трёх частей с одинаковым назначением, то что должны делать две оставшиеся части, если первая уже дала, допустим, команду на запуск ракеты-носителя? Как говорит поговорка, «нельзя дважды произвести первое впечатление». Действие побочных эффектов таково, что в общем случае «фарш невозможно провернуть назад».

Значит, надо разбивать задачу на части. Та функциональность, которая отвечает за побочные эффекты, должна существовать отдельно. Её в нашей схеме невозможно резервировать. Будем надеяться, что это будет лишь малая часть общей задачи. Оставшееся можно исполнить тремя разными способами и даже тремя разными исполнителями или подрядчиками, но решать оно должно одинаковые задачи. Схематически это можно представить так:

Надёжные программы из ненадёжных компонентов
Какие функции можно употреблять внутри троированных модулей, а какие нельзя? Произведём классификацию этих функций.

Классификация функций и побочных эффектов

Виды функции (в порядке убывания «качества» функций).

  1. Чистые функции.
  2. Функции логирования. Например, функции записи в системный журнал. При аккуратном исполнении они вообще могут считаться чистыми.
  3. Недетерминированные функции, не имеющие побочных эффектов. Например, функции time() или random().
  4. Недетерминированные функции, побочными эффектами которых можно пренебречь. Например, измерение температуры внешней среды вряд ли окажет заметный побочный эффект.
  5. Функции, вызывающие изменение внутреннего состояния системы. Поскольку внешняя среда не затронута, то изменения внутреннего состояния могут быть обратимы. При соблюдении определённых мер, конечно. Например, запоминание старого состояния перед записью нового. Тогда возможно реализовать восстановление предыдущих состояний — своего рода кнопку «Undo».
  6. Функции, вызывающие обратимые изменения во внешней среде. Похоже на предыдущий пункт, только для внешней среде, за пределами Вашей вычислительной системы.
  7. Функции, вызывающие необратимые изменения во внешней среде, за пределами Вашей вычислительной системы.

На рисунке выше троированные модули обозначены зелёным цветом. Внутри троированных модулей возможно употребление функций видов 1, 2 и 3.

Следующие функции — вида 4, 5 и 6 — нежелательны (хотя и возможны при аккуратном программировании) внутри троированных модулей. И чем ниже «качество» функций, тем они нежелательнее. Почему? Потому что смысл троирования в том, что мы не доверяем компонентам программы — они могут неправильно выполнить свою задачу. Но тогда нельзя доверять и той части, которая реализует «Undo». Если не верим, что будет выполнена прямая функциональность, логично не верить, что будет выполнена обратная.

Функции 7 вида троировать нельзя. Место им на рисунке выше — внутри блоков, раскрашенных красным.

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

Например, в языке D описание чистых функций сопровождаются ключевым словом «pure». Это обязывает к тому, что функции, вызываемые внутри описываемой, тоже должны быть чистыми и тоже должны иметь ключевое слово «pure». В новом языке градаций «качества» функций будет больше и компилятор будет оценивать их «качество» по наличию соответствующих указаний в описании. Этой теме будет посвящено отдельное обсуждение в дальнейшем. Сейчас же обрисовываются общие черты.

Как это работает

Ввод. Разбить его на три части не удастся, поскольку функции ввода не детерминированы. Это означает, что выполнив три раза ввод, мы в общем случае получаем три разных значения. Трём разным входным значениям будут соответствовать три разных результата. Ну и ещё такой момент: попробуем представить, что троированная функция авторизации вынуждает трижды ввести логин и пароль. «Не фонтан». Поэтому ввод делается единожды, а его результат являются общими для трёх версий модуля.

Работа троированных модулей. Каждый из модулей решает одинаковую задачу, хотя, возможно, разными способами. У троированных модулей — одинаковый интерфейс, то есть «снаружи» они одинаковые, но «изнутри» должны, по идее, отличаться. Ведь если они абсолютно одинаковы, то смысл троирования теряется. В принципе, поскольку при голосовании достаточно двух голосов для «победы», то третий модуль при совпадении результатов первого и второго может не вызываться. Но если идёт сбор статистики о работе модулей, то для её полноты надо вызывать все модули.

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

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

Предложенная выше классификация «качества» функций, имеющая поддержку на уровне синтаксиса, как раз поможет определить место функций в изображённой схеме. Развивая тему резервирования модулей ПО дальше, можно рассмотреть идею обновления ПО «на лету». В самом деле, если один из трёх модулей ПО работает неправильно, то его можно и нужно заменять. И хотелось бы, чтобы без остановки программы. Пока идёт замена одного из модулей, система может просто поработать без резерва, с отключенным третьим модулем. А вот только как это сделать? Надо думать...

Опубликовано: 2021.12.31, последняя правка: 2024.01.08    20:24

ОценитеОценки посетителей
   ███████████ 2 (25%)
   ████████████████ 3 (37.5%)
   ▌ 0
   ████████████████ 3 (37.5%)

Отзывы

     2023/12/21 05:02, MihalNik          # 

Тут в первую очередь следует уточнить: от какого рода нарушений требуется повысить надёжность. Например, физические повреждения электроники могут требовать копий одних и тех же данных, включая исполняемый код, параллельного исполнения одинаковых функций на разных вычислительных блоках. Если речь об ошибках программиста, то разные варианты решения одной и той же задачи иногда имеют смысл на этапе исполнения программы, но гораздо чаще используются на этапе разработки — в прототипировании, оптимизации и тестировании. Потому что основные сборочные рабочие единицы — функции, получают разные физические свойства — размер и сложность исходников, время их написания, компиляции, интерпретации, исполнения, размеры потребляемой при этом памяти. А ещё чисто математически бывает, что проверить решение легче, чем вычислить. Например, реализовав деление, можно тестировать остальные операции длинной арифметики в остаточных классах.

     2023/12/21 09:02, Вежливый Лис          # 

не нужно никаких "в первую очередь построить модель угроз", всё тут правильно сделано — изречена и изложена (записана) суть идеи, а это главное.

     2023/12/21 18:26, Автор сайта          # 

следует уточнить: от какого рода нарушений требуется повысить надёжность.

От всех отклонений от технического задания. В такой системе считается априори правильными две вещи: техническое задание и функции операционной системы. Это аксиомы, на которые опираются теоремы, то есть написанные программы.

Если речь об ошибках программиста

Да, человек — слабое звено, его работу надо проверять и контролировать. А тут как раз идёт речь об автоматизированном контроле и «голосовании» за правильный результат.

этапе разработки — в прототипировании, оптимизации и тестировании.

Конечно, это важно и на это нельзя махать рукой. Но надёжность особо критичных приложений можно повысить, дублируя функции. Реализацией таких функций могут заниматься разные разработчики. Или один и тот же, но разными способами. Ко всему прочему это даст протоколы ошибок тех функций, результаты которых не совпали с другими реализациями этой функции. Что является поводом вернуться к «сломавшейся» функции и разобраться в проблеме. И всё это — на уже правильно работающей системе!

В ближайшее время будет развитие этой темы.

     2024/03/17 17:11, Городняя Лидия Васильевна          # 

В голосовании побеждает большинство голосов: два из трёх

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

фарш невозможно провернуть назад

На этапе отладки возможно.

функции ввода не детерминированы

Повторный ввод пароля.

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

Можно сделать их элементами множества возможных результатов.

Не исключено, что создание функциональных версий следует рассматривать как элемент технологии. Сначала — чистые функции, удобные для продуктивности и верификации. Затем их функциональные эквиваленты, нагруженные дополнительными требованиями к производительности и особенностям аудитории. Функциональная эквивалентность допускает логико-информационную автоматическую проверку.

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

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

     2024/03/18 23:25, Автор сайта          # 

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

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

фарш невозможно провернуть назад

На этапе отладки возможно.

Отладка, а в широком смысле — испытания каких-то систем и технических комплексов, может пожертвовать опытным экземпляром техники. В этом случае невозможность провернуть фарш назад несущественна. А вот когда речь идёт о человеческой жизни, то откатить назад (в предыдущее состояние) гибель человека невозможно.

функции ввода не детерминированы

Повторный ввод пароля.

Если не брать тот факт, что вводимые пароли могут быть разными, то можно констатировать бинарную недетерминированность: введённый пароль может быть правильным или неправильным, и какой именно введут — непредсказуемо. То есть имеет место быть недетерминированность, то есть нет предопределённости.

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

Можно сделать их элементами множества возможных результатов.

Имелось в виду другое. Поскольку арбитр «слепой», как изображается Фемида на картинах и на скульптурах — с завязанными глазами, то надо выбрать или жребием, или первый вариант, или последний. То есть не делать попыток выбрать правильное, а то сам арбитр станет сложнее и вероятность ошибка в нём увеличится.

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

Однако, надо отметить, дублирование всё-таки даёт свои плоды. В те времена, когда электроника имела низкую надёжность, это было просто спасительным кругом, выходом из положения. Сейчас электроника стала значительно надёжнее программного обеспечения. Просто потому, что, в отличие от ПО:
1) сильно стандартизирована: существует лишь малое число вариаций процессоров; на таком малом ассортименте проще проверить правильность и найти ошибки,
2) колоссальное количество готовых изделий в эксплуатации является широчайшим полигоном для выявления ошибок,
3) производители электроники отвечают деньгами перед потребителями (гарантийные обязательства) от отличие от производителей ПО с их принципом «as is».

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

     2024/03/19 23:44, Городняя Лидия Васильевна          # 

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

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

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

Реальность необратима и в не столь важных случаях.

То есть не делать попыток выбрать правильное, а то сам арбитр станет сложнее и вероятность ошибки в нём увеличится.

Да, очень удобно, когда правильность не имеет значения! :)

электроника стала значительно надёжнее программного обеспечения.

Кроме того, круг пазработчиков электроники всё меньше подвержен крену в массовую профессию.

в ПО дублирование пригодилось бы.

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

     2024/03/20 13:13, Неслучайный читатель          # 

Да, когда все функции выдают одинаковый неправильный результат, то сравнение результатов ничего не даст.

Допустим, вероятность ошибки в функции равна 0,01. Если она написана 2 разработчиками, то вероятность равна 0,01*0,01 = 0,0001. Если тремя, то 0,01*0,01*0,01 = 0,000001. То есть вероятность одновременной ошибки во всех вариантах падает по экспоненте с увеличением резервных компонентов. Это математика и теория надёжности, с ними не поспоришь.

В электронике такая же картина.

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

То есть не делать попыток выбрать правильное, а то сам арбитр станет сложнее и вероятность ошибки в нём увеличится.

Да, очень удобно, когда правильность не имеет значения! :)

Техника должна принимать мгновенные решения на основе формальных математических методов, как в том же помехоустойчивом кодировании. Она должна снизить вероятность необнаруженной ошибки до приемлемого уровня (но не как фирма «Борланд» :)), а если ошибка обнаружена, то либо исправить (если возможно), либо сообщить о ней.

Добавить свой отзыв

Написать автору можно на электронную почту
mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Содержание

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

Анализ и критика

●  Устарел ли текст как форма представления программы

●  Русский язык и программирование

●  Многоязыковое программирование

Синтаксис языков программирования

Синтаксический сахар

●  Некоторые «вкусности» Алгол-68

●  «Двухмерный» синтаксис Python

●  Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

●  Должна ли программа быть удобочитаемой?

●  Стиль языка программирования

●  Тексто-графическое представление программы

●●  Разделители

●●  Строки программы

●●  Слева направо или справа налево?

●  Комментарии

●●  Длинные комментарии

●●  Короткие комментарии

●●  Комментарии автоматической генерации документации

●●  Нерабочий код

●●  Помеченные комментарии

●  Нужны ли беззнаковые целые?

●  Шестнадцатиричные и двоичные константы

●  Условные операторы

●  Переключатель

●  Циклы

●●  Продолжение цикла и выход из него

●  Некошерный «goto»

●  Изменение приоритетов операций

●  Операции присвоения и проверки на равенство. Возможно ли одинаковое обозначение?

●  Так ли нужны операции «&&», «||» и «^^»?

●  Постфиксные инкремент и декремент

●  Почему в PHP для конкатенации строк используется «.»?

●  Указатели и ссылки в C++

●●  О неправомерном доступе к памяти через указатели

●  Обработка ошибок

●  Функциональное программирование

●●  Нечистые действия в чистых функциях

●●  О чистоте и нечистоте функций и языков

●●  Макросы — это чистые функции, исполняемые во время компиляции

●●  Хаскелл, детище британских учёных

●●  Измеряем замедление при вызове функций высших порядков

●●  C vs Haskell: сравнение скорости на простом примере

●●  Уникальность имён функций: за и против

●●  Каррирование: для чего и как

●●  О тестах, доказывающих отсутствие ошибок

●  Надёжные программы из ненадёжных компонентов

●●  О многократном резервировании функций

●  Использование памяти

●  Почему динамическое распределение памяти — это плохо

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

●●  Типы переменного размера (dynamically sized types, DST) в языке Rust

●●  Массивы переменной длины в C/C++

●●  Размещение объектов в стеке, традиционный подход

●●  Размещение объектов переменной длины с использованием множества стеков

●●  Размещение объектов переменной длины с использованием двух стеков

●●  Реализация двухстековой модели размещения данных

●●  Двухстековая модель: тесты на скорость

●●  Изменение длины объекта в стеке во время исполнения

●●  Размещение объектов переменной длины с использованием одного стека

●  Можно ли забыть о «куче», если объекты переменной длины хранить в стеке

●  Безопасность и размещение объектов переменной длины в стеке

●  Массивы, структуры, типы, классы переменной длины

●  О хранении данных в стеке, вместо заключения

●  Реализация параметрического полиморфизма

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Новости и прочее




Последние отзывы

2024/06/21 00:20 ••• Gudleifr
О превращении кибернетики в шаманство

2024/06/19 00:16 ••• Gudleifr
Программирование исчезнет. Будет дрессировка нейронных сетей

2024/06/12 11:27 ••• Автор сайта
Все языки эквивалентны. Но некоторые из них эквивалентнее других

2024/05/31 12:31 ••• Прохожий
Идеальный транслятор

2024/05/28 15:16 ••• Прохожий
Русской операционной системой должна стать ReactOS

2024/05/25 17:18 ••• Прохожий
Избранные компьютерные анекдоты

2024/05/11 16:33 ••• Автор сайта
Энтузиасты-разработчики компиляторов и их проекты

2024/04/28 15:58 ••• Автор сайта
Обработка ошибок

2024/04/23 00:00 ••• alextretyak
Признаки устаревшего языка

2024/04/21 00:00 ••• alextretyak
Постфиксные инкремент и декремент

2024/04/20 21:28 ••• Бурановский дедушка
Русский язык и программирование

2024/04/01 23:39 ••• Бурановский дедушка
Новости и прочее

2024/03/22 20:41 ••• void
Раскрутка компилятора