Komputery równoległe (po co?): *prognozowanie zjawisk przyrody, *symulacja powstania i rozchodzenia się zanieczyszczeń atmosferze, *poszukiwanie złóż surowców naturalnych, *badanie zjawisk przepływowych, *badanie wytrzymałości, *badania podstawowe w zakresie fizyki, chemii, biologii molekularnej. Komputery równoległe (działanie): *większa liczba procesorów, *podzielenie zadania obliczeniowego na części nie związane, lub słabo związane z innymi, *przydzielenie tych części do oddzielnych procesorów, *wykonanie obliczeń Komputery równoległe (zadania): *wybór modułu programowania równoległego, *dobór typu architektury komputerowej do problemu, *wybór odpowiedniego algorytmu obliczeniowego i jego implementacja programowa, *dobór narzędzi programowych. Klasyfikacja architektur komputerowych: *sterowanie instrukcji, *sterowanie danymi, *mechanizm sterowania, *organizacja przestrzeni adresowej, *granulacja procesorów. Mechanizm sterowania (klasyfikacja Flyrna 1972) *strumień instrukcji (rozkazów), *strumień danych. SISD - Single Instruction stream Single Data stream; SIMD - Single Instruction stream Multiple Data stream Procesory macierzowe MIMD - Multiple Instruction stream Multiple Data stream; MISD - Multiple Instruction stream Single Data stream Organizacja przestrzeni adresowej: *Pamięć wspólna (niewielka liczba procesorów; 1)SGI Power Challenge (do 36 procesorów); 2)HP V2500 (do 32 procesorów); 3)SUN Enterprise 10000 (64 prosesory); 4)SMP - symetryczna wieloprocesorowość) *Pamięć rozproszona (a) architektury z przesyłaniem komunikatów (wiadomości): *wczesne konstrukcje (1 komp. 1 system oper.); *współczesne - architektura wielokomputerowa (n oddzielnych komputerów) (MPP) 1)IBM RS6000SP; 2)Inlet Paragon XP/S; 3)klastry komputerów b) architektury z pamięcią fizycznie rozproszoną, lecz wirtualnie wspólną DSM VSM; równoległość danych; NUMA (niejednolity dostęp do pamięci) przykłady systemów NUMA: 1)HIV2500SCA; 2)Racy T3D/E; 3)SGI Origin 2000) SYSTEMY SIECIOWE *systemy rozproszone (zbudowane z komputerów różnych klas) (usługi sieciowe); *klastry (prawie zawsze zawierają komp. tego samego typu) (obliczenia, specjalizowane usługi wysokiej dostępności) PODZIAŁ ZE WZGL. NA GRANULACJĘ PROCESÓW Granulacja - stosunek czasu przeznaczonego do wykonania elementarnej operacji komunikacji do czasu realizacji elementarnej operacji obliczeniowej *komputery drobnoziarniste (fine grained) charakteryzują się dużą granulacją, częstą komunikacją między procesami; *komputery gruboziarniste (coarse grained) mała granulacja, rzadsza komunikacja między procesami TEORET. MODEL KOMPUTERA RÓWNOLEGŁEGO: 1)Założenia modelu: *n procesorów ma dostęp do m komórek wspólnej pamięci o dowolnych adresach i dostęp jest realizowany w stałym czasie (identycznym dla procesów i adresów) PRAM - maszyna o równoległym dostępie swobodnym; Równoczesny dostęp do pamięci (zapis; odczyt; zapis i odczyt) 1.Model PRAM z równoczesnym odczytem - CREW PRAM 2.Model PRAM z równoczesnym zapisem - ERCE PRAM 3.Model PRAM z równoczesnym zapisem i odczytem - CRCW PRAM Strategie: *procesorom przydziela się priorytety i zwycięża ten procesor, który ma najwyższy priorytet; *równoległy zapis tej samej wartości; *zapis sumy (logicznej) wartości. Model EREW - niedozwolony równoczesny dostęp) Stosowane do: *algorytmów teorii grafów; *algorytmów sortowania; *algorytmów algebry nieliniowej; STRUKTURA SIECI POŁĄCZEŃ (połączenia międyprocesorowe): 1) Statyczne sieci połączeń (połączenia pasywne i nierekonfigurowalne) Parametry: p - liczba bezpośrednich połączeń; c - max liczba połączeń obsługiwanych przez procesor; d - średnica sieci = liczba połączeń między-procesorowych składająca się na najdłuższą ścieżkę Sieć o pełnym połączeniu: p=n(n-1)/2=0(n²) Szereg: p=n-1=0(n); c=2; d=n-1; Stosowane do: *algorytmów sortowania; *mnożenia macierzy Krata: *krata toroidalna; *krata klasyczna !Szereg i kratę zaliczamy do struktury typu siatka (mesh)! q - wymiar; q=1 (szereg); q=2 (krata); liczba połączeń dla siatki =2q; Zastosowanie architektury kraty: *sortowanie; *rozwiązywanie układów równań różniczkowych; *algorytmy grafowe Drzewo binarne: Zastosowanie: *równoległe przeszukiwanie plików; *mnożenia macierzy przez wektor; *składowe spójne (w grafice) Piramida: Zastosowanie: *algorytmy graficzne; *algorytmy przetwarzania obrazów; Sieć przetasowana n=2^k procesorów; procesory ponumerowane i=0,1,..., n-1łączenie: i -> 2i mod (n-1) - łącza tasowania; 2i <-> 2i +1- łącza wymiany; Zastosowanie: *transpozycja macierzy; *mnożenie macierzy; *sortowanie; *algorytmy graficzne Hiper sześcian (n-sześcian) n=2^k; k - sąsiadów; Łączenia polegają na różnicy jednego bita. Liczba, symbol k jest również nazywana wymiarem kiper. sześcianu. Zastosowanie: *mnożenie macierzy; *sortowanie; obliczanie wartości własnych macierzy; *algorytmy graficzne DYNAMICZNE SIECI POŁĄCZEŃ Rodzaje: *sieć jednostopniowa; *sieć wielostopniowa SPOSOBY POŁĄCZEŃ PROCESORY - PAMIĘĆ WSPÓLNA 1)System ze wspólną magistralą. Cechy: *małą złożoność funkcjonalna; *mały koszt; *trwałość rekonfiguracji; *„wąskie gardło” Arbirator - steruje dostępem do magistrali Metody: *metoda priorytetów statycznych; *metoda priorytetów dynamicznych; *metoda stałego kwantu czasu (z urządzeń ma dostęp do magistrali); *metoda kolejowa System z przełącznicą krzyżową: Cechy charakterystyczne: *duża złożoność funkcjonalna; *dużą przepustowość; *trudność rozbudowy Systemy z pamięcią wieloportową: Cechy: *kosztowna pamięć; *ograniczenie konfiguracji; *duża liczba przewodów MIARY EFEKTYW. OBL. RÓWNOLEGŁYCH Od czego zależy efektywność (jakościowo): *wielkość problemu obliczeniowego; *użyty algorytm; *liczba procesorów; *model programowania; *rodzaj architektury; n -wielkość zadania (liczba instrukcji, rozmiar danych);

==========================================================================================

p -liczba procesorów; T(n,p) -czas wykonania programu realizującego ten sam algorytm dla zadania o wielkości n na komputerze o liczbie procesorów p; S(n,p) -przyśp. realizacji zadania o wielkości n dzięki zrównolegleniu na p procesorów; S(n,p)=T(n,p)/(n,p)≤p; S(n,p)=p gdy zadanie można podzielić na n równych podzadań i przydzielić je do p procesorów; S(n,p)=T(n,1)/[T(n,1)/p]=p; S(n,p)=(t_s+t_r)/(t_s+t_r/p); t_s=f(n)T(n,1); t_r=(1-f(n))T(n,1); S(n,p)=1/[f(n)+(1-f(n))/p]=p/[1+(p-1)f(n)]; f(n)-prawo Amdahla; Aby przyśpieszenie było duże ułamek musi być mały. lim_p∞S(n,p)=1/f(n). Innym parametrem jest: *wydajność (ŋ) - stosunek przyśp. rzeczywistego do przyśpieszenia idealnego; ŋ(n,p)= =S(n,p)/p; Wydajność to względne przyśpieszenie; to % czasu wykonania zadania wykonanego przez procesory. koszt = czas obliczeń*liczba użytych procesorów; koszt obliczeń sekwencyjnych =T(n,1); koszt obliczeń równoległych =T(n,p)p=pT(n,1)/S(n,p)=T(n,1)/ŋ(n,p); *skalowalność - własność systemu (sprzętu i oprogramowania) polegająca na elastycznym dostos. się do zwiększającej się liczby procesorów tzn. zachowaniu w przybliżeniu tej samej wydajności systemu (ŋ). Jeżeli zwiększamy liczbę procesorów to zwiększa się czas transmisji (przyśpieszenie spada)wydajność spada; ŋ(n,p)=(n,p)/p=1/[1+(p-1)f(n)]; Funkcja stałej wydajności F_ISO Funkcja, która podaje przy zmieniającej się liczbie procesorów wielkość zadania. KOMPUTERY MACIERZOWE Wchodzą w skład klasy SIMD; Skalary (pojedyncza dana) rozkazy skalarne; Zbiory danych skalarnych rozkazy wektorów. Procesor macierzowy nie jest samodzielnym komputerem - jest podłączony do zwykłego komputera. Przykłady algorytmów realizowanie w procesie macierzowym: 1. Algorytm wyznaczania ciągu sum. for i:=0 to n do A[i+1]:=B[i]+A[i]; A[1]:=B[0]+A[0]; A[2]:=B[0]+B[1]+A[0]; …; A[n+1]:=B[0]+…+B[n]+A[0]; S_k=Σ_[k;i=0]B[i] ,k=0,1,…,n; Algorytm sortowania bąbelkowego: porównujesz od prawej do lewej sąsiednie cyfry i jak prawa mniejsza od lewej to je przestawiasz; n(n-1)/2=0(n²) operacji; C²_n=(ⁿ₂) Algorytm równoległy: n=0(n) PROGR. SYST. WIELOPROCESOROWYCH: Problemy: 1. Podział programu na zadania. 2. Dobór języka programowania równoległego. 3. Przydział zadań procesorom. 4. Komunikacja między procesorami i synchronizacja ich pracy. ad.1)Zadania współbieżne - fragmenty programu, które można wykonywać w tym samym czasie. Zadaniami są procedury. for i:=1 to N do P1: for i:=1 to N div 2 do || P2: for i:=N div 2+1 to N do ad.2)Algol60; Algol68 (Dijkstra) {cobegin .. coend; możliwe zagnieżdżenia}; Concurrent Pascal; Modula; Ada {C DINO, ParallelDistributed C, PC, DataParallel C} {Fortran 90, Fortran D, Vienna Fortran, HPF} {Occam notacja CSP; programowe kanały} {Linda - przestrzeń krotek (ang. tuple space)} {Strand} {Schedule} ad.3) Przydział zadań procesorom: *wystepowanie w zadaniach instrukcji warunkowych; *zmienna szybkość pracy procesorów; *komunikacja międzyprocesorowa (konflikty w: *dostępie do wspólnej pamięci (syst. ze wspólną pamięcią); *przesyłaniem komunikatów przez wspólną sieć (krzyżowanie się w marszu)); *przydział statyczny; *przydział dynamiczny (zadania przydzielane procesorom w trakcie działania programu) ad.4)Komunikacja przez: a)zmienne dzielone (wspólne); b)przesyłanie komunikatów ad.a) Zmienne dzielone - sposoby synchronizacji: *aktywne czekanie; *semafory; *monitory Cele synchronizacji przez zmienne dzielone: *sterowanie interferencją procesów; *porządkowanie zdarzeń; *sekcja krytyczna - ciąg instrukcji wykonywanych w 1 odcinku czasowym w ramach 1 procesu jako operacja jednostkowa i niepodzielna s:=s+e_i P_i Przy wykonywaniu sekcji krytycznych zachodzi wykluczanie wzajemne Aktywne czekanie Pojedyncza zmienna (flaga) *mała liczba procesów; *krótkie sekcje krytyczne SEMAFORY (Dijkstra) Semafor - zm. całkowita mogąca przyjmować jedynie wartość nieujemną. Stowarzyszona jest z nią kolejka, w której ustawiają się procesy oczek. na dostęp do zasobów. Kolejka: *regulamin naturalny (FIFO - First In First Out, FCFS) (P3P2 P1ððððððððððP3P2P1); *regulamin stosowy (P3P2P1stosP1P2P3);♦S (semafor); P(S): if s=0 then zawieszanie procesów i ustawianie go w kolejce; S:=S-1; V(S): S:=S+1; semafor binarny S={0,1}; P(S)sekcja krytycznaV(S)♦ Użycie semafora do synchronizacji [I₁:begin; …; P(s); Obliczenia;; …; end; ][ I₂:begin; …; V(s); Obliczenia;; …; end;] Zadanie o producencie i konsumencie Synchr. dostępu. Synchronizacja producent produkuje jeżeli są wolne miejsca w magazynie w przeciwnym czasie czeka konsument pobiera z magazynu jak coś jest jak nie ma to czeka. Jak producent coś wytworzył to daje to do magazynu to daje o tym znać konsumentowi jeżeli konsument pobrał coś z magazynu i zwolnił miejsce to daje o tym znać producentowi. PRODUCENT{while do true do►begin►wytwórz produkt►if brak wolnych miejsc w magazynie►then czekaj►złóż produkt zapisz że dodano jedną sztukę produktu;►if konsument czeka►then zaktywizuj go ►end;►|| while true do begin►P(m){wytwórz produkt; if m=0 then czekaj;►m:=m-1;►złóż produkt;►V(p){ p=p+1; if konsument czeka then zaktywizuj go►end►|| while true do ►begin►wytwórz produkt►P(m)►złóż produkt;►V(p)►End;} KONSUMENT {while true do► begin►if brak produktów produktów magazynie ►then pobierz produkt►zapisz, że pobrano jedną sztukę produktu;►if producent czeka►then zaktywizuj go;►wykorzystuje produkt►end;►|| while true do►begin►P(p){ it p=o then czekaj p:=p-1►Pobierz produkt►V(m){m:= m+1; if producent then zaktywizuj go; wykorzystaj produkt►end ►|| while true do ►begin►P(p);►Pobierz produkt,►V(m)►wykorzysta produkt►end}

Komputery równoległe (po co?): *prognozowanie zjawisk przyrody, *symulacja powstania i rozchodzenia się zanieczyszczeń atmosferze, *poszukiwanie złóż surowców naturalnych, *badanie zjawisk przepływowych, *badanie wytrzymałości, *badania podstawowe w zakresie fizyki, chemii, biologii molekularnej. Komputery równoległe (działanie): *większa liczba procesorów, *podzielenie zadania obliczeniowego na części nie związane, lub słabo związane z innymi, *przydzielenie tych części do oddzielnych procesorów, *wykonanie obliczeń Komputery równoległe (zadania): *wybór modułu programowania równoległego, *dobór typu architektury komputerowej do problemu, *wybór odpowiedniego algorytmu obliczeniowego i jego implementacja programowa, *dobór narzędzi programowych. Klasyfikacja architektur komputerowych: *sterowanie instrukcji, *sterowanie danymi, *mechanizm sterowania, *organizacja przestrzeni adresowej, *granulacja procesorów. Mechanizm sterowania (klasyfikacja Flyrna 1972) *strumień instrukcji (rozkazów), *strumień danych. SISD - Single Instruction stream Single Data stream; SIMD - Single Instruction stream Multiple Data stream Procesory macierzowe MIMD - Multiple Instruction stream Multiple Data stream; MISD - Multiple Instruction stream Single Data stream Organizacja przestrzeni adresowej: *Pamięć wspólna (niewielka liczba procesorów; 1)SGI Power Challenge (do 36 procesorów); 2)HP V2500 (do 32 procesorów); 3)SUN Enterprise 10000 (64 prosesory); 4)SMP - symetryczna wieloprocesorowość) *Pamięć rozproszona (a) architektury z przesyłaniem komunikatów (wiadomości): *wczesne konstrukcje (1 komp. 1 system oper.); *współczesne - architektura wielokomputerowa (n oddzielnych komputerów) (MPP) 1)IBM RS6000SP; 2)Inlet Paragon XP/S; 3)klastry komputerów b) architektury z pamięcią fizycznie rozproszoną, lecz wirtualnie wspólną DSM VSM; równoległość danych; NUMA (niejednolity dostęp do pamięci) przykłady systemów NUMA: 1)HIV2500SCA; 2)Racy T3D/E; 3)SGI Origin 2000) SYSTEMY SIECIOWE *systemy rozproszone (zbudowane z komputerów różnych klas) (usługi sieciowe); *klastry (prawie zawsze zawierają komp. tego samego typu) (obliczenia, specjalizowane usługi wysokiej dostępności) PODZIAŁ ZE WZGL. NA GRANULACJĘ PROCESÓW Granulacja - stosunek czasu przeznaczonego do wykonania elementarnej operacji komunikacji do czasu realizacji elementarnej operacji obliczeniowej *komputery drobnoziarniste (fine grained) charakteryzują się dużą granulacją, częstą komunikacją między procesami; *komputery gruboziarniste (coarse grained) mała granulacja, rzadsza komunikacja między procesami TEORET. MODEL KOMPUTERA RÓWNOLEGŁEGO: 1)Założenia modelu: *n procesorów ma dostęp do m komórek wspólnej pamięci o dowolnych adresach i dostęp jest realizowany w stałym czasie (identycznym dla procesów i adresów) PRAM - maszyna o równoległym dostępie swobodnym; Równoczesny dostęp do pamięci (zapis; odczyt; zapis i odczyt) 1.Model PRAM z równoczesnym odczytem - CREW PRAM 2.Model PRAM z równoczesnym zapisem - ERCE PRAM 3.Model PRAM z równoczesnym zapisem i odczytem - CRCW PRAM Strategie: *procesorom przydziela się priorytety i zwycięża ten procesor, który ma najwyższy priorytet; *równoległy zapis tej samej wartości; *zapis sumy (logicznej) wartości. Model EREW - niedozwolony równoczesny dostęp) Stosowane do: *algorytmów teorii grafów; *algorytmów sortowania; *algorytmów algebry nieliniowej; STRUKTURA SIECI POŁĄCZEŃ (połączenia międyprocesorowe): 1) Statyczne sieci połączeń (połączenia pasywne i nierekonfigurowalne) Parametry: p - liczba bezpośrednich połączeń; c - max liczba połączeń obsługiwanych przez procesor; d - średnica sieci = liczba połączeń między-procesorowych składająca się na najdłuższą ścieżkę Sieć o pełnym połączeniu: p=n(n-1)/2=0(n²) Szereg: p=n-1=0(n); c=2; d=n-1; Stosowane do: *algorytmów sortowania; *mnożenia macierzy Krata: *krata toroidalna; *krata klasyczna !Szereg i kratę zaliczamy do struktury typu siatka (mesh)! q - wymiar; q=1 (szereg); q=2 (krata); liczba połączeń dla siatki =2q; Zastosowanie architektury kraty: *sortowanie; *rozwiązywanie układów równań różniczkowych; *algorytmy grafowe Drzewo binarne: Zastosowanie: *równoległe przeszukiwanie plików; *mnożenia macierzy przez wektor; *składowe spójne (w grafice) Piramida: Zastosowanie: *algorytmy graficzne; *algorytmy przetwarzania obrazów; Sieć przetasowana n=2^k procesorów; procesory ponumerowane i=0,1,..., n-1łączenie: i -> 2i mod (n-1) - łącza tasowania; 2i <-> 2i +1- łącza wymiany; Zastosowanie: *transpozycja macierzy; *mnożenie macierzy; *sortowanie; *algorytmy graficzne Hiper sześcian (n-sześcian) n=2^k; k - sąsiadów; Łączenia polegają na różnicy jednego bita. Liczba, symbol k jest również nazywana wymiarem kiper. sześcianu. Zastosowanie: *mnożenie macierzy; *sortowanie; obliczanie wartości własnych macierzy; *algorytmy graficzne DYNAMICZNE SIECI POŁĄCZEŃ Rodzaje: *sieć jednostopniowa; *sieć wielostopniowa SPOSOBY POŁĄCZEŃ PROCESORY - PAMIĘĆ WSPÓLNA 1)System ze wspólną magistralą. Cechy: *małą złożoność funkcjonalna; *mały koszt; *trwałość rekonfiguracji; *„wąskie gardło” Arbirator - steruje dostępem do magistrali Metody: *metoda priorytetów statycznych; *metoda priorytetów dynamicznych; *metoda stałego kwantu czasu (z urządzeń ma dostęp do magistrali); *metoda kolejowa System z przełącznicą krzyżową: Cechy charakterystyczne: *duża złożoność funkcjonalna; *dużą przepustowość; *trudność rozbudowy Systemy z pamięcią wieloportową: Cechy: *kosztowna pamięć; *ograniczenie konfiguracji; *duża liczba przewodów MIARY EFEKTYW. OBL. RÓWNOLEGŁYCH Od czego zależy efektywność (jakościowo): *wielkość problemu obliczeniowego; *użyty algorytm; *liczba procesorów; *model programowania; *rodzaj architektury; n -wielkość zadania (liczba instrukcji, rozmiar danych);

==========================================================================================

p -liczba procesorów; T(n,p) -czas wykonania programu realizującego ten sam algorytm dla zadania o wielkości n na komputerze o liczbie procesorów p; S(n,p) -przyśp. realizacji zadania o wielkości n dzięki zrównolegleniu na p procesorów; S(n,p)=T(n,p)/(n,p)≤p; S(n,p)=p gdy zadanie można podzielić na n równych podzadań i przydzielić je do p procesorów; S(n,p)=T(n,1)/[T(n,1)/p]=p; S(n,p)=(t_s+t_r)/(t_s+t_r/p); t_s=f(n)T(n,1); t_r=(1-f(n))T(n,1); S(n,p)=1/[f(n)+(1-f(n))/p]=p/[1+(p-1)f(n)]; f(n)-prawo Amdahla; Aby przyśpieszenie było duże ułamek musi być mały. lim_p∞S(n,p)=1/f(n). Innym parametrem jest: *wydajność (ŋ) - stosunek przyśp. rzeczywistego do przyśpieszenia idealnego; ŋ(n,p)= =S(n,p)/p; Wydajność to względne przyśpieszenie; to % czasu wykonania zadania wykonanego przez procesory. koszt = czas obliczeń*liczba użytych procesorów; koszt obliczeń sekwencyjnych =T(n,1); koszt obliczeń równoległych =T(n,p)p=pT(n,1)/S(n,p)=T(n,1)/ŋ(n,p); *skalowalność - własność systemu (sprzętu i oprogramowania) polegająca na elastycznym dostos. się do zwiększającej się liczby procesorów tzn. zachowaniu w przybliżeniu tej samej wydajności systemu (ŋ). Jeżeli zwiększamy liczbę procesorów to zwiększa się czas transmisji (przyśpieszenie spada)wydajność spada; ŋ(n,p)=(n,p)/p=1/[1+(p-1)f(n)]; Funkcja stałej wydajności F_ISO Funkcja, która podaje przy zmieniającej się liczbie procesorów wielkość zadania. KOMPUTERY MACIERZOWE Wchodzą w skład klasy SIMD; Skalary (pojedyncza dana) rozkazy skalarne; Zbiory danych skalarnych rozkazy wektorów. Procesor macierzowy nie jest samodzielnym komputerem - jest podłączony do zwykłego komputera. Przykłady algorytmów realizowanie w procesie macierzowym: 1. Algorytm wyznaczania ciągu sum. for i:=0 to n do A[i+1]:=B[i]+A[i]; A[1]:=B[0]+A[0]; A[2]:=B[0]+B[1]+A[0]; …; A[n+1]:=B[0]+…+B[n]+A[0]; S_k=Σ_[k;i=0]B[i] ,k=0,1,…,n; Algorytm sortowania bąbelkowego: porównujesz od prawej do lewej sąsiednie cyfry i jak prawa mniejsza od lewej to je przestawiasz; n(n-1)/2=0(n²) operacji; C²_n=(ⁿ₂) Algorytm równoległy: n=0(n) PROGR. SYST. WIELOPROCESOROWYCH: Problemy: 1. Podział programu na zadania. 2. Dobór języka programowania równoległego. 3. Przydział zadań procesorom. 4. Komunikacja między procesorami i synchronizacja ich pracy. ad.1)Zadania współbieżne - fragmenty programu, które można wykonywać w tym samym czasie. Zadaniami są procedury. for i:=1 to N do P1: for i:=1 to N div 2 do || P2: for i:=N div 2+1 to N do ad.2)Algol60; Algol68 (Dijkstra) {cobegin .. coend; możliwe zagnieżdżenia}; Concurrent Pascal; Modula; Ada {C DINO, ParallelDistributed C, PC, DataParallel C} {Fortran 90, Fortran D, Vienna Fortran, HPF} {Occam notacja CSP; programowe kanały} {Linda - przestrzeń krotek (ang. tuple space)} {Strand} {Schedule} ad.3) Przydział zadań procesorom: *wystepowanie w zadaniach instrukcji warunkowych; *zmienna szybkość pracy procesorów; *komunikacja międzyprocesorowa (konflikty w: *dostępie do wspólnej pamięci (syst. ze wspólną pamięcią); *przesyłaniem komunikatów przez wspólną sieć (krzyżowanie się w marszu)); *przydział statyczny; *przydział dynamiczny (zadania przydzielane procesorom w trakcie działania programu) ad.4)Komunikacja przez: a)zmienne dzielone (wspólne); b)przesyłanie komunikatów ad.a) Zmienne dzielone - sposoby synchronizacji: *aktywne czekanie; *semafory; *monitory Cele synchronizacji przez zmienne dzielone: *sterowanie interferencją procesów; *porządkowanie zdarzeń; *sekcja krytyczna - ciąg instrukcji wykonywanych w 1 odcinku czasowym w ramach 1 procesu jako operacja jednostkowa i niepodzielna s:=s+e_i P_i Przy wykonywaniu sekcji krytycznych zachodzi wykluczanie wzajemne Aktywne czekanie Pojedyncza zmienna (flaga) *mała liczba procesów; *krótkie sekcje krytyczne SEMAFORY (Dijkstra) Semafor - zm. całkowita mogąca przyjmować jedynie wartość nieujemną. Stowarzyszona jest z nią kolejka, w której ustawiają się procesy oczek. na dostęp do zasobów. Kolejka: *regulamin naturalny (FIFO - First In First Out, FCFS) (P3P2 P1ððððððððððP3P2P1); *regulamin stosowy (P3P2P1stosP1P2P3);♦S (semafor); P(S): if s=0 then zawieszanie procesów i ustawianie go w kolejce; S:=S-1; V(S): S:=S+1; semafor binarny S={0,1}; P(S)sekcja krytycznaV(S)♦ Użycie semafora do synchronizacji [I₁:begin; …; P(s); Obliczenia;; …; end; ][ I₂:begin; …; V(s); Obliczenia;; …; end;] Zadanie o producencie i konsumencie Synchr. dostępu. Synchronizacja producent produkuje jeżeli są wolne miejsca w magazynie w przeciwnym czasie czeka konsument pobiera z magazynu jak coś jest jak nie ma to czeka. Jak producent coś wytworzył to daje to do magazynu to daje o tym znać konsumentowi jeżeli konsument pobrał coś z magazynu i zwolnił miejsce to daje o tym znać producentowi. PRODUCENT{while do true do►begin►wytwórz produkt►if brak wolnych miejsc w magazynie►then czekaj►złóż produkt zapisz że dodano jedną sztukę produktu;►if konsument czeka►then zaktywizuj go ►end;►|| while true do begin►P(m){wytwórz produkt; if m=0 then czekaj;►m:=m-1;►złóż produkt;►V(p){ p=p+1; if konsument czeka then zaktywizuj go►end►|| while true do ►begin►wytwórz produkt►P(m)►złóż produkt;►V(p)►End;} KONSUMENT {while true do► begin►if brak produktów produktów magazynie ►then pobierz produkt►zapisz, że pobrano jedną sztukę produktu;►if producent czeka►then zaktywizuj go;►wykorzystuje produkt►end;►|| while true do►begin►P(p){ it p=o then czekaj p:=p-1►Pobierz produkt►V(m){m:= m+1; if producent then zaktywizuj go; wykorzystaj produkt►end ►|| while true do ►begin►P(p);►Pobierz produkt,►V(m)►wykorzysta produkt►end}

---