[jcxz 243]

5 минут назад, mantech сказал:

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

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

[amaora 25]

А для чего по спискам бегать? Определить максимальный приоритет задач в очереди на захват мьютекса? То есть, нужен быстрый алгоритм нахождения максимума из некоторого множества для которого производятся операции добавления/удаления элементов?

 

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

 

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

Изменено 11 января, 2022 пользователем amaora

[jcxz 243]

37 минут назад, amaora сказал:

А для чего по спискам бегать? Определить максимальный приоритет задач в очереди на захват мьютекса? То есть, нужен быстрый алгоритм нахождения максимума из некоторого множества для которого производятся операции добавления/удаления элементов?

Посмотрите реализацию в любой ОС. Я не будут тут излагать вам словами весь алгоритм.

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

[dxp 65]

11.01.2022 в 12:51, mantech сказал:

Ну а если №8 уже занял устройство? №3 по любому будет ждать, хоть у него самый высший приоритет будет. Поэтому лучше метод каждому устройству свой поток. Медленное устройство прекрасно может работать по принципу мейлбокса, обслуживая фоновые запросы от неск. потоков и не блокируя их.

Что значит "занял устройство"? Смысл ведь вынести работу с общим ресурсом (в том числе и если это пусть устройство) в отдельный поток с нужным приоритетом. Вот пусть этот поток и "занимает устройство". Выглядит так: поток 8 хочет что-то сделать с устройством, сам к нему не лезет, а просто кидает в очередь, которую слушает поток 1, задание (адрес объекта). Да, поток 3 будет ждать по-любому, но это будет точно так же и в случае с инверсией приоритетов. Смысл инверсии приоритетов не в том, чтобы поток 3 мог отобрать доступ у потока 8 (это по логике задачи невозможно и не нужно), а в том, чтобы, например, поток 5 не вытеснил поток 8 на непонятное время, тормозя тем самым более приоритетный поток 3. Именно эту задачу решает инверсия приоритетов: поток 3 даёт временно поработать потоку 8 на своём приоритете, чтобы никакой поток с более низким, чем 3, приоритетом не мог вмешаться, чтобы модель приоритетного вытеснения (всегда работает наиболее приоритетный поток из готовых к выполнению) соблюдалась.

 

В любом случае имеет место схема: "высокоприоритетный поток выполняет какую-то работу низкоприоритетного". В случае инверсии приоритетов высокоприоритетный пускает поработать низкоприоритетный "на своём рабочем месте", а в случае очереди заданий низкоприоритетный "попросил" другой высокоприоритетный поток сделать эту работу. Какой способ лучше, определяется "ценой вопроса". Если потоки дорогие и тяжёлые, а колбасить потороха оси на этом фоне необременительно, что инверсия приоритетов вполне. Если потоки дёшевы, то наоборот. В случае простых, лёгких RTOS очевидно второй вариант в выигрыше. По коду там несколько строк. Работает это очень быстро. Код прозрачный. Легко переносится из проекта в проект (у меня в любом проекте есть всегда фоновый процесс, который и выполняет всякие такие несрочные, но затратные вычислительно задания, а в некоторых есть и foreground процесс - как раз для срочных дел). Это никакие не костыли, а очень простой, красивый и эффективный паттерн проектирования. Как раз инверсия приоритетов с перетряхиванием в потрохах RTOS кучи всего, не имеющего непосредственного отношения к рассматриваемому контексту "на всякий случай" - чтобы обеспечить корректность во всех кейсах, и выглядит натуральными костылями. 

[mantech 53]

4 часа назад, dxp сказал:

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

Так это и есть мейлбокс, я так и делаю..

[jcxz 243]

7 часов назад, dxp сказал:

Выглядит так: поток 8 хочет что-то сделать с устройством, сам к нему не лезет, а просто кидает в очередь, которую слушает поток 1, задание (адрес объекта). Да, поток 3 будет ждать по-любому, но это будет точно так же и в случае с инверсией приоритетов. Смысл инверсии приоритетов не в том, чтобы поток 3 мог отобрать доступ у потока 8 (это по логике задачи невозможно и не нужно), а в том, чтобы, например, поток 5 не вытеснил поток 8 на непонятное время, тормозя тем самым более приоритетный поток 3.

Примерно то же самое сделано в uCOS-II (я ещё в самом 1-м посте на неё ссылался). Только там не отдельный поток для этого создаётся, а повышается приоритет владеющего мьютексом потока до некоторого зафиксированного за данным мьютексом приоритета. Это решение лучше, чем создавать отдельный поток, со своим стеком и прочим. И к тому же такое повышение в uCOS-II происходит только при попытке захвата занятого мьютекса задачей, более приоритетной, чем владеющая. Когда занятый мьютекс никакой другой поток не пытается захватить или пытаются захватывать только менее приоритетные задачи, чем задача-владелец, то и повышения не происходит. В вашем же варианте, выполнение кода защищённого мьютексом, происходит всегда на самом высшем приоритете - приоритете выделенного потока (это дополнительный минус, кроме лишнего стека).

Ещё недостатки вашего метода (по сравнению с uCOS-II):

в каждом проекте программисту надо всю эту кухню (с отдельным потоком и передачей туда каких-то функций) прописывать отдельно (с uCOS-II - надо только зарезервировать приоритет, остальное сделает ОС);

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

 

Но даже у варианта решения uCOS-II тоже есть очевидные минусы (уже писал выше): Если скажем имеется такое распределение приоритетов (приоритет падает сверху-вниз):

0 - мьютекс (высший приоритет);

1 - задача1, могущая захватывать мьютекс;

2 - задача2, никогда не пытающаяся захватывать мьютекс;

3 - задача3, могущая захватывать мьютекс;

4 - задача4, могущая захватывать мьютекс (низший приоритет).

Если например мьютекс захватила задача4, а потом его пытается захватить задача3 (и встаёт на ожидание), то приоритет повышается до приоритета=0. А значит получается, что задача3 в этот момент имеет приоритет выше чем у задачи2 и задачи1, что неправильно. У Вашего метода также имеется этот недостаток.

 

PS: Это всё мне известно было на момент создания темы. Мне хочется правильного решения! Такого как мьютексы и должны работать по уму - не повышая приоритет выше необходимого. Поэтому просил описания лёгких алгоритмов реализации правильных мьютексов. Или ссылки на оное. А костыли мы и сами ваять умеем и всегда успеем.

[dxp 65]

4 минуты назад, jcxz сказал:

Примерно то же самое сделано в uCOS-II (я ещё в самом 1-м посте на неё ссылался). Только там не отдельный поток для этого создаётся, а повышается приоритет владеющего мьютексом потока до некоторого зафиксированного за данным мьютексом приоритета. Это решение лучше, чем создавать отдельный поток, со своим стеком и прочим. И к тому же такое повышение в uCOS-II происходит только при попытке захвата занятого мьютекса задачей, более приоритетной, чем владеющая. Когда занятый мьютекс никакой другой поток не пытается захватить или пытаются захватывать только менее приоритетные задачи, чем задача-владелец, то и повышения не происходит. В вашем же варианте, выполнение кода защищённого мьютексом, происходит всегда на самом высшем приоритете - приоритете выделенного потока (это дополнительный минус, кроме лишнего стека).

Ещё недостатки вашего метода (по сравнению с uCOS-II):

в каждом проекте программисту надо всю эту кухню (с отдельным потоком и передачей туда каких-то функций) прописывать отдельно (с uCOS-II - надо только зарезервировать приоритет, остальное сделает ОС);

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

 

Но даже у варианта решения uCOS-II тоже есть очевидные минусы (уже писал выше): Если скажем имеется такое распределение приоритетов (приоритет падает сверху-вниз):

0 - мьютекс (высший приоритет);

1 - задача1, могущая захватывать мьютекс;

2 - задача2, никогда не пытающаяся захватывать мьютекс;

3 - задача3, могущая захватывать мьютекс;

4 - задача4, могущая захватывать мьютекс (низший приоритет).

Если например мьютекс захватила задача4, а потом его пытается захватить задача3 (и встаёт на ожидание), то приоритет повышается до приоритета=0. А значит получается, что задача3 в этот момент имеет приоритет выше чем у задачи2 и задачи1, что неправильно. У Вашего метода также имеется этот недостаток.

 

PS: Это всё мне известно было на момент создания темы. Мне хочется правильного решения! Такого как мьютексы и должны работать по уму - не повышая приоритет выше необходимого. Поэтому просил описания лёгких алгоритмов реализации правильных мьютексов. Или ссылки на оное. А костыли мы и сами ваять умеем и всегда успеем.

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

 

Никогда не пользовался игнор-списком, но в данном случае сделаю исключение.

[jcxz 243]

30 минут назад, dxp сказал:

Все ваши выступления тут как обычно на тему "какой я крутой, продвинутый, прокачанный, опытный и всё знающий,

Я вроде нигде ничего подобного ни о себе не о вас лично не говорил...   Говорил только о предложенном вами методе. Вы разницу улавливаете? Или для вас любая критика - посягательство на вашу корону? Тогда извините что потревожил ваше ЧСВ.  

И на личности я не переходил в отличие от вас. А обсуждал только алгоритмы решения.

30 минут назад, dxp сказал:

мне не нравится этот подход потому-то и потому-то

Я вообще-то это и сказал. И обосновал. На наезжая на вас лично.

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

 

 

PS: Если ребёнок нарисовал корявую картинку и кто-то ему сказал, что можно нарисовать лучше и показал как, то ребёнок может обидеться, заплакать и убежать. Но чтобы взрослые люди так поступали, когда аргументированно критикуют их решения. Детский сад какой-то...  

[gridinp 3]

Посмотрите статью, в интернете можно найти, может она поможет "Non-Blocking Synchronization Between Real-Time and Non-Real-Time Applications"

 

[jcxz 243]

14 часов назад, gridinp сказал:

Посмотрите статью, в интернете можно найти, может она поможет "Non-Blocking Synchronization Between Real-Time and Non-Real-Time Applications"

Ещё раз: Вопрос не о том, какие существуют методы синхронизации. Вопрос конкретно о мьютексах.

 

PS: Какие существуют методы, в том числе и неблокирующие, мне прекрасно известно.

[jcxz 243]

Вобщем просмотрел внимательнее реализацию мьютексов в uCOS-II (заявлено, что она там работает согласно CPP(ceiling priority protocol)).

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

Для uCOS-III заявлено, что мьютексы в ней работают согласно PIP (priority inversion protocol). Это значительно более тяжёлое решение.