Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"

Автор книги: Джулиан Бакнелл

сообщить о нарушении

Текущая страница: 33 (всего у книги 36 страниц)

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

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

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

Естественно, необходимо выбрать функцию хеширования. Вместо того чтобы использовать одну из подпрограмм хеширования общего назначения, описанных в главе 7, мы воспользуемся тем фактом, что сигнатуры содержат три символа. В качестве сигнатуры мы определим три младших байта значения типа длинного целого (longint), старший байт которого является нулевым. В результате мы получаем хеш-значение, не требующее никаких вычислений. Как обычно, размер хеш-таблицы должен быть равен простому числу. Я выбрал значение 521 -наименьшее простое число, превышающее 512. Это означает, что в среднем 16 сигнатур из 8-Кбайтного скользящего окна будут преобразовываться в один и тот же номер элемента, образуя для просмотра во время поиска связный список приемлемого размера.

Для восстановления LZ77 целесообразно создать специальный класс хеш-таблице, поскольку в ней должен выполняться ряд специализированных операций. Код этого класса хеш-таблицы приведен в листинге 11.25.

Листинг 11.25. Хеш-таблица LZ77

type

TtdLZSigEnumProc =procedure (aExtraData : pointer;

const aSignature : TtdLZSignature;

aOffset : longint);

PtdLZHashNode = ^TtdLZHashNode;

TtdLZHashNode = packed record hnNext : PtdLZHashNode;

hnSig : TtdLZSignature;

hnOffset : longint;

end;

type

TtdLZHashTable = class private

FHashTable : TList;

FName : TtdNameString;

protected

procedure htError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure htFreeChain( aParentNode : PtdLZHashNode );

public

constructor Create;

destructor Destroy; override;

procedure Empty;

function EnumMatches(const aSignature : TtdLZSignature;

aCutOffset : longint; aAction : TtdLZSigEnumProc;

aExtraData : pointer): boolean;

procedure Insert(const aSignature : TtdLZSignature; aOffset : longint);

property Name : TtdNameString read FName write FName;

end;

constructor TtdLZHashTable.Create;

var

Inx : integer;

begin

inherited Create;

if (LZHashNodeManager = nil) then begin

LZHashNodeManager := TtdNodeManager.Create(sizeof(TtdLZHashNode));

LZHashNodeManager.Name := 1LZ77 node manager1;

end;

{создать хеш-таблицу, преобразовать все элементы в связные списки с фиктивным заглавным узлом}

FHashTable := TList.Create;

FHashTable.Count := LZHashTableSize;

for Inx := 0 to pred(LZHashTableSize) do FHashTable.List^[Inx] := LZHashNodeManager.AllocNodeClear;

end;

destructor TtdLZHashTable.Destroy;

var

Inx : integer;

begin

{полностью уничтожить хеш-таблицу, включая фиктивные заглавные узлы}

if (FHashTable <> nil) then begin

Empty;

for Inx := 0 to pred(FHashTable.Count) do

LZHashNodeManager.FreeNode(FHashTable.List^[Inx]);

FHashTable.Free;

end;

inherited Destroy;

end;

procedure TtdLZHashTable.Empty;

var

Inx : integer;

begin

for Inx := 0 to pred(FHashTable.Count) do htFreeChain(PtdLZHashNode(FHashTable.List^[Inx]));

end;

function TtdLZHashTable.EnumMatches( const aSignature : TtdLZSignature;

aCutOffset : longint;

aAction : TtdLZSigEnumProc;

aExtraData : pointer): boolean;

var

Inx : integer;

Temp : PtdLZHashNode;

Dad : PtdLZHashNode;

begin

{предположим, что ни один элемент не найден}

Result := false;

{вычислить индекс хеш-таблицы для этой сигнатуры}

Inx := (aSignature.AsLong shr 8) mod LZHashTableSize;

{выполнить обход цепочки, расположенной в позиции с этим индексом}

Dad := PtdLZHashNode (FHashTable.List^[Inx]);

Temp := Dad^.hnNext;

while (Temp <> nil) do

begin

{если смещение этого узла меньше значения смещения, по которому выполняется усечение, остальная часть цепочки удаляется, и выполняется выход из подпрограммы}

if (Temp^.hn0ffset < aCutOffset) then begin

htFreeChain(Dad);

Exit;

end;

{если сигнатура узла совпадает с данной сигнатурой, выполняется вызов подпрограммы, выполняющей действие}

if (Temp^.hnSig.AsLong = aSignature.AsLong) then begin

Result true;

aAction(aExtraData, aSignature, Temp^.hnOffset);

end;

(перешли к следующему узлу) Dad := Temp;

Temp := Dad^.hnNext;

end;

end;

procedure TtdLZHashTable.htFreeChain(aParentNode : PtdLZHashNode);

var

Walker, Temp : PtdLZHashNo4e;

begin

Walker := aParentNode^.hnNext;

aParentNode^.hnNext := nil;

while (Walker <> nil) do

begin

Temp := Walker;

Walker := Walker^.hnNext;

LZHashNodeManager.FreeNode(Temp);

end;

end;

procedure TtdLZHashTable.Insert(const aSignature : TtdLZSignature;

aOffset : longint);

var

Inx : integer;

NewNode : PtdLZHashNode;

HeadNode : PtdLZHashNode;

begin

{вычислить индекс хеш-таблицы для этой сигнатуры}

Inx := (aSignature.AsLong shr 8) mod LZHashTableSize;

{распределить новый узел и вставить его в начало цепочки, расположенной в позиции хеш-таблицы, определяемой этим индексом; тем самым обеспечивается упорядочение узлов в цепочке в порядке убывания значений смещения}

NewNode := LZHashNodeManager.AllocNode;

NewNode^.hnSig := aSignature;

NewNode^.hnQffset :=a0ffset;

HeadNode := PtdLZHashNode(FHashTable.List^[Inx]);

NewNode^.hnNext := HeadNode^.hnNext;

HeadNode^.hnNext := NewNode;

end;

В целях повышения эффективности в хеш-таблице используется диспетчер узлов, поскольку придется распределить и освободить несколько тысяч узлов. Это выполняется внутри конструктора Create. Через непродолжительное время метод EnumMatches вызывается снова. Он просматривает все элементы в хеш-таблице на предмет совпадения с конкретной сигнатурой и для каждого найденного такого элемента вызывает процедуру aAction. Так реализуется основная логика установления соответствия алгоритма LZ77.

Класс скользящего окна выполняет также ряд важных функций, кроме сохранения ранее встречавшихся байтов. Во-первых, во время кодирования скользящее окно считывает данные из входного потока большими боками, чтобы об этом не нужно было беспокоиться во время выполнения подпрограммы сжатия. Во-вторых, оно возвращает текущую сигнатуру и ее смещение во входном потоке. Третий метод выполняет сопоставление: он принимает смещение во входном потоке, преобразует его в смещение в буфере скользящего окна, а затем сравнивает хранящиеся там символы с символами в текущей позиции. Метод будет возвращать количество совпадающих символов и значение расстояния, что позволяет создать пару расстояние/длина. Заключительный фрагмент кода реализации этого класса скользящего окна приведен в листинге 11.26 (код остальных методов можно найти в листинге 11.23).

Листинг 11.26. Методы скользящего окна, используемые во время сжатия

procedure TtdLZSlidingWindow.Advance(aCount : integer);

var

ByteCount : integer;

begin

{при необходимости сместить начало скользящего окна}

if ((FCurrent – FStart) >= tdcLZSlidingWindowSize) then begin

inc(FStart, aCount);

inc(FStartOffset, aCount);

end;

{сместить текущий указатель}

inc(FCurrent, aCount);

{проверить смещение в зону переполнения}

if (FStart >= FMidPoint) then begin

{переместить текущие данные обратно в начало буфера}

ByteCount := FLookAheadEnd – FStart;

Move(FStart^, FBuffer^, ByteCount);

{сбросить различные указатели}

ByteCount := FStart – FBuffer;

FStart := FBuffer;

dec(FCurrent, ByteCount);

dec(FLookAheadEnd, ByteCount);

{выполнить считывание дополнительных данных из потока}

swReadFromStream;

end;

end;

function TtdLZSlidingWindow.Compare(aOffset : longint;

var aDistance : integer): integer;

var

MatchStr : PAnsiChar;

CurrentCh : PAnsiChar;

begin

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

{вычислить позицию в скользящем окне, соответствующую переданному смещению и ее расстоянию от текущей позиции}

MatchStr := FStart + (aOffset – FStartOffset);

aDistance := FCurrent – MatchStr;

inc(MatchStr, 3);

{вычислить длину строки совпадающих символов между данной и текущей позицией. Эта длина не должна превышать максимальной длины. Для конца входного потока определен специальный случай}

Result := 3;

CurrentCh := FCurrent + 3;

if (CurrentCh <> FLookAheadEnd) then begin

while (Result < tdcLZMaxMatchLength) and (MatchStr^ = CurrentCh^ ) do

begin

inc(Result);

inc(MatchStr);

inc(CurrentCh);

if (CurrentCh = FLookAheadEnd) then

Break;

end;

end;

end;

procedure TtdLZSlidingWindow.GetNextSignature(var aMS : TtdLZSignature;

var aOffset : longint);

var

P : PAnsiChar;

i : integer;

begin

{вычислить длину совпадающей строки; обычно она равна 3, но в конце входного потока она может быть равна 2 или менее.}

if ((FLookAheadEnd – FCurrent) < 3) then

aMS.AsString[0] := AnsiChar (FLookAheadEnd – FCurrent) else

aMS.AsString[0] := #3;

P := FCurrent;

for i := 1 to length (aMS.AsString) do

begin

aMS.AsString[i] := P^;

inc(P);

end;

aOffset := FStartOffset + (FCurrent – FStart);

end;

procedure TtdLZSlidingWindow.swReadFromStream;

var

BytesRead : longint;

BytesToRead : longint;

begin

{выполнить считывание дополнительных данных в зону упреждающего просмотра}

BytesToRead := FBufferEnd – FLookAheadEnd;

BytesRead := FStream.Read(FLookAheadEnd^, BytesToRead);

inc(FLookAheadEnd, BytesRead);

end;

Теперь, когда наш арсенал пополнился этими классами, можно создать подпрограмму сжатия, показанную в листинге 11.27. Она слегка осложняется необходимостью накапливать коды сжатия по восемь. Это делается для того, чтобы можно было вычислить байт флага для всех восьми байтов, а затем записать байт флага, за которым следуют восемь кодов. Именно этой цели служит массив Encodings. Однако, поскольку мы рассмотрели достаточно много вспомогательных подпрограмм, сама эта подпрограмма не слишком сложна для понимания.

Листинг 11.27. Подпрограмма ZL77

type

PEnumExtraData = ^TEnumExtraData; {запись дополнительных данных для }

TEnumExtraData = packed record { метода FindAll хеш-таблицы}

edSW : TtdLZSlidingWindow; {..объект скользящего окна}

edMaxLen : integer;{..максимальная длина совпадающих }

{строк на данный момент}

edDistMaxMatch: integer;

end;

type

TEncoding = packed record

AsDistLen : cardinal;

AsChar : AnsiChar;

IsChar : boolean;

{ $IFNDEF Delphi1}

Filler : word;

{$ENDIF}

end;

TEncodingArray = packed record

eaData : array [0..7] of TEncoding;

eaCount: integer;

end;

procedure MatchLongest(aExtraData : pointer;

const aSignature : TtdLZSignature;

aOffset : longint);

far;

var

Len : integer;

Dist : integer;

begin

with PEnumExtraData(aExtraData)^ do

begin

Len :=edSW.Compare(aOffset, Dist);

if (Len > edMaxLen) then begin

edMaxLen := Len;

edDistMaxMatch := Distend;

end;

end;

procedure WriteEncodings(aStream : TSTream;

var aEncodings : TEncodingArray);

var

i : integer;

FlagByte : byte;

Mask : byte;

begin

{построить байт флага и записать его в поток}

FlagByte := 0;

Mask :=1;

for i := 0 to pred(aEncodings.eaCount) do

begin

if not aEncodings.eaData[i].IsChar then

FlagByte := FlagByte or Mask;

Mask := Mask shl 1;

end;

aStream.WriteBuffer(FlagByte, sizeof(FlagByte));

{записать коды}

for i := 0 to pred(aEncodings.eaCount) do

begin

if aEncodings.eaData[i].IsChar then

aStream.WriteBuffer(aEncodings.eaData[i].AsChar, 1) else

aStream.WriteBuffer(aEncodings.eaData[i].AsDistLen, 2);

end;

aEncodings.eaCount := 0;

end;

procedure AddCharToEncodings(aStream : TStream;

aCh : AnsiChar;

var aEncodings : TEncodingArray);

begin

with aEncodings do

begin

eaData[eaCount].AsChar := aCh;

eaData[eaCount].IsChar := true;

inc(eaCount);

if (eaCount = 8) then

WriteEncodings(aStream, aEncodings);

end;

end;

procedure AddCodeToEncodings(aStream : TStream;

aDistance : integer;

aLength : integer;

var aEncodings : TEncodingArray);

begin

with aEncodings do

begin

eaData[eaCount].AsDistLen :=

(pred(aDistance) shl tdcLZDistanceShift) + (aLength – 3);

eaData[eaCount].IsChar := false;

inc(eaCount);

if (eaCount = 8) then

WriteEncodings(aStream, aEncodings);

end;

end;

procedure TDLZCompress(aInStream, aOutStream : TStream);

var

HashTable : TtdLZHashTable;

SlideWin : TtdLZSlidingWindow;

Signature : TtdLZSignature;

Offset : longint;

Encodings : TEncodingArray;

EnumData : TEnumExtraData;

LongValue : longint;

i : integer;

begin

HashTable :=nil;

SlideWin := nil;

try

HashTable := TtdLZHashTable.Create;

HashTable.Name := 'LZ77 Compression hash table';

SlideWin := TtdLZSlidingWindow.Create(aInStream, true);

SlideWin.Name := 'LZ77 Compression sliding window';

{записать заголовок в поток: 'TDLZ', за который следует размер несжатого исходного потока}

LongValue := TDLZHeader;

aOutStream.WrijteBuffer(LongValue, sizeof(LongValue));

LongValue aInStream.Size;

aOutStream.WriteBuffer(LongValue, sizeof(LongValue));

{подготовка к сжатию}

Encodings.eaCount := 0;

EnumData.edSW := SlideWin;

{получить первую сигнатуру}

SlideWin.GetNextSignature(Signature, Offset);

{до тех пор, пока длина сигнатуры равна трем символам...}

while ( length ( Signature.AsString) = 3 ) do

begin

{выполнить поиск в скользящем окне самой длинной совпадающей строки с использованием хеш-таблицы для идентификации соответствий}

EnumData.edMaxLen := 0;

if HashTable.EnumMatches(Signature,

Offset – tdcLZSlidingWindowSize, MatchLongest, @EnumData) then begin

{имеется по меньшей мере одно соответствие : необходимо сохранить пару расстояние/длина самой длинной совпадающей строки и сдвинуть скользящее окно на расстояние, равное этой длине}

AddCodeToEncodings(aOutStream,

EnumData.edDistMaxMatch, EnumData.edMaxLen, Encodings);

SlideWin.Advance(EnumData.edMaxLen);

end

else begin

{соответствие отсутствует: необходимо сохранить текущий символ и сдвинуть скользящее окно на один символ}

AddCharToEncodings(aOutStream,

Signature.AsString[1], Encodings);

SlideWin.Advance(1);

end;

{добавить эту сигнатуру в хеш-таблицу}

HashTable.Insert(Signature, Offset);

{извлечь следующую сигнатуру}

SlideWin.GetNextSignature(Signature, Offset);

end;

{если последняя сигнатура содержала не более двух символов, их нужно сохранить как коды литеральных символов}

if (length(Signature.AsString) > 0) then begin

for i := 1 to length (Signature.AsString) do AddCharToEncodings(aOutStream,

Signature.AsString[i], Encodings);

end;

{обеспечить запись заключительных кодов}

if (Encodings.eaCount > 0) then

WriteEncodings(aOutStream, Encodings);

finally SlideWin.Free;

HashTable.Free;

end; {try.. finally}

end;

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

Код программы сжатия LZ77 разбит на несколько файлов: TDLZBase.pas содержит несколько общих констант, TDLZHash.pas создает специализированную хеш-таблицу, TDLZSWin – класс скользящего окна, а TDLZCmpr.pas – код выполнения сжатия и восстановления. Все перечисленные файлы можно найти на web-сайте издательства, в разделе материалов.

После того, как мы ознакомились с алгоритмом и кодом реализации сжатия и восстановления LZ77, можно теоретически оценить возможные значения коэффициентов сжатия. Если бы можно было сжать все 10 байтовые строки в файле до 2 байт – иначе говоря, каждый раз получать максимальное соответствие – для каждых 80 байтов файла можно было бы записывать по 17 байт (один байт флага и восемь 2-байтовых кодов). В этом случае коэффициент сжатия равнялся бы 79 процентам. С другой стороны, если бы соответствия в файле вообще не удалось бы найти, для каждых восьми байтов исходного файла в действительности пришлось бы записывать по девять байтов. В этом случае коэффициент сжатия составил бы -13 процентов. В общем случае, как правило, сжатие файлов с применением этого метода позволяет получать коэффициенты сжатия, лежащие между упомянутыми крайними значениями.

Резюме

В этой главе мы провели исследования методов сжатия данных. Мы начали рассмотрение с двух статических алгоритмов кодирования с минимальной избыточностью: кодирования Шеннона-Фано и кодирования Хаффмана. Мы рассмотрели недостатки этих методов – необходимость двукратного считывания входных данных и какого-либо кодирования дерева, чтобы его можно было поставлять со сжатыми данными. Затем мы ознакомились с адаптивным алгоритмом – сжатия с использованием скошенного дерева – позволяющим устранить обе упомянутых проблемы. И в заключение мы рассмотрели сжатие с применением алгоритма JL11, в котором используется словарь, позволяющий сжимать строки символов, а не отдельные символы. Хотя все четыре рассмотренных алгоритма представляют интерес и сами по себе, для их реализации мы воспользовались рядом более простых алгоритмов и структур данных, которые были описаны в предшествующих главах.

Глава 12. Дополнительные темы.

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

Алгоритм считывания-записи

В многопоточных приложениях 32-разрядной операционной системы Windows приходится решать целый ряд проблем, которые в однопоточных программах просто не возникают. Действительно, первая проблема, с которой приходится сталкиваться – определение способа запуска и останова потоков. Но в основном она решается на уровне операционной системы: достаточно внимательно прочесть программную документацию операционной системы и правильно применить почерпнутые сведения.

Этот раздел адресован только тем программистам, которые работают в среде 32-разрядной Windows. Delphi I вообще не поддерживает многопоточную обработку, в то время как Kylix и Linux не предоставляют необходимых примитивных объектов синхронизации, с помощью которых можно было бы решить проблему считывания-записи.

Более серьезная проблема – совместное использование данных несколькими потоками, независимо от того, являются ли данные отдельным целочисленным значением или более сложной структурой данных. По существу, приходится решать вопросы параллельного доступа. Если конкретный поток обновляет часть данных, считывание этих данных в это же время другим потоком лишено смысла. В этом случае считывающий поток (обычно называемый программой считывания {reader} ) может получить частично обновленное значение, поскольку обновляющий поток (программа записи {writer} ) еще не закончил обновление, но операционная система отключилась от него.

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

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

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

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

Если для работы с многопоточными данными совместного использования применяется класс TList, Delphi 3 и последующие версии языка предоставляет класс TThreadedList. В основном, применяемая в этом классе стратегия синхронизации реализуется следующим образом: каждое обращение к TList защищается критическим разделом или флагом синхронизации. Delphi-версия класса TThreadedList предоставляет метод LockList, который выполняет вход в критический раздел и возвращает внутренний класс TList. Затем поток может свободно использовать этот объект TList до момента своего завершения, после чего подпрограмма потока должна вызвать метод UnLockList для выхода из критического раздела.

Хотя это решение работает, и притом весьма успешно, ему присущ очевидный недостаток: в любой отдельный момент времени только один поток может иметь доступ к объекту TList. Класс не делает никакого различия между доступом для считывания (в процессе которого список не изменяется) и доступом для записи (при котором он изменяется). Как уже отмечалось, в любой отдельный момент времени может существовать много программ, осуществляющих одновременное считывание объекта TList. Но может существовать только одна программа, осуществляющая запись в него. Это решение, хотя его и просто реализовать, характеризуется избыточностью. Оно не позволяет с максимальной эффективностью использовать TList для многопоточной обработки.

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

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

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

Разрабатываемый нами комплексный объект нуждается, по меньшей мере, в четырех методах. Поток считывания вызывает первый метод, чтобы начать считывание (обратите внимание, что внутри этой подпрограммы может происходить блокировка, обеспечивающая ожидание окончания работы потока записи). Иногда этот метод называют подпрограммой регистрации считывания (reader registration routine). Как только поток считывания завершает свою работу, он должен вызвать другую подпрограмму для прекращения использования объекта синхронизации и, возможно, предоставления свободы действий потоку записи (подпрограмма отмены регистрации считывания). Аналогично такие же две подпрограммы должны существовать и для потока записи. Назовем эти четыре подпрограммы, соответственно, StartReading, StopReadlng, StartWriting и StopWriting.

Описать возможную работу этого объекта достаточно легко. Сложнее его действительно реализовать. Подпрограмма StartReading выполняет несколько задач. Вначале она должна проверить существование ожидающего своей очереди потока записи. При наличии хотя бы одного такого потока, подпрограмма должна перейти в режим ожидания поступления какого-либо объекта синхронизации. Наиболее подходящие кандидаты на роль такого объекта – семафор или событие (эти объекты допускают одновременный запуск нескольких потоков при поступлении сигнала, в то время как флаг синхронизации или критический раздел не допускают этого). Если в данный момент времени поток записи действительно выполняется, подпрограмма StartReading должна выполнять блокировку таким же образом. В отсутствии выполняющегося или ожидающего потока записи подпрограмма StartReading регистрирует поток как считывающий, осуществляет выход, после чего поток получает возможность немедленно продолжить свою работу.

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

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

Метод StopWriting отменяет регистрацию потока, выполняющегося в качестве записывающего, а затем проверяет существование одного или более готовых к запуску потоков считывания. Если такие потоки существуют, метод передает им ожидаемый ими объект синхронизации и завершает свою работу. Если какие-то потоки считывания отсутствуют, метод проверяет наличие ожидающего потока записи. Если такие потоки существуют, метод предоставляет одному из них свободу действий, передавая ему ожидаемый всеми этими потоками объект, а затем прекращает свою работу. Если ни одна из перечисленных ситуаций не имеет места, метод оставляет составной объект в состоянии, позволяющем немедленный запуск потока чтения или записи.

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