Jump to content

    
jcxz

Лёгкие мьютексы. Возможно ли?

Recommended Posts

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

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

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

Share this post


Link to post
Share on other sites

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

 

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

 

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

Edited by amaora

Share this post


Link to post
Share on other sites
37 минут назад, amaora сказал:

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

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

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

Share this post


Link to post
Share on other sites
11.01.2022 в 12:51, mantech сказал:

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

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

 

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

Share this post


Link to post
Share on other sites
4 часа назад, dxp сказал:

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

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

Share this post


Link to post
Share on other sites
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: Это всё мне известно было на момент создания темы. Мне хочется правильного решения! Такого как мьютексы и должны работать по уму - не повышая приоритет выше необходимого. Поэтому просил описания лёгких алгоритмов реализации правильных мьютексов. Или ссылки на оное. А костыли мы и сами ваять умеем и всегда успеем.

Share this post


Link to post
Share on other sites
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: Это всё мне известно было на момент создания темы. Мне хочется правильного решения! Такого как мьютексы и должны работать по уму - не повышая приоритет выше необходимого. Поэтому просил описания лёгких алгоритмов реализации правильных мьютексов. Или ссылки на оное. А костыли мы и сами ваять умеем и всегда успеем.

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

 

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

Share this post


Link to post
Share on other sites
30 минут назад, dxp сказал:

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

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

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

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

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

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

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

 

 

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

Share this post


Link to post
Share on other sites
14 часов назад, gridinp сказал:

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

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

 

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

Share this post


Link to post
Share on other sites

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

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

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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.