Obliczenia współbieżne na wątkach

Program pokazuje jak zrealizować obliczenia współbieżne na wątkach.

Kiedy można stosować obliczenia współbieżne?

Aby obliczenia współbieżne były możliwe do zastosowania, musi istnieć możliwość podzielenia zadania
obliczeniowego na niezależne części.

Mój przykład

W moim przykładzie używam czterech wątków do obliczenia silni. Obliczanie silni w ten sposób nie ma
większego sensu i służy tu prostemu zobrazowaniu, na czym rzecz polega.
Omówię to na przykładzie silni z 12.
Silnia z N to iloczyn liczb od 1 do N. (Silnia z 0 jest 1.)
Dla 12 jest to 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 10 * 11 * 12.
Łatwo zauważyć, że taki iloczyn można podzielić na iloczyny częściowe np.:
(1 * 2 * 3) * (4 * 5 * 6) * (7 * 8 * 9) * (10 * 11 * 12).
Celowo utworzyłem 4 iloczyny częściowe, oddzielone nawiasami, bo mam zamiar przydzielić każdy z nich
jednemu z czterech wątków, którymi się posługuję w przykładzie.
Na koniec pomnożę iloczyny częściowe przez siebie i otrzymam wynik.

Synchronizacja różnych wątków

Warto zauważyć, że to końcowe mnożenie zostanie również wykonane przy użyciu wątków.
Ponieważ nie wiadomo, w jakim momencie poszczególne wątki wyliczą iloczyny częściowe, należy
wprowadzić synchronizację wątków. Wygląda to tak:
Pierwszy wątek pobiera własny, już obliczony iloczyn częściowy i ustawia flagę gotowości tego
iloczynu do pobrania przez inny wątek.
Drugi wątek po obliczeniu własnego iloczynu czeka na pojawienie się flagi gotowości pierwszego wątku
i mnoży własny iloczyn przez iloczyn z pierwszego wątku, po czym również ustawia flagę gotowości do
pobrania iloczynu przez trzeci wątek. Itd., co można zapisać jako:
Wątek 1: iloczyn_końcowy_1 = iloczyn_częściowy_1
Wątek 2: iloczyn_końcowy_2 = iloczyn_końcowy_1 * iloczyn_częściowy_2
Wątek 3: iloczyn_końcowy_3 = iloczyn_końcowy_2 * iloczyn_częściowy_3
Wątek 4: iloczyn_końcowy_4 = iloczyn_końcowy_3 * iloczyn_częściowy_4
Dzięki synchronizacji przez flagi odbędzie się to w takiej, a nie innej kolejności.
Wynikiem obliczeń jest iloczyn_końcowy_4.

Losowość

Abyś mógł się przekonać, że kolejność zadań wykonywanych przez wątki jest losowa (za wyjątkiem
przypadku synchronizacji) dodałem przycisk ‘Kolejność’.
Praktycznie za każdym razem jest inna.

Przypadek ogólny

Dla liczb, które nie dzielą się przez 4 (ilość wątków) np. 13, ostatni iloczyn jest rozszerzany.
Dla 13 będzie on wyglądał (10 * 11 * 12 * 13). Jest to prosta metoda, ale można się pokusić o
przerobienie programu tak, aby np. dla 14 utworzył iloczyny:
(1 * 2 * 3 * 13) * (4 * 5 * 6 * 14) * (7 * 8 * 9) * (10 * 11 * 12),
aby możliwie równomiernie obciążyć wątki.
Dla liczb zbyt małych, aby „obsadzić” wszystkie wątki, należy przyjąć iloczyny częściowe równe 1.
(Gdybyśmy dodawali wyrazy a nie mnożyli, byłoby to 0).

Uruchomienie programu

Aby uruchomić program, należy utworzyć nowy projekt z Form1, Unit1 i wkleić całą zawartość mojego
Unit1 oraz powiązać w zdarzenia OnCreate i OnClose w kodzie z formą.
Wszystkie kontrolki zostaną utworzone automatycznie po uruchomieniu.

Wykonanie obliczeń

W żółte pole należy wpisać liczbę od 0 do 20, której silnię chcemy obliczyć.
Wynik po kliknięciu Oblicz pojawi się w zielonym polu.

unit Unit1;

interface

uses
  Windows, SysUtils, Classes, Forms, Graphics, StdCtrls, ExtCtrls, Controls;

const
  ThreadCount = 4; //ilość wątków
  JobCount    = 4; //ilość zadań w wątku

type
  TThreadCalc = class(TThread)
  private
    Tag: integer; //numer wątku
    Job: integer; //numer zadania
    Succ: array [0..JobCount - 1] of integer; //kolejność wykonywania zadań
                                              //przez wszystkie wątki
    FGetSucc: boolean;  //jeśli true, badana jest kolejność
  protected
    procedure Execute; override;
    procedure GetData;  //pobranie danej do obliczenia silni
    procedure PutData;  //wyświtlenie rezultatu
    procedure CalcProc; //procedura obliczeniowa
    procedure GetSucc;  //bada kolejność
  public
    constructor CreateWithPar(aTag: integer; aFGetSucc: boolean = false);
      //konstruktor z parametrami
  end;

type
  TForm1 = class(TForm)
    procedure FormCreate(Sender: TObject);
    procedure Calc(Sender: TObject);
    procedure TimerTimer(Sender: TObject);
    procedure FormClose(Sender: TObject; var Action: TCloseAction);
  public
    Threads: array [0..ThreadCount - 1] of TThreadCalc;
      //tablica wątków
    Edits  : array [0..JobCount - 1, 0..ThreadCount - 1] of TEdit;
      //edity do wyświetlenia wyników pośrednich
      //lub kolejności
    Timer: TTimer; //warto umieścić na wypadek niepowodzeń
    procedure ClearEdits(Sender: TObject);
    procedure RunThreads(aFGetSucc: boolean = false);
      //uruchamia wszystkie wątki
  end;

type
  TValue = record
    IntValue: int64;
    StrValue: string;
    IsInt   : boolean; //flaga gotowości wartości int64 do dalszych obliczeń
    IsStr   : boolean; //flaga gotowości wartości string do dalszych obliczeń
  end;

var
  Form1: TForm1;
  Value: array [0..JobCount - 1, 0..ThreadCount - 1] of TValue;
    //tablica wyników pośrednich
    //służy także do synchronizacji obliczeń
  SuccCtr: integer; //licznik do badania kolejności wykonywania zadań
                    //przez wszystkie wątki

implementation

{$R *.dfm}

constructor TThreadCalc.CreateWithPar(aTag: integer; aFGetSucc: boolean = false);
  //tworzy wątek
  //jeśli aFGetSucc = true zbiera informacje o kolejności
var
  iJob: integer;
begin
  Tag := aTag;
  FGetSucc := aFGetSucc;
  for iJob := 0 to JobCount - 1 do //ustawienie flag wartości
                                   //na brak gotowości do dalszych obliczeń
  begin
    Value[iJob, Tag].IsInt := false;
    Value[iJob, Tag].IsStr := false;
  end;
  Self := Create(false);
end;

procedure TThreadCalc.GetData; //pobranie danej do obliczenia silni
begin
  Value[Job, Tag].IntValue := StrToInt(Form1.Edits[Job, 0].Text);
  Value[Job, Tag].IsInt := true;
end;

procedure TThreadCalc.PutData; //wyświetlenie wyników pośrednich
                               //lub kolejności
var
  iJob: integer;
begin
  if not FGetSucc then
  begin
    for iJob := 1 to JobCount - 1 do
      if Value[iJob, Tag].IsInt then
        Form1.Edits[iJob, Tag].Text := IntToStr(Value[iJob, Tag].IntValue)
      else
      if Value[iJob, Tag].IsStr then
        Form1.Edits[iJob, Tag].Text := Value[iJob, Tag].StrValue
      else
        Form1.Edits[iJob, Tag].Text := '';
  end
  else
    for iJob := 0 to JobCount - 1 do
      Form1.Edits[iJob, Tag].Text := IntToStr(Succ[iJob]);
  if Tag = 0 then
    Form1.Edits[0, Tag].ReadOnly := false;
end;

procedure TThreadCalc.CalcProc; //procedura obliczeniowa
  procedure Job0;
  begin
    Job := 0;
    Synchronize(GetData); //używamy Synchronize po pobieramy daną z Form1
                          //tj. wątku głównego
    GetSucc;
  end;
  procedure Job1; //zadanie przygotowuje iloczyn częściowy
                  //np. dla 12! i Tag = 1 jest to 4 * 5 * 6
  var
    s: string;
    v: int64;
    i: integer;
    Max, Min: int64;
  begin
    Job := 1;
    v := Value[Job - 1, Tag].IntValue;
    Min := Tag + Tag * (v div (ThreadCount + 1)) + 1;
    Max := Tag + (Tag + 1) * (v div (ThreadCount + 1)) + 1;
    if Tag = ThreadCount - 1 then
      Max := v;
    if Max > v then
      Max := v;
    for i := Min to Max do
     if i = Min then
       s := IntToStr(i)
     else
       s := s + '*' + IntToStr(i);
    if s = '' then
     s := '1';
    Value[Job, Tag].StrValue := s;
    Value[Job, Tag].IsStr := true;
    GetSucc;
  end;
  procedure Job2; //zadanie wylicza wartość iloczynu częściowego
  var
    v: int64;
    s: string;
  begin
    Job := 2;
    s := Value[Job - 1, Tag].StrValue;
    v := 1;
    s := s + '*';
    while Pos('*', s) > 0 do
    begin
      v := v * StrToInt(Copy(s, 1, Pos('*', s) - 1));
      s := Copy(s, Pos('*', s) + 1, Length(s));
    end;
    Value[Job, Tag].IntValue := v;
    Value[Job, Tag].IsInt := true;
    GetSucc;
  end;
  procedure Job3; //zadanie mnoży iloczyny częściowe
                  //np. dla Tag = 1 jest to
                  //iloczyn_częściowy(Tag = 0) * iloczyn_częściowy(Tag = 1)
                  //w zadaniu występuje synchronizacja wątków
  begin
    Job := 3;
    if Tag = 0 then
    begin
      Value[Job, Tag].IntValue := Value[Job - 1, Tag].IntValue;
      Value[Job, Tag].IsInt := true;
    end
    else
    begin
      while not Value[Job, Tag - 1].IsInt do //synchronizacja wątków
        ;                                    //tu: oczekiwanie na zakończenie
                                             //obliczeń przez wątek (Tag - 1)
      Value[Job, Tag].IntValue :=
        Value[Job - 1, Tag].IntValue * Value[Job, Tag - 1].IntValue;
      Value[Job, Tag].IsInt := true;
    end;
    GetSucc;
    Synchronize(PutData); //używamy Synchronize bo wpisujemy dane do Form1
                          //tj. wątku głównego
    Terminate; //jest to ostatnie zadanie i kończy wątek
  end;
begin
  Job0;
  Job1;
  Job2;
  Job3;
end;

procedure TThreadCalc.GetSucc;
begin
  if not FGetSucc then
    Exit;
  Inc(SuccCtr);
  Succ[Job] := SuccCtr;
end;


procedure TThreadCalc.Execute;
begin
  FreeOnTerminate := true;
  Priority := tpNormal;
  CalcProc;
end;

procedure TForm1.Calc(Sender: TObject); //uruchamia obliczenia
begin
  try
    if StrToInt(Edits[0, 0].Text) in [0..20] then
    begin
      Edits[0, 0].ReadOnly := true;
      if (Sender as TButton).Tag = 0 then
        RunThreads
      else
      if (Sender as TButton).Tag = 1 then
        RunThreads(true);
    end;
  except
  end;
end;

procedure TForm1.RunThreads(aFGetSucc: boolean = false); //uruchamia wszystkie wątki
var
  iThread: integer;
begin
  ClearEdits(nil);
  SuccCtr := 0;
  for iThread := 0 to ThreadCount - 1 do
    Threads[iThread] := TThreadCalc.CreateWithPar(iThread, aFGetSucc);
end;

procedure TForm1.TimerTimer(Sender: TObject);
begin
  Application.ProcessMessages;
end;

procedure TForm1.ClearEdits(Sender: TObject); //czyści edity
var
  iJob, iThread: integer;
begin
  for iJob := 0 to JobCount - 1 do
    for iThread := 0 to ThreadCount - 1 do
      if not ((iJob = 0) and (iThread = 0)) then
        Edits[iJob, iThread].Text := '';
end;


procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);
//należy powiązać z OnClose w ObjectInspectorze
var
  iThread: integer;
begin
  for iThread := 0 to ThreadCount - 1 do
    try
      Threads[iThread].Terminate;
    except
    end;
end;

procedure TForm1.FormCreate(Sender: TObject);
//tworzy wszystko co jest potrzebne do sprawdzenia jak to działa
//należy powiązać z OnCreate w ObjectInspectorze
const
  constWidth = 240;
  constHeight = 21;
var
  iJob, iThread: integer;
  l: TLabel;
  b: TButton;
begin
  Width      := 1000;
  Height     := 600;
  Position   := poScreenCenter;
  Font.Name  := 'Tahoma';
  Font.Size  := 8;
  Caption := 'Obliczanie silni na 4 wątkach, podaj wartość od 0 do 20';
  for iJob := 0 to JobCount - 1 do
  begin
    l := TLabel.Create(Self);
    l.Left := 10 + iJob * constWidth;
    l.Top  := 14;
    case iJob of
      0   : l.Caption := 'Zadanie ' + IntToStr(iJob) + ', wejście';
      1, 2: l.Caption := 'Zadanie ' + IntToStr(iJob);
      3   : l.Caption := 'Zadanie ' + IntToStr(iJob) + ', wyjście';
    end;

    InsertControl(l);
    for iThread := 0 to ThreadCount - 1 do
    begin
      Edits[iJob, iThread]       := TEdit.Create(Self);
      Edits[iJob, iThread].Width := constWidth;
      Edits[iJob, iThread].Left  := 10 + iJob * constWidth;
      Edits[iJob, iThread].Top   := 30 + iThread * constHeight;
      if not ((iJob = 0) and (iThread = 0)) then
        Edits[iJob, iThread].ReadOnly := true;
      InsertControl(Edits[iJob, iThread]);
    end;
  end;
  Edits[0, 0].OnChange := ClearEdits;
  Edits[0, 0].Color := clYellow;
  Edits[JobCount - 1, ThreadCount - 1].Color := clLime;
  b := TButton.Create(Self);
  b.Left := Edits[0, 0].Left;
  b.Top  := 30 + ThreadCount * constHeight;
  b.Width := constWidth;
  b.Tag := 0;
  b.Caption := 'Oblicz';
  b.OnClick := Calc;
  InsertControl(b);
  b := TButton.Create(Self);
  b.Left := Edits[1, 0].Left;
  b.Top  := 30 + ThreadCount * constHeight;
  b.Width := constWidth;
  b.Tag := 1;
  b.Caption := 'Kolejność';
  b.OnClick := Calc;
  InsertControl(b);
  Timer := TTimer.Create(Self);
  Timer.Interval := 100;
  Timer.OnTimer := TimerTimer;
  Timer.Enabled := true;
end;

end.