LINUX.ORG.RU

Планирование потоков в NPTL


0

0

Здравствуйте.

В приведенном ниже коде в NPTL потоки планируются таким образом, что "работает" только первый поток, второй блокируется при попытке захватить мьюьекс.

Если раскомментировать строку pthread_yield, то все в порядке: работают оба потока (вместо pthread_yield можно, например, usleep).

В LinuxThread в подобного рода коде мне никогда не приходилось думать ни о каких yield-ах.

Для меня это загадка. Что не так? Подскажите, плиз.

Slackware 12.0 (2.6.21.5)
glibc 2.5 (соответственно и NPTL 2.5)

Спасибо.

---------------------------------------------------------
void *run(void *arg)
{
pthread_mutex_t *m = (pthread_mutex_t *)arg;
for (;;) {
pthread_mutex_lock(m);
printf("[%lu] Do something...\n", pthread_self());
pthread_mutex_unlock(m);
// pthread_yield();
}
return NULL;
}

int main()
{
pthread_mutex_t m;
pthread_t t1, t2;

pthread_mutex_init(&m, NULL);

pthread_create(&t1, NULL, run, (void *)&m);
pthread_create(&t2, NULL, run, (void *)&m);

pthread_join(t1, NULL);
pthread_join(t2, NULL);

exit(0);
}

anonymous

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

У тебя второй поток не может получить блокировку; скорее всего, у тебя до завершения квоты проца первый поток всегда успевает вызвать pthread_mutex_lock.

jr_A
()

> Что не так?

Всё так. Шедулер не знает что ты хочешь чтобы работали оба потока попеременно.

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

execve
()
Ответ на: комментарий от execve

> Всё так. Шедулер не знает что ты хочешь чтобы работали оба потока попеременно.

Шедулер не знает, что он должен шедулить потоки? Странный однако шедулер.

fmj
()
Ответ на: комментарий от fmj

Угу, очень странный планировщик. Сталкивались когда-нибудь с заиканием музыки при интенсивном дисковом обмене? Вот это оно и есть. Кстати это известная "фича" O(1) планировщика ядра, которого сейчас заменяют на CFS.

jr_A
()

Дисциплина диспетчерезации может быть RR, FIFO или OTHER При OTHER время выполнения потока меняется динамически - т е от какого-то фиксированного значения и до бесконечности yeld заставляет передать управление другому потоку установите режим FIFO или RR (правда только под root) и должно работать http://www.roguewave.com/support/docs/leif/sourcepro/html/threadspl/4-3.html

anonymous
()
Ответ на: комментарий от fmj

>> Всё так. Шедулер не знает что ты хочешь чтобы работали оба потока попеременно.

> Шедулер не знает, что он должен шедулить потоки? Странный однако шедулер.

Что из фразы "Шедулер не знает что ты хочешь чтобы работали оба потока попеременно." тебе непонятно? Ты спрашивай, не стесняйся.

execve
()
Ответ на: комментарий от execve

>>> Всё так. Шедулер не знает что ты хочешь чтобы работали оба потока попеременно.

>> Шедулер не знает, что он должен шедулить потоки? Странный однако шедулер.

> Что из фразы "Шедулер не знает что ты хочешь чтобы работали оба потока попеременно." тебе непонятно? Ты спрашивай, не стесняйся.

Что из определния понятия "планировщик" тебе не понятно? Ты спрашивай, не стесняйся.

Речь идет не о том, что кому-то меньше положенного выделяют, а о том, что вообще все время отдается одному потоку, а второй получает болт. Т.е. шедулер по сути дела отдает 100% времени только одному потоку, что для равноприоритетных потоков с одинаковой "OTHER" политикой планирования является явным огрехом шедулера.

fmj
()
Ответ на: комментарий от jr_A

> Угу, очень странный планировщик. Сталкивались когда-нибудь с заиканием музыки при интенсивном дисковом обмене?

В моем случае это был нерабочий DMA режим винтов, все замирало при любом дисковом обмене, не только музыка ;)

fmj
()
Ответ на: комментарий от jr_A

> У тебя второй поток не может получить блокировку; скорее всего, у тебя до завершения квоты проца первый поток всегда успевает вызвать pthread_mutex_lock.

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

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

fmj
()
Ответ на: комментарий от fmj

> Речь идет не о том, что кому-то меньше положенного выделяют, а о том, что вообще все время отдается одному потоку, а второй получает болт.

Неа. Шедулер даёт шанс поработать обоим потокам, но второй всё время спит на мютексе, вот и не использует свой шанс.

> Т.е. шедулер по сути дела отдает 100% времени только одному потоку, что для равноприоритетных потоков с одинаковой "OTHER" политикой планирования является явным огрехом шедулера.

И ты, разумеется, без труда приведёшь цитату из UNIX'03 о том, что OTHER должен работать не как FIFO.

execve
()
Ответ на: комментарий от execve

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

У меня есть многопоточный код, который разрабатывался под LinuxThreads. О sched_yield я вспоминал только тогда, когда нужно было создать "неблагоприятные" условия при тестировании производительности. В NPTL я столкнулся с "залипанием" некоторых потоков и начал подозревать, что дело здесь именно в работе планировщика потоков.

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

>> Шедулер не знает что ты хочешь чтобы работали оба потока попеременно.

!!! Ничего себе! Да планировщик вообще не должен думать за меня! Раз я запустил поток, значит мне это нужно, а задача планировщика предоставить этому потоку ресурсы в соответствие с политикой и приоритетом.

>>...что для равноприоритетных потоков с одинаковой "OTHER" политикой планирования является явным огрехом шедулера.

Абсолютно согласен, но назвал бы это не "огрехом", а более конкретно: багом.

anonymous
()

в двух словах pthread_mutex_*lock() из LinuxThread делали автоматически неявную pthread_yield() что имело последствием тормознутость доступа к шареному ресурсу...

так что я склонен считать с что баг в чьихто ....

cvv ★★★★★
()
Ответ на: комментарий от cvv

А вот это очень дельная мысль насчет неявных yield-ов в LinuxThreads в pthread_mutex_lock, pthread_cond_wait и некоторых других. По крайней мере этим многое можно объяснить.

Со своим кодом я, конечно, разобрался: поставил в нескольких точках "явные" pthread_yield. Пока "полет нормальный". Расстраивает то, что лично я не вижу "методики". Отловить код типа

pthread_mutex_unlock
pthread_mutex_lock

и поставить между ними pthread_yield не сложно. Но в большом коде не всегда возможно в принципе определить те места, где могут быть потенциальные засады и нужно "вмешиваться в работу планировщика".

anonymous
()

На двухпроцессорной машине ваш пример работает, но второй тред работает гораздо меньше, чем первый, это да. Первый тред 99% времени держит мьютекс и если не делает resched(), то второй тред будет исполняться крайне редко, т.к. во время его работы мьютекс будет практически всегда залочен. Фактически, цикл во втором треде имеет шанс исполниться только в том случае, если у первого треда при отпущенном мьютексе закончился квант времени.

> Да планировщик вообще не должен думать за меня! Раз я запустил поток, значит мне это нужно,

Ну разберитесь, что вы делаете не так, раз вам это так важно.

mv ★★★★★
()
Ответ на: комментарий от anonymous

> и поставить между ними pthread_yield не сложно. Но в большом коде не всегда возможно в принципе определить те места, где могут быть потенциальные засады и нужно "вмешиваться в работу планировщика".

Делайте condition variables. Освободил ресурс - дай другим знать об этом.

mv ★★★★★
()
Ответ на: комментарий от cvv

А кто сказал, что после анлока мьютекса шедулер должен передать управление другому потоку? На моей машине,Linux krum-desktop 2.6.20-15-generic #2 SMP, достаточно случайно работает то один поток, то другой. К тому же, после printf нужно делать flush. Вообще это типичный race condition, и если ваша программа так написана, то надо задуматься у выпрямлении рук программиста.

krum
()
Ответ на: комментарий от anonymous

> Со своим кодом я, конечно, разобрался: поставил в нескольких точках "явные" pthread_yield. Пока "полет нормальный".

Пока тебе везет. Вообще-то yield давно не рекомендуют пользоваться, и планировщику разрешено вообще не принимать этот вызов во внимание. Если уж тебе хочется делать криво, по крайней мере пользуйся usleep.

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

tailgunner ★★★★★
()
Ответ на: комментарий от krum

> К тому же, после printf нужно делать flush.

Не в этом конкретном случае

> Вообще это типичный race condition

С printf? 8)

Описанную ситуацию можно с некоторой натяжкой назвать livelock, но никак не race.

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

Возможно, в любом случае, это анти-паттерн:)

krum
()
Ответ на: комментарий от tailgunner

Согласен, что и sched_yield и usleep - это "криво". Меня раздражает и то, и другое.

Хорошо то, что я не услышал практически ничего для себя нового (каких-то "секретов" работы именно с NPTL). В итоге иначе взглянул на некоторые "стремные" участки своего кода и буду их переделывать. Спасибо.

anonymous
()
Ответ на: комментарий от tailgunner

>Если уж тебе хочется делать криво, по крайней мере пользуйся usleep.

usleep() аналогично не рекомендована к использованию...

Я в решая в молодости аналогичную задачу пользовал nanosleep()

более Красивого способа дать возможность другому захватить ресурс иначе как усыпив текущий поток я не нашёл. Усыплять рекомендую на время равное 90% от HZ.

Иногда по красивому можно решить задачу закрепив за шареным ресурсом поток-менеджер который будет получать и обслуживать очереди запросов (сообщений)

cvv ★★★★★
()
Ответ на: комментарий от krum

>ообще это типичный race condition

как тебе уже сказали это НЕ "типичный race condition"

>кто сказал, что после анлока мьютекса шедулер должен передать управление другому потоку?

ты имел после ввиду yield()? никто не говорил. Просто это сильно увеличивает вероятность свободности ресурса на момент переключения контекстов и способствует равномерной доступности ресурса разным потокам...

cvv ★★★★★
()

на заметку:

Алан Кокс ещё в 2001-м году писал:

"В сущности, есть только два оправдания использованию тредов(нитей) в программировании:

1) Слабая подготовка программиста или слаборазвитые средства обработки событий в языке программирования.

2) Проблемы в реализации отдельных компонентов ОС (а в posix/sus unix API таковые есть)

Использование Co-routines или _выбор более подходящего языка_ являются гораздо более эффективными решения проблемы обработки событий.

(Источник: http://marc.info/?l=linux-kernel&m=99254377501835&w=2)

А вот ещё крылатая фраза, взятая с домашней странички Larry McVoy: "A computer is a state machine. Threads are for people who can't program state machines."

cvv ★★★★★
()
Ответ на: комментарий от cvv

>> Если уж тебе хочется делать криво, по крайней мере пользуйся usleep.

> usleep() аналогично не рекомендована к использованию...

> Я в решая в молодости аналогичную задачу пользовал nanosleep()

Если моя память мне ни с кем не изменяет, это один и тот же системный вызов (если не используется реализация с select, но для наших целей select вполне подойдет).

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

нет системного вызова usleep(). Это libc-шная ф-я котрую периодически реализуют на SIGALRM.

а nanosleep() - всегда сискол

cvv ★★★★★
()
Ответ на: комментарий от cvv

> нет системного вызова usleep().

Я и не говорил, что он есть. Я сказал, что usleep и nanosleep реализуются одним и тем же системным вызовом.

> Это libc-шная ф-я котрую периодически реализуют на SIGALRM.

На SIGALRM? В Линуксе? Может, назовешь версию libc, в которой так сделали?

tailgunner ★★★★★
()
Ответ на: комментарий от execve

Товарищи, разговор о том, что "лучше": yield, usleep или nonosleep - это спор о том какой костыль изящнее.

Пример кода, открывающий настоящую ветку - это доведение до абсурда. Но дело то в том, что даже этот абсурдный "бессмысленный" код ОБЯЗАН работать правильно, то есть работать должны оба потока и практически симметрично. Задача, которую решает каждый из них, - одна и та же. Асимметричность только в порядке старта потоков. Но "хороший" планировщик обязан забыть об этом очень быстро.

>Первый тред 99% времени держит мьютекс и если не делает resched(), то >второй тред будет исполняться крайне редко, т.к. во время его работы >мьютекс будет практически всегда залочен. Фактически, цикл во втором >треде имеет шанс исполниться только в том случае, если у первого треда >при отпущенном мьютексе закончился квант времени.

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

И дело вовсе не в том, "в молодости" пишется код типа

for(;;) {
pthread_mutex_lock;
...
pthread_mutex_unlock;
}

или "зрелым" программистом :-)




anonymous
()
Ответ на: комментарий от anonymous

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

krum
()
Ответ на: комментарий от anonymous

> и лишнее доказательство кривости не рук программиста, а алгоритмов планировщика.

Извини, но код написанный а-ля "кто первым встал того и тапки" так и должен исполняться, иначе само понятие программирование теряет смысл.

PS: Код в сабже - трэш.

iBliss
()
Ответ на: комментарий от anonymous

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

$ uniq -c out.txt | head -n 20 37999 3085343632 69 3076950928 53 3085343632 53 3076950928 52 3085343632 49 3076950928 50 3085343632 92 3076950928 53 3085343632 39 3076950928 52 3085343632

Я бы сказал, что шедулер очень неплохо справился со своими обязанностями.

Да, $ uname -r 2.6.20-16-generic Kubuntu 7.04

anonymous
()
Ответ на: комментарий от anonymous

Дурное форматирование:

$ uniq -c out.txt | head -n 20
  37999 3085343632
     69 3076950928
     53 3085343632
     53 3076950928
     52 3085343632
     49 3076950928
     50 3085343632
     92 3076950928
     53 3085343632
     39 3076950928
     52 3085343632

anonymous
()
Ответ на: комментарий от mv

> Абсолютно согласен, но назвал бы это не "огрехом", а более конкретно: багом.

Какой же это баг? Баг - это несоответствие спецификации. Но POSIX не указывает _никаких_ особенностей реализации политики SCHED_OTHER.

http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html

Поэтому вы просто _не_можете_ требовать от SCHED_OTHER чего-либо.

Так что использование pthread_yield - всего лишь "совет" планировщику отдать квант другому потоку. И это вполне оправданно в схеме с двумя соревнующимися потоками.

jek_
()
Ответ на: комментарий от tailgunner

После прочтения man usleep:

NOTES
...
The interaction of this function with the SIGALRM signal, and with other timer functions such as alarm(3), sleep(3),
...
is unspecified.

я на неё забил и всегда пользую nanosleep(). В нюансы реализаци в glibc и компании никогда не вникал и не интересовался...

cvv ★★★★★
()
Ответ на: комментарий от fmj

> Речь идет не о том, что кому-то меньше положенного выделяют, а о том, что вообще все время отдается одному потоку, а второй получает болт.

Вообще говоря, по правилам критические секции должны быть малы. В твоем случае, критическая секция занимает львиную долю времени выполнения потока, поэтому вероятность того, что другой поток чудом успеет прорваться в это микроскопическое окно, стремится к 0. Если ты вставляешь usleep, то окно увеличивается и второй поток иногда попадает в него и захватывает управление. При вставке yield ты передаешь управление явно.

Шедулер тут совершенно ни при чем, он делает все правильно. Представь, что у тебя два потока работают абсолютно параллельно (на двух процах, например) и залоченный поток время от времени пытается захватить мьютекс. Какова вероятность того, что очередная проверка увенчается успехом, если конкурент делает ввод/вывод в критической секции и освобождает мьютекс лишь на время выполнения инструкции jmp?

watashiwa_daredeska ★★★★
()
Ответ на: комментарий от watashiwa_daredeska

> Вообще говоря, по правилам критические секции должны быть малы.

Это не мой случай, и если вы прочитаете еще один мой пост, то поймете, что я свою точку зрения быстро поменял, немного пораскинув мозгами :)

fmj
()
Ответ на: комментарий от watashiwa_daredeska

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

Если говорить о реальных приложениях, например, когда нужно дать выполнить какую-то работу и другим потокам в ответ на какие-то события, то тогда удобно использовать парадигму "монитора". В Java за эту задачу отвечают методы wait и notify. В .NET есть специальный класс Monitor. Есть ли аналоги в NTPL - не знаю, но скорее всего должны быть.

Так что, не вижу никаких проблем. При желании все программируется и работает достаточно стабильно и предсказуемо.

dave ★★★★★
()

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

привяжите оба потока к одному CPU. если и тогда не будет
переключаться - вот тогда, действительно, можно ругать
scheduler. но я держу пари, что будет ;)

idle ★★★★★
()
Ответ на: комментарий от idle

> привяжите оба потока к одному CPU. если и тогда не будет переключаться - вот тогда, действительно, можно ругать scheduler.

Нельзя. Планировщик не обязан переключать контекст на pthread_mutex_unlock, если поток не исчерпал свой квант. Но после unlock поток сразу делает lock, что не дает работать второму потоку. Лишь когда исчерпание кванта случайно попадет на тот короткий промежуток, когда mutex свободен, второй поток получит шанс запуститься.

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

watashiwa_daredeska ★★★★
()
Ответ на: комментарий от watashiwa_daredeska

> > привяжите оба потока к одному CPU. если и тогда не будет переключаться -
> > вот тогда, действительно, можно ругать scheduler.
>
> Нельзя. Планировщик не обязан переключать контекст на pthread_mutex_unlock,
> если поток не исчерпал свой квант.

правильно

> Лишь когда исчерпание кванта случайно попадет на тот короткий промежуток,
> когда mutex свободен, второй поток получит шанс запуститься.

нет, это неверно, совсем. и, по моему мнению, такой планировщик считать
хорошим не следует.

динамический приоритет (->prio) у второго процесса будет выше. смотрите
try_to_wake_up(). activate_task()->recalc_task_prio() "учтет" что 2-ой
процесс "starved" (хотя этот термин наверное неправильный). поэтому у нас
будет TASK_PREEMPTS_CURR(), и текущий процесс будет вытеснен.

idle ★★★★★
()
Ответ на: комментарий от idle

> нет, это неверно, совсем.

В общем, да. Посмотрел исходники nptl, в mutex_unlock вызывается futex_wake. Значит, второй поток должен проснуться, когда первый отпустит mutex. Тогда непонятно, чего же dnjhjq поток ждет 38k оборотов.

> такой планировщик считать хорошим не следует.

А дело тут не в планировщике, а в поточной библиотеке. Если б в mutex_unlock не вызывался futex_wake, то процесс был бы в чистом виде вероятностный независимо от приоритетов. Ну, проснулся высокоприоритетный поток, проверил mutex и тут же снова уснул.

watashiwa_daredeska ★★★★
()
Ответ на: комментарий от watashiwa_daredeska

тоесть nptl в mutex_unlock обрабатывает результат futex_wake? каким образом? делает yeild()?

извиняюсь но лень сыпцы искать и ковырять...

кстати при использовании файловых блокировок вместо мютексов вожно было бы вырулить ситуацию на лизах (fcntl)

cvv ★★★★★
()
Ответ на: комментарий от watashiwa_daredeska

> В общем, да. Посмотрел исходники nptl, в mutex_unlock вызывается futex_wake.
> Значит, второй поток должен проснуться, когда первый отпустит mutex.

естественно

> Тогда непонятно, чего же dnjhjq поток ждет 38k оборотов.

хм... этого я не понял

> > такой планировщик считать хорошим не следует.
>
> А дело тут не в планировщике, а в поточной библиотеке. Если б в mutex_unlock не
> вызывался futex_wake, то процесс был бы в чистом виде вероятностный независимо
> от приоритетов.

ну что вы такое говорите... от реализации mutex поведение в данном случае
практически не зависит (разве что это реализацию исполняли вредители народного
хозяйства).

все, что требуется, это чтобы mutex был blocking, те не busy-wait/spinlock

> Ну, проснулся высокоприоритетный поток, проверил mutex и тут же снова уснул.

с чего бы ему проснуться? любая вменяемая реализация должна разбудить waiter
во время unlock. все! теперь от планировщика зависит какой из двух runnable
процессов будет испольняться и захватит семафор.

еще раз: это когда они на однои процессоре. когда они разнесены картина
другая и понятная.

idle ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.