ETHZ D-INFK

Prof. Dr. B. Meyer, Dr. S. Nanz

Concepts of Concurrent Computation Assignments
Spring 2013
Assignment 1: Introduction and challenges of concurrency
ETH Zurich
1 Amdahls Law
1.1 Background
Consider a program where multiple threads operate on a buer. Some threads only read from
the buer and other threads only write to the buer. Any number of readers can simultaneously
operate on the buer. While a writer is operating on the buer, no other writer or reader can
be active on the buer.
Assume a pool of N threads where each reader and writer is a thread. Hereby, 90 % of the
threads are readers and 10 % of the threads are writers. Each reader thread takes 2 seconds to
execute and each writer thread takes 3 seconds to execute. The program terminates when all
threads in the thread pool terminated.
1.2 Task
According to Amdahls Law, what is an upper bound for the speedup of the above implemen-
tation on a 4-core processor?
1.3 Solution
S =
1
1 p +
p
n
p =
0.9 2
0.9 2 + 0.1 3
With n = 4 this results in:
S =
14
5
= 2.8
2 Interleavings
2.1 Background
This exercise is taken from the book Principles of Concurrent and Distributed Programming [2].
Imagine two threads P and Q that share the variables K and n.
n := 0
P Q
1 do K times 1 do K times
2 temp := n 2 temp := n
3 n := temp + 1 3 n := temp 1
1
ETHZ D-INFK
Prof. Dr. B. Meyer, Dr. S. Nanz
Concepts of Concurrent Computation Assignments
Spring 2013
2.2 Task
What are the possible nal values of n for a given positive value of K?
2.3 Solution
The nal value of n can be any value between K and K. There are two main cases. Either
P executes one loop iteration between the moment Q reads n in line 2 and the moment Q is
about to write to n in line 3. In this case Q will overwrite the eect of Ps iteration. In the
other case the roles of P and Q are swapped. If the rst case occurs over and over again then
we end up with n = K. In the second case the execution results in n = K. The other possible
combinations of the two cases result in the values between K and K.
3 LTL Models
3.1 Background
We have the following model, M:
b
a a b
q
1
q
2
q
3
q
4
3.2 Task
You are given formulae:
a) Ga
b) aUb
c) a Fb
d) aU(X(a b))
e) Xb G(a b)
f) X(a b) F(a b)
For each of the above formulae, :
2
ETHZ D-INFK
Prof. Dr. B. Meyer, Dr. S. Nanz
Concepts of Concurrent Computation Assignments
Spring 2013
1. Find a path from q
3
that satisies .
2. Determine whether M, q
3
|= .
3.3 Solution
1. Sucessful paths given:
a) q
3
, q
4
, q
3
, q
4
, . . .
b) q
3
, q
2
, . . .
c) q
3
, q
4
, . . .
d) q
3
, q
4
, . . .
e) q
3
, q
1
, q
2
, q
2
, . . .
f) q
3
, q
4
, q
3
, q
1
, . . .
2. Counter-example paths given, where applicable:
a) No, q
3
, q
2
, . . .
b) No, q
3
, q
1
, . . .
c) Yes, a is satised immediately, and either state q
4
or q
2
is entered innitely often.
d) No, q
3
, q
1
, . . .
e) No, q
3
, q
4
, . . .
f) No, q
3
, q
1
, . . .
4 Safety vs. liveness
4.1 Task
Consider the following properties.
1. What goes up must come down.
2. If two or more processes are waiting to enter their critical sections, at least one succeeds.
3. If an interrupt occurs, then a message is printed.
4. The cost of living never decreases.
5. Two things are certain: death and taxes.
6. You can always tell a Harvard man.
For each of the above properties, state whether it is a safety or liveness property. Identify the
bad or good thing of interest.
3
ETHZ D-INFK
Prof. Dr. B. Meyer, Dr. S. Nanz
Concepts of Concurrent Computation Assignments
Spring 2013
4.2 Solution
With respect to the order provided in the question, the answers are as follows.
1. This is a liveness property. The good thing to happen is that the thing having gone up is
coming down.
2. This is a liveness property. The good thing to happen is that at least one processor
succeeds.
3. This is a liveness property. The good thing to happen is the message being printed.
4. This is a safety property. The bad thing that will never happen is that the cost of living
decreases.
5. This is a liveness property. The good thing to happen is death and taxes.
6. This is a safety property. The bad thing that will never happen is that you cannot tell a
Harvard man.
5 Interleavings in practice
5.1 Background
We know that the interleavings in a concurrent program may give rise to dierent behavior.
This exercise is designed to give a way to see how unpredictable these eects may be.
5.2 Task
Your task is to design a Haiku composer. A Haiku is a Japanese form of poetry with 17 syllables
in three lines, where the rst line must contain 5 syllables, the second must contain 7, and the
third line must contain 5 (this is the traditional layout). The lines may contain any number of
words, as long as the syllable restrictions are followed. The Haiku composer will have a small
(20-30 should be enough) list of words, and will spawn 3 threads to compose a Haiku poem.
Each thread is responsible for a single line of the Haiku.
For this task, you must use a single shared store of words. Once a thread has used a word, it
must be removed from the store. You may nd the usage of the java.util.concurrent package
helpful here. The store should have a reasonable number of 1-3 syllable words. It is also perfectly
OK to keep removing words until you nd the one that ts your syllable requirement. You
may wish to dene a Word class which can model a word, including syllable count.
This should be done without using concurrency operations such as synchronized and the
wait/notify capabilities of objects.
To spawn threads and the basics of java concurrency, you may refer to the chapter on Java
concurrency in the course book available at
http://se.inf.ethz.ch/courses/2013a spring/ccc/reading materials/book/.
5.3 Solution
The solution is available in the source code that comes with this solution.
4
ETHZ D-INFK
Prof. Dr. B. Meyer, Dr. S. Nanz
Concepts of Concurrent Computation Assignments
Spring 2013
References
[1] Andrei Voronkov. Script to Logic in Computer Science. 2009.
[2] Mordechai Ben-Ari. Principles of Concurrent and Distributed Programming (2nd Edition).
Addison-Wesley, 2006.
5