4. Pipelining
iii)
Speedup of pipelines vs sequential execution
gives us the speedup of pipeline vs sequential
5. Threads
b)
Ist es möglich die ParallelBlockingQ so zu ändern, dass isEmpty keine Synchro benötigt?
Ja → wir tracken einen AtomicInteger size, der geupdated wird.
isEmpty ist eh inherently racy, weil wir ja immer zuerst Q updaten, dann size.
7. FJ Framework
c)
Wir können auch ohne FJ Pool, vom CommonPool aus unseren Task starten, einfach mit .invoke().
8. State Diagrams
a)
Program is not wait-free.
- if it were, a thread should be able to make progress whilst another is not executing. But for example p1, q1, 0 if p wouldn’t execute, there is no way that q could make progress → taking turns
9. Synchro Strategies
ii)
Using Locks/Variablen
Lock lock = new Lock();
inc(variable x) {
lock.lock();
x++;
lock.unlock();
}iv)
Primitive: Compare-And-Swap, Variablen
do {
int b = a.get();
} while (!a.CAS(b, b+1));v)
This is bullshit anyways
10. Lin
a)
SC vs. Linearizability
The difference:
- SC only demands that there is an equivalent (thread projections identical) sequential history
- Lin. additionally asks for , i.e. for it to respect cross thread order for non-overlapping operations.
Linearizability is composable, while SC is not.
c)
Volatile enforces SC in java, but does not guarantee linearizability.
Since volatile technically only guarantees us a total order on all read/write ops on that variable, but not that it respects real time order (this is a x86 guarantee), we can simply do
A: w(1)-------void r------------1
B: r-------0
which is impossible to linearize, but possible to make SC. And it’s a possible history with volatile (atomic registers).
11. Monitors
a)
use Condition notEmpty = lock.newCondition(); and then notEmpty.await(), .signal/All().