1/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Vláknové programování
část IX
Lukáš Hejmánek, Petr Holub
{xhejtman,hopet}@ics.muni.cz
Laboratoř pokročilých síťových technologií
PV192
2011–04–21
2/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Přehled přednášky
ThreadPoolExecutors Revisited
Uváznutí
Optimalizace výkonu
Měření
(příklady povětšinou převzaty z JCiP, Goetz)
3/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
ThreadFactory
TPE vytváří vlákna pomocí ThreadFactory
◾ metoda newThread
◾ default ThreadFactory: nedémonická, bez speciálních nastavení
Možnost předefinovat, jak se budou vytvářet vlákna
◾ nastavení pojmenování vláken
◾ vlastní třída vytvářených vláken (statistiky, ladění)
◾ specifikace vlastního UncaughtExceptionHandler
◾ nastavení priorit (raději nedělat)
◾ nastavení démonického stavu (raději nedělat)
◾ v případě použití bezpečnostních politik (security policies) lze použít
privilegedThreadFactory
podědění oprávnění, AccessControlContext a contextClassLoader
od vlákna vytvářejícího privilegedThreadFactory, nikoli od vlákna
volajícího execute/submit (default)
4/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
ThreadFactory
public class MyThreadFactory implements ThreadFactory {
2 private final String poolName;
class MyAppThread extends Thread {
4 public MyAppThread(Runnable runnable, String poolName) {
super(runnable, poolName);
6 }
}
8
public MyThreadFactory(String poolName) {
10 this.poolName = poolName;
}
12
public Thread newThread(Runnable runnable) {
14 return new MyAppThread(runnable, poolName);
}
16 }
5/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Modifikace Executorů za běhu
settery a gettery na různé vlastnosti
možnost přetypování executorů vyrobených přes factory metody
(kromě newSingleThreadExecutor) na ThreadPoolExecutor
omezení modifikací
◾ nechceme nechat vývojáře šťourat do svých TPE
◾ factory metoda Executor.unconfigurableExecutorService
bere ExecutorService
vrací omezenou ExecutorService pomocí
DelegatedExecutorService, která rozšiřuje
AbstractExecutorService
◾ využíváno metodou newSingleThreadExecutor (vrací omezený Executor
– ačkoli implementace ve skutečnosti používá TPE s jediným vláknem)
6/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Modifikace TPE
Háčky pro modifikace
◾ beforeExecute
◾ afterExecute
◾ terminated
Např. sběr statistik
7/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Modifikace TPE
public class TimingThreadPool extends ThreadPoolExecutor {
2
public TimingThreadPool() {
4 super(1, 1, 0L, TimeUnit.SECONDS, null);
}
6
private final ThreadLocal<Long> startTime = new ThreadLocal<Long>();
8 private final Logger log = Logger.getLogger("TimingThreadPool");
private final AtomicLong numTasks = new AtomicLong();
10 private final AtomicLong totalTime = new AtomicLong();
12 protected void beforeExecute(Thread t, Runnable r) {
super.beforeExecute(t, r);
14 log.fine(String.format("Thread %s: start %s", t, r));
startTime.set(System.nanoTime());
16 }
8/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Modifikace TPE
protected void afterExecute(Runnable r, Throwable t) {
2 try {
long endTime = System.nanoTime();
4 long taskTime = endTime - startTime.get();
numTasks.incrementAndGet();
6 totalTime.addAndGet(taskTime);
log.fine(String.format("Thread %s: end %s, time=%dns",
8 t, r, taskTime));
} finally {
10 super.afterExecute(r, t);
}
12 }
14 protected void terminated() {
try {
16 log.info(String.format("Terminated: avg time=%dns",
totalTime.get() / numTasks.get()));
18 } finally {
super.terminated();
20 }
}
22 }
9/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Možné řešení kvízu
public class DynamicTPE {
2 static class CustomTPE extends ThreadPoolExecutor {
final int userProvidedPoolSize;
4 final int queueCapacity;
6 CustomTPE(int corePoolSize, int maximumPoolSize,
long keepAliveTime, TimeUnit unit,
8 BlockingQueue<Runnable> workQueue) {
super(corePoolSize, maximumPoolSize,
10 keepAliveTime, unit, workQueue);
userProvidedPoolSize = corePoolSize;
12 queueCapacity = workQueue.size()
+ workQueue.remainingCapacity();
14 }
16 @Override public Future<?> submit(Runnable task) {
autoAdjustCorePoolSize();
18 return super.submit(task);
}
20
@Override synchronized public void setCorePoolSize
22 (int corePoolSize) {
super.setCorePoolSize(corePoolSize);
24 }
@Override synchronized public void setMaximumPoolSize
26 (int maximumPoolSize) {
super.setMaximumPoolSize(maximumPoolSize);
28 }
10/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Možné řešení kvízu
synchronized private void autoAdjustCorePoolSize() {
2 final int queueRemaining = getQueue().remainingCapacity();
final int extension;
4 if (queueRemaining < 0.25 * queueCapacity) {
extension = (int) Math.round(0.25 * queueCapacity
6 - queueRemaining);
if (getCorePoolSize() + extension < getMaximumPoolSize())
8 setCorePoolSize(getCorePoolSize() + extension);
else
10 setCorePoolSize(getMaximumPoolSize());
}
12 else if (queueRemaining > 0.75 * queueCapacity) {
extension = (int) Math.round(queueRemaining
14 - 0.75 * queueCapacity);
if (getCorePoolSize() - extension > userProvidedPoolSize)
16 setCorePoolSize(getCorePoolSize() - extension);
else
18 setCorePoolSize(userProvidedPoolSize);
}
20 }
22 }
11/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Možné řešení kvízu
1 public static void main(String[] args) {
ThreadPoolExecutor tpe = new CustomTPE(1, 10, 60, TimeUnit.SECONDS, new
3 tpe.setRejectedExecutionHandler(new ThreadPoolExecutor.CallerRunsPolicy(
ArrayList<Future> taskList = new ArrayList<Future>();
5 Runnable r = new Runnable() {
public void run() {
7 try {
Thread.sleep(30);
9 } catch (InterruptedException e) {
}
11 System.out.println("bla");
}
13 };
for (int i = 0; i < 1000; i++) {
15 Future f = tpe.submit(r);
taskList.add(f);
17 System.out.println("TPE corepoolsize: " + tpe.getCorePoolSize());
System.out.println("TPE poolsize: " + tpe.getPoolSize());
19 }
for (Future future : taskList) {
21 try {
Object o = future.get();
23 } catch (InterruptedException e) {
} catch (ExecutionException e) {
25 }
}
27 tpe.shutdown();
}
12/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Možné řešení kvízu
TPE corepoolsize: 1
2 TPE poolsize: 1
TPE corepoolsize: 1
4 TPE poolsize: 1
TPE corepoolsize: 1
6 TPE poolsize: 1
TPE corepoolsize: 1
8 TPE poolsize: 1
TPE corepoolsize: 1
10 TPE poolsize: 1
TPE corepoolsize: 1
12 TPE poolsize: 1
TPE corepoolsize: 1
14 TPE poolsize: 1
TPE corepoolsize: 1
16 TPE poolsize: 1
TPE corepoolsize: 1
18 TPE poolsize: 1
TPE corepoolsize: 1
20 TPE poolsize: 1
TPE corepoolsize: 1
22 TPE poolsize: 1
TPE corepoolsize: 1
TPE poolsize: 1
2 TPE corepoolsize: 1
TPE poolsize: 1
4 TPE corepoolsize: 1
TPE poolsize: 1
6 TPE corepoolsize: 1
TPE poolsize: 1
8 TPE corepoolsize: 1
TPE poolsize: 1
10 TPE corepoolsize: 1
TPE poolsize: 1
12 TPE corepoolsize: 2
TPE poolsize: 2
14 TPE corepoolsize: 4
TPE poolsize: 4
16 TPE corepoolsize: 7
TPE poolsize: 7
18 TPE corepoolsize: 10
TPE poolsize: 10
20 TPE corepoolsize: 10
TPE poolsize: 10
22 bla
bla
13/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Možné řešení kvízu
Stojí nám to za to?
◾ drahá synchronizace
◾ režije se startováním a ukončováním vláken
◾ nestačí vhodně nastavit corePoolSize a allowCoreThreadTimeOut?
14/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Kompletně vlastní implementace TPE
Zdrojové kódy:
◾ http://kickjava.com/src/java/util/concurrent/
ThreadPoolExecutor.java.htm
◾ http://kickjava.com/src/java/util/concurrent/
ScheduledThreadPoolExecutor.java.htm
15/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Deadlock
Deadlock – uváznutí, smrtelné objetí ;-)
Vzájemné nekončící čekání na zámky
Potřeba globálního uspořádání zámků
◾ zamykání podle globálního uspořádání
Možnost využití Lock.tryLock()
◾ náhodný rovnoměrný back-off
◾ náhodný exponenciální back-off
◾ nelze použít s monitory
Řešení deadlocků runtimem (ne v Javě)
16/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Deadlock
public static void transferMoney(Account fromAccount,
2 Account toAccount,
DollarAmount amount)
4 throws InsufficientFundsException {
synchronized (fromAccount) {
6 synchronized (toAccount) {
if (fromAccount.getBalance().compareTo(amount) < 0)
8 throw new InsufficientFundsException();
else {
10 fromAccount.debit(amount);
toAccount.credit(amount);
12 }
}
14 }
}
17/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Deadlock
public static void transferMoney(Account fromAccount,
2 Account toAccount,
DollarAmount amount)
4 throws InsufficientFundsException {
synchronized (fromAccount) {
6 synchronized (toAccount) {
if (fromAccount.getBalance().compareTo(amount) < 0)
8 throw new InsufficientFundsException();
else {
10 fromAccount.debit(amount);
toAccount.credit(amount);
12 }
}
14 }
}
18/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Deadlock
public void transferMoney(final Account fromAcct,
2 final Account toAcct,
final DollarAmount amount)
4 throws InsufficientFundsException {
class Helper {
6 public void transfer() throws InsufficientFundsException {
if (fromAcct.getBalance().compareTo(amount) < 0)
8 throw new InsufficientFundsException();
else {
10 fromAcct.debit(amount);
toAcct.credit(amount);
12 }
}
14 }
int fromHash = System.identityHashCode(fromAcct);
16 int toHash = System.identityHashCode(toAcct);
System.identityHashCode(o) může vrátit pro dva různé objekty
identický hash
◾ řídký problém
19/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Deadlock
if (fromHash < toHash) {
2 synchronized (fromAcct) {
synchronized (toAcct) {
4 new Helper().transfer();
}
6 }
} else if (fromHash > toHash) {
8 synchronized (toAcct) {
synchronized (fromAcct) {
10 new Helper().transfer();
}
12 }
} else {
14 synchronized (tieLock) {
synchronized (fromAcct) {
16 synchronized (toAcct) {
new Helper().transfer();
18 }
}
20 }
}
20/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Deadlock
private static Random rnd = new Random();
2
public boolean transferMoney(Account fromAcct,
4 Account toAcct,
DollarAmount amount,
6 long timeout,
TimeUnit unit)
8 throws InsufficientFundsException, InterruptedException {
long fixedDelay = getFixedDelayComponentNanos(timeout, unit);
10 long randMod = getRandomDelayModulusNanos(timeout, unit);
long stopTime = System.nanoTime() + unit.toNanos(timeout);
21/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Deadlock
while (true) {
2 if (fromAcct.lock.tryLock()) {
try {
4 if (toAcct.lock.tryLock()) {
try {
6 if (fromAcct.getBalance().compareTo(amount) < 0)
throw new InsufficientFundsException();
8 else {
fromAcct.debit(amount);
10 toAcct.credit(amount);
return true;
12 }
} finally {
14 toAcct.lock.unlock();
}
16 }
} finally {
18 fromAcct.lock.unlock();
}
20 }
if (System.nanoTime() < stopTime)
22 return false;
NANOSECONDS.sleep(fixedDelay + rnd.nextLong() % randMod);
24 }
22/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Otevřená volání
1 class Taxi {
@GuardedBy("this") private Point location, destination;
3 private final Dispatcher dispatcher;
5 public Taxi(Dispatcher dispatcher) {
this.dispatcher = dispatcher;
7 }
9 public synchronized Point getLocation() {
return location;
11 }
13 public synchronized void setLocation(Point location) {
this.location = location;
15 if (location.equals(destination))
dispatcher.notifyAvailable(this);
17 }
19 public synchronized Point getDestination() {
return destination;
21 }
23 public synchronized void setDestination(Point destination) {
this.destination = destination;
25 }
}
23/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Otevřená volání
class Dispatcher {
2 @GuardedBy("this") private final Set<Taxi> taxis;
@GuardedBy("this") private final Set<Taxi> availableTaxis;
4
public Dispatcher() {
6 taxis = new HashSet<Taxi>();
availableTaxis = new HashSet<Taxi>();
8 }
10 public synchronized void notifyAvailable(Taxi taxi) {
availableTaxis.add(taxi);
12 }
14 public synchronized Image getImage() {
Image image = new Image();
16 for (Taxi t : taxis)
image.drawMarker(t.getLocation());
18 return image;
}
20 }
24/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Otevřená volání
1 class Taxi {
@GuardedBy("this") private Point location, destination;
3 private final Dispatcher dispatcher;
5 public Taxi(Dispatcher dispatcher) {
this.dispatcher = dispatcher;
7 }
9 public synchronized Point getLocation() {
return location;
11 }
13 public synchronized void setLocation(Point location) {
this.location = location;
15 if (location.equals(destination))
dispatcher.notifyAvailable(this);
17 }
19 public synchronized Point getDestination() {
return destination;
21 }
23 public synchronized void setDestination(Point destination) {
this.destination = destination;
25 }
}
class Dispatcher {
2 @GuardedBy("this") private final Set<Taxi> taxis;
@GuardedBy("this") private final Set<Taxi> availableTaxis;
4
public Dispatcher() {
6 taxis = new HashSet<Taxi>();
availableTaxis = new HashSet<Taxi>();
8 }
10 public synchronized void notifyAvailable(Taxi taxi) {
availableTaxis.add(taxi);
12 }
14 public synchronized Image getImage() {
Image image = new Image();
16 for (Taxi t : taxis)
image.drawMarker(t.getLocation());
18 return image;
}
20 }
setLocation → notifyAvailable
getImage → getLocation
25/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Otevřená volání
Otevřené volání (open call)
◾ volání metody, kdy volající nedrží žádný zámek
◾ preferovaný způsob
Převod na otevřené volání
◾ synchronizace by měla být omezena na lokální proměnné
◾ problém se zachováním sémantiky
Možnost globálního zámku
26/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Otevřená volání
class Taxi {
2 @GuardedBy("this") private Point location, destination;
private final Dispatcher dispatcher;
4
public Taxi(Dispatcher dispatcher) { this.dispatcher = dispatcher; }
6
public synchronized Point getLocation() { return location; }
8
public void setLocation(Point location) {
10 boolean reachedDestination;
synchronized (this) {
12 this.location = location;
reachedDestination = location.equals(destination);
14 }
if (reachedDestination)
16 dispatcher.notifyAvailable(this);
}
18
public synchronized Point getDestination() { return destination; }
20
public synchronized void setDestination(Point destination) {
22 this.destination = destination;
}
24 }
27/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Otevřená volání
class Dispatcher {
2 @GuardedBy("this") private final Set<Taxi> taxis;
@GuardedBy("this") private final Set<Taxi> availableTaxis;
4
public Dispatcher() {
6 taxis = new HashSet<Taxi>();
availableTaxis = new HashSet<Taxi>();
8 }
10 public synchronized void notifyAvailable(Taxi taxi) {
availableTaxis.add(taxi);
12 }
14 public Image getImage() {
Set<Taxi> copy;
16 synchronized (this) {
copy = new HashSet<Taxi>(taxis);
18 }
Image image = new Image();
20 for (Taxi t : copy)
image.drawMarker(t.getLocation());
22 return image;
}
24 }
28/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Hladovění
Hladovění (starvation) nastává, pokud je vláknu neustále odpírán
zdroj, který je potřeba k dalšímu postupu
◾ běžné použití zámků je férové
◾ problém při nastavování priorit
t.setPriority(Thread.MIN_PRIORITY); // 1
2 t.setPriority(Thread.NORM_PRIORITY); // 5
t.setPriority(Thread.MAX_PRIORITY); // 10
problém platformové závislosti priorit
možná pomoc pro zvýšení responsivity GUI
◾ typické pokusy o ,,řešení‘‘ problémů
1 Thread.yield();
Thread.sleep(100);
29/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Další typy uváznutí
Livelock
◾ uváznutí, při němž se vlákno (aktivně) snaží o činnosti, která opakovaně
selhává
◾ náhodnostní exponenciální back-off
Ztracené zprávy
◾ o.wait() a o.notify() resp. o.notifyAll nemají mechanismus zdržení
notifikace
◾ pokud vlákno usne na o.wait() později, než mělo být notifikováno přes
o.notify, nikdy se nevzbudí
30/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Hledání problémů
Výpis stavu JVM
◾ SIGQUIT na unixech (ev. Ctrl-/ pokud mapuje na SIGQUIT)
◾ Ctrl-Break na Windows
31/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Hledání problémů
public static void main(String[] args) {
2 final Object a = new Object();
final Object b = new Object();
4
Thread t1 = new Thread(new Runnable() {
6 public void run() {
try {
8 synchronized (a) {
Thread.sleep(1000);
10 System.out.println("t1 - cekam na b");
synchronized (b) {
12 System.out.println("t1 - jsem zde");
}
14 }
} catch (InterruptedException e) {
16 }
}
18 });
32/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Hledání problémů
Thread t2 = new Thread(new Runnable() {
2 public void run() {
try {
4 synchronized (b) {
Thread.sleep(1000);
6 System.out.println("t2 - cekam na a");
synchronized (a) {
8 System.out.println("t2 - jsem zde");
}
10 }
} catch (InterruptedException e) {
12 }
}
14 });
16 t1.start();
t2.start();
33/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Hledání problémů
$ java IntentionalDeadlock
2 t2 - cekam na a
t1 - cekam na b
4 2010-04-22 11:46:25
Full thread dump Java HotSpot(TM) Client VM (16.2-b04 mixed mode, sharing):
6
"DestroyJavaVM" prio=6 tid=0x020b1000 nid=0x164c waiting on condition [0x00000000]
8 java.lang.Thread.State: RUNNABLE
10 "Thread-1" prio=6 tid=0x02149800 nid=0x1b4c waiting for monitor entry [0x0480f000]
java.lang.Thread.State: BLOCKED (on object monitor)
12 at IntentionalDeadlock$2.run(IntentionalDeadlock.java:35)
- waiting to lock <0x243e6928> (a java.lang.Object)
14 - locked <0x243e6930> (a java.lang.Object)
at java.lang.Thread.run(Unknown Source)
16
"Thread-0" prio=6 tid=0x02146c00 nid=0x1a38 waiting for monitor entry [0x0477f000]
18 java.lang.Thread.State: BLOCKED (on object monitor)
at IntentionalDeadlock$1.run(IntentionalDeadlock.java:20)
20 - waiting to lock <0x243e6930> (a java.lang.Object)
- locked <0x243e6928> (a java.lang.Object)
22 at java.lang.Thread.run(Unknown Source)
34/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Hledání problémů
1 "Low Memory Detector" daemon prio=6 tid=0x02121400 nid=0xbd8 runnable [0x00000000]
java.lang.Thread.State: RUNNABLE
3
"CompilerThread0" daemon prio=10 tid=0x02119800 nid=0x1708 waiting on condition [0x00000000]
5 java.lang.Thread.State: RUNNABLE
7 "Attach Listener" daemon prio=10 tid=0x02118400 nid=0x13d0 runnable [0x00000000]
java.lang.Thread.State: RUNNABLE
9
"Signal Dispatcher" daemon prio=10 tid=0x02115400 nid=0x5a0 waiting on condition [0x00000000]
11 java.lang.Thread.State: RUNNABLE
Heap
2 def new generation total 4928K, used 466K [0x243b0000, 0x24900000, 0x29900000)
eden space 4416K, 10% used [0x243b0000, 0x24424828, 0x24800000)
4 from space 512K, 0% used [0x24800000, 0x24800000, 0x24880000)
to space 512K, 0% used [0x24880000, 0x24880000, 0x24900000)
6 tenured generation total 10944K, used 0K [0x29900000, 0x2a3b0000, 0x343b0000)
the space 10944K, 0% used [0x29900000, 0x29900000, 0x29900200, 0x2a3b0000)
8 compacting perm gen total 12288K, used 42K [0x343b0000, 0x34fb0000, 0x383b0000)
the space 12288K, 0% used [0x343b0000, 0x343ba960, 0x343baa00, 0x34fb0000)
10 ro space 10240K, 51% used [0x383b0000, 0x388dae00, 0x388dae00, 0x38db0000)
rw space 12288K, 54% used [0x38db0000, 0x394472d8, 0x39447400, 0x399b0000)
35/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Hledání problémů
Found one Java-level deadlock:
2 =============================
"Thread-1":
4 waiting to lock monitor 0x020d53ac (object 0x243e6928, a java.lang.Object),
which is held by "Thread-0"
6 "Thread-0":
waiting to lock monitor 0x020d6c74 (object 0x243e6930, a java.lang.Object),
8 which is held by "Thread-1"
10 Java stack information for the threads listed above:
===================================================
12 "Thread-1":
at IntentionalDeadlock$2.run(IntentionalDeadlock.java:35)
14 - waiting to lock <0x243e6928> (a java.lang.Object)
- locked <0x243e6930> (a java.lang.Object)
16 at java.lang.Thread.run(Unknown Source)
"Thread-0":
18 at IntentionalDeadlock$1.run(IntentionalDeadlock.java:20)
- waiting to lock <0x243e6930> (a java.lang.Object)
20 - locked <0x243e6928> (a java.lang.Object)
at java.lang.Thread.run(Unknown Source)
22
Found 1 deadlock.
36/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Statická analýza kódu
FindBugs
http://findbugs.sourceforge.net/
37/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Anotace
Vícečlenný tým programátorů – předávání myšlenek
◾ komentáře v kódy
◾ anotace
anotace se dají použít i pro statickou analýzu kódu
import net.jcip.annotations.GuardedBy;
2 // http://www.javaconcurrencyinpractice.com/jcip-annotations.jar
38/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Anotace
Anotace tříd
◾ @Immutable
◾ @ThreadSafe
◾ @NotThreadSafe
Anotace polí
◾ @GuardedBy("this")
monitor (intrinsic lock) na this
◾ @GuardedBy("jmenoPole")
explicitní zámek na jmenoPole pokud je potomkem Lock
jinak monitor na jmenoPole
◾ @GuardedBy("JmenoTridy.jmenoPole")
obdobné, odkazuje se statické pole jiné třídy
◾ @GuardedBy("jmenoMetody()")
metoda jmenoMetody() vrací zámek
◾ @GuardedBy("JmenoTridy.class")
literál třídy (objekt) pro pojmenovanou třídu
39/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Omezování zámků
zrychlení ≤
1
s + 1−s
n
JVM se snaží dělat
◾ eliminaci synchronizací, které nemohou nastat (např. pomocí escape
analysis – lokální objekt, který není nikdy publikován na haldu a je tudíž
thread-local)
◾ kombinace více zámků do jednoho (lock coarsening)
Zbytečně nesynchronizovat
◾ delegace bezpečnosti (thread safety delegation)
◾ omezení rozsahu synchronizace (get in – get out principle, např.
Taxi/Dispatcher)
◾ dělení zámků (lock splitting) – pouze pro nezávislé proměnné/objekty
◾ ořezávání zámků (lock stripping)
◾ RW zámky
Neprovádět object pooling na jednoduchých objektech
◾ new je levnější jako malloc
synchronized (new Object()) {
2 System.out.println("bleeee");
}
40/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Omezování zámků
zrychlení ≤
1
s + 1−s
n
JVM se snaží dělat
◾ eliminaci synchronizací, které nemohou nastat (např. pomocí escape
analysis – lokální objekt, který není nikdy publikován na haldu a je tudíž
thread-local)
◾ kombinace více zámků do jednoho (lock coarsening)
Zbytečně nesynchronizovat
◾ delegace bezpečnosti (thread safety delegation)
◾ omezení rozsahu synchronizace (get in – get out principle, např.
Taxi/Dispatcher)
◾ dělení zámků (lock splitting) – pouze pro nezávislé proměnné/objekty
◾ ořezávání zámků (lock stripping)
◾ RW zámky
Neprovádět object pooling na jednoduchých objektech
◾ new je levnější jako malloc
synchronized (new Object()) {
2 System.out.println("bleeee");
}
41/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Omezování zámků
Podobně jako dělení zámků, ale pro proměnný počet nezávislých
proměnných/objektů
Příklad ořezávání zámků – ConcurrentHashMap
◾ 16 zámků
◾ každý z N hash buckets je chráněný zámkem N mod 16
◾ předpokládáme rovnoměrné rozdělení položek mezi kbelíky
⇒ 16 paralelních přístupů
⇒ přístup k celé kolekci vyžaduje všech 16 zámků
◾ rozdělení kumulativních polí do jednotlivých kbelíků
42/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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
43/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Délka zpracování obrázku
44/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
velikost obrázku čas běhu
640 × 480 124,12983930928
1280 × 720 539,98450298239
1920 × 1080 1529,02398429008
4096 × 2160 10210,09238488922
45/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
velikost obrázku čas běhu
640 × 480 124,12983930928
1280 × 720 539,98450298239
1920 × 1080 1529,02398429008
4096 × 2160 10210,09238488922
46/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Měříme délku výpočtu v Javě
47/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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 kurtosis
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
48/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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
49/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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
50/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
0 5 10 15 20 25 30
100200300400500600
Javové měření
Měření
Čas [ms]
51/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
0 5 10 15 20 25 30
100200300400500600
Javové měření
Měření
Čas [ms]
HotSpot
garbage collector
52/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Soustava jednotek pro informatiky
Zdroj: http://www.icrf.nl/Portals/106/SI_units_diagram(1).jpg
53/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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)
54/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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?
55/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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é
56/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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
57/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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
58/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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
(
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α
59/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Náhodné chyby
aneb proč se běžně pracuje s normálním rozdělením chyb?
Co se stane, pokud m → ∞?
◾ 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
60/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Binomické vs. normální rozdělení
Srovnání binomického a normálního rozdělení pro p = 0,5 a n = 6
0 1 2 3 4 5 6
k
P[X=k]
0
0.05
0.15
0.25
0.3
0.2
0.1
Zdroj: http://en.wikipedia.org/wiki/File:Binomial_Distribution.svg
61/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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ů
62/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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
63/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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)
64/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Odhad spolehlivosti
x = (ˆµx ± zx) [jednotka]
Pro normální rozdělení chyby
zx = t(p;n−1)sx
H
H
HHn
P
0,683 0,954 0,99
H
H
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
65/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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
66/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu 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
67/67
ThreadPoolExecutors Revisited Uváznutí Optimalizace výkonu Měření
Skripta Fr. Šťastného (Sťastný, 1997)
http://amper.ped.muni.cz/jenik/nejistoty/