Real-Time Scheduling -- планировщик для RTOS

Цель статьи - восполнить нехватку терминологии в области управления процессами в системе реального времени, ОСРВ (анг. Real-Time OS). Надо определить, где наша RTOS располагатся относительно мировых достижений. В данной статье рассматривается терминология и обсуждается применимость методов планирования.

Хороший планировщик заданий - не обязательно сложный и ресурсоемкий алгоритм. Когда мы создаем операционную систему для контроллера мы работаем с голым железом. Ничто нас не ограничивает, мы можем использовать предоставляемые возможности контроллера на свое усмотрение. Эффективное управление можно описать без использования операционной системы. Необходимостью является довольно существенный объем системного кода, который выполняет переключение задач - планировщик заданий (анг. Task Scheduler).

Наша RTOS как идея зарождалась, когда мы еще использовали 8-битные контроллеры 51-й серии. Тогда не было никакой необходимости в планировании времени, наша ОС состояла из двух основных частей: жеского реал-тайма, который запускался по таймеру, и некоторой системной части - модульного ядра, которая выполнялась последовательно без переключения между заданиями. Позже, с переходом на 32 битные контроллеры ARM7TDMI, мы внедрили динамическое распределение памяти, и с переходом на Cortex-M стали активно использовать многозадачность. В качестве основного интерфейса был выбран CMSIS-RTOS API, с поддержкой тредов и полного набора возможностей синхронизации. В таком виде концепция ОС для конотроллеров просуществовала на протяжении 10 лет. Сегодня мы поддерживаем три системных интерфейса: CMSIS-RTOS API, CMSIS-RTOS v2, C11 <threads.h>. В этом году мы начали работу по масштабной поддержке системных интерфейсов POSIX. Реализация POSIX позволяет обеспечить переносимость прикладного кода между системами. Мы хотим сохранить эффективность управления заданиями и возможность гибкой настройки процессов планирования и в тоже время добавить переносимость для прикладного кода. Мы придерживаемся требования на сохранение эффективности кода: внедрение поддержки POSIX не должно вызывать существенного увеличения объема прошивок и снижения эффективности.

Терминология

Real-Time System

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

Soft real-time, Hard real-time

RTOS cистемы условно можно разделить на две категории: с мягкими и жесткими требованиями. Различие можно определить так: нарушение временных параметров запуска заданий ведет к фатальным последствиям (hard real-time) или к временным сбоям, с возможностью дальнейшей работы (soft real-time). Пример жесткого реал-тайма: управение двигателем, управление рановесием (балансом), упраление летательным аппаратом. Обычно жесткие требования возникают применительно к задачам с периодической активностью. Soft real-time применятеся к апериодичским процессам.

Task -- задача (τ_i), процесс или тред, объект, для которого выполняется планирование времени запуска.
Job -- задание (J_i,j), процесс (Task_i) складывается из заданий.
Arrival Time (a_i,j) -- абсолютное время, когда процесс (τ_i) готов к исполнению очередного задания (J_i,j).
Burst Time, Execution time (c_i,j) -- время исполнения, интервал времени, когда процесс исполняется на CPU (Job), занимает процессорное время.
Absolute deadline, d_i,j, -- время от момента постановки в очередь до завершения выполнения задания (J_i,j). Время ожидания (arrival) и время работы (Execution time) в сумме образуют deadline (готовность)
worst case execution time (WCET) -- максимальное время исполнения.
minimum inter-arrival time (MIT) -- минимальная измеренная разница между задержками (arrival) на исполнение двух последовательных заданий одного процесса.

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

Priority Scheduling (PS)
-- планирование на основе приоритетов. Процессы орагнизуются в несколько очередей, каждая со своим приоритетом: сначала исполняются процессы с большим приоритетом, затем - с меньшим. Термин PS может применяться в сочетании с другими принципами планирования. Система, в которой PS - единственный механизм планирования, не жизнеспособная и не применима к RTOS, поскольку не гарантирует своевременное исполнение заданий.

Cooperative vs. Preemptive -- кооперативная и вытесняющая многозадачность. Кооперативная получается, когда процесс может передать управление только добровольно, например при ожидании ввода-вывода. Вытесняющая, когда определены правила переключения задач по времени работы. Правила переключения задач могут включать требования на приоритеты задач. Самая простая модель -- переключение задач на основе приоритетов: сначала выполняются все задачи с большим приоритетом, затем с меньшим. Процессы с большим приоритетом могут прерывать работу процессов с меньшим приоритетом. Процессы могут быть организованы в кольцевой буфер без нарушения порядка следования, первым вошел первым вышел(FIFO). В случае PS на основе приоритетов говорят об использовании нескольких очередей, каждая со своим приоритетом.

Rate-monotonic scheduling

Это система планирования, при которой частота запуска задачи (период работы) определяется ее приоритетом. Период работы до переключения обрано пропорционален приоритету задачи (1/T_i). Отношение максимальной продолжительности исполнения задания C_i = max{c_i,j} к величине периода (T_i), дает оценку загруженности процессора. Система планирования дает хороший результат, если общая загруженность не превышает 69% (в литературе пишут). RMS планирование предоставляет каждой задаче время работы задания порядка C/T.

Deadline-monotonic scheduling
Период работы до переключения обрано пропорционален дедлайну задачи, оценке времени завершения.

Earliest Deadline First (EDF)
-- алгоритм планирования на основе оценки времени завершения задания. Задания в очереди готовых к исполнению заданий сортируются по времени завершения. Система планирования EDF дает хороший результат в высоко нагруженных системах, если общая загруженность достигает 100% (в литературе так пишут).

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

Mixed-Criticality real-time systems

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

Hierarchical Scheduling

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

Алгоритмы

FIFO - очередь процессов. Готовые к исполнению процессы перебираются по порядку из очереди, без нарушения порядка следования. Процесс может ожидать события или быть готовым к запуcку, так что представляем две очереди: процессы, которые ждут, и процессы готовые к исполнению. Процессы готовые к исполнению перебираются последовательно. В RTOS необходимо использовать вытесняющую многозадачность и обеспечить работу всех процессов. В сочетании с методом FIFO можно использовать кооперативную многозадачность. Расширением является планирование на основе приоритетов, нескольких очередей.

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

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

Можно получить хороший результат, если планирование выполняется методом RR. Когда я смотрю код контроллера - вижу, что метод RR - оптимальный выбор, сочетающий простоту и эффективность. Дело в том, что в RTOS не сильно загруженной, большая часть операций происходит асинхронно, каждая операция, которая требует отслеживания готовности или флага события не вызывает продолжительную загрузку CPU. Обработка событий выполняется в планировщике или по прерыванию, такми образом практически не реализуется необходимость принудительного переключения задач. Управление передается добровольно и возвращается по событию. Такое поведение характерно для систем с низкой нагруженностью. Однако можно представить некоторую ситуацию, когда отдельные процессы вызывают болшую загрузку CPU, например обработка графики или обработка сетевого трафика.

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

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

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

Параметры запуска будут включать приод, требование на джиттер, фазу и опцию фазовой подстройки частоты запуска задачи. При этом все эти задачи должны быть с высоким приоритетом, не прерываться, обладать свойством кооперативная многозадачность, добровольно передавать управление. Остальные задачи в системе должны выполняться в фоне, когда процессор не занят обработкой задач с требованием hard real-time.

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

Для RTOS НУЖЕН Планировщик, который обеспечивает такое планирование на периодических процессах. И в тоже время хорошо работает на не пероидических задачах.

Попробую описать модель. Определяем очередь событий таймера, в которую добавляются треды с задержкой запуска, указанной с точностью до микросекунды. Эта очередь анализируется периодически по таймеру. Сортировка в очереди соответсвует понятию EDF. По таймеру, при наступлении расчетного времени запуска задача ставится на исполнение и прерывает текущую задачу (preempt). Запишем так:

// тред прерывает работу исполнения треда
    // в зависимости от приоритета расчитывается прибавка к бюджету
    thread->budget += BUDGET(thread->priority)
    // бюджет не должен превышать установленный лимит
    if (thread->budget > thread->init_budget)
        thread->budget = thread->init_budget;
    // если процесс не активен, добавляем его в начало очереди
    thread->priority= thread->sched.priority;
    sched_head(thread, thread->priority);

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

if (running_thread->preempt) {
    running_thread->budget -= execution_time;
    sched_head(running_thread, running_thread->priority);
    __YIELD();
} else
if (running_thread->budget <= execution_time) {
  	running_thread->budget -= execution_time;
    running_thread->priority= running_thread->sched.low_priority;
  	running_thread->budget += BUDGET(running_thread->priority);
    sched_tail(running_thread, running_thread->priority);
    __YIELD();
}

В системе необходимо поддержать CPU_clock() - измерение штампа времени с точностью до такта процессора или такта системного таймера, из которого вычисляется execution_time до переключения.

Инициализация процесса происходит с атрибутами: sched_priority, sched_ss_low_priority, sched_ss_initial_budget. Можно немного доработать алгоритм и вычислять прибавку в бюджет BUDGET() на основе измеренного времени работы, thread->execution_time - время работы процесса до перехода в режим ожидания.

Aperiodic Task Scheduling

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

Апериодические сервисы называют Sporadic Server. Таким образом работу нашего планировщика можно описывать политикой SCHED_SPORADIC с набором атрибутов планирования. Такой сервис выполняется какое-то время (бюджетное, Q) с высоким приоритетом, затем приоритет занижается и разрешается прерывать задачу по времени, если она сама не отдала управление. Процесс ждет событие, затем выполняет некоторую работу в течение определенного времени (назовем бюджет) и уходит в ожидание. Если задача не ушла в ожидание, ей занижают приоритет. Измеренное время работы может использоваться для планирования и вычисления бюджета.

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

Background Service

Это механизм запука апериодических задач в фоновом режиме, в режиме FIFO. В одной системе мы можем использовать несколько планировщиков. Мы можем выделить некоторый квант времени на работу фоновых процессов, к которым не предъявляются особые требования и не применяется PS планирование на основе приоритетов. В нашей системе к таким сервисам отностится сбор мусора и терминал вывода отладочной информации.

Этим же термином мы можем определить две очереди в планировщике: background, foreground. Очередь background обрабатывается с низким приоритетом, в своем временном интервале и может прерываться процессами из очереди foreground. Если задача выполняется слишком долго, можно ее автоматически перекинуть в из очереди foreground в очередь background.

Polling Server (PS)

Апериодические процессы, к которым не предъявляются требования к синхронности обработки могут запускаться по опросу готовности. Мы поддерживаем некоторый механизм запуска задач (Сервисов) по событиям с периодическим опросом состояния. По сути у нас в системе есть еще один планировщик. Если бы нам удалось определить такие задачи через определение политики планировщика, их можно было бы запускать с использованием pthread или определить, как событие, как struct sigevent, подобно тому как запускаются таймерные задачи, но с запуском процесса по событию. PS работает в фоновом режиме. Теоретически реализация PS может быть представлена, как периодический запуск планировщика со своей очередью. Отличие сервиса от обычного треда: при выходе из функции подобно таймеру, сервис снова ставится в очередь ожидания обработки.

Deferrable Server (DS)

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

Sporadic Server (SS)

Политика SCHED_SPORADIC d POSIX.1-2017 задает набор параметров:
sched_priority -- начальный приоритет исполнения
sched_ss_max_repl -- ограничение на число операций начислений в бюджет
sched_ss_low_priority, -- низкий приоритет
sched_ss_repl_period, -- задержка перед активацией начисления
sched_ss_initial_budget -- максимальное время работы без переключения

Количество необработанных запросов (replenishment operation) на пополнение бюджета ограничено величиной sched_ss_max_repl. Превышение этого ограничения ведет к снижению приоритета. Если задача в данный момент не активна или сигнал не может быть доставлен, сигнал ставится в очередь с высоким приоритетом и параметром activation_time + sched_ss_repl_period, чтобы обработка произошла в течение заданного интервала времени, затем увеличиваем счетчик запросов thread->pending.

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

Политика SCHED_FIFO позволяет устанавливать приоритет в интервале pthread_setschedprio(). В определении политики SCHED_RR бюджет фиксирован и обозначается параметром Round-Robin Interval. Стандарт POSIX определяет политку SCHED_SPORADIC, которую мы используем под свои нужды, или определяем некотороую нестандартную политику SCHED_DEADLINE, обеспечивающую обработку событий в заданный интервал времени. Политика SCHED_OTHER ничего не определяет точно, под ней можно скрыть нормальный режим работы планировщика с любым количеством параметров. POSIX дает характеристики политикам планировщика [POSIX: 2.8.4 Process Scheduling]:

SCHED_FIFO

Threads scheduled under this policy are chosen from a thread list that is ordered by the time its threads have been on the list without being executed; generally, the head of the list is the thread that has been on the list the longest time, and the tail is the thread that has been on the list the shortest time

SCHED_RR

This policy shall be identical to the SCHED_FIFO policy with the additional condition that when the implementation detects that a running thread has been executing as a running thread for a time period of the length returned by the sched_rr_get_interval( ) function or longer, the thread shall become the tail of its thread list and the head of that thread list shall be removed and made a running thread.

SCHED_SPORADIC

The sporadic server policy is based primarily on two time parameters: the replenishment period and the available execution capacity. The replenishment period is given by the sched_ss_repl_period member of the sched_param structure. The available execution capacity is initialized to the value given by the sched_ss_init_budget member of the same parameter. The sporadic server policy is identical to the SCHED_FIFO policy with some additional conditions that cause the thread’s assigned priority to be switched between the values specified by the sched_priority and sched_ss_low_priority members of the sched_param structure.

POSIX Определяет группы опций и функций, из которых формируется понятие Real-Time. C этого ракурса Real-Time определяется возможностью настройки параметров планировщика из кода программы, возможностями диагностикии измерения временных параметров задач, наборами функций для синхронизации задач. За каждым термином кроется некоторый функционал ядра и режимы планирования.

Real-time

asynchronous, synchronized and prioritized I/O, shared memory objects, process and range based memory locking, semaphores, timers, real-time signals, message passing, process scheduling;

Advanced Real-time

clock selection, process CPU-time clocks, monotonic clock, timeouts, typed memory objects;

Real-time Threads

thread priority inheritance and protection, thread scheduling;

Advanced Real-time Threads

thread CPU-time clocks, thread sporadic server, spin locks and barriers.

Использованные здесь термины применяются в виде опеределений в заголовке <unistd.h>, который и определяет функционал ядра RTOS.

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

1. Mixed-Criticality/Иерархическое планирование - возможность разделения процессов на группы. Можно предложить выделить группы: hard real-time, soft real-time, background service.
2. RMS, EDF или RR -- методы планирования, методы выделения бюджета задаче. При этом в одном планировщике методы планирования могут сочетаться и применяться индивидуально к каждому процессу. RR рассматриваем, как частный случай при котором бюджет задания фиксирован.
3. Динамическое управление производительностью системы исходя из оценки загруженности системы.
4. Поддержка Deferable Server/Sporadic Server, сетевые интерфейсы (дарйверы) с ограниченной пропускной способностью. Предполагает поддержку очереди событий. О дин из видов события - начисление бюджета и повышение приоритета.
5. Поддержка Polling Server.

В настоящее время в нашей RTOS системе реализуется Mixed-Criticality с двумя группами на основе приоритета. hard real-time периодические процессы не могут прерываться по времени, по истечении бюджета задание переключается и переходит в группу с меньшим приоритетом, soft real-time -- использует RR - метод планирования с фиксированным интервалом переключения заданий. Экспериментально реализован метод планирования с выделением интервала переключения задач динамически на основе приоритета. Экспериментально поддержан механизм занижения приоритета по истечении бюджета. Поддержан механизм Deferred/Sporadic Service Экспериментально поддерживается EDF метод планирования. Политика EDF Реализуется с подменой FIFO очереди заданий на очередь с приоритетами. Задания могут исполняться в фоновом режиме background service (FIFO, Cooperative Miltitask), и в режиме опроса готовности (Polling services, FIFO, Cooperative), при этом весь поток background service участвует в процессе планирования, как единый процесс со своим приоритетом. Такое сочетание выведено опытным путем и применяется в условиях низкой загруженности системы. Динамическое управление производительностью выражено циклом WFE -- ожидание события в фоновом процессе. Поддержка сервисов в ядре задается через определения #define osFeature_* в конфигурационном файле системы <board.h>, <cmsis_os.h>(поддержка системных интерфейсов CMSIS RTOS) и набором опций _POSIX_* в файле <unistd.h>, который классифицирует поддержку системных интерфейсов POSIX.

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

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

Возможно ли сделать операционную систему 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, а не реализация. Реализация - приложится.