суббота, 24 августа 2013 г.

Развитие технических систем — Взрыв и стандартизация (с примером IBM)

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

При выходе в новую область наблюдается взрыв разнообразия различных форм. Так было с самолетами в 20-30-х гг., так было в войне Unix'ов, так было с кодировками до ASCII и до UTF-8.

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

После взрыва запускается процесс естественного отбора, когда разнообразие начинает уменьшаться, а видообразование приостанавливается. Отдельные наиболее приспособленные особи выживают и захватывают большие области, другим видам питаться нечем и они отмирают. Так, на сушу в свое время вышли 5-ти, 6-ти и 8-ми пальцевые существа, но выжили только потомки первых, потому мы такие и других больше не наблюдаем.

В технических системах происходит аналогичный процесс, когда остаются в основном 4-хколесные машины шириной в две крупы лошади, мейнстримовые языки программирования, типовые решения для аппаратных устройств (генераторы, трансформаторы), коробочные продукты (one-the-shelf), … Большие выжившие монстры решают большие классы задач, а в маленьких закоулках ютятся отдельные подвиды, зачастую мало кому известные и потенциально отмирающие.

Технические пути отбора

В технических системах с точки зрения отбора можно выделать два механизма.

Первый — насильственный захват и выбивание конкурентов. Например как это делает Windows — разработчики Windows сами себе стандарт, не обращая внимания на других, и способ захвата — выживают те решения, которые выигрывают на рынке, даже если эти решения не являются сильными. Это и сама ОС, и Ctrl-C Ctrl-V (задолго до них был Ctrl+Insert и Shift+Insert), и Win-1251 и др.. С точки зрения разработки — это решения для себя, для полного контроля и для вписывания в внутрикорпоративные стандарты.

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

Технетика

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

Таким образом, любые технические системы развиваются, живут и умирают. И, как ни странно, есть целые труды и школы, которые описывают данный процесс. С одной из таких я познакомился где-то на рубеже 2000-х, это была Технетика Б.И.Кудрина — информация в ней зубодробительна и слишком философска для обычных людей, но базовые понятия развития техники удалось почерпнуть именно оттуда. В дальнейшем элементы технетики встречались и замечались в жизни много раз, иногда принося существенную пользу.

Стандартизация вычислений с плавающей точкой

Сейчас ещё один такой случай, который увиделся при чтении Fatal Defect (chapter Wrong Number), где подробно разобрана история становления стандарта по вычислительным арифметическим операциям на компьютерах/калькуляторах с плавающей точкой. Особенность в том, что в 60-х не было единого подхода и решения того, как хранить вещественные числа в компьютере, а также как проводить вычислительные операции. Каждая организация делала свое решение, а зачастую внутри организации разные аппаратные разработки имели разные реализации.

Особенностей разностей несколько. Для примера, первая в том, что для повышения точности можно хранить разное количество дополнительных разрядов (кроме отображаемых на дисплее калькулятора можно хранить 0, 1, 3, … разрядов за краем табло, чтобы потом результат вычисления был более точным; например если не хранить, то 1/3*3 получится 0.99999). Второй является то, что можно использовать разные способы округления, которые также могут отражаться на конечном результате. Третьей являются разные алгоритмы выполнения данных операций, каждый из которых может отличаться точностью, быстродействием и неравномерным распределением ошибок. Четвертой — возможно разные преобразования между отображением и вычислением (например сначала берется то что на дисплее в 10-й системе счисления, переводится в 2 с/c, считается, далее обратно в 10 с/c). Пятой — стоимость системы.

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

Компьютер в любом случае не может обеспечить 100%-й точности для всех математических вычислений (так как числа в памяти есть конечное число единиц и нулей), и, казалось бы, с этим мало чего можно сделать. Однако в 70-х запустился процесс продвижения идеи, согласно которой необходимо было привести зоопарк к общему знаменателю, чтобы мы не всегда получали точный результат, но на разных компьютерах этот неточный результат был бы одинаковым.

В конце 70-х IBM инициировала внутри себя процесс создания подобного стандарта, так как зоопарк был внутри данной организации и руководство уговорили это сделать. После запуска процесса был собран IEEE-комитет из ~70 представителей различных компаний и институтов (не только из IBM). После многочисленных штурмов и споров (потому что каждый эксперт считает свои заблуждения самыми правильными) был выпущен черновой вариант с сомнениями о том, что этому кто-то будет следовать. Однако IBM в 1980-м выпускает первые чипы 8087, которые соответствовали описанным требованиям, и после этого запустился лавинообразный процесс, который охватил всех мировых производителей, хотя официальный чистовой вариант был принят в 1984-м.

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


среда, 21 августа 2013 г.

Радость от повторения

Дети любят, когда им несколько раз читают одни и те же сказки.

В фильмах и особенно в сериалах зрители любят, когда повторяются определенные фишки.

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

Часто можно наблюдать, как люди повторяют что-то банальное, что их греет и умиротворяет («во всем виновата мировая закулиса», «все плохо потому что у власти козлы», «а наши поезда все равно самые поездатые», …).

В разработке видео-игр, когда гейм-дизайнеры рассматривают игроков как подопытных кроликов, есть такое понятие как Core Gameplay Loop, заключающееся в том, чтобы формировать такие повторяющиеся радости, и чем чаще то делать, тем они сильнее закрепляются, и потом на них строить все остальное.

Если часто общаться с человеком, то можно заметить множество повторяющихся штук, в том числе и за собой.

По-моему, за всем этим стоит некий нейробиологический принцип, или общее психическое свойство. Но в популярных литературах ещё ничего такого не встречал.


понедельник, 19 августа 2013 г.

О правильном

В начале всяческой философии лежит удивление, ее развитием является исследование, ее концом — незнание.

М. Монтень

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

Не бывает правильного способа решения проблемы. Бывают способы с определенными последствиями.

Не бывает правильного принципа или метода. Бывают принципы и методы с определенными достоинствами и недостатками, работающие в определенном окружении.

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

Одно дело когда известен контекст и все понимают, чем «правильный» вариант лучше, чем остальные. Другое дело, когда контекст теряется, и народ уже не понимает что стоит за словом «правильный». «Потому что так написано в книге Х», «Потому что так сказал Y», «Мы всегда делали Z, и в дальнейшем будем делать так же», …

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

После того, как схема принята, то изменить её сложно. Классическая цитата Лоренца:

Для существа, лишенного понимания причинных взаимосвязей, должно быть в высшей степени полезно придерживаться той линии поведения, которая уже — единожды или повторно — оказывалась безопасной и ведущей к цели. Если неизвестно, какие именно детали общей последовательности действий существенны для успеха и безопасности, то лучше всего с рабской точностью повторять ее целиком. Принцип «как бы чего не вышло» совершенно ясно выражается в уже упомянутых суевериях: забыв произнести заклинание, люди испытывают страх. (К. Лоренц, Агрессия)

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

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

Понимайте причинно-следственные взаимосвязи.


пятница, 16 августа 2013 г.

Поступательное развитие

В последнее время вокруг меня что-то много звезд выстроилось по этому понятию…

Примеры

Нельзя сразу собрать проект, который реализует полет на Луну. Или создаст термоядерную бомбу. Или реализует национальную ПРО.

Сразу слетать на Луну — это будет глупая и бессмысленная смерть. Сначала надо собрать ракету и запустить. Понять, что чтобы слетать, надо работать над надежными двигателями, иначе летать она будет низко. Придумать гироскоп, иначе летать будет не туда. Собрать конструкцию заданного масштаба (ракеты малой дальности и межконтинентальные — это две болшие разницы). Запустить железяку и проверить, чтобы она не столкнулась с небесным сводом. Запустить жывотное, потому что его не жалко. Запустить человека в корпусе. Запустить и отработать технологии выхода в открытый космос. Слетать на Луну и померять радиацию. Попробовать прилуниться, а то иначе можно утонуть. И только потом появляются какие-то шансы на слетать и вернуться обратно.

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

Для ПРО сначала необходимо создать что-то, что сможет зарегистрировать массы самолетов. Потому что-то, что сможет засечь одиночный самолет. Потом что-то, что сможет засечь и определить высоту полета. Потом что-то, что сможет засечь, определить x,y,z,t и сбить. И только потом можно думать о чем-то, что сможет отразить атаку в глобальном масштабе.

Два простых правила

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

Законченные и дискретные решения
Необходимость поступательного развития — серия законченных проектов, каждый из которых имеет конкретную реализуемую цель, решая часть общей конечной задачи. На одних чертежах виртуально запустить в космос человека нельзя — должна быть конкретная задача и её воплощение, все этапы жизненного цикла.
Сложные системы строятся из простых
После Буча сейчас много где цитируют J.Gall'a *: «Любая работающая сложная система является результатом развития работавшей более простой системы... Сложная система, спроектированная "с нуля", никогда не заработает. Следует начинать с работающей простой системы».

Процесс роста

Совсем недавно встретил через Стратоплан картинку роста в любой области (источник — недра психологии потока):

От себя отношу картинку не только как к личностному росту, но и к росту проектов или групп людей (что почти одно и то же по закону Конвея).

На графике по вертикали сложность постановки задачи, они же требования к её исполнению (масштабность проекта, процент отказов, производительность системы, … — все это может быть большим уровнем по требованиям). По горизонтали наши умения (+ знания и навыки). Т.е. способность что-либо делать.

В самом начале мало чего умеем. И лучше, если не предъявляем к себе каких-либо сверх-требований. Тогда это нижний левый угол.

Делая что-то, мы учимся это делать лучше. Если делать это долго, то мы научимся это самое делать, но нам становится скучно. A1→A2. Если мы предъявляем к себе более высокие требования, то появляется чувство тревоги — получится ли? сложно! много всего.. и все такое. A1→A3.

В состояниях A2 и A3 зоны дискомфорта — человек может бросить этим заниматься, а может получить большой стимул к развитию.

Оптимальное развитие — как по красной линии, можно немного иногда заходить в сторону тревоги. Если делаем переход вида A1→A4, то растем и можем осуществить большее.

Следствия:

  • Сначала мы все ничего не умеем. Если мы предъявляем к себе большие требования, то станет страшно, ничего не будет получаться и все будет заброшено. Поэтому начинать надо с простых вещей.
  • Если долго делать одни и те же простые вещи, то станет скучно и уныло. Что делать? Повышать требования.
  • Что делать чтобы быстро расти вверх? Идти согласно коридору потока. Если проект большой и масштабный, то идти придется долго, зачастую окольными путями.

Под другим ракурсом

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

Слишком сложная цель

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

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

Работа в стол: переход на самообразование в случае плохого образования; постепенная выработка мастерства; методический и системный сбор информации.

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

Отсутствие цели

Проект выполнен, а дальнейших целей нет.

Активный поиск качественно более широкой и дальней цели и отсутствие ожидания. Без этого — останов процесса роста и потеря поступательного развития.

Отсутвие возможности работы над следующим этапом (не важно по каким причинам) — способствует потере команды и задела.

Цель забирают

По разным причинам — недопущение до информации, высмеивание, потеря контроля, куча соавторов.

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


* — данная мысль только в программной инженерии лет на 20 старше; у Брукса в статье о серебрьяной пуле есть ссылка на научную публикацию 1971 года и цитата коллеги 1958-го года.


воскресенье, 11 августа 2013 г.

Art of Failure

Теперь прибавился к известным мне квази-научным фотоконкурсам конкурс Art of Failure.

Конкурс проводится в рамках международного симпозиума IEEE по физическому анализу и анализу отказов интегральных полупроводниковых схем (IEEE International Symposium on the Physical and Failure Analysis of Integrated Circuits). На этом конкурсе представляются имеющие художественную ценность фотографии необычных объектов и явлений, которые возникают на кристаллах микросхем и других полупроводниковых приборов, возникшие в результате неисправности или выхода из строя этих кристаллов.

  • Именно эту картину увидел на изображении, снятом электронным развертывающим микроскопом, Лим Сав Синг (Lim Saw Sing), сотрудник компании Infineon Technologies, рассматривая поверхность полимидного кристалла, подвергнутого процессу ионного травления. Этот снимок занял первое место в конкурсе Art of Failure 2012.

  • Мембрана из специального материала "прилипла" к коротким частям из углеродной ленты, формируя подобие странного и необычного "леса" на этом изображении с микроскопа. Данный снимок сделал Лим Чен Вэй (Lim Chan Way) из компании Infineon Technologies.

  • Аналитики компании Advanced Micro Devices посчитали, что данная структура на поверхности кремниевой подложки очень смахивает на слона в головном уборе. Фотография так же принадлежит Жаклин Ква (Jacqueline Kwa) из компании AMD.

  • Проводя свои исследования, инженеры компании WinTech Nano-Technology создали эти 20-микронные структуры из меди, используя технологию нанопроизводства с использованием сфокусированного ионного луча. Фотогорафия Ху Бинг Шен из компании WinTech Nano-Technology.


пятница, 9 августа 2013 г.

Что такое человеческий фактор

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

В будущем на автоматизированном заводе не должно быть кроме роботов никого, только один человек и собака. Зачем человек? Чтобы кормить собаку. Зачем собака? Чтобы смотрела за тем, чтобы человек ничего не трогал.

Сейчас обнаружил более оригинальное высказывание (в книге Fatal Defect, 1995), которое походу имеет также корни ещё на лет 10-15 глубже. Итак, шутка, которая ходит среди инженеров-разработчиков автоматизированных систем авионики:

Future automated airplanes will have only a pilot and a dog in the cockpit. The pilot will be included to reassure the passengers while the computers fly the plane. The dog is there to bite the pilot in case he or she touches anything.

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

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

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

Приведенная цитата из книги принадлежит Nancy Leveson, она не является её автором, но от себя продолжает её так:

The pilot will also be there so that there's someone to blame in case of an accident.

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

Зачастую в случае различных происшествий называется человеческий фактор, формулируясь под видом «чего-то недосмотрели», «чего-то не учли», «не услышали сигнала» и пр.. Пара примеров.

Первый. Более подробное рассмотрение происшествия, описанного ранее. Во время снижения A320 получилось так, что пилоты задали слишком быстрое снижение и из-за этого врезались в гору. Однако за всем этим стоит нечто большее. В авионике за 20 лет до происшествия сделали обязательное правило для установки подсистемы, которая оповещает пилотов об опасности слишком низкой высоты полета. Эти подсистемы автоматически посылают звуковые сигналы с громкостью и частотой в зависимости от высоты полета. Однако в рассматриваемом деле на возможность исправить ситуацию с помощью их сыграло дополнительно два фактора. Во-первых, исторически получилось так, что зачастую реализация данных устройств оповещения была такой, что система до неприличия часто давала ложные срабатывания и поэтому пилоты привыкали к данным звукам и не обращали на них особого внимания. Со временем система улучшалась, но сотрудники авиакомпаний по-прежнему считали, что оповещения часто подвержены ошибкам. Во-вторых, для внутренних авиалиний Франции администрацией было принято решение, что раз это внутренние, то пилоты хорошо знают местность и для них такую систему можно просто не устанавливать. Таким образом получается, что на факт катастрофы повлияло как инженерное решение (слишком часто ложные срабатывания), так и административное (отсутствие оценки реальной опасности). Но в протоколах записано, что виноваты пилоты.

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

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

Для решения есть ряд путей:

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

Nancy Leveson часто и давно говорит о том, что катастрофа является результатом стечения ряда факторов, и обвинять только один из них является классической ошибкой. В случае с человеческим фактором почему-то получается так, что его очень удобно обвинить во всем.


четверг, 8 августа 2013 г.

Баг, о котором услышал весь мир (The "BUG" heard 'round the world)

10 апреля 1981 года, приблизительно за 20 минут до запланированного запуска первой американской космической транспортной системы, астронавты и технические сециалисты попробовали активизировать программную систему, выполненную с 4-хкратным резервированием и дополнительным запасным компьютером… но не смогли. Фактически, у них не было никакой возможности это сделать, так как компьютер просто не воспринимал команды… Это был баг, очень маленький, очень неуловимый, очень замысловатый и очень древний — это была ошибка в логике инициализации резервной системы. Это была ошибка, которая является кошмаром для программистов и руководителей, из разряда тех, которые «не могут произойти», даже если вы будете следовать всем правилам хорошего проектирования и разработки.

Самые глубокие секреты программной инженерии часто запрещаются к публикации и выявление причин проявления множества ошибок является чрезвычайно сложной задачей. Кроме того, корректную интерпретацию произошедшего может дать очень малое количество людей. Чаще всего получаются обрывочные факты, или множество несвязанных между собой или даже противоречащих друг другу фрагментов, а получить хорошо документированную историю крайне сложно. Peter G. Neumann говорит о том, что за годы его опыта самым эффективным способом является поиск ключевого инженера-разработчика всей системы или ответственного узла и попытка уговорить рассказать о том, что произошло.

Одним из самых известых багов в истории, которые при этом были документированы по описанному сценарию, является подготовка первого полета Шаттла 10 апреля 1981 года, когда контроллеры отменили запуск в космос шаттла Колумбия всего за 20 минут до намеченного времени. По этой причине на это обратила внимание мировая общественность и почувствовалось давление на то, чтобы подробности были раскрыты. Это был баг, который моментально стал извествен всему миру. Через некоторое время после проишествия Neumann нашел одного из разработчиков программного обеспечения, Jack'a Garman'a, и уговорил его раскрыть детали прозошедшего — именно так появилась эта публикация.

Для повышения надежности шаттл использует 4 идентичных компьютера, работающих по одной и той же программе, включенных в мажорирующую схему 2+2 с сильными связями, функционируя в горячем резерве. Это означает, что 4 компьютера разбиты на 2 пары, каждая из которых синхронизируется со своим «напарником». Если состояния пары одинаковы, то это считается корректной работой системы. Если одна из пар расходится во мнениях, то вся пара считается сломанной и управление переходит на вторую пару компьютеров. Синхронизация между парами происходит на каждом цикле внутренних часов. Данная организация позволяет защищаться от аппаратных проблем — например в случае сбоев из-за электромагнитного излучения.

Кроме описанных 4-х компьютеров в системе присутствует также 5-й компьютер, являющийся резервным. Его ПО обладает такой же функциональностью, но написано другими программистами и работающее под другой операционной системой — для обеспечения более высокого диверситета на программном уровне (в данном шаттловом случае компилятор и железо были одинаковыми с основной системой). Данный компьютер включается только в случае, когда обе пары из основной системы 2+2 выходят из строя, при этом резервная система управление и всю ответственность берет полностью на себя. Резервный компьютер программно призван отличаться от основного и в этом плане его назначение — избежать программных ошибок.

В описанной истории инженеры обнаружили баг временной синхронизации между описываемыми компьютерами. С вероятностью 1/67, которая срабатывает на каждом запуске системы, могло получится так, что часы синхронизации пары 2+2 и резерва окажутся на 1 такт впереди общих тактов синхронизации. Именно это произошло на реальной системе при пробной попытке запуска челнока за 30 часов до предполагаемого старта. В случае рассинхронизации получалось так, что старта основной системы не было, а резервный компьютер никогда бы не получил сигнала о том, что 2+2 вышли из строя. Следует заметить, что тысячи часов тестирования не смогли выявить описанную проблему.

В комплексе имелось три ленты времени — данные телеметрии, время для основной системы и время резервной. При подготовке к запуску заранее стартовала телеметрия (как обратный отсчет) и относительно её синхронизировались обе системы (основная и резервная), но время самого запуска в них системе вычислялось математически и по общим тактам. Далее, если происходила рассинхронизация, то получалось так, что время, которое оставалось до старта по расчету во время ожидания сигнала, становилось отрицательным (пришло время старта, ожидаем sync, а его нет). Число беззнаковое, поэтому оно становилось равным FF, т.е. конечному числу, а по меркам реальной системы — равному бесконечности.

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

В описанном я бы назвал несколько причин:

  1. Синхронизация между двумя разными системами (основная работала в виде асинхронной с приоритетами (fixed priority executives), а резервная периодическая синхронная (cyclic executive)).
  2. Разница сред тестирования и эксплуатации (таймеров).
  3. Отстутствие аналитической проверки при внесении изменений, влияющих на время синхронизации.

И да, доказательство корректности имело все шансы поразить проблему точно в цель (;


вторник, 6 августа 2013 г.

Выученная беспомощность

Встретил на днях в сети такое понятие, как выученная беспомощность. Много думал (;

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

Пропадание желания ломиться даже в открытые двери

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

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

Аналогичное явление в рабочем процессе. Появилась идея X — пробуем предложить/обсудить/внедрить с коллегами A, B, C. Если при разных X'ах какой-то из A, B, C не имеет смысла или не пробиваем, то желание ещё раз пропадает, при чем вне зависимости от того, кривые идеи или правильные, работающие или перспективные — по факту подсознательно все срабатывает, так в конце концов выливается в подпольные проекты, решение проблемы в обход A/B/C, уход от митингов с A/B/C и др.. "Осадок остался" (с), но при этом где-то глубоко.

Контроль всего (вторая часть в вики)

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


понедельник, 5 августа 2013 г.

В тюрьму из-за ошибки в программе?

BBC сообщило о том, что несколько из частных сотрудников (подрядчиков, почтмейстеров) почты UK были отправлены в тюрьму из-за ошибки в программном обеспечении (ПО), которое занимается их бухгалтерией. Причина — дефект в центральной компьютерной системе Horizon. Ранее известен опыт многих ошибок, из-за которых погибали люди, но как много из нас рассматривало ситуацию, что из-за ошибки в обычном ПО может так сказаться на каждом из нас?

Почта UK, работающая с ~11500 отделениями, в которых задействовано ~68000 сотрудников, по результатам ожесточенного спора с некоторыми из них признала то, что имеется дефект в её центральной системе. Более сотни людей говорили о том, что их преследовали по ошибке в судебном порядке для того, чтобы они выплатили деньги за то, что компьютер выполнил несуществующие транзакции. Часть из них потеряла репутацию, а несколько из них попало по этой причине в тюрьму.

В течение последнего года независимые расследователи, которые были наняты Почтой UK, проверяли несколько претензий от сотрудников. Несмотря на то, что они не нашли свидетельств систематических проблем в ядре ПО, они нашли баги (программные ошибки) в нем. Но вместе с этим было отмечено два проишествия в 2011 и 2012 годах, когда сам почтампт идентифицировал сбои (и полагаю, исправлял баланс) на сумму 9000 фунтов в 76 разных узлах.

Почтмейстеры, работающие в малых отделениях почты UK, не нанимаются напрямую центральным отделением, а работают независимо. Однако при этом они обязаны согласно контракту держать положительным баланс своего счета, а самим контролем баланса занимается центральная система (Horizon computer system). В течение многих лет некоторое меньшинство почтмейстеров обвиняло компьютерные системы центральной почты в том, что иногда она вычитала десятки и сотни фунтов по ошибке. При этом их заставляли оплачивать разницу, из-за чего они теряли свои контракты, а некоторые даже попали в тюрьму.

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

Картина из новости №1: Jo Hamilton по итогам недели рассчитал, что должен оплатить 2000 фунтов по обороту. Звонит в офис, а ему говорят, что вы должны 4000. После выяснения оплачивает, и тут оказывается, что он должен уже 9000!

Картина из новости №2: один из сотрудников проработал на королевскую почту 40 лет, а сейчас ему 60 и он празднует свой день рождения за решеткой.

Независимые расследования продолжаются, а народ требует справедливости.


воскресенье, 4 августа 2013 г.

Fatal Defect & Computer Related Risks

Читаю сейчас книги Fatal Defect и Computer Related Risks. Сначала планировал по отдельности, но придется читать вместе.

Эти книги рассказывают о том, как далеки от совершенства любые компьютеры и о том, к каким последствиям могут приводить различные программные и аппаратные ошибки. Компьютеры глубже проникают в нашу жизнь — они находятся в микроволновках и пылесосах, в автомобилях и самолетах, управляют биржами и опасным химическим производством, роботами и военными системами, выполняя при этом ключевые функции — и постепенно последствия дефектов становятся все более ощутимыми, разрушения более стремительными и масштабными. Цена ошибки возрастает и этому вопросу требуется уделять больше внимания.

Книги написаны в одно время и на одну тему, и, более того, основаны на очень похожем материале. Однако внутри имеют разные приближения к одной и той же проблематике. Computer Related Risks — весьма научная, где изложено все по полочкам и темам, по большей части сухая статистическая информация и тематический и факторный анализ. Fatal Defect — напротив, это книга для рядового читателя, где рассказывается множество различных случаев и историй, а сама книга читается как детектив и является хорошим кандидатом на то, чтобы вдохновить людей в или на данную область (Safety-Critical Systems).

Источники для книг основаны в первую очередь на Computer Risks Forum — это онлайновый ресурс, действующий с 1985 года. Его назначение — оповещение и обсуждение любых проблем, связанных с компьютерными рисками, но в первую очередь фокус ставится на больших системах автоматизации процессов, на системах, проблемы в которых могут приводить к большим экономическим потерям и угрожать здоровью и жизни людей. C самого начала существования форума его модератором является активист Peter G. Neumann (Harvard ph.D., длительное время работал в Bell Labs и ACM), занимающийся им в свое свободное время, — он же автор второй книги на моей картинке.

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

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

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


суббота, 3 августа 2013 г.

ПМО ИУС — Разное

Здесь две разные, последние темы, которые не вошли в предыдущие.

Разные 10 лет

За все время преподавания очень многие вещи изменялись от одной противоположности к другой. Кроме того, мною проводилось ряд экспериментов на поиск какой-либо более эффективной модели.

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

В связи с этим за все время все изложение и построение предмета изменялось от фокуcа на всех (должен быть какой-то минимум, он должен быть сделан и сдан, правила одинаковые для всех) к фокусу на отдельных студентах, когда информация дается как есть, без каких-либо жестких требований и указаний, а за первые занятия выделяются те студенты, которые проявляют интерес или являются по крайней мере сознательными. Таких на потоке получалось порядка 10-20%, а на лабораторных где-то 2-3 на группу-подгруппу. Соответственно на занятиях я уделял уже большую часть времени в общении с ними, а остальная часть потока проходила по линии наименьшего сопротивления мимо ПМО ИУС.

В начале для сдачи финального зачета была собрана достаточно жесткая для двоешников и списывателей схема. Во-первых, объявлялось, что своими конспектами можно пользоваться на зачёте несколько минут. Т.е. конспект должен быть свой и это может значительно помочь — формировалась обратная связь что конспект нужно писать. На зачете конспектом можно пользоваться, но только 1 раз (Read Only, без переписывания) — идея взята у Буя М.. Факт наличия своего проверялся совпаданием почерка в ответе на зачет и почерка конспекта. Во-вторых, схема зачета взята с приемных тестов абитуриентов. 10 человек сдают, больше никого, все вещи лежат отдельно, на столе у каждого только билет, бумага и ручка. Малое кол-во людей легко контролируется. В-третьих, принимается только то, что написано. Потому как устно что-то доказывать бесполезно. В-четвертых, время на зачет полчаса, что быстро. Плюс условие — по вопросам и задаче должно быть что-то написано, не обязательно все правильно, не обязательно много, но если человек разбирался и готовился, он должен хоть что-то написать. Т.е. требования были здесь низкие. Именно эта форма зачета сразу стала страшной для всех — т.е. когда все было сделано против списываний, а порог прохождения минимизирован, но по всем темам.

Несколько лет назад я изменил ситуацию. Жесткий зачет был снят, а для каждого студента выдавалась отдельная тема заранее, которую нужно было подготовить на зачет. Тема — вне курса, но в ней нужно было разобраться самостоятельно. Далее каждый приходил со своей темой, рассказывал 2 минуты, один вопрос на понимание, если ок, то все. Иначе — домой разбираться с вопросом и следующая попытка только на следующий день и вопрос будет новый. Фокус был на понимание, на умение оперировать разбираемой сущностью.

Ещё в самом начале я отмечал посещение на каждой паре всех студентов. Сначала это было по журналам, потом группами. Потому, что декан требовал отмечать и вообще отмечать — это правильно. Но в дальнейшем я полностью забил на отмечание (но об этом никому не говорил). На вопрос декана «вы отмечаете?» говорил «старосты отмечают». В начале (тотальное отмечание) посещали все, и выбор между вариантами преподавания был либо все пишем в тишине, либо говорим, ни никто меня не слышит. В последние годы получался другой эффект. Первые лекции тихие потому что они первые, а в дальнейшем студенты сами понимают, что не отмечают, и кому не интересно или те, кто не сознательные, на пару просто не приходят. Где-то к 3-4 лекции из ~120 человек оставалось ~30, из которых слушала только половина, чего мне было достаточно. Пока не зашел декан, поругал тех, кто отсутствует и пообещал выговор старостам, которые тоже отсутствовали (;

Мое положение изменялось и отличалось от других преподавателей тем, что с 2006-2007 года я начал работать в «Интервэйле». Это означало, что в первые годы мне декан прямым текстом говорил, что «либо вы выпускаете N-х студентов, либо мы вам перестаем платить зарплату», а на факультет приходили кандидатуры мне на замену. После этого рубежа что-то изменилось — пугать увольнением стало бесполезно и даже череповато, но и с другой стороны, времени и сил бороться с системой у меня уже было меньше, постепенно приближаясь к нулю. Ситуация такая, что верхи не могут, а низы не хотят. Университет не может отчислять студентов, потому что каждый студент — это $ в казну ВУЗа (минус платник, а минус бюджет означает что один из платников станет бюджетником), и этот блок стоит на уровне ректора. Хотя думаю ещё один блок стоит выше — так как «каждый гражданин РБ имеет право на высшее образование». Кроме того, уменьшение числа студентов на факультете означает, что у декана заберут зама и дадут нагрузку на кафедре. Второе: грубо говоря, студентам невозможно оценить качество материала и уровень преподавания по определению (образно говоря это ключевые последние технологии или русские народные сказки) — содержание курса мог сократить раза в 2, никто бы ничего не заметил. Кроме того, по моему впечатлению, студенты приходят учиться в ВУЗ как в школу — посещение и движение по линии наименьшего сопротивления. Третье: сотрудникам ВЦ все равно, как идет обучение, главное чтобы на них это никак не отражалось. 90% софта, который ставился на ВЦ для ПМО ИУС, ставился лично мной во всех аудиториях. Любое обновление — бумагу, только летом, ставь сам, и делай в выходные в свое личное время. Четвертое: Социального заказа со стороны «Интервэйла» или любых других организаций ни разу не слышал, хотя можно было часть содержимого курса перенаправить в конкретно ориентированную сторону. Последнее: качество содержания курса имело значение только для двух людей — преподавателя (как ответственность за то, что преподается) и зав. кафедры (потому что потом необученные студенты приходят писать диплом и лучше, чтобы они что-то знали).

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

Пару лет мы пытались использовать систему тестирования, когда сдача л.р. проходила методом ответов на определенный тест (5 вопросов случайных, 4 правильно — сдано). От этой практики отказался, так как студенты на занятиях гоняли тесты, тратили время на это вместо того, чтобы программировать и разбираться в предмете, а также учились отвечать на вопросы, а не понимать их смысл.

С точки зрения написания лабораторных работ и отбработки практических навыков также было несколько разных форм реализаций. Сначала — теория и готовые примеры. Как результат — студенты теряли значительную часть теории (так как она напрямую не связана конкретными действиями с практикой), а примеры копировали и немного изменяя под себя. как показала практика, копипаст не способствует обучению, — он очень близок к тому, когда за студента делает кто-то, или к тому, когда необходимо самому сделать re-engineering (понять почему в примере сделано именно так и что означают эти конструкции). Следующим шагом было предоставление видео по л.р., когда можно видеть как собирается работа и смотреть комментарии к действиям. Это оказалось гораздо эффективнее, однако тут две проблемы — с видео надо переписывать (много времени и мало смысла), плюс видео надо смотреть (его нельзя быстро просмотреть или быстро найти что-то). Последним самым эффективным вариантом было изложение примера step-by-step. Лаборатоная работа разбивалась на пару десятков шагов, каждый из которых описывался словами (что делаем, почему, особенности) и примером текстового кода, который изменялся, и каждая итерация должна была быть осмысленной и компилируемой в итоге. Т.е. на каждом шаге можно было понимать и усваивать малый кусочек материала, сразу видеть результат работы и в случае ошибок быстро их найти.

Система выдачи автоматов также постоянно изменялась. Это был проходной балл (предел), определенное кол-во работ, сданных вовремя, верхняя треть списка и др.. Автоматы хороши в случае, когда надо стимулировать массы, но в последнем варианте я сосредотачивался на отдельных людях, и вся система стимулирования всех просто отключилась. У меня в последние годы вообще пропало желание кого-то что-то заставлять делать или учить. Если есть желание — добро пожаловать, всегда и всего помногу. Иначе смысла нет.

Смайлики

И в завершение веселая тема, которую я называл смайлики. В общем случае это тема про систему оценок и выставления баллов студентам за их достижения в процессе работы в курсе ПМО ИУС.

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

Пример последней из таблицы рекордов: общая(+группы) и запасная ссылки.

По завершению каждого занятия преподаватель заходил на сервер через web-интерфейс и отмечал птицами кто что сдал (работа и отчет). Если работа сдавалась вовремя, то система давала одно кол-во баллов, если не во-время, то поменьше. Кроме того, преподаватель отмечал тех, кто отсутствовал на паре; тех, кто отрабатывал занятия; тех, кто был инициативным (по мнению преподавателя), и тех кто плохо себя проявил (опоздал на занятие например). На основании этой информации формировалось все остальное. Система контролировала выдачу заданий (не более 2-х несданных работ в одни руки), строила таблицы рекордов, формировала список автоматов и рассчитывала оценки контрольных сроков.

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

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

Данное положение изменялось, и это изменение за последнюю неделю показывалось рядом стоящими стрелками ( ). Т.е. если поднялся на 5 мест вверх, то стрелка вверх и число 5.

Далее рядом с каждым из них были смайлики. Это прописанные картинки, которые распределяются исходя из числа баллов равномерно от 2-го места к последнему, первое всегда один и тот же победитель. Смайлики были найдены ещё в 2003-м году, и тогда студенты ещё нас спрашивали, де их нашли (тогда найти было трудно). Кроме того, часть смайликов собственноручно нарисовал Андрей Логвиненко, так как они были слишком жестокими по отношению к девушкам либо не смотрелись женственно. Таким образом, у нас было две линейки смайликов — женские и мужские.

Не знаю как в последние годы, но в первые годы смайлики и таблица рекордов однозначно давали ощутимый позитивный эффект. Их параллельно начал использовать Харлап С.Н., но смайлики вручную вставлялись в Excel, а у нас было все автоматически.

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

Кроме всего этого, имелась система наград, которая включала много разных отличительных значков:

Черная метка — выдается тем, у кого самый худший вариант в группе. Мы долго думали как отображать награду, Андрей даже предлагал сапоги, но все таки остановились на метке. Значок баллов не дает, переходящий приз.
Кубок самому лучшему в специализации на потоке (микропроцессорщики, телемеханики, связисты — три таких кубка.). Баллов не дает, переходящий приз.
Награда за то, что все лабораторные выполнены, а отчеты сданы. +5 если все вовремя, +3 если хотя бы одна не вовремя.
Лучший студент на потоке, переходящий приз, баллов не дает.
Лучшая студентка на потоке, переходящий приз, баллов не дает.
Утешительный приз. Первый из тех, кто остался вообще без звезд или наград. Баллов не дает, переходящий приз.
Первооткрыватель лабораторных работ. Приз получает тот, кто первый выполняет лабораторную работу, но при этом не более одной в руки (такую звезду если уже получил, то больше за первооткрывательство не дадут). +3 балла.
Double, triple, tetris, … приз за сдачу нескольких работ в один день (дубль — две в день). +1/+2/+3/… баллов.
Приз за сданные 1, 6, 10, 13, 28, 100, 153, 200, 256, 300, 370, 371, 400, 407, 496, 500, 555, 600, 666, 700, 800, 900, 1000, 1024 работы. Система помнит, в каком порядке работы сдаются на потоке, и если это работа номер как в списке, то выдается приз. +2 балла.
Выдается тем, кто набрал больше всего баллов в соответствующем месяце. Баллов не дает.
Блуждающая звезда (планета, переходящая). Первый вариант — за активность. Первые 10 студентов, имеющие самую большую активность, получали эти звезды. Первые 5 — +3 балла, вторые 5 — +2 балла.
Второй тип планеты — выдается за массовую сдачу л.р.. Система вычисляет день, когда было сдано больше всего работ, и всем, кто сдавал в этот день, выдает награду. +2 балла.

Таблицы рекордов сохранившихся годов: 2003-2004, 2004-2005, 2005-2006, 2006, 2007, 2010, 2011, 2013.

На этой позитивной ноте думаю можно закончить. Спасибо всем, кто прочитал цикл про ПМО ИУС. Надеюсь все это писалось не зря.


пятница, 2 августа 2013 г.

ПМО ИУС — Структуры данных и STL

В то время, когда я учился, нам в рамках ни одной из дисциплин структур данных (и соответственно STL) никто не давал. Во время становления курса Андрей Логвиненко вписал в программу одну лабораторную по ассоциативным контейнерам STL, но до неё практически никто не доживал.

У меня в то время уже набрался отдельный приличный опыт кодирования различных структур данных (от простого стека до сложных B-tree деревьев различных разновидностей, как динамические так и статически реализации), поэтому структуры данных были оформлены как отдельная тема. Она оказалась хорошей подготовкой к теме STL, так как структуры данных сами по себе абстрактны и не зависят от языка реализации, а STL в значительной степени реализует большое число структур данных.

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

Удержание фокуса

Каждая структура данных — это объект какого-то общего класса, который описывает данный тип структур данных. Интерфейс полностью инкапсулирует внутреннее состояние структуры.

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

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

Подробности

Структуры данных и STL слайды.

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

Одну структуру данных мы уже знаем — массив. У нас в массиве всегда хранятся элементы одного типа, доступ в С++ через оператор [] по индексу, внешний пользователь использует массив не думая о том, как и где он хранится. Хотя пользователь может рассчитывать, что элементы в массиве хранятся последовательно и доступ к ним по индексу очень быстр (например в Perl массивы хранятся не последовательно, а организованы через хэш). Элементы могут быть любого, но одного типа. Взаимодействие с ними жестко определено интерфейсом. Внешний пользователь может создавать столько массивов, сколько ему захочется, и практически для любых типов (тип должен иметь фиксированный размер или гарантию того, что по размеру не выйдет за установленный предел).

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

Стек. Имеет операции вставки и извлечения, параметры глубины и максимального размера. Обычно в памяти структура данных сама хранит указатель HEAD, чаще всего указывающий на элемент, который должен быть вставлен в последствии. Описание операций вставки и извлечения. LIFO. Две разных реализации стека — статическая и динамическая. В первом случае через массив, который мы создаем заблаговременно и работаем по нему посредством указателей. Второй случай — каждый элемент структуры данных хранит рядом с собой указатели на соседние элементы. Певый случай быстр, не требует дополнительной памяти на указатели, но съедает заданное число памяти согласно первой инициализации и имеет ограничение на размер, в то время как динамическая реализация ограничена только всей оперативной памятью.

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

Очередь. Аналогично — есть HEAD и TAIL, можно вставлять в один хвост, а извлекать только из другого. FIFO. Аналогично реализуется статически и динамически.

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

Двусторонне-связанные списки. Картинка динамической реализации. Аналогично односторонне-связанные. Преимущества и недостатки.

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

Кольцевые списки.

Как организуется структура данных — основные правила.

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

Дерево как структура данных. Каждый элемент имеет родителя и потомков. В общем случае дерево начинается с корня, каждый элемент можно отнести к какому-то уровню, связи внутри дерева не пересекаются.

Бинарное дерево — количество потомков не более 2. Это имеет свои преимущества. Например в данном случае дерево отсортировано и можно простыми операциями сравнения найти нужный элемент, ища из корня.

Сбалансированное дерево — такое дерево, в котором все кроме одного последнего уровня обязательно заполнены. Такое дерево позволяет осуществить гарантированный поиск за log2(N) операций.

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

Виды проходов деревьев (pre-order, in-order, post-order, level-order).

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

Мультимножество.

Карта (отображение, map). Мультикарта (multimap).

Хэш. Сначала разбор понятия хэш функции (функция, возвращающая элемент, который имеет конечное число состояний). Данное число состояний в хэше ассоциируется с хэш-таблицей.

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

Понятий коллизий. Коллизии это плохо. как избежать коллизий (хорошая хэш-функция и изменение размеров хэш-таблицы).

Куча (heap). Выглядит как бинарное дерево, но в нем всегда в каждой тройке нижние элементы меньше верхнего, и справа всегда меньше чем слева. Такая организация позволяет нам создать приоритетную очередь, в которой скорость вставки и извлечения высока (log N), в обычных приоритетных очередях каждый раз нужно либо искать место вставки или пересортировать. Разбор операций вставки и извлечения и почему так происходит.

Пример экзотической структуры данных — sparse array и варианта его реализации.

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

STL. Базовые (но это не все) элементы — контейнеры, итераторы, алгоритмы.

Контейнеры — это фактически те структуры данных, которые мы рассматривали ранее, но на языке С++, и они уже готовы к применению. Итераторы — специальные объекты для доступа к элементам структуры данных, близкая аналогия — указатели. Алгоритмы — готовый набор функциональных действий, позволяющий получить что-то полезное.

Каждый контейнер представляет собой упорядоченную последовательность элементов. Т.е. все элементы можно выстроить в одну цепочку друг за другом. Если мы хотим перебрать все элементы контейнера (распечатать их, найти какой-то и др.), что является типичной операцией, то это делается через итерационный перебор. Пример перебора. Понятие end-of-sequence (элемент за последним, но не последний).

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

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

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

List. В STL — динамический двусвязный список со всеми вытекающими. Удаление и добавление элементов в список. Пример.

Образование контейнеров из list'a в STL: стек, очередь и приоритетная очередь сделаны на основании list'a.

Deque.

Множества и мультимножества как деревья в STL.

Карты и мультикарты в STL. Пример.

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

Типичные методы контейнеров, характерные для всех.

Разбор алгоритмов STL. Алгоритмов много. Они безопасны, проверены и быстры. Работают как с контейнерами, так и с массивами. Нужно знать.


четверг, 1 августа 2013 г.

ПМО ИУС — Исключения

В то время, когда я учился, исключения уже как отдельное понятие существовали, но в нашем курсе они отсутствовали, а на практике в той среде, которую мы использовали (Borland C++ 3.11) они были, но реализация была ужасна — как с точки зрения производительности, так и с точки зрения количества подводных камней особенностей компилятора и как следствие, безопасности и удобства использования.

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

Кроме общего изучения механизмов исключений были сформулированы два дополнительных акцента: создание собственных классов исключений (опционно с задействованием std::exception), задействование исключений других библиотек (VCL C++Builder, другие библиотеки также могут использовать стратегию обработки исключительных ситуаций через исключения, и это мы понимаем и используем).

Удержание фокуса

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

Смысловое и функциональное значение своих классов исключений.

Подробности

Слайды.

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

Итак, ошибочная ситуация. Суть стартует с простейшего примера — необходимо написать функцию деления двух чисел A на B. Пример функции:

int
func( int a, int b )
{
    return a / b;
}

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

С точки зрения обязательств все понятно. Однако здесь может получится так, что параметр B равен 0. В этом случае разработчик находится в затруднительном положении — он может понять и проанализировать, что B=0 (через if например), но этот случай не может быть обработан, так как возвращаемый функцией результат как число будет неверным. Если такое происходит (мы понимаем, что сами разрулить ситуацию не можем из-за особенностей функции или состояния системы, но делать что-то надо), то это называется ошибочной ситуацией.

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

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

Останов программы.
Останов в надежде, что придет человек и все решит. Человек действительно может все решить, но на это может потребоваться много времени. Резкий останов позволяет быстро диагностировать факт проблемы (останов не заметить крайне сложно) и заняться её устранением (fail-fast), но например в системах реального времени, от которых многое зависит (ПО на борту самолета), прийти и разобраться будет поздно. Кроме того, может получится так, что проблема на самом деле проста, и решить её можно программной логикой.
Вернуть что-то, как будто ничего не произошло.
Самый страшный способ. Внешний пользователь не сможет узнать, что система работает некорректно, соответственно ошибку сложнее будет обнаружить, из-за чего мы будем думать, что все в порядке, а на самом деле все плохо. Однако в крайне редких случаях, например когда нет другого способа, а система должна работать, это может применяться, но при этом надо отдавать себе отчет и пытаться сделать все возможное для диагностики (страшная запись в лог) и попытки решения проблемы.
Вернуть код ошибки (некоторое.
Традиционный способ обработки ошибочных ситуаций, встречающийся во многих системах нижнего уровня. Может быть обработан широкий спектр ошибок (с добавлением кодов в документацию). Однако у него есть ряд недостатков. Во-первых, не всегда можно вернуть код ошибки (как например в нашей функции делания A на B, нет ни одного зарезервированного значения для возврата кода ошибки). Во-вторых, в случае большого числа кодов ошибок и большой вложенности функций становится сложно все это сопровождать. Фактически каждая функция должна быть проверена на возвращаемое значение (вы часто проверяете возвращаемое значение printf?), и зачастую то не делается. А если делается, то код резко разрастается, и при этом логика обработки ошибок смешивается с бизнес-логикой приложения.
Вызвать некоторую общую функцию, которая решит все проблемы.
Общая функция — это логическая обработка, которая потенциально может все. Однако здесь есть ряд проблем: не каждую ошибочную ситуацию можно обработать; в больших системах такая функция начинает на себя брать все, а это ведет её разрастанию и глобализации (зависимость в случае сохранения внутреннего состояния функции; многопоточность и пр., очень похожее на синглтон и глобальные переменные), что череповато; не всегда есть возможность вызова такого рода функции из всех контекстов.

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

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

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

Рассмотрение аналогичного примера, только уже с использованием механизма исключений.

Разбор синтаксиса исключений.

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

Обработка множественных catch (только один из, выбор сверху вниз по типу исключения).

Собственные классы исключений и их иерархии. Выбор блока обработки исключительной ситуации в случае иерархии исключений.

Повторная генерация (отсутствие копии и сохранение оригинала).

Исключения std::exception, их рекомендация к использованию, почему они не обязательные как в других языках (исторически), уже готовые стандартные, наследование от них.

Исключения C++ Builder как пример исключений со сторонних библиотек. Другие библиотеки также могут использовать исключения и соответственно их функции бросать их.

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