ZOS – 9. cvičení, ukázky kódu
Pavel Bžoch
Obsah • • • • • • • • •
Komunikace mezi procesy Atomické operace TSL a CAS Zámky Semafory Semafory – vypsání věty Monitor Bariéra pomocí monitoru Implementace semaforu pomocí monitoru Problém producent-konzument
Komunikace mezi procesy • Zasílání zpráv ▫ Každá zpráva má jednoznačné ID ▫ msgget inicializace fronty pro zprávy a spárování s identifikátorem ▫ msgsnd, msgrvc funkce pro odeslání/přijmutí zprávy
• Roura ▫ Příkazem pipe(int[2]) vytvoříme rouru (do parametru jsou uloženy deskriptory pro čtení a pro zápis) ▫ Potomek dědí deskriptory rodiče
Komunikace mezi procesy • Sdílená paměť ▫ Mezi procesy standardně neexistuje sdílená paměť – musíme si o ní explicitně říci ▫ OS ji může poskytnout, ale nemusí ▫ shmget – alokace sdíleného paměťového segmentu a spárování s klíčem; vrací ID vytvořeného segmentu ▫ shmat – zpřístupnění vytvořeného segmentu (namapování do adresného prostoru našeho procesu) ▫ Pro synchronizaci procesů lze použít sdílený semafor (viz dále)
Atomická operace TSL • Jen pro připomenutí: atomic int TSL(int *zamek, int novaHodnota) { int oldValue = *zamek; *zamek = novaHodnota; return oldValue}
• Celá operace musí být provedena atomicky, tj. bez přeplánování a musí být podporována hardwarem a překladačem • Volání např. TSL(&zamek, 1);
Atomická operace TSL • Řešení v C/C++ (překladač gcc): • Funkce: int __sync_lock_test_and_set(int *, int)-
atomické nastavení požadované hodnoty __sync_lock_release(int *) – nastavení hodnoty zpět na 0 • Implementace spinlocku: void tsl_spinlock() { while (__sync_lock_test_and_set(&zamek, 1) == 1); }
Atomická operace TSL • Řešení v javě: • Balík java.util.concurrent.atomic.AtomicInteger • Metody: boolean compareAndSet(int expect, int update); void set(int newValue);
• Implementace spinlocku: public void lock(){ while (! aInteger.compareAndSet(0, 1)); }
Atomická operace CAS (Compare And Swap) • Další atomická operace • Musí být poskytována HW počítače (stejně jako TSL) • Provede atomicky test hodnoty v paměti, v případě shody nastaví novou hodnotu, vždy navrátí původní hodnotu v paměti • „Synchronizace bez čekání“
Atomická operace CAS - definice Atomic int CAS(int* pointer,int expectedValue, int newValue){ int oldValue= *pointer; if (oldValue== expectedValue) *pointer = newValue; return oldValue; }
Atomická operace CAS • Řešení v C/C++ (překladač gcc) • Funkce: int __sync_val_compare_and_swap (int *kde,int puvodni, int nove);
Atomická operace CAS • Řešení v javě (java tuto operaci nepodporuje) • Je nutné jí napsat pomocí jiných operací (např. synchronized metody – využijeme pouze zámku, nebudeme používat metody monitoru) • Implemetace: public synchronized int compareAndSwap (myIntegervar, intexpectedValue, intnewValue) { int oldValue = var.getMyIntValue(); if(oldValue == expectedValue) var.setMyIntValue(newValue); return oldValue; }
Zámek (mutex, Mutual exclusion) • Připomenutí: • Implementace: flag (zamčeno, odemčeno), struktura pro uložení čekajících vláken • Funkce: ▫ Iniciace, vstup (zamknutí), opuštění (odemknutí)
• Platí zde princip vlastnictví – „ten, kdo zamyká, musí také odemknout“
Zámek • • • •
Řešení v C/C++ (překladač gcc) Knihovna pthread.h (#include
) Proměnná pthread_mutex_t Inicializace pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
• Vstup do KS: pthread_mutex_lock(&lock); • Opuštění KS: pthread_mutex_unlock(&lock);
Zámek • Řešení v javě • Balík java.util.concurrent.locks, rozhraní Lock, třída ReentrantLock • Nad instancí třídy ReentrantLock lze volat metody: ▫ lock() – uzamčení KS ▫ unlock() – odemknutí KS
Semafor • Připomenutí: • Implementace: čítač, struktura pro uložení čekajících vláken • Standardní operace: Iniciace (nastavení počáteční hodnoty čítače) Vstup do semaforu: P(sem) Opuštění semaforu: V(sem)
Semafor • • • •
Řešení v C/C++ (překladač gcc) Knihovna semaphore.h (#include <semaphore.h>) Proměnná sem_t Iniciace: sem_init(sem_t *, int pshared , unsigned int value) ▫ Pozn. proměnná pshared slouží jako přepínač, který udává, zda je semafor sdílen mezi vlákny (=0) nebo mezi procesy (>0)
• Operace p: sem_wait(sem_t *); • Operace v: sem_post(sem_t *);
Semafor • Řešení v javě • Třída java.util.concurrent.Semaphore • Inicializace: při vytváření instance se konstruktoru předá inicializační hodnota Semaphore s = new Semaphore (1);
• Operace P: s.acquire(); • Operace V: s.release();
Semafor – vypsání věty • Proces P1:
Proces P2:
• Print(“Ahoj ”)
Print(“dnes ”)
• Print(“je”)
Print(“krásně.”)
Proces P3: Print(“venku ”)
P1,P2, P3 běží paralelně. Ošetřete SEMAFORY, aby vždy byla vypsána správná věta: Ahoj dnes je venku krásně.
Semafor, věta – řešení pomocí 4 semaforů
Semafor, věta – řešení pomocí 3 semaforů
Monitor • Připomenutí: • „jazyková konstrukce, kterou může vykonávat v jednu chvíli nejvýše jedno vlákno“ • Implementace: zámek, podmínková proměnná (struktura čekajících vláken)
• Standardní operace: ▫ Vstup do kritické sekce, případné uspání nad podmínkovou proměnnou (wait), případné vzbuzení nad podmínkovou proměnnou(notify), opuštění kritické sekce
Monitor • Řešení v C/C++ • Knihovna pthread.h (#include )
• Podmínková proměnná: ▫ pthread_cond_t
• Vytváření, rušení
▫ pthread_cond_init(pthread_cond_t *, const pthread_condattr_t *) ▫ pthread_cond_t c1= PTHREAD_COND_INITIALIZER; ▫ pthread_cond_destroy (pthread_cond_t *cond)
• Čekání na podmínku
▫ pthread_cond_wait(pthread_cond_t*, pthread_mutex_t *)
• Vzbuzení vlákna
▫ pthread_cond_signal(pthread_cond_t*) ▫ pthread_cond_broadcast (pthread_cond_t*, )
• + POSIXové zámky
Monitor v c/c++ pthread_mutex_lock(&zamek); if (!podmnika) pthread_cond_wait(&podminka, &zamek); else pthread_cond_signal(&podminka); } pthread_mutex_unlock(&zamek);
Monitor • Řešení v javě • Do verze javy1.5 pouze synchronizedmetoda (nebo synchronizedblok) • Lze volat wait(), wait(longtimeout) pro uspání vlákna nad podmínkovou proměnnou (object) • Lze volat notify(), notifyAll() pro probuzení vlákna(-en) nad podmínkou proměnnou (object) • Nelze např. definovat více podmínkových proměnných • Viz příklad zavoznik
Monitor v javě(zámek, podmínka) • Od verze 1.5 balík java.util.concurrent.locks, konkrétně třídy Condition a Lock(případně ReentrantLock) • Od zámku lze získat podmínkové proměnné • Doporučené řešení od Oracle(místo synchronized) Lockzamek= newReentrantLock(); Conditionpodminka1 = zamek. newCondition(); Conditionpodminka2 = zamek. newCondition();
Monitor v javě(zámek, podmínka) • Nad instancí třídy Conditionlze pro uspání volat metody await(), awaitUninterruptibly(), awaitNanos(longnanosTimeout) • Pro probuzení lze volat metody signal(), signalAll() • Příklad na dalším slidu, příklad zavoznik
Monitor v javě(zámek, podmínka) try { lock.lock(); //kritickasekce if (!podmnika) podminka1.awaitUninterruptibly(); else podminka1.signal(); } finally { lock.unlock(); }
Bariéra • • • •
Bariéra je nastavená na N vláken Vlákna volají barrier() N-1 vláken se zde zablokuje Když přijde N-té vlákno, všechna vlákna jsou vzbuzena a projdou bariérou • Např. iterační výpočty
Bariéra v c/c++ pthread_mutex_t bariera_zamek = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t cond_bariera = PTHREAD_COND_INITIALIZER; int bariera_cnt = 0; void barrier() { pthread_mutex_lock(&bariera_zamek); bariera_cnt++; if (bariera_cnt < N) pthread_cond_wait(&cond_bariera, &bariera_zamek) else { bariera_cnt = 0; pthread_cond_broadcast(&cond_bariera); } pthread_mutex_unlock(&bariera_zamek); }
Bariéra v javě – výhodné použití synchronized metody private synchronized void barrier() { cnt++; if ( cnt < N) try { wait(); } catch (InterruptedException ex) {} else { cnt = 0; notifyAll(); } }
Implementace semaforu pomocí monitoru • Obecné řešení (využívá test velikosti fronty): monitor monsem { int sem; condition c1; void P() { if sem > 0 sem=sem-1; else wait(c1); }
void V() { if not empty(c1) signal(c1); else sem=sem+1; }
void monIni(int param) { sem = param; } init {sem = 1;} }
Implementace semaforu pomocí monitoru • Nevýhoda předchozího řešení: potřebujeme funkci empty(), která zjistí zda je fronta nad podmínkou prázdná • Další možná implementace na dalším slidu (v javě) • Praktická ukázka v C/C++
Implementace semaforu pomocí monitoru – java 1/2 class Semafor{ int citac; Semafor(int citac){ this.citac = citac; } public sychronized void P(){ //kód na dalším slidu } public sychronized void V(){ //kód na dalším slidu } }
Implementace semaforu pomocí monitoru – java 2/2 public sychronized void P(){ if (citac == 0) wait(); operace P() i V() zde vždy manipulují citac--; s proměnnou citac } public sychronized void V(){ citac++; hodnota sem bude vždy notify(); O, 1, … }
Problém producent-konzument, semaforem Buffer velikosti N; semaphore prod = N; semaphore konz = 0; semaphore zamek = 1; producent() { while(1) { Produkuj(); P(prod); P(zamek); Vloz_do_buff(); V(zamek);V(konz); }}
konzument() { while(1) { P(konz); P(zamek); Vyber_z_buff(); V(zamek); V(prod); Konzumuj(); }} cobegin producent() || konzument() coend
Problém producent-konzument • Ostatní synchronizační primitiva – viz příklady v C/C++ • Mimo jiné ukázka, jak pomocí zámku vyrobit semafor
