1/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Vláknové programování
část III
Lukáš Hejmánek, Petr Holub
{xhejtman,hopet}@ics.muni.cz
Laboratoř pokročilých síťových technologií
PV192
2013–03–04
2/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Přehled přednášky
Vlákna v jazyce Java
Paralelní vzory
Pokročilé vlasnosti Javy
Atomické typy
Concurrent Collections
Explicitní zamykání
Měření
3/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Přehled přednášky
Vlákna v jazyce Java
Paralelní vzory
Pokročilé vlasnosti Javy
Atomické typy
Concurrent Collections
Explicitní zamykání
Měření
4/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Vzor producent–konzument
Třídy Queue a BlockingQueue
◾ metody:
offer() přidává na konec fronty (blokuje se v případě BlockingQueue a
zaplnění kapacity)
nepoužívat add() pro fronty s omezenou kapacitou
peek() vrátí prvek ze začátku fronty, ale neodstraní ho z fronty
poll() vrátí prvek ze začátku fronty, null pokud je fronta prázdná
remove() vrátí prvek ze začátku fronty, výjimka
NoSuchElementException pokud je fronta prázdná
take() vrátí prvek ze začátku blokující fronty, nebo se zablokuje, dokud je
fronta prázdná
◾ typy
ConcurrentLinkedQueue – neblokující, FIFO, efektivní wait-free algoritmus,
nesmí obsahovat null
PriorityQueue – podpora priority (přirozené uspořádání, public
interface Comparable<T>)
LinkedBlockingQueue – blokující obdoba ConcurrentLinkedQueue
PriorityBlockingQueue – blokující obdoba PriorityQueue
SynchronousQueue – synchronní blokující fronta (offer() se zablokuje
až do odpovídajícího take())
5/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Vzor producent–konzument
1 import java.util.*;
import java.util.concurrent.*;
3
public class Fronty {
5 public class NeblokujiciFronty {
Queue clq = new ConcurrentLinkedQueue();
7 Queue pq = new PriorityQueue(50);
Queue q = new SynchronousQueue();
9
}
11
public class BlokujiciFronty {
13 BlockingQueue bclq = new LinkedBlockingQueue(30);
BlockingQueue bpq = new PriorityBlockingQueue();
15
void pouziti() {
17 bclq.offer(new Object());
Object o = bclq.peek();
19 o = bclq.poll();
try {
21 o = bclq.take();
} catch (InterruptedException e) {
23 e.printStackTrace();
}
25 }
}
27
}
6/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Vzor producent–konzument
Vzor producent–konzument
◾ producenti přidávají práci do fronty (offer())
◾ konzumenti přidávají práci do fronty (take())
◾ zvláště zajímavé se thread pools
7/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Vzor producent–konzument
import java.util.concurrent.*;
2
public class ProducentKonzument extends Thread {
4 public class Task {
}
6 BlockingQueue<Task> bclq = new LinkedBlockingQueue<Task>();
8 public void run() {
Thread producent = new Thread() {
10 public void run() {
bclq.offer(new Task());
12 }
};
14
Thread konzument = new Thread() {
16 public void run() {
try {
18 Task t = bclq.take();
} catch (InterruptedException e) {
20 System.out.println("Necekane probuzeni!");
}
22 }
};
24
producent.start();
26 konzument.start();
}
28 }
8/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Vzor kradení práce
Deque a BlockingDeque
◾ umožňují vybírat prvky ze začátku i z konce fronty
◾ normální konzumenti vybírají prvky ze začátku fronty
◾ vlákna, která se „nudí“ mohou převzít práci z konce fronty
◾ např. udržování fronty per vlákno, „nudící se“ vlákna mohou koukat do
cizích front
◾ vhodné např. pro situace, kdy si vlákno generuje další práci samo pro
sebe (webový crawler)
9/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Vzor kradení práce
import java.util.concurrent.*;
2
public class KradeniPrace {
4 public class Task {
}
6 BlockingDeque<Task> deque = new LinkedBlockingDeque<Task>(20);
8 public void run() {
Thread producent = new Thread() {
10 public void run() { deque.offer(new Task()); }
};
12
Thread konzument1 = new Thread() {
14 public void run() {
try {
16 Task t = deque.take();
} catch (InterruptedException e) {
18 }
}
20 };
22 Thread konzument2 = new Thread() {
public void run() { Task t = deque.pollLast(); }
24 };
26 producent.start(); konzument1.start(); konzument2.start();
}
28 }
10/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Další synchronizační prvky
semafory
◾ počáteční kapacita N „permitů“
◾ acquire() získá „permit“, eventuálně se zablokuje, pokud permity
došly
◾ release() vrátí permit
11/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Další synchronizační prvky
závlačka – CountDownLatch
◾ speciální typ semaforu, z jehož kapacity lze jen odečítat
◾ await() čeká, až hodnota klesne na 0
◾ např. čekání na až doběhne n nějakých událostí
import java.util.concurrent.CountDownLatch;
2
public class Zavlacka extends Thread {
4 static final int POCET_UDALOSTI = 10;
CountDownLatch cdl = new CountDownLatch(POCET_UDALOSTI);
6 public void run() {
Thread ridici = new Thread(){
8 public void run() {
for (int i = 0; i < POCET_UDALOSTI; i++) {
10 cdl.countDown();
}
12 }
};
12/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Další synchronizační prvky
závlačka – CountDownLatch
14 Thread cekaci = new Thread() {
public void run() {
16 try {
System.out.println("Musim pockat na "
18 + POCET_UDALOSTI + " udalosti");
cdl.await();
20 System.out.println("Ted teprv muzu bezet.");
} catch (InterruptedException e) {
22 System.out.println("Neocekavane vzbuzeni!");
}
24 }
};
26 cekaci.start(); ridici.start();
}
28
public static void main(String[] args) {
30 new Zavlacka().start();
}
32 }
13/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Další synchronizační prvky
FutureTask
◾ podrobně si koncept probereme u Futures a ThreadPoolExecutors
◾ je implementována pomocí Callable
obdoba Runnable, akorát umožňuje vracet hodnotu
◾ metoda get() umožňuje čekat, než je k dispozici návratová hodnota
14/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Další synchronizační prvky
bariéry
◾ umožňuje více vláknům se se jít v jednom místě
◾ např. pro iterativní výpočty, kde jedna iterace může být rozdělena na n
paralelních a další iterace je závislá na výsledku předchozí iterace
◾ zatímco závlačky jsou určeny k čekání na události, bariéry jsou určeny k
čekání na jiná vlákna
◾ CyclicBarrier – bariéra pro opakované setkávání se konstantního počtu
vláken
◾ pokud se nějaké vlákno vzbudí během await() metody, považuje se
bariéra za prolomenou a všichni ostatní čekající dostanou
BrokenBarrierException
Exchanger
◾ výměna dat během bariéry
◾ ekvivalent konceptu rendezvous v Adě
15/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Atomické typy
čekání na synchronized monitor vede na přeplánování vlákna
atomické proměnné to zvládnou bez přepínání kontextu
◾ vyšší výkon pro nízkou až střední míru soutěžení o zámek (lock
contention)
◾ tzv. wait-free synchronizace
Zdroj: Goetz B., Peierls T., Bloch J., Bowbeer J., Holmes D., Lea D. Java Concurrency in Practice. Addison Wesley Professional, 2006
16/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Atomické typy
čekání na synchronized monitor vede na přeplánování vlákna
atomické proměnné to zvládnou bez přepínání kontextu
◾ vyšší výkon pro nízkou až střední míru soutěžení o zámek (lock
contention)
◾ tzv. wait-free synchronizace
Zdroj: Goetz B., Peierls T., Bloch J., Bowbeer J., Holmes D., Lea D. Java Concurrency in Practice. Addison Wesley Professional, 2006
17/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Atomické typy
podpora v HW
◾ compare-and-swap (CAS)
CAS(x, y)
funkce: porovnej obsah paměti s x a pokud je identický, nahraď jej za y
návratová hodnota: úspěch změny (buď jako boolean nebo jako hodnota,
kterou má paměť před provedením instrukce)
podpora: IA-32, Sparc
◾ double compare-and-swap (DCAS/CAS2)
funkce: výměna hodnot na dvou místech v paměti na základě původních
hodnot
jednoduchá implementace atomické Deque
lze emulovat pomocí CAS ⇒ (pomalá) podpora u Motorol 68k
◾ double-wide compare-and-swap
funkce: výměna hodnot na dvou přilehlých místech v paměti
podpora: CMPXCHG8B a CMPXCHG16B na novějších x86
◾ Single compare, double swap
funkce: výměna hodnot na dvou místech v paměti v závislosti na jedné
původní hodnotě
podpora: cmp8xchg16 u Ithania
18/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Atomické typy
podpora v HW
◾ load-link/store-conditional (LL/SC)
funkce: (1) LL načte hodnotu paměti, (2) SC ji změní pouze pokud se
původní hodnota od operace LL nezměnila, jinak selže
silnější než CAS – řeší i problém ABA
podpora: ldl_l/stl_c a ldq_l/stq_c (Alpha), lwarx/stwcx
(PowerPC), ll/sc (MIPS), ldrex/strex (ARM version 6 avyšší)
◾ fetch-and-add
funkce: atomická inkrementace obsahu paměti
návratová hodnota: původní hodnota paměti
podpora: x86 od 8086 (ADD s prvním operandem specifikujícím místo v
paměti, nicméně nevrací původní hodnotu – s LOCK prefixem atomické i u
více procesorů), XADD od 486 vrací původní hodnotu
19/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Atomické typy
AtomicX z java.util.concurrent
◾ AtomicBoolean, AtomicInteger, AtomicLong, AtomicReference
Zajištěné atomické aktualizace
Podpora od Java 5.0
HW optimalizace
◾ CAS instrukce (IA-32, Sparc)
◾ podpora v JVM od 5.0
20/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Využítí atomických typů
Návrh algoritmu
◾ buď vyžaduje pouze jednu atomickou změnu
◾ nebo z první změny musí být odvoditelné ostatní a musí je být schopen
dokončit „kdokoli“
Kolekce
◾ ConcurrentLinkedQueue
◾ WaitFreeReadQueue
http://www.rtsj.org/specjavadoc/javax/realtime/
WaitFreeReadQueue.html
◾ WaitFreeWriteQueue
http://www.rtsj.org/specjavadoc/javax/realtime/
WaitFreeWriteQueue.html
21/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Neblokující seznam: Michael-Scott, 1996
22/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Neblokující seznam: Michael-Scott, 1996
import java.util.concurrent.atomic.AtomicReference;
2 // dle http://www.javaconcurrencyinpractice.com/listings/LinkedQueue.java
4 public class AtomickySeznam<E> {
private static class Node<E> {
6 final E polozka;
final AtomicReference<AtomickySeznam.Node<E>> next;
8
public Node(E polozka, AtomickySeznam.Node<E> next) {
10 this.polozka = polozka;
this.next = new
12 AtomicReference<AtomickySeznam.Node<E>>(next);
}
14 }
16 private final AtomickySeznam.Node<E> dummy =
new AtomickySeznam.Node<E>(null, null);
18 private final AtomicReference<AtomickySeznam.Node<E>> hlava
= new AtomicReference<AtomickySeznam.Node<E>>(dummy);
20 private final AtomicReference<Node<E>> konec
= new AtomicReference<AtomickySeznam.Node<E>>(dummy);
23/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Neblokující seznam: Michael-Scott, 1996
22
public boolean put(E polozka) {
24 AtomickySeznam.Node<E> newNode =
new AtomickySeznam.Node<E>(polozka, null);
26 while (true) {
AtomickySeznam.Node<E> curkonec = konec.get();
28 AtomickySeznam.Node<E> konecNext = curkonec.next.get();
if (curkonec == konec.get()) {
30 if (konecNext != null) {
// dokoncime rozpracovany stav - posuneme konec
32 konec.compareAndSet(curkonec, konecNext);
} else {
34 // pokusime se vlozit
if (curkonec.next.compareAndSet(null, newNode)) {
36 // pri uspechu se pokusime posunout konec
konec.compareAndSet(curkonec, newNode);
38 return true;
}
40 }
}
42 }
}
44
}
24/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Problém ABA
Problém, jak detekovat změnu A → B → A
◾ podpora HW: LL/SC
◾ „verzování“: počítadlo změn
AtomicStampedReference
◾ odkaz + int počítadlo změn
AtomicMarkedReference
◾ odkaz + boolean indikátor
◾ některé algoritmy používají indikátor k označení uzlu v seznamu jako
smazaného
25/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Concurrent Collections
optimalizace kolekcí na výkon při paralelních přístupech
CopyOnWriteArrayList, CopyOnWriteArraySet
◾ optimalizované pro režim čti-často-měň-zřídka
◾ CopyOnWriteArraySet obdoba HashSet
◾ CopyOnWriteArrayList obdoba ArrayList, na rozdíl od Vector poskytuje
složené operace
◾ iterace poskytuje pohled na objekt v době konstrukce iterátoru
1 import java.util.concurrent.*;
3 public class CoW {
CopyOnWriteArraySet cowAS = new CopyOnWriteArraySet();
5 CopyOnWriteArrayList cowAL = new CopyOnWriteArrayList();
public void narabaj() {
7 cowAS.addAll(kolekce);
cowAS.contains(o);
9 cowAS.clear();
11 cowAL.addAllAbsent(kolekce);
cowAL.addIfAbsent(o);
13 cowAL.retainAll(kolekce);
}
15 }
26/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Concurrent Collections
ConcurrentHashMap
◾ kolekce optimalizovaná na vyhledávání prvků
◾ mnohem lepší výkon v porovnání se synchronizedMap a Hashtable
Threads ConcurrentHashMap [ms/10 Mops] Hashtable [ms/10 Mops]
1 1,00 1,03
2 2,59 32,40
4 5,58 78,23
8 13,21 163,48
16 27,58 341,21
32 57,27 778,41
https://www.ibm.com/developerworks/java/library/j-jtp07233/index.html
◾ úspěšná operace get() obvykle proběhne bez zamykání
◾ na iteraci se nezamyká celá kolekce
◾ mírně relaxovaná sémantika
při získávání prvků je možné najít i prvek, jehož vkládání ještě není
dokončeno (nikdy však nesmysl)
iterátor může ale nemusí reflektovat změny od té doby, co byl vytvořen
synchronizedMap a Hashtable lze nahradit tam, kde se nespoléhá na
zamykání celé tabulky
27/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Concurrent Collections
ConcurrentHashMap
1 import java.util.concurrent.ConcurrentHashMap;
3 public class CHT {
ConcurrentHashMap cht = new ConcurrentHashMap(10);
5
public void narabaj() {
7 cht.put(klic, objekt);
cht.putAll(mapa);
9 cht.putIfAbsent(klic, objekt);
cht.containsKey(klic);
11 cht.containsValue(objekt); // take contains()
cht.entrySet();
13 cht.keySet();
cht.values();
15 cht.clear();
}
17 }
28/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Explicitní zamykání
potřeba jemnějšího zamykání
◾ zvýšení výkonu – např. paralelizace read-only přístupů
potřeba rozšířené funkcionality
ReentrantLock
◾ ekvivalent synchronized, pouze explicitní
◾ rozšířené schopnosti (např. gettery)
◾ nezapomenout správně odemknout
1 import java.util.concurrent.locks.ReentrantLock;
3 public class RELock {
public static void main(String[] args) {
5 ReentrantLock relock = new ReentrantLock();
relock.lock();
7 try {
Thread.sleep(1000);
9 // kod
} catch (InterruptedException e) {
11 } finally {
relock.unlock();
13 }
}
15 }
29/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Explicitní zamykání
ReentrantReadWriteLock
◾ paralelizace na čtení, exkluzivní přístup na zápis
◾ reentrantní zámek jak pro čtení, tak pro zápis
◾ politiky: writer preference | fair
specifikací v konstruktoru
◾ downgrade zámku: získání read zámku před uvolněním write zámku
◾ neumožňuje upgrade zámku
◾ instrumentace pro monitoring (informace o držení zámků) – nikoli pro
synchronizaci!
možno si naimplementovat vlastní zámky, např. RW zámek s
podporou upgrade
◾ http://www.jtoolkit.org/articles/
ReentrantReadWriteLock-upgrading.html
◾ upgrade je nevýhodný z pohledu výkonu
30/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Explicitní zamykání
1 import java.util.concurrent.locks.ReentrantReadWriteLock;
3 public class RWLock {
boolean cacheValid = false;
5 public void pouzijCache() {
// rwlock s fair politikou
7 ReentrantReadWriteLock rwlock = new ReentrantReadWriteLock(true);
rwlock.readLock().lock();
9 if (!cacheValid) {
rwlock.readLock().unlock();
11 rwlock.writeLock().lock();
if (!cacheValid) { // znovu zkontroluj,
13 // neumime upgrade bez preruseni
// uloz data do cache
15 cacheValid = true;
}
17 // rucni downgrade zamku
rwlock.readLock().lock(); // jeste drzim na zapis
19 rwlock.writeLock().unlock();
}
21 // pouzij data
rwlock.readLock().unlock();
23 }
}
31/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Explicitní zamykání
Conditions
◾ čekání na splnění podmínky
interface Condition {
void await() throws IE;
boolean await(long time, TimeUnit unit) throws IE;
long awaitNanos(long nanosTimeout) throws IE;
void awaitUninterruptibly()
boolean awaitUntil(Date deadline) throws IE;
void signal();
void signalAll();
}
32/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Explicitní zamykání
Conditions
◾ výhody oproti wait()/notify()
více podmínek per zámek
final Lock zamek = new ReentrantLock();
final Condition nePlny = zamek.newCondition();
final Condition nePrazdny = zamek.newCondition();
absolutní a relativní timeouty
po návratu se dozvíme, proč jsme se vrátili
možnost nepřerušitelného čekání (nereaguje na metodu interrupt)
◾ může se vyskytnout spurious wakeup
je třeba používat idiom ověřování stavu podmínky! :(
33/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Explicitní zamykání
1 import java.util.concurrent.locks.*;
3 public class OmezenyBuffer {
Lock lock = new ReentrantLock();
5 Condition notFull = lock.newCondition();
Condition notEmpty = lock.newCondition();
7 Object[] items = new Object[100];
int putptr, takeptr, count;
9 public void put(Object x) throws InterruptedException {
lock.lock();
11 try {
while (count == items.length) notFull.await();
13 items[putptr] = x;
if (++putptr == items.length) putptr = 0;
15 ++count;
notEmpty.signal();
17 } finally {
lock.unlock();
19 }
}
21 public Object take() throws InterruptedException {
lock.lock();
23 try {
while (count == 0) notEmpty.await();
25 Object x = items[takeptr];
if (++takeptr == items.length) takeptr = 0;
27 --count;
notFull.signal();
29 return x;
} finally {
31 lock.unlock();
}
33 }
}
http://www.cs.umd.edu/class/spring2005/cmsc433/lectures/util-concurrent-new.pdf
34/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Programování v reálném čase
http://www.rtsj.org/
P. Dibble: Real-Time Java Platform Programming
http://www.sun.com/books/catalog/dibble.xml
◾ Interoperability with non-RT code, tradeoffs in real-time development,
and RT issues for the JVM software
◾ Garbage collection, non-heap access, physical and "immortal"memory,
and constant-time allocation of non-heap memory
◾ Priority scheduling, deadline scheduling, and rate monotonic analysis
◾ Closures, asynchronous transfer of control, asynchronous events, and
timers
35/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Interakce s JVM při měření
Problém garbage collection
◾ -verbose:gc
◾ krátká měření: vybrat pouze běhy, v nichž nedošlo ke GC
◾ dlouhé běhy: dostatečně dlouhé, aby se přítomnost GC projevila
representativně
Problém HotSpot kompilace
◾ -XX:+PrintCompilation
◾ dostatečný warm-up (minuty!)
◾ mohou se vyskytovat rekompilace (optimalizace, nahrání nové třídy
která zruší dosavadní předpoklady)
◾ housekeeping tasks: oddělení nesouvisejících měření pauzou nebo
restartem JVM
36/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Délka zpracování obrázku
37/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
velikost obrázku čas běhu
640 × 480 124,12983930928
1280 × 720 539,98450298239
1920 × 1080 1529,02398429008
4096 × 2160 10210,09238488922
38/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
velikost obrázku čas běhu
640 × 480 124,12983930928
1280 × 720 539,98450298239
1920 × 1080 1529,02398429008
4096 × 2160 10210,09238488922
39/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Měříme délku výpočtu v Javě
40/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
> library(psych)
> runlength <- read.csv(file="java-example.table", head=FALSE, sep=","
> summary(runlength$V1)
Min. 1st Qu. Median Mean 3rd Qu. Max.
92.08 104.70 108.80 166.80 187.20 594.70
> describe(runlength$V1)
var n mean sd median trimmed mad min max range skew k
1 1 30 166.82 113.67 108.78 142.1 20.88 92.08 594.71 502.63 2.14
4.55
se
1 20.75
41/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
N = 30
x = 166,82
sx = 113,67
sx = sx√
N
= 20,75
t0,05;29 = 2,045
x ± t0,05;N−1sx = 167 ± 42ms
0 100 200 300 400 500 600
051015
Javové měření
Čas [ms]
Četnost
42/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
N = 30
x = 166,82
sx = 113,67
sx = sx√
N
= 20,75
t0,05;29 = 2,045
x ± t0,05;N−1sx = 167 ± 42ms
0 100 200 300 400 500 600
051015
Javové měření
Čas [ms]
Četnost
43/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
0 5 10 15 20 25 30
100200300400500600
Javové měření
Měření
Čas [ms]
44/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
0 5 10 15 20 25 30
100200300400500600
Javové měření
Měření
Čas [ms]
HotSpot
garbage collector
45/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Soustava jednotek pro informatiky
Zdroj: http://www.icrf.nl/Portals/106/SI_units_diagram(1).jpg
46/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Soustava jednotek pro informatiky
Předpony nejen speciálně informatické
yocto- 10−24
y – – –
zepto- 10−21
z – – –
atto- 10−18
a – – –
femto- 10−15
f – – –
pico- 10−12
p – – –
nano- 10−9
n – – –
micro- 10−6
µ – – –
milli- 10−3
m – – –
kilo- 103
k kibi 210
Ki
mega- 106
M mebi 220
Mi
giga- 109
G gibi 230
Gi
tera- 1012
T tebi 240
Ti
peta- 1015
P pebi 250
Pi
exa- 1018
E exbi 260
Ei
zetta- 1021
Z zebi 270
Zi
yotta- 1024
Y yobi 280
Yi
Amendment 2 to “IEC 60027-2: Letter symbols to be used in electrical technology – Part 2:
Telecommunications and electronics” (1999)
47/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Výsledky měření
x = (ˆµx ± zx) [jednotka]
ˆµx... nejpravděpodobnější hodnota měřené veličiny
zx... interval spolehlivosti / přesnost
jak tyto věci spočítat / odhadnout?
48/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Chyby měření
Klasifikace chyb podle místa vzniku
◾ instrumentální (přístrojové) chyby
◾ metodické chyby
◾ teoretické chyby (principy, model)
◾ chyby zpracování
Klasifikace chyb podle původu
◾ hrubé (omyly)
◾ systematické
◾ náhodné
49/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Chyby měření
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
50/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Přesnost měřících nástrojů
Přesnost přístroje ... náhodná chyba
Správnost přístroje ... systematická chyba
Aditivní vs. multiplikativní chyby
Mezní hodnota chyb
Třída přesnosti přístroje
Aditivní model
skutečná hodnota
změřenáhodnota
Multiplikativní model
skutečná hodnota
změřenáhodnota
Kombinovaný model
skutečná hodnota
změřenáhodnota
51/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Hrubé chyby
Hrubé chyby se musí ze sady měření vyloučit
Volba měřící metody / měřících metod – příklad pro Javu
◾ Problém garbage collection
-verbose:gc
krátká měření: vybrat pouze běhy, v nichž nedošlo ke GC
dlouhé běhy: dostatečně dlouhé, aby se přítomnost GC projevila
representativně
◾ Problém HotSpot kompilace
-XX:+PrintCompilation
dostatečný warm-up (minuty!)
mohou se vyskytovat rekompilace (optimalizace, nahrání nové třídy která
zruší dosavadní předpoklady)
housekeeping tasks: oddělení nesouvisejících měření pauzou nebo
restartem JVM
52/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Náhodné chyby
aneb proč se běžně pracuje s normálním rozdělením chyb?
Hypotéza elementárních chyb (Horák, 1958)
◾ každá náhodná chyba v měření je složena z řady malých chyb
◾ při velkém počtu měření se vyskytne zhruba stejný počet chyb
kladných i záporných a malé chyby jsou početnější než velké
1. m elementárních náhodných vlivů
2. každý elementární vliv generuje chybu α (dále označováno jako případ
a) nebo −α (dále případ b)
3. chyby a a b jsou stejně časté
◾ dostáváme binomické rozdělení kumulace vlivů elementárních chyb
◾ pro velké množství náhodných jevů se blíží rozdělení normálnímu
53/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Náhodné chyby
aneb proč se běžně pracuje s normálním rozdělením chyb?
Co se stane, pokud m → ∞?
◾ binomické rozdělení
(
m
0
)am
,(
m
1
)am−1
b, . . . ,(
m
l
)am−l
bl
, . . . ,(
m
m
)bm
P(0) =
1
2m
(
m
m/2
) P(εl) =
1
2m
(
m
l
), εl = (l − (m − l))α = (2l − m)α = 2sα
◾ pro sudá m = 2k ⇒ k → ∞ (sudá, abychom měli P(0))
P(ε) = P(2sα) =
1
22k
(
2k
k + s
)
P(2sα)
P(0)
=
( 2k
k+s
)
(2k
k
)
=
k(k − 1)⋯(k − s + 1)
(k + 1)(k + 2)⋯(k + s)
=
(1 − 1
k
) (1 − 2
k
) ⋯ (1 − s−1
k
)
(1 + 1
k
) (1 + 2
k
) ⋯ (1 + s
k
)
◾ pro s ≪ k
ln(1 + x) = x −
x2
2
+
x3
3
− ⋅ ⋅ ⋅ ≈ x
ln
P(2sα)
P(0)
= −
1
k
−
2
k
− ⋅ ⋅ ⋅ −
s − 1
k
−
1
k
−
2
k
− ⋅ ⋅ ⋅ −
s
k
= −
2
k
s(s − 1)
2
−
s
k
= −
s2
k
P(2sα) = P(0)e− s2
k = P(0)e
− ε2
4kα2
54/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Studentovo rozdělení t
Používá se pro normální rozdělení při malém vzorku
f(t) =
Γ(ν+1
2
)
√
νπΓ(ν
2
)
(1 +
t2
ν
)
−(ν+1)/2
kde ν je počet stupňů volnosti.
◾ odhad průměrů a chyby
◾ t-test – odlišení průměrů
55/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Odhad spolehlivosti
x = (ˆµx ± zx) [jednotka]
Statistická definice (Šťastný, 1997): Je-li výsledek měření ˆµxa zxje chyba
tohoto měření odpovídající míře jistoty p, pak skutečná hodnota měřené
veličiny leží v intervalu (ˆµx ± zx) s pravděpodobností p.
Intervaly
◾ 0,68 – střední kvadratická chyba
◾ 0,95
◾ 0,99 – krajní chyba
Zaokrouhlování
◾ zxnejvýše na 2 platná místa
◾ ˆµxpodle zx
56/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Odhad spolehlivosti
x = (ˆµx ± zx) [jednotka]
Pro normální rozdělení chyby
ˆµx = x = ∑
N
i=1 xi
n
s směrodatná odchylka jednoho měření, D rozptyl
s =
√
D =
√
∑
N
i=1(x − xi)2
n − 1
sx =
√
∑
N
i=1(1
n
)2sxi
a protože měření byly prováděny za stejných
podmínek
sx =
sx
√
n
=
∑
N
i=1(x − xi)2
n(n − 1)
57/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Odhad spolehlivosti
x = (ˆµx ± zx) [jednotka]
Pro normální rozdělení chyby
zx = t(p;n−1)sx
HH
HHn
P
0,683 0,954 0,99
HH
HHn
P
0,683 0,954 0,99
1 1,8395 13,8155 63,6567 16 1,0329 2,1633 2,9208
2 1,3224 4,5001 9,9248 18 1,0292 2,1433 2,8784
3 1,1978 3,2923 5,8409 20 1,0263 2,1276 2,8453
4 1,1425 2,8585 4,6041 30 1,0176 2,0817 2,75
5 1,1113 2,6396 4,0321 40 1,0133 2,0595 2,7045
6 1,0913 2,5084 3,7074 50 1,0108 2,0463 2,6778
7 1,0775 2,4214 3,4995 60 1,0091 2,0377 2,6603
8 1,0673 2,3594 3,3554 70 1,0078 2,0315 2,6479
9 1,0594 2,3131 3,2498 80 1,0069 2,0269 2,6387
10 1,0533 2,2773 3,1693 90 1,0062 2,0234 2,6316
12 1,0441 2,2253 3,0545 100 1,0057 2,0206 2,6259
14 1,0377 2,1895 2,9768
58/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Odhad spolehlivosti
x = (ˆµx ± zx) [jednotka]
Příklad – měření výšky válečku (Šťastný, 1997):
výška v [mm] 4,6 4,5 4,7 4,4 4,5 4,6 4,4 4,4 4,3 4,5
n = 10
v = 4,49[mm]
sv = 0,038[mm]
t(0,68;9) = 1,059
t(0,99;9) = 3,250
v = (4,49 ± 0,04) mm pro p = 0,68
v = (4,49 ± 0,12) mm pro p = 0,99
59/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Zákon přenosu chyb
Na základě Taylorova rozvoje do druhého členu
s2
z =
N
∑
i=1
(
∂z
∂xi
)
2
s2
xi
+ 2
N−1
∑
i=1
N
∑
j=i+1
∂z
∂xi
∂z
∂xj
sxi
sxj ij ,
kde s2
xi
je rozptyl (variance) xi a ij je kovariance xi a xj.
Pro jednoduché případy, kdy x a y jsou nezávislé ( ij = 0):
◾ aditivní funkce z = ax ± by
sz =
√
a2s2
x
+ b2s2
y
, (1)
◾ multiplikativní funkce z = axb
yc
sz = z (
bsx
x
)
2
+ (
csy
y
)
2
. (2)
kde z = axb
yc
, protože
N
∑
i=1
(
∂z
∂xi
)
2
s
2
i
=
⎛
⎝
abxb
yc
sx
x
⎞
⎠
2
+
⎛
⎝
axb
cyc
sy
y
⎞
⎠
2
= z
2
((
bsx
x
)
2
+ (
csy
y
)
2
)
◾ Příklad použití: http://www.phy.ohiou.edu/~murphy/courses/sample.pdf
60/60
Vlákna v jazyce Java Paralelní vzory Pokročilé vlasnosti Javy Měření
Skripta Fr. Šťastného (Šťastný, 1997)
http://amper.ped.muni.cz/jenik/nejistoty/