Продолжение дискуссии "Как избежать гонок в потоках"

← →
evvcom © (2005-06-02 17:04) [0]

Продолжение трепа http://delphimaster.net/view/1-1117521494/ переносим сюда.

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

Проще начать с

> Alexander Panov © (02.06.05 15:41) [81]
> 3. С какого перепугу поток вдруг начнет обрабатывать PostMessage?

Согласен. Упустил. Сам поток как таковой не обрабатывает оконные сообщения. Для этого проще извещать основной поток (любую TForm).
Далее...

← →
Игорь Шевченко © (2005-06-02 17:22) [1]

> Сам поток как таковой не обрабатывает оконные сообщения

Обрабатывает. Собственно, все сообщения окнам потока потоку и приходят. Но лучше использовать PostThreadMessage и проверять равенство HWND=0

← →
Alexander Panov © (2005-06-02 18:32) [2]

Игорь Шевченко © (02.06.05 17:22) [1]
evvcom © (02.06.05 17:04)

Изначально поставлена такая задача:

1. Есть заранее неопределенное число потоков, которые получают данные извне, которые заполняющие некий буфер. Назовем их писателями(W)

2. Есть один или несколько потоков-читателей, которые в неопределенный момент времени должны прочитать из буфера данные. Для простоты пусть таковой будет один(R).

3. В некий момент времени R получает команду прочитать буфер.
При этом все остальные потоки W должны немедленно прекратить свою работу по записи буфера, кроме потока, который в данный момент заполняет буфер.
Поток, который пишет в буфер в данный момент, должен записать текущую порцию данных,а затем также должен прекратить попытки записывать данные до тех пор, пока буфер не будет прочитан R.

Предполагаемые требования к потокам:

1. Не должно быть холостых циклов(while Flag<>Value do)
2. Процесс не должен влиять на работу остальных приложений в системе.
---------------------------------

Утверждается:

Для выполнения поставленной задачидостаточно использования критических секций. Другие объекты синхронизации(Mutex, Event, и подобные) использовать необходимости нет.

Предлагаю решить поставленную задачу с этими ограничениями.
-----------------------------------------------------------

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

← →
iZEN © (2005-06-02 19:55) [3]

Alexander Panov,

http://izen.dev.juga.ru/notebook/solutions/threads/prodcons.html

ОНО?

← →
Alexander Panov © (2005-06-02 20:09) [4]

iZEN © (02.06.05 19:55) [3]
ОНО?

Не совсем.
Потребитель должен иметь приоритет преде производителем.

← →
GrayFace © (2005-06-02 21:40) [5]

А преоритет точно действует на крит. секции?

evvcom © (01.06.05 11:16) [35]
Ну и нафига здесь synchronize до выхода из крит.секции, да еще try finally навесил?
Чтоб главному потоку не приходилось ждать, пока какией-то потоки проводят запись в массив.

leonidus
См. книгу Рихтера "Windows для профессионалов". По слухам, есть на http://www.podgoretsky.com

leonidus © (01.06.05 19:42) [57]
Это да, но я так понял, что кто первый тот и молодец.
Как я помню, не всегда.

Alexander Panov © (01.06.05 21:01) [59]
Для таких флагов подходят как семафоры, так и мьютексы.
Мьютексы-флажки?? По-моему, на роль флажка лучше всего подходит Event(Manual Reset).

Digitman © (02.06.05 9:45) [68]
Основной поток имеет бонус в приоретете, т.к. имеет окна. Но это можно отключить где-то в настройках системы.

evvcom © (02.06.05 13:54) [79]
Во время оповещения читающий поток ждет, когда ему ОС выделит квант времени. :)
А в это время кто-то захватывает критическую секцию...

Alexander Panov
Чем использование объектов синхронизации будет лучше, чем вариант с FCS.Enter; Synchronize; FCS.Leave?

← →
Eraser © (2005-06-02 21:50) [6]

Alexander Panov © (02.06.05 18:32) [2]

При этом все остальные потоки W должны немедленно прекратить свою работу по записи буфера, кроме потока, который в данный момент заполняет буфер.

Непонял, а что в ОДИН И ТОТ ЖЕ буффер пишут сразу одновременно несколько потоков? Это как?

← →
Igorek © (2005-06-02 22:12) [7]

Alexander Panov © (02.06.05 18:32) [2]
Основной поток создает две крит. секции. Назовем их S1 и S2.
Читатель перед чтением ждет S2.
Писатель перед записью ждет S1, потом S2.

← →
Alexander Panov © (2005-06-02 23:20) [8]

Igorek © (02.06.05 22:12) [7]

Более развернутый алгоритм можно? Либо код.

← →
Alexander Panov © (2005-06-02 23:23) [9]

Хочу заметить, что стандартный код из книги, пример о "потребителях и производителях" не подойдет.
Не подойдет из-за условия 3.
Поэтому стандартный код прошу не предлагать. В нем другая ситуация. Кардинально.

← →
Eraser © (2005-06-02 23:23) [10]

Вот несколько типовых схем управления потоками, не вкурсе то это или не то, т.к. ветку http://delphimaster.net/view/1-1117521494/ не читал.
Но думаю в любом случае кому нибудь инфа пригодится.

http://mbo88.narod.ru/ToC.html

← →
Alexander Panov © (2005-06-02 23:27) [11]

Кстати, решение не так просто, как это описывали в ветке evvcom и Игорь Шевченко.

← →
КаПиБаРа © (2005-06-03 06:16) [12]

Igorek © (02.06.05 22:12) [7]
Согласен. Я предлагал такой же алгоритм, только на мьютексах.

← →
Тульский © (2005-06-03 08:17) [13]

> См. книгу Рихтера "Windows для профессионалов". По слухам,
> есть на http://www.podgoretsky.com

Не вижу

← →
leonidus © (2005-06-03 08:19) [14]

Коль уж я эту кашу заварил, хочу кое что уточнить:

>Alexander Panov © (02.06.05 18:32) [2]
Изначально поставлена такая задача:

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

2. Есть один или несколько потоков-читателей, которые в неопределенный момент времени должны прочитать из буфера данные. Для простоты пусть таковой будет один(R).
Читает буфер однозначно один поток - основной, он же передает считанные даные в блок закачки.

3. В некий момент времени R получает команду прочитать буфер.
При этом все остальные потоки W должны немедленно прекратить свою работу по записи буфера, кроме потока, который в данный момент заполняет буфер.
Поток, который пишет в буфер в данный момент, должен записать текущую порцию данных,а затем также должен прекратить попытки записывать данные до тех пор, пока буфер не будет прочитан R.
Да это так, только я бы сформулировал так:
3. В некий момент времени R получает команду прочитать буфер.
При этом если в буфер производилась запись потоком W, нужно что бы он доработал до конца, и передал буфер потоку R.

А то потом позникают вопросы типа "что в буфер пишут одновременно несколько потоков ?". Пишет или читает ВСЕГДА один поток, для этого я и применил критическую секцию

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

Пишущий поток должен ОБЯЗАТЕЛЬНО доработать до конца и умереть передав управление потоку R. И больше никаких попыток записиименно он делать не должен.

Утверждается:

Для выполнения поставленной задачи достаточно использования критических секций. Другие объекты синхронизации(Mutex, Event, и подобные) использовать необходимости нет.

Это было бы идеально. Т.к. во-первых я еще и с критическими секциями до конца не разобрался что бы лезть в еще более густые дебри синхронизации потоков. Меня бы вполне устроила бы схема изменения приоритетов или несложный алгоритм взведения флагов.

← →
evvcom © (2005-06-03 08:33) [15]

> Alexander Panov © (02.06.05 18:32) [2]

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

> Eraser © (02.06.05 21:50) [6]
> Alexander Panov © (02.06.05 18:32) [2]
>
> При этом все остальные потоки W должны немедленно прекратить
> свою работу по записи буфера, кроме потока, который в данный
> момент заполняет буфер.
>
> Непонял, а что в ОДИН И ТОТ ЖЕ буффер пишут сразу одновременно
> несколько потоков? Это как?

Хотя мне понятно, что Вы имели в виду.

> Игорь Шевченко © (02.06.05 17:22) [1]
>
> > Сам поток как таковой не обрабатывает оконные сообщения
>
>
> Обрабатывает. Собственно, все сообщения окнам потока потоку
> и приходят.

Каюсь, Игорь, упустил причастный оборот: "поток, не создавший окна для обработки оконных сообщений". Может и сейчас не совсем правильно построил фразу, так что сильно не пинайте.

← →
leonidus © (2005-06-03 08:38) [16]

>evvcom © (03.06.05 08:33) [15]
С учетом 3 пункта, я согласен, что одних крит.секций недостаточно.

Ну а изменения приоритетов между W и R тоже не достаточно?

← →
Digitman © (2005-06-03 08:45) [17]

> А то потом позникают вопросы типа "что в буфер пишут одновременно
> несколько потоков ?"

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

к примеру, есть buf: array[0..2] of byte (чем не буфер) ?

поток 0 пишет в buf[0]
поток 1 пишет в buf[1]
поток 2 читает из buf[2]

чем не "одновременность" ? никто никому не мешает ..

← →
КаПиБаРа © (2005-06-03 08:45) [18]

evvcom © (03.06.05 8:33) [15]
С учетом 3 пункта, я согласен, что одних крит.секций недостаточно.

Я считаю что достаточно и Igorek © в (02.06.05 22:12) [7] показал как это сделать.

← →
evvcom © (2005-06-03 08:54) [19]

> Ну а изменения приоритетов между W и R тоже не достаточно?

В смысле, если изменить приоритет потока? Т.е. ситуация описанная Александром:
1. 100 потоков W с приоритетом Normal-1 выполнили EnterCriticalSection и стопорнулись (ну кроме первого)
2. Потом поток R c приоритетом Normal тоже выполнил EnterCriticalSection и тоже стопорнулся.
3. 1-ый поток W освободил CriticalSection

Вопрос, какой из потоков войдет в крит. секцию один из W или R?

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

Жди, может еще кто чего добавит.

← →
evvcom © (2005-06-03 09:03) [20]

> Я считаю что достаточно и Igorek © в (02.06.05 22:12) [7]
> показал как это сделать.

> Читатель перед чтением ждет S2.
> Писатель перед записью ждет S1, потом S2.

А такой вариант:
1. W1 входит в S1 и S2
2. W2 запрос S1, ожидание
3. R запрос S2, ожидание
4. W1 выходит из S2 и S1
5. W2 входит в S1 и S2
А R так и продолжает ждать

← →
КаПиБаРа © (2005-06-03 09:11) [21]

Разрешите вас поправить

>А такой вариант:
>1. W1 входит в S1 и S2
>2. W2 запрос S1, ожидание
>3. R запрос S2, ожидание
>4. W1 выходит из S2 и S1
>5. W2 входит в S1 и S2
> А R так и продолжает ждать

А такой вариант:
1. W1 входит в S1 и S2
2. W2 запрос S1, ожидание
3. R запрос S2, ожидание
4. W1 выходит из S2
5 R входит в S2
6 W1 выходит из S1 и продолжает парсить
7. W2 входит в S1 и ждет S2
8 R выходит из S2
9 W2 входит в S2 и т.д.

Суть в том что S1 пропускает пишушие потоки только по одному.
К S2 одновременно могут подойти 1 пишущий поток и 1 читающий.
Если пишущий проскочит вперед, то следующим за ним обязательно будет читающий

← →
evvcom © (2005-06-03 09:20) [22]

> 4. W1 выходит из S2
> 5 R входит в S2

А где написано, что при выходе W1 из S2, ОС отберет тут же у W1 его квоту и передаст R? Я соглашусь с этим теоретически только, если приоритет потоков W будет ниже R, в противном случае нет. И окончательно соглашусь только после экспериментов (или опровергну).

← →
КаПиБаРа © (2005-06-03 09:38) [23]

evvcom © (03.06.05 9:20) [22]
А где написано, что при выходе W1 из S2, ОС отберет тут же у W1 его квоту и передаст R?

Интересный вопрос. Надо экспериментировать.

← →
evvcom © (2005-06-03 09:57) [24]

Это все очень интересно. Но изначально была описана leonidus задача такова, что условие 3 Alexander Panov © (02.06.05 18:32) [2] имхо на нее можно не накладывать. Тогда всё упрощается. Объясните мне зачем это условие здесь соблюдать, если каждый из потоков занимает секцию на миллионные, если не меньше, доли секунды? И зачем потоку R надо немедленно начинать парсить, если через долю секунды он все равно остановится и станет ждать, пока поток W докачает из интернета очередную порцию данных?

← →
КаПиБаРа © (2005-06-03 10:05) [25]

evvcom © (03.06.05 9:57) [24]
Может быт это не столь существенно но у вас несколько искаженное понимание первоначальной задачи.

Парсингом занимается не R поток, а W потоки. Закачивает страницы какой-то "блок закачки". R поток читает данные из буфера для передачи в "блок закачки". см leonidus © (03.06.05 8:19) [14]

← →
Igorek © (2005-06-03 10:34) [26]

Alexander Panov © (02.06.05 23:20) [8]
Более развернутый алгоритм можно? Либо код.
Код нету времени писать и тестировать. А алгоритм вроде прозрачный.

evvcom © (03.06.05 9:20) [22]
А где написано, что при выходе W1 из S2, ОС отберет тут же у W1 его квоту и передаст R?
Ты же сам написал - в настоящей реализации ОС запросы на крит. секции идут fifo для потоков одинаковых приоритетов. Поскольку я не писал о приоритетах, то они одинаковы по умолчанию. В качестве гарантии (кромы разности приоритетов читателя и писателя) также можно добавить между вызовами писателем S1 и S2 (и/или между освобождением в обратном порядке) задержку, гарантировано превышающую макс. таймаут на запрос проц. времени (или гарантированую квоту//уж не помню, надо в Рихтере почитать). Также можно в писателе юзать TryCriticalSection в цикле с задержкой.
А вообще надо у МВо еще спросить, он перевел книженцию, может чето добавит.

← →
Игорь Шевченко © (2005-06-03 10:43) [27]

Alexander Panov © (02.06.05 18:32) [2]

И нафига, спрашивается, из простого делать сложное ?

← →
Alexander Panov © (2005-06-03 10:53) [28]

Игорь Шевченко © (03.06.05 10:43) [27]
И нафига, спрашивается, из простого делать сложное ?

Не понял мысль-)

Alexander Panov © (03.06.05 10:53) [28]

У автора изначальной классический алгоритм многопоточного анализа и заполнения неких данных (ну, бывает). Зачем при этом вводить какие-то дополнительные условия вроде "предполагаемых требований к потокам" и условия 3, мне совсем непонятно.

S : TCriticalSection; ReadFlag ; boolean; procedure WriteBuffer( const Data; Size : cardinal ); label l1; begin l1: EnterCriticalSection( S ); if( ReadFlag ) then begin LeaveCriticalSection( S ) Goto l1; end; InternalWriteBuffer( Data, Size ); LeaveCriticalSection( S ); end; function ReadBuffer( var Data; BufferSize : cardinal ) : cardinal; begin ReadFlag := true; EnterCriticalSection( S ); Result := InternalReadBuffer( Data, BufferSize ); ReadFlag := fasle; LeaveCriticalSection( S ) ; end;

> у вас несколько искаженное понимание первоначальной задачи

Возможно. На протяжении стольких постов понимание могло исказиться.

> Парсингом занимается не R поток, а W потоки. Закачивает страницы какой-то "блок закачки".

Тогда уж поток парсинга можно назвать RW, причем, как я уже писал, его одного будет достаточно, имхо. Ему ж надо прочитать флаг, что "закачено", а потом записать флаг "распарсено" :) А "блок закачки" - это несколько потоков W

Я не пойму, а как будут между собой взаимодействовать две критические секции защищающие один ресурс? Для одной К.C. все ясно, на как работают две?

> Ты же сам написал - в настоящей реализации ОС запросы на
> крит. секции идут fifo для потоков одинаковых приоритетов.

Но я также писал, что это незадокументировано, поэтому ставку на это делать нельзя. И кроме того, я также не писал, что ОС отберет тут же у W1 его квоту и передаст R. W1 (при одинаковых приоритетах) может успеть покинуть и S1. И в этом случае, даже в текущей реализации ОС, квант времени наверняка получит (хотя я не утверждаю, что это факт) получит W2 и свободно займет обе секции.

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

> Для одной К.C. все ясно, на как работают две?

независимо друг от друга, вследствие чего легко получить deadlock

> Игорь Шевченко © (03.06.05 11:07) [34]

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

Недостаток, который нужно устранять в Verg © (03.06.05 10:58) [30] - при ReadFlag=True записывающие потоки не должны пытаться получтьб критическую секцию.

evvcom © (03.06.05 11:10) [36]

> Могу согласится, что чтение все же полезно по мере поступления
> обработанной информации,

И каким образом определяется, что информация пригодна для чтения ? Если каждый информация, представленная каждым пишушим потоком, не зависит от информации, представленной другими пишущими потоками, то это, опять же, классическая задача "производитель/потребитель", в которой многопточность используется для повышения скорости производителя (например, один поток производителя долго ожидает какого-то ввода-вывода для получения необходимых для начала разбора данных, а другие в это время занимаются разбором). В таком случае имеет смысл организовать очередь, куда все производящие потоки помещают результаты своей деятельности, а потоки потребителя опустошают эту очередь. Реализаций решения такого класса задач множество и они давно известны.
Если же результаты разбора имеют смысл только вместе (например, при многопоточной закачке одного файла с web-узла), когда части файла по отдельности смысла не имеют, то реализация напрашивается следующая - создается набор объектов "событие", изначально в занятом состоянии, каждый поток-производитель переводит свой объект "событие" в свободное состояние, а поток-потребитель вызывает WaitForMultipleObjects с параметром bWaitAll равным true для того, чтобы гарантировано дождаться завершения всех потоков-производителей.

> Alexander Panov © (03.06.05 11:24) [38]

при ReadFlag=True записывающие потоки не должны пытаться получтьб критическую секцию.

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

Продолжение дискуссии "Как избежать гонок в потоках" Найти похожие ветки