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

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

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

Меня всё нижесказанное, конечно, больше волнует с точки зрения разработки ядра ОС. Но почти всё применимо и к пользовательскому коду.

Кстати, ядра старых ОС в примитивах синхронизации не нуждались, поскольку преемптивной мультизадачности внутри ядра в старые добрые времена не было. (Уж за Юникс 7-й версии я отвечаю. Не было.) Точнее, единственным методом синхронизации был запрет прерываний. Но об этом позже.

Сначала перечислим героев. Мне известны следующие примитивы синхронизации:

User/kernel mode: mutex+cond, sema, enter/leave critical section.
Kernel only: spinlock, управление прерываниями.

Зачем всё это нужно, читатель, наверное, знает, но всё же уточним.

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

В прошлой заметке мы обсудили самую известную пару из лагеря инструментов синхронизации тредов — mutex и cond. Сегодня встретимся с sema — примитивом, который умеет заменять предыдущие два в одиночку.

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

Напомню фрагмент кода:

while(total_free_mem <= 0)
    {
    wait_cond(&got_free_mem, &allocator_mutex);
    }

Здесь цикл вокруг wait_cond гарантирует нам, что даже если мы вернёмся из ожидания события случайно или по ошибке, ничего страшного не случится — проверка в while обеспечит нам уверенность, что нужное состояние проверяемого объекта достигнуто. Если нет — поспим ещё в ожидании.

Отметим ещё раз, что проверяем мы состояние объекта (total_free_mem <= 0) при запертом мьютексе, то есть никто не может его менять в то же самое время.

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

(Наверное, потом напишу ещё одну про совсем уже нетипичную задачу, но это потом.)

Сегодня мы немножко заглянем в процессор. Чуть-чуть.

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

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

На уровне процесса всё так и есть — различия между спинлоком и мьютексом — чисто технические, вопрос реализации и производительности.

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

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

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

Итак, иерархия реализации такова: mutex/cond/sema сделаны на базе спинлоков, спинлоки — на базе атомарных операций, предоставляемых процессором. Мы в них немного заглянем сегодня.

Как устроен спинлок?

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

Встречайте – подсистема Intel Management Engine, самая загадочная составляющая архитектуры современных x86-платформ.

Я занимаюсь разработкой статического анализатор кода PVS-Studio для анализа программ на языке Си/Си++. После появления в PVS-Studio 4.00 анализа общего назначения мы получили множество откликов, как положительных, так и отрицательных. Кстати, предлагаю скачать новую версию PVS-Studio, в которой благодаря откликам людей было поправлено большое количество ошибок и недочетов.

В ходе обсуждения PVS-Studio 4.00 вновь встал вопрос, можно ли реализовывать большинство проверок, используя регулярные выражения, и не переусложняем ли мы, говоря, что обязательно необходимо строить и работать с деревом разбора. Вот пример комментария на эту тему. Подобный вопрос возникает уже не в первый раз, и я решил написать статью, чтобы объяснить, почему пытаться использовать регулярные выражения для анализа Си/Си++ кода — эта очень плохая идея.

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

В нашем проекте PT Application Inspector реализовано несколько подходов к анализу исходного кода на различных языках программирования:

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

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

К разрабатываемому модулю были, в числе прочих, сформулированы следующие требования:

• поддержка нескольких языков программирования и простое добавление новых;
• поддержка анализа кода, содержащего синтаксические и семантические ошибки;
• возможность описания шаблонов на универсальном языке (DSL, domain specific language).

В нашем случае все шаблоны описывают какие-либо уязвимости или недостатки в исходном коде.

Весь процесс анализа кода может быть разбит на следующие этапы:

1. парсинг в зависимое от языка представление (abstract syntax tree, AST);
2. преобразование AST в независимый от языка унифицированный формат;
3. непосредственное сопоставление с шаблонами, описанными на DSL.

Данная статья посвящена первому этапу, а именно: парсингу, сравнению функциональных возможностей и особенностей различных парсеров, применению теории на практике на примере грамматик Java, PHP, PLSQL, TSQL и даже C#. Остальные этапы будут рассмотрены в следующих публикациях.

На прошлой неделе в мире С++ произошло интересное событие. Компания Microsoft объявила о выходе обновления к компилятору С++ в Visual Studio 2013. Само по себе обновление компилятора отдельно от Visual Studio или её сервис-пака — уже нетривиальное для Microsoft событие. Но ещё интереснее то, что вошло в это обновление. Полный список можно почитать по ссылке выше, а я остановлюсь только на одном моменте — resumable функции. Для полного понимания ситуации: Microsoft изрядно протроллила и комитет по стандартизации С++ и разработчиков gcc\clang, выпустив (тут надо внимательно) реализацию экспериментальной и не утверждённой ещё возможности будущего стандарта C++17, основанной на экспериментальных и не утверждённых ещё возможностях будущего стандарта C++14, которые в свою очередь являются исправлениями не сильно ещё вошедших в повседневное программирование возможностей С++11.

Достаточно гиковский ход, не находите?

А ниже будет перевод статьи с meetingcpp.com, рассказывающей о том, что это за фича и как её использовать.

«Когда я только начинала работать в этой сфере, все это было для нас как Дикий Запад — мы были первооткрывателями неизведанных земель. Никто нас ничему не учил» Маргарет Гамильтон.



Это Маргарет. Она пишет код хорошо. Делайте как Маргарет.

А еще:

• программист-самоучка;
• написала код для навигационного компьютера программы «Аполлон»;
• когда американцы ступили на поверхность Луны ей был 31 год;
• Маргарет НЕ автор термина «software engineering»;
• часто брала на работу 4х-летнюю дочку;
• дочка помогла найти баг в программе.

Под руководством Маргарет Гамильтон писались программы для бортового компьютера КА Аполлон. В один из самых ответственных моментов миссии Аполлон 11 именно работа Маргарет и ее команды предотвратила возможный срыв высадки на Луну. За три минуты до прилунения сработало несколько аварийных сигнальных устройств. Компьютер был перегруженн входящими данными – в стыковочной радарной системе произошло непроизвольное обновление счетчика, что привело к запросу на выполнение компьютером большего числа операций, чем он был способен обработать. Благодаря устойчивой архитектуре компьютер продолжил свою работу: в разработке бортового ПО использовался подход асинхронного исполнения (asynchronous executive). Процессы с высоким приоритетом (критичные для прилунения) могли прервать низкоприоритетные процессы.

Проведя анализ 110 приложений (как Android, так и iOS), команда экспертов сделала вывод, что передача персональных данных пользователей этих приложений третьим лицам происходит достаточно часто. При этом у пользователя, зачастую, просто нет выбора. Как оказалось, подавляющее большинство проверенных приложений предоставляют Google, Apple и третьим лицам такие данные, как e-mail, имена и координаты своих пользователей. В среднем одно приложение Android отсылает данные такого рода по 3,1 адресам (доменам), а iOS приложение делает то же самое для 2,6 адресов (доменов). В некоторых случаях медицинские приложения отсылают поисковые результаты по словам «герпес» или «интерферон» не менее, чем на 5 различных доменов, не уведомляя пользователя о том, что происходит.

Эта статья – о рисках смены руководства в больших компаниях и характерных явлениях при попытках игнорировать закон эффективного управления собственностью:

Эффективно управлять можно только той собственностью, которую мог бы создать сам.
Кто не может создать, – будет только разрушать!
И.А. Дедюхова, Кодекс Хамурапи

Картинка для привлечения внимания читателей из поколений Y и Z:

Краткое содержание

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

---

Просто «El clasico»

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

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

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

«Согласно данным Научного Совета, к 2030 году количество специалистов в сфере информационно-коммуникационных технологий вырастет на 39%, а в отчете О2 за 2013 год отмечалось, что для удовлетворения спроса на такого рода специалистов в период до 2017 года потребуется порядка 745 000 новых сотрудников.

Кроме того, по результатам исследований, проведенных в прошлом году City & Guilds, три четверти работодателей из сферы IT, компьютерных и информационных услуг отметили явную нехватку квалифицированных кадров, в то время как 47% опрошенных заявили о неспособности действующей системы образования подготовить хороших специалистов».

Пара часов из жизни математика-программиста или читаем википедию

Для начала в качестве эпиграфа цитирую rocknrollnerd:

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

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

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

Раз уж пошёл эксгибиционизм про мою работу, то вот вам моё рабочее место (кликабельно):

Введение

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

Но я научился говорить, что я не знаю, что такое умножение. Да, я не знаю, что такое подалгебра над алгеброй Ли. Да, я не знаю, зачем нужны в жизни квадратные уравнения. К слову, если вы уверены, что вы знаете, то нам есть над чем поговорить! Математика — это серия фокусов. Математики стараются запутать и запугать публику; там, где нет замешательства, нет репутации, нет авторитета. Да, это престижно говорить как можно более абстрактным языком, что есть по себе полная чушь.

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

Я хотел бы подарить сообществу Хабра статью, в которой стараюсь дать достаточно полное описание подходов к алгоритмам подсчёта единичных битов в переменных размером от 8 до 64 битов. Эти алгоритмы относятся к разделу так называемой «битовой магии» или «битовой алхимии», которая завораживает своей красотой и неочевидностью многих программистов. Я хочу показать, что в основах этой алхимии нет ничего сложного, и вы даже сможете разработать собственные методы подсчёта единичных битов, познакомившись с фундаментальными приёмами, составляющими подобные алгоритмы.

В комментариях к недавнему топику возникло обсуждение: до какого размера можно ужать Windows EXE, печатающий в консоли «Hello, World!» Ответ: 268 байт, меньшие файлы Windows просто отказывается загружать.

Раз для «Hello, World!» предел возможного ужатия уже достигнут, то мне стало интересно, до какой степени удастся ужать программу, делающую хоть что-нибудь более интересное.

Сначала похвастаюсь результатом: моя программа всего на 46 байт больше теоретического минимума!

Многие считают, что неопределённое поведение программы возникает из-за грубых ошибок (например, запись за границы массива) или на неадекватных конструкциях (например, i = i++ + ++i). Поэтому для многих является неожиданностью, когда неопределенное поведение вдруг проявляет себя во вполне привычном и ничем не настораживающем коде. Рассмотрим один из таких примеров. Программируя на C/C++ никогда нельзя терять бдительность. Ад ближе чем кажется.

Вскоре после расширения своего интернет-вещания практически на весь мир, видеосервис Netflix объявил войну «пиратам» – в данном случае тем, кто пытается использовать VPN, прокси-серверы, «разблокировщики» и другие методы подмены ip для просмотра видеоконтента, не предназначенного для показа в стране проживания «злоумышленника». Глава компании заявил, что такие попытки в ближайшее время будут подвергаться безжалостной блокировке.

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

В естественном стремлении к искоренению несправедливости, пользователи обращаются к VPN-сервисам и другим средствам, позволяющим обойти географическое ограничение. Подключённый к VPN компьютер пользуется посредническими услугами одного из серверов VPN-провайдера, находящихся в «нужной» стране.

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



На яндекс видео:
video.yandex.ru/users/ztarlitz/view/5

Список лекций:

Лекция 1 — ПРИМЕР ФИЗИЧЕСКОГО ЗАКОНА — ЗАКОН ТЯГОТЕНИЯ
Лекция 2 — СВЯЗЬ МАТЕМАТИКИ С ФИЗИКОЙ
Лекция 3 — ВЕЛИКИЕ ЗАКОНЫ СОХРАНЕНИЯ
Лекция 4 — СИММЕТРИЯ ФИЗИЧЕСКИХ ЗАКОНОВ

Лекция 5 — РАЗЛИЧИЕ ПРОШЛОГО И БУДУЩЕГО
Лекция 6 — ВЕРОЯТНОСТЬ И НЕОПРЕДЕЛЕННОСТЬ — КВАНТОВОМЕХАНИЧЕСКИЙ ВЗГЛЯД НА ПРИРОДУ
Лекция 7 — В ПОИСКАХ НОВЫХ ЗАКОНОВ