Какой стандарт лучше выбрать. Выбор сделать не могу, однако хочу писать программки для контроллеров и для ПК на одном языке.
Я тут часто употребляю слово "семафор" -- в моей реализации это атомарный счетчик, который не блокирует поток. Семафоры я рассматриваю, как строительные блоки для более сложных объектов синхронизации. В других реализациях под семафорами могут пониматься весьма громоздкие конструкции завязанные на ядро и поток владельца, не следует путать.
Из POSIX можно уйти в C11, но нет нормального пути к RTOS. Я бы хотел обратно. Мне нравится стиль CMSIS. В своих программах для контроллеров я использую сигналы, потоки, и семафоры (osSignal, osThread, osMutex, osSeamaphore). Эта таблица не отражает того, что мне нужно.
В API операционной системы CMSIS RTOS для реализации обработки данных по событиям не хватает некоего системного объекта типа "идентификатор события", чтобы синхронизировать и запускать процессы. События должны быть доступны по уникальному идентификатору. Синхронизироваться используя API CMSIS RTOS я умею по сигналам (своего потока, которые живут в локальной-памяти-потока) и по семафорам/они же мьютексы. Про сигналы, стандарты ничего толком не знают. В С11 и POSIX сигналы нельзя использовать на нужды треда, они относятся к функционалу задачи, но не потока.
Чтобы запускать/синхронизировать процессы по завершению других процессов, мне не хватает функции osThreadJoin(), в реализации которой нужно уметь ожидать готовности по идентификатору события готовности потока. Причем идентификатор события такого в системе не предусмотрен. Объект "событие готовности", можно реализовать на базе osEvent, на атомарной логической переменной.
С11 и POSIX знают про условные переменные, которые у в CMSIS RTOS не определены. От микрософта мы отказались, уже очень давно, с тех пор как стали использовать glib на виндах. Но в микрософте есть своя фича, которая в той же концепции живет и в OpenCL -- это ожидание списка событий. Не мьютексов с условной переменной в комплекте, а события - флажка, без вспомогательных наростов.
Мне предстоит выбрать один из двух интерфейсов. Почему один?! Один вроде можно выразить через другой: или события, или условные переменные. Я на минуту задумался, может мне не стоило связываться с CMSIS RTOS API, вот ведь набор C11, который вообще достаточен для реализации операционной системы. Есть всего одна причина, по которой я придерживаюсь CMSIS: там минимизируется использование динамических данных, и это невероятно круто.
Реализация идентификаторов событий
На одно событие хочу использовать не более двух бит. Один бит на динамическое распределение событий, один на само событие. Событие - это однобитовая переменная, над которой определены атомарные операции чтения, сигнализации и сброса. Сигнализация оживляет множество тредов, которые ожидают событие. Тред может быть заблокирован событием. Если один тред сигнализирует о событии, это ничего не вызывает. Можно при очередной проверки условий в планировщике, сбросить ожидание если указанное событие перешло в состояние "готово". Для этого в недрах системы надо хранить состояния (флаги) всех событий, один бит на событие.
Реализация условных переменных
На самом деле от события нужен только идентификатор, которым может быть адрес структуры. Если нет тела события и не требуется проверять флаг события, интересует только функция ожидания, то проверить множество событий, можно только проверив весь список потоков в состоянии ожидания, выделить те, которые ждут условную переменную.
Условные переменные - это просто адрес, без тела структуры, адрес - это и есть уникальный идентификатор, который мы ожидаем. С тем же успехом можно ожидать любой уникальный идентификатор. Но вот по этому идентификатору должна быть возможность получить "тело", а доступ к телу по идентификатору -- это уже прикладная задача.
Реализация ожидания списка событий на условных переменных
Тут я вижу сложность реализации ожидания множества событий. Нельзя ожидать сразу несколько условных переменных, система может отследить один идентификатор, чтобы не перетрудиться. Если приложение работает со списком условий, то между проверкой элементов списка может произойти подтверждение события, ждать будет некого, для этого и нужна взаимная блокировка между процессом ожидания и процессом генерации событий, мьютекс. Что в этом мне не нравится. Мы получим очень тормозную систему. При большом количестве потоков, ожидающих событие, надо проверять многочисленные длинные списки, на каждое событие. На каждое событие блокируется множество потоков, в том числе раздающий-сервисный одним мьютексом. Надо, чтобы раздающий поток не блокировался. Нельзя использовать мьютексы со стороны системы, поэтому использование условных переменных в драйверах не допускается, должно быть что-то другое, что используется для сигнализации готовности, счетчик-семафора-флаг готовности, например.
Ожидание множества объектов
Интересный вариант предлагает Windows API, там можно ждать несколько объектов синхронизации, для этого на уровне системы должна поддерживаться типизация объектов типа handle. Типы указателей на ресурсы -- это лишние данные в памяти. Но хочется отметить что тип данных может быть один для всех объектов, если их проверять нужно одинаковым способом. Например, мьютексы и семафоры оказываются одним типом с точки зрения планировщика. Планировщик выполняет операцию проверки счетчика на ноль, если счетчик не ноль, то происходит вычитание единицы и выход из состояния ожидания. Эта проверка применима также для ожидания освобождения элемента памяти, при распределении памяти из пула, она же применима для ожидания очереди. Ожидание множества объектов можно реализовать, как ожидание атомарных переменных типа счетчик-семафор (в т.ч бинарный типа мьютекс), производится проверка счетчика на ненулевое значение.
Реализация условной переменной на семафоре
Почему бы и нет. Условную переменную, семафор, можно проверять на состояние. Можно ожидать штатным методом. Можно выставлять в системе. Чтобы раздать у.п. всем ожидающим, достаточно накинуть большое число в значение счетчика. Чтобы просигнализировать одному потоку, надо накинуть единицу. Таким образом, можно реализовать синхронизацию по множеству объектов синхронизации. Это достаточно эффективный способ, потому что он не замедляет работу системы, не вызывает циклов и дополнительных проверок в планировщике.
Отклонение от цели недопустимо
Моя цель -- предложить более менее понятный эффективный механизм синхронизации потоков, который бы позволял запускать потоки по событиям. События двух типов: пользовательские и события завершения потоков, есть события блокировки доступа (семафоры). Для этого нужен механизм обработки очереди потоков и проверки списков событий встроенный в ядро, в планировщик системы.
Критика
Реализация должна быть экономной: минимум обработки, минимум ресурсов. Какую-то выгоду надо получить в концепции статических данных, без динамического распределения. Всегда когда не хватает ресурсов, происходит ожидание потока. Очень важный параметр экономии - в контроллере просто нет достаточно ресурсов, чтобы запустить множество бездействующих потоков, ожидающий поток не должен запускаться. Проверка флагов-событий, по которым запускается очередной поток должен производится из ядра системы. Вместе с тем, я думаю, как выгружать из памяти состояние стека, например, задача спит по расписанию.
Реализация событий -- это раздача уникальных идентификаторов. Условные переменные требуют операций над списком задач, надо проверить все ожидания и разрешить исполнение задачам, которые ждут исполнения. В этом смысле мне больше нравятся события, но стандарты предлагают использовать условные переменные. Что же выбрать? Что же выбрать?
ПС Описал функцию ожидания списка событий WaitForEvents(), на базе условных переменных. Стало немного легче с пониманием. Используется одна условная переменная и один мьютекс на всех. Открыл для себя истину, если события не надо убивать, то распределение идентификаторов (событий или любых других) -- это счетчик на атомарной переменной. Выделил интересный объект -- распределение бит (флагов) из массива, этот же алгоритм годится для распределения из массива Pool, и как основа для распределения памяти в нарезке Slice.
Источники
[CMSIS] CMSIS - Cortex Microcontroller Software Interface Standard
[C11] N1570, последний черновик стандарта C1X
[POSIX] IEEE Std 1003.1™, 2013 Edition
На самом деле эти заметки я писал в 2016 году, сейчас можно сравнивать с POSIX '16 года. Мне эти заметки нужны, чтобы думать над операционкой, я снова вношу изменения и снова упираюсь в условные переменные. За отчетное время появися стандарт, CMSIS RTOS2, но нам туда не надо, я не хочу на него переходить. И не предлагаю сравнения.
Я тут часто употребляю слово "семафор" -- в моей реализации это атомарный счетчик, который не блокирует поток. Семафоры я рассматриваю, как строительные блоки для более сложных объектов синхронизации. В других реализациях под семафорами могут пониматься весьма громоздкие конструкции завязанные на ядро и поток владельца, не следует путать.
| CMSIS RTOS 1.02 | C11 threads ISO/IEC 9899:2011 | POSIX IEEE Std 1003.1, 2013 | |
|---|---|---|---|
| Типы данных | |||
| - | cond_t | pthread_cond_t | Условная переменная, для условных блокировок |
| - | - | pthread_rwlock_t | блокировка чтения записи |
| osMutexId | mtx_t | pthread_mutex_t | Мьютекс, бинарный семафор |
| osThreadId | thrd_t* | pthread_t * | Идентификатор треда, ссылка на тред |
| uint32_t | struct timespec | struct timespec | Временные интервалы и штампы времени |
| void(*)(void*) | int (*)(void*) | void *(*)(void*) | Функция треда |
| osMutexDelete | mtx_destroy | pthread_mutex_destroy | |
| osMutexCreate | mtx_init | pthread_mutex_init | Создание/инициализация мьютекса |
| osMutexWait | mtx_lock | pthread_mutex_lock | Блокировка |
| osMutexWait | mtx_timedlock | pthread_mutex_timedlock | Ожидание мьютекса с таймаутом |
| --* | mtx_trylock | pthread_mutex_trylock | |
| osMutexRelease | mtx_unlock | pthread_mutex_unlock | |
| --* | call_once | pthread_once | Однократное исполнение |
| osThreadCreate | thrd_create | pthread_create | Создание треда |
| osThreadGetId | thrd_current | pthread_self | Идентификатор треда |
| - | thrd_detach | pthread_detach | Отцепить тред от родителя |
| - | thrd_equal | pthread_equal | Сравнение |
| osThreadTerminate | thrd_exit | pthread_exit | Выход из треда |
| --* | thrd_join | pthread_join | Ожидать завершения треда |
| osWait | thrd_sleep | Ожидать сигнала | |
| osThreadYield | thrd_yield | pthread_yield | Запросить переключение задач |
| - | cnd_broadcast | pthread_cond_broadcast | Оживить всех |
| - | cnd_destroy | pthread_cond_destroy | Удалить переменную |
| - | cnd_init | pthread_cond_init | Инициализировать |
| - | cnd_signal | pthread_cond_signal | Сигнализировать |
| - | cnd_timedwait | pthread_cond_timedwait | Ожидать с таймаутом |
| - | cnd_wait | pthread_cond_wait | Ожидать переменную |
В API операционной системы CMSIS RTOS для реализации обработки данных по событиям не хватает некоего системного объекта типа "идентификатор события", чтобы синхронизировать и запускать процессы. События должны быть доступны по уникальному идентификатору. Синхронизироваться используя API CMSIS RTOS я умею по сигналам (своего потока, которые живут в локальной-памяти-потока) и по семафорам/они же мьютексы. Про сигналы, стандарты ничего толком не знают. В С11 и POSIX сигналы нельзя использовать на нужды треда, они относятся к функционалу задачи, но не потока.
Чтобы запускать/синхронизировать процессы по завершению других процессов, мне не хватает функции osThreadJoin(), в реализации которой нужно уметь ожидать готовности по идентификатору события готовности потока. Причем идентификатор события такого в системе не предусмотрен. Объект "событие готовности", можно реализовать на базе osEvent, на атомарной логической переменной.
С11 и POSIX знают про условные переменные, которые у в CMSIS RTOS не определены. От микрософта мы отказались, уже очень давно, с тех пор как стали использовать glib на виндах. Но в микрософте есть своя фича, которая в той же концепции живет и в OpenCL -- это ожидание списка событий. Не мьютексов с условной переменной в комплекте, а события - флажка, без вспомогательных наростов.
Мне предстоит выбрать один из двух интерфейсов. Почему один?! Один вроде можно выразить через другой: или события, или условные переменные. Я на минуту задумался, может мне не стоило связываться с CMSIS RTOS API, вот ведь набор C11, который вообще достаточен для реализации операционной системы. Есть всего одна причина, по которой я придерживаюсь CMSIS: там минимизируется использование динамических данных, и это невероятно круто.
Реализация идентификаторов событий
На одно событие хочу использовать не более двух бит. Один бит на динамическое распределение событий, один на само событие. Событие - это однобитовая переменная, над которой определены атомарные операции чтения, сигнализации и сброса. Сигнализация оживляет множество тредов, которые ожидают событие. Тред может быть заблокирован событием. Если один тред сигнализирует о событии, это ничего не вызывает. Можно при очередной проверки условий в планировщике, сбросить ожидание если указанное событие перешло в состояние "готово". Для этого в недрах системы надо хранить состояния (флаги) всех событий, один бит на событие.
Реализация условных переменных
На самом деле от события нужен только идентификатор, которым может быть адрес структуры. Если нет тела события и не требуется проверять флаг события, интересует только функция ожидания, то проверить множество событий, можно только проверив весь список потоков в состоянии ожидания, выделить те, которые ждут условную переменную.
Условные переменные - это просто адрес, без тела структуры, адрес - это и есть уникальный идентификатор, который мы ожидаем. С тем же успехом можно ожидать любой уникальный идентификатор. Но вот по этому идентификатору должна быть возможность получить "тело", а доступ к телу по идентификатору -- это уже прикладная задача.
Реализация ожидания списка событий на условных переменных
Тут я вижу сложность реализации ожидания множества событий. Нельзя ожидать сразу несколько условных переменных, система может отследить один идентификатор, чтобы не перетрудиться. Если приложение работает со списком условий, то между проверкой элементов списка может произойти подтверждение события, ждать будет некого, для этого и нужна взаимная блокировка между процессом ожидания и процессом генерации событий, мьютекс. Что в этом мне не нравится. Мы получим очень тормозную систему. При большом количестве потоков, ожидающих событие, надо проверять многочисленные длинные списки, на каждое событие. На каждое событие блокируется множество потоков, в том числе раздающий-сервисный одним мьютексом. Надо, чтобы раздающий поток не блокировался. Нельзя использовать мьютексы со стороны системы, поэтому использование условных переменных в драйверах не допускается, должно быть что-то другое, что используется для сигнализации готовности, счетчик-семафора-флаг готовности, например.
Ожидание множества объектов
Интересный вариант предлагает Windows API, там можно ждать несколько объектов синхронизации, для этого на уровне системы должна поддерживаться типизация объектов типа handle. Типы указателей на ресурсы -- это лишние данные в памяти. Но хочется отметить что тип данных может быть один для всех объектов, если их проверять нужно одинаковым способом. Например, мьютексы и семафоры оказываются одним типом с точки зрения планировщика. Планировщик выполняет операцию проверки счетчика на ноль, если счетчик не ноль, то происходит вычитание единицы и выход из состояния ожидания. Эта проверка применима также для ожидания освобождения элемента памяти, при распределении памяти из пула, она же применима для ожидания очереди. Ожидание множества объектов можно реализовать, как ожидание атомарных переменных типа счетчик-семафор (в т.ч бинарный типа мьютекс), производится проверка счетчика на ненулевое значение.
Реализация условной переменной на семафоре
Почему бы и нет. Условную переменную, семафор, можно проверять на состояние. Можно ожидать штатным методом. Можно выставлять в системе. Чтобы раздать у.п. всем ожидающим, достаточно накинуть большое число в значение счетчика. Чтобы просигнализировать одному потоку, надо накинуть единицу. Таким образом, можно реализовать синхронизацию по множеству объектов синхронизации. Это достаточно эффективный способ, потому что он не замедляет работу системы, не вызывает циклов и дополнительных проверок в планировщике.
Отклонение от цели недопустимо
Моя цель -- предложить более менее понятный эффективный механизм синхронизации потоков, который бы позволял запускать потоки по событиям. События двух типов: пользовательские и события завершения потоков, есть события блокировки доступа (семафоры). Для этого нужен механизм обработки очереди потоков и проверки списков событий встроенный в ядро, в планировщик системы.
Критика
Реализация должна быть экономной: минимум обработки, минимум ресурсов. Какую-то выгоду надо получить в концепции статических данных, без динамического распределения. Всегда когда не хватает ресурсов, происходит ожидание потока. Очень важный параметр экономии - в контроллере просто нет достаточно ресурсов, чтобы запустить множество бездействующих потоков, ожидающий поток не должен запускаться. Проверка флагов-событий, по которым запускается очередной поток должен производится из ядра системы. Вместе с тем, я думаю, как выгружать из памяти состояние стека, например, задача спит по расписанию.
Реализация событий -- это раздача уникальных идентификаторов. Условные переменные требуют операций над списком задач, надо проверить все ожидания и разрешить исполнение задачам, которые ждут исполнения. В этом смысле мне больше нравятся события, но стандарты предлагают использовать условные переменные. Что же выбрать? Что же выбрать?
ПС Описал функцию ожидания списка событий WaitForEvents(), на базе условных переменных. Стало немного легче с пониманием. Используется одна условная переменная и один мьютекс на всех. Открыл для себя истину, если события не надо убивать, то распределение идентификаторов (событий или любых других) -- это счетчик на атомарной переменной. Выделил интересный объект -- распределение бит (флагов) из массива, этот же алгоритм годится для распределения из массива Pool, и как основа для распределения памяти в нарезке Slice.
Источники
[CMSIS] CMSIS - Cortex Microcontroller Software Interface Standard
[C11] N1570, последний черновик стандарта C1X
[POSIX] IEEE Std 1003.1™, 2013 Edition
На самом деле эти заметки я писал в 2016 году, сейчас можно сравнивать с POSIX '16 года. Мне эти заметки нужны, чтобы думать над операционкой, я снова вношу изменения и снова упираюсь в условные переменные. За отчетное время появися стандарт, CMSIS RTOS2, но нам туда не надо, я не хочу на него переходить. И не предлагаю сравнения.
Комментариев нет:
Отправить комментарий