Пара вопросов о Win32 CriticalSections

Big Cheese · Post by **Big Cheese** » 12 Jan 2004 20:52

Недавно нашел в сети любопытный документ от Microsoft о том, как писать scalable server apps - http://www.mktgservice.com/developerclub/ppt/Tips%20and%20Tricks%20on%20Writing%20Scalable%20Applications,%20Part%201.pptВ нем, помимо всего прочего, приводится пример anti-convoy wrapper для critical section:

Code: Select all

ACQUIRE
retries = 0;
while( !TryEnterCriticalSection(&CritSec) ){
  if( retries++ < 100 ){
    if( retries % 10 ){         // DelayBetweenReferences
      for( i=0; i<Delay; i++);  // Delay = 1<<(cpus-1)
    } else {
      SwitchToThread();         //10 ctxsw max    
    }
    continue;
  }
  EnterCriticalSection(&CritSec);    
  break;
}

RELEASE
LeaveCriticalSection(&CritSec);

Возникает вопрос, чем данный код лучше, чем CriticalSection's spin count option, при условии (насколько я понимаю), что последний вариант призван решать все ту же проблему (lock convoys)?

Второй вопрос, ответ на который я не могу найти в документации, это собственно, стоимость объекта CriticalSection (Все, что я смог найти, сводится к тому, что Windows создает Event object, ассоциированный с critical section, при первом "столкновении", и этот Event object потребляет non-paged memory). К примеру, я хочу изваять bucket-level locking hash table, и планирую создавать critical section для каждого индекса хэш-таблицы. Является ли это допустимым с точки зрения масштабируемости? Если нет, какие могут быть альтернативы?

Заранее спасибо.

russianguy · Post by **russianguy** » 12 Jan 2004 22:07

Тхреад при ненулевом SpinCount выполняя EnterCriticalSection при захваченной CS сидит в цикле SpinCount раз,
надеясь что CS скоро "оттдадут".
Если нет уходит на ожидание с попутным созданием евента.

В приведенном фрагменте тхреад (кроме цикла ожидания) использует
SwitchToThread отдать свой квант времени, повышая шансы что CS "отдадут"

ИМХО: тем самым всеми силами пытаются предотовратить создание евента,
который жрет нонпагед поол, и который в свою очередь ресурс конечный

Big Cheese · Post by **Big Cheese** » 13 Jan 2004 01:31

russianguy wrote:Тхреад при ненулевом SpinCount выполняя EnterCriticalSection при захваченной CS сидит в цикле SpinCount раз,
надеясь что CS скоро "оттдадут".
Если нет уходит на ожидание с попутным созданием евента.

В приведенном фрагменте тхреад (кроме цикла ожидания) использует
SwitchToThread отдать свой квант времени, повышая шансы что CS "отдадут"

Вот этот SwitchToThread мне и непонятен в данном контексте (anti-convoy logic) - вроде как для надо минимизировать context switches (негативный эффект "конвоя"), а тут наоборот форсируется, пусть и урезаный, context switch...

tengiz · Post by **tengiz** » 13 Jan 2004 02:35

Конвой случается когда поток, в данный момент владеющий суперпопулярным ресурсом (ресурсом, который захватывается и освобождается много раз в течение кванта потока) вырабатывает свой квант и ОС его вытесняет. В результате другие потоки, конкурирующие за тот же ресурс, получить его не могут - ресурс занят и не может быть освобождён, так как владелец ресурса лишён ЦПУ. Поэтому другие потоки совершенно бесполезно покрутившись в спинлоке, впадают в спячку на событии, отдавая контекст другим таким же соискателям на ресурс.

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

Приведённый выше код при неудачной попытке захватить спинлок пытается избежать конвоя, явно отдавая ЦПУ другим потокам, а не ставя себя в линейную очередь за событием. А как только линейная очередь перестаёт соблюдаться, конвой быстро "рассасывается" – сначала идёт серия быстрых переключение контекста пока цикл не дойдёт до владельца ресурса. Зато после освобождения ресурса никто его немедленно не захватывает, поэтому текущий поток спокойно может повторно его захватить и период "всплеска" переключений между потоками прерывается до следующего неудачного момента, когда кто-то будет вытеснен в момент владения суперпопулярным ресурсом.

P.S. Идеальным вариантом было бы если бы в Win API имелось бы что-то типа TrySwitchToSpecificThread (ThreadId), что позволило бы отдать контекст напрямую владельцу ресурса, когда это возможно. При этом "рассасывание" конвоя могло бы происходить значительно быстрее.

Big Cheese · Post by **Big Cheese** » 13 Jan 2004 03:36

tengiz wrote:Конвой случается когда поток, в данный момент владеющий суперпопулярным ресурсом (ресурсом, который захватывается и освобождается много раз в течение кванта потока) вырабатывает свой квант и ОС его вытесняет. В результате другие потоки, конкурирующие за тот же ресурс, получить его не могут - ресурс занят и не может быть освобождён, так как владелец ресурса лишён ЦПУ. Поэтому другие потоки совершенно бесполезно покрутившись в спинлоке, впадают в спячку на событии, отдавая контекст другим таким же соискателям на ресурс.

Насколько я понимаю, в данном случае подразумевается, что время удержания ресурса больше чем или сопоставимо со временем "прокрутки" спинлока, иначе у потока, крутящегося на другом ЦПУ есть шанс дождаться и захватить ресурс. С учетом того, что при конвое время удержания ресурса довольно мало по определению, при грамотно подобранном spin count есть шанс этот конвой уменьшить, разве нет?

tengiz wrote:Приведённый выше код при неудачной попытке захватить спинлок пытается избежать конвоя, явно отдавая ЦПУ другим потокам, а не ставя себя в линейную очередь за событием.

К сожалению, в MSDN довольно невнятно (для меня) описано поведение планировщика в случае SwitchToThread. Вероятно, управление передается первому готовому к выполнению потоку, но что происходит с потоком, который добровольно отдал свой time slice - не понятно. Если он не ставится в конец очереди (что следует из вашего ответа), то что с ним происходит? Если под линейной очередью Вы имели в виду очередь потоков, ждущих на событии, то разве в Win32 ожидание реализовано в виде FIFO очереди?

tengiz · Post by **tengiz** » 13 Jan 2004 04:05

Big Cheese wrote:Насколько я понимаю, в данном случае подразумевается, что время удержания ресурса больше чем или сопоставимо со временем "прокрутки" спинлока, иначе у потока, крутящегося на другом ЦПУ есть шанс дождаться и захватить ресурс. С учетом того, что при конвое время удержания ресурса довольно мало по определению, при грамотно подобранном spin count есть шанс этот конвой уменьшить, разве нет?

Если я правильно понимаю Ваш вопрос - причина конвоя в том, код диспетчеризации не знает, что поток владеющий ресурсом лучше не вытеснять. А когда поток владеющий ресурсом вытеснен, он очевидно не не сможет его освободить пока он снова не получит ЦПУ. Понятно, что busy wait, в которые паларрельно / один за другим провалятся все остальные потоки, слабо зависит от соотношения времени удержания { которое в данном случае фактически равно времени, которое проходит, пока поток-владелец не получит снова ЦПУ и которое грубо ~ (SpinCount + время переключения контекста ) * количество потоков / количество ЦПУ } и SpinCount. Если, конечно не сделать SpinCount больше, чем это время. Что уж совсем бессмысленно.

tengiz wrote:К сожалению, в MSDN довольно невнятно (для меня) описано поведение планировщика в случае SwitchToThread. Вероятно, управление передается первому готовому к выполнению потоку, но что происходит с потоком, который добровольно отдал свой time slice - не понятно. Если он не ставится в конец очереди (что следует из вашего ответа), то что с ним происходит?

Это нигде не оговорено в публичной документации. Ставится он в конец очереди готовых или нет - неважно. Важно другое, что поток отдавший управление вызовом SwitchToThread не ставит себя в очередь ожидания события, тем самым устраняя причину конвоя.

Если под линейной очередью Вы имели в виду очередь потоков, ждущих на событии, то разве в Win32 ожидание реализовано в виде FIFO очереди?

Опять же - я не помню, чтобы в публичной документации эта деталь реализации явно оговаривалась. Но это тоже непринципиально (при условии, что очередь ведёт себя каким-то определённым образом, а не случайно) - главное, что если в очереди ожидающих освобождения кто-то есть, то вызов ResetEvent позволит немедленно захватить событие тому, кто первый стоит в очереди, поэтому текущий поток при повторной попытке захвата будет вытеснен и потеряет ЦПУ. Именно этого и старается избежать приведённый пример anti-convoy lock.

Big Cheese · Post by **Big Cheese** » 13 Jan 2004 05:02

Tengiz, спасибо Вам за желание учавствовать в ликбезе

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

Последний пункт (если он, конечно, имеет место быть) для меня неочевиден; поиск в MSDN нвавскидку ничего не дал... Буду признателен за подтверждение или опровержение. Не могли бы Вы также порекомендовать какие-нибудь ресурсы (книги/интернет), описывающие механизм работы наиболее важных с точки зрения прикладного программиста частей ядра Windows?

tengiz · Post by **tengiz** » 13 Jan 2004 05:25

Big Cheese wrote:- факт вытеснения потока, захватившего популярный ресурс, является вопросом времени и служит начальной фазой "конвоя"

Precisely.

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

Почти верно. Происходит это примерн так: поток 1 владеет ресурсом. В нашем случае случае это событие с автосбросом. В очереди на владение этим ресурсом стоит поток 2, соответственно этот поток не находится в очереди готовых к выполнениею. Поток 1 Вызывает SetEvent. Код ядра при этом проверяет очередь ожидания, если она непуста, то первый поток в очереди становится владельцем события и помещается в очередь готовых к выполнению потоков. Дальше возможны два варианта:

1. После возврата из SetEvent поток 1 продолжает работу и через небольшое время вызывает WaitForSingleObject для события. Код ядра видит, что событие уже занято, поэтому поток 1 помещается в очередь ожидания. Затем выбирается первый поток (поток 2) в очереди готовых к выполнению и происходит переключение контекста.

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

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

Из книг можно почитать Соломона с Руссиновичем. Подробнее чем они о внутренностях NT вроде больше никто не писал.

Big Cheese · Post by **Big Cheese** » 13 Jan 2004 07:11

tengiz wrote:Почти верно. Происходит это примерн так: поток 1 владеет ресурсом. В нашем случае случае это событие с автосбросом. В очереди на владение этим ресурсом стоит поток 2, соответственно этот поток не находится в очереди готовых к выполнениею. Поток 1 Вызывает SetEvent. Код ядра при этом проверяет очередь ожидания, если она непуста, то первый поток в очереди становится владельцем события и помещается в очередь готовых к выполнению потоков. Дальше возможны два варианта:

1. После возврата из SetEvent поток 1 продолжает работу и через небольшое время вызывает WaitForSingleObject для события. Код ядра видит, что событие уже занято, поэтому поток 1 помещается в очередь ожидания. Затем выбирается первый поток (поток 2) в очереди готовых к выполнению и происходит переключение контекста.

Tengiz, я полностью принимаю Ваше объяснение, за исключением одного момента (ну, занудный я человек!

): у Вас в рассуждении не учавствует spinlock, с которого, собственно, все и начиналось. Насколько мне видится, наличие spin count меняет картину в случае 1 (случай с потоками неравных приоритетов оставим, как слишком сложный) - тогда поток, отдавший ресурс и снова запрашивающий уже захваченный ресурс не отправляется планировщиком немедленно в очередь ожидания, а имеет шанс дождаться освобождения ресурса потоком 2, крутясь на spin lock'е на другом ЦПУ. Опять же, как мне видится, в момент "срыва в штопор", когда удерживающий ресурс поток вытеснен по истечению кванта, наличие spin count "тормозит" конвой на максимум SpinCount*nThreads*ContextSwitchTime/nCPU по сравнению с pure waitable CriticalSection. Когда управление снова попадает к потоку, "держащему" CS, повторяется все снова - при первом освобождении ресурса пробуждается поток 2 А т.к. spin count имеет смысл только при наличии нескольких CPU, поток 2 имеет хороший шанс немедленно начать исполняться на 2-м процессоре, и, т.к. время удержания CS очень мало, есть хорошая вероятность того, что на момент времени, когда поток 1 попытается снова захватить ресурс, ресурс уже будет свободен, или поток 1 "дотянется" до него, крутясь на спинлоке. Таким образом конвой худо-бедно разобъется.

Я не прав?

PS: За книгу - отдельное спасибо

tengiz · Post by **tengiz** » 13 Jan 2004 08:35

Big Cheese wrote:Я не прав?

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

Наличие нескольких процессоров и spincount разумеется меняет картину и при количестве потоков не превышающем количество процессоров получить конвой проблематично. Однако конвой - это проблема масштабируемости. Поэтому необходимые предпосылки для возникновения конвоя это: вытесняющая многозадачность, суперпопулярный ресурс и количество потоков, в разы превышающее количество доступных процессоров.

При этом чтобы резко уменьшить вероятность конвоя, spincount нужно сделать таким, чтобы busy wait был в несколько раз больше, чем время обработки данных, с которыми ассоциирован ресурс. Что в итоге получается пустым сжиганием циклов процессора. Это само по себе едва ли не хуже, чем конвой, который такая техника призвана предовратить.

Big Cheese · Post by **Big Cheese** » 13 Jan 2004 20:35

tengiz wrote:Случай, который мы подробно разобрали - один процессор, больше одного потока и где spincount не имеет никакого смысла - это конвой в чистом виде. Это наиболее простой для понимания сценарий возникновения конвоя.

Да, это так, и я Вам очень признателен за интересное обсуждение.

tengiz wrote:Наличие нескольких процессоров и spincount разумеется меняет картину и при количестве потоков не превышающем количество процессоров получить конвой проблематично. Однако конвой - это проблема масштабируемости. Поэтому необходимые предпосылки для возникновения конвоя это: вытесняющая многозадачность, суперпопулярный ресурс и количество потоков, в разы превышающее количество доступных процессоров.
При этом чтобы резко уменьшить вероятность конвоя, spincount нужно сделать таким, чтобы busy wait был в несколько раз больше, чем время обработки данных, с которыми ассоциирован ресурс. Что в итоге получается пустым сжиганием циклов процессора. Это само по себе едва ли не хуже, чем конвой, который такая техника призвана предовратить.

Пожалуй, тут мы (Вы) подвели обсуждение к ответу на изначально интересовавший меня вопрос, который и спровоцировал всю дискуссию.

Любопытно, что у меня и, насколько я могу судить, не только у меня сложилось мнение о spinlock'ed CS, как о способе сделать high contention lock масштабируемым. Что при внимательном рассмотрении оказывается не совсем соответствующим действительности. Хотя, с другой стороны - если количество потоков в системе в разы превышает количество процессоров, то такая система, видимо, сама по себе плохо масштабируется.

Michael Popov · Post by **Michael Popov** » 13 Jan 2004 21:00

Вопрос из зала ...

Нельзя ли привести пример такого "суперпопулярного" ресурса ? Желательно в контексте, когда проблема не может быть решена изменениями алгоритма и/или архитектуры и требуется использование методов, приведенных в начальном посте.

Big Cheese · Post by **Big Cheese** » 13 Jan 2004 23:16

Michael Popov wrote:Вопрос из зала ...

Из того, с чем приходилось сталкиваться, навскидку: есть некий кэш объектов, имеющий иерархическую организацию, причем этот кэш плохо или совсем не разбивается на части. Все потоки в приложении первым делом лезут в этот кэш, иногда что-то добавляется/удаляется, чаще просто делается lookup. Были попытки сделать multi-granular locking - все равно получилось дешевле иметь один глобальный lock.. Другой пример - memory allocator, хотя тут, конечно, можно несколько распараллелить доступ.

Еще часто бывает, что достается в наследство (или получается в результате долгой и плодотворной работы

) система, хронически страдающая с такими hotspots, а начальство стоит на позиции, что "мы не Microsoft, мы не можем себе позволить взять, и перетрясти архитектуру", а кушать хоца, сл-но, релизы выпускать надо, и в каждом релизе радовать кастомеров новыми фичами, и улучшенной производительностью... Ладно, что-то меня понесло

I think you know what am I talking about :wink:

Michael Popov · Post by **Michael Popov** » 13 Jan 2004 23:45

А слабо иметь копию кэша для каждого потока ? Или 2-уровневый кэш: для каждого потока свой "маленький" кэш и один большой общий. Количество обращений к общему ресурсу сокращается, и он перестает быть "суперпопулярным".

tengiz · Post by **tengiz** » 13 Jan 2004 23:59

Michael Popov wrote:Нельзя ли привести пример такого "суперпопулярного" ресурса?

Классический пример из СУБД - буфер журнал транзакций, куда последовательно и очень быстро сыпятся много коротких записей от многих активных транзакций в OLTP БД. Счёт идёт на десятки и даже сотни тысяч записей в секунду.

tengiz · Post by **tengiz** » 14 Jan 2004 00:09

Big Cheese wrote:Любопытно, что у меня и, насколько я могу судить, не только у меня сложилось мнение о spinlock'ed CS, как о способе сделать high contention lock масштабируемым. Что при внимательном рассмотрении оказывается не совсем соответствующим действительности. Хотя, с другой стороны - если количество потоков в системе в разы превышает количество процессоров, то такая система, видимо, сама по себе плохо масштабируется.

Проблема масштабируемости критической секции ведь не сводится только к конвоям? В случаях, когда доступ к критической секции имеет нерегулярный характер или когда за кририческую секцию конкурирует много потоков, но потокам она не нужна много раз в течение кванта, а также когда время, на которое захватывается CS очень маленькое (скажем, порядка или меньше времени переключения контекста), то правильно подобранный spincount может заметно снизить CPU utillization как раз в правильных случаях, когда количество потоков не очень сильно превышает количество процессоров.

Big Cheese · Post by **Big Cheese** » 14 Jan 2004 00:13

Michael Popov wrote:1)А слабо иметь копию кэша для каждого потока ? 2)Или 2-уровневый кэш: для каждого потока свой "маленький" кэш и один большой общий. Количество обращений к общему ресурсу сокращается, и он перестает быть "суперпопулярным".

1)Во-первых, надо будет поддерживать синхронность кэшей, что может свести на нет все преимущество. Во-вторых, такое решение неоптимально по памяти, и чревато возникновением проблем с увеличением объема данных...
2) В принципе, выглядит разумно, но сильно зависит от контекста, т.е. что, собственно, эти данные из себя представляют, и насколько эффективно и легко можно организовать их partitioning - "привязать" к потоку / поток - к ЦПУ и т.д. Мне, лично, это удается далеко не всегда...

Big Cheese · Post by **Big Cheese** » 14 Jan 2004 00:17

tengiz wrote:Проблема масштабируемости критической секции ведь не сводится только к конвоям? В случаях, когда доступ к критической секции имеет нерегулярный характер или когда за кририческую секцию конкурирует много потоков, но потокам она не нужна много раз в течение кванта, а также когда время, на которое захватывается CS очень маленькое (скажем, порядка или меньше времени переключения контекста), то правильно подобранный spincount может заметно снизить CPU utillization как раз в правильных случаях, когда количество потоков не очень сильно превышает количество процессоров.

Да, все так. Просто, для меня это было эээ... несколько не очевидно :oops:

.

Michael Popov · Post by **Michael Popov** » 14 Jan 2004 02:49

Big Cheese wrote:1)Во-первых, надо будет поддерживать синхронность кэшей, что может свести на нет все преимущество. Во-вторых, такое решение неоптимально по памяти, и чревато возникновением проблем с увеличением объема данных...
2) В принципе, выглядит разумно, но сильно зависит от контекста, т.е. что, собственно, эти данные из себя представляют, и насколько эффективно и легко можно организовать их partitioning - "привязать" к потоку / поток - к ЦПУ и т.д. Мне, лично, это удается далеко не всегда...

1) Не надо :umnik1:

Независимые кэши - это легко и красиво

2) Если потоки делают одну и ту же работу, то можно смело предоставлять каждому из них вести свой независимый кэш. И не надо ничего никуда привязывать.

А насчет неэффективного использования памяти : 64-бит эра на носу, да и производителям железа надо дать возможность заработать свой кусок хлеба с маслом