Programowanie współbieżne
Programowanie współbieżne
" Program współbieżny opisuje zachowanie się zbioru
procesów współbieżnych.
" Rodzaje uzależnienia procesów współbieżnych:
 Rywalizacja, współzawodnictwo
 Współpraca
" Typy programów współbieżnych:
 Przetwarzanie potokowe
 Przetwarzanie potokowe wielowymiarowe
 Zbiór takich samych procesów
 Klient-serwer
Wzajemne wykluczanie
Wzajemne wykluczanie
" Zasób dzielony jest wspólnym obiektem, z którego może
korzystać w sposób wyłączny wiele procesów.
" Sekcja krytyczna to fragment procesu, w którym korzysta on z
obiektu dzielonego.
" Ponieważ w danej chwili z zasobu dzielonego może korzystać
tylko jeden proces, wykonując swoja sekcję krytyczną
uniemożliwia on wykonanie sekcji krytycznych innym
procesom.
" Problem wzajemnego wykluczania:
Zsynchronizować N procesów, z których każdy w
nieskończonej pętli na przemian zajmuje się własnymi
sprawami i wykonuje sekcję krytyczną, w taki sposób, aby
wykonanie sekcji krytycznych jakichkolwiek dwóch lub więcej
procesów nie pokrywało się w czasie.
Rozwiązanie problemu wzajemnego wykluczania
Rozwiązanie problemu wzajemnego wykluczania
" Należy do treści każdego procesu wprowadzić dodatkowe
instrukcje poprzedzające sekcję krytyczną (protokół wstępny) i
następujące bezpośrednio po sekcji krytycznej (protokół
końcowy).
" Założenia:
 Żaden proces nie może wykonywać swej sekcji krytycznej
nieskończenie długo
 Protokół wstępny i końcowy muszą być wykonane w skończonym
czasie
 Poza sekcją krytyczną zachowanie procesu nie może być
ograniczone
 Procesy mogą się wykonywać z różnymi dowolnie wybranymi
prędkościami.
Zakleszczenie i zagłodzenie
Zakleszczenie i zagłodzenie
" Zbiór procesów znajduje się w stanie zakleszczenia
(deadlock), jeśli każdy z tych procesów jest wstrzymany w
oczekiwaniu na zdarzenie, które może być spowodowane tylko
przez jakiś inny proces z tego zbioru.
" Proces jest w stanie zagłodzenia (starvation), jeśli nie zostaje
wznowiony mimo, że zdarzenie na które czeka występuje
dowolna ilość razy, gdyż za każdym razem jest wybierany inny
czekający proces.
Problem producenta i konsumenta
Problem producenta i konsumenta
" Należy zsynchronizować dwa procesy: producenta, który
cyklicznie produkuje jedną porcje informacji, a następnie
przekazuje ja do skonsumowania, i konsumenta, który
cyklicznie pobiera porcje i konsumuje ją.
" Między producentem a konsumentem znajduje się N-
elementowy bufor.
" Producent wstawia porcję do niepełnego bufora, a konsument
pobiera ją z niepustego bufora.
" Jeśli w danej chwili producent nie może pozbyć się
wyprodukowanej porcji, musi czekać.
" Jeśli konsument nie może pobrać porcji, także musi czekać.
" Porcje powinny być konsumowane w kolejności
wyprodukowania.
Problem czytelników i pisarzy
Problem czytelników i pisarzy
" Należy zsynchronizować dwie grupy cyklicznych procesów
konkurujących o dostęp do wspólnej czytelni.
" Proces czytelnik co jakiś czas odczytuje informacje
zgromadzoną w czytelni.
" Proces pisarz co jakiś czas zapisuje nową informację.
" Czytelnik może czytać razem z innymi czytelnikami.
" Pisarz musi przebywać sam w czytelni
" Operacje czytania i pisania nie trwają nieskończenie długo.
Mechanizmy niskopoziomowe do wzajemnego wykluczania
Mechanizmy niskopoziomowe do wzajemnego wykluczania
" Blokowanie przerwań:
1. Przed wejściem do sekcji krytycznej proces wywołuje odpowiednie przerwanie.
2. Procedura obsługi przerwania:
 zablokowanie (zamaskowanie) przerwania
 wykonanie sekcji krytycznej
 odblokowanie przerwania
" Specjalne instrukcje procesora:
 TEST&SET(X,R): X<-R; R<-0
 SWAP(X,R): tmp<-X; X<-R; R<-tmp
var R:=1; var R:=1
process A; process B;
begin begin
... ...
while R=0 do TEST&SET(X,R); C:=0;
{sekcja krytyczna} repeat SWAP(R,C)
R:=1; until C=0;
... {sekcja krytyczna}
end; R:=1;
...
end;
Semafory
Semafory
" Pierwszy mechanizm synchronizacyjny stosowany w językach
wysokiego poziomu (Dijkstra 1968 r.).
" Definicja klasyczna
Semafor całkowity (ogólny) S jest zmienną całkowitą z dwoma
wyróżnionymi operacjami:
 Podniesienie semafora V(S): S:=S+1
 Opuszczenie semafora P(S): Czekaj, aż S>0; S:=S-1.
Semafor binarny jest zmienną przyjmującą wartości 0 lub 1 z dwoma
wyróżnionymi operacjami:
 Podniesienie semafora VB(S): S:=1
 Opuszczenie semafora PB(S): Czekaj, aż S=1; S:=0.
" Zakłada się, że podniesienie i opuszczenie semafora są
operacjami niepodzielnymi
Semafory  definicja praktyczna
Semafory  definicja praktyczna
" Semafor ogólny:
 Opuszczenie semafora:
Jeśli S>0, to S:=S-1, w przeciwnym razie wstrzymaj działanie procesu
wykonującego te operacje;
 Podniesienie semafora:
Jeśli są procesy wstrzymane w wyniku wykonania operacji opuszczania
semafora S, to wznów jeden z nich, w przeciwnym razie S:=S+1
" Należy założyć, że sposób wyboru wznawianego procesu nie
spowoduje zagłodzenia żadnego z czekających procesów.
Semafory - Wzajemne wykluczanie
Semafory - Wzajemne wykluczanie
var S: binary semaphore := 1; {semafor chroniący
zasób dzielony}
process P(i:1..N);
begin
while true do begin
wlasne_sprawy;
PB(S);
sekcja_krytyczna;
VB(S)
end
end;
Semafory - Producent i konsument
Semafory - Producent i konsument
Semafory  Czytelnicy i pisarze
Semafory  Czytelnicy i pisarze
Semafory - Zakleszczenie
Semafory - Zakleszczenie
Implementacja semaforów
Implementacja semaforów
" Operacje P i V powinny być wykonywane jako niepodzielne
" Kolejka może być zrealizowana jako FIFO lub wg priorytetów
Standard POSIX
Standard POSIX
" POSIX - Portable Operating System Interface for Computer
Environment
" Zdefiniowany przez IEEE (Institute of Electrical and Electronic
Engineers)
" Określa sprzęg między systemem operacyjnym a światem
zewnętrznym (aplikacje i użytkownicy)
" Dynamiczny rozwój w latach 90-tych
" Zalety:
 zgodność aplikacji na poziomie kodu z
ródłowego (biblioteki C)
 jednakowe środowisko użytkownika (shell, polecenia)
 otwartość na różne zastosowania
Semafory w POSIX - przykład
Semafory w POSIX - przykład
void put(buffer_t *b, char item) { char get(buffer_t *b) {
sem_wait(&b->empty); char item;
typedef struct {
sem_wait(&b->pmut);
char buf[BSIZE];
sem_wait(&b->occupied);
sem_t occupied;
b->buf[b->nextin] = item;
sem_t empty;
b->nextin++; sem_wait(&b->cmut);
int nextin;
b->nextin %= BSIZE;
int nextout;
item = b->buf[b->nextout];
sem_t pmut;
sem_post(&b->pmut); b->nextout++;
sem_t cmut;
sem_post(&b->occupied); b->nextout %= BSIZE;
} buffer_t;
}
sem_post(&b->cmut);
buffer_t buffer;
sem_post(&b->empty);
sem_init(&buffer.occupied, 0, 0);
sem_init(&buffer.empty,0, BSIZE);
return(item);
sem_init(&buffer.pmut, 0, 1);
}
sem_init(&buffer.cmut, 0, 1);
buffer.nextin = buffer.nextout = 0;
Uruchomienie producenta i konsumenta (pthread_create)
sem_destroy(&buffer.occupied);
sem_destroy(&buffer.empty);
Inne funkcje: sem_trywait, sem_timedwait, sem_getvalue
sem_destroy(&buffer.pmut);
sem_destroy(&buffer.cmut);
Semafory w UNIX
Semafory w UNIX
" Rozszerzenia:
 Operacje opuszczania i podnoszenia mają dodatkowy parametr
umożliwiający zmianę wartości semafora nie o 1, ale o dowolną
ilość jednostek.
 Występują one w postaci nieblokującej  jeżeli proces nie może
natychmiast wykonać żądanej operacji, to rezygnuje z jej
wykonania.
 Operacje są wykonywane na zestawach semaforów. Semafory
należące do danego zestawu są ponumerowane kolejnymi
liczbami naturalnymi.
 Działania na wielu semaforach można grupować w operację
jednoczesną  jej zakończenie następuje wtedy, gdy wszystkie
operacje składowe są wykonalne.
Semafory w UNIX - przykład
Semafory w UNIX - przykład
#include void V(int semid) {
#include struct sembuf buf;
#include buf.sem_num = 0;
buf.sem_op = 1; /* zwiększenie
semafora o 1)
static int sem; /* id semafora */
buf.sem_flg = 0;
semop(semid, &buf, 1);
void P(int semid) {
}
struct sembuf buf; /* struktura
używana przy operacjach
semaforowych */
void main() {
//utworzenie semafora
buf.sem_num = 0; /* numer
sem = semget (1,1, IPC_CREAT |
semafora */
0666);
buf.sem_flg = 0; /*operacja
semctl (sem, 0, SETVAL, 1); /*
blokująca*/
inicjacja semafora wartością 1 */
buf.sem_op = -1; /* zmniejszenie
// Wykorzystanie funkcji P i V
semafora o 1)
P(sem);
semop(semid, &buf, 1);
. Tutaj sekcja krytyczna
}
V(sem);
}
Monitory
Monitory
" Koniec lat 70-tych (Hoare i Brinch Hansen)
" Monitor to zebrane w jednej konstrukcji programowej zmienne
i funkcje działające na tych zmiennych.
 Część funkcji jest udostępniana na zewnątrz monitora i tylko z ich
pomocą procesy mogą uzyskać dostęp do zmiennych ukrytych
wewnątrz monitora.
 Wykonanie procedury monitora jest sekcją krytyczną
wykonującego go procesu  w danej chwili tylko jeden z procesów
może wykonywać procedurę monitora.
 Z poziomu monitora można wstrzymywać i wznawiać procesy za
pomocą zmiennych typu condition:
" wait(c) - wstrzymanie procesu i wstawienie go na koniec kolejki
zmiennej c, z jednoczesnym zwolnieniem monitora,
" signal(c)  wznowienie pierwszego procesu wstrzymanego w kolejce
zmiennej c. (Jeśli operacja ta nie jest ostatnią instrukcją procedury monitorowej, to
proces jest wstrzymywany do chwili, gdy wznowiony przezeń proces zwolni monitor).
" empty(c)  sprawdzenie czy kolejka zmiennej c jest pusta.
Wykonanie procedury monitora
Wykonanie procedury monitora
Monitory  wzajemne wykluczanie
Monitory  wzajemne wykluczanie
Monitory  Producent i konsument
Monitory  Producent i konsument
Monitory  Producent i konsument c.d.
Monitory  Producent i konsument c.d.
Monitory  Czytelnicy i pisarze
Monitory  Czytelnicy i pisarze
Monitory  Czytelnicy i pisarze c.d.
Monitory  Czytelnicy i pisarze c.d.
Monitory w .NET
Monitory w .NET
" Skojarzone z obiektem
" Przestrzeń nazw System.Threading
" Z klasy Monitor nie tworzy się instancji
" Funkcje:
Enter
Exit
Wait
Pulse, PulseAll
Monitory w .NET - przykład
Monitory w .NET - przykład
public class Alpha
{
public void BetaThread()
{
int cLoop = 10;
while ((cLoop--) > 0)
{
Monitor.Enter(this);
Console.Write("{0} Thread",Thread.CurrentThread.Name);
Thread.Sleep(500);
Console.WriteLine("Id:{0}",Thread.CurrentThread.ManagedThreadId);
Monitor.Exit(this);
}
}
}
Regiony krytyczne
Regiony krytyczne
" Podczas wykonywania instrukcji wchodzących w skład regionu krytycznego,
żaden inny proces nie ma dostępu do zmiennej związanej z tym regionem
" Przykład (producent i konsument)
var reg_bufor: shared record
bufor: array[0..N-1] of porcja;
ile,do_włożenia,do_wyjęcia:integer;
end;
process KONSUMENT;
process PRODUCENT;
var p: porcja;
var p: porcja; begin
begin
while true do begin
while true do begin
region reg_bufor when ile>0
produkuj(p); do begin
region reg_bufor when ilep := bufor[do_wyjęcia];
do begin
do_wyjęcia := (do_ wyjęcia+1) mod N;
bufor[do_włożenia] := p;
ile = ile - 1;
do_włożenia := (do_włożenia+1) mod N;
end
ile = ile + 1;
konsumuj(p);
end
end
end
end;
end;
Transakcje niepodzielne
Transakcje niepodzielne
" Transakcja  zbiór instrukcji, które wykonują logicznie spójną funkcję
" Przy realizacji transakcji konieczne jest zachowanie jej niepodzielności mimo awarii lub
błędów  transakcja wykonuje się w całości albo wcale.
" Sposoby realizacji niepodzielności transakcji:
" Zapisywanie wszelkich zmian w rejestrze (log)
" Tworzenie punktów kontrolnych (checkpoints).
Czytanie: Pisanie:
Odrzuć, gdy wartość została zmieniona w czasie tej transakcji Odrzuć, gdy:
przez póz
niejszą transakcję (potrzebna wartość już nie
1. w czasie transakcji czytano wartość w póz
niejszej
istnieje)
transakcji (wartość już nie jest potrzebna)
2. w czasie transakcji zapisano nową wartość w póz
niejszej
transakcji (nie można zapisać wartości nieaktualnej)