Хеш-плата для майнера

Плата после Ковидных коникул и балансировки питания наконец показала стаблиьную работу. Выглядит это так...

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

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

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

Результат скромный: 35ГигаХеш/сек с одной платы. Ожидали 40 ГигаХещ/сек. Надо оптимизировать питание на плате, чтобы добиться стабильной работы на большей частоте.

ПЛК контроллер для гидравлики

Который месяц не можем обеспечить производство контроллерами. Заказал контроллеры STM32G0, потому что они есть на складах. Изначально проект выполнен под контроллер STM32F3, но из этой серии невозможно добыть ни одного контроллера по разумным ценам. Делаем контроллер управления гидравлической системой на 24 релейных выхода. Это позволяет реализовать различные гидравлические установки с насосами и цилиндрами. В настоящее время на них выпускается гидравлическая платформа с четрьмя лапами и телескопической мачтой. В проекте переработка платы под маслостанции различного применения. Маслостанции - это общее название включающее один или несколько насосов, управление приводами заслонок трубопроводов, и гидрораспределительными клапанами, датчики давления и температуры. Для примера - промывочная масловстанция, с переключением режимов и поддержкой температуры промывочной жидкости. Установка применяется для промывки трубопроводов и промышленных устсновок, выпускается (Гидромашцентр, GMC.SU).

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

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

Сборочное производство

Собрали линию на новой площадке. Принимаем заказы на автоматический монтаж.

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

Хеш плата для Майнинга

Делаем хеш-плату для биткоинов.. с жидкостным охлаждением. Киловатт с квадратного децеметра.

Я поставил рекорд по плотности монтажа, все сигналы и сила разведены по одной стороне. Искусство схемотехники!

Плата должна выдерживать токи в 40-60А через кристалл размером 8х8мм. Дорожки усилены медной полосой. Питание радается каскадом: ток через один каскад чипов питает следующий каскад.

Размер платы всего 210x90мм. Успейте купить!

Цифровая подпись ГОСТ -- быстрое редуцирование по модулю простого числа

Настал момент поделиться ноу-хау, как ускорять криптографию ГОСТ. Вернее одна маленькая деталь, но самая важная. Как быстро выполнять редуцирование - модуль простого числа. Как вообще строится цифровая подпись. Есть математика на бублике, в поле целых чисел по модулю простого числа. На этом строится и RSA и ECDSA и ГОСТ. Можно сказать модуль числа - это самая критическая операция - остаток от деления.

Любая операция на бублике: это умножение большого числа (256 или 512 бит) или сложение большого числа сопровождается последующем редуцированием(взятием по модулю).
Простые числа в криптографии часто выбирваются исходя из простоты восприятия человеком и с возможностью оптимизации вычислений, например в ГОСТ представлены простые числа вида P = 2^(n-1)+p0 и P = 2^n - p0 где n=256 или n=512 бит.

Все операции в поле выполняются по модулю. Например, умножение по модулю - это умножение и модуль числа.

// Умножение с редуцированием по модулю простого числа.
void bn_mulm(bn* r, bn* a, bn* b)
{
	int cy = bn_mul(r, a, b);
	bn_mod(r, cy, Prime);
}

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

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

Что в таком случае редуцирование?

Представим результат операции - как перенос (сx- число, которое вылезло за пределы 512 бит) и число X, которое осталось в пределах 512 бит {cx, x}. При этом число x имеет разрядность 512 бита, а перенос - 32 или 64 бита, зависит от архитектуры процессора, ориентируемся на 64 бита.

Наша задача сводится к тому, чтобы вычесть из числа {cx,x} простое число несколько раз, чтобы перенос стал нулевым. При этом остаток помещается в 512 бит, но может требовать дальнейших операций по редуцированию. Нам важно только одно - результат редуцирования помещается в заданные 512 бит. Операцию можно выполнить в два этапа.

Алгоритм 1. Быстрое редуцирование в поле P = 2^N - p0
1. {cy,x} : = {cx, x} - (2^512-p0)*cx;
В результате cy может быть равен нулю или единице.
2. if cy>0 then {cy,x} : = {cy, x} - P;

Чтобы это работало на P надо наложить некоторые ограничения p0 < 2^(n-m), где m - разрядность переноса.

Алгоритм можно упростить:

Алгоритм 1.1. Быстрое редуцирование P = 2^N - p0
1. {cy,x} : = x + p0*cx;
2. if cy>0 then x : = x + p0;

Быстрое редуцирование не является взятием по модулю. Редуцирование возвращает число в заданную разрядность 2^n. Операция взятия модуля выполняется всего один раз на множество операций, только при сравнении чисел.

Теперь рассмотрим второй случай, когда простое число представленно суммой P=2^(N-1) + p0, где N -- разрядность поля, 256 или 512.

Алгоритм 2. Быстрое редуцирование P = 2^(N-1) + p0
1. {cy,x} : = {cx, x} - 2*(2^511+p0)*cx = x - 2*p0;
В результате cy может быть равен нулю или (-1). 
2. if cy<0 then {cy,x} : = {cy, x} + P;

При значении cy == (-1) x находится в интервале [-2*p0; -1], в старшем бите единица (1).

Полагаю равносильно заменить P на втором шаге на 2P. Cуть операции редуцирования не меняется.

Алгоритм 2.1. Быстрое редуцирование P = 2^(N-1) + p0
1. {cy,x} : = {cx, x} - 2*(2^511+p0)*cx = x - 2*p0*cx;
В результате cy может быть равен нулю или (-1).
2. if cy<0 then {cy,x} : = {cy, x} + 2*P = x + 2*p0;

Отдельно рассматриваем редуцирование при сложении и вычитании

Алгоритм 3. Сложение с редуцированием
1. {cy, x} := a+b
В результате cy принимает значения 0 или 1.
2. if (cy>0) {cy,x} := {cy,x} - (2^N - p0) = x + p0
Может понадобится третий шаг, очень мало вероятно:
3. if (cy>0) {cy,x} := {cy,x} - (2^N - p0) = x + p0

Для примера рассмотрим операцию вычисления умножения двух больших чисел разрядностью N. Зачем? Просто так, добавить больше нечего.

// Алгоритм 4. Умножение с накоплением (со сложением)
uint64_t bn_mla_512(uint64_t* r, uint64_t *a, uint64_t d)
{
    unsigned __int128 ac = 0;
    int i;
    for (i=0;i<8; i++) {
        ac +=  (unsigned __int128)d*a[i] + (unsigned __int128)r[i];
        r[i] = (uint64_t)ac;
        ac = ac>>64;
    }
    return (uint64_t)ac;
}

Операция "Умножение с накоплением" используется в реализации Алгоритма 1.1, быстрого редуцирования.

// Алгоритм 5. Умножение с вычитанием
 int64_t bn_mls_512(uint64_t* r, uint64_t *a, uint64_t d)
{
    __int128 ac = 0;
    int i;
    for (i=0; i<8; i++) {
        ac += (unsigned __int128)r[i] - (unsigned __int128)a[i]*d;
        r[i] = (uint64_t)ac;
        ac = ac>>64;
    }
    return (int64_t)ac;
}

Операция "Умножение с вычитанием" используется в реализации Алгоритма 2.1, быстрого редуцирования.

Эффективность описания операции (Alg.5) сомнительна, в рабочем проекте я использую ассемблер. Данное описание мне понадобилось для отладки под GCC 10 на платформе Intel x86_64.

Сжатие методом Хаффмана (Huffman Codes)

На картинке изображен метод кодирования Хаффмана, предложенный еще в 1952 году, 70 лет назад. Глядя на эту схему, приходит в голову сортированный список или стек(приоритеная очередь) с сортировкой по весовому коэффциенту.
Алгоритм построения кодов состоит из двух этапов. На первом этапе мы составляем и сортируем очередь указанным на картинке способом. На каждом шаге создаем композитный элемент очереди, включающий ссылки на два последних элемента и тем самым формируем из списка дерево -- еще одна динамическая структура. На втором этапе совершаем обход дерева, степень вложенности элементов в дерево будет давать длину кода. Данный метод используется для вычисления длин кодов, одновременно с эти можно вычислять сами коды, приняв направление ветвления, право - лево за ноль или единицу. Расчет кодов предлагается выполнять методом обхода дерева, а это -- рекурсия.

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

No |wght|bits|code
 0 | 20 |  2 |00
 1 | 18 |  3 |010
 2 | 10 |  3 |011
 3 | 10 |  3 |100
 4 | 10 |  3 |101
 5 |  6 |  4 |1100
 6 |  6 |  5 |11010
 7 |  4 |  5 |11011
 8 |  4 |  5 |11100
 9 |  4 |  5 |11101
10 |  4 |  5 |11110
11 |  3 |  6 |111110
12 |  1 |  6 |111111

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

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

Как избавиться от приоритетной очереди. От нее не избавиться, но мы могли бы использовать сортировку массива или создавать динамические данные из массива. Сортировка массива дает слишком много циклов и много операций копирования. В общем случае мы используем объект типа список из массива элементов и методы: "вставить с приоритетом"(list_insert_sorted), "получить следующий", и "выделить новый элемент из массива" (list_new). Используем процедуру обхода списка, в одном направлении -- односвязный список.

Это мы сейчас обсуждаем генерацию кодов, которая востребована на этапе упаковки данных, сжатия.

Декомпрессия выполнятся иначе. Для декомпрессии на вход подается таблица битовых длинн кодов, только третья колонка в нашем примере, вторая и четвертая колонки таблицы: частота использования и коды -- не заполнены.

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

Метод декодирования с использованием дерева ветвления - тоже сравнительно медленный. Чтобы понять насколько медленно скажем так: символы основного алфавита кодируются длинами от 1 до 15 бит. Если разброс длин таблицы кодирования большой, то может понадобиться 15 циклов, чтобы найти нужный код. Однако, тут надо иметь ввиду, что длинные коды встречаются реже, чем короткие. Так что, берем оценку по среднему - восемь циклов на декодирование каждого символа.

Метод декодирования с использованием кодовых таблиц в теории будет работать быстрее, потому что разбор ведется сразу по несколько бит, в среднем по 8 бит для литералов и длин, и по пять бит для смещения. Т.е. ожидаем производительность табличных методов в несколько раз выше. Однако, для декодирования кодов с максимальной длиной 15 бит нужны таблицы декодирования размером в 32-128 кБайт, а их генерировать возможно дольше, чем разбирать поток по одному биту. По этой причине мы рассматриваем методы, которые используют частичное декодирование с помощью таблиц, а затем вычисляют остаток.

Ставим задачу: получить производительность декодирования - один цикл на символ, в среднем. Как это сделать. Для начала надо научиться по префиксу кода, находить индекс в таблице. Готовим коды с выравниванием по левому краю, как указано в таблице, чтобы можно было выполнять сравнение чисел.

 0 | 20 |  2 |00XXX
 1 | 18 |  3 |010XX
 2 | 10 |  3 |011XX
 3 | 10 |  3 |100XX
 4 | 10 |  3 |101XX
 5 |  6 |  4 |1100X
 6 |  6 |  5 |11010
 . . .

В таком виде можно вычислять индекс по кодам. Привожу алгоритм описанный в обзорной статье [ACM Comput. Surv., Vol. 1, No. 1, Article 1. Publication date: June 2019].

    1) Найти такое ℓ чтобы first_code_l[ℓ] ≤ code < first_code_l[ℓ + 1];
-- Коды упорядочены по убыванию частоты использования, найти какому диапазону принадлежит код.
    2) пусть offset ← (code − first_code_l[ℓ]) >> (L − ℓ);
-- находим смещение в таблице - номер символа. 
    3) Находим сам символ s ← first_symbol[ℓ] + offset;

Для поиска в таком режиме применяем следующий цикл, именно он будет определять производительность метода:

// Алгоритм поиска кода по таблице.
    set ℓ ← search_start[code >> (L − t)];
    while code ≥ first_code_l[ℓ + 1] do
        set ℓ ← ℓ + 1.

Я бы сказал так, выражаясь шаблонами: мы используем хеш таблицу для поиска кода.

Сначала из таблицы некоторой фиксированной длины мы выбираем величину минимальной длины кода (t). Затем подбираем код по таблице. Казалось бы выигрыша особенного нет, потому что получаем цикл от минимальной до максимальной длины кода.

Для отладки и исследования алгоритма я ввел еще одну таблицу - search_end - максимальная длина кода с заданным префиксом, которая ограничивает глубину поиска кода.

// Предложенный алгоритм поиска
    set ℓ ← search_start[code >> (L − t)];
    set u ← search_end  [code >> (L − t)];
    while (ℓ < u) && code ≥ first_code[ℓ + 1] do
        set ℓ ← ℓ + 1.

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

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

И тут пришла в голову мысль, а не посмотреть ли как другие решают эту задачу. Посмотрел. Опять нашел код с исходниками Марка Адлера и отказом от права контролировать копии, с 1996 года в составе GNU, gzip -- этот код есть на каждом сервере. Код тридцатилетней давности, 30 лет, в коде упомянаются проблемы компиляции под MSDOS и OS/2, с ипсользованием Turbo C. В файле ТОДО рекомендуется использовать оптимизации CRC от Росса Вильямса, который уже пятнадцать лет, как на пенсии.

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

// Алгоритм декодирования
    do{
        t ← t.data + (взять_из_потока(t.n_bits) & маска_выборки(t.extra)) 
    } while нужно_продолжить(t.extra);
    сдвинуть_поток(t.n_bits);
    выполнить_обработку_данных(t.data, t.extra).

Примерно такой шаблон кода должен решать задачу декодирования. Более того, если этот фрагмент выполняется в цикле, таблицами (t) и переходами внутри таблицы (t.data) можно организовать контектстно-зависимый разбор. Маска выборки может быть линейная или не линейная. Допустим нам нужно декодировать программу из системы команд одного процессора в систему команд другого процессора. Или скажем, нужно написать итератор по системе команд Intel x86, т.е. по префиксам выделять длину инструкции -- тот же алгоритм декодирования, тот же шаблон. Или понадобилось разбирать синтаксис и грамматику в интерпретаторе команд, - тоже самое.

Конкретно, нам нужно выбрать инструкцию, на которой будет все работать. Для пионеров можем предложить реализацию на инструкции Intel AVX512_BITALG:

Synopsis
   __mmask16 _mm_bitshuffle_epi64_mask (__m128i b, __m128i c)

Instruction: vpshufbitqmb k, xmm, xmm
CPUID Flags: AVX512_BITALG + AVX512VL

Т.е на одной такой инструкции можно декодировать входной поток с использованием перестановки бит. Комбинация бит во входном потоке приводит к переходу по таблице декодирования. Результат - маска.

Мы выбираем простой способ формирования масок ((1<<(n))-1), который можно реализовать в одну инструкцию Intel BMI или BMI2;

В зависимости от целевой платформы, мы можем с таким алгоритмом достичь производительности в один такт(цикл) на кодовое слово. И тут происходит основное расстройство - мы живем в золотом веке программирования - этот подход уже реализован в gzip. С той лишь разницей, что реализован он средствами 30 летней давности, в инструкциях ANSI С. Более современная интерпретация алгоритма пристуствует в проекте zlib-ng.

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

Я потратил выходные на то чтобы научиться составлять таблицы декодирования и подобрать функцию декодера. И вот что получилось.

// Алгоритм декодирования
#define BIT_MASK(n) ((1<<(n))-1)

    t = t + (stream & BIT_MASK(N));
    if (t->extra) {
        t = te + t->n + ((stream>>N) & BIT_MASK(t->extra));
    }
    stream >>= t->bits;
    return t->n;

Функция использует две таблицы: (t) - основаная с разрядностью индекса N и дополнительная (te) - для декодирования кодов с длиной больше N. Декодирование выполняется не более чем в два этапа. На выходе алгоритм выдает декодированное значение. Параметр N выбирается разный для таблиц декодирования литералов (N=8) и для декодирования дистанций (N=5). При данных значениях параметра вторая таблица используется редко. Операции извлечения бит из потока могут выполняться с использованием инструкций Intel BEXTR (BMI1). Полагаю данная реализация является оптимальной с точки зрения производительности.Если при этом удасться сохранить лаконичность кода, то и самая быстрая в своем роде (быстрее gzip, zlib и zlib-ng).

Суммараная производительность алгоритма будет складываться из времени подготовки таблиц, времени работы алгоритма декодирования (inflate), и времени подгрузки данных.

Марку Адлеру - оптимизация алгоритма контрольной суммы PNG

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

uint32_t ADLER32_update_(uint32_t adler, uint8_t *p, size_t len){
	const uint32_t BASE = 65521;
	uint32_t s1 = (adler      ) & 0xFFFF;
	uint32_t s2 = (adler >> 16);
	if (len) do{
		s1 += *p++;
		if (s1 >= BASE) s1 -= BASE;
		s2 += s1;
		if (s2 >= BASE) s2 -= BASE;
	} while (--len);
	return (s2<<16) + s1;
}

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

Оптимизация - это последовательные тождественные преобразования алгоритма.

    const int Nmax = 5552;
    do {
        int n = len>Nmax? Nmax: len;
        len-=n;
        do {
            s1 += *p++;
            s2 += s1;
        }while (--n);
        // не полное редуцирование
        s1-= (s1>>16)*0xFFF1u;
        s2-= (s2>>16)*0xFFF1u;
    } while (len);
    s1 = mod65521(s1);// s1%=BASE;
    s2 = mod65521(s2);// s2%=BASE;

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

s2 = s2 + s1*n + p0*(n) + p1*(n-1) ... 
MAX(s2) = (n+1)*(0xFFF0 + 0xFF*n/2)

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

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

#define mod65521(x) ((x) - 0xFFF1*(unsigned long)(((x)*0x80078071ULL)>>47))

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

// Оптимизация вложенного цикла
    s2+=s1*n;
    do {
       s1 += p[0];
       s2 += p[0]*n;
       p++;
    } while (--n);

В таком варианте компилятор (GCC 10+ и clang) векторизует цикл и выполняет вычисления на векторе 16 байт. Вопреки ожиданиям, оптимизированный компилятором код довольно громоздкий и не дает ожидаемого ускорения в 16 раз, поскольку выполняется перепаковка входных дынных в вектор uint32х4. По этой причине дальнейшая оптимизация выполняется вручную за счет использования векторных инструкций горизонтального сложения для суммирования элементов (s1). Горизонтальное сложение и умножение на векторе можно выполнить с использованием инструкции _mm256_maddubs_epi16, а горизонтальное суммирование по вектору можно выполнить на инструкции _mm_sad_epu8

Ниже показываю, как разворачивается и сворачивается цикл. Начнем с шага 2.

// Развертывание вложенного цикла
    do {
       s3 += s1;
       s1 += p[0] + p[1];
       s2 += p[0]*2 + p[1]*1;
       p+=2;
    } while ((n-=2)>0);
    s2+=s3*2;

Тоже самое можно представить для произвольного шага L. Мы расчитываем преобразовать вложенный цикл, чтобы использовать свертку и векторизацию для L=16,32,64...

// Свертка по L-элементов
    do {
       s3 += s1;
       for (i=0;i<L; i++) {
          s1 += p[i];
          s2 += p[i]*(L-i);
       }
       p+=L;
    } while ((n-=L)>0);
    s2+=s3*L;

Тоже на векторных инструкциях Intel AVX2.

     do{
          vs3 = _mm256_add_epi32(vs3, vs1);
          __m256i v = _mm256_lddqu_si256((void*)p); p+=32;
          __m256i v1 = _mm256_maddubs_epi16(v, E);
          __m256i v2 = _mm256_maddubs_epi16(v, M);
          v1 = _mm256_madd_epi16 (v1, _mm256_set1_epi16(1));
          v2 = _mm256_madd_epi16 (v2, _mm256_set1_epi16(1));
          vs1 = _mm256_add_epi32(vs1,v1);
          vs2 = _mm256_add_epi32(vs2,v2);
     } while(--n);

Тоже на инструкциях Intel AVX512_VNNI (инструкции для сверточных нейро сетей подходят для наших целей).

    do {
       __m256i v = _mm256_lddqu_si256((void*)p); p+=32;
       vs3 = _mm256_add_epi32(vs3, vs1);
       vs1 = _mm256_dpbusd_epi32(vs1, v, E);
       vs2 = _mm256_dpbusd_epi32(vs2, v, M);
    } while((n-=32)>0);

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

Быстрое редуцирование на векторе удалость описать таким образом:

vs2 = _mm256_sub_epi32 (vs2, _mm256_mullo_epi32(_mm256_srli_epi32(vs2, 16), P));

Мы показали порядок вывода паралельного алгоритма из последовательного. Теперь перейдем к анализу быстродействия. Анализ выполняется с использованием анализатора машинного кода LLVM-MCA.

# gcc -O3 -march=skylake -S -o test.s adler.c
# llvm-mca.exe -mcpu=skylake -timeline test.s
Фрагмент отчета (временная диаграмма), начиная со второго цикла:
[2,0]     .    .DeeeeeeeE----------R    .   vlddqu      (%rax), %ymm0
[2,1]     .    .D================eER    .   vpaddd      %ymm5, %ymm2, %ymm3
[2,2]     .    .D=eeeeeeeeeeeeE----R    .   vpmaddubsw  .LC10(%rip), %ymm0, %ymm1
[2,3]     .    .D=eeeeeeeeeeeeE----R    .   vpmaddubsw  .LC11(%rip), %ymm0, %ymm0
[2,4]     .    . D=====eeeeeeeeeeeeER   .   vpmaddwd    .LC12(%rip), %ymm1, %ymm1
[2,5]     .    . D=====eeeeeeeeeeeeER   .   vpmaddwd    .LC12(%rip), %ymm0, %ymm0
[2,6]     .    . D=================eER  .   vpaddd      %ymm2, %ymm1, %ymm1
[2,7]     .    . D=================eER  .   vpaddd      %ymm4, %ymm0, %ymm0
[2,8]     .    .  DeE----------------R  .   addq        $32, %rax
[2,9]     .    .  D===============eE-R  .   vmovdqa     %ymm3, %ymm5
[2,10]    .    .  D=================eER .   vmovdqa     %ymm1, %ymm2
[2,11]    .    .  D=================eER .   vmovdqa     %ymm0, %ymm4
[2,12]    .    .  D=eE----------------R .   cmpq        %rcx, %rax
[2,13]    .    .  D==eE---------------R .   jne .L21

Из отчета видно, что скорость реализиации алгоритма на инструкциях AVX2 равняется 3 такта на цикл, на 32 байта. Раз в 10 ускорились! И это далеко не предел.

Полностью код доступен на Github

Неблокирующее многопотоковое программирование без простоя

Со знанием дела можно описать операционную систему...

Возможно ли сделать операционную систему Lock-free, без блокировок и без задержек, Wait-free.

Тут вспоминаются дебаты про свободу выбора, свободу от обязательств и бесплатное пиво.
Благодаря статье в Википедии и представленным терминам, можно выделить несколько свобод. Повторюсь: Свобода выбора существует.

Obstruction-free

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

Lock-free

(Без блокировок). Выполнение алгоритма не вызывает переключение задач или использования блокировок в виде Мьютексов. Это некоторый признак, но не само определение.

Wait-free

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

Определения и классификацию по этим признакам я хочу вовсе вывести из рассмотрения. Я вижу группу людей из Oracle и Sun придумали способ писать много лажи в базу данных, а потом удалять те записи, которые произошли по недоразумению [Moir]. Автор метода, позиционировал свой термин OF как алтернативная и более эффективная техника чем Lock-free в условиях распределенных вычислений и баз данных. Методика, которая предъявляет менее жесткое требования.. никакого определения не вводил. Кажется его не поняли коллеги и задвинули в классификации на задний план. Фраза про более слабый.. чего?.. менее жесткие требования на синхронизацию процессов, вычисления могуть проводится в изоляции.

Люди, которые приложились к развитию неблокирующих методов, включая OF и TM(Transactional Memory): Maurice P. Herlihy (DEC), Mark S. Moir, Victor M. Luchangco, Nir N. Shavit - по этим именам можно проследить публикации и патенты на тему Transactional Memory, Obstruction-free и Lock-free методов работы со списками, хешами и деревьями. При всем при том, я лично использую их корпоративный опыт, как верификацию того, что лезет мне в голову. Для меня лично изучение этой литературы происходит одновременно с написанием статьи, а создание и использование алгоритмов - из головы, по мере необходимости. Давайте прибавим к словам STM(Software Transactional Memory) букву D- Distributed (DSTM). STM и транзакции - это конечно распределенные вычисления и базы данных [].

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

Я несколько раз перечитал определения в Wikipedia этих терминов и не нашел нормальной (однозначной) интерпретации терминов в русской и английской версии. Поэтому обратился к статье, на которую ссылается Wikipedia [CPWL] [https://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf]. Привжу цитату и перевод, чтобы терминология была определена четко.

Non-blocking progress guarantee. In order to provide robustness against many liveness problems, such as deadlock, implementations of our APIs should be nonblocking. This means that even if any set of threads is stalled the remaining threads can still make progress.

Гарантия неблокирующего исполнения кода. Чтобы обеспечить устойчивость ко многим проблемам жизнеспособности программ, таким как зависание, реализации наших API должны быть неблокирующими. Это означает, что даже если какой-либо набор потоков остановлен, остальные потоки все равно могут исполняться. -- этот тезис должен быть в основе реализации ОС.

"Non-blocking algorithms can be classified according to the kind of progress guarantee that they make:
Не блокирующие алгоритмы можно классифицировать по виду ганрантии исполнения кода.

Obstruction-freedom

is the weakest guarantee: a thread performing an operation is only guaranteed to make progress so long as it does not contend with other threads for access to any location [Herlihy et al. 2003, Obstruction-Free Synchronization: Double Ended Queues as an Example].
поток, выполняющий операцию, гарантированно будет исполняться только до тех пор, пока он не будет бороться с другими потоками за доступ к какому-либо местоположению.

Lock-freedom

adds the requirement that the system as a whole makes progress, even if there is contention.
добавляет требование, чтобы система в целом продвигалась вперед, даже если испытывает конфликт доступа

Wait-freedom

adds the requirement that every thread makes progress, even if it experiences contention.
добавляет требование, чтобы каждый поток выполнялся, даже если он испытывает конфликт доступа.

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

Цитирую опеределения из патента[US 8176264 B2, Moir et al. 2012] в котором вводится термин Obstruction-free применительно к Отложенным транзакциям, к Software Transactional Memory в реализации для динамических струкур данных, DSTM.

Lock-freedom

An implementation of an operation is lock free if after a finite number of steps of any execution of that operation, Some operation execution completes (irrespective of the timing behavior of any concurrent operation executions).

Wait-freedom

An implementation of an operation is wait free if after a finite number of steps of any execution of that operation, that operation execution completes (irrespective of the timing behavior of any concurrent operation executions).

Obstruction-freedom

An implementation of an operation is obstruction-free if every operation execution that executes in isolation after Some point completes after a finite number of steps.

Я буду использовать термин Lock-free (Без блокировок) чтобы охарактеризовать ряд алгоритмов используемых в системе и в коде приложения. Без блокировок будет означать, что каждый поток НЕ передает управление системе и НЕ ожидает освобождение ресурса (Wait-free), разрешения конфлика доступа к разделяемому ресурсу (памяти, в частности). Т.е. меня интересует создание неблокирующей операционной системы, в которой никогда не возникает блокировок (Lock-free). В системе должна быть 100% гарантия исполнения кода, без простоя (Wait-free). Прогресс системы в целом должен быть 100%, удваиваем число ядер - удваивается производительность. Задержки на обработку событий не должны зависеть от числа задач или от загрузки операционной системы.

Термин atomic lock-free используется в стандарте языка Си для обозначения "не делимых" операций, которые выполняются без остановки обработки и не требуют поддержки со стороны операционной системы, отключения прерываний или отключения процесса планирования задач.

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

Операционная система (ОС) -- это управление разделяемыми (shared) ресурсами. Ценный ресурс - процессорное время. Есть рессурс - память. Может быть ряд других ресурсов: порт ввода-вывода, файловая система, графический акселератор и пр.
ОС переключает задачи, а задачи обращаются к общим ресурсам. Обращение двух потоков к общему ресурсу может вызывать конфликт доступа. Если разрешение конфликта не вызывает блокировкок Lock-free - это уже удивительно, если не вызывает простоя Wait-free это достижение в области архитектуры программ.

Основной параметр ОС влияющий на эффективность операций - это Preemption, возможность прерывания работы потока и передачи управления другим потокам. В операционной системе должна быть операция добровольной передачи управления от одного потока к другому (Yield). Если поток добровольно передает упрвление и время работы потока не регламентируется, то систему называют Кооперативной (Cooperative multitasking -- кооперативная многозадачность, также используется термин non-preemptive multitasking). Я знаю одну весомую причину передать управление принудительной - поток слишком долго выполняется. Фактически, любое обращение к системе вызывает или может вызывать переключение контекстов задач. Обращение к системе за разделяемым рессурсом может вызывать простой потока и может вызвать переключение контекстов задач. Любое прерывание от аппаратуры может вызвать переключение задач. Обращение к разделяемому ресурсу может выполняться в условиях Preemption ON/OFF, с отключением функции планирования по времени. Отключение процедуры переключения задач (Preemption) гарантирует прогресс системы (исполнение кода без задержек) при раздельном доступе на чтение, однако не гарантирует запись (изменение структуры данных).

Далее мы представим ряд проблем, которые надо решить для построения операционной системы Wait-free, все они сводятся к разрешению конфликтов доступа на четение и запись с использованием атомарных операций чтение-модификация-запись. Разберем примеры реализации объектов, таких как списки и очереди.

Динамическая память

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

Выделение динамической памяти - операция основанная на списках или на таблицах. Для реализации не блокирующего алгоритма выделения памяти требуется неблокирующая работа с массивами флагов или со списками. Ниже мы рассмотрим не блокирующие (Lock-free & Wait-free) алгоритмы работы со списками и неблокирующие операции с флагами событий.

Неблокрирующий ввод-вывод

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

Проблема читатель - писатель

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

Мы будем стремиться создавать не блокирующие алгоритмы без простоя и ожидания (Wait-free), в которых реализуется возможность одновременно записи и чтения. Это можно сделать на основе отложенных транзакций памяти (STM -- Software Transactional Мemory). Операции с объектами, такими как: база данных, хеш таблица, дерево, список, могут быть основаны на атомарной подмене блоков памяти (multi-word STM), атомарной операции записи/чтения массивов (memory-based STM), атомарной подмене структур данных (object-based STM). Такая подмена может обеспечиваться механизмом выделения памяти и аппаратной поддержкой виртуальной памяти. Среди прочего мы выделяем ряд алгоритмов, которые без блокировок (lock-free, wait-free) допускают дозапись, и помечают на удаление, но не удаляют структуры данных пока не закончился поток читателей способных добраться до этой структуры. При этом обеспечиывается целостность во всех версиях структуры. Такая концепция требует поддержки встроенной в механизм выделения памяти. Тут можно сослаться на алгоритмы RCU, но не будем, постараемся вывести свой класс алгоритмов. Строго говоря, алгоритмы RCU в Linux не являются Wait-free для писателя, а для сохранения целостности структуры читателям предлагается останавливать процесс планировщика задач, отключать Preemption. Для обозначения состояний дерева (структуры данных) введем термин структурная целострость данных при совместном использовании (mutual consistency -- отсуствие конфиликтов доступа при совместном использовании). (mutually-consistent snapshot - образ структуры данных типа дерево не испытывает конфликтов доступа при совместном использовании. Это определение подразумевает управлениями образами(версиями), каждый поток чтения находится в одной из версий структуры, для которой гарантируется структурная целостность данных).

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

Планировщик задач

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

Семафор -- это счетчик ресурсов, некоторый достаточно простой объект, определенный через операцию: Ресурс освобождается - счетчик увеличивается; Ресурс блокируется - счетчик уменьшается. Если счетчик равер нулю, рессурс не доступен. Счетчик должен обладать атомарностью операции чтение-модификация запись (atomic Read-Modify-Write, RMW), для этого он должен быть построен на операциях atomic lock-free. Мы выделяем функцию операционной системы, которая реализуется в планировщике -- ожидание ресурса, назовем ее WaitEvent. Все что должна уметь операционная система, минимальная ее функция -- это обеспечивать переключение задач при условии, что запрошенный ресурс стал доступен для приложения. Ожидание может быть ограничено по времени. Процесс может запросить ожидание освобождения ресурса, ожидание семафора. Кроме того, можно ожидать флаг события. НИКАКИХ дополнительных функций в планировщике не нужно. Все остальные механизмы синхронизации можно свести к этим двум. Можно обойтись без флагов событий, если стоит задача - минимизировать планировщик. В unix-подобной системе флаги не требуются, однако требуется поддержка сигналов, которая может быть представлена через флаги событий или через очередь событий фиксированной глубины. Работа с очередью событий может быть выражена через ожидание семафора. В CMSIS RTOS совместимой системе флаги требуются.

Планировщик RTOS может быть такой:

_scheduler ()
{
	. . .
    if (process->status==osWaitSignal) 
    {// процесс ожидает событие (флаги событий)
        if ((process->signals & process->event.flags)!=0) 
        {// переключение по событию
            running_thread = process;
        }
    }
    if (process->status==osWaitSemaphore) 
    {// процесс ожидает ресурс
        if (semaphore_enter(process->event.ptr)) 
        {// ресурс доступен, выполнить переключение задач
            running_thread = process;
        }
    }
    . . .
}

Функция semaphore_enter уменьшает счетчик ресурса на единицу, если он не ноль. Если ресурс доступен, возвращает true.

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

    WaitEvent() -- ожидание ресурса, сигнала, или просто ожидание.
    Yield() -- передать управление другой задаче (кооперативная мультизадачность).
    Kill() -- снять задачу принудительно.

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

Язык Си в редакции С11 [C11-n1570], С2x [C2x-n2596] предлагает стандартизованные примитивы синхронизации: mutex, condition variable. Стандарт языка Си претендует на опистание не только языка, но и минимального набора фукнций операционной системы, в частности описывает программный интерфейс примитивов синхронизации потоков и API многопотокового программирования <threads.h>.

На базе атомарных операций atomic_flag_test_and_set и atomic_flag_clear можно построить реализацию mutex. На базе mutex можно реализовать condition variable.

Mutex -- mutual exclusion

Mutex - бинарный семафор. Счетчик ресурса: есть, нет. Не блокирующая реализация mutex возможна без обращения за поддержкой к операционной системе.

/* пример реализации Wait-free мьютекс */
int mtx_trylock(mtx_t * mtx)
{
    register int count;
    volatile int* ptr = &mtx->count;
    do {
    	count = atomic_get(ptr);
    } while (!atomic_compare_exchange(ptr, count, 0));
    return count;
}

В этом примере я определил примитив синхронизации через два другие примитива. atomic_get - получает доступ к атомарной переменной, а функция atomic_compare_exchange(ptr, v, n) выполняет атомарно операцию сравнения с условной заменой. Если в памяти по адресу ptr раположено прежнее значение (v), полученное при обращении к atomic_get(ptr), то производится запись нового значения (n), иначе следует повторить попытку. Вместе эта структура (шаблон) позволяет реализовать атомарную операцию чтение-модификация-запись (atomic RMW).

Этот же шаблон можно предствить в виде,

/* Шаблон для преобразования операции 'v=op(v)' чтение-модификация-запись
к атомарному исполнению */
int atomic_RMW_$op(void * ptr)
{
    word v, n;
    do {
    	v = atomic_get(ptr);
        n = op(v);// некоторая операция
        atomic_mb();
    } while (!atomic_compare_exchange(ptr, v, n));
    return count;
}

Мы используем API (программный интерфейс для описания атомарных операций) и такой вот шаблон для преобразования операции RMW в атомарную.

/* Альтернативная запись Шаблона atomic RMW, которую можно встретить в литературе */
int atomic_RMW_$op(void * ptr)
{
    word v, n;
    do {
    	v = ACCESS_ONCE(p);
        n = op(v);// некоторая операция
        WRITE_MEMORY_BARRIER();
    } while (!CAS(ptr, v, n));
    return count;
}

Такая структура (шаблон) типична для большинства процессорных архитектур с поддержкой инструкции Сompare & Swap, CAS. Но иснтрукция CAS (Сompare & Swap) или SWAP поддерживается далеко не во всех архитектурах. Мы используем макроопределения atomic_get и atomic_compare_exchange таким образом, чтобы была возможность подстановки инструкций процессора выбранной архитектуры. Кроме того, мы используем макрос atomic_mb() для обозначения барьера памяти, когда все операции связанные с изменением (сохранением) данных должны быть выполнены до следующей инструкции. Надо понимать, что на конвейере процессора могут обрабатываться одновременно несколько инструкций и обработка инструкций занимает несколько тактов процессора. Допускаем возможность аппаратной перестановки порядка следования инструкций. Чтобы обеспечить запись данных из регистров в память, для выполнения синхронизации необходима аппаратная функция барьера памяти.

Заметим, что в языке Cи (C11) есть функция atomic_thread_fence() для реализации барьеров памяти, что позволяет изначально создавать переносимый код, опираясь на стандарт. Шаблон атомарных операций в языке Си отличается, от того что мы применяем:

// шаблон атомарных операций
exp = atomic_load(&cur);
do {
    des = op(exp);
} while (!atomic_compare_exchange_weak(&cur, &exp, des));

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

На платформе ARM есть инструкции синхронизации с аппаратной поддержкой эксклюзивного доступа на уровне ядра процессора (Локальный Монитор), и на уровне разделяемой (Shareble) памяти (Глобальный монитор), в многоядерном варианте архитектуры. Аппаратная функция -- монитор эксклюзивного доступа к памяти (Exclusive Monitor). Эксклюзивный не блокирующий доступ к памяти в архитектуре ARM реализован с использованием пары инструкций: LDREX - операция эксклюзивного чтения (загрузка с пометкой) и STREX - операция сохранения с учетом пометки. На платформе MIPS реализована поддержка в виде двух инструкций LL/SC: LL -- загрузка с пометкой в мониторе (Load-Locked) и SC -- сохранение условное (Store-Conditional), с учетом пометки. Аналогичный метод LDx_L/STx_C (Load memory to register Locked/Store-Conditional) использовался ранее в архитектуре DEC Alpha [Alpha Arhitecture Handbook]. Мы в последнее время сталкиваемся в основном с платформой Intel и ARM. Про MIPS и Alpha упомянаю исключительно потому, что они и есть прaродители аппаратного решения, которое ныне используется в архитектуре ARM для реализации не-блокирующих атомарных операций RMW (atomic lock-free -- термин из стандарта языка Си).

Рассмотрим простой пример реализации Мьютекса с использованием атомарных операций.

/* Не блокирующий Wait-free мьютекс */
int mtx_trylock(mtx_t * mtx)
{
    register int count;
    volatile int* ptr = &mtx->count;
    do {
    	count = __LDREXW(ptr);
    } while (!__STREXW(0,ptr));
    return count;
}

Документация ARM [ARM_Sync] рекомендует выполнить операцию __DMB (Data Memory Barrier "SY") перед очередным чтением переменной из памяти. Зачем? Затем, что порядок обработки команд может меняться на усмотрение компилятора и процессора. У меня лично есть сомнение, что процессор переставляет порядок выполнения инструкций, но может начать исполнение самой инструкции STREX до завершения предыдущей, и начать грузить последующую инструкцию до завершения обработки STREX. На практике я встречал ситуации, когда инструкция __DMB необходима, при взаимодействии с аппаратурой, чтобы сразу при выходе из прерывания не возникло второе прерывание, потому что флаг в аппаратуре еще не опущен, а инструкция обрабатывается. Я бы сказал хороший стиль, перед выходом из прерывания ставить Full-System Data Memory Barrier. Возможно в большинстве случаев можно избежать применения __DMB заменив его на Compiler Memory Barrier, запретив компилятору переставлять инструкции.

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

Псевдокод инструкции LDREX/STREX и развернутое описание работы автомата LocalMonitor и GlobalMonitor [[ARMARM] Arm, Arm Architecture Reference Manual (7-A / 7-R), Arm DDI 0406C]

LDREX - загрузка с пометкой в мониторе
Rn = Mem[address]
LL[SEGMENT(address)] = 1// пометка в локальном мониторе - флаг

STREX - сохранение регистра в память
exclusive = LL[SEGMENT(address)]
if (exclusive) {
	Mem[address] = Rn;
    LL[SEGMENT(address)] = 0;// пометка снимается
}
return exclusive;

При этом способ сегментации памяти для хранения пометок - дело аппаратуры, в разных ядрах может быть реализован с разной сегментацией. Из документации известно, что во всех архитектурах ARM Cortex-M Эксклюзивный монитор использует только один флаг, т.е. физический адрес никак не уточняется. Любая операция STREX сбрасывает флаг эксклюзивного доступа. [ARM_TRM_M4 -- Arm® Cortex®-M4 Processor Revision: r0p1 Technical Reference Manual][ARM_TRM_M55 -- Arm® Cortex®-M55 Processor Revision: r0p2 Technical Reference Manual][ARM_TRM_M33]. Кроме того, утверждается, что повторное использование STREX без LDREX может вызвать ложное срабатывание. Несколько операций LDREX не нарушает логику. Справедливости ради замечу, что на платформе Alpha и MIPS физический адрес при сохранении не уточняется, логика таже.

Пометка глобального монитора относится к сегменту разделяемой (shared) памяти, с раздельным доступом, т.е. функция Глобального монитора может не работать, если память не обладает свойством Shareable. Минимальные требовния к реализации данного механизма Эксклюзивного доступа, LL - это флаг состояния ядра (кеш-памяти) процессора. Не всякая память поддерживает эти инструкции. Т.е. может понадобиться специальное слово, чтобы характеризовать сегмент памяти, где могут размещаться атомарные переменные, а где не могут. Повторюсь, глобальный монитор поддерживает раздельных доступ к памяти в многоядерной системе с общим кешем.

Представим ситуацию, что один процесс выполнил операцию LDREX, произошло переключение задач. Второй процесс тоже выполнил операцию LDREX-, произошло переключение обратно... STREX снимает пометку памяти. Все нормально, если возврат происходит к первому процессу. Второй процесс еще раз запрашивает LDREX и еще раз пытается обновить переменную. Пример описывает interleaved (перекрывающиеся) циклы RMW. Если используются вложенные прерывания (Nested interrupt) и в прерывании происходит обращение к атомарным инструкциям, выход из прерывания должен быть с опущенным флагом эксклюзивного доступа. Логика блокировки эксклюзивного доступа по прежнему работает.

Теперь предположим, что один процесс не сбросил флаг эксклюзивного доступа к памяти LDREX-STREX, выполнил LDREX для следующей операции, но не выполнил STREX. При переключении задачи может возникнуть конфликтная ситупация, когда флаг поднят в одном процессе, а опущен в другом процессе. Документация ARM требует (MUST) выполнять CLREX (clear exclusive) -- очистку монитора при переключении контекстов задач. Возможность возникновения конфликта с использованием флага эксклюзивного доступа показана на диаграмме.

В первом случае (a) будет выполнена повтороная попытка цикла чтение-модификация-запись, во втором случае возникает ложное срабатывание операции STREX. Такая ситуация возникает только при переключении контекстов задач в ОС с premptive multitasking и Не возникает при обработке вложенных прерываний. В системе с кооперативной многозадачностью подобного конфликта не возникает. Чтобы избежать такой ситуации предлагается при каждом переключении задач выполнять очистку флага эксклюзивного доступа, atomic_clear().

Семафоры

Семафор - счетчик ресурса. Приводим неблокирующую реализацию без ожидания, Wait-free.

/* использовать ресурс */
int semaphore_enter(volatile int * ptr)
{
    register int count;
    do {
    	count = __LDREXW(ptr);
        if (count>0) count--;
    } while (!__STREXW(count,ptr));
    return count;
}
/* освободить ресурс */
int semaphore_leave(volatile int * ptr)
{
    register int count;
    do {
    	count = __LDREXW(ptr);
    } while (!__STREXW(count+1,ptr));
    return count;
}

Семафор может быть базовой операцией. Мьютекс можно определить как семафор с начальным значением 1(единица) - бинарный симафор, счетчик от 1 до 0(нуля).

Атомарные не-блокирующие операции, atomic lock-free

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

// шаблон атомарной операции
int afomic_fetch_$op(volatile int * ptr)
{
    register int v,n;
    do {
    	v = __LDREXW(ptr);
        n = op(v);
    } while (!__STREXW(n,ptr));
    return v;
}

Какую бы еще операцию выполнить атомарно?!. См. по ссылке, что данная архитектура считает на регистре. [ACLE][Arm C Language Extensions Documentation, ACLE Q3 2020]. Если операция на регистре не считается, а использует память, то следует перед __STREXW вставить барьер памяти atomic_mb(), все операции записи в память должны быть выполнены до синхронизации.

Есть другой API для гарантии выполнения операций чтения/записи в память.

// шаблон гарнтированной загрузки/сохранения - гарантированного однократного обращения к памяти.
#define ACCESS_ONCE(ptr) ((volatile typeof(ptr))(ptr))

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

// другой шаблон атомарной операции
int afomic_fetch_$op(int * ptr)
{
    int v,n;
    do {
    	v = ACCESS_ONCE(ptr);
        n = op(v);
        WRITE_MEMORY_BARRIER;
    } while (!CAS(ptr, v, n));
    return v;
}

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

// Псевдокод инструкции CAS
atomically bool CAS (word *a, word e, word n) {
    word x := *a;
    if ( x = e ){
    	*a := n;
        return true;
    }
    return false;
}

Для платформы ARM операцию CAS можно выразить так

bool CAS (uint32_t *ptr, uint32_t e, uint32_t n) {
    uint32_t x = __LDREX(ptr);
   	return ( x == e ) && __STREX(n, ptr);
}

Некоторые алгоритмы, которые я встречал в литературе выражаются через операцию CAS. Всё, что относится к архитектуре Intel лучше описывать такими шаблонами. Шаблон избыточный, но рабочий. Более того, определенные в языке Си примитивы атомарных операций реализуются исходя из такого шаблона. В частности, компилятор GCC с поддержкой std=c11 заменяет atomic_compare_exchange_weak именно на такую структуру. НО этот шаблон порождает избыточный код, мы его не используем. Равно как и не используем примитивы atomic_compare_exchange_weak. Не нравится, как выглядит результат компиляции.

Рекурсивные и живучие мьютексы

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

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

Condition variable

Термин не переводится. Кондиция/готовность -- подойдет. Можно ждать кондиции ресурса (когда созреет), можно из одного треда сообщить другим, что ресурс приобрел кондицию (готовность). Можно сообщить всем, кто ждет этой готовности, что объект приобрел кондицию, готов, когда условие готовности выполнено. Что за условие не уточняем. Т.е. кондиция -- это структура данных, о которой ничего не надо знать кроме того, что она символизирует какое-то условие. Condition представляет собой механизм синхронизации процессов, когда ресурс потребляет один из процессов или сразу множество процессов. У объекта cond_t есть список, неявный, но есть. Потому что операция cond_broadcast разблокирует все заблокированные процессы, каждый со своим мьютексом. Процессы и их мьютексы связаны с condition. Таким образом, либо переменная condition должна быть атрибутом мьютекса, либо список мьютексов должен быть атрибутом объекта condition. Чтобы вынести из ядра операционной системы понятие cond надо выбрать второй вариант - объект готовность (cond) содержит список мьютексов.

Предполагаем возможным описать неблокирующую реализацию готовности (Condition variable) в том случае, если удается реализовать неблокирующие списки. Неблокирующие мьютексы - реализовать возможно.

Не блокирующие списки

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

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

/*! добавить элемент списка в хвост */
void list_append_atomic(List_head_t* list, List_t* node)
{
  do {
      node->next = atomic_get(&list->tail);
      atomic_mb();// операция зписи должна быть выполнена
  } while (!atomic_compare_exchange(&list->tail, node->next, node));
}

/*! добавить элемент списка в начало */
void list_prepend_atomic(List_head_t* list, List_t* node)
{
  do {
      node->next = atomic_get(&list->head);
      atomic_mb();// операция записи в память должна быть выполнена
  } while (!atomic_compare_exchange(&list->head, node->next, node));
}

Следует заметить, что одновременно (атомарно без блокировок, atomic lock-free) вносить изменения в два указателя нельзя. Можно атомарно вносить изменения в одну структуру, которая умещается в слово (в размер регистра). Таким образом можно решить проблему - много писателей, но писать можно либо только в хвост либо только в гриву. И в хвост и в гриву не выйдет.

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

/*! добавить элемент списка перед */
void rlist_insert_atomic(List_t** list, List_t* node)
{
    List_t* next;
    do {
        next = atomic_get(list);
        if (next == NULL) node->next=node;
        else node->next = next;
        atomic_mb();// операция записи в память должна быть выполнена
    } while (!atomic_compare_exchange(list, next, node));
}

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

/*! удалить элемент из списка */
List_t* rlist_remove_atomic(List_t** ptr)
{
    register List_t *next, *node;
    do {
        node = atomic_get(ptr);
        next = node->next;
        if (node == next) next=NULL;
    } while (!atomic_compare_exchange(ptr, node, next));
    return node;
}

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

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

/*! найти элемент в списке */
List_t** curr_rd;// глобальный (общий) указатель 
List_t* list_fetch_next_atomic(List_t** ptr)
{
    register List_t *next, *node;
    do {
        node = atomic_get(ptr);
        next = (node!=NULL)? node->next : node;
    } while (!atomic_compare_exchange(ptr, node, next));
    return node;
}

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

Множество писателей и множество читателей

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

/*! найти элемент в списке */
{
    register List_t *next, *node;
    do {
      while ((lock = atomic_get(&node->lock))!=0) 
          node = node->next;
    } while (!atomic_compare_exchange(&node->lock, lock, LOCK_FLAG));
    return node;
}

Особенностью данного алгоритма является повторное использование инструкции эксклюзивного чтения из памяти __LDREX (в реализации макроса atomic_get). В данном варианте алгоритма каждый процесс чтения имеет возможность работать с каждым элементом списка. Однако, чтобы избежать конфлика не допускается запись в переменную node->next. Допускается выборка одного элемента списка несколькими процессами.

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

/*! вариант того же алгоритма, с глобальным указаетелем позиции чтения (curr_rd) */
{
    register List_t *node;
    register int lock;
    do {
      do{
          node = list_fetch_next_atomic(&curr_rd);
          if (node==NULL){
          	return node;
          }
      } while ((lock = atomic_get(&node->lock))!=0);
    } while (!atomic_compare_exchange(&node->lock, lock, LOCK_FLAG));
    return node;
}

Вероятно следует ограничить число итераций во вложенном цикле.

Таким образом у нас появляется возможность атомарно (atomic lock-free) добавлять в список и обрабатывать элементы по списку, количество чистателей и писателей не ограничено. Есть проблема с удалением. Мы не можем вторично использовать объект List_t node, пока все читатели не отцепятся от этого объекта. Можно предложить использовать счетчик читателей с атомарным доступом. Когда счетчик читателей обращается в нуль, можно удалить и сам объект. Однако, атомарный счетчик числа обращений не обеспечивает сам по себе mutual-consistency (как это по русски, не исключает конфликт доступа при одновременном использовании). Конфиликт возникает по причине, что чтение структуры данных (atomic_get) и чтение-модификация счетчика (atomic_fetch_xxx) - это две раздельных операции, между которыми может произойти переключение задач. Удаление node в данном примере -- это транзакция, отложенное действие. Ниже мы рассмотрим вопрос организации транзакций.

Дерево c со списком дочерних элементов

Такие деревья мы будем применять для организации директории.

/*! структура дерева */
struct _Node {
    struct _Node *next;
    struct _Node *children;
	struct int    key;
    struct void  *data;
};
/* добавить дочерний объект */
void node_append(Node_t *parent, Node_t *n)
{
    do {
        node = atomic_get(&parent->children);
        n->next = node;
        atomic_mb();
    } while (!atomic_compare_exchange(ptr, node, n));	
}
/* удалить дочерний объект */
Node_t* node_remove(Node_t *parent, uint32_t key)
{
    Node_t *node, *next;
    Node_t **prev = (&parent->children);
    do {
      next = NULL;
      while ((node = atomic_get(prev))!=NULL){
          if (node->key == key) {
              next = node->next;	
              break;
          }
          prev = &node->next;
      }
   	} while(!atomic_compare_exchange(prev, node, next);
    return node;
}
/* найти дочерний объект */
void node_lookup(Node_t *parent, uint32_t key)
{
	. . .
}

Бинарное Дерево

void* tree_lookup(tree_t **parent, uint32_t key)
{
    while((node = *parent)!=NULL) {
		int32_t cmp = key - node->key;
		if(cmp==0) break;
        parent = (cmp < 0)? &node->prev: &node->next;
    }
    return node;
}
Node_t* tree_insert(tree_t *parent, uint32_t key, void* data)
{
   	do {
        while((node = atomic_get(parent))!=NULL) {// найти куда бы вставить
            int32_t cmp = key - node->key;
            if(cmp==0) {
            	. . .;
            }
            parent = (cmp < 0)? &node->prev: &node->next;
        }
    } while (!atomic_compare_exchange(parent, node, n));
    return node;
}

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

Выделение памяти из кучи, malloc

Выделение и освобождение памяти должно обладать тем же свойством, Wait-free. Поскольку основной потребитель этого механизма- слайсы и буферы обмена, мы не накладываем существенных ограничей на механизм сбора мусора. Для встроенных систем можно предложить разработчику использовать malloc без освобождения, без функции free. Чтобы повысить эффективность сбора мусора можем предложить разработчику освобождать память в обратной последовательности.

/*! выделение памяти из кучи*/
struct _List_heap {
    struct _List_heap *next;
    uint8_t data[0];
};

static List_heap_t *heap;
static List_heap_t *heap_top;

void* _alloc(size_t size){
    List_heap_t * node;
    do {
        node = atomic_get(&heap_top);
        next = (void*)node+ALIGN(size,4);
    } while (!atomic_compare_exchange(&heap_top, node, next));
    node->next = next;
	atomic_mb();
	return node->data;
}
void _free(void* data){// вернуть объект в кучку.
	List_heap_t * node = (List_heap_t *)data - 1;
    node->next |= 1;// подняли флаг освобождения
}

Из рассмотрения исключаем процедуру сбора мусора, которая включает объединение обрезков памяти, сортировку обрезков и вторичное использование. Тут нам важно показать, что обе операции можно производить без задержки и без ожидания. Циклы на выделение и на освобождения памяти не используются.

Переменная node->next заполняется уже после того, как записан указатель вершины кучи. После того как владение переменной переходит к текущему процессу. Придется теперь вводить понятие "владение"..

Один шаг сбора мусора можно добавить в функцию _free

void _free(void* data){
	List_heap_t * node = (List_heap_t *)data - 1;
    node->next |= 1;// подняли флаг освобождения
    do {
    	top = atomic_get(&heap_top);
        if (top != node->next){
        	atomic_clear();
        	break;
        }
    } while (!atomic_compare_exchange(&heap_top, top, node));
}

void* _realloc(void* data, size_t size){
	List_heap_t * node = (List_heap_t *)data - 1;
    do {
    	top = atomic_get(&heap_top);
        if (top != node->next){// перезаписать данные в новый блок
            . . .
            break;
        }
    } while (!atomic_compare_exchange(&heap_top, top, node->data + ALIGN(size,4)));
    return node->data;
}

Распределение блоков памяти из массива, слайсы

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

/*! выделение памяти блоками из массива*/
static List_slice_t *slices[N];

void* slice_alloc(size_t size){
	int idx = block_index(size);
    List_slice_t * node;
    do {
        node = atomic_get(&slices[idx]);
        if (node==NULL) {
        	node = block_new(idx);
            atomic_free();
        	break;
        }
    } while (!atomic_compare_exchange(&slices[idx], node, node->next));
	return node;
}

Нарезка (слайсы) организована в списки односвязные. За одно движение мы снимаем первый элемент списка - стек. При освобождении слайса кладем на стек соответсвующего списка.

void slice_free(void* data, size_t size)
{// добавить в список свободных блоков.
	int idx = block_index(size);
	List_slice_t * node = data;
    do {
        node->next = atomic_get(&slices[idx]);
        atomic_mb();// запись в память должна быть завершена
    } while (!atomic_compare_exchange(&slices[idx], node->next, node));
}

В данном примере оставляем без внимания функцию округления размера блока (block_index) и функцию наполнения (block_new), чтобы не перегружать изложение.

Асинхронная очередь

Асинхронная очередь - это два указателя, указатель чтения (head) и указатель записи (tail). Если оба указателя держать в одой структуре с атомарным доступом, все получится. Если читатель один, а писателей много, получится даже если указатели держать в разных местах. Мы можем обеспечить атомарное изъятие из очереди со стороны читателя, правда с нарушением порядка следования. Когда читатель один, можно упорядочить очередь со стороны читателя.

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

/*! забрать элемент атомарно */
void* atomic_pointer_exchange(void** ptr, void* n)
{
    void *v;
    do {
        v = __LDREXW(ptr);
    } while (!__STREXW(n, ptr));
    return v;
}

/*! добавить элемент в очередь */
void async_queue_push(Queue_t* queue, List_t* n)
{
    List_t *v;
    do {
        v = __LDREXW(&queue->tail);
        n->next = v;
        __DMB();
    } while (!__STREXW(n, &queue->tail));
}

/*! забрать элемент из очереди */
void* async_queue_pop(Queue_t* queue)
{
	// взять с начала списка
	List_t *list = atomic_pointer_exchange(&queue->tail, NULL);
    // вывернуть список, выполнить сортировку
    while (list) {
        . . .
    	list = list->next;
    }
    return v;
}

Данная реализация работает через одну переменную tail, принцип работы с переменной - стек.

Читатель атомарно забирает весь хвост очереди, затем производит разбор и сортировку очереди. Мы предполагаем одного читателя очереди, так что упорядоченный список (head) может располагаться и быть доступным только читателю без ограничений. Асинхронная очередь с такой организацией может быть использована в ядре ОС для орагизации списка задач, например, или для организации потока событий адресованных процессу. Сортировка со стороны читателя может выполняться с учетом приоритета (или Дедлайна). Для организации очереди сообщений между процессами нужно еще одно свойство - ограничение длины очереди, которое может производиться с использованием семафора. Очередь с семафором рассмотрим ниже.

Кольцевой буфер FIFO с множеством писателей, wait-free

Читателем кольцевого буфера может быть обработчик прерываний от интерфейса (один читатель).

Кольцевой буфер можно защитить от переполнения с использованием семафора.

#define SIZE (1<<N) // Размер буфера
volatile int queue_count = SIZE;
/* процесс писателя, multiple writers */
int osFIFO_put(FIFO_t* fifo, data, timeout) 
{
    if (!semaphore_enter(&fifo->count)){// FIFO переполнено
        return -1;
    }
    volatile int * wr_pos = &fifo->wr_pos;
    do {
        wr = atomic_get(wr_pos);
    } while (!atomic_compare_exchange(wr_pos, wr, (wr+1) & (SIZE-1)));
    ACCESS_ONCE(buf[wr])= data;
    // обозначить готовность элемента очереди: NULL - блок не заполнен
    return 0;
}
// процесс читателя, single reader
void* osFIFO_get(FIFO_t* fifo)
{
  void* data = atomic_exchange(&fifo->buf[rd], NULL);
  if (data!=NULL){
     rd = (rd+1) & (SIZE-1);
     semaphore_leave(&fifo->count);
  }
  return data;
}

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

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

Известна реализация на четырех указателях, каждый из указателей curr_rd и curr_wr представлен двумя, один - резервирование, второй - готовность, но каждый процесс вынужден ждать и соблюдать очередность записи в указатель готовности. [Multi-reader, multi-writer lock-free ring buffer. US8095727B2 ] -- отстой!! Ожидание на каждой операции мы хотим исключить.

Хеш-таблицы, Wait-free

Я исхожу из того, что читатель много знает про списки. Хеш таблицы надо уметь заполнять атомарно и желательно без ожидания, Wait-free. Хеш таблица состоит из таблицы (bucket) определенного размера, например 2^^n и списками по каждому хешу. Есть необходимость поддержать хеш таблицы в файловой системе, в алгоритмах работы со строками, текстовом поиске, базах данных (поиск).

void* htable_insert(FIFO_t* fifo, char* key, )
{
	int index = hash(key);
    List_t **prev = &htable->bucket[key % htable->n_bucket];
    while ((node = *prev)!=NULL){
    	if (node->index > index) {
            break;
        }
    	prev = &node->next;
    }
    n->next = node;
    *prev = n;
}

Пробуем преобразовать этот алгоритм...

// не блокирующий алгоритм
List_t* htable_insert_lockfree(HTable_t* htable, char* key, List_t *n)
{
	int index = hash(key);
    List_t *node;
  	List_t **prev;
    prev = &htable->bucket[key % htable->n_bucket];
	do { 
        while ((node = atomic_get(prev))!=NULL){
            if (node->index >  index) {
                break;
            }
            prev = &node->next;
        }
        n->next = node;
        atomic_mb();
	} while (!atomic_compare_exchange(prev, node, n));
    return node;
}

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

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

List_t* htable_lookup(HTable_t* htable, char* key)
{
	int index = hash(key);
	List_t **prev;
 	prev = &htable->bucket[index % htable->n_bucket];
    while ((node = *prev)!=NULL){
    	if (node->index == index) {
            break;
        }
    	prev = &node->next;
    }
	return node;
}

Проверка функций на отсуствие конфликтов

Выше мы предложили некоторое количество алгоритмов, построенных на одном или нескольких шаблонах. Надо сформулировать правила проверки этих алгоритмов, как доказать что алгоритмы работают и не имеют ошибок типа не инициализированная переменна или переменная инициализируется дважды. Предлагаем тесты, варианты конфликтов внутри конструкции
do {v = atomic_get;..}while(!atomic_compare_exchange()).

1. Все операции выполняются на регистрах без общения к памяти. - ОК
2. После общения к памяти стоит барьер записи в память. - ОК
3. Выполняется обращение к памяти на запись и переменная принадлежит текущему треду. - ОК
4. Выполняется обращение к памяти на чтение и переменная не может быть изменена в другом треде - ОК
5. При работе со списками используется глобальный общий указатель вершины - ОК

. . .

. . .

API для STM, программный интерфейс описания отложенных транзакций памяти

Тут мы обсудим программные интерфейсы работы с объектами типа очередь, хеш-таблица, дерево и т.п.

RCU? -- Нет! Я беру за основу некоторую идею: не каждая модификация структуры данных нарушает целостность данных (mutual consistency). Возможно дописывать очереди и деревья таким образом, чтобы чтение и новой версии и старой не приводило к потере данных. Например, когда список читается только в одном направлении. Если второй процесс вставил в список элемент в процессе чтения, то результат относится к пердыдущей или текущей версии, мы не знаем. Нужно разбирать какие то конкретные примеры, когда это критично, а когда нет.

/*! программный интерфейс читателя */
void* object_read_access(...)
{
    do {
        tx = start_transaction();
        // просто читаем структуру, без атомарных операций
    } while (!commit_transaction(tx));
}

Возможно ли построить STM всего на одном аппаратно поддержаном флаге, на флаге Эксклюзивного монитора(EX)? Операция start_transaction поднимает флаг EX, а commit_transaction опускает. Можно при этом считать изменения. Нужна диаграмма конкуренции процессов, попробую словами изложить. Если выключить Preemption, могут возникать прерывания (Nested, вложенные). Принцип вложенности не нарушает логику операций LDREX/STREX, если каждая операция завершается очисткой флага EX. Если включен режим Preemption, то планировщик обязан опустить флаг EX при переключении задач, чтобы логика не нарушалась. Ткаим образом гарантируется сброс EX в случае использования эксклюзивного доступа в любом другом процессе или прерывании.

static inline 
start_transaction(STM_t *stm)
{
	stm->revision = __LDREXW(head);// EX:=1
}
static inline bool commit_transaction(STM_t *stm)
{
	__DMB();// все операции записи, связанные с ревизией должны быть выполнены
	return __STREXW(head, stm->revision);// EX:=0
}
static inline void clear_transaction(STM_t *stm)
{
	__CLREX();// EX:=0
}

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

Упражнения на закрепление темы

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

void atomic_ref(volatile int*ptr)
{
	register unsigned count;
    do {
        count = __LDREXW(ptr);
    } while(__STREXW(count+1, ptr));
}
unsigned atomic_unref(volatile int*ptr)
{
	register unsigned count = __LDREXW(ptr);
    if (count>0) count--;
    __STREXW(count, ptr);
    return count;
}

Правильный ответ -- Нет! Если есть два отдельных слова, ссылка на объект и счетчик обращений, даже если каждый из них изменяется с помощью атомарной операции, вместе две операциии теряют атомарность. У объекта может быть читатель в момент удаления, до обращения к atomic_ref(&obj->count). Можно применять эти фукнции только если объект после уменьшения счетчика перемещается в карантин, но фактически не удаляется до последнего читателя способного дотянуться до счетчика.

Следующие функции построены на ином шаблоне. Без конфликтов?

/*! атомарно пролстать(читать) из список */
List_t* list_lookup(STM_t** head, key)
{
    register List_t *node;
    do {
    	tx = atomic_get(head);// __LDREXW()
        
        while ((node = ACCESS_ONCE(prev))!=NULL) {
            if (node->key == key) {
                break;
            }
            prev = &node->next;
        }
    } while (!atomic_compare_exchange(head, tx, tx));
    return node;
}

Допустимо, если никакой другой процесс не меняет структуру списка, т.е. никакие поля node->next не меняются в процессе чтения.

Следующие функции построены на ином шаблоне. Надо опеределить на глаз имеют ли они право на существование или нет. Обеспечивают ли структурную целостность при одновременном обращении на чтение и изменение.

/*! атомарно исключить из упорядоченного списка */
void* list_remove_atomic(List_t** prev, key)
{
    register List_t *node;
    register void* data;
      while ((node = ACCESS_ONCE(prev))!=NULL) {
          if (node->key == key) {
          	  data = atomic_exchange(&node->data, NULL);
              return data;
          }
          prev = &node->next;
      }
    return NULL;
}

Аналогично, допустимо, если поля node->next не меняются.

/*! атомарно в список */
List_t* list_delete_atomic(List_t** prev, key)
{
    register List_t *node, *next;
    do {
        while ((node = ACCESS_ONCE(prev))!=NULL) {
            if (node->key == key){
            	data = atomic_exchange(&node->data, NULL);
                break;
            }
            prev = &node->next
        }
    } while(!CAS(prev, node, next));// атомарно
    return data;
}

От операции CAS требуется, чтобы до начала ее исполнения был выполнен WRITE_MEMORY_BARRIER.

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

MCAS, Многословный CAS

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

/* операция доступа к памяти */
void* tm_open (trans_t * tx, void** ptr) {
    tx->ptr = ptr;
	do {
      tm_node_t* src = atomic_get(ptr);
      tx->dst = tm_copy(tx->dst, src);
      tx->src = src;
      atomic_mb();
    } while (!atomic_compare_exchange(ptr, src, src));
    return tx->dst;
}

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

/* операция доступа к памяти */
bool MCAS (void** ptr, void* prev, void* dst) 
{
    void* src;
    do {
      src = atomic_get(ptr);
      if(src!=prev || memcmp(dst, src, len)!=0){
          atomic_clear();
          return false;
      }
    } while (!atomic_compare_exchange(ptr, src, dst));
    return true;
}

/* операция доступа к памяти */
void* MCASRead (void** ptr) 
{
    void* src;
    do {
      src = atomic_get(ptr);
      memcpy(dst, src, len);
      atomic_mb();
    } while (!atomic_compare_exchange(ptr, src, src));
    return dst;
}

Эта конструкция будет работать только на операциях LDREX/STREX. При этом мы подразумеваем, что при каждом обращении к памяти используются операции эксклюзивного чтения/записи. Механизм тот же: флаг эксклюзивного доступа поднимаем, флаг опускаем.

Ниже приведу пример API STM на операциях MCAS из статьи [CPWL]

typedef struct _node node_t;
struct _node { int key; struct _node *next; };

void list insert mcas (node_t **head, node_t *n) 
{
    node_t *curr;
    do {
        node_t *prev = MCASRead( head );
        curr = MCASRead( &prev->next );
        while ( curr->key < n->k ) {
            prev = curr;
            curr = MCASRead( &prev->next );
        }
        n->next = curr;
    } while ( !MCAS (&prev->next, curr, n) );
}

Куда там копируется память MCASRead и почему нет проверки на NULL - сложно сказать, но в целом понятно, что хотели высказать. Операции производятся с элементами списка. Чтобы сохранить целостность, элемент списка копируется целиком. Операции MCASRead и MCAS должны употребляться парой и обращаться к одному и тому же указателю (&prev->next). Операция позволяет читать и вставлять, но вот удаление дается с трудом. Мы научились работать атомарно с объектами(блоками памяти), но не можем два объекта зафиксировать одновременно. Для удаления надо фиксировать два объетка: предыдущий и искомый.

/* операция записи блока данных */
bool tm_commit (trans_t *tx) 
{

	// в списке существуют оба объекта: старый и новый. 
	ACCESS_ONCE(&tx->code) = TM_COMMIT;
    return true;
}

/* сбор мусора выполняется фоном */
void tm_garbage_collect() 
{
	do {
    	tx = atomic_get(&tx_head);
		if(tx->next==NULL || tx->code == TM_ACTIVE) {
            return;
        }
    } while(!atomic_compare_exchange(&tx_head, tx, tx->next));
    if (tx->src!=NULL)
        tm_block_delete(tx->src);
    tm_delete(tx);
}

/* начало транзакции */
trans_t * tm_start () 
{
	trans_t *tx = tm_alloc();
    tx->next= NULL;
    tx->src = NULL;
    tx->code= TM_ACTIVE; // в одном поле живет с ptr
    atomic_mb();
	do {
      tx_prev = atomic_get(&tx_last);
    } while(!atomic_compare_exchange(&tx_last, tx_prev, tx));
    ACCESS_ONCE(&tx_prev->next) = tx;
    return tx;
}

/* операция чтения памяти без копирования */
void* tm_read (trans_t * tx, void** ptr) {

    return ACCESS_ONCE(ptr);
}

/* операция записи */
void tm_write (trans_t * tx, void** ptr, void* prev, void* n) {
	do {
      v = atomic_get(ptr);
      if (v!= prev) {
          return;
      }
    } while (!atomic_compare_exchange(ptr, v, n));
    tx->src = v;
}

Мы представили операции над блоком данных. Для блока можно определить уникальный идентификатор, адрес блока. В списке блок данных определяется идентификатором по которому функция tm_read или tm_open выдает доступ.

. . .

// пример алгоритма использующий API STM
void list_insert_tm (BlockId ref, int k, n) {
	trans_t *tx;
    do {
        tx = tm_start();
        while ((node = tm_read(tx, ref))!=NULL) {
        	if (node->key >= k) break;
            ref = tm_ref(node->next);// прибавляет смещение (константу)
        }
        tm_write(tx, ref, node, n);

    } while (!tm_commit(tx));
}

/*! заменяем элемент в списке */
void list_replace_tm(BlockId ref, k, n)
{
    do {
    	tx = tm_start();
        while ((node = tm_read(tx, ref))!=NULL) {
            if (node->key == key) break;
            ref = tm_ref(node->next);
        }
        n->next = (node!=NULL)? node->next: NULL;
        tm_replace(tx, ref, node, n);// записываем транзакцию: где, что и чем заменяем.
    } while(!tm_commit(tx));
}

tm_write должна помечать новый элемент списка(n), как принадлежащий транзакции (tx) и помечать элемент (prev) на удаление. Мы хотим, чтобы tm_read, по сути ничего не производила. НО, есть одно великое ограничение, не должен нарушаться порядок действий. Мы хотим чтобы никакие действия по чтению не требовали дополнительных пометок. Мы хотим чтобы операция чтения не требовала операции ожидания при обращении к tm_commit.

Tранзакции STM связаны с объектами типа элемент дерева или элемент списка, вот тут мы и переходим к следующей концепции -- object-based software transactional memory (OSTM).

Я создал что-то свое? Я создал не рабочее API? Я утверждаю, что подобное API неотделимо от менеджера памяти tm_alloc. Элементы сипска выделяются слайсами, нарезкой из массива.

DSTM, отложенные транзакции для динамических структур данных

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

Что тут общего с RCU? RCU отключает preemption на время чтения. Синхронизация дается с трудом, и вызывает ожидание в десятки миллисекунд. Однако тут скрыта хороша идея, которую надо бы поддержать. Идея - читателей очень много, структура данных - это скорее всего системный реестр или конфигурация, в нее редко дописывают. При проектировании RCU подобного API мы хотим получить максимальную скорость чтения, никогда не ждать завершения записи. Требуем mutual consistency (целостности во всех версиях). Допускаем одновременное существование одной и более версий структуры и не пытаемся их различать. Таким образом из описания следует API читателя, приведу в виде примера алгоритма чтения.

/*!  */
do {
  tx = tm_start(READ_ONLY);
  ref = &head;
  while((node = tm_read(tx, ref))!=NULL) {// работа со списком
      . . .
      ref = node->next;
  }
} while(!tm_commit(tx));

Дополнительное требование к этому API - транзакция читателя всегда завершается без повторной обработки цикла do.

Самое главное свойство TM - вся работа выполняется В ИЗОЛЯЦИИ. Т.е. мы изначально предполагаем, что база данных, реестр, список, директория, динамические данные находятся на другом конце света и при каждом обращении к API происходят транзакции - копирования данных с недоступного для обозрения места (с удаленного хранилища, диска или сервера) в локальную память приложения. Мы предполагаем, что процессоров очень много, как в видеокарте и у каждого своя локальная память. Нужен пример, двух других действий, так не понять.

/*! изменение данных в структуре */
do {
  tx = tm_start(READ_COPY_UPDATE);
  ref = &head;
  while(node = tm_read(tx, ref)) {// работа со списком
      . . .
      ref = node->next;
  }
  if (node!=NULL) {// исключить элемент
      n = tm_copy(tx, ref, node);
      . . .
      n->data = data;
      tm_update(tx, ref, node, n);
  }
} while(!tm_commit_transaction(tx));

/*! удаление данных из структуры */
do {
  tx = tm_start(READ_DELETE);
  ref = &head;
  while(node = tm_read(tx, ref)) {// работа со списком
      . . .
      ref = node->next;
  }
  if (node!=NULL) {// исключить элемент
      tm_delete(tx, ref, node);
  }
} while(!tm_commit_transaction(tx));

/*! добавление данных в структуру */
do {
  tx = tm_start(READ_UPDATE);
  ref = &head;
  while(node = tm_read(tx, ref)) {// работа со списком
      . . .
      ref = &node->next;
  }
  if (node!=NULL) {// вставить элемент
      . . . // инициализация
      n->next = node->next;
      node->next = tm_insert(tx, ref, n);
  }
} while(!tm_commit(tx));

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

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

Перейдем к реализации. Сначала мы будем рассматривать системную функцию управление реестром, потом попробуем перенести часть функционала на сторону клиента и обеспечить Wait-free доступ к данным на чтение.

tm_start

создает транзакцию. идентификатор версии, открытой на чтение

tm_read

создает локальную копию данных по уникальному идентификатору записи.

tm_copy

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

tm_insert

создает уникальный идентификатор записи для данных.

tm_update

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

tm_replace

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

tm_delete

удаляет данные с уникальным идентификатором из новой версии.

tm_commit

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

Подведем итоги

Предложена концепция построения операционной системы для встроенных приложений, полностью Wait-free (без ожидания ресурса и без блокирования исполнения множества потоков). Подход основан на механизме atomic lock-free операций эксклюзивного доступа к памяти типа LL/SC (MIPS) и LDREX/STREX (ARM). Показано, что аналогично можно использовать операции CAS, создавая при этом кросплатформенный исходный код.

Автором статьи создана операционная система для встроенных приложений, поддерживающая preemptive multitasking, обладающая характеристиками Wait-free, не блокирующая с прогнозируемыми(фиксированными) задержками получения результата. Операционная система поддерживает интерфейсы и библиотек C11, включая потоки, mutex, conditional variable. Поддерживает интерфейс CMSIS RTOS.

• [ARM_Sync] ARM® Synchronization Primitives. Development Article, 2009. DHT0008A (ID081709)
• [ACLE] Arm C Language Extensions Documentation, Release ACLE Q3 2020, Sep 30, 2020
• [ARMARM_7A] Arm, Arm Architecture Reference Manual (7-A / 7-R), Arm DDI 0406C
• [ARMARM_8M] Arm®v8‑M Architecture Reference Manual.
• [ARMTRM_M4] Arm® Cortex®-M4 Processor Revision: r0p1 Technical Reference Manual
• [ARMTRM_M55] Arm® Cortex®-M55 Processor Revision: r0p2 Technical Reference Manual
  -- много документов, в которых я изыскиваю обрывки знаний про Exclusive Monitor. НО было время, когда лет 10-20 назад я прочитал с листа об инструкциях LL/SC MIPS32 и все сразу стало ясно. Инструкции LL/SC, как и понятие атомарных инструкций Read-Modify-Write, появились в процессарах MIPS II (1990?). Потом уже изучал инструкции Sparc и Intel чтобы найти что-то похожее, находил SWAP и CAS. Нашел инструкции load-locked и Store-Conditional в архитектуре DEC Inc. Alpha AXP (Alpha Architecture Handbook, 1996) и тоже понял, как работает этот механизм в SMP симметричной мульти-процессорной архитектуре. Но реально только на микроконтроллерах ARM стал применять, а собственную операционку с Wait-free примитивами синхронизации сделал в 2014г.
• [C11-N1570]
• [C2x-N2596] Programming languages — C. working draft — December 11, 2020 ISO/IEC 9899:202x (E)
• [CPWL] Concurrent Programming Without Locks, KEIR FRASER and TIM HARRIS
  -- это вот центральная статья, которая многим позволила говорить про отложенные транзакции. Мне хочется переделать историю. История не такая. Не эта стаья является отправной точкой работы, она каким-то образом завершает изыскания в области трназакций, потому переводит алгоритмы в разряд интерфейса API для многопотокового программирования. Под впечатлением статьи я говорю важен API, а не реализация. Реализация - приложится.