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

← →
Verg © (2005-06-03 11:30) [40]

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

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

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

← →
evvcom © (2005-06-03 11:31) [41]

Полностью согласен, Игорь.

← →
Alexander Panov © (2005-06-03 11:32) [42]

Verg © (03.06.05 11:30) [40]
Они просто снова встанут на ожидании ее освобождения сразу после захвата секции читающим

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

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

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

← →
Alexander Panov © (2005-06-03 11:37) [44]

Игорь Шевченко © (03.06.05 10:58) [29]
Вообще это вполне реальная задача(та, которую я обрисовал).

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

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

Не вижу в этой задаче ничего надуманного.

← →
Verg © (2005-06-03 11:37) [45]

> Почему ты думаешь, что в секцию зайдет читающий, а не пишущий
> поток?

Читающий поток встает на ожидании S, предварительно взведя ReadFlag. Если к этому моменту времени ее уже ожидали N W-еров, то при получении S они тут же будут возвращаться к ожиданию S (вставать в конец очереди), пока эта очередь не дойдет до читающего.

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

← →
Alexander Panov © (2005-06-03 11:40) [46]

Verg © (03.06.05 11:37) [45]
Читающий поток встает на ожидании S, предварительно взведя ReadFlag. Если к этому моменту времени ее уже ожидали N W-еров, то при получении S они тут же будут возвращаться к ожиданию S (вставать в конец очереди), пока эта очередь не дойдет до читающего.

Я ничего не знаю про очередность. Сомневаюсь, что она каким-либо образом соблюдается.
R может долго не получить секцию, пока W крутятся вхолостую, нагружая процессор ненужной работой.

← →
Игорь Шевченко © (2005-06-03 11:42) [47]

Alexander Panov © (03.06.05 11:37) [44]

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

Очередь. Классика.

← →
evvcom © (2005-06-03 11:45) [48]

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

Задача реальная. Но зачем держать крит.секцию все время обработки данных? Ведь секция здесь нужна только для того, чтобы читать/писать массив флагов/адресов и т.п. А сами данные пусть обрабатываются после освобождения секции.

← →
Verg © (2005-06-03 11:56) [49]

> Alexander Panov © (03.06.05 11:40) [46]
> Verg © (03.06.05 11:37) [45]
> Читающий поток встает на ожидании S, предварительно взведя
> ReadFlag. Если к этому моменту времени ее уже ожидали N
> W-еров, то при получении S они тут же будут возвращаться
> к ожиданию S (вставать в конец очереди), пока эта очередь
> не дойдет до читающего.
>
> Я ничего не знаю про очередность. Сомневаюсь, что она каким-либо
> образом соблюдается.
> R может долго не получить секцию, пока W крутятся вхолостую,
> нагружая процессор ненужной работой.

Это не проблема. writer-ов можно пустить в "отстойник" на время работы ридера.

S : TCriticalSection; ReaderInQue : boolean; ReadFlag : TEvent; // Manual reset, initial state = TRUE procedure WriteBuffer( const Data; Size : cardinal ); label l1; begin l1: EnterCriticalSection( S ); if( ReaderInQue ) then begin LeaveCriticalSection( S ) // Вариант с двумя КС- то же нормальный, но в моем мы имеем возможность направить writer-ов выполнять некоторый полезный код, пока с буфером "хозяйничает" ридер // Вот сдесь прямо. WaitForSingleObject( ReadFlag, INFINITE ); Goto l1; end; InternalWriteBuffer( Data, Size ); LeaveCriticalSection( S ); end; function ReadBuffer( var Data; BufferSize : cardinal ) : cardinal; begin ResetEvent( ReadFlag ); ReaderInQue := true; EnterCriticalSection( S ); Result := InternalReadBuffer( Data, BufferSize ); SetEvent( ReadFlag ); ReaderInQue := fasle; LeaveCriticalSection( S ) ; end;

← →
Igorek © (2005-06-03 12:00) [50]

evvcom © (03.06.05 11:07) [33]
Ты противоречишь сам себе в этом посте. Ты путаешь квоты и приоритеты крит. секций.

← →
Igorek © (2005-06-03 12:08) [51]

2 Verg ©
Написано же:

> 1. Не должно быть холостых циклов(while Flag<>Value do)

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

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

Igorek © (03.06.05 12:00) [50]

> квоты и приоритеты крит. секций.

А эти звери из какого зоопарка ?

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

Igorek © (03.06.05 12:08) [51]

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

← →
Alexander Panov © (2005-06-03 12:13) [54]

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

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

← →
evvcom © (2005-06-03 12:14) [55]

> Igorek © (03.06.05 12:00) [50]

А без голословных "обвинений" можно?

← →
Игорь Шевченко © (2005-06-03 12:15) [56]

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

← →
Igorek © (2005-06-03 12:53) [57]

Игорь Шевченко © (03.06.05 12:10) [52]
Ни из какого, ибо таких зверей не существует.

evvcom © (03.06.05 12:14) [55]
Ты же сам написал, что кто первый запросил крит. секцию, тот первый ее и получит.
А потом пишешь, что порядок распределения квот проц. времени может это изменить.

Alexander Panov © (03.06.05 12:10) [53]
Как раз последняя схема полностью удовлетворяет постановке задачи.
Так вашей же постановке в [2] не удовлетворяет.

← →
Alexander Panov © (2005-06-03 12:56) [58]

Igorek © (03.06.05 12:53) [57]
Так вашей же постановке в [2] не удовлетворяет.

В приведенной схеме нет холостых циклов;)

← →
Alexander Panov © (2005-06-03 12:57) [59]

Сейчас сделаю обертку, и можно положить в ящик-)

← →
Игорь Шевченко © (2005-06-03 13:11) [60]

Igorek © (03.06.05 12:53) [57]

Тогда наверное несуществующие термины не стоит употреблять, тем более, в споре, не так ли ?

> Ты же сам написал, что кто первый запросил крит. секцию,
> тот первый ее и получит.
> А потом пишешь, что порядок распределения квот проц. времени
> может это изменить.

Порядок изменения предоставления процессора может изменить того, кто будет первым, разве не так ?

← →
Igorek © (2005-06-03 13:52) [61]

Игорь Шевченко © (03.06.05 13:11) [60]
Тогда наверное несуществующие термины не стоит употреблять, тем более, в споре, не так ли ?
Зачем тогда употребляешь?

← →
Игорь Шевченко © (2005-06-03 13:55) [62]

Igorek © (03.06.05 13:52) [61]

> Зачем тогда употребляешь?

Ой. А разве процитированный пост [50] не твой ?

← →
GrayFace © (2005-06-03 14:57) [63]

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

Igorek © (02.06.05 22:12) [7]
Хорошее решение, но для полного счастья такая поправка:
Читатель, завершив свое грязное дело, освобождает S2, передает квант проц. времени читателю, и только потом освобожает S1.

КаПиБаРа © (03.06.05 9:11) [21]
6 W1 выходит из S1 и продолжает парсить
Противоречит схеме автора.

Verg © (03.06.05 10:58) [30]
Наихудший вариант.

leonidus © (03.06.05 11:00) [32]
Я не пойму, а как будут между собой взаимодействовать две критические секции защищающие один ресурс? Для одной К.C. все ясно, на как работают две?
Крит. секции вообще не обязаны защищать какие-то ресурсы. Работают они по-простому: кто успел, тот захватывает, остальные, вызвавшие FCS.Enter, ждут. Потом кто-то из них пробуждается после вызова FCS.Leave. Соответственно, перебирай все варианты, учитывая, что в любой момент квант проц. времени может исхерпаться, и активизируется другой поток.

Alexander Panov © (03.06.05 12:56) [58]
В приведенной схеме нет холостых циклов;)
Зато есть объект синхронизации, отличный от крит. секции.

← →
GrayFace © (2005-06-03 14:59) [64]

Описка:

Igorek © (02.06.05 22:12) [7]
Хорошее решение, но для полного счастья такая поправка:
Писатель, завершив свое грязное дело, освобождает S2, передает квант проц. времени читателю, и только потом освобожает S1.

← →
Игорь Шевченко © (2005-06-03 15:08) [65]

GrayFace © (03.06.05 14:57) [63]

Матчасть ?

← →
Igorek © (2005-06-03 15:16) [66]

Игорь Шевченко © (03.06.05 13:11) [60]
Порядок изменения предоставления процессора может изменить того, кто будет первым, разве не так ?
В контексте цитаты не так.
Игорь Шевченко © (03.06.05 13:55) [62]
Ой. А разве процитированный пост [50] не твой ?
Мой, а что?

← →
Игорь Шевченко © (2005-06-03 15:20) [67]

Igorek © (03.06.05 15:16) [66]

> Мой, а что?

А то, что термины взяты из твоего поста. Вот и все.

> В контексте цитаты не так.

Тогда расскажи, как ты понял контекст цитаты :)

← →
Igorek © (2005-06-03 15:40) [68]

Игорь Шевченко © (03.06.05 15:20) [67]
А то, что термины взяты из твоего поста. Вот и все.
В моем посте нету несуществующих терминов.
Игорь Шевченко © (03.06.05 15:20) [67]
Тогда расскажи, как ты понял контекст цитаты :)
Так это ж моя цитата! Тебе ее пояснить, что бы ты лучше понял? :)

Igorek © (03.06.05 15:40) [68]

> В моем посте нету несуществующих терминов.

Тогда разъясни мне фразу "Ты путаешь квоты и приоритеты крит. секций.".

Что такое квота крит. секции и приоритет крит. секции.

> Что такое квота крит. секции

Я понял его так: "Ты путаешь (квоты) и (приоритеты крит. секций)"
насчет квоты все понятно, а насчет приоритетов...

Игорь Шевченко © (03.06.05 15:49) [69]
Тогда разъясни мне фразу "Ты путаешь квоты и приоритеты крит. секций.".
Что такое квота крит. секции и приоритет крит. секции.
Квоту критической секции я не упоминал. Не знаю такого термина, и сожалею, что ты меня неправильно понял.
Есть:
квота - это та часть процессорного времени, которой пользуется данный поток после переключения контекста процессора на него (на данный поток) и до переключения на другой поток
приоритет критической секции - это правило, по которому из числа ожидающих занятую крит. секцию потоков (одинакового приоритета) выбирается один, которому эта секция после освобождения предоставляется;

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

Igorek © (03.06.05 16:28) [71]

Квота в твоей цитате, и в evvcom - это вообще-то квант называется.

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

Нет такого правила.

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

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

> Igorek © (03.06.05 12:08) [51]
> 2 Verg ©
> Написано же:
>
> > 1. Не должно быть холостых циклов(while Flag<>Value do)

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

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

Вобщем между делом наклепал пример.

Может излишне перегружен код, но меня всегда подводит тяга к универсализму.

unit uRW; interface uses Classes, windows, SyncObjs; type TWRProc=procedure(Sender: TObject); TTypeWR=(twrReader,twrWriter); TBuffer=class private FFlagRead: THandle; FCS: TCriticalSection; FProcOnWrite: TWRProc; FProcOnRead: TWRProc; function GetOnWrite: TWRProc; procedure SetOnWrite(const Value: TWRProc); function GetOnRead: TWRProc; procedure SetOnRead(const Value: TWRProc); function GetFlagRead: Boolean; procedure SetFlagRead(const Value: Boolean); public constructor Create; destructor Destroy; override; procedure Enter; procedure Leave; procedure WriteBuf(Sender: TObject;aProc: TWRProc); procedure ReadBuf(Sender: TObject;aProc: TWRProc); property OnWrite: TWRProc read GetOnWrite write SetOnWrite; property OnRead: TWRProc read GetOnRead write SetOnRead; property FlagRead: Boolean read GetFlagRead write SetFlagRead; procedure WaitReader; end; TWR = class(TThread) private FReadEvent: THandle; FType: TTypeWR; FBuf: TBuffer; FProc: TWRProc; procedure Display; protected procedure Execute; override; public constructor Create(aBuf: TBuffer;Proc: TWRProc; aType: TTypeWR); destructor Destroy; override; procedure CheckBuffer; property IOProc: TWRProc read FProc write FProc; end; implementation { TBuffer } constructor TBuffer.Create; begin FFlagRead := CreateEvent(nil,True,False,nil); FCS := TCriticalSection.Create; end; destructor TBuffer.Destroy; begin CloseHandle(FFlagRead); FCS.Free; end; procedure TBuffer.Enter; begin FCS.Enter; end; function TBuffer.GetFlagRead: Boolean; begin Result := ( WaitForSingleObject(FFlagRead,0)=WAIT_OBJECT_0 ); end; function TBuffer.GetOnRead: TWRProc; begin Result := FProcOnRead; end; function TBuffer.GetOnWrite: TWRProc; begin Result := FProcOnWrite; end; procedure TBuffer.Leave; begin FCS.Leave; end; procedure TBuffer.ReadBuf(Sender: TObject;aProc: TWRProc); begin if Assigned(aProc) then begin FlagRead := False; Enter; try aProc(Sender); finally FlagRead := True; Leave; end; end; end; procedure TBuffer.SetFlagREad(const Value: Boolean); begin case Value of True: SetEvent(FFLagRead); False: ResetEvent(FFLagRead); end; end; procedure TBuffer.SetOnRead(const Value: TWRProc); begin FProcOnRead := Value; end; procedure TBuffer.SetOnWrite(const Value: TWRProc); begin FProcOnWrite := Value; end; procedure TBuffer.WaitReader; begin WaitForSingleObject(FFlagRead, INFINITE); end; procedure TBuffer.WriteBuf(Sender: TObject;aProc: TWRProc); begin if Assigned(aProc) then begin WaitReader; Enter; try aProc(Sender); finally Leave; end; end; end; { TWR } procedure TWR.CheckBuffer; begin SetEvent(FReadEvent); end; constructor TWR.Create(aBuf: TBuffer; Proc: TWRProc; aType: TTypeWR); begin inherited Create(True); if FType=twrReader then FReadEvent := CreateEvent(nil,True,False,nil); FBuf := aBuf; FProc := Proc; FType := aType; Resume; end; destructor TWR.Destroy; begin if FType=twrReader then CloseHandle(FReadEvent); inherited Destroy; end; procedure TWR.Display; begin case FType of twrReader: if Assigned(FBuf.OnRead) then FBuf.OnRead(Self); twrWriter: if Assigned(FBuf.OnWrite) then FBuf.OnWrite(Self); end; end; procedure TWR.Execute; begin Randomize; while not Terminated do begin if FType=twrReader then FBuf.ReadBuf(Self,FProc) else FBuf.WriteBuf(Self,FProc); Synchronize(Display); if FType=twrReader then begin if WaitFOrSingleObject(FReadEvent,10000)=WAIT_OBJECT_0 then ResetEvent(FReadEvent); end else Sleep(Random(1000)+100); end; end; end.

Использование:

unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, uRW; type TForm1 = class(TForm) Button1: TButton; Memo1: TMemo; Button2: TButton; procedure Button1Click(Sender: TObject); procedure Button2Click(Sender: TObject); procedure FormCreate(Sender: TObject); procedure FormClose(Sender: TObject; var Action: TCloseAction); private { Private declarations } public { Public declarations } end; var Form1: TForm1; Reader: TWR; Writer: TWR; List: TStringList; Buf: TBuffer; implementation {$R *.dfm} procedure ProcRead(Sender: TObject); var s: String; begin s := IntToStr(TWR(Sender).ThreadID)+": Reader прочитал данные"; Form1.Memo1.Lines.Add(s); end; procedure ProcWrite(Sender: TObject); var s: String; begin s := IntToStr(TWR(Sender).ThreadID)+": Writer записал данные"; Form1.Memo1.Lines.Add(s); end; procedure Wr(Sender: TObject); var s: String; begin s := IntToStr(TWR(Sender).ThreadID);; List.Add(s); Sleep(100); end; procedure Re(Sender: TObject); begin while List.Count>0 do begin List.Delete(0); end; Sleep(100); end; procedure TForm1.Button1Click(Sender: TObject); var i: Integer; begin for i := 0 to 9 do TWR.Create(Buf,Wr,twrWriter); Reader := TWR.Create(Buf,Re,twrReader); end; procedure TForm1.Button2Click(Sender: TObject); begin Reader.CheckBuffer; Memo1.Lines.Add("Запрос чтения"); end; procedure TForm1.FormCreate(Sender: TObject); begin List := TStringList.Create; Buf := TBuffer.Create; Buf.OnRead := ProcRead; Buf.OnWrite := ProcWrite; end; procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction); begin List.Free; end; end.

> Квота в твоей цитате, и в evvcom - это вообще-то квант называется

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

Игорь Шевченко © (03.06.05 16:48) [72]
Квота в твоей цитате, и в evvcom - это вообще-то квант называется.
Да квант.//мне этот термин не очень нравится, т.к. квант это обычно нечто неделимое, а процессорный квант имеет переменную длину (что подразумевает его делимость)

Короче. Вот цитирую Рихтера:
"EnterCriticalSection выполняет следующие действия.
- Если ресурс свободен, ..//бла-бла
- Если значения элементов структуры свидетельствуют, что ресурс уже захвачен вызывающим потоком, ..//бла-бла
- Если значения элементов структуры указывают на то, что ресурс занял другим потоком, EnterCriticalSection переводит вызывающий поток в режим ожидания. Это потрясающее свойство критических секций: поток, пребывая в ожидании, не тратит ни кванта процессорного времени Система запоминает, что данный поток хочет получить доступ к ресурсу, и - как только поток, занимавший этот ресурс, вызывает LeaveCriticalSection — вновь начинает выделять нашему потоку процессорное время...
...
В конце участка кода, использующего разделяемый ресурс, должен присутствовать вызов.
VOID LeaveCriticalSection(PCRITICAL_SECTION pcs);
Эта функция просматривает элементы структуры CRITICAL_SECTION и уменьша ет счетчик числа захватов ресурса вызывающим потоком на 1. Если его значение больше 0, LeaveCriticalSection ничего не делает и просто возвращает управление.
Если значение счетчика достигло 0, LeaveCnitcalSection сначала выясняет, есть ли в системе другие потоки, ждущие данный ресурс в вызове EnlerCriticalSection Если есть хотя бы один такой поток, функция настраивает значения элементов структуры, что бы они сигнализировали о занятости ресурса, и отдает его одному из ждущих потоков (поток выбирается «по справедливости»)"
Джеффри РИХТЕР
WINDOWS
Создание эффективных WIN32-приложений с учетом специфики 64-разрядной версии Windows
ГЛАВА 8 Синхронизация потоков в пользовательском режиме

Вопросы?

Alexander Panov © (03.06.05 17:02) [74]

У меня вопрос - а что эта программа делает, кроме того, что память кушает ?
Я ее честно скомпилировал, запустил. Не смог остановить, пришлось снимать.

Игорь Шевченко © (03.06.05 17:44) [77]

-)
это пример, и не более того. Сделан как иллюстрация к задаче в [2].

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

Память он не кушает зря. Просто в Memo1 не удаляются строки.

Alexander Panov © (03.06.05 17:49) [79]

Я несколько к другому. То есть, мне из запущенного примера даже непонятно, корректно ли она работает или некорректно. Уж если делать демку, то так, чтобы было видно, в одном мемо, например, записанные данные, в другом - прочитанные, чтобы можно было проверить, что то, что записано, оно и прочиталось. Чтобы можно было остановить процесс, наконец :)

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