Test Questions Flashcards
See picture
The Actor Model uses direct naming to adress other computational units, whereas CSP uses indirect naming (port/channels).
MPI is an implementation of message passing and uses ideas from both concepts. The communicators in MPI correspond to indirect naming in CSP. The idea of passing messages between computational units originated from the Actor Model first and is also present in MPI.
Name and briefly explain three criteria that a valid wait-free consensus protocol must fulfill.
wait-free: returns in finite time for each thread
consistent: all threads decide on the same value
valid: the decision is some thread’s input
Assume the state diagram of a binary consensus protocol for N threads has height h, the initial state is at height 0.Proof or disprove the following Lemma:If the consensus protocol has a critical state at height x for
1 ≤ x ≤ h −1 then it cannot have a second critical state atheight x + 1
See picture
Give a two-thread history that is sequentially consistent, but not lineariz-able. Use a single atomic register r that initially contains the value zero and supports the operations read and write.
Possible solution:
Initially value = 0
A: r.write(1) A: void B: r.write(2) B: void A: r.read() A: 1
Name three conditions a correct lock/ critical section implementation must fullfill. Briefly explain the meaning of each condition, i.e., give a short defini-tion.
Mutual exclusion. Only one thread must be allowed inside the critical section at any given time.
Deadlock freedom. If threads are trying to enter the critical section, one of them must eventually get in.
Starvation freedom. If any thread is trying to enter the critical section, it must eventually get in.
Give definitions for the following terms(used in the context of linearizability):
1) Equivalent histories
2) Sequential history
3) Well formed history
1) Two histories are equivalent if their per-thread projections are identical ( since H | A = G | A and H | B = G | B.)
2) A history is sequential if:
1. Its first event is an invocation
2. Every invocation, except possibly the last, is immediately followed by a matching response.
3) A history is well formed if the per-thread projections are sequential, so that methods cannot interleave in the same thread. Histories that are not well formed usually do not make sense.
See picture
a) True, there should always be one thread that can acquire the lock and thus make progress
b) False
c) True
d) answer are not sure
e) True
f) False, satarvation freedom provides no guarantee on how long a thread waits if it is “passed”. A counterexample would be the Filterlock, which has starvation freedom, but is not fair.
Use the listed primitives, addition andloops to implement a function voidinc() that increments a shared variableby one. If this task is impossible, explainwhy. Use pseudocode. GIVE CODE
Primitives: Transactional Memory,variables
See picture.
Use the listed primitives, addition andloops to implement a function voidinc() that increments a shared variableby one. If this task is impossible, explainwhy. Use pseudocode. GIVE CODE
Primitives: Locks, variables
See picture
Use the listed primitives, addition andloops to implement a function voidinc() that increments a shared variableby one. If this task is impossible, explainwhy. Use pseudocode. GIVE CODE
Primitives: Atomic Variables (volatile in Java)
Impossible. volatile only guarantees that any write gets written to memory immediately and that any read will read the latest value written to it. Since to increment a variable we first need to read it, then increment it, and lastly write it back to memory, we can’t guarantee that while a thread is incrementing the variable another thread won’t read the yet to be updated value.
Use the listed primitives, addition andloops to implement a function voidinc() that increments a shared variableby one. If this task is impossible, explainwhy. Use pseudocode. GIVE CODE
Primitives: Compare-And-Swap, variables
See picture
Use the listed primitives, addition andloops to implement a function voidinc() that increments a shared variableby one. If this task is impossible, explainwhy. Use pseudocode. GIVE CODE
Primitives: N-thread consensus, variables
See picture.
Explain the difference between Sequen-tial Consistency and Linearizability
Linearizability is a stronger version of sequential consistency, requiring the cross-thread order to be respected. In sequential consistency, this order does not have to be respected and we can reorder invocations as long as program order is maintained.
Give an example of a history that issequentially consistent but not lineariz-able. Concept important
See picture
Can implement mutual exclusion foran arbitrary number of threads.
Say True or False.
Atomic Register
Locks
Compare-and-swap
Transactional Memory
All True
mark all true statements
False (bad interleavings: i++ is equivalent to temp = i + 1; i = temp)
False (synchronized is implemented in java using lock)
False (Lock-free guarantees that some thread finishes in a bounded number of steps)
True
True
False (Deadlock happens when the involved process do not advance to the critical section because they are waiting)
True (Lock = Semaphore(1))
False (We use validate only with optimistic and lazy synchronization.)
True
False
True
