История изменений

Я смог таки запилить lock-free планировщик - http://pastebin.com/HirFnhMb. Правда он немного странный. Я использую ленивое усыпление нитей. То есть усыпление по факту приводит лишь к выставлению спец. флага. А планировщик при попытке переключиться на процесс с таким флагом удаляет его из очереди и идёт к следующему. Если нить пробудят до того, как до неё дойдёт очередь, то никаких операций со списком не потребуется.

Прогнал некоторые тесты. Вот результаты (всё время в наносекундах, график построен по первому блоку тестов):

https://pp.vk.me/c627616/v627616975/650cd/ofCdRyvTK-o.jpg

Процессор - Core i5-4210U (4 ядра). 1 поток (настоящий, линуксовый) 10 миллионов раз вызывает schedulerNextThread. 3 потока (тоже настоящих) в бесконечном цикле (точнее пока не закончит выполнение главный поток) генерируют 2 случайных числа. Первое - номер потока (не настоящего, а моего), второе - действие (отправить в сон или наоборот пробудить). И выполняют это действие с указанным потоком, замеряя время выполнения действия. При этом если поток уже был в нужном состоянии или заблокирован другой операцией (если кто-то уже начал добавлять/удалять поток, то функция выходит ни с чем - кто первый начал, тот и прав), то её время выполнения не учитывается в общей статистике. Ах да, процесс запускаю от root и с nice -19.

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

На мой взгляд условия теста более жёсткие, чем бывает на микроконтроллерах в реальных задачах, так что для грубой оценки сверху вполне подходят (весьма сомнительно, что в штатных условиях работы, может быть результат хуже). А ещё ведь микроконтроллер одноядерный и уровень вложенности вызовов функций suspend/resume весьма ограничен, так что потери на CAS должны быть значительно меньше. Resume должен выполняться быстрее, чем FindNext.

Получается, что среднее время работы планировщика на Core i5 - 50 наносекунд (вряд ли кто-то будет запускать на МК сотни процессов, да ещё и непрерывно будить и усыплять их, спящие потоки ресурсов кроме памяти не жрут, ибо удалены из очереди). Есть идеи, как можно очень грубо перевести это в ситуацию с микроконтроллером? Во сколько раз мой Core i5 круче какого-нибудь STM32F103?

P.S.: Проверял корректность работы планировщика на большем числе итераций (вплоть до 10 миллиардов) с различными уровнями оптимизации (O0, O2 и O3). Ни при каких обстоятельствах не происходит разрушения данных или зависания. А функция замера времени отбрасывает оверхед от вызова функций получения timestamp.

Я смог таки запилить lock-free планировщик - http://pastebin.com/HirFnhMb. Правда он немного странный. Я использую ленивое усыпление нитей. То есть усыпление по факту приводит лишь к выставлению спец. флага. А планировщик при попытке переключиться на процесс с таким флагом удаляет его из очереди и идёт к следующему. Если нить пробудят до того, как до неё дойдёт очередь, то никаких операций со списком не потребуется.

Прогнал некоторые тесты. Вот результаты (всё время в наносекундах, график построен по первому блоку тестов):

https://pp.vk.me/c627616/v627616975/650cd/ofCdRyvTK-o.jpg

Процессор - Core i5-4210U (4 ядра). 1 поток (настоящий, линуксовый) 10 миллионов раз вызывает schedulerNextThread. 3 потока (тоже настоящих) в бесконечном цикле (точнее пока не закончит выполнение главный поток) генерируют 2 случайных числа. Первое - номер потока (не настоящего, а моего), второе - действие (отправить в сон или наоборот пробудить). И выполняют это действие с указанным потоком, замеряя время выполнения действия. При этом если поток уже был в нужном состоянии или заблокирован другой операцией (если кто-то уже начал добавлять/удалять поток, то функция выходит ни с чем - кто первый начал, тот и прав), то её время выполнения не учитывается в общей статистике. Ах да, процесс запускаю от root и с nice -19.

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

На мой взгляд условия теста более жёсткие, чем бывает на микроконтроллерах в реальных задачах, так что для грубой оценки сверху вполне подходят (весьма сомнительно, что в штатных условиях работы, может быть результат хуже). А ещё ведь микроконтроллер одноядерный и уровень вложенности вызовов функций suspend/resume весьма ограничен, так что потери на CAS должны быть значительно меньше. Resume должен выполняться быстрее, чем FindNext.

Получается, что среднее время работы планировщика на Core i5 - 50 наносекунд (вряд ли кто-то будет запускать на МК сотни процессов, да ещё и непрерывно будить и усыплять их, спящие потоки ресурсов кроме памяти не жрут, ибо удалены из очереди). Есть идеи, как можно очень грубо перевести это в ситуацию с микроконтроллером? Во сколько раз мой Core i5 круче какого-нибудь STM32F103?

P.S.: Проверял корректность работы планировщика на большем числе итераций (вплоть до 10 миллиардов) с различными уровнями оптимизации (O0, O2 и O3). Ни при каких обстоятельствах не происходит разрушения данных или зависания.

Я смог таки запилить lock-free планировщик - http://pastebin.com/HirFnhMb. Правда он немного странный. Я использую ленивое усыпление нитей. То есть усыпление по факту приводит лишь к выставлению спец. флага. А планировщик при попытке переключиться на процесс с таким флагом удаляет его из очереди и идёт к следующему. Если нить пробудят до того, как до неё дойдёт очередь, то никаких операций со списком не потребуется.

Прогнал некоторые тесты. Вот результаты (всё время в наносекундах, график построен по первому блоку тестов):

https://pp.vk.me/c627616/v627616975/650cd/ofCdRyvTK-o.jpg

Процессор - Core i5-4210U (4 ядра). 1 поток (настоящий, линуксовый) 10 миллионов раз вызывает schedulerNextThread. 3 потока (тоже настоящих) в бесконечном цикле (точнее пока не закончит выполнение главный поток) генерируют 2 случайных числа. Первое - номер потока (не настоящего, а моего), второе - действие (отправить в сон или наоборот пробудить). И выполняют это действие с указанным потоком, замеряя время выполнения действия. При этом если поток уже был в нужном состоянии или заблокирован другой операцией (если кто-то уже начал добавлять/удалять поток, то функция выходит ни с чем - кто первый начал, тот и прав), то её время выполнения не учитывается в общей статистике. Ах да, процесс запускаю от root и с nice -19.

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

На мой взгляд условия теста более жёсткие, чем бывает на микроконтроллерах в реальных задачах, так что для грубой оценки сверху вполне подходят (весьма сомнительно, что в штатных условиях работы, может быть результат хуже). А ещё ведь микроконтроллер одноядерный и уровень вложенности вызовов функций suspend/resume весьма ограничен, так что потери на CAS должны быть значительно меньше. Resume должен выполняться быстрее, чем FindNext.

Получается, что среднее время работы планировщика на Core i5 - 50 наносекунд (вряд ли кто-то будет запускать на МК сотни процессов, да ещё и непрерывно будить и усыплять их, спящие потоки ресурсов кроме памяти не жрут, ибо удалены из очереди). Есть идеи, как можно очень грубо перевести это в ситуацию с микроконтроллером? Во сколько раз мой Core i5 круче какого-нибудь STM32F103?