Showing posts with label описание. Show all posts
Showing posts with label описание. Show all posts

Sunday, December 14, 2014

Пиринговый браузер

Bittorent планирует выпустить браузер базирующийся на использовании пиринга для получения данных с сайтов, возможно такая идея имеет некоторые затруднения:
  1. популярность, нужно получить достаточный процент использования, чтобы выйти на уровень эффективности технологии и как следствие требуются плагины для основных браузеров или модуль проксирования для поддержки остальных браузеров;
  2. при кажущейся приватности: сайт и провайдер теряют к какой-то степени возможность контроля за трафиком, переходя в ранг трекеров, но в тоже время все соседи с которых идет скачивание контента начинают видеть хоть и частично весь трафик. И появляются проблемы с https/http 2.0 - загнать такой трафик в пиринговую сеть сложно так как каждый пакет шифруется ключом зависящим от сессии и как следствие его не расшариш без сессии нужны надежные обходные пути. 

Анонимность номера

Счастье всем даром 
и пусть никто не  уйдет обиженным.
Стругацкие.

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

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

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

Monday, September 7, 2009

Уникальные идентификаторы для контента

В принципе можно решать как общую задачу создания уникальных идентификаторов:
  • использовать данные генератора случайных чисел (не удобно так как не возможно четко контролировать результат);
  • использовать псевдослучайные значения, например время, процесс/поток с последующим преобразованием в символьное имя;
  • символьное имя очень полезно - так как позволяет лучше при отладке отличать идентификаторы (числа в любом виде хуже отображают отличия);
, а можно учитывать специфику:
  • имена должны поддерживаться файловой системой(запрет на использование спец символов);
  • максимально короткие эффективные имена(снижение затрат памяти), использование всего пространства допустимых символов,
  • близкие по времени создания и исходному значению имена должны быть максимально случайны по результату - то есть использовать максимально эффективный хеш-функцию - обычно достигается использованием хеш значений от псевдослучайных факторов времени создания, процесса/потока и идентификатора хранилища;
  • решение противоречивой в общем-то задачи:
    • максимального разброса имени контента для сохранения;
    • и возможности по имени определить максимально быстро наиболее вероятное хранилище в распределенной системе можно использовать 2 имени - внутреннее и внешнее;
    • внутреннее должно быть максимально эффективно дробить множество доступных вариантов размещения в локальной системе с разбиением на подкатологи с минимальной вероятностью превышения пределов на одновременное количество вложенных каталогов. Это ограничение возникает как из-за временных затрат при работе с большими каталогами, вытекающее иногда в невозможность добавления данных в каталог, и удобства конечного владельца системы, хоть и редко, но удобнее ходить по маленьким каталогам. Также при максимальном разбросе можно разместить часть каталогов на другом разделе и реализовать дешёвое подобие RAID.
    • внешнее - не противоречить правилам для протокола доступа, например не содержать спец символов специфичных для http и html разметки. Позволять легко определить максимально вероятное место расположения в распределенной системе для быстрого выявления не корректно отвечающей части, также при дублировании на другие ресурсы - можно легко удалить данные не специфичные узлу при окончании ресурсов.
Очень желательно, чтобы в внутреннем имени присутствовали хеш функция от размера данных (можно просто выделение остатка от деления на какое-то число с получением base64 + как подкаталог base64 от полного размера) и его контента (для снижение количества коллизий лучше сразу два хеш значения от контента). В результате можно быстро найти подобный контент найдя подобную запись в списке преобразований внутреннее имя <-> внешнее имя или, что должно работать гораздо быстрее при большом количестве разнообразного контента, присутствия такого каталога на диске. В дальнейшем можно проверить его содержимого на совпадение с добавляемыми данными. Как результат мы не будем забивать хранилище дубликатами и при желании сможем сообщать, что пользователь пытается снизить энтропию вселенной.

Wednesday, June 24, 2009

Параметры мобильного телефона используя wurfl

Для того чтобы определить параметры мобильного телефона можно использовать 2 пути:
  • определение свойств на основе мобильного профайла возвращенного в заголовках запроса (CC/PP);
  • определение на основе данных переданных в качестве UserAgent.
Первый случай дает возможность сделав несколько запросов на профайл и изменения в нем по протоколу CC/PP получить полные официальные данные об устройстве, но этот случай имеет несколько недостатков, указанный в профайле ресурс может быть недоступен и мы терем время на эти запросы.

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

Принцип работы с базой wurfl:
  1. найти максимально похоже имя user agent по xpath пути:"/wurfl/devices/device/@user_agent. (В первой версии искалось полное соответствие.)
  2. определить идентификатор этого описания: "/wurfl/devices/device[@user_agent='UserAgent']/@id"
  3. попытаться получить описание нужного нам свойства используя: "/wurfl/devices/device[@id='идентификатор']/group[@id='markup']/capability[@name='html_wi_oma_xhtmlmp_1_0']/@value" . markup - имя группы свойств, html_wi_oma_xhtmlmp_1_0 - свойство.
  4. Если получить не удалось получаем идентификатор подобного устройства: "/wurfl/devices/device[@id='идентификатор']/@fall_back".
  5. Если получить описание устройства не удается через fall_back мы всегда попадем на описание generic устройства, у которого значение всех свойств равно false.
Ссылки:

Friday, March 27, 2009

Простейшая реализация OpenID

Документация изначально написана для внутреннего пользования при создании модуля работы с OpenId. Модуль поддерживает только часть функционала openid (только регистрацию по первой версии OpenId). Результат можно посмотреть в здесь. Поддерживает только идентификаторы вида http://имя пользователя с именем провайдера - на этот идентификатор все openid провайдеры должны возвращать свое описание в заголовках страницы. Решил выложить, так как за пол года не появилось более полной реализации по сравнению с той, что есть у меня.

Общие шаги(OpenID *)

Полученному идентификатору запрашиваем страницу в ней ищем значения openid2.provider(OpenId 2.0), openid.delegate (OpenId 1.0 в общем случае должен совпадать с введенным именем пользователя), openid2.local_id(OpenId 2.0 в общем случае должен совпадать с введенным именем пользователя), openid.server (OpenId 1.0) и X-XRDS-Location (OpenId 2.0).

Например:
  • <link rel="openid2.provider" href="http://openid.yandex.ru/server/" />
  • <link rel="openid2.local_id" href="http://openid.yandex.ru/имя пользователя/" />
  • <link rel="openid.server" href="http://openid.yandex.ru/server/" />
  • <meta http-equiv="X-XRDS-Location" content="http://openid.yandex.ru/имя пользователя/yadis/" />
Для OpenId 1.0 Перенаправление пользователя для проверки его валидности

Сделать запрос к серверу (openid.server) на проверку пользователя (openid2.local_id) режим checkid_setup - так как это простейший режим и требующий минимальной реализации с нашей стороны:
  1. [openid.server]?
  2. openid.mode=checkid_setup&
  3. openid.identity=[openid2.local_id]&
  4. openid.return_to=[Путь на который нужно вернуться]&
  5. openid.trust_root=[Проверяем доверие серверу(доменное имя)]&
  6. openid.claimed_id=[openid2.local_id]
Для OpenId 2.0 Получение дополнительной информации

По полученному X-XRDS-Location получаем Yadis документ:
<?xml version="1.0" encoding="UTF-8" ?>
<xrds:XRDS xmlns:xrds="xri://$xrds" xmlns="xri://$xrd*($v*2.0)">
<XRD>
<Service priority="20">
<Type>http://specs.openid.net/auth/2.0/signon</Type>
<Type>http://openid.net/signon/1.0</Type>
<URI>http://openid.yandex.ru/server/</URI>
<LocalID>http://openid.yandex.ru/имя пользователя/</LocalID>
</Service>
</XRD>
</xrds:XRDS>

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

Возвращаемый сайтом ответ через обратное переполнение
В результате проверки на сайт мы должны вернуться в любом случае с такими параметрами:
  1. Удачный:
  • [Вернутся на такой url]?
  • openid.assoc_handle=[Тип подписи]&
  • openid.identity=[openid2.local_id]&
  • openid.mode=id_res& (нам доверяют)
  • openid.op_endpoint=[openid.server]&
  • openid.response_nonce=[временной штамп]&
  • openid.return_to=[Вернутся на такой url]&
  • openid.sig=&(подпись)
  • openid.signed=(от каких полей подпись)
  1. Не удачный
  • [Вернутся на такой url]?
  • openid.mode=cancel (вам не доверяют)
Проверка подписи
Для яндекса проверка не сработала, когда я тестировал модуль, возможно я что-то делаю не так. Стандартный код проверки OpenId тоже не делал эту проверку.

После получения мы должны проверить, а те ли нам ответили и запросить с сервера дополнительные сведения:
  • [openid.server]?
  • openid.mode=check_authentication&
  • openid.assoc_handle=[Значение openid.assoc_handle из предыдущего запроса]&
  • openid.sig=[Значение openid.sig из предыдущего запроса]&
  • openid.signed=[Значение openid.signed из предыдущего запроса]&
  • openid.identity=[Значение openid.identity из предыдущего запроса]&
  • openid.return_to=[Значение openid.return_to из предыдущего запроса]

Saturday, January 24, 2009

Protothreads(перевод)

Перевод описания Protothreads, пытался перевести
максимально близко к тексту.

Введение

Protothreads - программная модель разработанная Adam Dunkels объединяющая достоинства событие-ориентированной модели (event-driven) (иногда называемый конечным автоматом (state machine) и потокового программирования. Основным достоинством событийной модели является эффективное использование памяти и скорости исполнения. Основным достоинством потоковой модели является простота алгоритма (algorithm clarity). Протопотоки получают достоинства обоих моделей, предоставляя также экстремально легковесные потоки. Как и в событийно-ориентированным программировании мы имеет единый стек, но также благодаря потоковому программированию функция может (хотя-бы в теории) содержать примитивы взаимоблокировки. В текущей реализации мы имеем:

  • не реализует стандартное API (POSIX или какие-либо другие);
  • не требуется ассемблерный код или использование setjmp/longjmp;
  • кросс-платформенная реализация;
  • не вытесняющий (non-preemptibly) планировщик и четко определенный порядок(deterministically) выполнения;
  • не использует возможностей SMP.

Я решил переписать эту версию с нуля без совместимости с другими более ранними версиями протопотоков. Реализация имеет только одну не определенную стандартом С особенность - использование переменных как меток перехода (gcc label variables).

Проект включает:

  • Полный исходный код (около 400 строк включая комментарии);
  • реализацию двух примитивов синхронизации (семафоры и блокировки);
  • около 800 строчек тестового кода;
  • gdb макросы для отображения стека потока или потоков.

Потоки без стека

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

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

Вы можете считать протопоток обычной событийно-ориентированной моделью. В такой модели(если обрабатывается запрос) обычно сохраняется только указатель на функцию (или состояние( state)) которое используется в больших операциях условных переходов (switch) вместо отдельных функций) и контекст(context), включающих текущее состояние обработки. В протопотоках не используется указатель на функции и контекст, переход осуществляется непосредственно на адрес(без функции). Этот адрес гораздо лучше описывает состояние чем указатель на функцию. Действительно, протопотоки более универсальны; если функция A вызывает функцию B, B вызывает C и C блокируется, тогда поток сохраняет только три указателя на реальное место запуска в середине этих функций.

Пример производитель-потребитель

Далее показана версия известного алгоритма производитель-потребитель с двумя потоками и одним общим почтовым ящиком. Здесь описана основная идея, детали описаны далее. Все функции и типы протопотоков начинаются с префикса pt_ или для системных функций protothread_. Каждый поток требует описания контекста (context structure):
 typedef struct {
pt_thread_t pt_thread;
pt_func_t pt_func;
int i;
int * mailbox;
} pc_thread_context_t;

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

Пример 2 описание потоков производителя и потребителя:

 static pt_t
producer_thr(void * const env)
{
pc_thread_context_t * const c = env;
pt_resume(c);

for (c->i = 1; c->i <= 100; c->i++) {
while (*c->mailbox) {
/* mailbox is full */
pt_wait(c, c->mailbox);
}
*c->mailbox = c->i;
pt_signal(pt_get_pt(c), c->mailbox);
}
return PT_DONE;
}

static pt_t
consumer_thr(void * const env)
{
pc_thread_context_t * const c = env;
pt_resume(c);

for (c->i = 1; c->i <= 100; c->i++) {
while (*c->mailbox == 0) {
/* mailbox is empty */
pt_wait(c, c->mailbox);
}
assert(*c->mailbox == c->i);
*c->mailbox = 0;
pt_signal(pt_get_pt(c), c->mailbox);
}
return PT_DONE ;
}

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

Эта технология синхронизации потоков (и термин канал "channel") впервые использовалась в ядре UNIX. Концепция подобна переменным состояния (condition variable) в POSIX потоках -- в данном случае память не ассоциируется с каналом или переменной состояния(как в POSIX); сигнал или смена состояние переменной для ожидающего потока не изменяет его состояния. Основной причиной выбора реализации использующей канал, является простота реализации, так как не требуется выделение переменной состояния. API также включает pt_broadcast(), подобный pt_signal() отличающийся от него только тем что он пробуждает все ожидающие потоки, не только наиболее длительно ожидающие.

Тестовая функция создает служебный объект и контекст для каждого потока, инициализирует почтовый ящик, создает потоки, и выполняет цикл пока выполняется условие:

 static void
test_pc(void)
{
protothread_t const pt = protothread_create();
pc_thread_context_t * const cc = malloc(sizeof(*cc));
pc_thread_context_t * const pc = malloc(sizeof(*pc));
int mailbox = 0;

/* set up consumer context, start consumer thread */
cc->mailbox = &mailbox;
cc->i = 0;
pt_create(pt, &cc->pt_thread, consumer_thr, cc);

/* set up producer context, start producer thread */
pc->mailbox = &mailbox;
pc->i = 0;
pt_create(pt, &pc->pt_thread, producer_thr, pc);

/* while threads are available to run ... */
while (protothread_run(pt)) {
}

/* threads have completed */
assert(cc->i == 101);
assert(pc->i == 101);

free(cc);
free(pc);
protothread_free(pt);
}

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

А теперь детали. Две наиболее интересные функции в этом примере pt_resume() и pt_wait(). Раскроем эти функции потока производителя чтобы изучить как они работают. (Полное описание API можно посмотреть в конце статьи.) Поле pt_func структуры контекста содержит приватные данные протопотоков(function context); макрос позволяет обращаться к полю по имени.
 static pt_t
producer_thr(void * const env)
{
pc_thread_context_t * const c = env;

/* pt_resume(c) expanded: *****/
if ((c)->pt_func.label) goto *(c)->pt_func.label;
/* pt_resume end *****/

for (c->i = 1; c->i <= 100; c->i++) {
while (*c->mailbox) {
/* mailbox is full */

/* pt_wait(c, c->mailbox) expanded: *****/
do {
(c)->pt_func.label = &&pt_label_18;
pt_enqueue_wait((c)->pt_func.thread, c->mailbox);
return PT_WAIT;
pt_label_18:;
} while (0);
/* pt_wait end *****/
}
*c->mailbox = c->i;
pt_signal(pt_get_pt(c), c->mailbox);
}
return PT_DONE;
}

В начале работы потока, переменная содержит NULL, и функция не выполняет переход на сохраненный адрес(goto) -- код входит в выполнение цикла for в начале функции. Достигнув вызова pt_wait(), сохраняет значение адреса переменной (ее имя имя получяется из номера строки __LINE__; уточнение: двойной амперсанд сообщает, что нужно использовать расширение получения адреса по имени переменной), ставит поток в очередь ожидания внутри описания потока, сохраняет адрес возврата, что равносильно ожиданию сигнала связанного с адресом общей переменой, в данном случае почтового ящика, и возвращает PT_WAIT. (Результат возврата в данном примере не используется; как будет описано ранее он используется только для вложенных функций protothread.)

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

Структура protothread

Структура описания протопотока обязательно содержит одну или больше протопотоковых функций. Только функции протопотоков могут блокироваться или вызывать блокируемые функции. Всем протопотокам требуется pt_thread_t структура для хранения внутренних состояний потоков. Кроме этого, каждый уровень вложенности функций нуждается в pt_func(тип pt_func_t), которая содержит внутреннюю(служебную) информацию для функций. Если A вызывает B которая вызывает C (и C блокируется), каждая из них нуждается в собственном экземпляре структуры pt_func.

Эта структура также содержит определенные пользователем состояния специфичные для функции, обычно это внутренние переменные если используется потоки POSIX. Функции протопотоков обычно не содержат внутренних переменных, так как эти переменные не сохраняются во время ожиданий событий. (Вы можете посмотреть в примере используется c->i вместо просто i для организации циклов.) Существует одно исключение, однако в обычно в C коде есть несколько локальных переменных инициализируемые при описании (на основе аргументов) и неизменные во время исполнения. Вы можете использовать этот принцип и при создании потоков protothreads также (перед вызовом pt_resume()), так как эта инициализация не имеет побочных эффектов. Пример 2 содержит подобную переменную c.

Существует только 2 пути запуска функций в протопотоках; протопоточные функции нельзя запускать непосредственно.

  • Любой код(обычная функция или протопоточная функция) вызывается через pt_create() для создания нового потока. При передаче управления указатель на функцию и контекст исполнения передается одним аргументом. Этот вызовы планирует вызов потока (но не запускает его непосредственно). Не существует метода отмены выполнения потока. Систем пропотоков не сообщает когда он выполниться; он только запланирует выполнение. Вызов pt_create() также требует уникальной структуры (для данного потока) pt_thread_t, которая может быть выделена где угодно, но обычно это делают в вызывающей функции и включают в контекст вызывающей функции (как структура pc_thread_context_t указанная выше).
  • Функция (внутри потока) может вызывать pt_call(). Последовательность обработки подобна обычному вызову функции, кроме того что вы используете pt_call() для вызова функции. Любое количество аргументов любых типов может быть передано при вызове функции ( проверку типов обычно осуществляет компилятор), но первым аргументом обязательно должен быть указатель на контекст исполнения (содержащий поле pt_func) для сохранения состояния функции после ее вызова.

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

Вложенные функции в Protothread

Как работает вложенность? Когда функция A вызывает (используя pt_call()) потоковую функцию B, и B ожидает события (pt_wait()), B сохраняет текущее адрес исполнения и возвращает PT_WAIT в pt_call() в A, что вызывает сохранение его в контекст исполнения A как адрес восстановления где будет вызвана B. A возвращает PT_WAIT функции которая ее вызывала. Когда планировщик продолжит исполнение A , вызовется pt_resume() вызывающая B, так как A вызвала B, и B's pt_resume() перейдет на адрес после блокировки и продолжит исполнение. Так стек разматывается, когда поток блокируется и восстанавливается при снятии блокировки. Так можно описать как реализуется использование единого стека. Также мы должны осветить как обрабатываются параметры которые A передает B без побочных эффектов -- A всегда вызывает B при возобновлении работы.

Когда B полностью завершиться и возвратит PT_DONE, A будет знать что нужно продолжить выполнение кода после вызова pt_call() для B.

Контекст исполнения функции A может включать контекст B's внутри себя, или динамически создавать контекст функции B; выделение контекста возложено на пользователя. Для получения скрытия данных, A может выделять очень минимальную копию структуры pt_func и указатель не скрытую контекст B(для A). И в начале обработки B динамически выделяет память под полную структуру данных и связывает ее с переданной от A структурой.

Другая интересная идея заключается в том что,если A вызовет B, затем B вернет A вызов C (так что B и C не может работать одновременно), контекст для B и C могут быть полями(union) внутри контекста A. Эта разделение памяти между B и C подобна разделению стека внутри POSIX потока.

Четкий порядок исполнения

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

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

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

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

Наиболее известная реализация протопотоков (Adam Dunkels) использует 2 байта на каждый поток. Эта реализация не такая оптимальная ( в основном благодаря тому что реализация включает планировщик: потоки могут быть в списке ожидающих или работающих потоков); наше окружение не столь ограничено в использовании памяти. Каждый описатель потока содержит структуру pt_func_t , содержащую 2 указателя. Полное описание содержит структуру pt_thread_t, содержащую 5 указателей. Но все равно это гораздо меньше чем у стандартного потока POSIX.

Время создания и уничтожения нерабочих потоков на моем компьютере около 12.2 nanoseconds. Время создания и уничтожения при использовании POSIX реализации 7.85 microseconds, то есть различие в 643 раз. Для сравнения времени переключения контекста для модели производитель-потребитель, каждый поток переключался за 22.2 nanoseconds. Смена контекста в стандартной реализации 3.0 microseconds, то есть разница в 135 раз.

Заключение

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

Описание API

Контекст исполнения потока

Далее указаны используемые макросы ( реализованные чтобы выглядеть и работать подобно функциям) первым аргументов выступает определенная пользователем структура описатель контекста выполнения, c (подобная context_t, но описанная пользователем). Для всех служебных функций используется тип pt_f_t.

void pt_resume(struct context_t *c)

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

void pt_wait(struct context_t *c, void *channel)

Заблокировать на время отправки сигнала в указанный канал. Канал интерпретируется как void * и обычно им выступает адрес структуры изменение состояния которой интересует функцию. Сам канал не имеет состояния; система протоптоков никогда не обращается по указанному адресу. Обычно, после возврата значения этой функцией функция будет вызвана еще раз. Аналог для POSIX pthread_cond_wait().

void pt_yield(struct context_t *c)

Перепланировать текущий поток и освободить процессор. Подобно pt_wait() по которому сразу пришел сигнал. В текущей реализации списка потоков он ставиться в конец очереди и возвращает управление планировщику.

void pt_call(struct context_t *c, pt_f_t child_func, struct child_context_t *child_context, arg...)

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

bool_t pt_call_waited(struct context_t *c)

Возвращает TRUE если выполнение функции pt_call() было заблокировано (непосредственно в вызывающей функции или в ее потомке). Если функция A вызывает B и B блокируется, тогда при возврате в A, это поможет понять что должен исполняться другой поток, это позволит заново пересчитать значение глобального состояния. Но если B не заблокирована, тогда A знает, что нужно только изменение локального состояния (независимо от того, что B выполнил).

protothread_t pt_get_pt(struct context_t *c)

Возвращает указатель на описание потока(protothread_t). Используется для вызова функций требующих для исполнение описания потока, таких как: pt_create() или pt_signal().

Контекст исполнения других реализаций потоков

void pt_create(protothread_t, pt_thread_t, pt_f_t func, void *env)

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

void pt_broadcast(protothread_t, void *channel)

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

void pt_signal(protothread_t, void *channel)

Подобно pt_broadcast() но пробуждаеться только наиболее долго ждавший поток. Аналог для POSIX pthread_cond_signal().

protothread_t protothread_create(void)

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

void protothread_free(protothread_t)

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

Планирование

bool_t protothread_run(protothread_t)

Запуск следующего готового процесса (если он конечно есть). Возвращает TRUE, если нет ждущих исполнения потоков.

void protothread_set_ready_function(protothread_t, void (*ready_function)(void *), void *env)

Эту функция предназначена для использования с уже существующим планировщиком (если нет возможности его заменить, или не хотим его заменять). Вам эта функция не нужна, если вы используете собственный планировщик. Эта функция обычно запускается один раз во время инициализации. Результатом вызова этой функции является вызов для всех свободных потоков ready_function (с передачей ей env) когда поток будет готов (и нет рабочих потоков), и нет (в данный момент ) запущенных потоков. Вы можете передать NULL вместо ready_function для отключения этой возможности.
Указанная ready_function обычно планирует (используя методы доступные в вашей системе). Другая функция вызывает protothread_run() пока не закончатся потоки для выполнения (protothread_run() returns FALSE). ready_function не должна вызывать protothread_run() непосредственно.
Для того чтобы последовательность выполнения потоков не заняла слишком много времени, функция может ограничить количество запусков protothread_run(); для примера: она запускает не более 20 потоков до того как вернуть управление планировщику для выполнения других задач (вне протопотоков). Она это делает (если последний вызов protothread_run() вернет TRUE), только если нужно выполнить перепланировку, так как осталась не завершенные задачи.

Источники

Wikipedia protothreads

Описание потоков POSIX

Большая благодарность Adam Dunkels (с поддержкой от Oliver Schmidt) за блестящую идею. Пожалуйста, зайдите на его сайт.

Большое спасибо также за помощь Paul Soulier в разработке концепции потоков, Marshall McMullen и John Rockenfeller за рецензию черновиков этой статьи.

Larry Ruane программист в LeftHand Networks, Inc., an HP Company