Threads die wieder andere Threads aufrufen in einer schleife

[Votum]

Hallo Liebe Community, meine erster Post hier aber ich hoffe ihr helfft mir trotzdem.

Ich versuche seid gestern einen Webcrawler zu schreiben. Dieser soll Links ausgeben und in eine Listbox ausgeben. Das klappt auch supper. Da er aber auch die unterebenen durchsuchen soll, erstelle ich für jeden Link einen weiteren Thread der die Links der 2 ebene Parst und überprüft ob diese schon in der Listbox vorhanden sind.Danach soll es weiter zur 3. Ebene gehen. Also erstellt der Thread sich rekursiv weiter. So lange bis er keine neuen Links mehr findet.

Mein Problem: Ab 150 Threads wird entweder das Programm grottig langsam oder die Page geht down.

Daher will ich die Anzahl der Threads begrenzen. Leider ist das nicht so einfach da ich ja nicht eifnach sagen kann so stop da es sonst ein Deadlock gibt.

Hat jemand eine Idee?


Hier noch mein bisheriger Quellcode:

Delphi-Quellcode:

unit Unit3;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, JvComponentBase, StdCtrls, idhttp, strutils;




type
  THTTPThread = class(TThread)
  private
    FURL: String;
    HTTP: tidhttp;
    FListText: String;
  protected
    procedure DoWriteListBox;
    procedure DoUpdateThreadCount;
  public
    procedure Execute; override;
    constructor Create(URL: String);
    destructor Destroy; override;
  published
    property URL: String read FURL;
  end;

  TArrayofstring = array of string;
  TForm3 = class(TForm)
    Edit1: TEdit;
    Button1: TButton;
    ListBox1: TListBox;
    Memo1: TMemo;
    Label1: TLabel;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;


var
  Form3: TForm3;
  host:string;
  ccount: integer = 0;

implementation

{$R *.dfm}

constructor THTTPThread.Create(URL: String);
begin
  inherited Create(true);
  FreeOnTerminate := true;
  FURL := URL;
  Resume;
end;


function FindInString(Text, SearchFrom, SearchTo: string; FirstOnly: Boolean; var Return: TArrayOfString): Boolean;
var
  i: Integer;
  FoundString: string;
begin
  Result := False;
  SetLength(Return, 0);
  i := Pos(SearchFrom, Text);
  while i > 0 do
  begin
    Result := True;
    i := i + Length(SearchFrom);
    FoundString := Copy(Text, i, PosEx(SearchTo, Text, i) - i);
    SetLength(Return, Length(Return) + 1);
    Return[High(Return)] := FoundString;
    Delete(Text, 1, i);
    i := Pos(SearchFrom, Text);
    if FirstOnly then
      Break;
  end;
end;



procedure TForm3.Button1Click(Sender: TObject);
var
  I: Integer;
begin
  host := edit1.Text;
  THTTPThread.Create(host);
end;




destructor THTTPThread.Destroy;
begin
  inherited;
end;

procedure THTTPThread.DoUpdateThreadCount;
begin
  Form3.label1.Caption := IntToStr(CCount);
end;

procedure THTTPThread.DoWriteListBox;
begin
  Form3.ListBox1.Items.Add(FListText);
end;

procedure THTTPThread.Execute;
  var
i, j,x,position:integer ;
http:tidhttp;
links:tarrayofstring;
s: string;
found: boolean;
begin

inc(ccount);
synchronize(DoUpdateThreadCount);

HTTP := TIdHTTP.Create(nil);
http.HandleRedirects:= true;
try
  s := http.Get(URL);
except
  S := '';
end;

   findinstring(s,'href="','"',false,links);
   for I := 0 to High(Links) do
   begin
        FListText := links[i];
           if Copy(FListText, 1, 4) <> 'http' then
            begin

              FListText := host + FListText;

              // und hier mit nem if oder ?
              found := false;
              for j := 0 to form3.ListBox1.items.count -1 do
              begin
                if form3.listbox1.items[j] = FListText then
                begin
                  found := true;
                  break;
                end;
              end;
              if not found then
              begin
              THTTPThread.Create(FListText);
              Synchronize(DoWriteListBox);
              end;
            end else if Pos(Host, FListText) > 0 then
            begin
              found := false;
              for j := 0 to form3.ListBox1.items.count -1 do
              begin
                if form3.listbox1.items[j] = FListText then
                begin
                  found := true;
                  break;
                end;
              end;
              if not found then
              begin
              THTTPThread.Create(FListText);
              Synchronize(DoWriteListBox);
              end;
            end;



   end;
   dec(ccount);
synchronize(DoUpdateThreadCount);
end;

[dominikkv]

Zitat:

Zitat von Votum

Daher will ich die Anzahl der Threads begrenzen. Leider ist das nicht so einfach da ich ja nicht eifnach sagen kann so stop da es sonst ein Deadlock gibt.

Warum?

Delphi-Quellcode:

// Execute
begin
  while ccount > 10 do
    sleep(500);

  inc(ccount); 
  // ...

[taveuni]

Hallo,

Threadpool heisst das Zauberwort.
Du erstellts eine (konfigurierbare) Anzahl Threads.
Des weiteren eine Jobliste für Deine auszuführenden Aktionen.
Jeder Thread welcher seine aktuelle Aufgabe beendet hat nimmt sich den
nächsten aus der Jobliste.

Die Zugriffe auf die Liste müssen natürlich z.b. mit einer CritcalSection abgesichert werden.

[Zacherl]

@dominikkv Das kann ja nicht funktionieren. Beispiel:
Thread 1 findet 10 Links. In der Schleife erstellt er nun 3 weitere Instanzen von sich selbst (4 nehmen wir mal ans Begrenzung an). Die erstellten Instanzen parsen die übergebenen Links. Da jetzt aber schon insgesamt 4 Threads laufen, warten die Child Threads bis in alle Ewigkeit, wobei der Thread 1 ebenfalls bis in alle Ewigkeit darauf wartet, dass einer der Child Threads beendet wird.
:arrow: DeadLock

[rollstuhlfahrer]

HI und Herzlich Willkommen in der DP :dp: :dp:

zuerst: Threads arbeiten GLEICHZEITIG. Das heißt, sie teilen sich die CPU-Last untereinander auf. Und wenn du deine CPU-Last auf 150 Rechner (Threads) verteilen müsstest, wäre dein Rechner auch lahm.
"die Page geht down" - ist klar. Fällt übrigens unter DOS-Angriff.
Dann verwendest du in deinem Code inc() und dec() für die Zählvariable. Dies ist aber nicht richtig. Wenn 2 Threads gleichzeitig die Variable erhöhen wollen, was durchaus vorkommt bei so vielen, wird die Variable nur um 1 erhöht. (2 Zugriffe, die beide dann erhöhen und ihren Wert ungeprüft zurückschreiben. Dafür bietet Delphi auch bestimmte Funktionen an. Ich würde das aber mit einer Semaphore lösen. (Ist threadsicher). Einer Semaphore kannst du sagen, dass sie eine bestimmte Prozedur nur x-Mal gleichzeitig ausführen darf. Alle die dann die Prozedur ausführen möchten, müssen so lange warten, bis wieder einer fertig ist,
Zum Zählen: InterlockedIncrement und InterlockedDecrement
Die Semaphore: hier

Eine CriticalSection würde ich nicht empfehlen, da diese auch die anderen Threads anhällt.

Bernhard

[Votum]

Zitat:

Zitat von rollstuhlfahrer

HI und Herzlich Willkommen in der DP :dp: :dp:

zuerst: Threads arbeiten GLEICHZEITIG. Das heißt, sie teilen sich die CPU-Last untereinander auf. Und wenn du deine CPU-Last auf 150 Rechner (Threads) verteilen müsstest, wäre dein Rechner auch lahm.
"die Page geht down" - ist klar. Fällt übrigens unter DOS-Angriff.
Dann verwendest du in deinem Code inc() und dec() für die Zählvariable. Dies ist aber nicht richtig. Wenn 2 Threads gleichzeitig die Variable erhöhen wollen, was durchaus vorkommt bei so vielen, wird die Variable nur um 1 erhöht. (2 Zugriffe, die beide dann erhöhen und ihren Wert ungeprüft zurückschreiben. Dafür bietet Delphi auch bestimmte Funktionen an. Ich würde das aber mit einer Semaphore lösen. (Ist threadsicher). Einer Semaphore kannst du sagen, dass sie eine bestimmte Prozedur nur x-Mal gleichzeitig ausführen darf. Alle die dann die Prozedur ausführen möchten, müssen so lange warten, bis wieder einer fertig ist,
Zum Zählen: InterlockedIncrement und InterlockedDecrement
Die Semaphore: hier

Eine CriticalSection würde ich nicht empfehlen, da diese auch die anderen Threads anhällt.

Bernhard

Das dies ein Dos Angriff ist, ist mir durchaus bewust jedoch ist ein Http Flood nicht alzu wirksam.... Falsches Thema :D :angel:

Wie Zacherl gesagt hat geht es schlecht mit maximal 4 Threads wenn ein Thread sich weiter aufruft, kann er ja nicht weitermachen.
Wie arbeitet der Threadpool und wie die Semaphore dann ?

[Zacherl]

Hat man bei der Semaphore nicht das selbe Problem, dass es zu einem DeadLock kommt, da die Threads ja rekursiv arbeiten? Ist ja praktisch genauso, wie es dominikkv beschrieben hatte, nur etwas eleganter.

[rollstuhlfahrer]

nein hat man nicht. Man kann den Thread erzeugen, doch der fängt halt sofort an zu warten, dass ihm ein anderer Platz macht. -> Der Thread wird erzeugt und gestartet. Die erste Aktion dieses Threads ist nur, dass er mal nachfrägt, ob er darf und wenn nicht halt solange nichts tut, bis er darf. Wenn man die neuen Threads startet, kann man ja getrost auf fertig schalten, da die restlichen Threads dann schneller arbeiten können. Der Thread 1. Ordnung soll nicht auf die Threads höherer Ordnung warten, sondern diese starten und sich dann selbst beenden. So hat man zwar auch mal mehr als 150 Threads aktiv, nur machen die zu vielen alle nichts.

Wobei das Konzept mit den Worker-Threads auch nicht schlecht ist. Der Thread parst eine Seite und erstellt für jeden Link einen Job. Ist er fertig, frägt er die Job-Warteschlange, ob welche da sind. Sind welche da, wird der oberste genommen und abgearbeitet. Und so weiter. Dieser Vorgang ist sehr gut skalierbar. Vorteil hierbei ist halt, dass man die Anzahl der vorhandenen Threads absolut begrenzen kann und hat keine schlafenden Threads. Erst wenn alle fertig sind, schaltet man alle zusammen ab und fertig ist die Aufgabe.

Bernhard

[Zacherl]

Finde das ThreadPool Konzept hier auch sinnvoller. Semmaphore war auch meine erste Idee, aber da hat man halt entweder das von mir beschriebene Problem oder die Tatsache, dass du zwar die HTTP Requests limitierst, aber nicht die Threads ansich (wenn man es so macht wie du es eins weiter oben beschreibst).

[shmia]

Die rekursive Technik ist bei einem Webcrawler nicht ratsam.
Man braucht stattdessen zwei Listen:
a.) besuchte URLs
b.) noch nicht besuchte URLS
Die Listen müssen durch Semaphoren oder ähnliche Sperrmechanismen geschützt werden.
Dann startet man z.B. 5 Threads.
Alle Threads machen das Gleiche;
1.) sie entnehmen aus Liste b.) eine URL (wenn Liste b. leer ist: Sleep(1000))
2.) besuchen die URL und schreiben sie in Liste a.)
3.) extrahieren alle gefundenen URLs
4.) prüfen für jede URL, ob sie nicht schon in Liste a.) ist
und hängen sie an Liste b.) an

Man kann das Ganze auch mit einer Liste machen.
Dabei muss für jede URL in der Liste zusätzlich ein Status (besucht oder nicht besucht) geführt werden.
Wenn man schon dabei ist, kann man auch noch den HTTP Resultcode (z.B. 404) in der Liste speichern.