Пару дней назад я опубликовал и потом внезапно убрал в черновики статью о плане написать про создание своей ОС для архитектуры ARM. Я сделал это, потому что получил много интересных отзывов как на Хабре, так и в G+.

Сегодня я попробую подойти к вопросу с другой стороны, я буду рассказывать о том, как программировать микроконтроллеры ARM на нарастающих по сложности примерах, пока мы не напишем свою ОС или пока мне не надоест. А может, мы перепрыгнем на ковыряние в Contiki, TinyOS, ChibiOS или FreeRTOS, кто знает, их там столько много разных и интересных (а у TinyOS еще и свой язык программирования!).

Итак, почему ARM? Возиться с 8-битными микроконтроллерами хотя и интересно, но скоро надоедает. Кроме того, средства разработки под ARM обкатаны долгим опытом и намного приятнее в работе. При этом, начать мигать светодиодами на каком-то «evaluation board» так же просто, как и на Arduino.

Данная статья написана в форме поста для блога. Если она окажется вам интересной, то будет продолжение.

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

Общая задумка (пока весьма далёкая от реализации) следующая: единое 64-битное адресное пространство с вечно живущими нитями (как у Phantom OS); виртуальная машина, обеспечивающая безопасность исполнения кода. На данный момент реализованы:

1. загрузка ядра при помощи multiboot-загрузчика (GRUB);
2. текстовый VGA-режим (16-цветов, kprintf);
3. простой интерфейс настройки отображения страниц;
4. возможность обработки прерываний на C;
5. идентификация топологии процессоров (сокеты, ядра, потоки) и их запуск;
6. работающий прототип вытесняющего SMP-планировщика с поддержкой приоритетов;

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

Введение

Numenta NuPIC — открытая реализация алгоритмов, моделирующих процессы запоминания информации человеком, происходящие в неокортексе. Исходные коды NuPIC на github

В двух словах, назначение NuPIC можно описать как «фиговина, выявляющая, запоминающая и прогнозирующая пространственные и временные закономерности в данных». Именно этим большую часть времени занимается человеческий мозг — запоминает, обобщает и прогнозирует. Очень хорошее описание этих процессов можно найти в книге Джеффа Хокинса «On Intelligence» (есть русский перевод книги под названием «Об интеллекте»).

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

HotSpot JVM имеет множество опций для отслеживания происходящего в виртуальной машине: PrintGC, PrintCompilation, TraceClassLoading и т.п. Как правило, они включаются параметрами командной строки, например, -XX:+PrintGCDetails. Однако порой возникает необходимость включить или выключить такой флаг непосредственно во время работы приложения, когда перезапуск JVM с другими параметрами невозможен. Этого можно добиться как штатным, так и хакерским способом, причем последний и мощнее, и интереснее. Впрочем, внимания заслуживают оба.

Из данной статьи вы узнаете:

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

UPD: схема заменена на вариант с контейнерами из С++11, соавторы — в комментариях ниже

В рамках своей научной активности реализовал так называемый Федеративный Фильтр Калмана (Federated Kalman Filter). В этой статье рассказывается о том, что такое «Федеративный ФК», чем он отличается от обобщенного, а также описывается консольное приложение, реализующее данный фильтр и генетические алгоритмы для подбора параметров его математической модели. Приложение было реализовано с использованием TPL (Task Parallel Library), поэтому пост будет интересен не только специалистам по цифровой обработке сигналов.

UPD1: после прочтения двух недавних статей решил тоже присоединиться к эксперименту/исследованию/авантюре (называйте как хотите). В конце статьи добавил еще один опрос — "Стали бы Вы поощрать рублем такие узко специализированные статьи на Хабрахабре?".

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

В статистике тоже есть нечестный метод, который позволяет получить примерный ответ на многие практические вопросы без анализа, грубой компьютерной силой: бутстрап (англ. bootstrap). Придумал и опубликовал его в 1979 году Брэдли Эфрон.

Rust — новый язык программирования, разрабатываемый корпорацией Mozilla. Главная цель разработчиков — создание безопасного практичного языка для параллельных вычислений. Первая версия языка была написана Грэйдоном Хором в 2006 году, а в 2009 году к разработке подключилась Mozilla. С тех пор изменения претерпел и сам компилятор, изначально написанный на OCaml: он был успешно переписан на Rust с использованием LLVM в качестве back-end.

Основным продуктом, разрабатываемым на Rust, является новый веб-движок Servo, разработка которого также ведется Mozilla. В 2013 году к разработке Rust и Servo присоединилась корпорация Samsung Electronics, при активном участии которой код движка Servo был портирован на ARM архитектуру. Поддержка языка столь серьезными игроками IT индустрии не может не радовать и дает надежду на его дальнейшее активное развитие и совершенствование.

Язык Rust просто не может не понравится системным и сетевым разработчикам, тем, кому по работе приходится писать много кода, производительность которого критична, на C и C++, потому что:

1. Rust ориентирован на разработку безопасных приложений. Сюда входит безопасная работа с памятью: отсутствие null-указателей, контроль за использованием не инициализированных и деинициализированных переменных; невозможность совместного использования разделяемых состояний несколькими задачами; статический анализ времени жизни указателей.
2. Rust ориентирован на разработку параллельных приложений. В нем реализована поддержка легких (зеленых) потоков, асинхронного обмена сообщениями без копирования пересылаемых данных, возможность выбора размещения объектов на стеке, в локальной куче задачи или куче, разделяемой между задачами.
3. Rust ориентирован на разработку эффективных по скорости и памяти приложений. Использование LLVM в качестве back-end позволяет производить компиляцию приложения в нативный код, а простой интерфейс взаимодействия с C кодом – легко использовать уже имеющиеся высокопроизводительные библиотеки.
4. Rust ориентирован на разработку кросс-платформенных приложений. Компилятор официально поддерживается на платформах Windows, Linux и Mac OS X, при этом существуют порты на другие *NIX платформы, такие как FreeBSD. Также поддерживается и несколько архитектур процессоров: i386, x64 и ARM.
5. Rust позволяет писать в разных стилях: объектно-ориентированном, функциональном, actor-based, императивном.
6. Rust поддерживает уже существующие отладочные инструменты: GDB, Valgrind, Instruments.

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

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

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

В первой части этой статьи мы познакомились с форматом UEFI Capsule и Intel Flash Image. Осталось рассмотреть структуру и содержимое EFI Firmware Volume, но для понимания различий между модулями PEI и драйверами DXE начнем с процесса загрузки UEFI, а структуру EFI Firmware Volume отставим на вторую часть.

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

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

Недавно я выложил в сеть под BSD лицензией небольшой проект на 8 килострочек C кода. Официально это коллекция бенчмарков для моих клиентов — вендоров промавтоматики. Код очень специфический, и, на первый взгляд, малоприменим за пределами узкой области PLC и motion control. Но есть небольшая изюминка, на которой я не очень акцентировал внимание в статье на IDZ. В поставку бенчмарков включена baremetal среда для их исполнения. В этом посте я опишу, что это такое, и как ее можно использовать.

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

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

В повседневной практике разработчика встраиваемых систем приходится сталкиваться с необходимостью запуска двух и более разноплановых ОС на n-ядерных системах на кристалле. Это, как правило, Linux и специализированная RTOS. На плечи Linux ложится работа с тяжеловесными стеками протоколов, а RTOS же занимается задачами реального времени.
 
Одна из основных задач, которая встает при такой организации системы — обеспечение механизма взаимодействия, то есть межъядерный обмен данными. Если вам интересно узнать один из вариантов решения на базе открытой библиотеки OpenMCAPI, пролистать пару десятков строк программного кода и увидеть реальные цифры пропускной способности при использовании этой библиотеки, добро пожаловать под кат.

На прошедшем неделю назад чемпионате мира по командному программированию ACM ICPC 2013 было 11 задач, одну из которых за отведённое время не смогла решить правильно ни одна из команд.

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

В этом году на ACM ICPC был 21 аналитик из Швеции, Нидерландов, США, Словакии, Беларуси и России. И 10 из них были из Яндекса. Все они в разные годы были призёрами ICPC. Специально для Хабра они разобрали все задания чемпионата.

Внимание: перед тем как читать текст ниже, вы уже должны иметь представление о том, что такое монады. Если это не так, то прежде прочитайте вот этот пост!

Перед нами функция half:


И мы можем применить её несколько раз:

half . half $ 8
=> 2

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

half x = (x `div` 2, "Я только что располовинил  " ++ (show x) ++ "!")

Что ж, отлично. Но что будет если вы теперь захотите применить half несколько раз?

half . half $ 8

Вот то, что мы хотели бы, чтобы происходило:


Спойлер: автоматически так не сделается. Придётся всё расписывать ручками:

finalValue = (val2, log1 ++ log2)
    where (val1, log1) = half 8
          (val2, log2) = half val1

Фу! Это ни капли не похоже на лаконичное

half . half $ 8

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

Вот некое простое значение:


И мы знаем, как к нему можно применить функцию:


Элементарно. Так что теперь усложним задание — пусть наше значение имеет контекст. Пока что вы можете думать о контексте просто как о ящике, куда можно положить значение:


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

data Maybe a = Nothing | Just a

Позже мы увидим разницу в поведении функции для Just a против Nothing. Но сначала поговорим о функторах!

От Аристотеля к Витгенштейну

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

Предисловие

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



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

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

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

Пользователи желают иметь примерно такие типы данных

Пользователи хотели иметь возможность составлять данные так, как они сами того хотят. Хотели, хотят, и наверняка будут хотеть. Всё больше, всё разнообразней и сильнее.
Именно поэтому полезно проследить за развитием пользовательских типов данных в программах и языках программирования.