книги хакеры / журнал хакер / 194_compressed

ПОСТАНОВКА ЗАДАЧИ

Наш планировщик должен уметь:

•добавлять неограниченное количество заданий на произвольные моменты времени;

•выполнять фоновые задания (даже если устройство заснуло);

•благополучно переживать перезагрузку устройства.

ВКЛЮЧИТЬ СИГНАЛИЗАЦИЮ!

Для выполнения поставленной задачи в Android предусмотрен специальный Java-класс AlarmManager (менеджер сигнализаций), позволяющий установить сигнализацию (Alarm), срабатывающую в установленное время или с заданной периодичностью. В качестве формата даты и времени сигнализации выступает старое доброе UNIX-time, то есть время, выраженное в миллисекундах, прошедших с 1 января 1970 года.

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

АРХИТЕКТУРА ПРОЕКТА

Наш проект будет разделен на четыре модуля (см. исходник):

1.Главная активность (Main.java).

2.Широковещательный приемник (AlarmReceiver.java).

3.Фоновый сервис (AlarmService.java).

4.База данных заданий (AlarmDB.java).

Главная активность (Main.java), по сути, является графическим интерфейсом нашего приложения, состоящим из стандартных компонентов — текстовых меток (TextView), полей ввода (EditView) и главной кнопки (Button). Основная его цель — определить параметры задания: дату и время, частоту срабатывания, само задание.

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

Главная активность (Main.java), по сути, является графическим интерфейсом нашего приложения, состоящим из стандартных компонентов — текстовых меток (TextView), полей ввода (EditView)

и главной кнопки (Button)

уведомление со звуком. Фоновый сервис (класс Service) в Android выполняется в главном потоке приложения и требует использования многопоточности при длительных операциях (в противном случае рискуешь увидеть раздражающее ANR — «Приложение не отвечает»). Для наших целей прекрасно подойдет класс IntentService (наследник Service), который, вопервых, самостоятельно создаст рабочий поток, во-вторых, автоматически завершится после выполнения задачи.

База данных (AlarmDB.java) — вспомогательный класс для помещения заданий в базу SQLite и их извлечения оттуда. Структура нашей таблицы представлена во врезке на следующей странице. Останавливаться на этом модуле смысла нет, так как в нем используются стандартные SQL-запросы вида INSERT/SELECT.

У тебя наверняка возник вопрос: для чего нужен широковещательный приемник (AlarmReceiver.java)? Дело

втом, что при перезагрузке устройства все сигнализации AlarmManager’а пропадают, что, естественно, нас не устраивает (см. последний пункт постановки задачи). Единственное, что мы можем сделать, — попросить систему сразу после загрузки запустить наш код, восстанавливающий все задания (о соответствующем разрешении для приложения смотри врезку). Подобная процедура должна быть обернута в широковещательный приемник (BroadcastReceiver) и определена

вpublic void onReceive(). В нашем случае эта функция будет определена статической static void scheduleAlarms(), что позволит ее вызывать из любого места приложения. Любой ши-

роковещательный приемник должен отработать максимально Приступаем к работе быстро — Android отводит для этого максимум десять секунд,

СТРУКТУРА БД

Для простоты наша база данных будет состоять из одной таблицы:

CREATE TABLE tbSheduler (

_id INTEGER PRIMARY KEY AUTOINCREMENT,

utime NUMERIC,

msg TEXT ),

где _id — первичный ключ, utime — запланированное время задания, msg — текст сообщения. В боевом проекте вместо поля типа TEXT правильнее было бы указать уникальный ключ (FOREIGN KEY), описывающий задание в рамках других связанных таблиц.

АВТОЗАГРУЗКА

Разрешение на автозагрузку приложения нужно запросить в файле-манифесте (AndroidManifest.xml):

<uses-permission android:name= "android.permission.RECEIVE_BOOT_COMPLETED" />

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

}

AlarmReceiver.scheduleAlarms(this);

SET VS SETREPEATING

Внимательный читатель наверняка заметит, что в классе AlarmManger уже есть подходящая функция для задания периодических сигнализаций — setRepeating, но, тем не менее, мы ее не используем. Эта функция, безусловно, хороша в том случае, если у тебя всего десяток сигнализаций. А если их в десять раз больше? Управлять всем этим зоопарком будет гораздо сложнее, чем в нашем случае. Кроме того, как ты сам видишь, ручной расчет периодичности с помощью Javaкалендаря (Calendar) не представляет особой сложности.

БОНУС ОТ ][

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

adb shell dumpsys

alarm > alarm.txt

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

СПЯЩИЙ ANDROID

Несмотря на то что мы использовали флаг AlarmManager. RTC_WAKEUP, существует ненулевая вероятность того, что разбуженный с его помощью фоновый сервис (IntentService) фактически не успеет начать обрабатывать намерения. Все дело в блокировке пробуждения, которой обладают широковещательный приемник (BroadcastReceiver) и менеджер сигнализаций (AlarmManager) для пробуждения устройства, но которая освобождается после выполнения кода в onReceive приемника. Фоновый сервис подобной блокировкой не обладает. На страницах «Хакера» уже поднималась эта тема в № 6 за 2013 год (см. «Задачи на собеседованиях»).

ШИРОКОВЕЩАТЕЛЬНЫЙ ПРИЕМНИК

Код приемника (AlarmReceiver.java) представлен ниже:

public class AlarmReceiver extends

BroadcastReceiver {@Override

public void onReceive(Context context, Intent intent)

{

scheduleAlarms(context);

}

static void scheduleAlarms(Context ctxt) {

long NOW = Calendar.getInstance()

.getTimeInMillis();

startAlarmService(ctxt, NOW);

}

static void scheduleAlarms(Context ctxt,

long TIME) {

startAlarmService(ctxt, TIME);

}

static void startAlarmService(Context ctxt,

long UTIME) {

Intent i = new Intent(ctxt,

AlarmService.class);

i.setAction(AlarmService.SET_ALARM);

i.putExtra("utime", UTIME);

ctxt.startService(i);

}

}

Данный код требует некоторых пояснений. Класс AlarmReceiver наследуется от суперкласса BroadcastReceiver, который требует реализации абстрактного метода public void onReceive(Context context, Intent intent), срабатывающего при поступлении определенного намерения (в нашем случае — intent.action.BOOT_COMPLETED). Любой приемник должен быть обязательно зарегистрирован в манифесте приложения (AndroidManifest.xml):

<receiver android:name=".AlarmReceiver" >

<intent-filter>

<action android:name=

</receiver>

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

ИЗУЧАЕМ ГЕТЕРОГЕННЫЙ ПАРАЛЛЕЛИЗМ НА C++ С ПОМОЩЬЮ AMP

Когда увеличивать количество транзисторов на ядре микропроцессора стало физически невозможно, производители начали помещать на один кристалл несколько ядер. Вместе с тем появились фреймворки, позволяющие распараллеливать исполнение кода: Threading Building Blocks и Cilk от Intel,

Concurrency Runtime (включает Parallel Patterns Library и Asynchronous Agents Library) и Task Parallel Library (первый для нативного кода, второй для управляемого) от Microsoft и другие. И это было только начало. Производители видеоадаптеров — графических процессоров тоже не стояли на месте, они добавляли ядра не единицами, а десятками и сотнями. И программистам это понравилось!

Юрий «yurembo» Язев, независимый игродел yazevsoft@gmail.com

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

их мощью, чтобы передать на графические ускорители часть вычислений. Поскольку ГП невозможно использовать таким же образом, как ЦП, понадобились новые инструменты, которые не заставили себя ждать. Так появились CUDA, OpenCL и DirectCompute. Эта новая волна получила имя GPGPU (General-purpose graphics processing units), обозначающее технику использования графического процессора для вычислений общего назначения. Таким образом, для решения весьма общих задач стали использоваться несколько совершенно разных микропроцессоров, что породило название «гетерогенный параллелизм». Собственно, это и есть тема нашего сегодняшнего разговора.

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

CUDA

Итак, CUDA — запатентованная технология GPGPU от NVIDIA, и в этом совсем нет ничего плохого. Для написания Cudaскриптов используется язык, близкий к C, но со своими ограничениями. В целом — заслуживающая внимания и довольно широко используемся технология. Между тем зависимость от конкретного вендора портит всю картину.

FIRESTREAM

FireStream — то же самое, что CUDA, только от AMD, поэтому не будем задерживать пациента.

OPENCL

OpenCL — открытый язык вычислений, свободная, непатентованная технология, весьма интересное зрелище, однако в своей основе это весьма отличный от C язык (хотя разработчики говорят об обратном). В таком случае программисту придется изучать почти полностью новый язык с нестандартными функциями. Это навевает грусть. К тому же, так как не существует стандарта на двоичный код, компилятор от любого вендора имеет полное право генерировать несовместимый код, из чего следует, что на каждой платформе шейдеры придется перекомпилировать, для чего необходимы их исходные коды. Изначально OpenCL был разработан в Apple, ну а сейчас им заведует Khronos Group — так же, как OpenGL.

лирующий ГП на ЦП, также называется средством программной отрисовки. Он работает гораздо медленнее аппаратного ГП. Присутствует только в Windows 8. Используется главным образом для отладки приложений. CPU accelerator есть как в Windows 8, так и в Windows 7. Тоже очень медленный, поскольку работает на ЦП, применяется для отладки. Microsoft Basic Renderer Driver — лучший выбор из эмулируемых ускорителей, также работает на CPU, поставляется в комплекте с Visual Studio 2012 и выше. Он же известен как WARP (Windows Advanced Rasterization Platform). Для рендеринга использует функциональность Direct3D. Повышенная скорость работы по сравнению с другими эмуляторами достигается благодаря применению инструкций SIMD (SSE).

Кроме того, для разработки и отладки C++ AMP приложений рекомендуется использовать ОС Windows 8, и это утверждение я готов аргументировать. Как я говорил выше, вопервых, это поддержка отладки на эмулируемом ускорителе, поддержка вычислений с двойной точностью, благодаря спецификации WDDM 1.2, увеличенное количество буферов (я про буферы DirectCompute), позволяющие запись (c поддержкой DirectX 11.1). И самое главное — из-за того, что в Windows 8 во время копирования данных из ускорителя в память ЦП глобальная блокировка ядра не захватывается (в отличие от положения дел на Windows 7), операция копирования происходит быстрее, от чего возрастает общая производительность.

ЭЛЕМЕНТЫ AMP

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

Мы уже видели объект класса accelerator, представляющий вычислительное устройство. По умолчанию он инициализируется самым подходящим из имеющихся акселераторов. После получения с помощью функции get_all списка всех присутствующих ускорителей ему методом set_default можно назначить другой ГП, передав в параметре путь к последнему. Каждый ускоритель (объект класса accelerator) имеет одно или несколько изолированных логических представлений (находящихся в памяти видеоадаптера), в которых производят вычисления нити, относящиеся к данному конкретному ГП. Объект класса accelerator_view представляет собой своего рода ссылку на ускоритель. Она позволяет более широко работать с объектом: например, у тебя будет возможность обрабатывать исключения TDR — обнаружение тайм-аута и восстановление (такое исключение происходит, к примеру, если ГП выполняет вычисления дольше двух секунд, при этом

вWindows 7, в отличие от Windows 8, исключения TDR нельзя отключить). Если это исключение не обработать и не передать вычисления на другой accelerator_view, тогда восстановить работу можно только перезапуском приложения. Шаблонный тип array, как и следует из названия, представляет набор данных, предназначенных для вычислений на ГП. Эта коллекция создается в представлении ГП. Чтобы создать коллекцию данного типа, надо передать конструктору два параметра: тип данных и количество объектов данного типа. Можно создать массив разных размерностей (до 128), задается в конструкторе или путем изменения его шаблонного типа extent <>; имеются перегруженные конструкторы; заполнить массив значениями можно как на этапе его создания (в конструкторе), так и после (с помощью метода copy). Для определения позиции элемента в массиве существует специальный шаблонный тип index <>. Тип array_view относится к типу array так же, как accelerator_view к accelerator, другими словами — представляет собой ссылку. Она может быть кстати, когда не нужно копировать данные из памяти ЦП в память ГП и обратно. Например, коллекция array всегда находится в памяти ГП, то есть

вмомент ее инициализации данные копируются из ЦП в ГП. С другой стороны, если объявить объект array_view на основе вектора из области ЦП, данные вектора не будут скопированы до момента непосредственной работы с ГП, а эта работа выполняется внутри алгоритма parallel_for_each. Таким образом, это единственная точка приложения, где код распараллеливается для выполнения на акселераторе. Код выполняется на том ГП, массив которого передан алгоритму. В первом параметре parallel_for_each получает объект extent (или размерность) массива объектов, для которых алгоритм выполняет

Рис. 2. Доступные

ускорители

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

В итоге самое медленное место в любом приложении, использующем вычисления на GPU, — это копирование данных из памяти ЦП в память ГП и обратно. Поэтому необходимо это учитывать, и если вычислений немного, то, скорее всего, будет быстрее их выполнить на CPU.

ПРИМЕНЕНИЕ AMP

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

Итак, установим DirectX SDK, выпуск от июня 2010 года (версия, включающая 11-ю версию интерфейсов). Рассмотрим пример для работы с графикой: вращение треугольника, построенного средствами Direct3D 11. Открой проект DXInterOp. Если построить и запустить приложение, то мы увидим следующее изображение, только в динамике (рис. 3).

Файл DXInterOpsPsVs.hlsl содержит вершинный и пиксельный шейдеры, в файле DXInterOp.h, кроме макросов безопасного удаления объектов, объявлена структура двумерной вершины (Vertex2D), используемая на протяжении всей программы. В файле DXInterOp.cpp находится основной код приложения: создание окна, инициализация графической подсистемы (создание, разрушение устройства Direct3D, загрузка и создание объектов шейдеров, построение треугольника, заливка + перерисовка окна) и так далее. Весь этот код использует функциональность Direct3D и потому не является темой нашего сегодняшнего разговора. В файле ComputeEngine.h находится интересующая нас часть приложения. Класс AMP_compute_engine отвечает за преобразование координат вершин. В его конструкторе создается ссылка на объект accelerator, который представляется устройством Direct3D. Затем этот класс инициализирует объект m_data, который представлен уникальным указателем на одномерный массив вершин (объявленный ранее как Vertex2D). Рабочей лошадкой класса выступает функция run, в которой в алгоритме parallel_ for_each внутри лямбда-выражения вычисляется новая позиция координат для поворота треугольника:

parallel_for_each(m_data->extent, [=, &data_ref]

(index<1> idx) restrict(amp)

{

DirectX::XMFLOAT2 pos = data_ref[idx].Pos;

data_ref[idx].Pos.y = pos.y *

cos(THETA) - pos.x * sin(THETA);

data_ref[idx].Pos.x = pos.y * sin(THETA)

+ pos.x * cos(THETA);

});

Обрати внимание на интродуктор лямбды: указывается, что data_ref типа array<Vertex2D, 1> передается по ссылке, а объект idx типа index — по значению, этот индекс является номером выполняемой в данный момент нити.

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

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

БЛОЧНЫЕ АЛГОРИТМЫ

Когда вычисления происходят на GPU, то, в отличие от CPU,

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

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

tile_static int num[32][32];

107

Алгоритм parallel_for_each имеет перегруженную версию, которая в качестве первого параметра принимает объект класса tiled_extent — extent, разделенный на блоки в двумерном или трехмерном пространстве. Вот пример:

parallel_for_each(extent<2>(size, size), =,

&input, &output ( (index<2> idx) restrict(amp)

В этом примере имеем массив size*size в двумерном пространстве. Когда алгоритму parallel_for_each первым параметром передается tiled_extent, то лямбде передается объект tiled_index, в том же пространстве, что tiled_extent:

parallel_for_each(extent<1>(number_of_threads).

tile<_tile_size>(), =

(tiled_index<_tile_size> tidx) restrict(amp)

Внутри лямбды из объекта tiled_index можно получить доступ как к глобальному, так и к локальному индексу с помощью свойств global и local:

const int tid = tidx.local[0];

const int globid = tidx.global[0];

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

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

Рассмотрим такой случай. Перед обработкой данных внутри лямбды они копируются из коллекции глобальной в коллекцию в блочно-статической памяти. После этого вызывается алгоритм для обработки коллекции в блочно-статической памяти. Но если, предположим, заполнение массива происходило в соответствии с индексом нити, то перед обработкой он может быть заполнен не полностью, так как нити выполняются независимо и, дойдя до вызова алгоритма, ни одна нить не в состоянии узнать, выполнилась ли каждая нить, то есть заполнен ли массив полностью. В таком случае перед вызовом алгоритма надо вставить вызов метода wait объекта класса tile_barrier, который невозможно создать независимо, но можно получить из объекта класса tile_index, переданного в лямбду: tidx.barrier.wait();

tile_static int num[32][32];

num[tidx.local[0]][tidx.local[1]] =

arr[tidx.global];

tidx.barrier.wait();.

if (tidx.local == index<2>(0,0)) {

num[0][0] = t[0][0] + num[0][1] +

num[1][0] + num[1][1];

}

ЗАКЛЮЧЕНИЕ

AMP может быть использован не только из C++, но и из управляемого кода, например на C#. Вдобавок приложения для Windows Store тоже в полной мере используют C++ AMP — гетерогенный параллелизм на графических ускорителях, которые в настоящее время есть не только в ПК, но и в планшетах и смартфонах.

Опять опасный мужчина Иннокентий Сенновский, этот Самсон цифрового мира и Геркулес дебаггинга, справился с очередными задачками самым первым. Ну что с ним поделаешь? Будет награжден. А вот и его решение.

Впервом задании сначала собираем указатель на функцию обработчика прерывания sysenter. От начала ищем сигнатуру вызова диспетчера прерывания по номеру сискола. Следующие 4 байта, на которые будет указывать ptr в случае правильной сигнатуры, — это адреса отдельных обработчиков (таблица сисколов).

Второе задание на этот раз очень интересное. Сначала о структуре файла. В начале даны 4 байта, в которых количество константных переменных строк. Далее структуры — 2 байта длины и сама строка. Далее количество динамических переменных (4 байта). Далее 1 байт типа переменной: 0x09 — хендл, 0x05 — массив. После байта типа следуют 4 байта описания.

Вних хранится номер строки-константы, которая описывает эту переменную. Если тип 0x9, то после сразу идут 2 байта под хендл, если 0x5, то 1 байт

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

Теперь команды по порядку. 0x65 — первый аргумент является индексом переменного массива, второй — индексом константной строки. Оба по 4 байта (вообще, в коде все аргументы по 4 байта). Так мы собираем в массиве строку «Greetings from the Dreamworld!». 68 — открытие файла (аргумент — константа-имя Kaspersky). 0x69 — сохранение хендла от файла. Два аргумента — первый динамический (индекс переменной-хендла), второй — константный (имя файла, который уже быт открыт). 0x6c — аналогично 0x6b, но в отличие от 0x6b второй аргумент — индекс переменной, а не константы. Записывает строку в файл по индексу хендла. То есть записывает в файл Kaspersky строку «Greetings from the Dreamworld!». 0x6a — освобождение хендла по индексу. Все.