Возможный косяк в boost::mutex
От: ioni Россия  
Дата: 13.04.11 10:53
Оценка: :)
Рассмотрим реализацию boost::mutex (последняя версия)

            bool timed_lock(::boost::system_time const& wait_until)
            {
(1)                if(!win32::interlocked_bit_test_and_set(&active_count,lock_flag_bit))
                {
                    return true;
                }
                long old_count=active_count;
(2)                for(;;)
                {
                    long const new_count=(old_count&lock_flag_value)?(old_count+1):(old_count|lock_flag_value);
                    long const current=BOOST_INTERLOCKED_COMPARE_EXCHANGE(&active_count,new_count,old_count);
                    if(current==old_count)
                    {
                        break;
                    }
                    old_count=current;
                }

                if(old_count&lock_flag_value)
                {
                    bool lock_acquired=false;
                    void* const sem=get_event();

                    do
                    {
(3)                        if(win32::WaitForSingleObject(sem,::boost::detail::get_milliseconds_until(wait_until))!=0)
                        {
                            BOOST_INTERLOCKED_DECREMENT(&active_count);
                            return false;
                        }
                        old_count&=~lock_flag_value;
                        old_count|=event_set_flag_value;
                        for(;;)
                        {
                            long const new_count=((old_count&lock_flag_value)?old_count:((old_count-1)|lock_flag_value))&~event_set_flag_value;
                            long const current=BOOST_INTERLOCKED_COMPARE_EXCHANGE(&active_count,new_count,old_count);
                            if(current==old_count)
                            {
                                break;
                            }
                            old_count=current;
                        }
                        lock_acquired=!(old_count&lock_flag_value);
                    }
                    while(!lock_acquired);
                }
                return true;
            }

            void unlock()
            {
                long const offset=lock_flag_value;
(4)                long const old_count=BOOST_INTERLOCKED_EXCHANGE_ADD(&active_count,lock_flag_value);
                if(!(old_count&event_set_flag_value) && (old_count>offset))
                {
(5)                    if(!win32::interlocked_bit_test_and_set(&active_count,event_set_flag_bit))
                    {
                        win32::SetEvent(get_event());
                    }
                }
            }


рассмотрим такую ситуацию
Имеем три потока с приоритетами Low, Medium, High
в начальном состоянии поток Low захватил mutex в точке 1 потому что он первый,
далее начинает работать стартует поток Medium система передает ему управление так как он имеет более высокий приоритет
потом начинает работать поток High и пытается захватить mutex, так как mutex уже захвачен доходит до точки 3 и ждет
так как поток High ждет, управление передается потоку Medium и пока он не отработает не произойдет инверсии приоритета для
потока Low и поток High не получит управления.
Вот такая дыра обнаружилась
Re: Возможный косяк в boost::mutex
От: fdn721  
Дата: 14.04.11 06:55
Оценка: +1
Здравствуйте, ioni, Вы писали:

I>Рассмотрим реализацию boost::mutex (последняя версия)

I>
I>            bool timed_lock(::boost::system_time const& wait_until)
I>            {
I>(1)                if(!win32::interlocked_bit_test_and_set(&active_count,lock_flag_bit))
I>                {
I>                    return true;
I>                }
I>                long old_count=active_count;
I>(2)                for(;;)
I>                {
I>                    long const new_count=(old_count&lock_flag_value)?(old_count+1):(old_count|lock_flag_value);
I>                    long const current=BOOST_INTERLOCKED_COMPARE_EXCHANGE(&active_count,new_count,old_count);
I>                    if(current==old_count)
I>                    {
I>                        break;
I>                    }
I>                    old_count=current;
I>                }

I>                if(old_count&lock_flag_value)
I>                {
I>                    bool lock_acquired=false;
I>                    void* const sem=get_event();

I>                    do
I>                    {
I>(3)                        if(win32::WaitForSingleObject(sem,::boost::detail::get_milliseconds_until(wait_until))!=0)
I>                        {
I>                            BOOST_INTERLOCKED_DECREMENT(&active_count);
I>                            return false;
I>                        }
I>                        old_count&=~lock_flag_value;
I>                        old_count|=event_set_flag_value;
I>                        for(;;)
I>                        {
I>                            long const new_count=((old_count&lock_flag_value)?old_count:((old_count-1)|lock_flag_value))&~event_set_flag_value;
I>                            long const current=BOOST_INTERLOCKED_COMPARE_EXCHANGE(&active_count,new_count,old_count);
I>                            if(current==old_count)
I>                            {
I>                                break;
I>                            }
I>                            old_count=current;
I>                        }
I>                        lock_acquired=!(old_count&lock_flag_value);
I>                    }
I>                    while(!lock_acquired);
I>                }
I>                return true;
I>            }

I>            void unlock()
I>            {
I>                long const offset=lock_flag_value;
I>(4)                long const old_count=BOOST_INTERLOCKED_EXCHANGE_ADD(&active_count,lock_flag_value);
I>                if(!(old_count&event_set_flag_value) && (old_count>offset))
I>                {
I>(5)                    if(!win32::interlocked_bit_test_and_set(&active_count,event_set_flag_bit))
I>                    {
I>                        win32::SetEvent(get_event());
I>                    }
I>                }
I>            }
I>


I>рассмотрим такую ситуацию
I>Имеем три потока с приоритетами Low, Medium, High
I>в начальном состоянии поток Low захватил mutex в точке 1 потому что он первый,
I>далее начинает работать стартует поток Medium система передает ему управление так как он имеет более высокий приоритет
I>потом начинает работать поток High и пытается захватить mutex, так как mutex уже захвачен доходит до точки 3 и ждет
I>так как поток High ждет, управление передается потоку Medium и пока он не отработает не произойдет инверсии приоритета для
I>потока Low и поток High не получит управления.
I>Вот такая дыра обнаружилась

Что-то у вас какое-то мутное представление о приоритете потоков.
Re[2]: Возможный косяк в boost::mutex
От: ioni Россия  
Дата: 14.04.11 10:07
Оценка:
Здравствуйте, fdn721, Вы писали:

I>>[/ccode]

I>>рассмотрим такую ситуацию
I>>Имеем три потока с приоритетами Low, Medium, High
I>>в начальном состоянии поток Low захватил mutex в точке 1 потому что он первый,
I>>далее начинает работать стартует поток Medium система передает ему управление так как он имеет более высокий приоритет
I>>потом начинает работать поток High и пытается захватить mutex, так как mutex уже захвачен доходит до точки 3 и ждет
I>>так как поток High ждет, управление передается потоку Medium и пока он не отработает не произойдет инверсии приоритета для
I>>потока Low и поток High не получит управления.
I>>Вот такая дыра обнаружилась

F>Что-то у вас какое-то мутное представление о приоритете потоков.

Вполне нормальное, кстати такое поведение успешно наблюдается на kernel диаграмме под wince
когда управление передается не высоко приоритетному потоку который ждет а какому то другому потоку
впрочем что вам кажется не так в моих рассуждениях?
Re[2]: Возможный косяк в boost::mutex
От: Mr.Delphist  
Дата: 14.04.11 10:23
Оценка:
Здравствуйте, fdn721, Вы писали:

I>>рассмотрим такую ситуацию
I>>Имеем три потока с приоритетами Low, Medium, High
I>>в начальном состоянии поток Low захватил mutex в точке 1 потому что он первый,
I>>далее начинает работать стартует поток Medium система передает ему управление так как он имеет более высокий приоритет
I>>потом начинает работать поток High и пытается захватить mutex, так как mutex уже захвачен доходит до точки 3 и ждет
I>>так как поток High ждет, управление передается потоку Medium и пока он не отработает не произойдет инверсии приоритета для
I>>потока Low и поток High не получит управления.
I>>Вот такая дыра обнаружилась

F>Что-то у вас какое-то мутное представление о приоритете потоков.

Ну, при конкретно этой тройке особого вреда не будет, кроме тормозов. А вот появление еще одного потока с high-приоритетом да, с неплохой вероятностью накроет этот пикничок медным тазом. И надолго (ежели не навсегда).
Встретившись пару раз с такой засадой (WinXP, если чего), вскоре перестал маяться дурью задавать приоритеты руками. Профит!
Re: Возможный косяк в boost::mutex
От: quodum  
Дата: 15.04.11 06:46
Оценка:
Здравствуйте, ioni, Вы писали:


I>рассмотрим такую ситуацию
I>Имеем три потока с приоритетами Low, Medium, High
I>в начальном состоянии поток Low захватил mutex в точке 1 потому что он первый,
I>далее начинает работать стартует поток Medium система передает ему управление так как он имеет более высокий приоритет
I>потом начинает работать поток High и пытается захватить mutex, так как mutex уже захвачен доходит до точки 3 и ждет
I>так как поток High ждет, управление передается потоку Medium и пока он не отработает не произойдет инверсии приоритета для
I>потока Low и поток High не получит управления.

Описанная ситуация как раз и называется инверсией приоритетов, потому что поток с низшим приоритетом (Medium) блокирует поток с высшим приоритетом (High). Разные ОС выходят из неё по-разному. Канонический метод -- поднять приоритет Low до уровня High, пока он не отпустит мутекс. Винда примерно это и делает, только с добавкой недетерминизма (пруф).
Re[2]: Возможный косяк в boost::mutex
От: ioni Россия  
Дата: 15.04.11 08:37
Оценка:
Здравствуйте, quodum, Вы писали:

Q>Здравствуйте, ioni, Вы писали:

I>>рассмотрим такую ситуацию
I>>Имеем три потока с приоритетами Low, Medium, High
I>>в начальном состоянии поток Low захватил mutex в точке 1 потому что он первый,
I>>далее начинает работать стартует поток Medium система передает ему управление так как он имеет более высокий приоритет
I>>потом начинает работать поток High и пытается захватить mutex, так как mutex уже захвачен доходит до точки 3 и ждет
I>>так как поток High ждет, управление передается потоку Medium и пока он не отработает не произойдет инверсии приоритета для
I>>потока Low и поток High не получит управления.

Q>Описанная ситуация как раз и называется инверсией приоритетов, потому что поток с низшим приоритетом (Medium) блокирует поток с высшим приоритетом (High). Разные ОС выходят из неё по-разному. Канонический метод -- поднять приоритет Low до уровня High, пока он не отпустит мутекс. Винда примерно это и делает, только с добавкой недетерминизма (пруф).

Именно, если ядро системы видит что высокоприоритетный поток ждет ( Wait функции ) планировщик поднимет приоритет потоку Low ( инверсия )
что бы этот поток быстро освободил блокировку.
В текущей реализации boost::mutex( начиная с версии 1.36 ) этого не произойдет по причине того что система не состоянии определить какой поток держит ресурс.
В результате поток High висит, что категорически не верно.
Re[3]: Возможный косяк в boost::mutex
От: quodum  
Дата: 15.04.11 18:12
Оценка:
Здравствуйте, ioni, Вы писали:

I>В текущей реализации boost::mutex( начиная с версии 1.36 ) этого не произойдет по причине того что система не состоянии определить какой поток держит ресурс.
I>В результате поток High висит, что категорически не верно.

А ведь правда! Не обратил внимания, что там event.

Интересно, насколько велик импакт. Надо будет освежить детали виндового планировщика, как только доберусь до литературы. Если мне склероз не изменяет, планировщик рано или поздно заметит, что низкоприоритетный поток простаивает, и выдаст ему priority boost, так что совсем уж катастрофы, как в системах с более жёстким планировщиком, не случится.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.