Programowanie wsp

bie

• 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

• 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

• 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

• 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

• 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

• 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

•

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
process B;
begin
...
C:=0;
repeat SWAP(R,C)
until C=0;
{sekcja krytyczna}
R:=1;
...
end;

var R:=1;
process A;
begin
...
while R=0 do TEST&SET(X,R);
{sekcja krytyczna}
R:=1;
...
end;

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

• 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

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

Zakleszczenie

Implementacja semafor

• Operacje P i V powinny być wykonywane jako niepodzielne

• Kolejka może być zrealizowana jako FIFO lub wg priorytetów

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 źródłowego (biblioteki C)

– jednakowe środowisko użytkownika (shell, polecenia)

– otwartość na różne zastosowania

Semafory w POSIX

przyk

typedef struct {

char buf[BSIZE];

sem_t occupied;

sem_t empty;

int nextin;

int nextout;

sem_t pmut;

sem_t cmut;

} buffer_t;

buffer_t buffer;

sem_init(&buffer.occupied, 0, 0);

sem_init(&buffer.empty,0, BSIZE);

sem_init(&buffer.pmut, 0, 1);

sem_init(&buffer.cmut, 0, 1);

buffer.nextin = buffer.nextout = 0;

void put(buffer_t *b, char item) {

sem_wait(&b->empty);

sem_wait(&b->pmut);

b->buf[b->nextin] = item;

b->nextin++;

b->nextin %= BSIZE;

sem_post(&b->pmut);

sem_post(&b->occupied);

}

char get(buffer_t *b) {

char item;

sem_wait(&b->occupied);

sem_wait(&b->cmut);

item = b->buf[b->nextout];

b->nextout++;

b->nextout %= BSIZE;

sem_post(&b->cmut);

sem_post(&b->empty);

return(item);

}

sem_destroy(&buffer.occupied);

sem_destroy(&buffer.empty);

sem_destroy(&buffer.pmut);

sem_destroy(&buffer.cmut);

Uruchomienie producenta i konsumenta (pthread_create)

Inne funkcje: sem_trywait, sem_timedwait, sem_getvalue

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

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

static int sem; /* id semafora */

void P(int semid) {

struct sembuf buf; /* struktura
używana przy operacjach
semaforowych */

buf.sem_num = 0; /* numer
semafora */
buf.sem_flg = 0; /*operacja
blokująca*/
buf.sem_op = -1; /* zmniejszenie
semafora o 1)
semop(semid, &buf, 1);

}

void V(int semid) {

struct sembuf buf;
buf.sem_num = 0;
buf.sem_op = 1; /* zwiększenie
semafora o 1)
buf.sem_flg = 0;
semop(semid, &buf, 1);

}

void main() {

//utworzenie semafora
sem = semget (1,1, IPC_CREAT |
0666);
semctl (sem, 0, SETVAL, 1); /*
inicjacja semafora wartością 1 */
// Wykorzystanie funkcji P i V
P(sem);
. Tutaj sekcja krytyczna
V(sem);

}

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

Monitory

–

Czytelnicy i pisarze c.d.

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

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

•

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 PRODUCENT;
var p: porcja;
begin

while true do begin

produkuj(p);
region reg_bufor when ile<N

do begin

bufor[do_włożenia] := p;
do_włożenia := (do_włożenia+1) mod N;
ile = ile + 1;

end

end;

process KONSUMENT;
var p: porcja;
begin

while true do begin

region reg_bufor when ile>0

do begin

p := bufor[do_wyjęcia];
do_wyjęcia := (do_ wyjęcia+1) mod N;
ile = ile - 1;

end
konsumuj(p);

end

end;

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

Pisanie:

Odrzuć, gdy:

w czasie transakcji czytano wartość w późniejszej
transakcji (wartość już nie jest potrzebna)

w czasie transakcji zapisano nową wartość w późniejszej
transakcji (nie można zapisać wartości nieaktualnej)

Czytanie:

Odrzuć, gdy wartość została zmieniona w czasie tej transakcji

przez późniejszą transakcję (potrzebna wartość już nie
istnieje)