Здравствуйте, Roman Odaisky, Вы писали:
RO>Ingo Molnár считает, что «user-space spinlocks are broken beyond words for anything but perhaps SCHED_FIFO tasks».
RO>А почему?
цитато:
SCHED_FIFO: планировщик FIFO (First In-First Out)
Алгоритм SCHED_FIFO можно использовать только со значениями статического приоритета, большими нуля. Это означает, что если процесс с алгоритмом SCHED_FIFO готов к работе, то он сразу запустится, а все обычные процессы с алгоритмом SCHED_OTHER будут приостановлены. SCHED_FIFO — это простой алгоритм без квантования времени. Процессы, работающие согласно алгоритму SCHED_FIFO подчиняются следующим правилам: процесс с алгоритмом SCHED_FIFO, приостановленный другим процессом с большим приоритетом, останется в начале очереди процессов с равным приоритетом, и его исполнение будет продолжено сразу после того, как закончатся процессы с большими приоритетами. Когда процесс с алгоритмом SCHED_FIFO готов к работе, он помещается в конец очереди процессов с тем же приоритетом. Вызов функции sched_setscheduler или sched_setparam , который посылается процессом под номером pid с алгоритмом SCHED_FIFO приведет к тому, что процесс будет перемещен в конец очереди процессов с тем же приоритетом. Процесс, вызывающий sched_yield, также будет помещен в конец списка. Других способов перемещения процесса с алгоритмом SCHED_FIFO в очереди процессов с одинаковыми статическим приоритетом не существует. Процесс с алгоритмом SCHED_FIFO работает до тех пор, пока не будет заблокирован запросом на ввод/вывод, приостановлен процессом с большим статическим приоритетом или не вызовет sched_yield.
конец цитаты.
видимо наблюдается тот же эффект, что и при раундробин, который я предположил в топике несколько ниже.
короче если на спинлоке крутится процесс с высоким приоритетом или вот этот фифо, то
— в случае с раунд робин, при переключении процесса захватившего спинлок(квант времени кончился), меньшего приоритета, чем ожидающий, ожидающий заблокирует внутренний и не выпустит таким образом из спинлока, чтобы войти туда самому.
— с фифо все еще хуже. фифо просто работает как монополист, пока сам себя не прервет или его не прервет процесс с более высоким приоритетом. таким образом низкоприоритетный внутри охраняемого участка будет блокирован. грубо говоря на спинлок такой процесс придет монополистом, и если спинлок уже занят, то просто зациклится. чтобы этого не было, нужно ему приостанвливать самого себя. хотя бы иногда. даже приостановка этого фифо более высокоприоритетным, не работает, поскольку фифо запустится сразу как только высокприоритетный остановится.
Здравствуйте, Roman Odaisky, Вы писали:
RO>Ingo Molnár считает, что «user-space spinlocks are broken beyond words for anything but perhaps SCHED_FIFO tasks». RO>А почему?
Это специфично для Linux. При применении спин-локов ОС ничего не знает о зависимостях о потоках — "кто-то кого-то ждёт", "кто-то кого-то задерживает". Для ОС все потоки выглядят просто как "работающие". Соотв. ОС в такой ситуации может делать очень плохой шедулинг.
В Windows есть замечательный вызов SwitchToThread(), который явно говорит шедулеру ОС "я не делаю никакой полезной работы, просто жду какой-то другой поток". Соотв. поток делающий такой вызов неминуемо будет попадать в конец очереди готовых потоков, даже если он высокоприоритетный.
Здравствуйте, remark, Вы писали:
RO>>Ingo Molnár считает, что «user-space spinlocks are broken beyond words for anything but perhaps SCHED_FIFO tasks». RO>>А почему?
R>Это специфично для Linux. При применении спин-локов ОС ничего не знает о зависимостях о потоках — "кто-то кого-то ждёт", "кто-то кого-то задерживает". Для ОС все потоки выглядят просто как "работающие". Соотв. ОС в такой ситуации может делать очень плохой шедулинг.
R>В Windows есть замечательный вызов SwitchToThread(), который явно говорит шедулеру ОС "я не делаю никакой полезной работы, просто жду какой-то другой поток". Соотв. поток делающий такой вызов неминуемо будет попадать в конец очереди готовых потоков, даже если он высокоприоритетный.
Что-то я не совсем понял. SwitchToThread — это аналог позиксового sched_yield(2), верно? Я взял цитату с http://kerneltrap.org/Linux/Using_sched_yield_Improperly, и самое первое предложение там, опять же цитируя Инго, звучит так: «Really, I have never seen a single mainstream application where the use of sched_yield() was the right choice».
sched_yield/SwitchToThread/boost::this_thread::yield как раз ничего вразумительного планировщику не говорят («я чего-то жду, но чего, не скажу»). Уж если инициировать системный вызов и смену контекста, так почему бы сразу не указать ожидаемое событие?
Но речь о другом: спинлоки, как кажется сразу, могли бы быть полезны на многопроцессорных системах, где вроде бы дешевле дождаться освобождения другим процессором ресурса еще в течение этого кванта времени, чем отдать весь остаток своего кванта и потом еще ждать своей очереди. Ingo Molnár считает иначе, но не приводит обоснований. Каковы могут быть причины?
Я где-то видел статью, автор которой, в контексте программирования на WinAPI, утверждал, что каждый вызов Sleep вызывает у него самые худшие подозрения, и что он исправил много багов в многопоточных системах, попросту переписывая все увиденные упоминания Sleep. Проблема здесь та же: поток чего-то ждет, но программеру лень указать точно, чего именно, вот он и усыпляет поток, наивно надеясь, что утро вечера мудренее.
Здравствуйте, Roman Odaisky, Вы писали:
RO>Ingo Molnár считает, что «user-space spinlocks are broken beyond words for anything but perhaps SCHED_FIFO tasks». RO>А почему?
Так как легко могут вызвать "узкие места" в загруженный системах — если система переключит поток, который держит спинлок, то другие потоки на этом спинлоке будут бесполезно способствовать глобальному потеплению. А в незагруженных один фиг проще системные мьютексы использовать.
Здравствуйте, Roman Odaisky, Вы писали:
RO>Здравствуйте, remark, Вы писали:
RO>>>Ingo Molnár считает, что «user-space spinlocks are broken beyond words for anything but perhaps SCHED_FIFO tasks». RO>>>А почему?
R>>Это специфично для Linux. При применении спин-локов ОС ничего не знает о зависимостях о потоках — "кто-то кого-то ждёт", "кто-то кого-то задерживает". Для ОС все потоки выглядят просто как "работающие". Соотв. ОС в такой ситуации может делать очень плохой шедулинг.
R>>В Windows есть замечательный вызов SwitchToThread(), который явно говорит шедулеру ОС "я не делаю никакой полезной работы, просто жду какой-то другой поток". Соотв. поток делающий такой вызов неминуемо будет попадать в конец очереди готовых потоков, даже если он высокоприоритетный.
RO>Что-то я не совсем понял. SwitchToThread — это аналог позиксового sched_yield(2), верно? Я взял цитату с http://kerneltrap.org/Linux/Using_sched_yield_Improperly, и самое первое предложение там, опять же цитируя Инго, звучит так: «Really, I have never seen a single mainstream application where the use of sched_yield() was the right choice».
угу. это yield и есть.
но правильно говорит товарищ Инго. если в прикладном коде возникают yield — это говорит о вмешательстве прикладника в процесс реализации установленной политики многозадачности шедулером.
RO>sched_yield/SwitchToThread/boost::this_thread::yield как раз ничего вразумительного планировщику не говорят («я чего-то жду, но чего, не скажу»). Уж если инициировать системный вызов и смену контекста, так почему бы сразу не указать ожидаемое событие?
видимо ремарк имел ввиду самостоятельную реализацию спинлока.
какой кстати спинлок вы имеете ввиду? просто крутимся в цикле пока не...чего-то там произойдет?
если так, то я вам ответил, что вы заблокируете систему в случае FIFO треда на спинлоке.
RO>Но речь о другом: спинлоки, как кажется сразу, могли бы быть полезны на многопроцессорных системах, где вроде бы дешевле дождаться освобождения другим процессором ресурса еще в течение этого кванта времени, чем отдать весь остаток своего кванта и потом еще ждать своей очереди. Ingo Molnár считает иначе, но не приводит обоснований. Каковы могут быть причины?
опять двадцать пять.
какие требования у вас к вашему спинлоку? сколько вы готовы на нем ждать?
а если другой процессор не освободит ваш ресурс еще минуту?
вы даете цитату не пойми откуда, и обсуждаете вне всяких уточнений.
RO>Я где-то видел статью, автор которой, в контексте программирования на WinAPI, утверждал, что каждый вызов Sleep вызывает у него самые худшие подозрения, и что он исправил много багов в многопоточных системах, попросту переписывая все увиденные упоминания Sleep. Проблема здесь та же: поток чего-то ждет, но программеру лень указать точно, чего именно, вот он и усыпляет поток, наивно надеясь, что утро вечера мудренее.
слип оправдан только если тред сам генерит себе события. типа сам себе таймер. например сборщик мусора, уведомитель какой-нить и проч. или вы чудовищно делаете свой собственный спинлок или чот-от вроде того, крутитесь в цикле и чтобы не грузить проц на все 100 все таки иногда уходите в слип. но это крайний моветон.
RO>И всё же спинлоки: чем они провинились?
тем что не освобождают проц во время ожидания.
Здравствуйте, merk, Вы писали:
M>- в случае с раунд робин, при переключении процесса захватившего спинлок(квант времени кончился), меньшего приоритета, чем ожидающий, ожидающий заблокирует внутренний и не выпустит таким образом из спинлока, чтобы войти туда самому.
Поэтому в Windows есть динамическое повышение приороитетов.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, Roman Odaisky, Вы писали:
RO>Я где-то видел статью, автор которой, в контексте программирования на WinAPI, утверждал, что каждый вызов Sleep вызывает у него самые худшие подозрения, и что он исправил много багов в многопоточных системах, попросту переписывая все увиденные упоминания Sleep. Проблема здесь та же: поток чего-то ждет, но программеру лень указать точно, чего именно, вот он и усыпляет поток, наивно надеясь, что утро вечера мудренее.
В Windiows, если тред чего-то ждёт, он просто изымается из списка готовых к выполнению (WaitFor*). А Sleep используется, что бы приостановить выполнение (например, что бы taskmanager не показывал 100% загрузку CPU). Его не используют для синхронизации тредов, т.к. это трата ресурсов CPU.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, remark, Вы писали:
R>В Windows есть замечательный вызов SwitchToThread(), который явно говорит шедулеру ОС "я не делаю никакой полезной работы, просто жду какой-то другой поток".
Это уже домыслы.
The SwitchToThread function causes the calling thread to yield execution to another thread that is ready to run on the current processor
R> Соотв. поток делающий такой вызов неминуемо будет попадать в конец очереди готовых потоков, даже если он высокоприоритетный.
Помещается он в начало очереди (которая реализована как массив — LIST_ENTRY KiDispatcherReadyListHead[MAXIMUM_PRIORITY]; )
The yield of execution is in effect for up to one thread-scheduling time slice. After that, the operating system reschedules execution for the yielding thread. The rescheduling is determined by the priority of the yielding thread and the status of other threads that are available to run.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, Cyberax, Вы писали:
C>Спинлок+мьютекс — это уже более интересно.
Ага, это CRITICAL_SECTION в Win32. Голые спинлоки там никогда не используются.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, gear nuke, Вы писали:
GN>Помещается он в начало очереди (которая реализована как массив — LIST_ENTRY KiDispatcherReadyListHead[MAXIMUM_PRIORITY]; ) GN>
The yield of execution is in effect for up to one thread-scheduling time slice. After that, the operating system reschedules execution for the yielding thread. The rescheduling is determined by the priority of the yielding thread and the status of other threads that are available to run.
В Линуксе это не так. Новый планировщик помещает поток после sched_yield в произвольное место дерева процессов, так что оно ждать может доооолго.
Здравствуйте, gear nuke, Вы писали:
C>>Спинлок+мьютекс — это уже более интересно. GN>Ага, это CRITICAL_SECTION в Win32. Голые спинлоки там никогда не используются.
Системные крит. секции — это не то, там до требуется вызов функции, да ещё и в DLLке. Спинлок на чистом С++ зато может жутко заинлайнится до пары ассемблерных команд, что очень важно на fastpath'ах.
Здравствуйте, Cyberax, Вы писали:
C>Системные крит. секции — это не то, там до требуется вызов функции, да ещё и в DLLке.
Какая разница, где физически размещены ассемблерные команды?
C> Спинлок на чистом С++ зато может жутко заинлайнится до пары ассемблерных команд, что очень важно на fastpath'ах.
До пары, кстати, не рекомендуется на современных камнях:
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, gear nuke, Вы писали:
GN>>Помещается он в начало очереди (которая реализована как массив — LIST_ENTRY KiDispatcherReadyListHead[MAXIMUM_PRIORITY]; ) GN>>
The yield of execution is in effect for up to one thread-scheduling time slice. After that, the operating system reschedules execution for the yielding thread. The rescheduling is determined by the priority of the yielding thread and the status of other threads that are available to run.
C>В Линуксе это не так. Новый планировщик помещает поток после sched_yield в произвольное место дерева процессов, так что оно ждать может доооолго.
не произвольное. а то, что ему полагается в зависмости от его политики его шедулинга — FIFO, RR, OTHER.
треды со статическим приоритетом больше нуля будут конкурировать только с тредами своего и большего приоритета, вытесняя — меньшего приоритета.
цитато
Scheduling Policies
The scheduler is the kernel part that decides which runnable process will be executed by the CPU next. The Linux scheduler offers three different scheduling policies, one for normal processes and two for real-time applications. A static priority value sched_priority is assigned to each process and this value can be changed only via system calls. Conceptually, the scheduler maintains a list of runnable processes for each possible sched_priority value, and sched_priority can have a value in the range 0 to 99. In order to determine the process that runs next, the Linux scheduler looks for the non-empty list with the highest static priority and takes the process at the head of this list. The scheduling policy determines for each process, where it will be inserted into the list of processes with equal static priority and how it will move inside this list.
SCHED_OTHER is the default universal time-sharing scheduler policy used by most processes, SCHED_FIFO and SCHED_RR are intended for special time-critical applications that need precise control over the way in which runnable processes are selected for execution. Processes scheduled with SCHED_OTHER must be assigned the static priority 0, processes scheduled under SCHED_FIFO or SCHED_RR can have a static priority in the range 1 to 99. Only processes with superuser privileges can get a static priority higher than 0 and can therefore be scheduled under SCHED_FIFO or SCHED_RR. The system calls sched_get_priority_min and sched_get_priority_max can be used to to find out the valid priority range for a scheduling policy in a portable way on all POSIX.1b conforming systems.
All scheduling is preemptive: If a process with a higher static priority gets ready to run, the current process will be preempted and returned into its wait list. The scheduling policy only determines the ordering within the list of runnable processes with equal static priority.
Здравствуйте, merk, Вы писали:
M>не произвольное. а то, что ему полагается в зависмости от его политики его шедулинга — FIFO, RR, OTHER. M>треды со статическим приоритетом больше нуля будут конкурировать только с тредами своего и большего приоритета, вытесняя — меньшего приоритета.
Это понятно, при sched_yield приоритет учитывается. Однако, среди потоков одинакового приоритета механизм действия sched_yield поменялся.
Здравствуйте, gear nuke, Вы писали:
C>>Системные крит. секции — это не то, там до требуется вызов функции, да ещё и в DLLке. GN>Какая разница, где физически размещены ассемблерные команды?
Вызов в DLL нельзя за-inline-ить, да ещё он идёт и через косвенную таблицу.
C>> Спинлок на чистом С++ зато может жутко заинлайнится до пары ассемблерных команд, что очень важно на fastpath'ах. GN>До пары, кстати, не рекомендуется на современных камнях:
Ну не до "пары", а до нескольких штук.
GN>Чистый С++ не справится.
Естественно. Нужен inline-ассемблер или ему подобный механизм типа intrinsic'ов.
Здравствуйте, Cyberax, Вы писали:
C>Вызов в DLL нельзя за-inline-ить, да ещё он идёт и через косвенную таблицу.
Детали реализации — неинтересные мелочи, получается вид с боку. Что значит "это не то"?
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, Roman Odaisky, Вы писали:
RO>Здравствуйте, remark, Вы писали:
RO>>>Ingo Molnár считает, что «user-space spinlocks are broken beyond words for anything but perhaps SCHED_FIFO tasks». RO>>>А почему?
R>>Это специфично для Linux. При применении спин-локов ОС ничего не знает о зависимостях о потоках — "кто-то кого-то ждёт", "кто-то кого-то задерживает". Для ОС все потоки выглядят просто как "работающие". Соотв. ОС в такой ситуации может делать очень плохой шедулинг.
R>>В Windows есть замечательный вызов SwitchToThread(), который явно говорит шедулеру ОС "я не делаю никакой полезной работы, просто жду какой-то другой поток". Соотв. поток делающий такой вызов неминуемо будет попадать в конец очереди готовых потоков, даже если он высокоприоритетный.
RO>Что-то я не совсем понял. SwitchToThread — это аналог позиксового sched_yield(2), верно? Я взял цитату с http://kerneltrap.org/Linux/Using_sched_yield_Improperly, и самое первое предложение там, опять же цитируя Инго, звучит так: «Really, I have never seen a single mainstream application where the use of sched_yield() was the right choice».
Ну если он не видел, то что ж теперь?
RO>sched_yield/SwitchToThread/boost::this_thread::yield как раз ничего вразумительного планировщику не говорят («я чего-то жду, но чего, не скажу»).
Тем не менее, шедулер может интерпретировать вызов yield() достаточно вразумительным образом — дать возможность повыполняться всем остальным готовым потокам перед повторным запуском текущего.
RO>Уж если инициировать системный вызов и смену контекста, так почему бы сразу не указать ожидаемое событие?
При прочих равных — лучше.
Но в мьютексе получается не при прочих равных — за указание того, чего ждём приходится платить дополнительной атомарной операцией при *каждом* захвате/освобождении мьютекса.
RO>Но речь о другом: спинлоки, как кажется сразу, могли бы быть полезны на многопроцессорных системах, где вроде бы дешевле дождаться освобождения другим процессором ресурса еще в течение этого кванта времени, чем отдать весь остаток своего кванта и потом еще ждать своей очереди. Ingo Molnár считает иначе, но не приводит обоснований. Каковы могут быть причины?
Я так понял, что он имеет в виду мьютексы с пассивным спином, а не с активным. С активным — это вообще очень... спорная вещь.
RO>Я где-то видел статью, автор которой, в контексте программирования на WinAPI, утверждал, что каждый вызов Sleep вызывает у него самые худшие подозрения, и что он исправил много багов в многопоточных системах, попросту переписывая все увиденные упоминания Sleep. Проблема здесь та же: поток чего-то ждет, но программеру лень указать точно, чего именно, вот он и усыпляет поток, наивно надеясь, что утро вечера мудренее.
Это отдельный случай — полагание на специфические тайминги.
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Roman Odaisky, Вы писали:
RO>>Ingo Molnár считает, что «user-space spinlocks are broken beyond words for anything but perhaps SCHED_FIFO tasks». RO>>А почему? C>Так как легко могут вызвать "узкие места" в загруженный системах — если система переключит поток, который держит спинлок, то другие потоки на этом спинлоке будут бесполезно способствовать глобальному потеплению. А в незагруженных один фиг проще системные мьютексы использовать.
Я так понимаю, что речь идёт о мьютексах с пассивным спинов, а не с активным.
